The Compositional Reasoning Bottleneck

Agents are strong tool users and weak navigators. Given a well-specified single call they perform; asked to compose a sequence of steps toward a goal, they degrade sharply. On a DAG-structured benchmark of 1,400 Wikipedia navigation tasks, the best agents reached only 37.2% accuracy, with navigation errors accounting for 27–52% of all failures.

The shape of that result matters more than the headline. The failures are not concentrated in tool invocation or extraction — the agent typically calls the right tool correctly and reads the page correctly, then chooses the wrong next step. Compositional reasoning, not capability at any individual step, is the frontier bottleneck.

This is also why more capable models have not closed the gap: each step was already being executed well. The identified remedy is structural rather than a matter of scale — constructing an explicit problem model before generating a solution reduces constraint violations against both chain-of-thought and ReAct across five planning domains. Making the plan a first-class artifact the agent reasons over, rather than an implicit trajectory, is a harness decision.

Key Claims

• 37.2% best-agent accuracy on 1,400 DAG-structured navigation tasks; navigation errors are 27–52% of failures. Evidence: strong (paper) (The Amazing Agent Race)
• Compositional reasoning is the primary frontier bottleneck, not per-step tool competence. Evidence: strong (paper) (The Amazing Agent Race)
• Explicit problem-model construction reduces constraint violations vs CoT and ReAct across five planning domains. Evidence: moderate (paper) (Model-First Reasoning)