Resumo Técnico: GraphInstruct

Declaração do Problema

Dados estruturados em grafos são fundamentais para aplicações que vão desde análise de citações e modelagem de redes sociais até design molecular e construção de grafos de conhecimento. Embora os Modelos de Linguagem de Grande Escala (LLMs) sejam cada vez mais utilizados como sintetizadores de grafos orientados por prompts, os frameworks de avaliação existentes sofrem de uma lacuna diagnóstica crítica. Os benchmarks clássicos frequentemente antecedem a era dos LLMs ou organizam as avaliações ao longo de eixos (por exemplo, tipo de grafo, domínio de tarefa) que promediam a complexidade estrutural que governa as falhas dos modelos. Consequentemente, as pontuações agregadas de qualidade não conseguem localizar onde no espectro de complexidade um LLM falha, obscurecendo se um método melhora a adesão a uma única restrição, a composição de múltiplas restrições ou a fundamentação semântica de domínio. Há uma falta de benchmarks que estratifiquem a geração de grafos por complexidade estrutural progressiva e forneçam verificação determinística por restrição para impulsionar o desenvolvimento direcionado de métodos.

Metodologia

O Benchmark GraphInstruct

O GraphInstruct é um benchmark de complexidade progressiva projetado para diagnosticar lacunas de capacidade na geração de grafos por LLMs. Ele compreende três componentes principais:

1. Camada de Instrução Progressiva: O benchmark organiza 800 instruções escritas manualmente em seis níveis de complexidade (L0–L5), onde cada nível introduz um novo tipo de restrição estrutural em vez de um escalar de dificuldade monotônico:

   • L0 (Geração de Formato): Emissão pura de sintaxe (por exemplo, contagens de nós/arestas).
   • L1 (Restrição Explícita Única): Uma restrição estrutural (por exemplo, "uma árvore com 10 nós").
   • L2 (Composição de Múltiplas Restrições): Satisfação simultânea de $\ge$4 restrições conjuntas (por exemplo, direcionado, conectado, distribuição de grau específica).
   • L3 (Controle de Atributos Numéricos): Controle sobre propriedades numéricas como densidade, coeficientes de agrupamento e comprimentos de caminho.
   • L4 (Semântica de Domínio): Geração de grafos aderentes a priores específicos de domínio (por exemplo, redes sociais, estruturas moleculares) com rótulos de texto associados.
   • L5 (Edição de Grafos em Múltiplos Passos): Edição de um grafo base por meio de operações ordenadas para satisfazer novas restrições.

2. Soluções de Referência: O benchmark inclui 1.582 soluções de referência sintetizadas algoritmicamente (duas por instrução viável). Estas são geradas por algoritmos de satisfação de restrições (por exemplo, geradores do NetworkX, descascamento de k-core) e verificadas por meio de um conjunto de 549 testes unitários cobrindo analisadores, validadores e métricas. Nove instruções L2 são intencionalmente inviáveis para servir como detectores de alucinação.

3. Pipeline de Avaliação em Cinco Dimensões: As saídas são pontuadas em cinco dimensões complementares, com subconjuntos ativos variando por nível:

   • D1 (Fidelidade Estrutural): Taxa de validade e unicidade; inclui MMD (Discrepância Média Máxima) para níveis orientados por distribuição (L3–L4).
   • D2 (Similaridade Textual): Sobreposição em nível de token e presença de texto específico de domínio (ativo principalmente em L4).
   • D3 (Qualidade de Embedding): Coerência de Grassmann e lacunas de classificação de nós (ativo em L3+).
   • D4 (Correspondência de Instrução): Satisfação de restrição explícita, inferência implícita e verificações de contradição. Esta dimensão fornece o sinal de feedback determinístico para métodos iterativos.
   • D5 (Eficiência de Token): Combina tokens por grafo válido (TPV) e contagens de chamadas de API.

Protocolo de Avaliação

Os autores conduziram uma avaliação de capacidade em grande escala em 12 LLMs (abrangendo três níveis de capacidade: T1, T2, T3) e quatro estratégias de prompting (Zero-Shot, Few-Shot, Zero-CoT, Few-CoT). Isso resultou em aproximadamente 180.000 saídas geradas. Além disso, os autores propuseram e avaliaram um framework de Geração Iterativa Guiada por Verificação (VGIG), Prompting Adaptativo Consciente de Restrições (CAAP) e Priors de Domínio para demonstrar a utilidade do benchmark como uma plataforma de desenvolvimento.

Principais Descobertas

A avaliação produziu seis achados diagnósticos (F1–F6) que benchmarks agregados ocultam sistematicamente:

