PaperlayerView exact revision on arXiv

Source-linked AI summary

The Amazing Agent Race: Strong Tool Users, Weak Navigators

Zae Myung Kim, Dongseok Lee, Jaehyung Kim, Vipul Raheja, Dongyeop Kang

arXiv:2604.10261v2cs.AIcs.CLcs.LG

TL;DR

Existing tool-use benchmarks largely test linear chains, leaving fork-merge navigation and tool composition underexamined. AAR evaluates agents on DAG puzzles with decomposed metrics, finding that the best framework achieves only 37.2% finish-line accuracy and that navigation errors dominate tool-use errors.

  • Problem

    Existing benchmarks leave non-linear navigation and fork-merge tool dependencies underexamined, despite agents needing both capabilities in practice.

  • Method

    AAR evaluates agents on Wikipedia-based DAG legs requiring navigation, parallel tool branches, result merging, and separate navigation, tool-use, and computation metrics.

  • Results

    37.2% finish-line accuracy was achieved by the best framework; navigation errors dominated while tool-use errors remained below 17%.

  • Takeaways & Limitations

    Agents were competent tool users but poor navigators, and compositional structure amplified this gap.

  • Takeaways & Limitations

    AAR uses Wikipedia as its sole navigation source, with broader domains and richer DAG topologies left for future work.

Abstract

from arXiv · show

Existing tool-use benchmarks for LLM agents are overwhelmingly linear: our analysis of six benchmarks shows 55 to 100% of instances are simple chains of 2 to 5 steps. We introduce The Amazing Agent Race (AAR), a benchmark featuring directed acyclic graph (DAG) puzzles (or "legs") with fork-merge tool chains. We release 1,400 instances across two variants: sequential (800 legs) and compositional (600 DAG legs). Agents must navigate Wikipedia, execute multi-step tool chains, and aggregate results into a verifiable answer. Legs are procedurally generated from Wikipedia seeds across four difficulty levels with live-API validation. Three complementary metrics (finish-line accuracy, pit-stop visit rate, and roadblock completion rate) separately diagnose navigation, tool-use, and arithmetic failures. Evaluating three agent frameworks on 1,400 legs, the best achieves only 37.2% accuracy. Navigation errors dominate (27 to 52% of trials) while tool-use errors remain below 17%, and agent architecture matters as much as model scale (Claude Code matches Codex CLI at 37% with 6x fewer tokens). The compositional structure of AAR reveals that agents fail not at calling tools but at navigating to the right pages, a blind spot invisible to linear benchmarks. The project page can be accessed at: https://minnesotanlp.github.io/the-amazing-agent-race

1 Introduction

The Amazing Agent Race (AAR) addresses a gap in predominantly linear benchmarks by testing agents that navigate Wikipedia, branch tool chains, and merge results in DAG-structured legs. Across 1,400 legs, navigation—not tool calling—is the primary failure mode.

  • Problem: Across six existing benchmarks, 55–100% of instances are strictly linear chains averaging only 2–5 steps, leaving navigation and compositional tool chains insufficiently tested.Tool-use benchmarks omit navigation, compositional benchmarks provide inputs upfront, and web-navigation benchmarks omit compositional tool chains.
  • This work: AAR evaluates Wikipedia navigation, multi-step tool chains, analytical reasoning, and aggregation through fork–merge DAG legs rather than linear chains.Each leg uses parallel branches that originate from shared information and later merge into a single-digit answer.
  • This work: AAR procedurally generates legs from random Wikipedia seeds across four difficulty levels, using 19 tools, 8–33 pit stops, live APIs, and clue paraphrasing to require information discovery rather than recall.Its finish-line accuracy, pit-stop visit rate, and roadblock completion rate separately measure final answers, navigation, and tool use.
  • Key findings: 37.2% finish-line accuracy was achieved by the best framework across 1,400 legs, while navigation errors affected 27–52% of trials and tool-use errors stayed below 17%.Figure 1 reports 36.6% best-agent accuracy and navigation errors of 5%–52%, while the key findings report 37.2% FA and 27%–52% navigation errors.
  • Key findings: Moving from AAR-Linear to AAR-DAG lowered navigation scores by 13–18 percentage points while tool-use scores remained stable, isolating compositional structure as a navigation challenge.AAR therefore distinguishes navigation, tool use, and final-answer failures rather than collapsing them into one outcome.

