💬 NLP

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

Het artikel introduceert Search-on-Graph-R1, een model met 8 miljard parameters dat een state-of-the-art prestatie levert in Knowledge Graph Question Answering door grafische navigatie te internaliseren via supervised fine-tuning en reinforcement learning, waarbij het grotere frontier LLM's overtreft zonder dat er tijdens de inferentie hulpmodules of LLM-beoordelaars nodig zijn.

Oorspronkelijke auteurs: Jia Ao Sun, Hao Yu, Fengran Mo, Zhan Su, Yuchen Hui, Bang Liu, Jian-Yun Nie

Gepubliceerd 2026-07-22

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Jia Ao Sun, Hao Yu, Fengran Mo, Zhan Su, Yuchen Hui, Bang Liu, Jian-Yun Nie

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme, meerstaps mystery probeert op te lossen, zoals uitzoeken wie de burgemeester van een stad is, maar dan alleen als die stad een specif kind soort zeldzame boom laat groeien. Om dit op te lossen, kun je niet alleen vertrouwen op je eigen geheugen; je brein zou de naam van de boom of de stad vergeten kunnen zijn, of het zou feiten uit oude films met elkaar kunnen verwarren. In plaats daarvan heb je een kaart nodig. In de wereld van kunstmatige intelligentie wordt deze kaart een Knowledge Graph genoemd. Het is een gigantisch, digitaal web waar elk feit een stip (entiteit) is, verbonden door lijnen (relaties). Als je een antwoord wilt vinden, moet je van stip naar stip "springen", de lijnen volgen totdat je bij de juiste aankomt.

