🔬 condensed matter

Learning Pseudorandom Numbers with Transformers: Permuted Congruential Generators, Curricula, and Interpretability

Este artigo demonstra que modelos Transformer podem aprender e prever sequências de Geradores Congruenciais Permutados (PCGs) complexos por meio de aprendizagem por currículo e pela descoberta de representações bit a bit rotacionalmente invariantes, revelando uma lei de escala onde o comprimento de contexto necessário cresce como a raiz quadrada do módulo.

Autores originais: Tao Tao, Maissam Barkeshli

Publicado 2026-07-17

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Tao Tao, Maissam Barkeshli

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando ensinar um robô a prever o próximo número em um truque de mágica. Você mostra a ele uma sequência como 3, 7, 15, 31, e ele tem que adivinhar o que vem a seguir. No mundo real, os computadores usam receitas especiais chamadas "Geradores de Números Pseudoaleatórios" (PRNGs) para criar números que parecem completamente aleatórios para nós, como o embaralhamento de um baralho ou a estática de uma TV antiga. Mas, para o computador, esses números não são nada aleatórios; eles seguem uma regra matemática rigorosa e oculta. Se você souber a regra e o número inicial, pode prever todo o futuro da sequência perfeitamente.

Por muito tempo, cientistas se perguntaram: a IA moderna, especificamente um tipo de modelo chamado "Transformer" (o mesmo tipo de cérebro por trás de muitos chatbots e geradores de imagem), consegue descobrir essas regras ocultas apenas olhando para exemplos? É como perguntar se um aluno consegue aprender o código secreto de uma fechadura apenas observando alguém abri-la algumas vezes, sem nunca ter sido informado sobre como a fechadura funciona. Isso é algo grandioso, porque esses geradores de números são a espinha dorsal da segurança de computadores. Se a IA puder quebrá-los com muita facilidade, pode significar que nossas fechaduras digitais não são tão seguras quanto pensamos. Mas se a IA não conseguir quebrá-los, isso nos diz algo profundo sobre como esses modelos aprendem padrões e onde residem seus limites.

A História do Artigo: Quebrando o Código com um Toque Especial

Neste artigo, os autores propõem um desafio para os Transformers usando uma família específica e difícil de geradores de números chamada "Geradores Congruenciais Permutados" (PCGs). Pense em um gerador de números padrão como uma máquina simples que soma e multiplica números para obter o próximo. Um PCG é essa mesma máquina, mas com um toque: antes de mostrar o resultado, ele embaralha os bits (os minúsculos 0s e 1s que compõem o número) usando uma série de deslocamentos, inversões e rotações. É como pegar uma mensagem secreta, escrevê-la e depois embaralhar as letras para que pareça um amontoado de caracteres sem sentido, embora a mensagem original fosse perfeitamente lógica.

Os pesquisadores descobriram que os Transformers são surpreendentemente bons nisso. Mesmo quando o computador vê apenas um pequeno pedaço embaralhado da saída — às vezes apenas um único bit, como um simples "sim" ou "não" — o modelo ainda consegue prever o próximo número com alta precisão. É como se o robô estivesse olhando para um único pixel de uma imagem embaralhada e, de alguma forma, soubesse exatamente como é a imagem inteira. Os modelos aprenderam a fazer isso sem serem informados sobre as regras; eles simplesmente descobriram o padrão a partir dos exemplos fornecidos.

No entanto, há uma pegadinha. Quanto mais difícil o quebra-cabeça, mais ajuda o robô precisa. Os autores descobriram uma "lei de escala": conforme os números ficam maiores (especificamente, conforme o módulo, ou o tamanho do conjunto de números, cresce), o modelo precisa ver mais exemplos em sequência para resolver o enigma. Se os números forem pequenos, o modelo precisa ver cerca de 128 exemplos. Se os números forem enormes (como $2^{22}$ ), o modelo precisa de aproximadamente $\sqrt{m}$ exemplos, o que significa que o comprimento do contexto tem que crescer significativamente. É como tentar resolver um quebra-cabeça de peças: se as peças são minúsculas, você precisa segurar muitas delas na mão para enxergar a imagem.

A descoberta mais empolgante foi sobre como o modelo aprende. Quando os pesquisadores tentaram treinar o modelo diretamente nos quebra-cabeças mais difíceis e maiores, ele ficou travado. O modelo ficava encarando os dados por um longo tempo, sem fazer quase nenhum progresso, como um aluno encarando um problema de matemática que não entende. Mas quando usaram um "currículo" — uma estratégia de ensino onde começavam o modelo com quebra-cabeças fáceis e pequenos e introduziam gradualmente os mais difíceis — o modelo de repente conseguiu. Foi como se o modelo precisasse aprender a andar antes de conseguir correr. Ao começar pequeno, o modelo aprendeu a "gramática" básica da geração de números e, então, pôde aplicar esse conhecimento aos quebra-cabeças gigantes e complexos.

