ScrambleToolBench: Agents Search Exhaustively Even When Their Own Map Points to the Next Step
2026-08-03 • Computation and Language
Computation and Language
AI summaryⓘ
The authors created ScrambleToolBench, a new test that makes autonomous agents learn how tools work just by trying things out, without any hints. This test changes over time, adding challenges like random failures and shifting rules, to see if agents can adapt their guesses about how things work. Their study shows that even smart language models struggle to adjust when the environment changes, often repeating the same mistakes or resorting to slow trial-and-error. Giving the agents memory helps a bit but doesn't fix the core problem of understanding changes quickly. Overall, the authors highlight that current AI agents are not yet good at figuring out and adapting to unexpected changes on their own.
autonomous agentstool-use benchmarksbehavioral reasoningtrial-and-error interactionmapping driftstochastic action failurestemporal execution windowsdeductive strategiesbelief inertiapersistent memory
Authors
Vernon Toh, Navonil Majumder, Zhengyuan Liu, Nancy F. Chen, Soujanya Poria
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.