Adam Langley usa Lean e LLMs para automatizar provas e recriar o Zstandard

O especialista em computação e segurança Adam Langley publicou uma análise detalhada sobre o uso de Modelos de Linguagem de Grande Porte (LLMs) para automatizar a verificação de provas formais na linguagem Lean, aplicando o conceito na construção do zero de um decodificador para o utilitário de compressão Zstandard (zstd). Em sua publicação lançada na plataforma pessoal sob a URL relativa a julho de 2026, intitulada "We have proof automation now", Langley demonstra como sistemas modernos de inteligência artificial podem superar o histórico gargalo de esforço técnico exigido por linguagens com tipos dependentes, como o Lean e o histórico Coq — recentemente renomeado para Rocq.

A atração exercida por linguagens baseadas em tipos dependentes decorre da capacidade do seu compilador de codificar e impor invariantes matemáticas arbitrárias diretamente na estrutura de tipos do programa. Em linguagens de programação convencionais, essas garantias de projeto terminam apenas registradas em comentários de código que se perdem rapidamente conforme as equipes de engenharia crescem. Langley relembra que participou anos atrás de uma conferência sobre a linguagem Coq na Universidade de Princeton, onde sugeriu ao público que o nome da linguagem era um obstáculo comercial no mundo anglófono, oportunidade em que fez piadas citando a personagem Tyrion Lannister e os termos Coq e Hoare antes do encerramento da série da HBO.

O grande obstáculo histórico desse paradigma de programação reside no enorme volume de esforço humano necessário para construir as demonstrações matemáticas exigidas pelo compilador. Langley relata ter passado dias inteiros tentando provar proposições numéricas extremamente simples dentro desses sistemas formais, classificando a experiência de desenvolvimento como um processo desafiador, mas excessivamente moroso quando o programador não possui treinamento acadêmico avançado em lógica formal.

"Doing proofs is actually quite fun: it's challenging, interactive, and there's a clear goal. But gosh, does it take a lot of time, especially if, like me, you don't know what you're doing."

O gargalo do projeto seL4

O impacto prático dessa sobrecarga mecânica foi documentado de maneira minuciosa no projeto do microkernel seL4, reconhecido internacionalmente como um dos marcos da verificação formal de software escrito em linguagem C. A retrospectiva oficial publicada pela equipe do seL4 revelou um dado crítico sobre o custo de produção de software formalmente verificado: mesmo após os engenheiros desenvolverem larga experiência no sistema, eles dedicaram cerca de 10 vezes mais tempo construindo e validando provas do que projetando e implementando o código-fonte em si.

A desproporção métrica no projeto do microkernel seL4 também se refletiu no volume bruto de código produzido pela equipe de desenvolvimento. A contagem final do projeto revelou a existência de mais de 20 vezes mais linhas de código dedicadas exclusivamente às provas formais do que linhas de código-fonte na linguagem C. Essa discrepância massiva fez com que a programação em linguagens com tipos dependentes ficasse restrita a um nicho extremamente reduzido da indústria de tecnologia.

"They spent about 10 times as much time proving as they did designing and implementing. They ended up with more than 20 times as many lines of proof code as they did C code."

Das ferramentas SMT aos LLMs

Tentativas anteriores de automatizar o processo de verificação formal recorreram a solucionadores do tipo SMT (Satisfiability Modulo Theories), abordagem adotada pela linguagem F*. O problema dessa arquitetura, conforme explica Langley, ocorre quando o solucionador SMT entra em um espaço de busca indeterminado, executando rotinas por horas seguidas sem dar retorno se terminará a verificação. Isso força os desenvolvedores a buscarem uma sensibilidade mística sobre o comportamento do verificador para estruturar o código apenas para agradar à ferramenta automatizada.

A virada tecnológica defendida no artigo baseia-se no princípio lógico da irrelevância da prova (proof irrelevance). Por essa regra teórica, uma vez que uma proposição matemática é confirmada como verdadeira pelo sistema, o conteúdo exato das etapas internas da demonstração torna-se irrelevante para a compilação final — apenas a garantia formal da sua existência importa. A união entre esse princípio e a capacidade de sintaxe dos modelos LLMs permite gerar as etapas intermediárias de verificação sem intervenção humana ostensiva.

