# Wikidata Search Traces: A Dataset for Training Knowledge Graph Search Agents

arXiv: https://arxiv.org/abs/2610.06650 · HTML: https://mlsanity.com/paper/2610.06650/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Web, search, and research agents, one of 16 directions in LLM agents and tool use.
- Builds on 20 of its 26 references that are in the map.
- First posted on arXiv 5 Oct 2026.

## Placed in

- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 20 of 20)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [Executable Code Actions Elicit Better LLM Agents](https://mlsanity.com/paper/2402.01030/) (2024)
- [Large Language Models Struggle to Learn Long-Tail Knowledge](https://mlsanity.com/paper/2211.08411/) (2022)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [WebSailor: Navigating Super-human Reasoning for Web Agent](https://mlsanity.com/paper/2507.02592/) (2025)
- [Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases](https://mlsanity.com/paper/2011.07743/) (2020)
- [WebShaper: Agentically Data Synthesizing via Information-Seeking Formalization](https://mlsanity.com/paper/2507.15061/) (2025)
- [Recursive Language Models](https://mlsanity.com/paper/2512.24601/) (2025)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [KQA Pro: A Dataset with Explicit Compositional Programs for Complex Question Answering over Knowledge Base](https://mlsanity.com/paper/2007.03875/) (2020)
- [DeepDive: Advancing Deep Search Agents with Knowledge Graphs and Multi-Turn RL](https://mlsanity.com/paper/2509.10446/) (2025)
- [REDSearcher: A Scalable and Cost-Efficient Framework for Long-Horizon Search Agents](https://mlsanity.com/paper/2602.14234/) (2026)
- [Open Data Synthesis For Deep Research](https://mlsanity.com/paper/2509.00375/) (2025)
- [Prime Agent: A Self-Improving RLM Harness](https://mlsanity.com/paper/2608.23552/) (2026)
- [Diagnosing and Addressing Pitfalls in KG-RAG Datasets: Toward More Reliable Benchmarking](https://mlsanity.com/paper/2505.23495/) (2025)
- [LoHoSearch: Benchmarking Long-Horizon Search Agents Beyond the Human Difficulty Ceiling](https://mlsanity.com/paper/2606.12837/) (2026)
- [SearchArt: Training Long-Horizon Search Agent with Scalable Synthetic and Verified Task](https://mlsanity.com/paper/2607.24850/) (2026)
- [The Wikidata Query Logs Dataset](https://mlsanity.com/paper/2602.14594/) (2026)

## Abstract (arXiv)

Wikidata is one of the largest open knowledge bases, yet answering a complex question over it still requires a SPARQL query that names the right entities and properties and chains their relations. Language models offer a natural-language alternative but answer largely from memory, which is least reliable for less prominent entities. We study agents that instead answer by exploring the graph, and argue that two obstacles limit them: the lack of training data recording how a solver explores, and interfaces that add large graph results directly to the model's context. We test three hypotheses: that the difficulty of graph search can be controlled through the structure of a question rather than only through obscure entities or wording; that much of the failure on long-horizon search comes from how retrieved evidence is managed rather than from the model itself; and that, in a suitable environment, open-weight models can match commercial closed ones. We construct multi-hop questions on a frozen Wikidata snapshot by replacing named entities with nested conditions, checking after each expansion that the target remains unique and that every new condition is necessary. We release 10,235 solving traces over single-entity and multi-hop questions, together with the recursive language model (RLM) harness that produced them, in which models batch graph calls, keep results in persistent Python state and interpret selected evidence through sub-calls. On 100 questions, the harness improves both models we ran under both interfaces compared with direct tool calling over the same functions: gpt-6-luna rises from 49 to 61 correct answers, doubling its multi-hop accuracy, and Qwen3.8-27B, an open-weight model served on a single GPU, from 60 to 74.