Resumo Técnico: Computação Empírica: Prompting versus Programação

Declaração do Problema

O artigo identifica uma mudança de paradigma na resolução de problemas computacionais: a transição da programação (especificação de algoritmos e estruturas de dados precisos) para o prompting (fornecimento de descrições informais em linguagem natural para Grandes Modelos de Linguagem ou agentes). Enquanto a computação tradicional baseia-se em procedimentos determinísticos com correção verificável e limites de complexidade bem definidos (por exemplo, $O(n \log n)$ para ordenação), a "computação empírica" baseia-se na amostragem de saídas de uma distribuição de probabilidade.

O problema central é que as capacidades e os limites desta nova forma de computação não podem ser compreendidos dentro do clássico framework racionalista da ciência da computação. Especificamente:

1. Falta de Determinismo: As saídas não são geradas proceduralmente, mas são o resultado "empiricamente mais provável", tornando-as suscetíveis a alucinações e erros que não podem ser localizados ou reparados via depuração tradicional.
2. Ambiguidade na Entrada: Ao contrário da programação, que exige contratos formais (tipos, formatos), o prompting aceita entradas informais onde a interpretação depende do contexto e da distribuição de treinamento do modelo.
3. Complexidade Incerta: O comportamento do tempo de execução parece estar desacoplado da complexidade computacional clássica, correlacionando-se, em vez disso, com a tokenização e o comportamento de inferência do modelo.
4. Lacuna de Verificação: As técnicas existentes de engenharia de software (SE) (análise estática, verificação formal) são mal equipadas para analisar sistemas onde não existe um programa explícito para verificar.

Metodologia

Os autores conduziram experimentos preliminares para caracterizar a eficiência e a correção da computação empírica em cinco problemas computacionais clássicos:

1. Ordenação (Sorting): Ordem ascendente de números aleatórios.
2. Busca (Searching): Encontrar um índice em listas ordenadas e não ordenadas.
3. Maior Substring Palindrômica (Longest Palindromic Substring): Encontrar a sequência palindrômica mais longa em uma string.
4. Problema da Soma de Subconjuntos (Subset Sum Problem - SSP): Encontrar um subconjunto de números que some um valor alvo.

Configuração Experimental:

• Modelo: Os experimentos utilizaram o modelo de pesos abertos gemma-4-26b-a4b rodando localmente em um MacBook Pro (M5 Pro, 48GB RAM) para eliminar a latência de rede.
• Configurações: Três modos foram testados:
  • Default (Padrão): Temperatura = 1.0.
  • Deterministic (Determinístico): Temperatura = 0.0.
  • Thinking (Pensamento): Modo de raciocínio habilitado.
• Métricas:
  • Eficiência: Tempo para a solução e tempo para a primeira solução correta.
  • Correção: Proporção de tentativas que retornam a resposta matematicamente correta.
• Variáveis: Tamanho da entrada ($n$), precisão numérica e representação linguística (dígitos vs. palavras em vários idiomas: inglês, alemão, coreano, japonês, etc.).
• Verdade Fundamental (Ground Truth): Para problemas não triviais (Substring, SSP), programas simples em Python geraram as respostas corretas para validação.

Resultados Principais

1. Eficiência vs. Complexidade Clássica

Contrariamente à teoria clássica, o tempo de execução da computação empírica não segue estritamente a complexidade algorítmica do problema (ex: $O(n)$ vs. $O(n \log n)$).

• Escalonamento Linear: Para ordenação, busca e SSP, o tempo para a solução aumentou linearmente com o tamanho da entrada ($O(n)$) em todos os modos. Os autores atribuem isso ao aumento linear de tokens de entrada/saída, em vez da lógica computacional.
• Dependência de Tokens: O tempo para incrementar um número foi comparável ao de prever texto puro de um hash SHA-512, sugerindo que o tempo de execução é impulsionado pela tokenização e mecânicas de inferência, em vez da dificuldade do problema.
• Custo do Modo Thinking: Habilitar o "pensamento" (raciocínio) aumentou significativamente o tempo de execução (ex: até 275s para ordenar 150 elementos), mas manteve uma alta correção.

