💬 NLP

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

O artigo apresenta o Search-on-Graph-R1, um modelo de 8 bilhões de parâmetros que alcança o estado da arte em Resposta a Perguntas sobre Grafos de Conhecimento ao internalizar a navegação em grafos por meio de ajuste fino supervisionado e aprendizado por reforço, superando modelos de linguagem de grande escala (LLMs) de fronteira mais robustos sem exigir módulos auxiliares ou juízes de LLM durante a inferência.

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

Publicado 2026-07-22

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

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

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando resolver um mistério massivo e de múltiplas etapas, como descobrir quem é o prefeito de uma cidade, mas apenas se essa cidade cultivar um tipo específico de árvore rara. Para resolver isso, você não pode confiar apenas na sua própria memória; seu cérebro pode ter esquecido o nome da árvore ou da cidade, ou pode estar confundindo fatos de filmes antigos. Em vez disso, você precisa de um mapa. No mundo da inteligência artificial, esse mapa é chamado de Grafo de Conhecimento (Knowledge Graph). É uma teia digital gigante onde cada fato é um ponto (uma entidade) conectado por linhas (relacionamentos). Se você quiser encontrar uma resposta, terá que "pular" de ponto em ponto, seguindo as linhas até chegar ao ponto correto.

Por muito tempo, os cérebros de computador mais inteligentes (chamados de Modelos de Linguagem de Grande Escala ou LLMs) eram como detetives brilhantes que leram todos os livros da biblioteca, mas não conseguiam ler o mapa. Eles tinham que adivinhar a resposta com base no que lembravam, o que frequentemente levava a erros. Métodos mais novos ensinaram esses modelos a parar de adivinhar e começar a usar uma "ferramenta de busca" para saltar pelo mapa, mas os modelos que faziam a busca eram como robôs caríssimos e superpotentes que custavam uma fortuna para operar e eram lentos demais para o uso no mundo real. A grande questão para os cientistas tornou-se: Podemos ensinar um robô menor, mais barato e rápido a fazer esse mesmo trabalho de detetive de saltar pelo mapa tão bem quanto, sem precisar da ajuda do robô caro?

Isso é exatamente o que o artigo Search-on-Graph-R1 (SOG-R1) se propõe a fazer. Os pesquisadores construíram um sistema de treinamento inteligente para ensinar um modelo de IA compacto, de 8 bilhões de parâmetros (um "estudante"), a navegar nesses mapas de conhecimento por conta própria. Em vez de apenas deixar o estudante adivinhar, eles criaram um robô "professor" que já conhecia o caminho secreto para a resposta. Mas aqui está o truque: o professor não apenas sussurrou a resposta; ele recebeu o projeto do mapa (uma consulta especial chamada SPARQL) e foi instruído a percorrer o caminho passo a passo usando a mesma ferramenta de busca que o estudante usaria. Enquanto o professor caminhava, ele registrava cada movimento, cada beco sem saída que evitava e cada fato que encontrava no banco de dados ao vivo.

O estudante então aprendeu com essas jornadas registradas em duas etapas. Primeiro, ele praticou imitando os passos do professor (Ajuste Fino Supervisionado ou Supervised Fine-Tuning), aprendendo como fazer as perguntas certas e ler o mapa. Segundo, ele jogou um jogo onde tentava encontrar respostas por conta própria, ganhando pontos por estar correto e pontos extras por ser rápido (Aprendizado por Reforço ou Reinforcement Learning). O resultado? Esse pequeno estudante de 8 bilhões de parâmetros tornou-se um mestre detetive. Em três grandes campos de teste (WebQSP, CWQ e GrailQA), ele superou todos os sistemas de "super-robôs congelados" que os pesquisadores compararam, incluindo aqueles alimentados pelos modelos mais avançados e caros disponíveis.

O que torna isso ainda mais impressionante é que o estudante não apenas melhorou na busca de respostas; ele ficou mais esperto sobre como pesquisar. Embora o caminho do professor fosse perfeito, o estudante aprendeu a pegar atalhos. Ele descobriu como alcançar as mesmas respostas usando menos chamadas de busca do que quando estava apenas copiando o professor. Os pesquisadores descobriram que este método funciona mesmo se você substituir o estudante por um tipo diferente de modelo, provando que a técnica de treinamento em si é o ingrediente secreto. Crucialmente, o artigo descarta a ideia de que o modelo precisa memorizar todo o mapa ou depender de um segundo robô "juiz" para avaliar seu trabalho durante o treinamento. Em vez disso, o modelo aprendeu a confiar na ferramenta de busca ao vivo e na lógica do próprio caminho. Ao final do treinamento, este pequeno e eficiente IA podia navegar em teias de conhecimento complexas de forma mais rápida e precisa do que seus equivalentes muito maiores e mais caros, tudo isso sem precisar de nenhum ajudante extra ou hardware caro durante a busca real.