Os autores também espiaram dentro do "cérebro" do modelo (suas representações internas de dados) e descobriram algo fascinante. O modelo não apenas memorizou os números; ele os organizou com base em sua estrutura binária. Ele agrupou números que tinham padrões de zeros e uns semelhantes, mesmo que esses números parecessem totalmente diferentes na superfície. Parece que o modelo descobriu que as regras de "embaralhamento" usadas pelos geradores tratam certos padrões de bits como sendo iguais, e ele aprendeu a respeitar essas regras. Isso sugere que o modelo não está apenas adivinhando; ele está construindo um mapa mental das simetrias matemáticas ocultas.

Em resumo, o artigo mostra que os Transformers podem aprender a prever sequências numéricas complexas e embaralhadas, mesmo quando a informação é drasticamente reduzida. Mas eles precisam do caminho de treinamento correto: começando pequeno e evoluindo. Embora possam superar alguns métodos de invasão antigos, eles ainda encontram um limite quando os números ficam grandes demais sem esse currículo de apoio. Isso nos diz que, embora a IA esteja ficando melhor em encontrar padrões ocultos, ela ainda depende de uma forma estruturada de aprendizado, muito parecida com um estudante humano, para enfrentar os mistérios matemáticos mais difíceis.

Resumo Técnico: Aprendendo Números Pseudorrandômicos com Transformers

Declaração do Problema

O artigo investiga a capacidade de modelos Transformer de aprender e prever sequências geradas por Geradores de Permutação Congruencial (PCGs - Permuted Congruential Generators), uma família amplamente utilizada de geradores de números pseudorrandômicos (PRNGs). Embora os Transformers tenham demonstrado sucesso no aprendizado em contexto (ICL - in-context learning) para várias tarefas algorítmicas, questões fundamentais permanecem sobre sua capacidade de descobrir padrões determinísticos ocultos dentro de dados projetados para passar em testes de aleatoriedade estatística.

Os PCGs apresentam um desafio significativamente mais difícil do que os Geradores Congruenciais Lineares (LCGs). Enquanto os LCGs seguem uma recorrência linear simples ( $s_i = (a s_{i-1} + c) \mod m$ ), os PCGs aplicam uma função complexa $f$ ao estado oculto $s_i$ antes de produzir a saída $x_i$ . Essa função envolve deslocamentos de bits (bitwise shifts), XORs, rotações e truncamentos. Essas operações são projetadas para obscurecer a estrutura linear subjacente, tornando os PCGs resistentes a ataques algébricos clássicos que assumem o conhecimento do módulo e do multiplicador. Os autores visam determinar se os Transformers podem descobrir essas relações de recorrência ocultas e estruturas de permutação sem o conhecimento explícito dos parâmetros do gerador, e compreender os mecanismos e limitações de tal aprendizado.

Metodologia

Configuração Experimental

O estudo utiliza um benchmark controlado usando várias variantes de PCG (XSLRR, XSHRR, XSHRS) e um LCG Truncado (TLCG).

Geradores: O estado interno $s_i$ evolui via um LCG, e a saída $x_i = f(s_i)$ é derivada através de permutações específicas. Os autores variam o módulo $m$ (de $2^{14}$ a $2^{22}$ ) e o tamanho da saída (por exemplo, saídas de 8 bits a partir de estados de 16 bits).
Conjuntos de Dados: Dois cenários são empregados:
1. Separado: Treinamento e teste em um único tipo de gerador.
2. Combinado: Treinamento e teste em uma mistura de todos os tipos de geradores, exigindo que o modelo distinga entre diferentes regras de permutação.
- Os conjuntos de dados consistem em sequências geradas com multiplicadores ( $a$ ) e incrementos ( $c$ ) não vistos para testar a generalização.
Arquitetura do Modelo: Transformers do tipo decodificador apenas (estilo GPT) com Embeddings Posicionais Rotativos (RoPE). Os experimentos escalam a profundidade do modelo (1–6 camadas), largura (cabeças de atenção) e tamanho do vocabulário (baseado na largura de bits da saída).
Treinamento: Os modelos são treinados de forma autorregressiva para prever o próximo token usando perda de entropia cruzada (cross-entropy loss). O treinamento envolve até 100 mil passos com tamanhos de lote (batch sizes) de 512.

Técnicas Principais

Aprendizado por Currículo (Curriculum Learning): Para módulos grandes ( $m \ge 2^{20}$ ), o treinamento direto frequentemente falha, levando a uma estagnação prolongada. Os autores introduzem uma estratégia de currículo onde dados de módulos menores são misturados ao conjunto de dados de módulo maior. A razão de mistura $\alpha$ decai exponencialmente ao longo dos passos de treinamento.
Inicialização Pré-treinada: Modelos treinados em módulos menores são usados para inicializar os pesos para tarefas de módulos maiores, transferindo as estruturas de embedding aprendidas.
Análise de Interpretabilidade: Os autores utilizam Análise de Componentes Principais (PCA) nos embeddings dos tokens e analisam os padrões de atenção para entender como o modelo representa os dados de entrada.