2 Related Work

Existing benchmarks evaluate isolated tool use, web navigation, or shallow compositions, whereas AAR combines open-web navigation with multi-step tool composition in automatically generated, structurally controlled episodes. Its DAG structure addresses a compositionality gap: prior benchmarks are mostly linear or shallow, while every AAR instance averages 22 pit stops with fan-out and fan-in.

  • Related benchmark capabilities: AAR combines open-web navigation with multi-step tool composition in a structurally controlled, automatically generated benchmark.This targets the integrated episode requirements of interpreting instructions, navigating information sources, invoking APIs, and chaining results.
  • Tool-use benchmarks: ToolBench, BFCL, and API-Bank scale the number of available tools but present APIs in isolation, so agents need not find inputs before calling them.StableToolBench replaces unstable live endpoints with a virtual server, while BFCL uses AST-based scoring and stateful workflows.
  • Compositionality gap: 100% of ToolBench, ToolHop, and GAIA instances are linear, while TaskBench is 94% linear with 1.7 steps on average.NESTFUL and T-Eval show more non-linearity, but remain shallow at 3.4 and 4.8 steps, respectively.
  • Compositionality gap: Every AAR instance is a DAG averaging 22 pit stops, with fan-out and fan-in through diamond patterns.This creates a structural gap relative to prior benchmarks’ predominantly linear or shallow dependency graphs.
  • Web navigation benchmarks: WebArena, Mind2Web, OSWorld, and GAIA evaluate increasingly broad web or GUI interaction settings, but GAIA is closest to AAR’s combined scope.GAIA includes questions requiring both web lookup and tool use, alongside 466 manually curated static instances.

3 Benchmark Design Principles

AAR uses Wikipedia’s dense, semi-structured, diverse, and contamination-sensitive knowledge graph to construct verifiable DAG legs rather than linear tool chains. Typed pit stops, composable tools, diamond-shaped dependencies, and independently varied difficulty parameters define the benchmark’s design.

  • Knowledge source and inputs: Wikipedia supplies dense hyperlink graphs, semi-structured infoboxes, broad topical coverage, free licensing, and a contamination testbed requiring paraphrased clues and live API calls beyond memorized facts.The benchmark uses a seed URL, a natural-language clue envelope that omits page titles and tool names, 19 described tools, and a step budget B = max(10, ⌊1.5K⌋).
  • DAG leg structure: AAR legs form typed directed acyclic graphs whose route-info, roadblock, detour, and finish-line stops navigate, execute tools, transform values, and aggregate a single-digit answer.Transitions and values are typed, enabling type-aware argument passing between stops.
  • DAG leg structure: Diamond patterns create genuine non-linear structure by branching from one source into independent tool chains and merging both outputs, with diamond counts increasing from 1 for easy to 3–5 for extreme.The benchmark uses four branch pairings: elevation×POI, elevation×rating, population×area, and temperature×precipitation.
  • Tool and value design: AAR’s 19 tools are organized for composability and temporal dynamism, with 17 roadblock templates composing 1–3 tools and canonical units plus explicit conversion stops.Examples include geocode → elevation, while stock and crypto tools return live data.
  • Difficulty control: Four difficulty levels independently vary leg length, roadblock and detour counts, extraction complexity, and Wikipedia crawl depth; diamond augmentation adds 3 stops per diamond.Extreme legs average 33 stops despite a configured pre-augmentation range of 17–21.

4 The AAR Benchmark Construction

AAR constructs procedurally generated Wikipedia navigation legs through an automated pipeline with live-API validation and quality guarantees. It releases sequential and fork–merge DAG variants designed to resist memorization through paraphrased clues, changing API values, derived detours, and modular finish codes.

  • Generation pipeline: Each leg is generated by crawling Wikipedia, planning a thematic route, instantiating stops and tool chains, pre-validating APIs, linking stops, and augmenting the instance.The pipeline includes route-info stops, roadblocks, detours, and live-API dry runs that discard failing chains before re-indexing.
  • Quality control: Every leg must be solvable, API-stable, reproducible, cleanly specified, geocodable, and compliant with clue-envelope integrity requiring round-trip alignment of at least 0.7.Reproducibility relies on cached traces and page snapshots, while clue envelopes avoid direct Wikipedia titles.
  • Anti-memorization design: AAR resists memorization by paraphrasing clues, using changing live-API answers, deriving detour values absent from Wikipedia, and applying modular arithmetic to finish-line codes.These mechanisms make answers dependent on procedurally generated instances rather than titles or static Wikipedia content.
  • Benchmark variants: AAR releases 800 AAR-Linear legs with sequential tool chains and 600 AAR-DAG legs with diamond fork–merge patterns, sampled from popular English Wikipedia articles.Both variants undergo tool-chain pre-validation, golden execution, and round-trip clue-envelope validation; DAG legs additionally receive diamond augmentation.

