Autonomous Knowledge Graph Exploration with Adaptive Breadth-Depth Retrieval

1. Declaração do Problema

A recuperação de evidências em Grafos de Conhecimento (KGs) para consultas de Modelos de Linguagem de Grande Escala (LLMs) envolve um compromisso fundamental entre amplitude (cobrir o grafo para encontrar entidades relevantes) e profundidade (travar caminhos relacionais de múltiplos saltos para encontrar evidências específicas).

• Recuperadores baseados em similaridade (e.g., BM25, embeddings densos) oferecem cobertura ampla, mas frequentemente permanecem superficiais, falhando em capturar cadeias relacionais complexas.
• Métodos baseados em travessia (e.g., agentes de grafo) excel em raciocínio de múltiplos saltos, mas dependem da seleção de nós "semente" para iniciar a exploração. Se a seleção da semente for ambígua ou incompleta, a busca fica presa localmente, perdendo evidências relevantes em outros lugares.
• Limitações existentes: As abordagens atuais frequentemente tratam esses modos de forma isolada, exigem treinamento específico para a tarefa ou dependem de seleção de semente frágil e profundidades de salto pré-definidas. Há uma falta de um framework sem treinamento que equilibre dinamicamente a busca global e a travessia local com base nas necessidades da consulta.

2. Metodologia: ARK (Recuperador Adaptativo de Conhecimento)

O ARK é um framework de recuperação sem treinamento, que utiliza ferramentas, capacitando um agente LLM a navegar autonomamente em um KG. Ele opera através de um processo interativo onde o agente seleciona ferramentas para construir uma trajetória de recuperação.

Arquitetura Central

• Definição do Agente: Um agente $A = \langle LLM, T \rangle$ interage com um KG $G = \langle V, E, \dots \rangle$. O agente mantém uma lista classificada de nós recuperados $R$ e termina através de uma ação FINISH ou um limite de etapas.
• Interface de Duas Ferramentas:
  1. Busca Global (SearchG): Realiza uma busca léxica (usando BM25) sobre descritores de nós (títulos, descrições) em todo o grafo. Isso fornece pontos de entrada amplos para consultas ricas em texto.
  2. Exploração de Vizinhança (Neighbors): Explora o bairro de um salto de um nó específico, filtrado por tipos de nó/aresta e opcionalmente reclassificado por uma subconsulta. Isso permite travessia direcionada de múltiplos saltos.
• Estratégia Adaptativa: O LLM decide dinamicamente qual ferramenta usar com base na consulta e no contexto atual.
  • Consultas ricas em texto: Prioriza Busca Global.
  • Consultas ricas em relações: Prioriza Exploração de Vizinhança para traversar caminhos.
  • Consultas complexas: Alterna entre reancoragem global e expansão local.
• Exploração Paralela: Para melhorar a robustez, o ARK executa $n$ agentes independentes em paralelo. Suas listas recuperadas são agregadas usando uma estratégia de fusão de classificação baseada em votação (frequência de aparência + tempo de descoberta mais cedo).
• Destilação sem Rótulos: Uma inovação chave é a capacidade de destilar a política de uso de ferramentas de um grande modelo "professor" (e.g., GPT-4.1) para um modelo "aluno" menor (e.g., Qwen3-8B) usando ajuste fino supervisionado em trajetórias de interação. Crucialmente, isso requer nenhum rótulo de relevância ground-truth; o aluno aprende imitando as chamadas de ferramentas e observações bem-sucedidas do professor.

3. Contribuições Principais

1. Framework ARK: Introdução de um framework de recuperação sem treinamento que dá aos LLMs controle sobre o compromisso amplitude-profundidade através de um conjunto mínimo e expressivo de ferramentas (Busca Global + Exploração de Vizinhança).
2. Recuperação Adaptativa: Demonstração de que o ARK pode mudar estratégias autonomamente com base no tipo de consulta (texto vs. relacional) sem regras pré-definidas ou treinamento específico para a tarefa.
3. Destilação Eficiente: Um método para transferir políticas complexas de exploração de grafos de modelos grandes para modelos compactos de 8B através de imitação de trajetória sem rótulos, preservando alto desempenho a uma fração do custo de inferência.
4. Avaliação Abrangente: Benchmarking rigoroso no dataset heterogêneo STaRK, mostrando melhorias consistentes sobre bases de referência tanto baseadas em recuperação quanto baseadas em agentes.

4. Resultados Experimentais

O framework foi avaliado no benchmark STaRK, que inclui três grandes grafos heterogêneos ricos em texto: AMAZON (comércio eletrônico), MAG (acadêmico) e PRIME (biomédico).

• Desempenho:
  • O ARK alcançou o melhor desempenho médio em todas as métricas.
  • Hit@1: 59,1% (Média), melhorando em até 31,4% sobre métodos baseados em recuperação e 28,0% sobre métodos baseados em agentes.
  • MRR: 67,4% (Média).
  • O ARK performou excepcionalmente bem no MAG (73,4% Hit@1) e AMAZON (55,8% Hit@1), mantendo-se competitivo no PRIME.
• Adaptabilidade:
  • No AMAZON (rico em texto), o ARK usou Busca Global em 87,7% das chamadas.
  • No MAG e PRIME (ricos em relações), ele mudou para Exploração de Vizinhança em 65,3% e 52,3% das chamadas, respectivamente, correspondendo à distribuição de consultas sem anotação explícita.
• Eficiência da Destilação:
  • Destilar o ARK para um modelo Qwen3-8B manteve até 98,5% da taxa Hit@1 do professor.
  • No dataset PRIME, o modelo destilado de 8B melhorou o Hit@1 em +13,5 pontos absolutos sobre o modelo base de 8B.
  • A destilação é eficiente em dados: usando apenas 10% das trajetórias de treinamento, recuperou-se aproximadamente metade do ganho total de desempenho.
• Estudos de Ablação:
  • Remover Exploração de Vizinhança causou quedas significativas em grafos relacionais (MAG/PRIME), confirmando a necessidade de travessia de múltiplos saltos.
  • Remover a filtragem baseada em tipos prejudicou o desempenho em grafos heterogêneos, destacando a importância das restrições de esquema.
  • Léxico vs. Densidade: O BM25 (léxico) superou a recuperação densa no setting iterativo do ARK, sugerindo que a capacidade do agente de refinar subconsultas compensa limitações léxicas.

5. Significado e Impacto

• Praticidade: O ARK demonstra que a recuperação robusta de KGs não requer treinamento complexo ou orçamentos massivos de computação. Uma interface de ferramenta simples e bem projetada permite que LLMs naveguem em grafos complexos de forma eficaz.
• Escalabilidade: A abordagem de destilação sem rótulos torna o raciocínio avançado de grafos acessível a modelos menores e de código aberto, reduzindo a barreira de entrada para implantar sistemas aumentados por KGs.
• Interpretabilidade: O sistema oferece um compromisso claro "orçamento-desempenho". Os usuários podem ajustar o número de agentes e limites de etapas para equilibrar latência e precisão, fornecendo um ponto de operação transparente para diferentes necessidades de aplicação.
• Generalização: Ao evitar treinamento específico para a tarefa, o ARK é inerentemente mais transferível entre diferentes domínios e esquemas de grafos em comparação com modelos de recuperação supervisionados.

Em conclusão, o ARK estabelece um novo paradigma para recuperação adaptativa de grafos, provando que combinar busca léxica global com exploração controlada de vizinhança orientada por agentes produz resultados superiores tanto em precisão quanto em eficiência em comparação com métodos estáticos existentes ou puramente baseados em travessia.