💬 NLP

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

Il documento presenta Search-on-Graph-R1, un modello da 8 miliardi di parametri che raggiunge prestazioni allo stato dell'arte nel Knowledge Graph Question Answering interiorizzando la navigazione nei grafi attraverso il fine-tuning supervisionato e l'apprendimento per rinforzo, superando modelli LLM più grandi e all'avanguardia senza richiedere moduli ausiliari o giudici LLM durante l'inferenza.

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

Pubblicato 2026-07-22

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

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

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di cercare di risolvere un mistero enorme e multi-fase, come cercare di capire chi sia il sindaco di una città, ma solo se quella città fa crescere un tipo specifico di albero raro. Per risolverlo, non puoi fare affidamento solo sulla tua memoria; il tuo cervello potrebbe aver dimenticato il nome dell'albero o della città, oppure potrebbe confondere i fatti con quelli di vecchi film. Invece, hai bisogno di una mappa. Nel mondo dell'intelligenza artificiale, questa mappa è chiamata Knowledge Graph (Grafo della Conoscenza). È una gigantesca rete digitale dove ogni fatto è un punto (un'entità) collegato da linee (relazioni). Se vuoi trovare una risposta, devi "saltare" da un punto all'altro, seguendo le linee finché non approdi su quello giusto.

Per molto tempo, i cervelli informatici più intelligenti (chiamati Large Language Models o LLM) sono stati come brillanti detective che avevano letto tutti i libri della biblioteca, ma non sapevano leggere la mappa. Dovevano indovinare la risposta basandosi su ciò che ricordavano, il che portava spesso a errori. Metodi più recenti hanno insegnato a questi modelli a smettere di indovinare e a iniziare a usare uno "strumento di ricerca" per saltare attraverso la mappa, ma i modelli che effettuavano la ricerca erano come robot costosi, super potenti e capaci di fare cose incredibili, che costavano una fortuna e troppo lenti per l'uso nel mondo reale. La grande domanda per gli scienziati è diventata: Possiamo insegnare a un robot più piccolo, economico e veloce a fare questo stesso lavoro investigativo di salto sulla mappa altrettanto bene, senza aver bisogno dell'aiuto del robot costoso?

Questo è esattamente ciò che il documento Search-on-Graph-R1 (SOG-R1) si propone di fare. I ricercatori hanno costruito un sistema di addestramento intelligente per insegnare a un modello di IA compatto, da 8 miliardi di parametri (uno "studente"), come navigare autonomamente in queste mappe della conoscenza. Invece di lasciare semplicemente che lo studente indovini, hanno creato un robot "insegnante" che conosceva già il percorso segreto per la risposta. Ma ecco il trucco: all'insegnante non è stato solo sussurrato la risposta; gli è stata data la planimetria della mappa (una query speciale chiamata SPARQL) ed è stato istruito per percorrere il cammino passo dopo passo usando lo stesso strumento di ricerca che lo studente userebbe. Mentre l'insegnante camminava, registrava ogni mossa, ogni vicolo cieco evitato e ogni fatto trovato dal database in tempo reale.

Lo studente ha poi imparato da questi viaggi registrati in due fasi. Prima, si è esercitato imitando i passi dell'insegnante (Supervised Fine-Tuning), imparando come porre le domande giuste e come leggere la mappa. Secondo, ha giocato a un gioco in cui cercava di trovare risposte da solo, ottenendo punti per essere corretto e punti extra per essere veloce (Reinforcement Learning). Il risultato? Questo piccolo studente da 8 miliardi di parametri è diventato un maestro detective. Su tre grandi campi di prova (WebQSP, CWQ e GrailQA), ha superato ogni singolo sistema a "robot congelato" che i ricercatori hanno confrontato, inclusi quelli alimentati dai modelli più avanzati e costosi disponibili.

Ciò che rende tutto questo ancora più impressionante è che lo studente non è solo diventato più bravo a trovare risposte; è diventato più intelligente nel modo in cui cercava. Mentre il percorso dell'insegnante era perfetto, lo studente ha imparato a prendere scorciatoie. Ha capito come raggiungere le stesse risposte utilizzando meno chiamate di ricerca rispetto a quando stava solo copiando l'insegnante. I ricercatori hanno scoperto che questo metodo funziona anche se si sostituisce lo studente con un tipo diverso di modello, dimostrando che la tecnica di addestramento stessa è la formula segreta. Fondamentalmente, il documento esclude l'idea che il modello debba memorizzare l'intera mappa o fare affidamento su un secondo robot "giudice" per valutare il suo lavoro durante l'addestramento. Invece, il modello ha imparato a fidarsi dello strumento di ricerca in tempo reale e della logica del percorso stesso. Alla fine dell'addestramento, questo piccolo ed efficiente IA poteva navigare in complessi web di conoscenza più velocemente e accuratamente dei suoi molto più grandi e costosi compagni, il tutto senza bisogno di alcun aiuto extra o hardware costoso durante la ricerca effettiva.

Sintesi Tecnica: Search-on-Graph-R1 (SOG-R1)

Definizione del Problema

Il Question Answering su Knowledge Graph (KGQA) richiede di navigare dalle entità tematiche verso le risposte che possono trovarsi a diversi passaggi di relazione di distanza. Sebbene approcci recenti abbiano dimostrato che i modelli linguistici di frontiera (LLM) possono raggiungere un'accuratezza competitiva interagendo con i Knowledge Graph (KG) tramite strumenti di recupero, questi metodi si affidano a costosi modelli di frontiera congelati (es. GPT-4) che sono impraticabili per la produzione a causa di latenza, costi e vincoli di accesso.

I tentativi esistenti di post-addestrare modelli open-source più piccoli per replicare questa capacità affrontano limitazioni significative:

Approcci di Parsing Semantico: Questi addestrano i modelli a emettere una forma logica completa (es. SPARQL) in un unico passaggio. Faticano quando gli elementi dello schema richiesti non sono stati visti durante l'addestramento.
Recupero e Ragionamento Disgiunti: Alcuni metodi (es. EoG) estraggono sottografi statici offline, limitando l'accuratezza alla recall della fase di pre-elaborazione. Altri (es. KG-Hopper) utilizzano la ricerca live ma si affidano a giudici LLM esterni per verificare le tracce di ragionamento, introducendo stocasticità e overhead computazionale.
Fallback Parametrico: Molti sistemi consentono al modello di ricorrere alla memoria parametrica quando il recupero fallisce, il che significa che i fatti citati non sono garantiti esistere nel KG.

La sfida centrale è interiorizzare la navigazione nei KG in un modello compatto (es. 8 miliardi di parametri) che esegua il recupero e il ragionamento live senza moduli ausiliari, giudici esterni o dipendenza dalla memoria parametrica.

Metodologia: SOG-R1

SOG-R1 affronta queste sfide attraverso una pipeline di post-addestramento in due fasi applicata a un modello studente compatto e istruito (Llama-3.1-8B-Instruct). L'approccio fonde recupero e ragionamento in un unico ciclo in cui il modello decide cosa recuperare tramite chiamate di ricerca (Search) live.

1. Generazione di Tracce Cold-Start Scaffolding-ata da SPARQL

Per inizializzare la capacità del modello di navigare nel KG, gli autori generano traiettorie di alta qualità utilizzando una strategia "insegnante":

Configurazione dell'Insegnante: Un LLM insegnante su scala di frontiera (Qwen3-235B) viene fornito con la domanda e la sua query SPARQL d'oro (gold).
Scaffolding: Inveve di chiedere all'insegnante di scoprire il percorso, la query SPARQL d'oro funge da progetto (blueprint). L'insegnante utilizza lo stesso strumento di ricerca live che lo studente userà per attraversare il percorso noto che porta alla risposta.
Grounding (Ancoraggio): Ogni chiamata allo strumento viene eseguita contro un server Freebase live. Ciò assicura che le traiettorie risultanti siano ancorate al KG per costruzione, contenendo chiamate allo strumento valide, osservazioni e la risposta finale.
Filtraggio: Le traiettorie vengono mantenute solo se la risposta finale corrisponde esattamente alla risposta d'oro e tutte le chiamate vengono eseguite senza errori.

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

Il modello studente viene sottoposto a fine-tuning tramite Low-Rank Adaptation (LoRA) sulle traiettorie raccolte dall'insegnante.

I dati di addestramento sono serializzati come conversazioni multi-turno in cui i turni dell'assistente sono chiamate allo strumento di ricerca e i turni intermedi sono le osservazioni restituite.
Il modello impara a produrre chiamate allo strumento e risposte basandosi sul contesto, senza essere addestrato a predire gli output dello strumento stesso.
Questa fase produce SOG-SFT, stabilendo un forte prior di navigazione.

3. Fase 2: Reinforcement Learning (RL)

Il modello SFT viene ulteriormente raffinato utilizzando il Group Relative Policy Optimization (GRPO) con un reward deterministico basato sull'esito.

Funzione di Reward: Il reward è il prodotto di tre fattori:
1. Format Gate ( $g$ ): Assicura che il modello chiami lo strumento almeno una volta e termini correttamente con una stringa "Final answer:".
2. Exact-Match ( $r_{em}$ ): Restituisce 1 se l'insieme della risposta predetta corrisponde alla risposta d'oro, 0 altrimenti.
3. Fattore di Efficienza ( $f$ ): Una penalità moltiplicativa per chiamate allo strumento eccessive (turni), incoraggiando percorsi più brevi tra le traiettorie corrette.
Vincolo Chiave: Il ciclo di reward non contiene un giudice LLM e non ha supervisione del percorso d'oro; si basa esclusivamente sulla correttezza della risposta finale e sull'efficienza del percorso.

Innovazione dello Strumento

Gli autori introducono uno strumento di Recupero dei Vicini a 1-Hop Batching. A differenza degli strumenti precedenti che richiedevano una chiamata per ogni entità, questo strumento accetta una lista di entità in una singola chiamata. Ciò evita che il modello perda entità durante l'espansione di più nodi nello stesso hop, riducendo i costi di inferenza e i tassi di errore.

Risultati Chiave

Il modello è stato valutato su tre benchmark standard basati su Freebase: WebQSP, CWQ e GrailQA.

Performance rispetto ai Modelli di Frontiera Congelati: Il sistema SOG-R1 da 8B supera ogni sistema basato su LLM di frontiera congelato (inclusi i metodi basati su GPT-4 come ToG, PoG e LMP) su tutti e tre i benchmark.
Performance rispetto ai Sistemi Post-Addestrati:
- SOG-R1 raggiunge l'accuratezza più alta su CWQ (88,7%) tra tutti i sistemi confrontati, superando altri modelli post-addestrati come ChatKBQA (86,0%) ed EoG (82,6%).
- Su WebQSP e GrailQA, raggiunge risultati comparabili o leggermente inferiori ai migliori sistemi post-addestrati (EoG), ma con il distintivo vantaggio di eseguire il recupero live invece di ragionare su un sottografo estratto staticamente.
- Rispetto a KG-Hopper: Contro il sistema concorrente più simile (KG-Hopper, anch'esso Llama-3.1-8B), SOG-R1 mostra guadagni significativi (+14,8 a +34,6 punti), attribuiti all'assenza di giudici esterni e all'integrazione di recupero e ragionamento.

Studi di Ablazione e Analisi

Contributi delle Fasi:
- SFT fornisce il salto di prestazione più grande, portando il modello da un baseline zero-shot a livelli vicini allo stato dell'arte, confermando il valore delle tracce scaffoldate da SPARQL.
- RL fornisce guadagni complementari, particolarmente sul complesso dataset CWQ, migliorando ulteriormente l'accuratezza e raffinando la policy.
- RL-Only (SOG-R1-ZERO): Applicare l'RL direttamente al modello base senza l'inizializzazione SFT produce risultati significativamente peggiori rispetto al modello inizializzato con SFT, indicando che le tracce di cold-start sono necessarie per un RL efficace in questo dominio.
Compressione del Percorso: Un risultato unico è che la fase di RL insegna all'agente a navigare in modo più efficiente. SOG-R1 riduce il numero medio di chiamate di ricerca per domanda rispetto alla sua inizializzazione SFT (es. -15% su WebQSP) aumentando contemporaneamente l'accuratezza. Questo contrasta con i metodi di RL per la ricerca sul web dove gli agenti tendono a emettere più chiamate.
Scala dei Dati: L'approccio è efficiente nei dati. Le prestazioni raggiungono un plateau precocemente; sono necessari solo pochi migliaia di quesiti annotati per raggiungere l'accuratezza quasi ottimale. L'RL fornisce il sollevamento più significativo quando il pool di dati di cold-start è piccolo.
Generalità del Backbone: La pipeline si trasferisce con successo a una diversa famiglia di modelli (Qwen3-4B), mantenendo la gerarchia delle prestazioni (Base < SFT < RL).

Significato e Rivendicazioni

Il paper afferma che SOG-R1 riesce a interiorizzare con successo il paradigma "Search-on-Graph" in un modello compatto. I suoi principali contributi sono:

Interiorizzazione: Trasforma la navigazione nei KG da un compito di orchestrazione al tempo di inferenza a un comportamento appreso all'interno dei pesi di un modello da 8B, eliminando la necessità di moduli ausiliari o giudici esterni.
Cold-Start Ancorato: Scaffolding di un insegnante con query SPARQL d'oro ed esecuzione live, genera dati di addestramento che sono intrinsecamente ancorati al KG, evitando i rischi di allucinazione delle tracce puramente generative.
Efficienza: Dimostra che l'RL può imparare a raggiungere le risposte in meno passaggi rispetto all'inizializzazione SFT, ottimizzando sia la correttezza che la latenza.
Efficienza State-of-the-Art: Raggiunge un'accuratezza competitiva o superiore rispetto a modelli molto più grandi e altri sistemi post-addestrati a una frazione del costo di inferenza.

Limitazioni: Gli autori notano che la valutazione è limitata a Freebase e assume la disponibilità di entità tematiche d'oro (oracle entity linking) e query SPARQL d'oro durante l'addestramento. La trasferibilità a grafi senza tali annotazioni (es. Wikidata) o la capacità di eseguire l'entity linking autonomamente rimane non testata.