acceptodds
Under review as a conference paper at ICLR 2027

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

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 reveals that initial discovery does not translate into robust adaptation. Removing semantic priors reduces mean completion from 93% to 32%, which falls to 3% under combined dynamic stress. When mappings shift, agents exhibit belief inertia or search exhaustively rather than following the displacement pointers recorded in their own map. Increasing test-time reasoning improves completion rates and reduces redundant actions, but it relies on broad exploration rather than structured 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.

Primary area:
datasets and benchmarks
Keywords:
AI Agents, Tool-Use Benchmark, Behavioral Reasoning & Discovery, Non-Stationary Environments

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_iczxOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces ScrambleToolBench, a benchmark for evaluating whether LLM agents can discover unknown tools and adapt to environmental changes. It removes semantic information from tool interfaces and introduces mapping drift, stochastic failures, and temporal execution windows. Experiments across 15 models show large performance drops after scrambling and under dynamic conditions. The authors also find that agents often rely on exhaustive exploration instead of using previously discovered tool mappings for efficient recovery.

Critical strengths
  1. Evaluating how agents adapt their previously learned knowledge to changing environments is an interesting problem, especially for long-running agents. The benchmark provides a controlled setting to study this behavior.

  2. I find the behavioral analysis more interesting than the overall success rates. The behavioral analysis is useful. Particularly the observation that increasing reasoning effort improves task completion but does not necessarily lead to more efficient recovery strategies.

Critical weaknesses
  1. I have some doubt about the motivation of this benchmark. Why do we need to completely remove semantic information from tool interfaces? Even undocumented tools usually have meaningful names, parameters or response structures, and using these information is a reasonable part of agent capability. The mapping drift is also quite artificial, where existing identifiers suddenly execute unrelated functions. I understand these are controlled settings, but the connection to real agent robustness is not very clear. The large performance drop mainly shows agents struggle when useful interface information is deliberately removed. Whether this reflects a meaningful limitation in practical tool use remains unclear. For a benchmark paper, I think this is quite important.

  2. The conclusion about agents failing to exploit their own mapping knowledge is not fully convincing. The cycle-tracing reference assumes accurate tool mappings and a particular permutation structure, while agents have incomplete knowledge and are not informed about this structure. Table 2 measures whether agents follow displacement pointers for previously discovered tools, but having discovered a tool does not mean the agent has correctly maintained its mapping. Also, without knowing the cyclic structure, following the displaced identifier is just one possible exploration strategy. The observed inefficiency could come from inaccurate memory or uncertainty about environment changes. Hard to conclude that agents fail at structured reasoning from these results.

Questions for authors
  1. Is there any evidence that performance on ScrambleToolBench correlates with agents' ability to handle real undocumented tools or API changes? What practical capability should a high score on this benchmark indicate?

  2. For Table 2, can you report the pointer-following rate conditioned on the agent actually having the correct previous mapping available in its memory? Currently, previously discovered tools and correctly maintained mappings seem mixed together.

  3. How would a simple online tracker perform if it maintains observed tool fingerprints and updates mappings after drift, without knowing the underlying cyclic permutation? This could help understand how much of the recovery gap is due to reasoning.

  4. If agents are provided with a correct but incomplete mapping table, without revealing the permutation rule, would their recovery behavior change substantially? This may help distinguish knowledge maintenance from reasoning over existing knowledge.

Reviewer_se3QOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

is paper proposes ScrambleToolBench, a simulated terminal benchmark for evaluating whether LLM agents can discover tool behavior through interaction alone and adapt when the environment subsequently changes. The environment contains 28 mock system-administration tools and 3 plaintext meta-commands. In the scrambled setting, function identifiers, parameter keys, response keys, and the success/failure status tokens are all replaced by random aliases, and the initial schema exposes no parameter definitions. Each episode is a curriculum of five consecutive tasks sampled from 20 procedural templates, each requiring an ordered sequence of four tools. On top of this static Base setting, the authors introduce three environmental dynamics: (1) mapping drift, a cyclic permutation of a fraction of the tool identifiers between tasks, which invalidates part of the agent's learned mapping; (2) stochastic action failure, refunded timeout errors on valid calls that simulate transient network faults; and (3) temporal execution windows, where calling a task's trigger tool starts a countdown within which the agent must submit, after which the environment state is reset.

