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

arXiv: https://arxiv.org/abs/2608.02358 · HTML: https://mlsanity.com/paper/2608.02358/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Tool learning and function calling, one of 16 directions in LLM agents and tool use.
- Builds on 8 of its 11 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Placed in

- LLM agents and tool use / [Tool learning and function calling](https://mlsanity.com/agents/tool-learning-and-function-calling/)

## Builds on (most cited first, 8 of 8)

- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [Terminal-Bench: Benchmarking Agents on Hard, Realistic Tasks in Command Line Interfaces](https://mlsanity.com/paper/2601.11868/) (2026)
- [Large Language Models as Tool Makers](https://mlsanity.com/paper/2305.17126/) (2023)
- [On the Tool Manipulation Capability of Open-source Large Language Models](https://mlsanity.com/paper/2305.16504/) (2023)
- [MCP-Universe: Benchmarking Large Language Models with Real-World Model Context Protocol Servers](https://mlsanity.com/paper/2508.14704/) (2025)
- [MCP-Atlas: A Large-Scale Benchmark for Tool-Use Competency with Real MCP Servers](https://mlsanity.com/paper/2602.00933/) (2026)
- [OpaqueToolsBench: Learning Nuances of Tool Behavior Through Interaction](https://mlsanity.com/paper/2602.15197/) (2026)

## Built on by (most cited first, 1 of 1)

- [MNIST-PRO: MNIST is Back as a Partially Observable World for AI Agents](https://mlsanity.com/paper/2608.31022/) (2026)

## Abstract (arXiv)

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.