2. Correção e Tamanho da Entrada

• Sensibilidade ao Tamanho: Nos modos Default e Deterministic, a correção degradou rapidamente conforme o tamanho da entrada aumentava.
  • Para ordenar 50 inteiros, a correção caiu para ~50% (probabilidade de cara ou coroa).
  • Para ordenar 150 inteiros, a correção caiu para ~58% (apesar do aumento de tempo linear).
  • Para o problema da Soma de Subconjuntos, a correção aproximou-se de zero para listas de comprimento 10.
  • Para o problema da Substring, a correção caiu para próximo de zero para strings de comprimento 5.
• Resiliência do Modo Thinking: Quando as capacidades de raciocínio foram habilitadas, a correção permaneceu alta (>90%) mesmo para entradas maiores, embora dentro dos limites de tokens/tempo.

3. Impacto da Representação em Linguagem Natural

O estudo investigou como a linguagem usada para representar números afeta a correção.

• Viés de Representação de Dados: A correção é fortemente dependente da representação da linguagem nos dados de treinamento do modelo.
• Alta vs. Baixa Representação: Ordenar números escritos em inglês (bem representado) rendeu >95% de correção para o tamanho 20. Em contraste, ordenar números escritos em alemão (sub-representado) rendeu <1% de correção para o mesmo tamanho.
• Conclusão: A computação empírica não é agnóstica à linguagem; ela é enviesada para linguagens e formatos prevalentes no corpus de treinamento.

4. Características de Erro

Ao contrário de programas tradicionais, onde as falhas podem ser localizadas em linhas específicas de código, os erros na computação empírica são não-determinísticos. O LLM pode:

• Adicionar números não presentes na entrada.
• Remover números presentes na entrada.
• Duplicar números.
• Falhar em ordenar a lista inteira.
• Truncar grandes entradas.

Principais Contribuições

1. Definição de Computação Empírica: O artigo introduz formalmente a "computação empírica" como um campo distinto onde soluções são geradas via prompting e amostragem, em vez de execução procedural.
2. Caracterização Empírica: Fornece a primeira medição sistemática de eficiência e correção para LLMs resolvendo problemas algorítmicos clássicos, revelando que o tempo de execução correlaciona-se com a tokenização, e não com a complexidade algorítmica.
3. Identificação de Limites: O estudo demonstra que, sem modos de raciocínio, a computação empírica falha em escalar de forma confiável com o tamanho da entrada e é altamente sensível à representação linguística das entradas.
4. Chamada para Novos Fundamentos de SE: Os autores argumentam que a comunidade de engenharia de software deve desenvolver novas ferramentas para "análise de programa empírico" (raciocínio estatístico, contrafactual ou causal) para analisar, estimar e prever a correção desses sistemas.

Significância e Visão

O artigo postula que a comunidade de engenharia de software não pode confiar em frameworks racionalistas clássicos ou ferramentas de análise de programa existentes para garantir a confiabilidade da computação impulsionada por IA. À medida que LLMs e agentes se tornam integrais para resolver problemas computacionais, o campo deve evoluir para abordar:

• Como analisar a correção na ausência de um programa formal.
• Como definir e testar os limites da computação empírica.
• Como melhorar a correção para instâncias específicas de problemas sem introduzir regressões.

Os autores enquadram isso como uma área de pesquisa oportuna e rica, instando o desenvolvimento de técnicas de "análise de programa empírico" para preencher a lacuna entre a natureza probabilística dos LLMs e as exigências rigorosas da engenharia de software. O artigo não pretende resolver esses problemas, mas sim estabelecer o campo e destacar a necessidade urgente de novos fundamentos teóricos e práticos.