Evolving Self-tuning Benchmarks for Long-Horizon Tool Use
Hyunji Alex Nam, Michael Dennis, Natasha Jaques, Minsuk Chang
cs.AI
2026-10-20
Using a proposer, solver, and feedback model, TURTLE evolves AppWorld tasks until Gemma 4 31B's hard-task share rises from 19.8% to 52.5% and solve rates cluster at 40-60%.
Tool-use benchmarks stall on task authoring. Suites like AppWorld and τ-bench need people to rewrite instructions and align database state, and once a model saturates them someone has to write more. A fresh environment and API set usually fails to plug into an existing harness.
Tasks written only in text often name actions the simulator cannot run. ToolGrad-style pipelines fix the gold tool calls first and then write a matching sentence. Those tasks are solvable, and they read like templates. Random walks on a state-dependency graph stall once the tools and their dependencies multiply.
TURTLE (Tool Use Related Tasks with Long-Horizon Evolution) rewrites instructions and recombines API calls inside sandboxes that already exist. Kept tasks are ones the solver finishes only some of the time.
Three LLMs split the work. The proposer edits a task, the solver attempts it and supplies fitness, and a feedback model compresses traces into a failure note. Search runs through AlphaEvolve, a gradient-free evolutionary loop, so a closed proposer never has to expose weights.
On AppWorld a task is a Python program: initial database, natural-language instruction, gold API sequence, and optional grading rules. If only part of the state changes, the score is the final state from executing the gold solution in the simulator.
Paying the proposer to tank the solver invites vague instructions. The gate is at least one perfect success in 10 tries. Past that gate, six scores use completion rate c and the length L of successful solver trajectories. A bell-shaped target equals 1 at c = 50% and falls to 0.1 at total success or total failure. The learnability term c(1-c) also peaks at 50%. The other four add L only when c is inside 0.3-0.7 or 0.4-0.6. No-op calls padded onto the gold solution showed up early, so L counts only trajectories the solver actually finished.
Mutation instructions on AppWorld are short. After search, each parent keeps the variants with the highest completion-rate variance, ties included. Gemini 3.6 Flash then drops false failures from formatting or paraphrase. AppWorld runs for 1,000 steps and the other suites for 500. In the main run, solver and feedback model are both Gemma 4 31B-it.
On AppWorld, Gemma 4 31B-it splits the original 106 tasks into extremes: 68.9% are solved every time and 12.3% never. The 735 evolved tasks sit almost entirely in the 40-60% band of average completion. That pile-up is what the fitness function pays for, and the final cut keeps high-variance items.
A second reading uses the 1-3 scale. Humans originally scored tasks by interaction and reasoning. Here Gemini 3.6 Flash applies the rubric.
| Set | Tasks | Easy | Medium | Hard | Mean |
| Original AppWorld | 106 | 12.3% | 67.9% | 19.8% | 2.08 |
| TURTLE | 735 | 3.7% | 43.8% | 52.5% | 2.49 |
Hard tasks move from 19.8% to 52.5%, a 165% relative increase. About four fifths of the original set is easy or medium. After evolution, hard tasks are the majority, and the mean moves from 2.08 to 2.49.
Intermediate tool calls sit at 100% on both sides. Every other tracked feature rises by 29-212% relative, and the largest step is from 9.4% to 29.3%. Those features were not written into the mutation prompt. Gemini Embedding 2 (768 dimensions) places the ten farthest original-evolved pairs at cosine distance 0.30-0.49. One original task only asks for a private $68 Venmo transfer to a phone number. The evolved task asks for the user's birth month, coworkers born that month who live in Seattle, a private $75 to each, and a note that depends on age.
AutomationBench grows from 16 tasks to 23. Every original task uses 4 apps. After evolution, 52% need 5 and 13% need 6. Distinct app pairs go from 15 to 30, out of 36 possible unordered pairs, and Banboohr, Google Drive, and Stripe appear.
Feature-by-failure cells go from 49 pairs to 54. The original heatmap misses 11 cells and the evolved one misses 6. Gemini 3.1 Flash Lite treats the artist name Seraphina Dawn as two people and botches the passcode arithmetic. Asked to send a text, Gemma 4 31B-it files a Venmo request for a made-up $1.
| Environment | Parents | Evolved |
| AppWorld (Gemma 4 31B-it) | 106 | 735 |
| τ-telecom | 84 | 299 |
| τ-banking (BM25) | 17 | 82 |
| τ-banking (golden retrieval) | 24 | 178 |
| AutomationBench | 16 | 23 |
The other three suites do not get a difficulty histogram at this resolution. With Gemini 3.6 Flash, 9 seeds produce 22 tasks. With Gemini 3.1 Flash Lite, 64 seeds produce 141. Completion rates again fall toward 40-60%.
The harness can stay. AppWorld's 4,571 APIs, the τ-bench user simulator, and AutomationBench's 47 SaaS apps do not need a rewrite, and new tasks enter the old pipeline. The added cost is inference for mutations and for 10 solves.
A 50% solve rate is the learning frontier in Rutherford et al.: tasks with maximum outcome variance. Those items could feed reinforcement learning with verifiable rewards, or behavioral cloning on successful trajectories only, followed by another round of generation. That loop is not run.
Landing in the 40-60% band means the objective did its job. The hard-label shift from 19.8% to 52.5%, the feature-frequency gains, and the app-pair jump from 15 to 30 are not implied by a completion rate near 0.5. Hard labels and feature tags still come from Gemini 3.6 Flash.
Proprietary inference cost is named as the practical limit. The Gemini ablations use few seeds: 9 for 3.6 Flash and 64 for 3.1 Flash Lite. A larger public set would need more parents.
One judge, Gemini 3.6 Flash, labels difficulty, features, and failure reasons. The original rubric was human, and agreement with people is not reported. Failure coverage only moves from 49 pairs to 54, so the diagnostic claim is thin.
The suite moves with the solver. On a public leaderboard the difficulty would be tuned to the model being scored. The proposer can see the gold solution. Whether instructions stay clear to a person depends on the judge deleting obviously vague items, and no human audit rate is reported.
AutomationBench has 23 tasks, so a jump from 15 app pairs to 30 can swing with a handful of items. Reinforcement learning and behavioral cloning on these tasks remain a proposal.