The Map Was There, They Searched Anyway: Reviewing ScrambleToolBench

Source Document

Vernon Toh, Navonil Majumder, Zhengyuan Liu, Nancy F. Chen, Soujanya Poria, "ScrambleToolBench: Agents Search Exhaustively Even When Their Own Map Points to the Next Step", arXiv:2608.02358 [cs.CL], submitted 2026-08-03, DOI 10.48550/arXiv.2608.02358. Affiliations: DeCLaRe Lab, Nanyang Technological University, and A*STAR, Singapore; corresponding author Soujanya Poria.

This is a preprint that has not been peer reviewed, filed primarily under Computation and Language (cs.CL). We checked both the HTML full text and the abstract page and found no funding statement and no conflict-of-interest disclosure — a common omission in benchmark papers, but worth recording given that fifteen commercial and open-weight models are ranked here. The document is licensed CC BY-SA 4.0.

Study Overview

The benchmark asks whether an agent facing an undocumented system can infer how its tools behave through interaction alone, and — having inferred it — whether it can revise that belief when the environment shifts underneath it. Existing tool-use benchmarks expose semantic schemas such as send_email, so a model can answer from prior knowledge while appearing to have discovered something. The authors cut that confound by stripping every semantic cue from tool identifiers inside an interactive terminal environment.

The unit of measurement is an episode: a curriculum of five sequential tasks, with 20 episodes run per condition and an action budget of 100 inference steps per task. Five conditions are separated cleanly — a control that keeps semantic names (Unscrambled), identifier anonymisation only (Base), mid-episode remapping of 25% of functions (+Drift, ρ_drift=0.25), stochastic timeouts at 15% probability (+Failure, p_fail=0.15), a hard ten-action execution window (+Window, k=10), and all three at once (+All). Fifteen models were evaluated without memory; four of them were re-run with persistent memory attached.

Three metrics carry the results. P_ep is the share of episodes in which all five tasks were solved, T_avg is the mean number of tasks solved (0–5), and A_avg is the mean total action count computed over successful episodes only. That last qualifier matters for interpretation: runaway failures never enter A_avg, so real-world waste is larger than the table shows.

Key Results

Condition-level means across the fifteen no-memory models (Table 2) are below. The two columns use different bases — the first counts only fully completed episodes, the second credits partial progress.

The averages read as "remove the names and everything collapses," but the frontier rows tell a sharper story. Claude Sonnet 5 held a perfect 1.00 completion rate under drift alone and under stochastic failure alone, then dropped to 0.00 when the same perturbations were combined. Surviving each fault in isolation is a different capability from surviving them together.

The cost axis moves faster than the accuracy axis. Mean actions on successful episodes (Table 3) rose for Gemini 3.1 Pro from 25.1 in the control to 80.8 at Base and 152.4 under drift; Claude Sonnet 5 went 25.6 → 115.8 → 193.6. That is a six- to eightfold increase measured only on the runs that worked.

The result behind the title sits in Tables 4 and 5. The authors derive an expected recovery cost of 4.25 extra actions per drift event if an agent simply cycle-traces the mapping it has already built. Observed recovery ran far above that reference: averaged over tasks 2–5, Gemini 3.1 Pro at high reasoning spent 5.57× the expected cost, and Claude Sonnet 5 spent 8.94×, 7.38× and 7.52× at low, medium and high reasoning respectively. More thinking did not make recovery cheaper. Table 5 explains why: the rate at which a model called the next identifier in the recovery chain within three actions was 11.0% for Gemini 3.1 Pro against a random-selection baseline of 10.8% (p=0.934), and 14.1% versus 10.6% for Claude Sonnet 5 at high reasoning — statistically significant (p=0.006), but a 3.5-point gap.

