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

Suppose an agent has worked out which command reads a file and which one queries a database. It has written the names down and used both successfully. Then the interface changes. The command that used to read a file now calls a different function.

The agent could try every command again. But the unexpected response contains a clue: it tells the agent which function has moved into that name. Its old map can tell it where that function used to be. Together, those two observations suggest a specific next call.

We built ScrambleToolBench to examine what agents do at moments like this. The strongest models can discover unfamiliar tools and complete tasks with them. Recovering cheaply after a change is harder. Even with the relevant entries in memory, they rarely follow the chain those entries imply.

This connects to a question from my MNIST-PRO note: when an agent has already gathered useful evidence, what stops it from using that evidence? Here the evidence is a tool’s behavior rather than a fragment of an image. We can inspect the next action to see whether the agent has made the connection.

What the tool names normally tell you

A name such as read_file gives an agent a useful starting hypothesis. It suggests both the operation and the kind of argument to supply. That is helpful in practice, but it makes it difficult to tell how much an agent has learned from the current environment and how much it brought with it.

ScrambleToolBench removes these cues from 28 tools for file operations, network diagnostics and data processing. A tool receives an arbitrary name such as fn_3d8a. Its parameter names are replaced with tags such as arg_0, and the initial schema does not list them. A malformed call reveals the required keys and types. Output fields and success indicators are also obfuscated, so the agent has to interpret the responses it receives.

The environment is a Python simulator, with 20 procedural task templates. An episode contains five tasks, each with a budget of 100 inference steps. The tasks share a history: a discovery made while investigating a service can be useful later when locating a file or retrieving a value. Three control commands, including submit_solution, remain readable so that submitting an answer does not itself require tool discovery.

We then change the conditions in three ways. Mapping drift moves seven of the 28 tool identifiers in a cycle between tasks. Action failure makes valid executions return a timeout with probability 0.15. Execution windows require certain procedures to finish within ten actions of a trigger; an expired window resets the state and regenerates intermediate values. We test each change separately and all three together.

These changes require different responses. A timeout can justify retrying a correct call. A changed mapping requires revising which command to use. An expired window requires restarting the procedure rather than reusing values from the previous attempt. An agent that treats all three as the same kind of error will waste calls or carry an incorrect assumption forward.

Discovery can succeed while adaptation fails

The main evaluation uses 20 five-task episodes per model and condition. Episode completion means solving all five tasks. With 20 episodes, one completed episode changes the reported completion rate by five percentage points.

The selected results below show why the changing environment matters. Claude Sonnet 5, Gemini 3.1 Pro and Gemini 3.5 Flash all complete every episode in the static scrambled setting. Under the three combined changes, their completion rates fall to 0%, 20% and 25%.

These are selected rows from Table 2 of the paper. The mean includes the full set of 15 no-memory models, not just the four displayed here. A dash denotes an unreported condition, not zero performance.

The memory variant maintains two structured stores: task recipes and tool knowledge. One records reusable procedures; the other records inferred tool behavior, arguments and confidence. The agent updates these stores as it acts. For Gemini 3.1 Pro, memory raises completion in the combined condition from 20% to 50%. That is a useful gain, but it leaves another question: does the agent use its remembered map to reason about the change, or does it simply search more successfully?

A wrong call can tell you where to look next

Consider a small illustrative example. Before a change, command A reads files, B queries the database and C lists interfaces. After the names rotate, A lists interfaces, C queries the database and B reads files.

The agent wants to read a file, so it starts with A. The response identifies the interface-listing function. The old map says that function used to be at C, so C is the next place to look. C now returns the database function, whose old name was B. Calling B reaches the file reader. The route is A → C → B; the agent did not need to scan the remaining commands.

That is cycle tracing. After a mismatch, identify the function that answered, look up its previous identifier, and call that identifier next. Repeat until the required function appears. The stable, function-specific response fields let the agent match a response to an earlier observation even when the command name changes.

For the benchmark’s seven-identifier cycle, this takes six extra calls relative to an ordinary successful tool call. That guarantee assumes the stored map was current immediately before the drift and the returned functions can be identified. The same calls reveal the changed part of the map, allowing it to be repaired before the next task. If the map mixes unresolved observations from several changes, the six-call bound no longer follows.

The paper also gives a reference for a task requiring four of the 28 functions. With seven identifiers chosen uniformly for drift, the probability that at least one required function moved is one minus the probability that all four stayed unchanged. Multiplying that probability by six gives 4.25 expected extra actions at one fresh task boundary. This is a recovery reference under the stated assumptions, not a bound on the cost of discovering the whole environment or handling the combined stressors. The derivation is in Section 4.2.

Do agents follow that clue?

We measure whether, after observing a changed mapping, the agent calls the next identifier in the chain within three actions. The comparison is with random selection among identifiers the agent has already mapped.

