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.
Figures & tables
Figure 1: Graph growth through SELECT and EXPAND. Successive panels show how the same target remains identifiable as named entities become variables and the graph expands. The final Monaco graph contains 16 relations after ten expansions.
Question type
Requested answer
Illustrative question
Identity
The target entity
Which race matches this description?
Year
A year from a target property or relation qualifier
In which year did this race take place?
Quantity
A measured value and its unit
How many laps long was this race?
Group
All entities pointing to the target through a specified property
Which drivers participated in this race?
Count
The number of entities in that group
How many drivers participated in this race?
Argmax
The group member with the highest value or latest date
Who was the youngest participant in this race?
Table 1: Multi-hop question types. Illustrative question endings after a description identifying a race. Group tasks use participation links; extrema compare participants’ dates of birth.
Stage
Multi-hop
Single-entity
Attempted seeds / selected facts
2,160
11,199
Certified graphs
2,003
—
Accepted questions
1,498
11,130
Attempted solving traces
1,224
11,130
Retained traces
672
9,563
Table 2: Generation and retention counts. Single-entity generation starts from selected facts. Each example counts once despite revisions or retries.
Function
Returned information
search_entity
Entities matching a name through labels and aliases, with the total match count
search_property
Properties matching a name, with the total match count
claims
Statements, typed values, ranks and qualifiers; preferred statements by default when present, otherwise non-deprecated statements
references
Recorded sources for statements, optionally restricted to one property
describe
Entity types, labels, descriptions, aliases and sitelinks across six languages
labels , label
Available labels across the six languages, or a label in one specified language
Table 3: Graph functions shared by both evaluation interfaces. The six languages are English, French, German, Chinese, Arabic and Russian.
Model
Interface
Single-entity
Multi-hop
Total
Cost/question
Qwen3.8-27B
RLM harness
46/50
28/50
74/100
$0.04 ∗
gpt-6-luna
RLM harness
42/50
19/50
61/100
$0.013
Qwen3.8-27B
tool-calling agent
40/50
20/50
60/100
$0.025 ∗
GLM-5.3-flash
tool-calling agent
37/50
13/50
50/100
$0.067
gpt-6-luna
tool-calling agent
40/50
9/50
49/100
$0.005
Gemini-3.1-flash-lite
tool-calling agent
31/50
10/50
41/100
$0.19
Table 4: Main evaluation results and execution patterns, ordered by total accuracy. gpt-6-luna and Qwen3.8-27B ran under both interfaces. Target reached counts runs whose graph calls touched the target entity, whether or not the final answer was correct. Graph calls are rounded means per run; tokens are median input plus output tokens per run. Repeats use a function and arguments already called in the same run; no answer counts runs that ended without a final answer: at the turn or cost limit or, for the eight Qwen3.8-27B agent runs, with an empty reply. ∗ Qwen costs estimate batched serving on one H100 through Google Colab; API costs use token prices.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Measure
50-seed study
100-seed study
Usable entities after root
.88 [.78, .96]
.81 [.68, .92]
Share of root bundles opening a three-hop chain
.82 [.70, .93]
—
Share of root bundles leaving a usable entity
.80 [.66, .91]
—
Number of three-hop chains
.78 [.64, .90]
—
Outgoing degree
—
.72 [.61, .82]
Number of valid root bundles
—
.71 [.58, .83]
Appendix
Table 5: Seed-level growth predictors. The first row uses the accepted root expansion; root-bundle and chain measures can be computed before a run. A dash indicates a measure not reported in that study.
Measure
Definition
AUC
Incoming/outgoing degree
Links pointing to/from the entity
.53/.56
Usable-condition count
Retained incoming and outgoing relations
.54
Largest valid bundle size
Most conditions in a valid bundle
.53
Describable-neighbour count
Neighbours with a valid bundle
.54
Entity-necessity query resolvability
Whether the target query resolves after replacing the name with an unconstrained variable
.78
Entity-necessity target-answer count
Number of target answers after that replacement; one means the name is redundant
.97 ∗
Appendix
Table 6: Predictors of successful entity expansion. Static measures use the 100-seed probe; entity-necessity measures use replayed trajectories. ∗ Computed only for resolvable queries.
Step
Hidden entity
Added conditions
1
Seed race
Location: Circuit de Monaco; part of: 1986 championship
Knowledge graph question answering (KGQA) requires navigating from topic entities to an answer several relations away. Recent methods prompt a frontier LLM to explore the graph through a retrieval tool, but their reliance on frontier-scale inference makes them costly to deploy. We present Search-on-Graph-R1 (\sogrone{}), which internalizes this navigation into a compact 8B model through supervised fine-tuning (SFT) followed by reinforcement learning (RL). Our central idea is to scaffold a frontier teacher with each question's gold SPARQL query, so the teacher traverses a known answer-bearing path with a live \texttt{Search} tool rather than having to discover the path itself. Since every call executes against a live Freebase server, the resulting trajectories are grounded in the knowledge graph by construction. On WebQSP, CWQ, and GrailQA, \sogrone{} at 8B surpasses every frozen frontier-LLM system in our comparison and posts the strongest results on CWQ of any system we compare against. It does so using no auxiliary module at inference and no LLM judge during training. Isolating each training stage shows that SFT and RL contribute complementary gains, our approach transfers across model families, and RL learns to reach answers in fewer \texttt{Search} calls than its SFT initialization.
Jia Ao Sun, Hao Yu, Fengran Mo +4
Université de Montréal · Mila – Québec AI Institute · McGill University +2
Large language models (LLMs) frequently generate confident yet factually incorrect content when used for language generation (a phenomenon often known as hallucination). Retrieval augmented generation (RAG) tries to reduce factual errors by identifying information in a knowledge corpus and putting it in the context window of the model. While this approach is well-established for document-structured data, it is non-trivial to adapt it for Knowledge Graphs (KGs), especially for queries that require multi-node/multi-hop reasoning on graphs. We introduce UltRAG, a training-free KG-RAG recipe that combines LLM query generation, a fully inductive neural query executor, and LLM arbitration. This off-the-shelf composition achieves state-of-the-art results on Knowledge Graph Question Answering (KGQA) tasks without retraining the LLM or executor, while enabling language models to interface with Wikidata-scale graphs (116M entities, 1.6B relations) at comparable or lower costs. Our ablation studies indicate that these gains come from the full system design rather than from any single component.
Dobrik Georgiev, Kheeran K. Naidu, Alberto Cattaneo +3
Agentic retrieval improves multi-hop question answering by giving language models autonomy to iteratively gather evidence. Recent work augments these systems with knowledge graphs for structured traversal, but this combination introduces significant cost: expensive graph construction at index time and compounding token usage at inference time. We introduce Graph Agentic Search over Propositions (GRASP), an agentic system that simultaneously optimizes for high accuracy and minimal token usage in multi-hop question answering. Rather than executing a rigid, singular query, GRASP actively coordinates its retrieval strategy by decomposing multi-hop queries into dependency-aware plans. This enables GRASP to dynamically scale the number of sub-agents according to the complexity of the problem. Each sub-agent resolves its single-hop query by exploring a novel three-layer hierarchical graph of entities, propositions, and passages, using the entity layer for targeted traversal and the proposition layer for high-recall passage retrieval via reciprocal-rank voting. We evaluate GRASP on MuSiQue, 2WikiMultihopQA, and HotpotQA under two settings: open-corpus retrieval and extended context reasoning (LongBench). GRASP achieves the highest QA accuracy in the open retrieval setting on MuSiQue and 2Wiki while using 40-50 percent fewer tokens than IRCoT+HippoRAG2. Furthermore, GRASP leads on EM and F1 across all three datasets in the LongBench setting while using 30 percent fewer tokens than the next most accurate method. Finally, we introduce success economy - the amortized token cost per correct answer, weighted by difficulty - and advocate for efficiency-aware evaluation as a standard practice for agentic QA.
Stockton Jenkins, Ramya Korlakai Vinayak, Junjie Hu