• F1: Poder Discriminativo Pico na Composição de Restrições. A maior lacuna de capacidade entre modelos de nível superior (T1) e nível inferior (T3) ocorre em L2 (composição de múltiplas restrições), com uma lacuna de 0,219. Isso é 1,8–3$\times$ maior do que as lacunas em outros níveis, indicando que a satisfação simultânea de múltiplas restrições é o principal gargalo, e não a profundidade de raciocínio (L3–L5).
• F2: Sensibilidade ao Prompt Escala Inversamente com a Capacidade. Modelos mais fracos (T3) exibem alta sensibilidade às estratégias de prompting (grande variância na qualidade entre estratégias), enquanto modelos mais fortes (T1) são mais estáveis. Orçamentos de engenharia de prompt devem escalar inversamente à capacidade do modelo.
• F3: Nenhuma Estratégia de Prompting Universal. Nenhuma estratégia única domina em todos os níveis. Por exemplo, Few-Shot é prejudicial em L2 (viésando a topologia) mas benéfico em L4 (transmitindo priores de domínio); Few-CoT ajuda em L5 (etapas de edição) mas prejudica L3 (amplificando o desvio numérico).
• F4: Polaridade do CoT é Limitada à Família do Modelo. A eficácia do prompting Chain-of-Thought (CoT) não é uniforme entre famílias. É uniformemente positivo para a família Qwen3.5, mas claramente negativo para modelos GPT mais fracos (GPT-3.5, GPT-4o-mini), sugerindo que a distribuição de pré-treinamento dita a utilidade do CoT mais do que o nível de capacidade.
• F5: Escalonamento de Parâmetros é Não Monotônico por Nível. O escalonamento dentro de uma família (por exemplo, Qwen3.5 de 35B para 397B) não garante melhoria em cada nível. Notavelmente, modelos maiores não mostraram ganho detectável em L5 (edição de grafos) e, na família GPT, modelos menores (GPT-3.5) superaram os maiores (GPT-4.1) em atributos numéricos de L3.
• F6: Teto de Capacidade Consciente de Custo. Apenas 6 de 45 configurações (modelo, estratégia) são Pareto-ótimas. Três modelos T3 nunca atingem um limiar de qualidade de $Q \ge 0,8$ independentemente da estratégia de prompting, estabelecendo um teto de capacidade empírico que o prompting sozinho não pode ultrapassar.

Resultados de Desenvolvimento de Métodos

Usando os sinais D4 de alta granularidade do benchmark, os autores desenvolveram um pipeline guiado por verificação (Combinado: CAAP + VGIG + Priors de Domínio).

• Superando o Oráculo: A abordagem Combinada superou o "Oráculo" (o melhor das quatro estratégias de prompting padrão por nível) em +0,035 a +0,050 em três modelos-alvo.
• Verificação vs. Amostragem: A amostragem pura (tentativa novamente ou auto-consistência) sem verificação falhou em melhorar o desempenho, confirmando que, para tarefas estruturadas de grafos, a infraestrutura de verificação é mais crítica do que a amostragem paralela.
• Granularidade do Feedback: Um sinal binário de aprovação/rejeição capturou 75% do ganho total, com feedback mais fino adicionando melhorias marginais.
• Saturação de Iteração: O refinamento iterativo satura em aproximadamente 5 rodadas, significativamente mais curto do que as 10–20 rodadas típicas em auto-refinamento de domínio de texto.
• Invariância L4: A qualidade de L4 (semântica de domínio) permaneceu invariante à contagem de iterações e à granularidade do feedback, indicando que este modo de falha é uma "lacuna de fundamentação" que requer recuperação ou priores de domínio em vez de mais computação.

Significado e Alegações

O artigo alega que o GraphInstruct é o primeiro benchmark a ocupar seis eixos diagnósticos simultaneamente: geração de grafos estáticos, estratificação de complexidade em 6 níveis, avaliação em 5 dimensões, levantamento de 12 LLMs, referências sintetizadas algoritmicamente e métodos de melhoria incorporados.

Os autores posicionam o GraphInstruct não meramente como uma ferramenta de avaliação, mas como uma plataforma de desenvolvimento. Os sinais de verificação determinística por restrição de alta granularidade (D4) permitem famílias de métodos (como VGIG) que benchmarks agregados não podem suportar. Os achados sugerem que a pesquisa futura deve mudar da engenharia de prompt geral para:

1. Iteração guiada por verificação para restrições estruturais (L0–L3, L5).
2. Recuperação e fundamentação para semântica de domínio (L4).
3. Estratégias de prompting específicas por família em vez de suposições universais de CoT.

O trabalho conclui que benchmarks agregados subestimam sistematicamente o poder discriminativo da geração estruturada e que a próxima fronteira de pesquisa reside em quebrar a barreira de saturação do prompting iterativo por meio de geração aumentada por recuperação e métodos conscientes de estrutura. Todos os dados, código e artefatos de reprodutibilidade foram lançados publicamente.