Technische Samenvatting: Search-on-Graph (SoG)

Probleemstelling

Large Language Models (LLMs) die worden versterkt met Knowledge Graphs (KGs) bieden een veelbelovende weg voor kennisintensieve redenering. Echter, bestaande methoden voor het selecteren van redeneerpaden binnen KGs kampen met een kritieke beperking: het selectieproces is vaak losgekoppeld van de redeneervereisten. Huidige benaderingen vertrouwen typisch op afzonderlijke modules of onafhankelijke criteria (zoals semantische gelijkenis met de oorspronkelijke vraag) om relaties te filteren of te selecteren. Deze ontkoppeling leidt tot twee primaire faalmodi:

1. Semantische Drift: De exploratie wijkt af van de logische keten die nodig is om de vraag te beantwoorden, omdat de selectie gebaseerd is op oppervlakkige gelijkenis in plaats van de redeneergeschiedenis.
2. Voortijdige Pruning: Logisch correcte maar lexicaal minder gelijke relaties worden vroegtijdig geëlimineerd, waardoor het redeneerproces mislukt.

Bovendien maken veel bestaande agentische methoden gebruik van complexe architecturen met meerdere componenten (afzonderlijke planning-, retrieval- en redeneermodules) of onderhouden ze parallelle exploratiepaden via beam search, wat een aanzienlijke overhead aan geheugen en computationele complexiteit introduceert zonder de validiteit van de redenering te garanderen.

Methodologie: Search-on-Graph (SoG)

De auteurs stellen Search-on-Graph (SoG) voor, een framework dat padselectie en redenering verenigt binnen één enkele LLM. SoG werkt volgens een observe-think-navigate paradigma, waarbij de LLM iteratief door de KG navigeert door weloverwogen beslissingen te nemen op basis van de volledige redeneergeschiedenis en de huidige lokale graafstructuur.

Kerncomponenten

1. Iteratieve 1-Hop Search:
   SoG maakt gebruik van een enkele, zorgvuldig ontworpen Search-functie als de enige interface van de LLM voor KG-exploratie. Deze functie haalt 1-hop buren op van een gegeven entiteit in een opgegeven richting (uitgaand of inkomend).

   • Input: Entiteit-ID, richting en optionele eigenschappen voor filtering.
   • Output: Een efficiënte markdown-tabel met property-ID's, labels, waarde-ID's en waarde-labels.

2. Omgaan met High-Degree Nodes:
   Om de uitdaging van entiteiten met duizenden verbindingen (bijv. landen, beroemdheden) aan te pakken, gebruikt SoG een tweestaps filteringmechanisme:

   • Property Discovery: Als een node meer dan $k$ buren heeft (standaard $k=50$) en er geen specifieke eigenschappen worden opgevraagd, geeft het systeem alleen de unieke property-typen terug in plaats van alle instanties.
   • Targeted Retrieval: De LLM analyseert de beschikbare eigenschappen en doet een tweede, gerichte Search-aanroep met specifieke eigenschappen om alleen de relevante buren op te halen.
   • Truncatie: Als de resultaten nog steeds de drempelwaarde $p$ overschrijden (standaard $p=1000$), wordt de lijst afgekort om binnen de contextlimieten te passen.

3. Context-bewuste Navigatie:
   In tegen tegenstelling tot beam search-methoden die meerdere parallelle paden onderhouden, stuurt SoG de LLM aan om bij elke stap één enkele relatie te selecteren op basis van de volledige redeneergeschiedenis. De LLM observeert de buren van de huidige entiteit, redeneert over welke weg de beantwoording bevordert (bijv. "Ik ben bij Zundert, kwam van Van Gogh, heb het land nodig, dus ik zoek naar 'Bevat door'") en navigeert dienovereenkomstig. Dit zorgt voor logische coherentie zonder de ruisaccumulatie van parallelle exploratie.

