Resumo Técnico: Priores de LLM para ERM sobre Programas

Declaração do Problema

O artigo aborda a tensão fundamental entre eficiência de amostragem e eficiência computacional no aprendizado de descrições de programas curtos e discretos (ex: "código Python") a partir de dados rotulados.

A teoria clássica do aprendizado (PAC learning) sugere que, se uma função alvo admite uma descrição de programa curta de comprimento $L$ sobre um alfabeto $\Sigma$, ela pode ser aprendida a partir de $\tilde{O}(L \log |\Sigma|)$ exemplos via Minimização do Risco Empírico (ERM) sobre a classe de programas. No entanto, implementar o ERM requer a enumeração exaustiva de programas candidatos, o que escala exponencialmente como $\Theta(|\Sigma|^L)$, tornando-o computacionalmente inviável mesmo para um $L$ moderado.

Por outroして, abordagens modernas de aprendizado profundo usando Gradiente Descendente Estocástico (SGD) em redes neurais de alta capacidade evitam a enumeração explícita e são computacionalmente eficientes. Contudo, resultados teóricos no framework de Consultas Estatísticas (SQ) indicam que métodos baseados em gradiente lutam com famílias estruturadas e "SQ-hard" (como funções de paridade e primitivas criptográficas). Esses métodos frequentemente exigem um número exponencial de amostras para ter sucesso, pois a interface de gradiente é mal compatível com a estrutura discreta da regra alvo, levando à falha de generalização além das sequências de treinamento.

A questão central é: Podemos recuperar a eficiência de amostragem do ERM sobre programas curtos sem pagar o custo total da enumeração exaustiva?

Metodologia: LLM-PV

Os autores propõem o LLM-PV (LLM Propose-and-Verify), um algoritmo de aprendizado que trata um Grande Modelo de Linguagem (LLM) pré-treinado não como um preditor, mas como um prior de busca para o ERM.

O Algoritmo

O LLM-PV desacopla os papéis de proposta e seleção:

1. Proposta (O Prior): Um LLM pré-treinado é estimulado (prompted) com um conjunto de treinamento $S_{tr}$ para induzir uma distribuição dependente dos dados sobre candidatos a programas. O LLM gera um pequeno número de programas candidatos (ou edições) que se hipotetiza explicarem os dados.
2. Verificação (O Passo ERM): Cada programa candidato é compilado e executado em um conjunto de validação mantido à parte $S_{val}$. Programas que falham ao compilar, não param ou produzem saídas inválidas são descartados.
3. Seleção: O algoritmo seleciona o programa com o menor erro de validação. Crucialmente, nenhum update de gradiente é realizado no LLM, e nenhum feedback de validação é usado para adaptar a distribuição de amostragem do LLM durante a busca. O LLM atua unicamente como um mecanismo de viés indutivo.

Framework Teórico

O artigo formaliza o desempenho do LLM-PV usando uma garantia de "propor e verificar". Se a distribuição de proposta do LLM coloca uma massa não desprezível $p_\epsilon(S_{tr})$ em programas com erro de população $\le \epsilon$, então o número de tentativas $k$ para encontrar uma boa hipótese escala como $O(\log(1/\delta) / p_\epsilon(S_{tr}))$. Isso substitui o espaço de busca exponencial $|\Sigma|^L$ por um tamanho de busca efetivo de $1/p_\epsilon(S_{tr})$.

Os autores também fornecem limites inferiores teóricos demonstrando que, para problemas de $k$-paridade plantados, o SGD de coordenada de mini-lote de precisão finita requer $\Omega(\sqrt{N}/2^b)$ novos exemplos (onde $N$ é o número de alvos possíveis), enquanto a enumeração requer $\Theta(|\Sigma|^L)$ tempo. Isso estabelece um regime onde tanto a enumeração ingênua quanto o treinamento padrão baseado em gradiente falham, motivando a abordagem LLM-PV.

Principais Contribuições

