💬 NLP

Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling

Il paper propone Explore-on-Graph (EoG), un nuovo framework che utilizza l'apprendimento per rinforzo con segnali di ricompensa basati sui percorsi per incentivare i Large Language Models a esplorare autonomamente e diversificare il ragionamento su Knowledge Graphs, ottenendo prestazioni state-of-the-art su cinque dataset di benchmark.

Autori originali: Shiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao, Shuai Chen, Tianyi Zhang, Shijie Zhang, Wei Qiang Zhang, Yongfeng Huang, Haixin Duan, Yunqi Zhang

Pubblicato 2026-02-26

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Shiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao, Shuai Chen, Tianyi Zhang, Shijie Zhang, Wei Qiang Zhang, Yongfeng Huang, Haixin Duan, Yunqi Zhang

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 che un Grande Modello Linguistico (LLM) sia come un turista molto colto ma un po' distratto che viaggia in un enorme labirinto chiamato Grafo della Conoscenza (Knowledge Graph). Questo labirinto è pieno di strade (relazioni) che collegano città (entità) e punti di riferimento.

Il problema? Quando il turista deve rispondere a una domanda complessa (es. "Quale paese con codice ISO 736 importa dal Giappone?"), tende a:

Allucinare: Inventarsi strade che non esistono.
Fare sempre la stessa strada: Se ha imparato che "Google -> Carol -> Londra" è una strada comune, ripeterà sempre quella, anche se la risposta giusta è nascosta in un vicolo cieco o in un percorso insolito come "Google -> Subsidiario -> Youtube -> Alice -> Londra".

I metodi precedenti erano come guide turistiche rigide: dicevano al turista "Segui solo queste 10 regole" o "Copia esattamente quello che ha fatto il turista di ieri". Il risultato? Funzionavano bene solo per le strade che conoscevano già, ma fallivano miseramente quando si trovavano di fronte a un nuovo tipo di labirinto.

La Soluzione: "Explore-on-Graph" (EoG)

Gli autori propongono un nuovo approccio: invece di dare al turista una mappa rigida, gli insegnano a esplorare autonomamente e a imparare dai propri errori, proprio come un bambino che impara a camminare.

Ecco come funziona, diviso in due fasi magiche:

Fase 1: L'Apprendistato (SFT - Supervised Fine-Tuning)

Prima di lasciarlo libero, diamo al turista un corso intensivo.

Cosa succede: Gli mostriamo migliaia di esempi di come si risolvono questi enigmi, passo dopo passo, con un ragionamento logico e strutturato.
L'analogia: È come se il turista leggesse un manuale di sopravvivenza e facesse un tirocinio con un esperto. Impara a non inventare strade e a usare la logica.
Il limite: Anche dopo questo corso, il turista tende a essere "pigrone": usa solo le strade che ha visto nel manuale. Se incontra un percorso nuovo, si blocca.

Fase 2: L'Esplorazione con Ricompense (Reinforcement Learning - RL)

Qui avviene la magia. Lasciamo il turista libero di vagare nel labirinto, ma introduciamo un sistema di premi intelligenti.

