Skip to content

The Amazing Agent Race: Strong Tool Users, Weak Navigators

🕒 Published (v1): 2026-04-17 00:00 UTC · Source: HuggingFace · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

AAR introduces a 1,400-instance benchmark of DAG-structured Wikipedia-navigation + tool-composition tasks, exposing a critical "compositionality gap" in prior benchmarks (55–100% linear). Evaluation of three agent frameworks shows the best achieves only 37.2% finish-line accuracy, with navigation errors (27–52% of trials) dominating over tool-use errors (<17%). Agent architecture matters as much as model scale: Claude Code matches Codex CLI at 37% with 6× fewer tokens.

Problem

Existing tool-use benchmarks are overwhelmingly linear (55–100% of instances are simple 2–5-step chains), leaving fork–merge compositional reasoning untested. Navigation and tool composition are evaluated in isolation: tool-use benchmarks omit navigation, web-navigation benchmarks omit chained tool calls. This structural gap prevents diagnosis of where agents actually fail in realistic multi-step tasks.

Method

AAR frames evaluation as a race across Wikipedia. Each instance ("leg") is a directed acyclic graph (DAG) of typed pit stops: Route Info (Wikipedia navigation + fact extraction), Roadblock (external tool chain, e.g., geocode→elevation), Detour (analytical transform, e.g., digital root), and Finish Line (modular aggregation to a single digit \(\hat{y} \in \{0,\ldots,9\}\)). DAG structure is enforced via diamond patterns: a source stop forks into two parallel branches (e.g., elevation and POI count from the same geocoded entity), which merge downstream.

An eight-step automated pipeline generates legs: crawl Wikipedia, LLM-plan a thematic route, instantiate stops, pre-validate tool chains against live APIs, link stops, augment with diamonds, execute golden traces, and verbalize into a clue envelope (circumlocutions replacing Wikipedia titles, round-trip alignment \(\geq 0.7\) required). Three decomposed metrics isolate failure modes: FA (finish-line accuracy), PVR (pit-stop visit rate, navigation), RCR (roadblock completion rate, tool use).

Evaluation runs through Harbor, an open-source agent evaluation harness that orchestrates trials in containerized Docker environments, wrapping Codex CLI, Claude Code, and mini-swe-agent behind a common interface.

Key Contributions

  • Compositionality analysis of six prior benchmarks showing 55–100% linearity, motivating a new structural gap metric.
  • AAR benchmark (1,400 legs: 800 AAR-Linear, 600 AAR-DAG) with procedurally generated DAG legs, 19 tools, four difficulty levels (5–33 pit stops), contamination resistance via live APIs and clue paraphrasing.
  • Three decomposed metrics (FA, PVR, RCR) that independently diagnose navigation, tool-use, and arithmetic failures.
  • Empirical evaluation across 7,000 trials (three frameworks, two model families) with a failure taxonomy.

Results

  • Best finish-line accuracy: 37.2% (Claude Code + Sonnet 4), against a 10% random baseline.
  • Navigation errors dominate: 30.9% of all trials (rising to 52% at extreme difficulty); tool-use errors: 8.6%.
  • FA degrades monotonically with difficulty; best config drops 13.5 pp from easy to extreme, driven by PVR (88.7%→37.1%) not RCR (83.6%→49.2%).
  • DAG structure penalizes navigation (PVR drops 13–18 pp on AAR-DAG vs. AAR-Linear) while RCR stays stable or increases slightly.
  • Framework gap (Codex CLI vs. mini-swe-agent, 11 pp) exceeds model-scale gap (GPT-5.4 vs. GPT-5.4-mini).
  • Claude Code matches Codex CLI (37.2% vs. 37.1%) using 6× fewer tokens (114–225K vs. 1.4–1.8M/trial).
  • Reasoning model (GPT-OSS-120B with extended thinking) achieves 3.1% FA — near random — due to timeout from spending budget on internal reasoning (2.2 tool calls vs. 27 for GPT-5.4).
  • 14–21% of AAR-DAG trials reach correct answers via shortcuts (visiting <30% of required pages), up from 6–11% on AAR-Linear.

Limitations

  • Single-digit finish-line codes (\(y^* \in \{0,\ldots,9\}\)) limit answer space; modular arithmetic may introduce coincidental correctness.
  • Wikipedia-only navigation; generalization to other knowledge sources untested.
  • PVR measures exact URL match against golden trace, which may penalize valid alternative navigation paths.
  • Shortcut trials (correct answer, low PVR) inflate FA without reflecting genuine task completion.
  • Live API dependence creates temporal instability despite caching heuristics.
  • Evaluation limited to three agent frameworks; no fine-tuned or retrieval-augmented baselines.

Relevance to Harnesses / Meta-Harnesses

AAR is evaluated entirely through Harbor, an open-source agent evaluation harness that wraps heterogeneous agent frameworks (Codex CLI, Claude Code, mini-swe-agent) behind a uniform Docker interface — a direct example of a meta-harness coordinating multi-agent benchmarking at scale. The finding that agent architecture matters as much as model scale is directly actionable for harness designers: the harness scaffolding (planning loop, step budget, tool routing) contributes ~11 pp of accuracy variation, comparable to frontier vs. cost-efficient model choice. The paper's automated generation pipeline is itself a meta-harness: an eight-stage orchestration of LLM planning, live API validation, golden execution, and NL verbalization to produce verified evaluation instances — a template for building contamination-resistant, self-growing benchmarks. The 6× token-efficiency advantage of Claude Code over Codex CLI at matched accuracy also highlights that harness design (how tool outputs are managed, how steps are budgeted) is a first-class variable in agent system performance.