No entanto, a simplificação automatizada de provas enfrenta dois desafios descritos no relatório de Langley: o conceito de "engenharia de prova" (proof engineering), cunhado pelo grupo do seL4 para indicar o esforço de reestruturar demonstrações após modificações no código original, e o consumo excessivo de memória nos verificadores de tipos (type checkers). Provas excessivamente intrincadas podem fazer o type checker esgotar a memória RAM da máquina, embora testes preliminares conduzidos pelo autor em Lean indiquem que os LLMs conseguem contornar essa limitação técnica.

Desempenho do algoritmo Zstandard

Para testar o potencial prático da linguagem Lean impulsionada por automação via LLM, Langley desenvolveu um decodificador para o algoritmo Zstandard (zstd), criado por Yann Collet com base nos estudos teóricos de ANS (Asymmetric Numeral Systems) publicados por Jarek Duda. O formato Zstandard venceu a competição do mercado para substituir o tradicional gzip como utilitário padrão de compressão, combinando o algoritmo de janela deslizante LZ77 com codificadores de entropia voltados para alta vazão no processamento de dados.

Em medições de desempenho realizadas por Langley em uma máquina de referência da Apple, aplicando compressores sobre uma amostra de 64 MiB de código-fonte do projeto Lean e da biblioteca matemática mathlib, o algoritmo lzma (utilizado no XZ/LZMA2) alcançou o maior percentual de espaço economizado, com cerca de 85%. O compressor bzip2 atingiu aproximadamente 78% de redução de espaço, o Zstandard registrou perto de 75%, enquanto o tradicional gzip salvou em torno de 71% do tamanho original do arquivo.

A grande vantagem competitiva do Zstandard transparece na métrica de taxa de transferência na descompressão (decompression throughput, medida em MiB/s em escala logarítmica). Enquanto compressores de alta taxa de redução como o lzma e o bzip2 registraram vazões lentas de aproximadamente 200 MiB/s e 100 MiB/s, respectivamente, o zstd alcançou taxas de descompressão próximas a 2000 MiB/s. O utilitário gzip rodando na versão otimizada do sistema Apple atingiu marcas entre 1000 MiB/s e 1500 MiB/s.

O funcionamento do Finite State Entropy

A documentação oficial do Zstandard está contida em uma **RFC** técnica descrita por **Langley** como extremamente concisa. O autor conta que precisou reler a **Seção 4.1** do documento técnico mais de seis vezes para compreender detalhadamente o funcionamento da codificação de entropia do formato. Ele também cita como referência fundamental a análise publicada por seu colega de trabalho **Nigel Tao**, que produziu uma explicação detalhada sobre a engenharia por trás do **zstd**.

Os compressores de entropia tradicionais, como os baseados na árvore de **Huffman**, constroem uma estrutura binária de prefixos em que os símbolos ficam nas folhas da árvore. O algoritmo de **Huffman** prova matematicamente a geração de uma árvore ótima ao selecionar repetidamente os dois símbolos de menor probabilidade e fundi-los em um novo nó. A limitação fundamental do sistema de **Huffman** é a obrigação de alocar um número inteiro de bits por símbolo, mesmo quando o cálculo teórico de entropia dado pela fórmula `-log2(p)` exige frações de bits, como **2,3 bits**.

Para superar esse gargalo sem perder velocidade, o **Zstandard** adota o **FSE** (Finite State Entropy), um sistema baseado em uma máquina de estados finitos. No **FSE**, o número total de estados da tabela é superior ao número de símbolos do fluxo de dados. Cada símbolo recebe uma fatia do espaço de estados exatamente proporcional à sua frequência estatística. Por exemplo, se um determinado símbolo possui **50%** de probabilidade de ocorrência, ele ocupará aproximadamente **50%** de todos os estados disponíveis na tabela do decodificador.

Exemplo prático de tabela FSE