La Ricompagna Finale (Outcome Reward):
- Se il turista trova la risposta giusta alla fine del percorso, riceve una medaglia d'oro.
- Problema: Potrebbe trovare la medaglia facendo un giro lunghissimo e inutile, o indovinando a caso.
La Ricompensa del Percorso (Path-Refined Reward) - L'innovazione chiave!
- Qui sta il genio del paper. Non premiamo solo dove arriva il turista, ma come ci arriva.
- Se il turista segue un sentiero che ha senso logico (anche se non l'aveva mai visto prima), riceve un premio extra.
- L'analogia: Immagina di avere un GPS che non ti dice solo "Hai arrivato!", ma ti dice: "Bravo! Hai preso quella strada sterrata che sembrava sbagliata, ma in realtà era l'unica che portava alla soluzione!".
- Questo incoraggia il modello a osare. Invece di seguire solo le strade battute (i dati di addestramento), inizia a esplorare i "vicoli ciechi" che si rivelano essere scorciatoie geniali per domande mai viste prima.

Perché è così speciale?

Immagina di dover risolvere un puzzle.

I metodi vecchi ti dicono: "Metti i pezzi rossi qui e quelli blu lì". Se il puzzle ha un pezzo verde, non sai cosa fare.
EoG ti dice: "Ecco come si assemblano i pezzi. Ora prova a mescolarli tu stesso. Se trovi un modo nuovo per far combaciare i pezzi, ti do un punto bonus!".

Grazie a questo sistema, il modello impara a:

Non allucinare: Perché ogni passo deve essere giustificato dal grafo.
Generalizzare: Riesce a rispondere a domande su argomenti o strutture che non ha mai visto durante l'addestramento (Out-of-Distribution), perché ha imparato a esplorare e non solo a memorizzare.

I Risultati

Nel paper, gli autori hanno messo alla prova questo "turista esploratore" su 5 gare di logica molto difficili. Il risultato?

Ha battuto i migliori modelli "aperti" (quelli gratuiti e modificabili).
Ha battuto persino i modelli "chiusi" e super potenti (come GPT-5 o Gemini Pro), che sono come turisti con una memoria fotografica perfetta ma senza la capacità di adattarsi a nuovi percorsi.

In sintesi: EoG non insegna al modello cosa pensare, ma gli insegna come esplorare la conoscenza in modo sicuro e creativo, trasformandolo da un semplice ripetitore di nozioni in un vero investigatore autonomo.

1. Il Problema

I Large Language Models (LLM) eccellono in molte attività di elaborazione del linguaggio naturale, ma soffrono di allucinazioni e lacune conoscitive nelle attività di Question Answering (QA). Per mitigare ciò, è comune ancorare le risposte a fonti di conoscenza verificabili come i Knowledge Graph (KG).

Tuttavia, i metodi attuali per potenziare i KG con LLM presentano due limiti principali:

Metodi basati su regole: Impongono vincoli rigidi durante la generazione, limitando la flessibilità.
Metodi basati sull'imitazione: Addestrano i modelli a imitare percorsi di ragionamento derivati da un set fisso di dimostrazioni (fine-tuning supervisionato).

Il problema centrale è che questi approcci confinanano il ragionamento dell'LLM entro i limiti dei dati di addestramento o delle regole predefinite. Di conseguenza, i modelli faticano a generalizzare su problemi di ragionamento su grafi che sono Out-Of-Distribution (O.O.D.), ovvero che richiedono percorsi logici non visti durante l'addestramento o che deviano dai pattern più comuni.

2. Metodologia: Explore-on-Graph (EoG)

Gli autori propongono EoG, un nuovo framework che incentiva l'esplorazione autonoma degli LLM sullo spazio dei percorsi di ragionamento nei KG. Il framework si articola in due fasi distinte:

Fase 1: Supervised Fine-Tuning (SFT) con Long Chain-of-Thought (CoT)

Per fornire una base solida, il modello viene prima addestrato tramite SFT su un dataset di ragionamento strutturato a "lunga catena" (Long CoT).

Obiettivo: Insegnare al modello la logica multi-step necessaria per navigare nei grafi, utilizzando dimostrazioni generate tramite distillazione della conoscenza (usando modelli avanzati come Gemini 2.5 Flash).
Risultato: Il modello acquisisce la capacità di generare percorsi di ragionamento strutturati e logici, evitando l'esplorazione casuale iniziale.

Fase 2: Reinforcement Learning (RL) con Reward Modeling Raffinato

Questa è la fase innovativa per incentivare l'esplorazione autonoma e la scoperta di nuovi percorsi. L'addestramento RL è diviso in due sottostadi:

Reward basato sull'Esito (Outcome Reward):
- Utilizza l'algoritmo GRPO (Group Relative Policy Optimization).
- Il segnale di ricompensa è basato sulla correttezza della risposta finale (calcolata tramite F1-score a livello di entità).
- Questo spinge il modello a trovare percorsi che portano alla risposta corretta, ma non garantisce l'efficienza o la semantica del percorso stesso.
Reward Raffinato dal Percorso (Path-Refined Reward):
- Per migliorare l'efficienza e la significatività semantica dell'esplorazione, viene introdotto un segnale di ricompensa aggiuntivo.
- Meccanismo: Viene calcolato quanto il percorso di ragionamento generato dal modello si sovrappone ai tripletti (soggetto, relazione, oggetto) del percorso di verità (ground-truth).
- Pipeline "Search-and-Verify": Per dataset privi di percorsi espliciti, viene utilizzato un BFS (Breadth-First Search) per trovare percorsi topologici, filtrati poi semanticamente da un LLM per confermare la loro pertinenza logica rispetto alla domanda.
- Ricompensa Combinata: La ricompensa totale è una combinazione lineare: $R_{joint} = R_{outcome} + \alpha \cdot R_{path}$ . Questo incentiva il modello a non solo trovare la risposta giusta, ma a farlo attraverso percorsi logicamente validi ed efficienti, riducendo le esplorazioni inutili.

3. Contributi Chiave

Esplorazione Autonoma: Spostamento dal paradigma di "imitazione" a quello di "esplorazione", permettendo agli LLM di scoprire pattern di ragionamento O.O.D. non presenti nei dati di addestramento.
Reward Modeling Ibrido: Introduzione di un meccanismo di ricompensa che combina la correttezza del risultato finale con la fedeltà semantica del percorso di ragionamento, risolvendo il problema della ricompensa sparsa e dell'esplorazione inefficiente.
Framework EoG: Un approccio completo che integra SFT per la struttura e RL per la diversificazione e l'ottimizzazione della politica di esplorazione.

4. Risultati Sperimentali

Il metodo è stato valutato su 5 dataset benchmark per KGQA (WebQSP, CWQ, GrailQA, QALD10-en, 2WikiMultihop).

Prestazioni SOTA: EoG ha raggiunto le prestazioni più avanzate (State-of-the-Art) su tutti i dataset, superando sia modelli open-source che modelli proprietari chiusi (come GPT-5 e la serie Gemini 2.5 Pro/Flash).
Generalizzazione O.O.D.: Il modello dimostra una robustezza superiore nei casi di ragionamento complesso (es. pattern superlativi, percorsi con 3+ hop) e su dati fuori distribuzione, dove i metodi basati su regole o imitazione falliscono.
Analisi di Ablazione:
- La rimozione della fase RL causa un crollo delle prestazioni, confermando che l'esplorazione autonoma è guidata dal RL e non solo dal SFT.
- La rimozione del Path-Refined Reward riduce l'efficienza e la copertura dello spazio di ragionamento, dimostrando che il segnale di ricompensa sul percorso è cruciale per evitare esplorazioni "rumorose".
Efficienza: Nonostante l'uso di RL, il framework è computazionalmente efficiente, richiedendo un numero limitato di step di addestramento e ore GPU rispetto ad approcci RL tradizionali su larga scala.

5. Significato e Impatto

Il lavoro di EoG rappresenta un passo significativo verso l'affidabilità dei LLM in scenari reali basati su conoscenza.

Superamento dei Limiti di Addestramento: Dimostra che è possibile addestrare modelli a "pensare fuori dagli schemi" (O.O.D.) senza dipendere esclusivamente da dati di dimostrazione preesistenti.
Riduzione delle Allucinazioni: Ancorando il ragionamento a percorsi verificabili nel grafo e premiando la fedeltà semantica, si riduce drasticamente il rischio di allucinazioni.
Scalabilità: L'approccio è applicabile a diverse architetture di LLM (testato su Qwen2.5 e Llama-3.1) e si rivela competitivo anche contro modelli chiusi molto più grandi, offrendo una soluzione praticabile ed economica per il ragionamento su Knowledge Graph.

In sintesi, Explore-on-Graph trasforma l'LLM da un semplice imitatore di pattern noti a un esploratore attivo e autonomo della conoscenza, guidato da segnali di ricompensa intelligenti che bilanciano accuratezza e logica.