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