2026-07-22 04:00 UTCOriginal source2 min readUpdated: 2026-07-22 08:31 UTC

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning

Search-on-Graph-R1 internalizes knowledge graph navigation into a compact 8B model using supervised fine-tuning and reinforcement learning, outperforming frozen frontier-LLM systems on multiple benchmarks without auxiliary modules at inference or LLM judges during training.

SourcearXiv Computational LinguisticsAuthor: Jia Ao Sun, Hao Yu, Fengran Mo, Zhan Su, Yuchen Hui, Bang Liu, Jian-Yun Nie

-->

[Submitted on 20 Jul 2026]

Title:Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning

View a PDF of the paper titled Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning, by Jia Ao Sun and 6 other authors

View PDF HTML (experimental)

Abstract: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.

Subjects:

Computation and Language (cs.CL)

Cite as: arXiv:2607.18481 [cs.CL]

(or arXiv:2607.18481v1 [cs.CL] for this version)

https://doi.org/10.48550/arXiv.2607.18481

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Jia Ao Sun [view email] [v1] Mon, 20 Jul 2026 19:58:32 UTC (190 KB)

Full-text links:

Access Paper:

View a PDF of the paper titled Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning, by Jia Ao Sun and 6 other authors

View PDF

HTML (experimental)

TeX Source

view license

Current browse context:

cs.CL

new | recent | 2026-07

Change to browse by:

References & Citations

NASA ADS

Google Scholar

Semantic Scholar

Data provided by:

Bibliographic Tools

Bibliographic and Citation Tools

Bibliographic Explorer Toggle

Bibliographic Explorer (What is the Explorer?)

Connected Papers Toggle

Connected Papers (What is Connected Papers?)

Litmaps Toggle

Litmaps (What is Litmaps?)

scite.ai Toggle

scite Smart Citations (What are Smart Citations?)

Code, Data, Media

Code, Data and Media Associated with this Article

alphaXiv Toggle

alphaXiv (What is alphaXiv?)

Links to Code Toggle

CatalyzeX Code Finder for Papers (What is CatalyzeX?)

DagsHub Toggle

DagsHub (What is DagsHub?)

GotitPub Toggle

Gotit.pub (What is GotitPub?)

Huggingface Toggle

Hugging Face (What is Huggingface?)

ScienceCast Toggle

ScienceCast (What is ScienceCast?)

Demos

Replicate Toggle

Replicate (What is Replicate?)

Spaces Toggle

Hugging Face Spaces (What is Spaces?)

Spaces Toggle

TXYZ.AI (What is TXYZ.AI?)