Resumo Técnico: Search-on-Graph-R1 (SOG-R1)

Declaração do Problema

O Questionamento de Grafos de Conhecimento (KGQA) requer a navegação de entidades de tópicos até as respostas, que podem estar a várias relações de distância. Embora abordagens recentes tenham demonstrado que modelos de linguagem de fronteira (LLMs) podem alcançar uma acurácia competitiva ao interagir com Grafos de Conhecimento (KGs) via ferramentas de recuperação, esses métodos dependem de modelos de fronteira caros e congelados (ex: GPT-4), que são impraticáveis para produção devido à latência, custo e restrições de acesso.

Tentativas existentes de pós-treinar modelos menores e de código aberto para replicar essa capacidade enfrentam limitações significativas:

Abordagens de Parsing Semântico: Treinam modelos para emitir uma forma lógica completa (ex: SPARQL) em uma única passagem. Eles têm dificuldade quando os elementos de esquema necessários não foram vistos durante o treinamento.
Recuperação e Raciocínio Disjuntos: Alguns métodos (ex: EoG) extraem subgrafos estáticos offline, limitando a acurácia pela recall da etapa de pré-processamento. Outros (ex: KG-Hopper) usam busca ao vivo, mas dependem de juízes LLM externos para verificar os rastros de raciocínio, introduzindo estocasticidade e sobrecarga computacional.
Fallback Paramétrico: Muitos sistemas permitem que os modelos recorram à memória paramétrica quando a recuperação falha, o que significa que os fatos citados não têm garantia de existirem no KG.

O desafio central é internalizar a navegação em KG em um modelo compacto (ex: 8B de parâmetros) que realize recuperação e raciocínio ao vivo sem módulos auxiliares, juízes externos ou dependência de memória paramétrica.

Metodologia: SOG-R1

O SOG-R1 aborda esses desafios através de um pipeline de pós-treinamento de dois estágios aplicado a um modelo estudante instruído compactamente (Llama-3.1-8B-Instruct). A abordagem funde recuperação e raciocínio em um único loop onde o modelo decide o que buscar via chamadas de Busca (Search) ao vivo.

1. Geração de Trajetória de Cold-Start Escafolada por SPARQL

Para inicializar a habilidade do modelo de navegar no KG, os autores geram trajetórias de treinamento de alta qualidade usando uma estratégia de "professor":

Configuração do Professor: Um LLM de escala de fronteira (Qwen3-235B) é provido com a pergunta e sua query SPARQL ouro.
Escafolamento (Scaffolding): Em vez de pedir ao professor para descobrir o caminho, a query SPARQL ouro atua como um blueprint. O professor usa a mesma ferramenta de Busca ao vivo que o estudante usará para percorrer o caminho conhecido que leva à resposta.
Aterramento (Grounding): Cada chamada de ferramenta é executada contra um servidor Freebase ao vivo. Isso garante que as trajetórias resultantes sejam fundamentadas no KG por construção, contendo chamadas de ferramentas válidas, observações e a resposta final.
Filtragem: As trajetórias são retidas apenas se a resposta final corresponder exatamente à resposta ouro e todas as chamadas forem executadas sem erro.

2. Estágio 1: Ajuste Fino Supervisionado (SFT)

O modelo estudante é ajustado finamente usando Low-Rank Adaptation (LoRA) nas trajetórias coletadas do professor.

Os dados de treinamento são serializados como conversas de múltiplos turnos onde os turnos do assistente são chamadas de ferramenta de Busca e os turnos intermediários são as observações retornadas.
O modelo aprende a produzir chamadas de ferramenta e respostas baseadas no contexto, sem ser treinado para prever as saídas da ferramenta em si.
Este estágio produz o SOG-SFT, estabelecendo um prior de navegação forte.

3. Estágio 2: Aprendizado por Reforço (RL)

O modelo SFT é refinado adicionalmente usando Group Relative Policy Optimization (GRPO) com uma recompensa de resultado determinística.

Função de Recompensa: A recompensa é o produto de três fatores:
1. Portão de Formato (Format Gate - $g$ ): Garante que o modelo chame a ferramenta pelo menos uma vez e termine limpamente com uma string "Final answer:".
2. Correspondência Exata (Exact-Match - $r_{em}$ ): Retorna 1 se o conjunto de respostas previsto coincidir com a resposta ouro, 0 caso contrário.
3. Fator de Eficiência ( $f$ ): Uma penalidade multiplicativa para chamadas de ferramenta excessivas (turnos), incentivando caminhos mais curtos entre trajetórias corretas.
Restrição Chave: O loop de recompensa não contém um juiz LLM e não possui supervisão de caminho ouro; ele depende exclusivamente da correção da resposta final e da eficiência do caminho.