Cada estado contido na tabela do **FSE** armazena três valores fundamentais: o símbolo associado àquela posição, a quantidade exata de bits que devem ser lidos da transmissão (bitstream) e um número de estado base (baseline state number). A grande inovação técnica do **FSE** consiste na alternância dinâmica da quantidade de bits lidos: para representar uma meta de **1,5 bits** por símbolo, metade dos estados associados a esse símbolo exigirá a leitura de **1 bit**, enquanto a outra metade exigirá a leitura de **2 bits**, atingindo a média fracionária exata sem cálculos de ponto flutuante pesados no processador.

As tabelas do **FSE** não são transmitidas no arquivo comprimido; elas são reconstruídas pelo decodificador através de um algoritmo padronizado na **RFC** que utiliza apenas a lista de probabilidades quantizadas dos símbolos. Embora o formato **Zstandard** exija o uso de no mínimo **32 estados** em suas tabelas reais, **Langley** demonstra o funcionamento do sistema através de uma tabela reduzida de **16 estados** (indexados de **0** a **15**) atendendo a **4 símbolos** distintos identificados como **A**, **B**, **C** e **D**.

No modelo didático de **16 estados**, o símbolo **D** é representado por apenas um estado (o estado de número **3**). Como é o único estado disponível para **D**, ele exige a leitura de **4 bits** da transmissão para conseguir alcançar qualquer um dos **16 estados** possíveis na transição seguinte. Já o símbolo **B**, que possui probabilidade de **5/16** no fluxo de dados e valor ideal de entropia calculado em `-log2(5/16) = 1,68 bits`, é distribuído em **5 estados** da tabela (posições **2**, **5**, **8**, **11** e **15**), dos quais três estados leem **2 bits** e dois estados leem **1 bit**.

A lógica de decodificação reversa

O funcionamento mecânico do **FSE** impõe uma particularidade algorítmica: o fluxo de dados comprimidos não pode ser processado na sequência direta de leitura. Como a escolha do estado inicial do estado atual depende de qual símbolo virá na sequência, a codificação no **FSE** precisa obrigatoriamente começar pelo último símbolo do fluxo e trabalhar no sentido inverso, do fim para o início.

Por conta dessa restrição de processamento, o compressor do **Zstandard** gera a saída de forma incremental, mas codifica os dados de trás para a frente. Para conseguir descompactar os dados, o decodificador escrito em **Lean** precisa mover o ponteiro de leitura diretamente para o final do bloco de memória e ler a sequência de bits em ordem reversa para desdobrar a cadeia original de bytes.

O sistema **FSE** é aplicado no **Zstandard** de forma combinada com uma estrutura tradicional do tipo **LZ77** (**Lempel–Ziv**). Enquanto o algoritmo **LZ77** identifica redundâncias entre sequências de texto ou dados binários criando referências para posições anteriores, o **FSE** é utilizado para codificar com máxima eficiência os números de deslocamento (offsets) e os comprimentos dessas repetições dentro do arquivo comprimido.

Aplicações da linguagem Lean

Durante a implementação do decodificador **Zstandard** na linguagem **Lean**, **Langley** explorou a capacidade do sistema de tipos para validar rotinas de processamento de dados. O sistema de tipos dependentes do **Lean** permite definir uma função capaz de ler exatamente **n** bytes de um fluxo contínuo e, em tempo de compilação, exigir garantias matemáticas formais de que a operação não ultrapassará os limites alocados em memória ou lerá dados fora do array.

Ao conectar a capacidade de checagem do compilador do **Lean** com a automação de provas fornecida por modelos **LLMs**, o projeto desenvolvido por **Adam Langley** demonstra que a construção de software verificado pode deixar de exigir os fatores de sobrecarga observados em marcos históricos como o **seL4**. A automação de provas abre caminho para que a implementação de algoritmos críticos de infraestrutura — como o utilitário **Zstandard**, sistemas operacionais e bibliotecas de criptografia — alcance níveis máximos de verificação de segurança mantendo a viabilidade técnica de desenvolvimento.