🤖 machine learning

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete

Este artigo demonstra que codificações posicionais não são estritamente necessárias para que os transformers alcancem a completude de Turing, uma vez que o mecanismo de janela deslizante por si só quebra a simetria de permutação e fornece informação posicional suficiente para simular computação universal.

Autores originais: Qian Li, Xinyu Mao, Shang-Hua Teng

Publicado 2026-06-02

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Qian Li, Xinyu Mao, Shang-Hua Teng

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 contar uma história ou resolver um problema de matemática. Por muito tempo, cientistas da computação acreditaram que, para fazer isso, o robô precisaria de um "caderno de endereços" especial anexado a cada palavra que lesse. Este caderno de endereços, chamado Codificação Posicional (Positional Encoding - PE), dizia ao robô exatamente onde cada palavra estava na frase (1ª, 2ª, 3ª, etc.). Sem ele, diziam, o robô ficaria confuso e não conseguiria distinguir entre "O gato perseguiu o cachorro" e "O cachorro perseguiu o gato".

Este artigo argumenta que você não precisa realmente desse caderno de endereços se o robô estiver trabalhando com um tipo específico de memória: uma janela deslizante (sliding window).

Aqui está a ideia central, dividida com algumas analogias do cotidiano:

1. A Crença Antiga: A "Foto Estática"

Pense em um modelo Transformer padrão (o tipo por trás de muitos chatbots de IA) como um fotógrafo tirando uma foto de uma multidão inteira. Se você apenas entregar ao fotógrafo um monte de rostos de pessoas sem dizer quem está onde, eles não conseguirão distinguir entre uma fila de pessoas e um amontoado aleatório. Eles precisam de uma etiqueta na testa de cada pessoa (Codificação Posicional) para saber a ordem.

2. A Nova Descoberta: O "Ônibus em Movimento"

Os autores perceberam que, quando a IA realiza um raciocínio complexo, passo a passo (como resolver um problema de matemática longo), ela não olha para todo o histórico de uma só vez. Em vez disso, ela usa uma janela deslizante.

Imagine que a IA está sentada em um ônibus com uma janela que mostra apenas as últimas 10 pessoas que passaram por ela.

A Visão Antiga: Se você olhar apenas para as 10 pessoas que estão atualmente na janela, não consegue dizer quem entrou primeiro ou quem saiu por último. É apenas um grupo de 10 pessoas.
A Nova Visão: Os autores notaram que o ônibus está se movendo.
- A cada segundo, uma nova pessoa entra no ônibus (entra na janela).
- A cada segundo, a pessoa mais antiga cai pela parte de trás (sai da janela).

Mesmo que a IA não consiga ver os "endereços de rua" das pessoas dentro do ônibus, o ato do ônibus se mover cria um padrão. A IA pode ver: "Oh, uma nova pessoa acabou de entrar, e eu sei quem acabou de sair porque o grupo total mudou".

3. O "Histograma Mágico" (O Modelo HIST)

Para provar isso, os autores inventaram um robô teórico chamado modelo HIST.

Este robô é cego à ordem. Ele não consegue dizer "A camisa vermelha é a 3ª".
Ele vê apenas uma contagem (um histograma). Ele sabe: "Há 3 camisas vermelhas, 2 azuis e 1 verde no grupo agora".
Ele também possui uma pequena memória (um "estado de controle") para lembrar das últimas coisas que aconteceram.

O truque mágico é este: Ao comparar a contagem antes de uma nova pessoa entrar e a contagem depois, o robô consegue descobrir exatamente quem acabou de sair do ônibus, mesmo sem ver a etiqueta de identificação deles.

Antes: 3 Vermelhas, 2 Azuis.
Nova pessoa entra (Azul).
Depois: 3 Vermelhas, 3 Azuis.
Espere, o tamanho da janela é fixo! Se uma nova Azul entra, uma Vermelha deve ter saído.
Conclusão: O robô sabe que uma camisa Vermelha acabou de cair pela parte de trás, mesmo sem nunca ter visto a etiqueta de posição da camisa Vermelha.

4. O Grande Resultado: Completude de Turing

Na ciência da computação, ser "Turing Completo" significa que uma máquina pode, teoricamente, resolver qualquer problema que um computador possa resolver, dado tempo e memória suficientes.

