ScrambleToolBench: Agents Search Exhaustively Even When Their Own Map Points to the Next Step

2608.02358 ↗ · 2026-08-03 · cs.CL · h-max 80 · 0 citations

Vernon Toh, Navonil Majumder, Zhengyuan Liu, Nancy F. Chen, Soujanya Poria

The finding

Headline claim

Current LLM agents fail to use deductive reasoning when tool mappings shift unexpectedly, collapsing from 93% to 3% episode completion under combined dynamic conditions and resorting to exhaustive brute-force search even when their own internal map could guide recovery.

The test

20 five-task evaluation episodes per model on ScrambleToolBench, a terminal benchmark with 28 obfuscated API tools and 20 procedural task templates. Tested 15 models (open-source and proprietary, including Claude Sonnet 5, Gemini 3.5 Flash, GPT-5.4, Qwen 3.6 27B, and others) across six conditions: unscrambled baseline, plus four independent dynamic stressors (mapping drift, stochastic action failure, temporal execution windows) and all combined. Memory-augmented variants tested for four models.

Effect size & scope

Aggregate episode completion rate (mean across 15 no-memory models) falls from 0.93 in the unscrambled baseline to 0.03 under all combined dynamics, a drop of 0.90. Average tasks solved falls from 4.88 to 0.84 out of 5. Best-performing individual model (Claude Sonnet 5) achieves 1.00 completion under drift alone and stochastic failure alone but drops to 0.00 under the combined condition. Persistent memory improves aggregate completion by +0.09 on average under combined conditions but does not recover full performance; no memory-augmented model exceeds 0.50 completion under all dynamics.

Limitations

Authors concede: the environment is a lightweight Python simulator rather than a live Docker system, which may reduce ecological validity. The task pool is limited to 20 templates and 28 tools, so generalization to richer real-world APIs is unproven. Semantic obfuscation represents an intentional worst-case scenario that may not reflect the partial-semantic conditions most common in practice. The memory baseline is a single schema design (Appendix A) rather than a search over memory architectures. Only one cycle-tracing recovery strategy is analyzed analytically, and it was never spontaneously discovered by any agent.

Counterpoint

The benchmark is a deliberately adversarial worst-case: fully obfuscated identifiers are rare in real deployments, so the 0.03 collapse figure may overstate fragility for practical use. The simulator is not a live environment, raising questions about whether failure modes would manifest identically in production systems. With only 20 episodes per condition, variance estimates are wide. The best model (Claude Sonnet 5) performs perfectly under several individual stressors, suggesting the combined condition may be measuring benchmark extremity rather than a broadly reproducible reasoning failure. Benchmark novelty also makes independent replication impossible at time of publication.

Economy implication

In the 12 to 24 month horizon, these findings complicate enterprise deployment of autonomous agents in environments with evolving or poorly documented APIs, a common real-world scenario. If agents revert to exhaustive search when tool behavior drifts, token and inference costs per task spike sharply, eroding the ROI case for unattended agentic pipelines. Operators will likely need human-in-the-loop checkpoints or explicit memory and monitoring infrastructure, adding integration cost. Little direct revenue or market impact is measurable from a single benchmark paper, but the result adds evidence that current agents are not ready for reliably autonomous operation in non-stationary tool environments.

Who this matters for

Technical Capability: The benchmark isolates a specific and previously unmeasured reasoning gap: agents cannot translate a correct internal model into deductive recovery when mappings shift, and scaling test-time compute worsens token cost without fixing the failure.

Market & Valuation: Enterprises evaluating agentic products for IT operations, API orchestration, or system administration tasks should note that even top-tier models collapse under realistic dynamic conditions, raising questions about readiness and TCO for unattended deployments.

Bears on (advisory · papers never write evidence)

[1.3] Agentic reliability (multi-step completion without human correction) is improving materially, not just peak single-shot.

[3.3] Enterprises achieve measurable ROI and renew / expand, not just pilot.

[B1] Agentic reliability gains will translate into enterprise ROI.

Abstract

To operate robustly in open-world environments, autonomous agents should be able to infer the behavior of unfamiliar systems through interaction alone, even in the absence of documentation. However, existing tool-use benchmarks expose semantic tool schemas in static environments, allowing agents to rely on prior knowledge rather than autonomous discovery. To address this limitation, we introduce ScrambleToolBench, an interactive terminal benchmark designed to isolate behavioral reasoning. By removing semantic cues and enforcing a continuous task curriculum, the benchmark requires agents to uncover hidden tool behaviors entirely through trial-and-error interaction. The benchmark further introduces dynamic challenges, including mapping drift, stochastic action failures, and temporal execution windows, to evaluate whether agents can revise and adapt their hypotheses as the environment changes. Our evaluation of state-of-the-art language models reveals that successful initial discovery does not translate into robust adaptation. When faced with structural changes such as mapping drift, agents fail to use deductive strategies such as cycle tracing, and instead exhibit belief inertia or fall back to exhaustive search. Increasing test-time reasoning only amplifies this expensive brute-force search rather than enabling deductive recovery. While equipping agents with persistent memory reduces compounding errors, they remain unable to efficiently infer structural changes, highlighting a gap in current agent reasoning.