Inovação de Ferramenta

Os autores introduzem uma ferramenta de Recuperação de Vizinho de 1-Salto em Lote (Batched 1-Hop Neighbour Retrieval). Diferente de ferramentas anteriores que exigiam uma chamada por entidade, esta ferramenta aceita uma lista de entidades em uma única chamada. Isso evita que o modelo descarte entidades ao expandir múltiplos nós no mesmo salto, reduzindo o custo de inferência e as taxas de falha.

Resultados Principais

O modelo foi avaliado em três benchmarks padrão baseados em Freebase: WebQSP, CWQ e GrailQA.

Performance vs. Modelos de Fronteira Congelados: O SOG-R1 de 8B supera todos os sistemas de LLM de fronteira congelados (incluindo métodos baseados em GPT-4 como ToG, PoG e LMP) nos três benchmarks.
Performance vs. Sistemas Pós-Treinados:
- O SOG-R1 alcança a maior acurácia no CWQ (88.7%) de qualquer sistema comparado, superando outros modelos pós-treinados como ChatKBQA (86.0%) e EoG (82.6%).
- No WebQSP e GrailQA, alcança resultados comparáveis ou ligeiramente abaixo dos melhores sistemas pós-treinados (EoG), mas com a vantagem distinta de realizar recuperação ao vivo em vez de raciocinar sobre um subgrafo extraído estaticamente.
Comparação com KG-Hopper: Contra o sistema concorrente mais similar (KG-Hopper, também Llama-3.1-8B), o SOG-R1 mostra ganhos significativos (+14.8 a +34.6 pontos), atribuídos à ausência de juízes externos e à integração de recuperação e raciocínio.

Estudos de Ablação e Análise

Contribuições dos Estágios:
- SFT fornece o maior salto de performance, elevando o modelo de um baseline zero-shot para níveis próximos ao estado da arte, confirmando o valor das trajetórias escafoladas por SPARQL.
- RL fornece ganhos complementares, particularmente no dataset complexo CWQ, melhorando a acurácia adicionalmente e refinando a política.
- RL-Only (SOG-R1-ZERO): Aplicar RL diretamente ao modelo base sem inicialização SFT performa significativamente pior do que o modelo inicializado com SFT, indicando que as trajetórias de cold-start são necessárias para um RL eficaz neste domínio.
Compressão de Caminho: Um achado único é que o estágio de RL ensina o agente a navegar de forma mais eficiente. O SOG-R1 reduz o número médio de chamadas de Busca por pergunta comparado à sua inicialização SFT (ex: -15% no WebQSP) enquanto simultaneamente aumenta a acurácia. Isso contrasta com métodos de RL de busca na web, onde os agentes tendem a emitir mais chamadas.
Escala de Dados: A abordagem é eficiente em termos de dados. A performance estabiliza cedo; apenas alguns milhares de perguntas anotadas são necessários para atingir uma acurácia próxima da ótima. O RL fornece o aumento mais significativo quando o pool de dados de cold-start é pequeno.
Generalidade do Backbone: O pipeline transfere-se com sucesso para uma família de modelos diferente (Qwen3-4B), mantendo a hierarquia de performance (Base < SFT < RL).

Significância e Alegações

O artigo afirma que o SOG-R1 consegue internalizar com sucesso o paradigma "Search-on-Graph" em um modelo compacto e único. Suas principais contribuições são:

Internalização: Transforma a travessia de KG de uma tarefa de orquestração em tempo de inferência em um comportamento aprendido dentro dos pesos de um modelo de 8B, eliminando a necessidade de módulos auxiliares ou juízes externos.
Cold-Start Aterrado: Ao escafolar um professor com queries SPARQL ouro e execução ao vivo, gera dados de treinamento que são inerentemente fundamentados no KG, evitando os riscos de alucinação de trajetórias puramente generativas.
Eficiência: Demonstra que o RL pode aprender a alcançar respostas em menos passos do que a inicialização SFT, otimizando tanto a correção quanto a latência.
Eficiência de Estado da Arte: Alcança acurácia competitiva ou superior a modelos muito maiores congelados e outros sistemas pós-treinados por uma fração do custo de inferência.

Limitações: Os autores observam que a avaliação é restrita ao Freebase e assume a disponibilidade de entidades de tópico ouro (entity linking de oráculo) e queries SPARQL ouro durante o treinamento. A transferibilidade para grafos sem tais anotações (ex: Wikidata) ou a capacidade de realizar entity linking autonomamente permanece não testada.