Principais Contribuições e Resultados

1. Predição Bem-sucedida em Contexto

Os Transformers podem realizar a predição em contexto com sucesso em sequências PCG de múltiplas variantes, generalizando para parâmetros não vistos ( $a, c$ ).

Desempenho: Os modelos alcançam >90% de precisão em diversas variantes de PCG após observar aproximadamente 512 elementos em contexto.
Robustez: A predição permanece robusta mesmo quando a saída é fortemente truncada (por exemplo, retendo apenas o bit mais alto do estado), onde o modelo supera significativamente o palpite aleatório.
Generalização: Esta capacidade excede os ataques clássicos publicados, que tipicamente requerem conhecimento prévio do módulo e do multiplicador.

2. Leis de Escala (Scaling Laws)

O artigo identifica uma lei de escala específica em relação ao comprimento do contexto necessário para uma predição bem-sucedida:

Comprimento de Contexto vs. Módulo: O número de elementos de sequência em contexto necessários para exceder 90% de precisão escala como $\sqrt{m}$ . Isso é mais íngreme do que a escala de $m^{0.25}$ observada para LCGs, refletindo a obscuridade da informação introduzida pelas permutações do PCG.
Tamanho do Modelo: Modelos maiores (aumento de profundidade e largura) requerem menos elementos observados para atingir a mesma precisão, sugerindo que a escala permite um desenvolvimento de estratégia mais eficiente.

3. Necessidade de Aprendizado por Currículo

Para módulos grandes ( $m \ge 2^{20}$ ), o treinamento direto dentro de orçamentos de computação fixos resulta em fases de estagnação estendidas com redução mínima de perda.

Eficácia do Currículo: Incorporar dados de módulos menores (como misturar dados de $m=2^{16}$ em um treinamento de $m=2^{18}$ ) elimina a fase de estagnação, amplia a faixa de taxas de aprendizado estáveis e produz um desempenho final substancialmente mais forte.
Pré-treinamento: Inicializar com pesos de um modelo de módulo menor atua como uma forma discreta de currículo, permitindo que o modelo pule a fase inicial de estagnação e converja mais rápido.

4. Interpretabilidade e Representação

A análise das representações aprendidas revela insights estruturais inéditos:

Agrupamento por Bits (Bitwise Clustering): O PCA da matriz de embedding mostra que os tokens se agrupam espontaneamente com base em estruturas rotacionalmente invariantes de bits, especificamente o número e o arranjo de sequências contíguas de zeros (ex: $Z(1)$ , $Z(2,1)$ ).
Transferibilidade: Esta estrutura de agrupamento persiste através de diferentes módulos, explicando por que a inicialização pré-treinada é eficaz; o modelo internaliza as invariâncias inerentes ao gerador.
Separação de Geradores: Em configurações de treinamento combinado, as ativações intermediárias do modelo (especificamente no MLP da terceira camada) diferenciam espontaneamente entre distintas variantes de PRNG, mesmo sem supervisão explícita sobre a identidade do gerador.

Significância e Alegações

O artigo afirma demonstrar que os Transformers possuem uma habilidade notável de descobrir padrões determinísticos ocultos em dados projetados para parecerem aleatórios, superando as capacidades de ataques algébricos clássicos que dependem do conhecimento explícito dos parâmetros do gerador.

O trabalho destaca que, embora os Transformers possam aprender estruturas de PRNG complexas, eles enfrentam restrições de escala distintas. A exigência de que o comprimento do contexto cresça como $\sqrt{m}$ e a necessidade de aprendizado por currículo para módulos grandes sugerem que, embora esses modelos possam generalizar para regimes não vistos, eles ainda não são capazes de "quebrar" geradores arbitrariamente grandes ou complexos sem estratégias de treinamento específicas.

A identificação do agrupamento rotacionalmente invariante no espaço de embedding fornece uma explicação mecanística de como esses modelos generalizam: eles aprendem a representar entradas com base nas simetrias do algoritmo subjacente, em vez de memorizar sequências específicas. Isso oferece uma nova perspectiva sobre como as redes neurais processam aritmética modular e tarefas baseadas em permutação, preenchendo a lacuna entre o raciocínio algorítmico e o reconhecimento de padrões estatísticos.

Os autores concluem que, embora os Transformers possam se aproximar da predição de PRNGs não criptográficos de forma eficaz, um relato mecanístico completo da solução e a exploração de sua capacidade de atacar geradores criptograficamente seguros permanecem direções importantes para trabalhos futuros.