Based on experiments with fifteen open-weight and proprietary models, the paper reports four main findings:

  1. Most LLMs rely heavily on semantic priors: performance degrades sharply once tool names and schemas are anonymized, and only a few frontier models can still complete tasks through exploration.
  2. Strong initial discovery does not imply adaptability. Models that succeed in the Base setting largely fail once the dynamics are introduced, with mapping drift causing the largest increase in action cost.
  3. Under drift, agents either exhibit belief inertia—repeatedly calling identifiers that no longer map to the intended tool—or fall back to exhaustive search over the entire action space. Using an analytical oracle (cycle tracing) as a reference, the authors show that agents follow the displacement pointer recorded in their own map at a rate barely above chance, and their recovery cost is several times the oracle's.
  4. Increasing reasoning effort improves completion rates and reduces redundant actions, but these gains come from broader exploration rather than from discovering a structured recovery strategy. Persistent memory reduces compounding re-discovery errors, but its benefit depends on the model clearing stale entries, and it does not make agents exploit the displacement clues stored in memory.
Critical strengths
  • The proposed benchmark provide a testbed to evaluate model's adaptive capability of tool using under scrambled environment. It is a well-designed permutation test for robustness evaluation. Moreover, the author concluded some interesting findings from the experiments

  • The design of scrambled condition and environment are well described in the paper. The overall methodology is clear and easy to follow. As well as the findings are reasonable if the experimental results are verified

  • The author present an in-depth behavioral analysis beyond task completion rates rather than relying solely on task success rates. They analyze action overhead, stale tool calls and recovery strategies. In particular, the cycle-tracking reference provides a theoretically grounded comparison for recovery efficiency under mapping drift

  • In experimental section, the paper evaluates 15 open-source and proprietary models across six experimental conditions, with additional studies on reasoning effort and persistent memory

Critical weaknesses
  • The boundary of "removing semantic cues" is not well defined. In the abstract and intoduction, the author state the benchmark remove "semantic cues/isolates behavioral reasoning". But in Section 2.2, the return value retain the semantic cues. After I check the code in supply material, the value of error_msg is plaintext. I am concerning if this could affect the conclusion since its seems not fully isolate all the semantic cues

  • In unscrambled experiments it pass the entire schema and in scrambled setting there is no valid semantic parameters. Thus the degradation from 0.93 → 0.32 therefore reflects the joint effect of losing semantic names, the parameter schema, and readable output keys. Thus cannot be attributed to the removal of semantic priors alone

  • The authors introduce Cycle Tracing as an analytically efficient recovery strategy under mapping drift and, observing that no model adopts it, conclude that agents fall back on exhaustive search instead of structured recovery. Without telling the the agent to mapping drift follows cyclic permutation, it is not an optimized strategy to search by following the old mapping

Questions for authors

The experiments use fixed settings for mapping drift (25%), stochastic failures (15%), and temporal execution windows (10 actions). Could the authors provide sensitivity analyses across different perturbation strengths? In particular, would the same failure patterns emerge under milder environmental changes, or are the conclusions primarily driven by the selected difficulty levels?

Reviewer_y3SyOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces ScrambleToolBench, which aims to evaluate agents' ability to proactively discover the hidden rules in changing environments for efficient task completion. It reports that LLMs tend to rely on exhaustive search instead of smartly find the efficient way for exploration.

Critical strengths

This paper provides an interesting perspective on studying the behavioral patterns of LLM agents.

Critical weaknesses
  • This benchmark lacks realism and generalizability. First, the benchmark consists of only 28 simulated tools and 20 task templates. Second, the mapping drift in cycle behavior rarely occur in real tasks. It remains unclear whether this benchmark can reflect agents' adaptation capabilities in real tasks.
  • I am not convinced by the conclusions about structural reasoning. Agents are neither informed of the underlying cycle pattern nor explicitly encouraged to minimize exploration costs. Therefore, it is unclear whether exhaustive search reflects a reasoning limitation or simply a reasonable strategy under the given setting.
  • I would expect a more in-depth theoretical analysis of why LLMs exhibit these behavioral patterns, grounded in the underlying mechanisms of LLM reasoning and decision-making.
Questions for authors

See weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.