5 Experimental Setup

Experiments use Harbor to evaluate diverse agent architectures and models under a standardized interface, timeout, and metric suite across all AAR legs. The setup also specifies reproducibility controls, baselines, and computational costs.

  • Evaluation framework: Harbor standardizes evaluation by running agents in containerized Docker environments with identical tool executors, clue files, and internet access.The shared executor exposes all 19 AAR tools.
  • Agent frameworks: Three agent architectures—Codex CLI, Claude Code, and mini-swe-agent—test whether AAR distinguishes autonomous planning and multi-step tool-orchestration strategies.Codex CLI and Claude Code autonomously plan and execute shell commands, while mini-swe-agent uses a ReAct-style bash loop.
  • Models: Evaluations cover GPT-5.4, GPT-5.4-mini, Claude Sonnet 4, and GPT-OSS-120B across every leg, with results reported by difficulty and in aggregate.Codex CLI and mini-swe-agent use OpenAI models; Claude Code uses Claude Sonnet 4; Codex CLI also uses GPT-OSS-120B.
  • Agent interface: Agents receive a seed URL, clue envelope, 19 tool schemas, and a step budget B = max(10, ⌊1.5K⌋), producing one digit with outputs truncated at 8,000 characters.The step budget depends on the number of pit stops K.
  • Evaluation controls: A uniform 600-second timeout supports fair cross-difficulty comparisons because it contains 92% of correct AAR-Linear and 95% of correct AAR-DAG answers.Longer incorrect trials generally continue along wrong paths without recovery, while temperature 0 and cached traces support deterministic re-scoring.
  • Metrics: The evaluation reports finish-line accuracy, pit-stop visit rate, and roadblock completion rate to separate answer success, navigation quality, and tool-execution performance.Finish-line accuracy is primary; the supplementary indicators are defined separately in the metric suite.

6 Results

Across 1,400 legs, no configuration exceeds 37.2% finish-line accuracy, with navigation consistently weaker than tool use and agent architecture rivaling model scale. Difficulty and compositional DAG structure primarily impair navigation, while time-constrained reasoning models and wrong-page exploration expose additional failure modes.

  • Difficulty and failure localization: 45.0% to 31.5% and 43.0% to 28.9% are the easy-to-extreme FA drops for Codex + GPT-5.4 and Claude Code, while PVR falls 88.7% to 37.1% and RCR 83.6% to 49.2%.Navigation therefore drives the difficulty-related accuracy decline more strongly than tool use.
  • Aggregate results: 37.2% is the highest reported finish-line accuracy, while PVR remains consistently the weakest metric and Claude Code + Sonnet 4 ties Codex + GPT-5.4 at about 37%.The full spread across configurations is 11 percentage points.
  • Agent architectures: 37.1% versus 26.1% is the FA comparison between Codex + GPT-5.4 and mini-swe-agent + GPT-5.4-mini, while RCR is 65.8% versus 34.4%.The 11-point framework gap exceeds the model-scale gap, and Claude Code + Sonnet 4 reaches 37.2%.
  • Compositionality: 13–18 pp PVR declines from AAR-Linear to AAR-DAG, while RCR remains stable or slightly increases and stronger-configuration FA drops modestly, including −5.5 pp for Codex + GPT-5.4.DAG fork-merge structure adds difficulty through longer navigation trails rather than tool invocation.
  • Compositionality: 14–21% of AAR-DAG trials reach the correct answer while visiting under 30% of required pages, versus 6–11% on AAR-Linear.These shortcuts are not lucky guesses: they retain 43.8% RCR and 60.9% intermediate accuracy, while PVR below 0.3 flags navigation bypass.

7 Conclusion