Lange tijd waren de slimste computereigenwijzen (genaamd Large Language Models of LLM's) als briljante detectives die elk boek in de bibliotheek hadden gelezen, maar de kaart niet konden lezen. Ze moesten het antwoord raden op basis van wat ze zich herinnerden, wat vaak tot fouten leidde. Nieuwere methoden leerden deze modellen om te stoppen met gokken en een "zoektool" te gebruiken om over de kaart te springen, maar de modellen die de zoekopdrachten uitvoerden, waren als dure, superkrachtige robots die een fortuin kostten om te draaien en te traag waren voor echt gebruik. De grote vraag voor wetenschappers werd: Kunnen we een kleinere, goedkopere, snellere robot leren om ditzelfde kaart-springende detectivewerk net zo goed te doen, zonder de hulp van de dure robot te nodig hebben?

Dit is precies wat het artikel Search-on-Graph-R1 (SOG-R1) beoogt te doen. De onderzoekers bouwden een slim trainingssysteem om een compact AI-model met 8 miljard parameters (een "student") te leren hoe het zelfstandig door deze kenniskaarten kan navigeren. In plaats van de student gewoon te laten gokken, creëerden ze een "leraar"-robot die het geheime pad naar het antwoord al kende. Maar hier is de truc: de leraar kreeg niet alleen het antwoord gefluisterd; de leraar kreeg de blauwdruk van de kaart (een speciale query genaamd SPARQL) en kreeg de opdracht om het pad stap voor stap te bewandelen met behulp van dezelfde zoektool die de student zou gebruiken. Terwijl de leraar liep, legde hij elke beweging, elke doodlopende weg die hij vermeed, en elk feit dat hij uit de live database vond, vast.

De student leerde vervolgens uit deze geregistreerde reizen in twee fasen. Eerst oefende hij door de voetstappen van de leraar na te bootsen (Supervised Fine-Tuning), waarbij hij leerde hoe hij de juiste vragen moest stellen en de kaart moest lezen. Ten tweede speelde hij een spel waarbij hij probeerde zelfstandig antwoorden te vinden, waarbij hij punten kreeg voor het zijn van correct en extra punten voor het zijn van snel (Reinforcement Learning). Het resultaat? Deze kleine, 8 miljard-parameter student werd een meesterdetective. Op drie belangrijke testterreinen (WebQSP, CWQ en GrailQA) presteerde hij beter dan elk enkel "bevroren" super-robot systeem waartegen de onderzoekers hem vergeleken, inclusief die ondersteund door de meest geavanceerde, dure modellen die beschikbaar zijn.

Wat dit zelfs nog indrukwekkender maakt, is dat de student niet alleen beter werd in het vinden van antwoorden; hij werd slimmer in hoe hij zocht. Hoewel het pad van de leraar perfect was, leerde de student af te snijden. Hij ontdekte hoe hij dezelfde antwoorden kon bereiken met minder zoekoproepen dan hij deed toen hij alleen de leraar aan het kopiëren was. De onderzoekers ontdekten dat deze methode werkt, zelfs als je de student vervangt voor een ander type model, wat bewijst dat de trainingsmethode zelf het geheime ingrediënt is. Cruciaal is dat het artikel de gedachte weerlegt dat het model de hele kaart moet onthouden of moet vertrouwen op een tweede "rechter"-robot om zijn werk tijdens de training te beoordelen. In plaats daarvan leerde het model te vertrouwen op de live zoektool en de logica van het pad zelf. Aan het einde van de training kon deze kleine, efficiënte AI sneller en nauwkeuriger door complexe kennisweefsels navigeren dan zijn veel grotere, duurdere tegenhangers, en dat allemaal zonder extra helpers of dure hardware tijdens de daadwerkelijke zoektocht te nodig te hebben.

Technische Samenvatting: Search-on-Graph-R1 (SOG-R1)

Probleemstelling

Knowledge Graph Question Answering (KGQA) vereist navigatie van onderwerp-entiteiten naar antwoorden die mogelijk meerdere relaties verwijderd zijn. Hoewel recente benaderingen hebben aangetoond dat geavanceerde frontier Large Language Models (LLM's) een competitieve nauwkeurigheid kunnen bereiken door te interageren met Knowledge Graphs (KG's) via retrieval-tools, vertrouwen deze methoden op dure, bevroren frontier-modellen (bijv. GPT-4) die onpraktisch zijn voor productie vanwege latentie, kosten en toegangsbeperkingen.

Bestaande pogingen om kleinere, open-source modellen te post-trainen om deze capaciteit te repliceren, kampen met aanzienlijke beperkingen:

Semantische Parsing-benaderingen: Deze trainen modellen om een volledige logische vorm (bijv. SPARQL) in één enkele passage uit te stoten. Ze hebben moeite wanneer de vereiste schema-elementen niet tijdens de training zijn gezien.
Gescheiden Retrieval en Redeneren: Sommige methoden (bijv. EoG) extraheren offline statische subgrafen, waarbij de nauwkeurigheid wordt begrensd door de recall van de preprocessing-stap. Anderen (bijv. KG-Hopper) gebruiken live zoekopdrachten maar vertrouwen op externe LLM-judges om redeneersporen te verifiëren, wat stochastiek en computationele overhead introduceert.
Parametrische Fallback: Veel systemen staan toe dat modellen terugvallen op parametrisch geheugen wanneer retrieval faalt, wat betekent dat de geciteerde feiten niet gegarandeerd in de KG aanwezig zijn.

De kernuitdaging is het internaliseren van KG-navigatie in een compact model (bijv. 8B parameters) dat live retrieval en redeneren uitvoert zonder hulpmodules, externe judges of afhankelijkheid van parametrisch geheugen.

Methodologie: SOG-R1

SOG-R1 pakt deze uitdagingen aan via een tweetraps post-training pipeline toegepast op een compact, instructie-getuned student-model (Llama-3.1-8B-Instruct). De aanpak versmelt retrieval en redeneren in een enkele loop waarbij het model beslist wat het ophaalt via live Search-calls.

1. SPARQL-Scaffolded Cold-Start Trace Generation

Om het vermogen van het model om door de KG te navigeren te initialiseren, genereren de auteurs hoogwaardige trainings-trajecten met behulp van een "teacher"-strategie:

Teacher Setup: Een frontier-schaal teacher LLM (Qwen3-235B) krijgt de vraag en de bijbehorende gold SPARQL query te zien.
Scaffolding: In plaats van de teacher te vragen het pad te ontdekken, fungeert de gold SPARQL query als een blauwdruk. De teacher gebruikt dezelfde live Search tool die de student zal gebruiken om het bekende, antwoord-dragende pad te traverseren.
Gronding: Elke tool call wordt uitgevoerd tegen een live Freebase server. Dit zorgt ervoor dat de resulterende trajecten door constructie gegrond zijn in de KG, inclusief geldige tool calls, observaties en het uiteindelijke antwoord.
Filtering: Trajecten worden alleen behouden als het uiteindelijke antwoord exact overeenkomt met het gold antwoord en alle calls zonder fouten worden uitgevoerd.

2. Fase 1: Supervised Fine-Tuning (SFT)

Het student-model wordt gefinetuned met behulp van Low-Rank Adaptation (LoRA) op de verzamelde teacher-trajecten.

De trainingsdata wordt geserialiseerd als multi-turn conversaties waarbij de assistant-turns tool calls zijn en de tussenliggende turns de geretourneerde observaties zijn.
Het model leert om tool calls en antwoorden te produceren op basis van de context, zonder getraind te worden om de tool outputs zelf te voorspellen.
Deze fase produceert SOG-SFT, wat een sterke navigatie-prior vestigt.

3. Fase 2: Reinforcement Learning (RL)

Het SFT-model wordt verder verfijnd met behulp van Group Relative Policy Optimization (GRPO) met een deterministische outcome reward.

Reward Functie: De reward is het product van drie factoren:
1. Format Gate ( $g$ ): Zorgt ervoor dat het model de tool minstens één keer aanroept en netjes afsluit met een "Final answer:" string.
2. Exact-Match ( $r_{em}$ ): Geeft 1 terug als de voorspelde antwoordset overeenkomt met het gold antwoord, anders 0.
3. Efficiency Factor ( $f$ ): Een multiplicatieve straf voor excessieve tool calls (turns), wat kortere paden onder correcte trajecten aanmoedigt.
Belangrijke Beperking: De reward loop bevat geen LLM-judge en geen gold-pad supervisie; het vertrouwt uitsluitend op de correctheid van het uiteindelijke antwoord en de efficiëntie van het pad.

Tool Innovatie

De auteurs introduceren een Batched 1-Hop Neighbour Retrieval tool. In tegenstelling tot eerdere tools die één call per entiteit vereisten, accepteert deze tool een lijst met entiteiten in één enkele call. Dit voorkomt dat het model entiteiten verliest bij het uitbreiden van meerdere nodes in dezelfde hop, wat de inference kosten en foutpercentages vermindert.

Belangrijkste Resultaten

Het model werd geëvalueerd op drie standaard Freebase-gebaseerde benchmarks: WebQSP, CWQ, en GrailQA.

Prestaties vs. Bevroren Frontier Modellen: De 8B SOG-R1 overtreft elk bevroren frontier-LLM systeem (inclusief GPT-4 gebaseerde methoden zoals ToG, PoG, en LMP) op alle drie de benchmarks.
Prestaties vs. Post-getrainde Systemen:
- SOG-R1 bereikt de sterkste CWQ nauwkeurigheid (88.7%) van alle vergeleken systemen, waarmee het andere post-getrainde modellen zoals ChatKBQA (86.0%) en EoG (82.6%) overtreft.
- Op WebQSP en GrailQA behaalt het resultaten die vergelijkbaar zijn met of licht onder de beste post-getrainde systemen (EoG) liggen, maar met het duidelijke voordeel dat het live retrieval uitvoert in plaats van te redeneren over een statische, vooraf geëxtraheerde subgraaf.
- Vergelijking met KG-Hopper: Tegenover het meest vergelijkbare gelijktijdige systeem (KG-Hopper, eveneens Llama-3.1-8B), laat SOG-R1 significante winst zien (+14.8 tot +34.6 punten), toe te schrijven aan de afwezigheid van externe judges en de integratie van retrieval en redeneren.

Ablatie-studies en Analyse

Bijdragen van de Fasen:
- SFT zorgt voor de grootste prestatiesprong, waardoor het model van een zero-shot baseline naar bijna state-of-the-art niveaus stijgt, wat de waarde van SPARQL-scaffolded traces bevestigt.
- RL levert complementaire winst, met name op de complexe CWQ dataset, waarbij de nauwkeurigheid verder wordt verbeterd en het beleid wordt verfijnd.
- RL-Only (SOG-R1-ZERO): Het direct toepassen van RL op het basismodel zonder SFT-initialisatie presteert aanzienlijk slechter dan het met SFT geïnitialiseerde model, wat aangeeft dat de cold-start trajecten noodzakelijk zijn voor effectieve RL in dit domein.
Padcompressie: Een unieke bevinding is dat de RL-fase de agent leert om efficiënter te navigeren. SOG-R1 vermindert het gemiddelde aantal Search calls per vraag vergeleken met zijn SFT-initialisatie (bijv. -15% op WebQSP) terwijl de nauwkeurigheid tegelijkertijd toeneemt. Dit staat in contrast met web-search RL-methoden waarbij agents de neiging hebben om meer calls uit te voeren.
Datagrootte: De aanpak is data-efficiënt. De prestaties vlaken vroeg af; slechts enkele duizenden geannoteerde vragen zijn nodig om bijna optimale nauwkeurigheid te bereiken. RL biedt de meest significante uplift wanneer de cold-start datapool klein is.
Algemeenheid van de Backbone: De pipeline wordt succesvol overgedragen naar een andere modelfamilie (Qwen3-4B), waarbij de prestatiehiërarchie behouden blijft (Base < SFT < RL).

Betekenis en Claims

Het artikel claimt dat SOG-R1 er succesvol in is geslaagd de "Search-on-Graph" paradigma te internaliseren in een compact, enkel model. De primaire bijdragen zijn:

Internalisatie: Het transformeert KG-traversatie van een inference-time orchestratie-taak naar een geleerd gedrag binnen de gewichten van een 8B model, waardoor de noodzaak voor hulpmodules of externe judges wordt geëlimineerd.
Gegronde Cold-Start: Door een teacher te scaffolden met gold SPARQL queries en live executie, genereert het trainingsdata die inherent gegrond is in de KG, wat de risico's op hallucinaties van puur generatieve trajecten vermijdt.
Efficiëntie: Het demonstreert dat RL kan leren om antwoorden in minder stappen te bereiken dan de SFT-initialisatie, waarbij geoptimaliseerd wordt voor zowel correctheid als latentie.
State-of-the-Art Efficiëntie: Het bereikt een competitieve of superieure nauwkeurigheid vergeleken met veel grotere frozen modellen en andere post-getrainde systemen tegen een fractie van de inference kosten.

Beperkingen: De auteurs merken op dat de evaluatie beperkt is tot Freebase en uitgaat van de beschikbaarheid van gold topic entities (oracle entity linking) en gold SPARQL queries tijdens de training. De overdraagbaarheid naar grafen zonder dergelijke annotaties (bijv. Wikidata) of het vermogen om entiteits-linking autonoom uit te voeren, is nog niet getest.