Resumo Técnico: Search-on-Graph (SoG)

Declaração do Problema

Modelos de Linguagem de Grande Escala (LLMs) aumentados com Grafos de Conhecimento (KGs) oferecem uma via promissora para o raciocínio intensivo em conhecimento. No entanto, os métodos existentes para selecionar caminhos de raciocínio dentro de KGs enfrentam uma limitação crítica: o processo de seleção é frequentemente desacoplado dos requisitos de raciocínio. As abordagens atuais dependem de módulos separados ou critérios independentes (como similaridade semântica com a pergunta original) para podar ou selecionar relações. Esse desconexão leva a dois modos principais de falha:

1. Deriva Semântica (Semantic Drift): A exploração diverge da cadeia lógica necessária para responder à pergunta porque a seleção é baseada em similaridade superficial em vez do histórico de raciocínio.
2. Poda Prematura (Premature Pruning): Relações logicamente corretas, mas lexicalmente dissimilar, são eliminadas precocemente, causando a falha no processo de raciocínio.

Além disso, muitos métodos agênticos existentes empregam arquiteturas de múltiplos componentes complexos (módulos separados de planejamento, recuperação e raciocínio) ou mantêm caminhos de exploração paralelos via busca em feixe (beam search), o que introduz um overhead de memória e complexidade computacional significativos sem garantir a validade do raciocínio.

Metodologia: Search-on-Graph (SoG)

Os autores propõem o Search-on-Graph (SoG), um framework que unifica a seleção de caminho e o raciocínio dentro de um único LLM. O SoG opera em um paradigma observar-pensar-navegar, onde o LLM atravessa iterativamente o KG tomando decisões informadas baseadas no histórico de raciocínio completo e na estrutura local atual do grafo.

Componentes Principais

1. Busca Iterativa de 1-Salto (1-Hop Search):
   O SoG utiliza uma única função Search cuidadosamente projetada como a única interface do LLM para a exploração do KG. Esta função recupera vizinhos de 1-salto de uma entidade dada em uma direção especificada (saída ou entrada).

   • Entrada: ID da Entidade, direção e propriedades opcionais para filtragem.
   • Saída: Uma tabela markdown eficiente em termos de espaço contendo IDs de propriedades, rótulos, IDs de valores e rótulos de valores.

2. Tratamento de Nós de Alto Grau:
   Para abordar o desafio de entidades com milhares de conexões (ex: países, celebridades), o SoG emprega um mecanismo de filtragem em dois estágios:

   • Descoberta de Propriedades: Se um nó possui mais de $k$ vizinhos (padrão $k=50$) e nenhuma propriedade específica é solicitada, o sistema retorna apenas os tipos de propriedades únicos, em vez de todas as instâncias.
   • Recuperação Direcionada: O LLM analisa as propriedades disponíveis e realiza uma segunda chamada de Search direcionada com propriedades específicas para recuperar apenas os vizinhos relevantes.
   • Truncamento: Se os resultados ainda excederem um limite $p$ (padrão $p=1000$), a lista é truncada para caber nos limites de contexto.

3. Navegação Consciente do Contexto:
   Ao contrário dos métodos de beam search que mantêm múltiplos caminhos paralelos, o SoG guia o LLM para selecionar uma única relação em cada etapa com base no histórico completo de raciocínio. O LLM observa os vizinhos da entidade atual, raciocina sobre qual caminho avança a resposta (ex: "Estou em Zundert, vim de Van Gogh, preciso do país, então procuro por 'Contido por'") e navega de acordo. Isso garante coerência lógica sem o acúmulo de ruído da exploração paralela.

4. Estratégia de Prompting:
   O sistema utiliza um system prompt definindo o papel do agente e um conjunto de exemplares few-shot (tipicamente 5) demonstrando três fases: exploração inicial, travessia iterativa e extração de resposta. O LLM determina autonomamente quando informações suficientes foram reunidas para interromper as chamadas de ferramenta e fornecer uma resposta final.

Principais Contribuições

1. Um Framework Unificado: O SoG propõe um framework de KGQA simples, porém eficaz, onde um único LLM orquestra a travessia iterativa do KG, eliminando a necessidade de módulos separados de planejamento ou recuperação.
2. Navegação Consciente do Contexto: O método realiza a navegação baseada no histórico completo de raciocínio, evitando a deriva semântica comum em métodos de poda sem contexto como o Think-on-Graph (ToG).
3. Agnosticismo de Esquema: A abordagem generaliza através de diferentes esquemas de KG (Freebase e Wikidata) sem modificação ou ajuste fino específico para a tarefa.
4. Eficiência: Ao selecionar relações únicas por salto em vez de manter caminhos paralelos, o SoG reduz significativamente o número de chamadas de LLM e tokens de saída em comparação com as bases de comparação de beam search.

Resultados Experimentais

Os autores avaliaram o SoG em seis benchmarks de KGQA abrangendo Freebase (SimpleQA, WebQSP, CWQ, GrailQA) e Wikidata (QALD-9, QALD-10).

• Desempenho: O SoG alcançou resultados de estado da arte (SOTA) em cinco de seis conjuntos de dados sem qualquer ajuste fino específico para a tarefa.
  • Nos benchmarks de Wikidata, demonstrou ganhos substanciais de mais de 11,3% em relação aos melhores métodos anteriores.
  • Nos conjuntos de dados Freebase, superou sistemas anteriores, ficando atrás por apenas 0,1% no CWQ em relação ao Generate-on-Graph.
• Robustez do Backbone: O framework é compatível com vários backbones de LLM. Alcançou desempenho SOTA usando o GPT-4o e também demonstrou resultados fortes com modelos de código aberto (série Qwen3). Notavelmente, mesmo o modelo compacto Qwen3-4B superou métodos anteriores nos benchmarks de Wikidata, provando a eficácia do método em diferentes tamanhos de modelo.
• Eficiência: Comparado ao baseline Think-on-Graph, o SoG reduziu as chamadas de LLM em pelo menos 46,4% e os tokens de saída em 69,9%, embora exija mais tokens de entrada para manter o contexto completo de raciocínio.
• Estudos de Ablação:
  • Aprendizado Few-Shot: O desempenho melhorou dramaticamente com apenas um exemplar de navegação, estabilizando-se com 3 a 5 shots.
  • Tipo de Modelo: Modelos de "Pensamento" (otimizados para raciocínio) superaram consistentemente modelos padrão de instrução, particularmente em tarefas de múltiplos saltos (multi-hop).
  • Formato de Saída: O formato proposto de "Markdown + Filtro de Propriedade" alcançou o melhor equilíbrio entre precisão e eficiência de tokens.

Significância e Alegações

O artigo afirma que o Search-on-Graph valida um novo paradigma onde a navegação impulsionada por LLM é uma abordagem de raciocínio em grafos de conhecimento superior aos métodos que dependem de módulos de seleção separados ou planejamento prévio.

Os autores argumentam que a suposição de que um único LLM está mais equipado para selecionar relações relevantes em cada etapa — com base nos requisitos reais de raciocínio e no contexto completo — é verdadeira. Essa abordagem simplifica a arquitetura, reduz o overhead computacional e generaliza efetivamente através de diferentes esquemas de KG e tamanhos de modelo. Os resultados sugerem que a simplicidade arquitetônica, combinada com o gerenciamento cuidadoso do contexto, pode superar sistemas mais elaborados de múltiplos componentes.