Memory helped only at the margin: averaged over the four memory-augmented pairs, the combined condition improved by +0.09 P_ep and +0.59 T_avg. Failure styles, by contrast, split sharply. For Claude Sonnet 5, 97.5% of failures were budget exhaustion and only 2.5% early exits, while GPT-OSS 20B and Gemma 4 31B failed by early exit 100% of the time.

Credibility Assessment

Three design choices earn trust. Running a semantic-cue control alongside the scrambled conditions separates what models knew in advance from what they discovered. Splitting perturbations into drift, failure and time window with published parameters makes attribution possible — you can say which factor broke what. And reporting behavioural metrics (action counts, retry rates, stale tool calls) alongside pass rates, with a random baseline and p-values on chain-following, is more discipline than most agent benchmarks show.

The caveats are equally concrete. Twenty episodes per condition quantises P_ep to 0.05, so a gap between 0.20 and 0.25 is a single episode; ranking models by decimals is not supportable at this sample size. The environment is a Python simulator rather than a live Docker container, and drift is a bijective permutation — gentler than real API changes that also alter arguments and return types. The parameters ρ=0.25, p=0.15 and k=10 are design choices, with no sensitivity analysis showing the pattern holds elsewhere. There is no dedicated limitations section, no funding or conflict disclosure we could locate, and the work has not been peer reviewed.

Reviewer's Judgement

First, the most expensive number here for practitioners is not the 0.03 average but the Claude Sonnet 5 row: 1.00 under drift alone, 1.00 under failure alone, 0.00 when combined. Passing fault-injection tests one fault at a time certifies nothing about concurrent faults — and in production, faults rarely arrive alone. Agent evaluation has not internalised that operational commonplace.

Second, 11.0% against 10.8% is one of the coldest numbers this series has reviewed. After drift, models did not narrow the candidate set using the mapping they themselves had built; they swept tools in an order statistically indistinguishable from random. Even where significance appeared, a 3.5-point edge reads less like deductive recovery and more like occasional luck. Recording state and reasoning over that state are evidently different things.

Third, the risk surfaces in spend before it surfaces in accuracy. The jump in A_avg from 25 to 152 is measured on episodes that succeeded; the episodes that failed ran to the budget ceiling instead — 97.5% of Claude Sonnet 5's failures were budget exhaustion. On the day a tool schema changes quietly, the first thing to move on your dashboard is the token bill, not the error rate.

Fourth, budget exhaustion and early exit are different incidents and deserve different alarms. The former is a cost and latency event; the latter (100% of failures for GPT-OSS 20B and Gemma 4 31B) is a silent one, returning an incomplete result without complaint. Monitoring that tracks only a completion rate will miss the quiet failure entirely.

Putting It to Work

• Combined-perturbation regression suite — exercise schema drift, intermittent tool failure and time limits both individually and simultaneously in staging. Passing them separately is not a release criterion.
• Action budgets with overrun alerts — cap actions and tokens per task, and log any successful run that spent three times its usual budget as its own event. Cost creep on the success path is the earliest signal available.
• Separate the failure modes — count budget exhaustion and early exit as distinct metrics, and attach an "incomplete result returned" alert to the latter so silent failures surface.
• Track stale tool calls — measuring how often an agent calls identifiers that have already changed shows exactly how long it clings to an outdated hypothesis.
• Treat a model swap as a re-measurement event — even a stronger model from the same vendor differs in combined-condition performance and in how it fails. Re-run the same suite and keep the comparison.

Conclusion

ScrambleToolBench exposes the gap between using tools and re-learning them after they change. Given 20 episodes per condition, the patterns travel better than the absolute values: collapse under combined perturbation, recovery search indistinguishable from random, and a six-fold action cost even on the successful path. For the rubric side of this problem, see Designing an AI Agent Evaluation Rubric.

References

• ScrambleToolBench: Agents Search Exhaustively Even When Their Own Map Points to the Next Step — arXiv abstract (source)
• Full HTML text of the same paper — used to verify Tables 2–5
• Designing an AI Agent Evaluation Rubric — sunny34.com blog