AAR is a DAG-structured benchmark whose decomposed metrics diagnose navigation, tool-use, and computation failures; across 1,400 legs, the best of three agent frameworks achieves only 37.2% finish-line accuracy. The benchmark currently uses Wikipedia and 19 tools, with planned extensions to broader domains, richer DAGs, multi-leg seasons, and partial-credit evaluation.

  • Conclusion: 37.2% FA is the best result across 1,400 legs and three agent frameworks, showing competent tool use but poor navigation that compositional structure amplifies.AAR’s three metrics—FA, PVR, and RCR—separately diagnose navigation, tool-use, and computation failures.
  • Conclusion: AAR currently uses Wikipedia as its sole navigation source with 19 tools, limiting the benchmark’s domain coverage.The planned expansion targets calendars and databases.
  • Conclusion: Planned extensions add shared sub-expressions and conditional branches, multi-leg seasons with cross-episode state, and partial-credit evaluation via calibrated LLM judges.These plans also broaden AAR beyond Wikipedia to calendars and databases.

Ethics Statement

AAR uses publicly available data and commercial APIs within their terms, protects privacy, and avoids human-subject research. The authors also describe safeguards for crawling and evaluation costs.

  • AAR uses Wikipedia content under CC BY-SA and queries Google Maps, Yahoo Finance, Binance, and Serper within their terms of service.
  • The benchmark collects, stores, and redistributes no personal data and does not involve human subjects.
  • The Wikipedia crawler respects robots.txt and rate limits.
  • The authors acknowledge the environmental cost of large-scale LLM evaluations and mitigate it by caching golden execution traces.

Reproducibility Statement · A Additional Related Work · B Difficulty Level Parameters

AAR instances are deterministically reproducible through cached pages, execution traces, intermediate values, and finish-line code, while its related-work positioning spans holistic agent benchmarks and contamination-resistant evaluation. Difficulty is parameterized by pit stops, diamond-induced fork–merge dependencies, and Wikipedia crawl hops, with augmentation increasing pit-stop counts.

  • Reproducibility Statement: AAR enables deterministic re-scoring independent of live API state by caching Wikipedia snapshots, golden traces with intermediate values, finish-line code y∗, and generated tool outputs.Generation uses GPT-4o with temperature 0, while tool chains run against live APIs at generation time before their outputs are cached.
  • A Additional Related Work: Holistic agent benchmarks cover environments, subgoal progress, simulated-app APIs, tool-agent-user interaction, and professional tasks.The cited benchmarks include AgentBench, AgentBoard, AppWorld, tau-bench, and TheAgentCompany, with the passage reporting tau-bench’s GPT-4o pass1 rate as below 50%.
  • A Additional Related Work: AAR addresses contamination concerns by seeding instances from random Wikipedia articles and querying live APIs whose data changes daily.The passage contrasts this design with fixed benchmarks such as MMLU, GSM8K, and HumanEval, and with MCP-Bench’s manually curated live-server setup.
  • A Additional Related Work: Fixed benchmarks including MMLU, GSM8K, and HumanEval face growing contamination as their instances enter training corpora.MCP-Bench instead uses 250 tools across 28 live MCP servers but relies on manual curation.
  • B Difficulty Level Parameters: Difficulty levels configure pre-augmentation pit-stop ranges, diamond counts, and available Wikipedia link-graph crawl hops.Diamonds represent fork–merge patterns that create non-linear DAG dependencies.
  • B Difficulty Level Parameters: After diamond augmentation, each diamond adds three stops—two branches and one merge—so actual pit-stop counts exceed the configured ranges.The table describes these parameters before augmentation.

C Benchmark Validity … G Agent Recovery from Partial Success

