Can a Recursive Language Model Harness Improve Knowledge Graph Search Agents?

Two obstacles limit agents that explore Wikidata

Wikidata holds explicit, sourced statements, but combining them normally requires a SPARQL query that names the right entities and properties and chains their relations. A language model can answer in natural language instead, yet it answers largely from memory, which the paper says is least reliable for less prominent entities and gives no account of where an answer comes from. The study therefore examines agents that answer by exploring the graph rather than recalling it.

The paper argues two obstacles hold these agents back. The first is data: training an agent to explore requires traces of exploration over tasks whose difficulty can be varied and whose answers can be checked, and on the open web it is hard to certify that a question has exactly one answer and that each clue is needed. A frozen knowledge graph allows both checks. The second is the interface: one navigation step on a hub entity can return thousands of neighbours and statements, and tool-calling agents add those results to their conversation, where long-context studies show models miss evidence depending on its position and lose accuracy as input grows.

Questions are grown by hiding named entities

The authors represent a question as a set of constraints on an unknown answer, where a condition restricts the answer through one property and a set of entities. A condition's candidate count is the number of entities in the whole graph that satisfy it alone; participation in the 24 Hours of Le Mans, for example, has a candidate count of 2,331. The paper uses this count as a proxy for ambiguity, since a condition with more candidates restricts the answer less on its own.

To add difficulty, two operators turn a named entity into a hidden one. SELECT chooses which named entity to hide next, and EXPAND replaces its singleton set with a bundle of one to three conditions describing that entity. Repeating the pair adds nested dependencies. Each expansion must pass two checks: certification, meaning the complete question graph identifies the seed alone, and necessity, meaning removing any new condition admits another answer. The authors also reject clues that reveal hidden names and require each condition to match at least two candidates.

Questions are built on a frozen Wikidata snapshot from February 2026 with about 48 million entities and 262 million facts. Seeds vary by entity type, language and prominence, with a share described only in Arabic, Russian or Chinese, and a long-tail score samples popular, moderate and rare seeds. The authors selected 2,973 seeds and attempted generation from 2,160 of them, requiring at least three expansions and depth three, with limits of ten expansions and depth seven.

The harness stores evidence instead of flooding context

The evaluation compares two interfaces to the same 13 graph functions. The RLM harness gives the model a persistent Python REPL where it can combine function calls, filter results and store intermediate data in variables. The tool-calling agent receives the functions as tools and their outputs as conversation messages, implemented with the OpenAI Agents SDK. Because both interfaces use the same functions, the paper says the main difference concerns how the model orchestrates calls and manages retrieved evidence.

The harness also provides llm_query and llm_map helpers that interpret supplied evidence through model sub-calls, and these helpers have no graph access. The main model stores and filters graph results in Python. The authors note that the evaluation tests this combined interface rather than isolating the effect of recursive calls.

Budgets do not equalize graph calls: agents allow up to 100 model calls and a $0.50 cost cap per question, while RLM runs allow up to 100 turns and 80 sub-calls, and a Python cell can execute many graph calls. Both interfaces truncate visible outputs at 10,000 characters. The paper reports graph calls alongside accuracy for this reason.

Both models improve under the harness

On 100 questions, 50 single-entity and 50 multi-hop, the harness improves both models that ran under both interfaces. gpt-6-luna rises from 49 to 61 correct answers, and Qwen3.8-27B, an open-weight model served on a single GPU, from 60 to 74. The multi-hop split shows the sharper change: gpt-6-luna goes from 9 to 19 out of 50, doubling its multi-hop accuracy, while Qwen3.8-27B goes from 20 to 28 out of 50.

The gain tracks reaching the target rather than interpreting it better. On the 50 multi-hop questions, gpt-6-luna reaches the target entity in 17 runs as an agent and 35 under the harness; Qwen3.8-27B goes from 27 to 39. Once the target is reached, each model's share of correct answers stays about the same under both interfaces. The authors read this as consistent with evidence management, rather than the model itself, limiting long-horizon search, while noting the comparison holds for two models under unmatched graph-call budgets.

The open-weight model also produced the highest score of the evaluation, 74 out of 100, above gpt-6-luna under both interfaces: 74 against 61 in the harness and 60 against 49 as an agent. GLM-5.3-flash and Gemini-3.1-flash-lite ran only as tool-calling agents, scoring 50 and 41 out of 100.

Multi-hop questions stay harder in every configuration

Multi-hop questions are markedly harder than single-entity ones in every configuration tested: 9 to 28 correct out of 50, against 31 to 46. The paper is explicit that this gap also reflects other differences between the two sets, so it does not yet show that difficulty follows the depth or number of expansions. Testing that claim would require an analysis by graph structure and a human estimate of how faithfully written questions preserve their graphs.

This is the study's first hypothesis, about whether graph-search difficulty can be controlled through question structure rather than only through obscure entities or wording. Certification and necessity give a checkable way to grow questions whose conditions must all be used, but the paper treats the structural explanation as still open.

The released traces carry reasoning only from the open model

The authors release 10,235 solving traces over single-entity and multi-hop questions, together with the RLM harness that produced them. Which model generated a trace changes what it contains. Commercial frontier models such as gpt-6-luna reason internally and return only a final reply, whereas Qwen3.8-27B returns its full reasoning, which the harness records beside the code, outputs and graph calls of each turn. Traces from an open model can therefore include the reasoning behind each action and can be produced locally without per-token costs or provider terms restricting their use for training.

The traces were collected with graph-derived clues to the solution path in the model's prompt, and the published prompts omit these clues. The paper states that collection therefore favours direct routes with few dead ends, and that each question graph identifies one target with a fixed expected answer, so the dataset provides no examples with several valid answers or none.

The evidence bears unevenly on the three hypotheses

The harness result is the strongest of the three hypotheses, and it holds for two models under unmatched graph-call budgets. The openness result is a single evaluation: an open-weight model served on one H100 GPU scores highest, but whether the traces pass that ability on to smaller models remains untested. The authors propose fine-tuning a smaller open model around 12B parameters on the traces and evaluating it in the same harness against its base model.

The structural hypothesis is the least settled, because the multi-hop gap is confounded with other differences between the two question sets. Broader testing would also require running GLM-5.3-flash and Gemini-3.1-flash-lite in the harness, repeating runs on a larger question set, matching graph-call budgets, and enabling or disabling the sub-call helpers to show which parts of the harness contribute most.

The decisive test is training a smaller open model

For readers weighing whether to adopt this approach, the paper's own priority ordering matters more than the headline accuracy. The harness gain is demonstrated with the model held fixed, so it is the most transferable finding: the environment around the model, not only the model, carries part of the capability on structured public knowledge. The open-weight result is a single configuration on one GPU, and the structural claim about question difficulty is explicitly unresolved.

The next step the authors single out is fine-tuning a smaller open model, around 12B parameters, on the released traces and evaluating it in the same harness against its base model. That test would show whether the traces make a model smaller than 27B usable on these questions, which is the question that decides whether the dataset, rather than the harness alone, is the reusable contribution.

Sources used in this answer