Task-CoEvolve: Efficient Harness Optimization via Adaptive Validation Task Selection
Atsuyuki Miyai, Kiyoharu Aizawa, Toshihiko Yamasaki
cs.CL, cs.AI, cs.LG
2026-08-20
Samples validation tasks by Bernoulli variance and scores via inclusion probability. Hits 49.3% vs 48.6% full search at 20% budget; Terminal-Bench within 1.1 points.
Automated harness optimization rewrites the code around a frozen LLM, scores each rewrite on a validation set, and keeps the better version. Changing that layer around a fixed model has been shown to swing the same benchmark by as much as 6×. Meta-Harness and similar loops evaluate the entire validation set every iteration. That is cheap on short classification items and brutal on Terminal-Bench, where a single sandbox task can run for tens of minutes.
The evaluation is also static. Once the harness improves, items that every candidate already solves, or that none can solve, still consume budget and give almost no ranking signal.
The paper asks a narrower question than how to propose better harnesses: given a limited number of task executions, which validation tasks should each candidate see, and how can those partial scores stay comparable across iterations.
Task-CoEvolve co-evolves the validation subset with the harness. Selection and scoring look only at historical pass/fail; they never read the task text or the harness source.
Phase 0 is already paid for. Search has to run two starting harnesses on the full set so the meta-agent has something to rewrite. Those outcomes become the initial per-task success rates p̄t.
Each later iteration draws m=⌈ρN⌉ tasks with variance-weighted sampling. The weight is Bernoulli variance p̄t(1-p̄t), largest near 0.5 and zero when a task is always solved or always failed. Never-solved tasks get a floor ℓ=0.125 so they are not dropped forever. Tasks with few observations get an extra λ/√nt bonus (λ=0.025) so a couple of early flukes cannot exile them.
A raw subset mean is not usable. A frozen subset overfits; a freshly drawn subset has a different difficulty, so scores from two iterations are not on the same scale. The method estimates the full-set score Ŝ(h) with inclusion probabilities πt (Horvitz-Thompson). Text classification uses the Hájek form, weighting by 1/πt, because per-dataset success rates sit near 0 or 1. Terminal-Bench uses an anchored residual estimator: weight xt(h)-p̄t rather than xt(h). The appendix records why. On one Qwen run a candidate scored 33.3% on three tasks and Hájek reported Ŝ=85.9%, after a rarely sampled, almost-always-solved task dominated the sum.
Final pick is the candidate with the highest Ŝ. Ties go to the earliest iteration; Ŝ is continuous and never tied in these runs.
Online text classification follows Meta-Harness: GPT-OSS-120B as the classifier, Claude Opus 4.6 as the meta-agent, 20 iterations, three candidates each. About 130 validation items across LawBench, Symptom2Disease, and USPTO-50k.
| Method | ρ | Evals | Avg accuracy |
| Few-shot | - | - | 41.6% |
| Meta-Harness full | 100% | 7,800 | 48.6±0.8% |
| Naive fixed subset | 7% | 480 | 45.2±3.2% |
| Random-Resample | 7% | 480 | 47.0±2.2% |
| Task-CoEvolve | 7% | 480 | 47.6±0.9% |
| Task-CoEvolve | 20% | 1,560 | 49.3±0.8% |
At 7% budget the selected harness reaches 47.6%, 6 points above few-shot, with 1/16 of the full-search evaluations. At 20% it reaches 49.3% and beats full search by about 0.7 points. The paper attributes the reversal to full-search overfitting the validation set. Ablation at 20%: rotating the subset is the largest single step (47.2 to 48.2), then estimation (+0.6), then variance-weighted sampling (+0.5).
Terminal-Bench 2.1 has 89 tasks. Search and final eval share that pool because a split would starve an already expensive benchmark. GPT-5.6-Luna and Qwen3.6-35B-A3B, 10 iterations, one candidate each, one rollout per task.
| Method | ρ | GPT-5.6-Luna | Qwen3.6 | Avg |
| Terminus 2 start | - | 52.8 | 34.8 | 43.8 |
| Full search | 100% | 62.9 | 42.7 | 52.8 |
| Naive | 20% | 55.1 | 39.3 | 47.2 |
| Rotation | 20% | 59.6 | 37.1 | 48.4 |
| Task-CoEvolve | 20% | 61.8 | 41.6 | 51.7 |
Average gap to full search is 1.1 points, one task out of 89. Full search sees every final-eval task every iteration, so the comparison is stacked. Task-CoEvolve still lands next to it at 20% of the evaluations.
Cost: GPT-5.6-Luna full search uses 2,888M input tokens, $117, 22.2 hours. Task-CoEvolve uses 579M, $30, 11.5 hours (80% fewer input tokens). Self-hosted Qwen3.6 drops from 38.0 to 20.5 hours and 67% fewer tokens. Random-Resample at the same 20% task budget cuts tokens 96%, because it also draws short, easy tasks. Variance-weighted sampling concentrates on long, multi-turn items where candidates disagree (3.2M tokens per trial, same as full search) and still wins by 3.3 points. Wall time only halves: 10-way parallelism is gated by the slowest task, and the meta-agent spends a fixed 2.4 to 3.3 hours proposing code.
The pool is lopsided. Tasks that nobody solves or that almost everybody solves stay above 70% of the pool. The most discriminative band (success between 1/3 and 2/3) is 10% of text-classification items and 24% of Terminal-Bench. The mix also moves: "almost everybody solves it" on text classification rises from 34 to 58 items; "nobody solves it" on Terminal-Bench falls from 32 to 21.
Ŝ is a coarse ranker. Re-scoring all 60 candidates from one run on the full 130-item val set: Spearman 0.62 at ρ=20%, and the Ŝ winner is 12th of 60 (51.3% vs true best 54.7%). At ρ=7% Spearman falls to 0.13; the pick is still 10th of 60. It avoids disasters more than it finds the optimum.
The expensive part of harness search is often not proposing code. It is running the validation set to the end, every round. Prior efficiency work (ShinkaEvolve, TurboEvolve, HarnessCompass) spends fewer candidates. This paper spends fewer tasks per candidate. The two stack.
Beating full search at 20% on held-out text classification is the cleaner number: rotating toward frontier tasks can act as a regularizer, not only a cheaper approximation. On Terminal-Bench, cutting evaluations to one-fifth and tokens to one-fifth through one-third, with search time from a day to half a day, is already operational.
The token math is less pretty than the evaluation-count math. Variance weighting parks budget on the slowest tasks. Matching Random-Resample's token cut costs 3.3 points.
Headroom shrinks with model strength. Appendix full-search on DeepSeek-V4-Flash: Terminus 2 already at 70.8%, best of ten candidates still 70.8%. A better evaluation protocol cannot invent scaffolding gains that the model no longer needs.
The paper states the main one: the number of tasks per candidate is fixed before any of its results arrive. There is no early stop for a clearly worse rewrite, and no extra budget when two candidates are close.
Estimator choice is manual. Swap Hájek onto Terminal-Bench or residuals onto text classification and accuracy drops by about 3 points, or a 33.3% raw score inflates to 85.9%. Phase 0 inspects the pool and picks a form. That is another knob, with no automatic rule for a new benchmark.
Terminal-Bench search and final eval share the 89 tasks. Full search has seen the test distribution every iteration. The held-out text-classification reversal is the cleaner claim.
At 7% budget, Ŝ barely ranks (Spearman 0.13). "Nearly matches full search" describes the selected harness on the test set, not the reliability of the search-time ranking.
ℓ and λ are shared across both settings (0.125 / 0.025) with no sensitivity sweep.