Diagnosing CFG Interpretation in LLMs

1. O Problema

À medida que os Grandes Modelos de Linguagem (LLMs) são integrados em sistemas autônomos (agentes), eles precisam interagir com interfaces dinâmicas e interpretáveis por máquinas, como esquemas JSON ou assinaturas de funções definidas em tempo de execução. Isso exige que os LLMs atuem como interpretadores de gramática em contexto (in-context interpreters): dada uma nova Gramática Livre de Contexto (CFG) especificada no prompt, o modelo deve gerar saídas que sejam:

1. Sintaticamente válidas: Seguirem as regras de produção da gramática.
2. Comportamentalmente funcionais: Executarem a ação desejada no ambiente.
3. Semanticamente fiéis: Otimizarem a lógica estrutural correta (a Árvore de Sintaxe Abstrata - AST deve corresponder à intenção).

O desafio central é determinar se os LLMs realmente internalizam a lógica formal de uma gramática nova ou se apenas recuperam regularidades superficiais de seu pré-treinamento. Em cenários reais, "quase correto" é insuficiente, pois erros de delimitação ou desalinhamento lógico podem causar falhas catastróficas.

2. Metodologia

Os autores propõem o ROBOGRID, um framework de avaliação diagnóstica que utiliza um ambiente de mundo em grade determinístico para desacoplar a lógica da tarefa da adesão à sintaxe.

A. Ambiente e Geração de Dados

• ROBOGRID: Um ambiente onde um robô navega, coleta objetos e executa comandos (mover, virar, pegar, loops, condicionais).
• Especificação CFG via EBNF: As gramáticas são definidas usando a Forma Normal de Backus-Naur Estendida (EBNF).
• Geração Controlada: O sistema sintetiza instâncias variando sistematicamente três dimensões (Tabela 1):
  • Recursão: Profundidade máxima de aninhamento ($D$) e probabilidade de ramificação (Else-Branch).
  • Expressão: Profundidade de predicados aritméticos e booleanos ($E$).
  • Superfície: Estilo sintático (Blocos, C-style, S-expr) e Familiaridade Lexical.
• Vocabulário "Alien": Uma inovação crucial onde palavras-chave familiares (ex: loop, if) são substituídas por tokens opacos aleatórios (ex: v_xkqm). Isso força o modelo a depender exclusivamente da indução simbólica a partir da gramática fornecida, eliminando priors semânticos de pré-treinamento.

B. Tarefas de Avaliação

O framework avalia os LLMs em três tarefas progressivamente difíceis:

1. Julgamento de Gramaticalidade: Classificar se uma string é válida ou inválida segundo a CFG.
2. Geração Condicionada ao Objetivo: Sintetizar um programa que leve o robô a um estado final específico.
3. Instrução para Código: Gerar código que implemente fielmente uma instrução em linguagem natural, exigindo alinhamento total de sintaxe, comportamento e semântica.

C. Métricas de Avaliação

Uma hierarquia de três métricas é utilizada para diagnosticar falhas em diferentes níveis:

• Taxa de Validade Sintática (SVR): Proporção de saídas que podem ser analisadas (parseadas) corretamente.
• Taxa de Equivalência Comportamental (BER): Proporção de programas que, ao serem executados, atingem o estado final desejado.
• Taxa de Corretude Semântica (SCR): Proporção de saídas cuja AST induzida é estruturalmente idêntica à solução de referência (ground-truth).
• Métricas Condicionais (CBER, CSCR): Isolam o desempenho lógico assumindo que a sintaxe já está correta.

3. Contribuições Principais

1. ROBOGRID: Um benchmark diagnóstico que utiliza uma hierarquia de três camadas (Sintaxe, Comportamento, Semântica) para localizar falhas no raciocínio estrutural.
2. Formalização da Tarefa: Define a interpretação de gramática em contexto como um problema de indução de regras formais, deslocando o foco do reconhecimento de padrões superficiais.
3. Caracterização dos Limites Operacionais: Revela uma lacuna massiva entre a adesão sintática e o alinhamento semântico, demonstrando que a capacidade de manter a fidelidade lógica colapsa com o aumento da complexidade.

4. Resultados e Descobertas Chave

Os experimentos com diversos modelos (Qwen, GPT-5, DeepSeek, etc.) revelaram um degradação hierárquica consistente: $SCR < BER < SVR$.

• Colapso Estrutural: Embora os modelos frequentemente mantenham a sintaxe superficial (alta SVR), a fidelidade semântica (SCR) cai drasticamente sob alta densidade estrutural (recursão profunda e alto branching).
• Dependência de Priors Semânticos: O uso do vocabulário "Alien" causou uma queda acentuada no desempenho. Isso indica que os LLMs dependem de bootstrapping semântico (adivinhar a função de palavras-chave familiares) em vez de realizar indução simbólica pura baseada na gramática fornecida.
• Impacto da Recursão: Existe um decaimento não linear acentuado à medida que a profundidade de aninhamento aumenta. Em profundidades extremas ($D=20$), o alinhamento semântico quase desaparece (próximo de 0%), mesmo que a sintaxe pareça válida.
• Estratégias de Prompting:
  • Chain-of-Thought (CoT): É uma necessidade funcional para manter o rastreamento de estado hierárquico. Sem CoT, o desempenho é abismal.
  • Few-Shot Learning: Apresenta retornos decrescentes. Em estruturas recursivas profundas, exemplos adicionais não ajudam significativamente e podem introduzir ruído.
• Falhas Específicas:
  • Fragilidade Sintática: Erros de delimitadores e mapeamento lexical.
  • Desalinhamento Comportamental: Predicados lógicos invertidos ou falhas na simulação aritmética.
  • Deriva Semântica: O modelo gera código funcional, mas com uma AST diferente (ex: achatamento de expressões ou repetição autoregressiva de blocos).

5. Significado e Conclusão

O trabalho demonstra que, embora os LLMs de última geração (SOTA) pareçam fluentes em linguagens comuns, eles carecem de rastreamento de estado hierárquico robusto necessário para agentes confiáveis e agnósticos à gramática.

A descoberta de que a coerência semântica se perde rapidamente sob recursão profunda e dependência de vocabulário familiar sugere que os modelos atuais não internalizam verdadeiramente a lógica formal de novas especificações. Em vez disso, eles simulam sucesso baseado em heurísticas superficiais. Para criar agentes robustos, a comunidade precisa avançar além do prompt engineering de superfície e desenvolver mecanismos de indução simbólica robusta e rastreamento de estado confiável em estruturas hierárquicas densas.