Crença anterior: Os Transformers precisavam de Codificações Posicionais para serem Turing Completos.
A prova deste artigo: Um Transformer com uma janela deslizante não precisa de Codificações Posicionais para ser Turing Completo. O próprio movimento da janela fornece informação sequencial suficiente para simular um computador universal.

Os autores construíram uma ponte matemática mostrando que:

Uma máquina que apenas conta tipos de tokens (o modelo HIST) pode simular um computador universal (especificamente, uma "Máquina de Post", que é como um computador com uma fila).
Um Transformer padrão (sem Codificações Posicionais) pode imitar perfeitamente essa máquina de contagem.

5. O Que Isso Significa (e o Que Não Significa)

As Boas Notícias:
Acontece que o "movimento" de processar dados passo a passo é poderoso o suficiente para criar ordem. Você não precisa marcar manualmente cada palavra com um número para obter computação universal. A própria ação de "deslizar" quebra a simetria por si só.

As Ressalvas (O que o artigo não diz):

Não é sobre velocidade: Esta é uma prova de possibilidade, não de eficiência. Só porque um robô pode resolver um problema sem o caderno de endereços não significa que ele o fará de forma rápida ou fácil na vida real.
Ele não lê posições exatas: O robô ainda não consegue dizer "A 5ª palavra é 'maçã'". Ele só consegue deduzir "Alguém saiu do grupo". É um truque inteligente de dedução, não um mapa direto.
Requer um pouco de mágica matemática: A prova depende de o robô ser capaz de contar de forma muito precisa (verificações de paridade) para saber exatamente quem saiu da janela. Na vida real, isso pode exigir matemática de altíssima precisão, um detalhe técnico que os autores reconhecem.

Resumo

Pense na Codificação Posicional como uma coordenada de GPS para cada palavra. Este artigo diz: "Você não precisa de um GPS se estiver caminhando por uma rua e observando as pessoas entrarem e saírem de uma loja. O fluxo de pessoas entrando e saindo conta a história, mesmo que você não saiba os endereços de rua exatos delas."

A própria janela deslizante é o "GPS" para a IA, tornando desnecessário o caderno de endereços externo para que a máquina seja capaz de computação universal.

Resumo Técnico: Repensando o Papel da Codificação Posicional em Transformers de Janela Deslizante

1. Definição do Problema

A codificação posicional (PE - Positional Encoding) tem sido considerada, há muito tempo, um componente necessário para arquiteturas Transformer processarem sequências ordenadas. A intuição predominante é que, sem informações posicionais explícitas, o mecanismo de autoatenção é invariante à permutação, tornando o modelo incapaz de distinguir entre diferentes ordenações dos mesmos tokens de contexto. Essa premissa fundamenta resultados teóricos anteriores que estabelecem a completude de Turing de Transformers com raciocínio de Cadeia de Pensamento (Chain-of-Thought - CoT), os quais dependem fortemente de PE para simular computação sequencial.

No entanto, esses resultados de universalidade frequentemente assumem que o modelo atende a todo o histórico. Em cenários práticos de raciocínio de longo formato, os modelos operam com uma janela de contexto deslizante finita. À medida que a janela desliza para frente, tokens entram e saem, introduzindo uma assimetria temporal. A questão central abordada por este artigo é: As codificações posicionais são verdadeiramente necessárias para a computação universal em Transformers de janela deslizante? Os autores investigam se o próprio mecanismo de janela deslizante fornece estrutura sequencial suficiente para alcançar a completude de Turing sem PE explícita.

2. Metodologia e Estrutura

O Modelo HIST

Para isolar o poder computacional derivado da janela deslizante, os autores introduzem um modelo autoregressivo abstrato chamado modelo HIST.

Definição: Uma máquina HIST gera o próximo token baseando-se apenas em um estado de controle finito e no histograma de contagem de tokens da janela atual (o vetor de frequências de tokens indexado pelo alfabeto).
Restrição: O modelo não tem acesso às posições específicas de tokens individuais dentro da janela; sua função de transição é invariante à permutação em relação ao conteúdo da janela.
Variante Parity-HIST: Uma versão restrita onde a função de transição depende apenas da paridade do histograma (ou seja, se a contagem de cada tipo de token é par ou ímpar).

Estratégia Teórica

A prova de completude de Turing procede em duas etapas principais:

