Source-linked AI summary
ScrambleToolBench: Agents Search Exhaustively Even When Their Own Map Points to the Next Step
Vernon Toh, Navonil Majumder, Zhengyuan Liu, Nancy F. Chen, Soujanya Poria
TL;DR
Existing benchmarks often preserve semantic cues and stable environments, limiting evaluation of agents’ autonomous behavioral reasoning and adaptation. ScrambleToolBench removes those cues and introduces changing conditions, finding that completion drops from 93% to 3% under combined stress as agents favor exhaustive search over deductive recovery.
Problem
Existing benchmarks largely retain semantic cues and structurally stable environments, limiting evaluation of agents’ autonomous behavioral reasoning and adaptive hypothesis revision.
Method
ScrambleToolBench uses obfuscated terminal commands and dynamic challenges to evaluate behavioral reasoning through trial-and-error discovery and adaptation.
Results
93% to 3%: under combined mapping drift and transient failures, aggregate completion drops as agents favor belief inertia or exhaustive search over deductive recovery.
Takeaways & Limitations
Persistent initial tool maps do not ensure efficient adaptation, while increased test-time reasoning amplifies brute-force exploration rather than enabling deductive recovery.
Takeaways & Limitations
Smaller models may maintain stuck beliefs after unexpected observations, repeatedly retrying actions with minor variations instead of updating their command understanding.
Abstract
from arXiv · showhide
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.
1 Introduction
ScrambleToolBench evaluates whether agents can discover and adapt to hidden tool behavior without semantic cues in changing environments. Although models discover static mappings well, they struggle with drift and failures, resorting to exhaustive search, while persistent memory only partially improves resilience.
- Motivation: Existing evaluations often assume stable environments, leaving agents’ ability to reason from tool behavior under structural change insufficiently tested.Agents commonly rely on semantic priors from intuitive function names, but incomplete documentation, undocumented behavior, and transient failures can invalidate those priors.
- Benchmark: ScrambleToolBench removes semantic cues through obfuscated command signatures, forcing agents to infer tool mechanics by probing execution inputs and outputs.The benchmark anonymizes tool identifiers, parameters, and outputs to isolate behavioral reasoning from pretrained memorization.
- Findings: 93% to 3%: Under combined challenges, aggregate completion rates collapse despite models successfully discovering and maintaining initial tool-behavior maps.The results expose a gap between successful initial discovery and robust adaptation in non-stationary environments.
- Benchmark: The benchmark’s continuous curriculum tests adaptation through mapping drift, stochastic action failures, and strict temporal execution windows.Mapping drift reassigns identifiers, valid actions may return timeout errors, and required action sequences must finish within a step limit.
- Findings: Agents fail to deduce new mappings from their internal maps, exhibit belief inertia, and resort to exhaustive search instead of cycle tracing or other recovery strategies.Persistent memory reduces redundant rediscovery loops, but stale beliefs require pruning and agents still incur substantial action-token overhead under drift.
2 The ScrambleToolBench Benchmark
ScrambleToolBench evaluates whether agents can discover and retain hidden tool behaviors through interaction in sequential, stateful tasks rather than relying on semantic API knowledge. It further tests adaptation under mapping drift, stochastic failures, and temporal execution windows.
- Behavioral discovery: Agents must infer obfuscated tool behaviors by testing hypotheses through commands in a sequential curriculum of stateful tasks.Target tools can produce observations and state transitions, while task progression and solution submission also change environment state.
- Behavioral discovery: Semantic obfuscation removes linguistic cues by randomizing function identifiers, parameter keys, and output fields, while plaintext meta-commands remain control anchors.Parameter requirements and type hints are revealed only through schema mismatch errors, forcing empirical exploration.
- Benchmark construction: Sequential curricula require agents to discover reusable tool behaviors and retain them across tasks, with strict action budgets and exact-string solution matching.Each task supplies a text-based goal and requires submission through the submit_solution meta-command.
- Benchmark construction: The benchmark combines 28 core API tools with 20 procedural task templates, generating varied episodes from shared tools and dynamically populated targets.A lightweight Python simulator computes ground-truth solutions for generated states.
- Environmental dynamics: Three dynamics probe adaptation: partial mapping permutations, valid-action failures with probability p_fail, and k-step execution windows that penalize brute-force exploration.Mapping drift is controlled by ρ_drift, stochastic failures return timeout messages without consuming the action budget, and expired windows reset the state.
3 Experiments
Experiments evaluate frontier models across progressively difficult scrambled environments and show that semantic priors support control performance but do not yield robust autonomous discovery. Environmental dynamics impair adaptation, while persistent memory improves resilience across scrambled conditions.
- Experimental Setup: The evaluation covers open-source Qwen, Gemma, and GPT-OSS models alongside proprietary OpenAI, Google, and Anthropic frontier models.Proprietary evaluations include GPT-5.4, GPT-5.4 Mini, multiple Gemini variants, and Claude Sonnet 4.5 and 5.
- Experimental Setup: Evaluations span unscrambled control, Base scrambling, isolated failure, drift, and execution-window conditions, plus an All condition combining all three dynamics.The settings use pfail = 0.15, ρdrift = 0.25, and k = 10, with a fixed random seed for reproducibility.
- Evaluation Metrics: Episode Completion Rate (Pep) measures solving all N = 5 sequential tasks, while Average Tasks Solved (Tavg) captures the mean number completed per episode.Any task failure halts sequential progress, making Pep a stringent reliability measure.
- Results: Unscrambled control performance reaches Pep ≥0.60 and Tavg ≥4.5, but most models collapse to a 0.00 completion rate in scrambled Base.Examples include Gemma 4 26B-A4B, GPT-5.4 Mini, and Gemini 3.1 Flash Lite, indicating dependence on semantic cues.
- Results: Mapping drift lowers completion rates, with Qwen 3.6 27B falling from 0.55 to 0.25 and Gemini 3.1 Pro from 1.00 to 0.90.Drift reassigns 25% of tool identifiers mid-episode; stochastic failure drops Qwen to 0.35 while frontier models remain unaffected.
- Results: Persistent memory increases aggregate completion by 0.14 under drift and 0.13 under tight execution windows.For Qwen 3.6 27B, memory raises + Drift completion from 0.25 to 0.40 and + Window completion from 0.15 to 0.35.
4 Analysis · 4.1 Quantifying Adaptation, Persistence, and Belief Inertia · 4.2 Cycle Tracing: A Cheap Recovery Strategy for Mapping Drift
The analysis shows that scrambling and mapping drift sharply increase action costs, while retry persistence and persistent memory partially buffer environmental stress. Although cycle tracing offers a cheap deductive recovery strategy, agents rarely exploit it consistently and instead continue costly search despite persistent mapping knowledge.
- 4.1.1 Action Overhead: Scrambling raises action overhead from the 25–27-action unscrambled baseline by 3–5×, while Drift adds 1.89× for Gemini 3.1 Pro.Gemini 3.1 Pro rises from 25.1 →80.8 actions in Base and 80.8 →152.4 under Drift; Qwen 3.6 27B rises from 26.5 →129.7.
- 4.1.2 Stochastic Retry and Persistence: Retry behavior separates robust error attribution from premature hypothesis abandonment under stochastic failures and combined stress.At 𝑝fail = 0.15, Claude Sonnet 5 achieves 71.8% immediate and 78.7% persistent retry rates, whereas GPT-OSS 20B has 0.0% immediate retries; GPT-5.4 falls from 58.6% to 43.6% persistent retries under All.
- 4.1.3 Failure Mode Distribution: Persistent memory stabilizes behavior but changes failure profiles according to model tenacity, reducing Claude Sonnet 4.5’s budget exhaustion from 49.3% to 17.1%.Gemini 3.1 Pro and Gemini 3.5 Flash remain at 60.0% and 100% budget exhaustion, respectively; memory also reduces stressed action overhead, including Qwen 3.6 27B from 161.3 →141.9 actions.
- 4.1.4 Stale Tool Calling: Stale calls expose belief inertia after Drift: Qwen 3.6 27B reaches 3.67 calls per task, while Gemini 3.5 Flash averages 0.93 and memory reduces these to 2.05 and 0.44.Under All, Claude Sonnet 5’s stale calls more than double to 5.32, while memory increases Claude Sonnet 4.5 from 2.38 to 2.76.
- 4.2.2 Cycle tracing recovery: Cycle Tracing recovers a moved function by following identifier chains, requiring at most six additional calls per drift event without knowing permutation size or structure.For a benchmark cycle of 𝑘 = 7 identifiers, recovery costs 𝑘−1 = 6 extra calls; unchanged functions require no recovery.
- 4.2.1 Setup: The benchmark applies Drift by permuting 𝑘 = 7 of 𝑀 = 28 identifiers between tasks, creating successive cycles while leaving other identifiers unchanged.A five-task episode contains four drift events, and selected identifiers may overlap across boundaries.
- 4.2.3 Expected cost: Cycle tracing is cheaper than blind search when the stored mapping is sufficiently current, but unresolved earlier mappings can lengthen cycles and alter costs.For 𝑀 = 28 and 𝑘 = 7, the stated condition holds; otherwise blind search may be cheaper on average.
- 4.2.4 Observed cost: Agents often remember mappings without exploiting the recovery chain: Sonnet follows it at only 14.0%, 11.9%, and 14.1% across reasoning levels, while Gemini is no better than random selection.Gemini follows the correct next identifier in 12.8% of opportunities versus a 10.9% random baseline; memory reduces Gemini’s Drift actions from 154.9 to 139.9 and exact repeated calls from 38.2 to 24.6.
4.3 The Role of Reasoning Effort
Higher reasoning effort improves completion for Gemini 3.1 Pro and Claude Sonnet 5, especially under mapping drift, but does not ensure efficient reasoning. Claude achieves comparable high-reasoning performance at substantially higher token and action costs, while low-reasoning failures differ by agent.
- Reasoning effort and performance: Higher reasoning raises Gemini’s T_avg from 3.40 to 5.00 in Base and 1.25 to 4.90 under drift, while Claude improves more modestly.Gemini’s P_ep also rises from 0.55 to 1.00 in Base and 0.10 to 0.90 under drift.
- Reasoning effort and performance: At high reasoning, Claude uses 7,326 versus Gemini’s 1,584 completion tokens per solved task in Base, and 11,652 versus 3,332 under drift.These correspond to 4.6× and 3.5× higher costs for Claude, respectively.
- Reasoning effort and efficiency: Lower reasoning does not reliably reduce cost: Gemini remains near 1,580–1,686 tokens in Base and 3,332–3,382 under drift.For Claude under drift, low reasoning is most expensive at 13,274 tokens per solved task, versus 9,741 at medium and 11,652 at high.
- Reasoning effort and failure behavior: At high reasoning, Claude averages 16.36 actions over Tasks 2–5 in Base and 36.93 under drift, versus Gemini’s 9.84 and 28.66.At low reasoning, Gemini quits early in all 9 Base and 18 drift failures, whereas Claude’s three Base failures reach the 100-action limit.
4.4 Qualitative Insights into Agent Reasoning
Agents commonly fail by persisting with invalidated actions after environmental changes, whereas persistent memory and active state monitoring support efficient tool selection, memory revision, temporal execution, and recovery from resets.
- Stuck beliefs after environmental change: After mapping drift invalidates a successful function, agents may repeat the same call in a 7-step loop rather than update their plans.Qwen 3.6 27B continues calling fn_fc40 after it begins returning empty results, varying only its rationalizations and search patterns.
- Memory-supported adaptation: Persistent memory lets agents map semantic goals to validated tools immediately, while targeted pruning removes stale mappings after environmental shifts.Gemini 3.5 Flash uses saved mappings to execute the correct tool on its first turn, and Gemini 3.1 Pro clears prior mappings while preserving task-critical details.
- Recovering from resets and confusion: Agents that monitor environment state can recover from expired temporal windows by diagnosing resets, backtracking, re-invoking triggers, and re-executing the required sequence.Frontier models adjust their plans after invalid-state errors, unlike weaker models that reuse invalidated session variables.
5 Related Work
Related work evaluates tool use through semantic schemas, interactive discovery, and long-horizon execution in stateful environments. ScrambleToolBench builds on these directions while targeting unfamiliar tool behavior and extended interaction.
- Tool-Use Benchmarks: Tool-use benchmarks evaluate agents’ ability to interface with external systems and APIs.Foundational evaluations use static environments with explicit plaintext schemas.
- Tool-Use Benchmarks: Recent tool-use benchmarks require agents to probe unfamiliar interfaces or infer the semantics of intentionally obfuscated tools.These approaches extend beyond static, schema-based evaluation toward interactive discovery.
- Interactive Benchmarks: Interactive agent benchmarks assess long-horizon reasoning and continuous execution within stateful computing environments.They cover complex software workflows, real computer interfaces, and multi-step error recovery across extended terminal sessions.
6 Conclusion
ScrambleToolBench isolates behavioral reasoning in unstable environments by removing semantic priors and introducing scrambled mappings, stochastic failures, and temporal execution windows. Experiments expose agents’ reliance on exhaustive search under mapping drift, while persistent memory improves task completion and reduces redundant loops.
- Benchmark design: ScrambleToolBench evaluates autonomous tool discovery without semantic priors through scrambled mappings, stochastic action failures, and temporal execution windows.The benchmark is designed to expose language models’ over-reliance on semantic cues in unstable environments.
- Empirical findings: Most agents fail under combined stress, while persistent memory improves frontier-model task completion rates and reduces redundant loops.The passage reports recovery of task completion rates and fewer redundant loops when persistent memory is provided.
- Reasoning failure: Under mapping drift, agents exhibit belief inertia, fail to recognize structural permutations, and choose exhaustive search over deductive strategies such as cycle tracing.The finding identifies a reasoning gap in adapting to structural changes.
A Memory-Enhanced Baseline Schema
The memory-enhanced baseline externalizes learned representations in two structured databases, Task Recipes and Tool Knowledge, and provides them to the agent throughout interaction. The agent can update these databases alongside its actions through structured JSON outputs.
- The baseline equips the agent with two structured databases: Task Recipes and Tool Knowledge.This design evaluates whether externalizing learned representations improves efficiency on long-horizon tasks.
- At every environment step, both databases are serialized into JSON and injected into the system prompt.The prompt payload includes the current system state and memory contents.
- The agent updates memory by returning an optional memory_update dictionary alongside its standard action in one JSON response.Updates can record inferred tool behavior, parameter meanings, and confidence levels.
B Core API Functions
The benchmark exposes core API functions spanning virtual-filesystem operations, encoding and decryption utilities, system and network inspection, archive access, task control, and solution submission. Together, these functions support file discovery and reading, environment diagnosis, data transformation, and episode management.
- Data transformation: Encoding and cryptographic utilities encode or decode UTF-8 text as Base64 and decrypt symmetric ciphertext with a secret key.The Base64 operations are in-memory transformations, while decryption recovers raw plaintext.
- Task control: Control APIs let agents submit a proposed solution, skip the current task, or terminate the episode early.Solution submission evaluates whether the proposed string matches the correct task solution.
- System inspection: System and environment APIs retrieve operating-system, hardware, shell, process, user-group, cron, kernel-module, host, CPU, and environment-variable information.They expose both high-level platform categories and detailed local system state.
- Network inspection: Network APIs measure ping reachability and latency, resolve domains, test TCP ports, list active connections and interfaces, and retrieve routing tables.These functions cover connectivity, address resolution, socket state, adapter status, and kernel routing information.
- Filesystem and archives: Filesystem APIs list directories, read files, search text, inspect metadata, determine file types, query permissions, and measure disk usage.Archive-specific functions additionally list compressed contents and read a file from an archive.
- Filesystem and archives: Archive APIs traverse compressed zip/tar contents and read text directly from a specified archived file.These operations complement ordinary filesystem listing and file reading.
C Task Taxonomy
The task pool covers diverse system-administration and diagnostic scenarios generated dynamically from procedural templates. Tasks require multi-step tool combinations spanning service discovery, file and archive forensics, process and kernel inspection, networking, security, and system profiling.
- Task generation: Procedural templates dynamically instantiate episode-specific administration and diagnostic goals, such as tracing a database process from connection logs to its internal hostname.The Web Service Audit example varies the port and target variable across episodes.
- Networking and services: Service, network, and DNS tasks diagnose hosts through connection discovery, interface and route inspection, hostname resolution, reachability checks, and port verification.Examples include Host Verification Diagnostics, Network Route Interface Mapping, Hostname Access Diagnostics, DNS Firewall Verification, and DNS Firewall Routing.
- File and archive forensics: File and archive forensics tasks locate, read, decode, encode, decrypt, classify, and measure files or archived contents, including encrypted payloads and compressed logs.These tasks combine directory and archive traversal with content transformation or metadata and permission checks.
- Processes, kernels, and access: Process, kernel, and access-audit tasks inspect running processes, SSH keys, kernel modules, cron jobs, user groups, and protected resources.They include process SSH key inspection, driver integrity, kernel module forensics, automated job storage, and user process access.
- System profiling: System-profiling tasks combine shell, environment, hardware, CPU, and system metadata to construct fingerprints or verify capabilities and access conditions.The System Fingerprinting Profile, CPU Capability System, and Hardware Specs Shell exemplify this category.
D Recovery Cost without Application-Level Failures
A counterfactual analysis assigns zero cost to known-schema calls that fail at the application level, favoring the models by removing actions that consumed the evaluation budget. Even under this favorable adjustment, Tasks 2–5 remain 3.61–5.65× more costly than cycle tracing.
- Counterfactual cost adjustment: The robustness check assigns zero action cost to known-schema calls returning application-level errors, while retaining argument-schema errors.Examples of application-level errors include “File not found” and “Host unreachable.”
- Counterfactual cost adjustment: The adjusted comparison uses paired episodes and excludes early exits, matching the main analysis in Table 4.The adjustment favors models because these calls consumed the action budget during the actual evaluation.
- Adjusted cost definition: For Tasks 2–5, the adjusted compared cost is A_Drift,adj − 5, against the expected 4.25-action cycle-tracing reference.The ratio uses the reference’s unrounded value.
- Result: 3.61–5.65×: Tasks 2–5 averages remain this many times the reference despite removing real actions from model costs.This result shows that application-level failures do not account for the remaining recovery-cost gap.