1. Formalização da Tensão Computação-Amostragem: O artigo isola um regime específico de poucos dados (paridade $k$-plantada) onde o ERM de classe finita é eficiente em amostragem, mas computacionalmente intratável, enquanto o treinamento baseado em gradiente é computacionalmente conveniente, mas ineficiente em amostragem devido à dureza SQ.
2. Algoritmo LLM-PV: A introdução de um pipeline limpo de "propor e verificar" que utiliza LLMs pré-treinados estritamente como um mecanismo de proposta. Isso preserva a auditabilidade e as garantias teóricas do ERM (seleção baseada em erro de validação) enquanto aproveita a capacidade do LLM de concentrar a busca em hipóteses plausíveis.
3. Evidência Empírica de Recuperação de Regra: Experimentos extensos através de diversas tarefas algorítmicas (variantes de paridade, autômatos celulares, palíndromos, Dyck-2, teste de primalidade e paridade de SHA-256) mostram que o LLM-PV frequentemente recupera a regra subjacente exata a partir de apenas 200 exemplos rotulados.
4. Generalização de Comprimento: Ao contrário de modelos transformer treinados via SGD, modelos ajustados (fine-tuned) ou baselines de Aprendizado em Contexto (ICL), que frequentemente memorizam distribuições de treinamento e falham ao generalizar para sequências de entrada mais longas, o LLM-PV frequentemente sintetiza programas invariantes de dimensão que generalizam perfeitamente para comprimentos de entrada muito superiores aos do conjunto de treinamento.
5. Auditabilidade: O método produz código executável e legível por humanos e um rastro de raciocínio completo (a sequência de programas propostos e seus erros de validação), permitindo depuração direta e validação mecanística do processo de aprendizado.

Resultados

Os autores avaliaram o LLM-PV contra uma ampla gama de baselines, incluindo ML clássico (XGBoost, SVM, Algoritmos Genéticos), modelos treinados via SGD (do zero e fine-tuned) e In-Context Learning (ICL) com modelos de grande escala ajustados para instrução.

• Tarefas Algorítmicas: Em tarefas como 10-Parity, Cellular Automata Parity e testes de primalidade, os baselines padrão (incluindo modelos ICL de 30B+ parâmetros) tiveram desempenho próximo ao acaso (50% de acurácia) em comprimentos de teste ($n=100$), mesmo quando treinados em 200 exemplos. Em contraste, o LLM-PV alcançou 100% de acurácia de teste nessas tarefas com os mesmos 200 exemplos.
• Generalização: Ao serem treinados em sequências curtas ($n=10$) e testados em sequências longas ($n=100$), os baselines de SGD e fine-tuning colapsaram para a acurácia de acaso. O LLM-PV manteve alta acurácia, sintetizando com sucesso regras que são invariantes ao comprimento de entrada.
• Escalabilidade de Dados: Aumentar o tamanho do conjunto de treinamento para modelos baseados em SGD (até 100k exemplos) não resolveu a falha de generalização nas tarefas de paridade e autômatos celulares, confirmando a natureza SQ-hard desses problemas para aprendizes baseados em gradiente.
• Uso de Ferramentas: O artigo observa que, embora o ICL aumentado por ferramentas (onde o modelo pode executar código) melhore o desempenho em relação ao prompting direto, ele ainda falha em recuperar regras algorítmicas de forma confiável. O sucesso do LLM-PV é atribuído ao objetivo de busca específico (propor programas e selecionar por erro de validação) em vez do acesso a ferramentas por si só.
• Dados Tabulares: Em benchmarks tabulares padrão, o LLM-PV teve desempenho comparável a fortes aprendizes tabulares, sugerindo que a abordagem não se limita a tarefas de sequências sintéticas.

Significância e Alegações

O artigo afirma que priores de LLM pré-treinados podem servir como vieses de busca eficazes para o ERM, reduzindo com sucesso a lacuna entre eficiência estatística e computacional no aprendizado de programas.

A principal significância reside na separação de papéis: o LLM é usado apenas para propor hipóteses, enquanto o objetivo de aprendizado permanece fundamentado em verificação executável e erro de validação. Esta abordagem:

• Evita a natureza de "caixa preta" dos preditores baseados em gradiente ao fornecer código explícito e verificável.
• Supera a ineficiência de amostragem de métodos baseados em gradiente em tarefas discretas e estruturadas onde o alvo admite uma descrição curta.
• Fornece um mecanismo para generalização de comprimento que os métodos tradicionais de deep learning falham em alcançar em tarefas algorítmicas.

Os autores são modestos quanto ao escopo, reconhecendo que o método depende da capacidade do LLM de colocar massa suficiente nos programas corretos e que a abordagem é atualmente adaptada para regimes de poucos dados e estruturados, em vez de servir como um substituto geral para o aprendizado supervisionado profundo em dados não estruturados. O sucesso depende de o "propositor" ser capaz e a "verificação" ser robusta.