AAR is solvable, diverse, and temporally stabilized, but performance worsens for specialized tools and longer chains. Partial success is insufficient for reliable answers, especially on compositional DAG legs where merge-point aggregation reduces recovery.

  • C Benchmark Validity: Every evaluation leg is solvable by the golden executor, and round-trip validation confirms that its clue envelope unambiguously implies the golden answer.This establishes solvability with the provided tool set before agent evaluation.
  • C Benchmark Validity: 99.1% of sampled leg pairs share zero Wikipedia pages, with mean Jaccard similarity of 0.0005, making memorization shortcuts ineffective.Diversity is measured across 800 legs using 10,000 randomly sampled pairs of visited-page sets.
  • C Benchmark Validity: AAR stabilizes live-data evaluation by caching golden traces and using modular arithmetic that absorbs small tool-output perturbations.The benchmark uses cached reference values for rescoring and applies mod10 and digital-root computations; 15 of 17 roadblock templates query live data.
  • D Tool Set and Roadblock Templates: The tool set contains 19 available tools and 17 roadblock templates, each composing 1–3 tool calls with explicit argument-passing formats for chained outputs.Arguments can merge previous output dictionaries or format coordinates and origin-destination pairs for downstream tools.
  • E Per-Template Tool-Use Analysis: 40.2% accuracy for date computation and 33.4% for math conversion exceed specialized-template accuracy, including 18.5% for stock price and 22.2% for weather.Geographic templates are intermediate: geocode elevation reaches 27.0% and nearby POI 28.1%, while place rating reaches 22.5%.
  • F Scaling Behavior: 40.2% finish-line accuracy on short legs falls to 17.4% on long legs, while PVR drops from 83.5% to 35.8% and RCR from 71.6% to 37.5%.These results for Codex CLI + GPT-5.4-mini show that longer chains compound navigation errors into lower overall accuracy.
  • G Agent Recovery from Partial Success: 31.7% of AAR-DAG legs with both high PVR and RCR yield correct answers, versus 50.3% on AAR-Linear, a 19-point drop attributed to compositional finish-line aggregation.On AAR-Linear, high-PVR legs alone recover 45.0% of answers, while both-high recovery reaches 50.3% across 199 legs; AAR-DAG both-high recovery is 31.7% across 60 legs.

H Discussion: What AAR Reveals About Agent Limitations … O Computational Resources

AAR exposes navigation and compositional computation as distinct agent weaknesses: incorrect trials over-explore with valid tools, while shortcuts can yield correct answers without intended navigation. Results also show that execution strategy and computational resources strongly affect performance in time-constrained agentic tasks.

  • H Discussion: What AAR Reveals About Agent Limitations: 20.5% of trials are near-misses with strong PVR (63.5%) and RCR (71.4%), while 12.8% navigate successfully but fail downstream with RCR of 69.2%.These failure populations separate final aggregation errors from tool-chain or computation errors after successful navigation.
  • H Discussion: What AAR Reveals About Agent Limitations: Incorrect trials average 21.7 tool calls versus 16.5 for correct trials, despite >98% call validity, indicating over-exploration on wrong pages rather than malformed tool use.The central problem is selecting the right tools and data, not executing invalid calls.
  • I Additional Case Studies: A perfectly navigated 8-stop leg achieved PVR = 1.00 and RCR = 1.00 but produced 3 instead of the expected 5 through a compositional arithmetic error.The agent reached 88% intermediate value accuracy yet misrouted values through the diamond merge and finish-line expression.
  • J Reasoning Model Analysis: GPT-OSS-120B achieves 3.1% FA on AAR-Linear versus GPT-5.4’s 37.1%, averaging 2.2 versus 27 tool calls and often timing out before answering.Its extended internal reasoning consumes the budget needed for many shallow tool interactions; a preliminary AAR-DAG run achieved 0% FA across 68 trials.
  • K Tool-Use Shortcuts: On AAR-DAG, shortcuts account for 45–58% of correct answers and 88% on extreme legs; excluding them lowers accuracy from 31% to 14–17%.Shortcuts are genuine tool-chain reasoning rather than lucky guesses, but they exploit clue leakage and inflate difficulty-level accuracy.
  • L Full Benchmark Comparison: Table 10 compares AAR with 12 representative benchmarks across navigation, metrics, step-level evaluation, live data, difficulty control, gold traces, generation, and branching structure.The comparison reports linear and DAG instance fractions and mean pit stops per golden chain.
  • N Full Results Table: Table 11 reports main results for AAR-Linear and AAR-DAG using finish-line accuracy, pit-stop visit rate, and roadblock completion rate.These metrics correspond to FA, PVR, and RCR across both benchmark variants.
  • O Computational Resources: Codex CLI uses 1.4–1.8M tokens per trial, mini-swe-agent 149K–187K, and Claude Code 114–225K while Claude Code takes 292–320 seconds per trial.Table 12 reports mean input-plus-output tokens, mean wall-clock time, and cumulative agent time per configuration.
Loading 2604.10261v2…