The opportunity counts are diagnostic events, not independent episodes; the analysis excludes early-exit episodes as described in Table 5. Gemini’s follow rates are close to the random baseline, including with memory. Sonnet is modestly above it at low and high reasoning, but increasing reasoning does not make it follow the chain more consistently. These results do not mean that no useful deduction ever occurs. They show that this particular recovery rule is not used reliably.

One trajectory makes the alternative behavior easy to recognize. Qwen 3.6 27B had used fn_fc40 for file search. After drift, it kept varying the arguments to that name over a seven-step loop, trying different search patterns instead of reconsidering which function the name now referred to. The agent was changing its query while keeping the more consequential assumption fixed.

Memory can also be revised sensibly. In another episode, Gemini 3.1 Pro explicitly cleared its old tool mappings while retaining task progress and critical details. Under an execution window, Gemini 3.5 Flash stopped making exploratory calls and focused on the required sequence. These examples show useful local adaptation. They also explain why a single success rate cannot tell us whether the agent found the cheaper recovery procedure.

More reasoning improves completion, but not the shortcut

We vary the reasoning effort for Gemini 3.1 Pro and Claude Sonnet 5 in both the static scrambled environment and the drift condition. Higher effort improves the number of tasks completed, especially for Gemini. The chain-following results above show that this improvement should not be mistaken for reliable cycle tracing.

Completion tokens per solved task count tokens spent across all episodes, including failed ones, and divide by the total number of tasks solved. At high reasoning under drift, Sonnet uses 11,652 tokens per solved task, compared with Gemini’s 3,332—about 3.5 times as many at similar task completion.

The cost does not rise monotonically with reasoning effort. Sonnet’s low-effort drift setting is the most expensive per solved task; Gemini’s cost changes little across effort levels. The distinction is between completing more tasks and adopting a more economical strategy. A larger reasoning budget can improve the former while leaving the latter largely unchanged.

The connection to MNIST-PRO

In MNIST-PRO, an agent moves a small window over a handwritten digit. It may collect many useful fragments and still give the wrong answer. In ScrambleToolBench, it may identify a changed function and retain the relevant earlier mapping, yet choose an unrelated command next. Both failures happen after useful evidence has reached the agent.

The two benchmarks let us investigate that gap in different ways. For MNIST-PRO, we keep a completed trajectory fixed and assemble its observed glimpses into a coordinate-aligned canvas. No new region becomes visible. If the final answer improves, a better search path cannot explain the gain: organizing the existing observations has helped. For example, on Claude Opus 5’s Textual State trajectories, this changes Level 1 accuracy from 41% to 76% and Level 2 accuracy from 13% to 67%.

For ScrambleToolBench, we inspect a decision rather than supply a consolidated view. Once a changed call returns a known function, does the agent use its old map to choose the next identifier? The low follow rates show that storing the relevant entries does not reliably produce that action. We have not shown here that a different memory format would fix the problem; the MNIST-PRO canvas result is not evidence that the same intervention works for tool use.

There is also an important difference in what changes. The digit in MNIST-PRO stays still. An early guess may be wrong, or the agent may have failed to join its views together, but a previously observed stroke does not move. ScrambleToolBench deliberately changes the interface: a mapping that was correct can become stale. The first task calls for constructing and interpreting a state from partial views; the second additionally calls for revising that state when the environment changes.

This is why I would not treat either result as a general argument for more memory. A history can preserve the right observations without exposing their spatial relationship. A tool dictionary can preserve a correct old mapping without prompting the reverse lookup that would make it useful now. The question is what the stored information allows the agent to do at the next decision.

What I would test next

For tool use, I would separate three checks: whether the map contains the needed entries, whether the agent recognizes a mismatch, and whether it follows the implication of that mismatch. A controlled intervention could provide the current pre-drift map, then test a reverse-lookup rule only when a response identifies a displaced function. That would help distinguish incomplete discovery from a failure to use information already available. It is a proposed test, not a result reported here.

For perception, the corresponding check is to hold the path fixed before changing how its observations are represented. If the agent never saw the second digit, a better arrangement of its existing glimpses cannot supply it. If it did see the distinguishing strokes, the next question is whether it can use them together.

The practical aim is to locate the missed step. In ScrambleToolBench, an error response can be the observation that tells the agent where to call next. In MNIST-PRO, several individually ambiguous crops can become a recognizable digit when placed together. An agent needs to carry those relationships into its decisions, not just carry the observations into its context.

Citation

@misc{toh2026scrambletoolbenchagentssearchexhaustively,
  title={ScrambleToolBench: Agents Search Exhaustively Even When Their Own Map Points to the Next Step},
  author={Vernon Toh and Navonil Majumder and Zhengyuan Liu and Nancy F. Chen and Soujanya Poria},
  year={2026},
  eprint={2608.02358},
  archivePrefix={arXiv},
  primaryClass={cs.CL},
  url={https://arxiv.org/abs/2608.02358}
}