Technical Summary: LLM-WikiRace

Problem Definition

Large Language Models (LLMs) have demonstrated proficiency in narrow domains such as mathematical reasoning or specific real-world tasks like trip planning. However, existing benchmarks often fail to evaluate how models leverage the breadth of world knowledge acquired during pre-training to perform active planning and reasoning in open-domain settings. While reasoning and world knowledge are frequently studied in isolation, real-world tasks require their tight integration.

The paper introduces LLM-WikiRace, a benchmark designed to evaluate an LLM's ability to navigate a real-world knowledge graph (Wikipedia) using only local information and internal knowledge. The task requires an agent to traverse from a source Wikipedia page to a target page by selecting hyperlinks step-by-step. Crucially, the agent does not have access to the global graph structure, shortest paths, or the content of unvisited pages; it must rely on pre-trained world knowledge to infer semantic connections and plan long-horizon action sequences.

Methodology

Benchmark Construction

• Graph Source: The benchmark is built on a Wikipedia snapshot from June 23, 2025. The authors retain the largest strongly connected component, resulting in a graph of 549,232 pages where every node is reachable from every other node.
• Task Mechanics: At each step, the model receives the current page title, the target page title, the history of visited pages, and a list of up to 50 outgoing link titles. The model must select one link to follow. The episode terminates upon reaching the target or exhausting a 30-step budget.
• Difficulty Stratification: The benchmark is divided into three difficulty levels based on the shortest path length between the source and target:
  • Easy: 200 pairs with path lengths of 3 or 4.
  • Medium: 150 pairs with path lengths of 5 or 6.
  • Hard: 100 pairs with path lengths of 7 or 8.
• Constraints: To ensure the task relies on internal knowledge rather than in-context retrieval, the body text of the current article is excluded from the prompt. The list of outgoing links is capped at 50; for pages with more links, the 50 closest to the target (in terms of shortest path) are selected, though this information is hidden from the model to prevent algorithmic shortcuts.

Evaluation Protocol

• Models Evaluated: A diverse set of over 20 models, including closed-source frontier models (Gemini 3.1, GPT-5, Claude Opus 4.6, Grok 4.1) and open-source models (LLaMA 3, Gemma 3, DeepSeek R1, Kimi K2, Mistral, Qwen, and diffusion-based models).
• Metrics:
  • Success Rate: The percentage of games completed within the step budget.
  • Suboptimal Steps: The average number of excess steps taken in successful games (measuring path efficiency).
  • World Knowledge Probe: A separate classification task where models predict if two pages are directly linked, used to correlate internal knowledge with planning performance.
• Analysis: The study includes trajectory-level analysis to examine planning strategies, replanning behaviors, and loop detection.

Key Contributions

1. A Benchmark for Open-Domain Planning: LLM-WikiRace is the first benchmark requiring interactive, multi-step planning over the full Wikipedia hyperlink graph, isolating the integration of world knowledge and long-horizon reasoning.
2. Identification of the "Planning Gap": The authors identify a significant performance divergence between "reasoning" models (e.g., GPT-5, DeepSeek R1) and standard "instruct-tuned" models. Despite possessing similar levels of world knowledge (as measured by a static probe), reasoning models achieve success rates up to 20 percentage points higher. This suggests that post-training for reasoning enhances the ability to deploy knowledge during planning.
3. Diagnosis of Replanning Failures: Trajectory analysis reveals that even the strongest models struggle to recover from errors. Models frequently enter loops (revisiting pages) and fail to effectively replan after recognizing a suboptimal path. There is a strong negative correlation between loop frequency and success rate.
4. Limits of Post-Training: Experiments fine-tuning a Qwen-2.5-7B model using the DAPO algorithm show that while post-training can improve performance on easy instances (increasing success from 22.5% to 67.5%), these gains do not transfer to medium or hard difficulties, which remain at 0% success.

Results

• Performance by Difficulty:
  • Easy Split: Frontier models achieve high success rates (>90%), with Gemini 3.1 leading at 96.0%.
  • Medium Split: Performance drops significantly, with top models (Gemini 3.1, Claude Opus 4.6) achieving roughly 50–70%.
  • Hard Split: Performance collapses. The best-performing model, Gemini 3.1, succeeds in only 29% of hard games. Most open-source models achieve near-zero success on this split.
• Model Comparison:
  • Gemini 3.1 outperforms all other models across all difficulty levels.
  • GPT-5 and Claude Opus 4.6 follow closely but show a notable performance drop on medium/hard splits compared to their predecessors or other variants (e.g., GPT-5.2 performed worse than GPT-5 on medium/hard).
  • Open-Source Models: Generally lag behind closed-source counterparts, particularly on hard instances. DeepSeek R1 and Kimi K2 are competitive but trail the top performers.
• Replanning Behavior: Analysis of successful vs. unsuccessful trajectories shows that models often exhibit "hub-seeking" strategies (moving to broad topics early) but fail to escape loops once formed. For instance, on hard tasks, Gemini 3 encountered loops in 86% of cases, with a success rate of only 10% for those looped trajectories.

Significance and Claims

The paper posits that LLM-WikiRace serves as a "simple benchmark" that exposes clear limitations in current reasoning systems. Its significance lies in:

• Isolating Planning Capabilities: By removing domain-specific complexities and tool-use quirks, the benchmark reveals that failures often stem not from a lack of reasoning ability alone, but from an inability to retrieve or apply world knowledge effectively during multi-step planning.
• Highlighting the Replanning Deficit: The benchmark demonstrates that current frontier models, while capable of initial planning, lack robust adaptive control. They frequently fail to revise strategies after failure, leading to repetitive loops.
• Defining the Frontier: The results indicate that while models have mastered the easy split, the hard split remains largely unsolved. The "planning gap" suggests that current post-training methods for reasoning are insufficient to fully bridge the divide between knowledge retrieval and effective long-horizon planning in complex, open-domain environments.

The authors conclude that LLM-WikiRace offers an open arena where planning-capable LLMs still have much to prove, particularly in their ability to navigate real-world knowledge graphs without algorithmic assistance.