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
Figures & tables
Figure 1: (a) Existing benchmarks are 55 to 100% linear; AAR is 0% linear (all DAGs). Numbers in parentheses show mean steps per instance (abbreviated “s”). (b) Best agent accuracy is 36.6% (aggregated across 1,400 legs). (c) Navigation errors dominate (5% to 52%) while tool-use errors stay below 15%.
Evaluation
Design
Compositionality
Benchmark
Venue
Tools
Nav
Met
Stp
Lve
Diff
Gld
Gen
Steps
%Lin
%DAG
Tool-use & composition
ToolBench
ICLR’24
16k+
✗
2
✗
✓ †
3 lvl
✓
Auto
1.9
100
0
TaskBench
NeurIPS’24
graph
✗
3
✓
✗
size
✓
Auto
1.7
94
2.5
NESTFUL
arXiv’24
nest
✗
2
✓
✗
depth
✓
Scr
3.4
55
45
Web navigation & agent
Table 1: Comparison with representative benchmarks (3 per category; full table with 12 benchmarks in Appendix L ). † ToolBench suffers API instability. ‡ GAIA step count from annotator metadata only.
Figure 2: An example clue envelope (or a “leg”) as presented to the agent.
Figure 3: Diamond pattern structure.
Figure 4: The eight-step automated pipeline for generating AAR benchmark legs. Each leg passes a validation gate before producing evaluation targets: finish-line accuracy (FA), pit-stop visit rate (PVR), and roadblock completion rate (RCR).
Var.
Level
Legs
Stops
RB
Det.
Tools
AAR - Lin.
Easy
200
5.4
1.1
1.0
1.4
Medium
200
11.7
2.3
2.3
2.9
Hard
200
18.7
4.1
3.9
5.0
Extreme
200
24.3
5.4
5.3
6.6
All
800
15.0
3.2
3.1
4.0
AAR - DAG
Easy
100
8.3
3.6
1.0
4.8
Table 2: Dataset statistics. Stops : mean per leg. RB : roadblocks. Det. : detours. Tools : tool invocations in the golden trace.
Figure 5: (a) Aggregate results across all 1,400 legs (weighted average of Linear and DAG). FA (finish-line accuracy), PVR (navigation), RCR (tool use). Best FA is 36.6% (Claude + Sonnet 4); PVR is consistently the weakest metric. (b) FA degrades monotonically with difficulty (best: − 13.5 pp, worst: − 19.0 pp). Per-variant breakdown in Appendix M .
Figure 6: DAG structure penalizes navigation, not tool use.
Level
Nav.
Tool
Comp.
Corr.
Linear
Easy
5.0
15.0
40.0
40.0
Medium
20.0
10.0
32.5
37.5
Hard
46.5
6.0
16.5
31.0
Extreme
52.0
3.5
20.5
24.0
All
30.9
8.6
27.4
33.1
DAG
Easy
24.0
9.0
41.0
26.0
Table 3: Error decomposition (%) for Codex CLI + GPT-5.4-mini. Nav. errors increase +16pp on DAG while tool errors decrease − 5pp despite 3 × longer chains.
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Level
Pit Stops
Roadblocks
Detours
Diamonds
Extraction
Crawl
Easy
3–6
1–2
1–2
1
infobox, prose
1
Medium
7–12
2–4
2–3
1–2
+ cross-section
2
Hard
13–16
4–5
3–4
2–3
+ cross-section
3
Extreme
17–21
5–7
4–6
3–5
+ cross-section
3
Appendix
Table 4: Difficulty level parameters (pre-augmentation). Pit Stops : configured range before diamond insertion. Diamonds : fork–merge patterns that create non-linear DAG dependencies (§ 3.3 ). Crawl : Wikipedia link-graph hops available for route planning. After diamond augmentation, each diamond adds 3 stops (two branches + merge), so actual pit-stop counts exceed these ranges.
Category
Tool
Description
Fetch & Search
fetch_webpage
Fetch and parse web content
web_search
Google search via Serper API
Google Maps
maps_geocode
Address to coordinates
maps_reverse_geocode
Coordinates to address
maps_search_places
Search nearby places
maps_place_details
Place metadata and ratings
Appendix
Table 5: The 19 tools available to agents, organized by category.
Template
Requires
Produces
geocode_elevation
location
elevation
geocode_weather_historical
location, date
temperature
geocode_weather_precipitation
location, date
precipitation
geocode_distance
2 locations
distance
geocode_directions_duration
2 locations
duration
date_computation
date
day count
Appendix
Table 6: Roadblock templates. Each composes 1–3 tool calls.
FA (%) by Config
Template
N
C 5.4
C m
M 5.4
M m
Avg
date_comp
202
48.0
40.6
40.6
31.7
40.2
math_conv
298
39.9
35.2
30.2
28.2
33.4
geocode_dist
41
39.0
34.1
36.6
22.0
32.9
country_area
44
31.8
29.5
31.8
22.7
29.0
country_pop
209
34.4
29.2
28.2
22.0
28.5
Appendix
Table 7: Per-template FA (%) on AAR -Linear. N : legs containing this template. C : Codex CLI. M : mini-swe-agent. m : GPT-5.4-mini.
Stops
FA (%)
PVR (%)
RCR (%)
N
3–8
40.2
83.5
71.6
199
9–14
36.2
62.4
57.5
185
15–20
32.6
41.3
47.1
215
21–26
24.7
38.6
44.3
178
27–40
17.4
35.8
37.5
23
Appendix
Table 8: Scaling behavior: FA, PVR, and RCR as a function of leg length (number of pit stops) for Codex CLI + GPT-5.4-mini on AAR -Linear.
PVR ≥ 0.8 → FA = 1
Both ≥ 0.8 → FA = 1
Config
Lin.
DAG
Lin.
DAG
Codex + 5.4
45.0
30.6
50.3
31.7
Codex + 5.4-mini
44.1
36.0
47.0
30.0
MSWA + 5.4
43.6
30.8
48.3
39.4
MSWA + 5.4-mini
38.5
28.9
39.0
62.5 †
Appendix
Table 9: Recovery rates (%): FA conditioned on high partial metrics. Lin. : AAR -Linear. DAG : AAR -DAG. † Based on only 8 legs.
Evaluation
Design
Compositionality
Benchmark
Venue
Tools
Nav
Met
Stp
Lve
Diff
Gld
Gen
Steps
%Lin
%DAG
Tool-use & composition
ToolBench
ICLR’24
16k+
✗
2
✗
✓ †
3 lvl
✓
Auto
1.9
100
0
BFCL
ICML’25
2k+
✗
3
✗
✗
cat
✓
Mix
–
–
–
TaskBench
NeurIPS’24
graph
✗
3
✓
✗
size
✓
Auto
1.7
94
2.5
T-Eval
ACL’24
mult
✗
6
✓
✗
2 lvl
✓
Man
4.8
62
14
Appendix
Table 10: Full comparison with 12 representative benchmarks (condensed version in Table 1 ). Nav : navigation required. Met : number of metrics. Stp : step-level evaluation. Lve : live API data ( † ToolBench suffers instability). Diff : difficulty control. Gld : verified gold trace. Gen : generation method (Auto/Man/Scr/Mix). Steps : mean pit stops per golden chain. %Lin / %DAG : fraction of strictly linear vs. branching instances. ‡ GAIA step count from annotator metadata (validation split only).
Figure 7: Main results on both benchmark variants: (a) AAR -Linear (800 legs, 6 configs including GPT-OSS-120B), (b) AAR -DAG (600 legs, 5 configs). PVR drops 13 to 18pp from Linear to DAG while RCR remains stable or increases.
Figure 8: Per-difficulty breakdown on AAR -Linear. Navigation quality degrades far faster than tool-use competence.
AAR -Linear (800 legs)
AAR -DAG (600 legs)
Agent
Model
Level
FA
PVR
RCR
FA
PVR
RCR
Codex CLI
GPT-5.4
Easy
45.0
88.7
82.8
26.0
76.1
86.8
Medium
39.5
71.5
73.4
30.0
55.5
75.5
Hard
32.5
43.8
57.4
31.9
32.6
64.0
Extreme
31.5
37.1
49.2
35.9
24.3
55.3
All
37.1
60.3
65.7
31.7
43.0
68.0
Appendix
Table 11: Main results (%) on both benchmark variants. FA : finish-line accuracy. PVR : pit-stop visit rate. RCR : roadblock completion rate.
Agent
Model
Tok.
Time
Total
AAR -Linear (800 legs per config)
Codex CLI
GPT-5.4
1.44M
211 s
46.9 h
Codex CLI
GPT-5.4-mini
1.66M
92 s
20.4 h
mini-swe
GPT-5.4
154K
58 s
12.8 h
mini-swe
GPT-5.4-mini
156K
31 s
6.9 h
Claude Code
Sonnet 4
225K
292 s
65.0 h
Appendix
Table 12: Computational resources per configuration. Tok. : mean input + output tokens per trial. Time : mean wall-clock time per trial. Total : cumulative agent time.