4. Prompting Strategie:
   Het systeem gebruikt een system prompt die de rol van de agent definieert en een reeks few-shot exemplaren (doorgaans 5) die drie fasen demonstreren: initiële exploratie, iteratieve traversatie en antwoordextractie. De LLM bepaalt autonoom wanneer er voldoende informatie is verzameld om te stoppen met tool-calls en een definitief antwoord te geven.

Belangrijkste Bijdragen

1. Een Verenigd Framework: SoG stelt een eenvoudig maar effectief KGQA-framework voor waarbij een enkele LLM de iteratieve KG-traversatie aanstuurt, waardoor de noodzaak voor afzonderlijke planning- of retrievalmodules vervalt.
2. Context-bewuste Navigatie: De methode voert navigatie uit op basis van de volledige redeneergeschiedenis, waardoor semantische drift wordt vermeden die gebruikelijk is bij contextvrije pruning-methoden zoals Think-on-Graph (ToG).
3. Schema-agnostisch: De benadering generaliseert over verschillende KG-schema's (Freebase en Wikidata) zonder modificatie of taakspecifieke fine-tuning.
4. Efficiëntie: Door per hop één enkele relatie te selecteren in plaats van parallelle paden te onderhouden, vermindert SoG het aantal LLM-aanroepen en output-tokens aanzienlijk in vergelijking met beam search baselines.

Experimentele Resultaten

De auteurs hebben SoG geëvalueerd op zes KGQA-benchmarks verspreid over Freebase (SimpleQA, WebQSP, CWQ, GrailQA) en Wikidata (QALD-9, QALD-10).

• Prestaties: SoG behaalde state-of-the-art (SOTA) resultaten op vijf van de zes datasets zonder enige taakspecifieke fine-tuning.
  • Op Wikidata-benchmarks toonde het substantiële verbeteringen van meer dan 11,3% vergeleken met voorheen beste methoden.
  • Op Freebase-datasets presteerde het beter dan eerdere systemen, en bleef op CWQ slechts 0,1% achter bij Generate-on-Graph.
• Backbone Robuustheid: Het framework is compatibel met diverse LLM-backbones. Het behaalde SOTA-prestaties met GPT-4o en toonde ook sterke resultaten met open-source modellen (Qwen3-serie). Opmerkelijk genoeg presteerde zelfs het compacte Qwen3-4B model beter dan voorheen gebruikte methoden op Wikidata-benchmarks, wat de effectiviteit van de methode over verschillende modelgroottes bewijst.
• Efficiëntie: Vergeleken met de Think-on-Graph baseline verminderde SoG het aantal LLM-aanroepen met ten minste 46,4% en de output-tokens met 69,9%, hoewel het meer input-tokens vereist om de volledige redeneercontext te behouden.
• Ablatie Studies:
  • Few-Shot Learning: De prestaties verbeterden drastisch met slechts één navigatie-exemplaar en bereikten een plateau bij 3-5 shots.
  • Model Type: "Thinking" (redeneer-geoptimaliseerde) modellen presteerden consistent beter dan standaard instructie-getunede modellen, vooral bij multi-hop taken.
  • Output Formaat: Het voorgestelde "Markdown + Property Filter" formaat bereikte de beste balans tussen nauwkeurigheid en token-efficiëntie.

Betekenis en Claims

Het artikel beweert dat Search-on-Graph een nieuw paradigma valideert waarbij LLM-gestuurde navigatie een superieure benadering is voor kennisgraaf-redenering vergeleken met methoden die vertrouwen op afzonderlijke selectiemodules of voorafgaande planning.

De auteurs argumenteren dat de aanname dat een enkele LLM beter in staat is om relevante relaties bij elke stap te selecteren — op basis van werkelijke redeneervereisten en volledige context — waar is. Deze benadering vereenvoudigt de architectuur, vermindert de computationele overhead en generaliseert effectief over verschillende KG-schema's en modelgroottes. De resultaten suggereren dat architecturale eenvoud, gecombineerd met zorgvuldig contextbeheer, de overhand kan hebben op meer complexe, multi-component systemen.