Simulação de Máquinas de Post: Os autores provem que uma máquina Parity-HIST pode simular uma Máquina de Post (um autômato baseado em fila conhecido por ser Turing completo).
- Insight Chave: Embora a máquina Parity-HIST observe apenas a paridade da janela, a natureza FIFO (First-In-First-Out / Primeiro a Entrar, Primeiro a Sair) da janela deslizante permite que ela infira o token que acabou de sair da janela. Ao comparar o histograma de paridade antes e depois de uma atualização da janela (e utilizando o estado de controle finito para armazenar o token recém-entrado), a máquina pode deduzir a identidade do token "descartado" na frente. Isso simula efetivamente uma operação de dequeue de uma fila sem endereçamento posicional explícito.
Simulação de Parity-HIST com Transformers: Os autores constroem um Transformer de janela deslizante sem PE que pode simular o modelo Parity-HIST.
- Mecanismo: O Transformer utiliza um alfabeto de tamanho constante e um bit de atualização adaptativo. Para recuperar as contagens brutas de tokens (e, portanto, sua paridade) a partir do mecanismo de atenção, a construção introduz um símbolo marcador (#) especial.
- Dinâmica de Atenção: Ao utilizar atenção uniforme (alcançada via matrizes de Query e Key zeradas), os pesos de atenção tornam-se $1/m$ (onde $m$ é o tamanho da janela). A presença de um único marcador permite que o modelo infira o tamanho da janela $m$ e converta as massas de atenção normalizadas de volta em contagens inteiras brutas.
- Extração de Paridade: Com precisão aritmética suficiente (logarítmica em relação ao tamanho da janela), a camada MLP computa a paridade das contagens de tokens, replicando efetivamente a função de transição Parity-HIST.

3. Principais Contribuições e Resultados

Teorema 1 (Alto Nível): O modelo Parity-HIST é Turing completo. Os autores demonstram que a evolução temporal de uma janela deslizante, combinada com um resumo de permutação invariante (paridade do histograma) e um estado finito, é suficiente para simular máquinas de Post.
Teorema 2 (Alto Nível): Toda máquina Parity-HIST pode ser simulada por um Transformer de janela deslizante sem codificações posicionais.
Corolário: Transformers de janela deslizante sem PE são Turing completos.
Detalhes da Construção:
- A construção utiliza um vocabulário de tamanho constante e um número constante de parâmetros treináveis.
- Emprega um mecanismo de atualização de janela adaptativo onde os tokens carregam um bit de controle para deslizar a janela (padrão) ou expandi-la (retendo o token mais antigo), evitando a necessidade de pré-especificar um tamanho de janela de pior caso.
- A simulação requer precisão logarítmica ( $O(\log S)$ ) para operações aritméticas para computar paridades, onde $S$ é o comprimento máximo da janela.

4. Significância e Alegações

O artigo afirma separar fundamentalmente os conceitos de codificação posicional e estrutura sequencial no contexto de computação universal.

PE não é Indispensável: Os resultados demonstram que as codificações posicionais explícitas não são um pré-requisito para que os Transformers realizem computação universal. A própria "movimentação do tipo FIFO" da janela deslizante quebra a simetria de permutação e fornece o sinal sequencial necessário.
Refinando a Universalidade: O trabalho esclarece que, embora a computação universal exija alguma fonte de estrutura sequencial, essa estrutura não precisa ser fornecida por um sistema de endereçamento posicional externo. Ela pode emergir naturalmente da dinâmica temporal do processo de geração.
Distinção de Trabalhos Anteriores: Diferente de provas de universalidade anteriores que usam PE para armazenar estruturas de circuitos ou identificar tokens específicos, esta construção roteia a simulação através de um modelo de resumo de janela invariante à permutação.
Limitações e Escopo:
- A construção é um resultado de expressividade, não uma afirmação sobre aprendibilidade ou eficiência prática. Não implica que Transformers padrão aprenderão esses algoritmos naturalmente.
- O modelo não recupera as posições exatas dos tokens dentro da janela; ele apenas infere a identidade dos tokens que entram e saem.
- A construção depende de um primitivo de paridade que exige precisão logarítmica, o qual é isolado como um requisito numérico em vez de uma limitação arquitetônica fundamental da redução.

Em resumo, o artigo estabelece que o mecanismo de janela deslizante sozinho, mesmo na ausência de codificações posicionais, confere aos Transformers a capacidade de computação universal ao alavancar a assimetria temporal de entrada e saída de tokens.