🤖 machine learning

Indexing: the Beginning and the End

Este artigo introduz o conceito de complexidade causal para demonstrar que arquiteturas de aprendizado profundo mascaradas, como RNNs e transformers de atenção linear, são fundamentalmente limitadas na resolução da primitiva de indexação quando o índice aparece ao final da entrada, ao passo que transformers com softmax e com atenção linear não mascarada podem resolvê-la eficientemente, uma separação teórica que é corroborada por experimentos empíricos.

Autores originais: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

Publicado 2026-07-27

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

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ê esteja tentando construir um robô superinteligente que possa ler uma história e responder perguntas sobre ela. Este é o mundo da inteligência artificial, especificamente um campo chamado "aprendizado profundo" (deep learning), onde os computadores aprendem padrões observando quantidades massivas de dados. Por muito tempo, os robôs mais populares para este trabalho foram chamados de "Transformers". Eles são como bibliotecários brilhantes que podem folhear instantaneamente um livro inteiro para encontrar um fato específico. Mas há um problema: conforme o livro fica mais longo, o bibliotecário fica cada vez mais lento, e construí-los exige muita energia e dinheiro.

Para resolver isso, cientistas inventaram novos tipos de robôs, como os "RNNs" (que leem histórias palavra por palavra, como um humano) e os "SSMs" (que tentam ler a história inteira de uma vez, mas de uma forma muito simplificada). A grande questão que todos estão fazendo é: "Estes novos robôs, mais rápidos, são tão inteligentes quanto os antigos, lentos, ou possuem pontos cegos ocultos?" Para descobrir a resposta, os pesquisadores não apenas adivinham; eles dão aos robôs pequenos e complicados enigmas para resolver. Esses enigmas são como o "dever de casa de matemática" do mundo da IA. Se um robô não consegue resolver um problema simples de matemática, isso prova que o cérebro do robô tem um limite fundamental, não importa o quanto você o treine.

Este artigo, intitulado "Indexing: the Beginning and the End", utiliza um enigma muito específico e simples chamado "Indexing" (Indexação) e o usa para testar os cérebros dessas diferentes arquiteturas de robôs. O enigma é enganosamente fácil: imagine que você tem uma lista de $n$ bits (uma sequência de 0s e 1s) e um número $i$ que indica qual bit escolher. O objetivo é simplesmente exibir o valor desse bit específico. É como se lhe entregassem uma fileira de 64 interruptores de luz e um número, digamos "17", e lhe perguntassem: "O interruptor 17 está ligado ou desligado?"

Os pesquisadores, Alexander Kozachinskiy, Vicente Opazo e Felipe Urrutia, descobriram que a ordem em que o robô vê a informação muda tudo. Eles descobriram que alguns robôs são incrivelmente rápidos nesta tarefa, enquanto outros atingem uma barreira que simplesmente não conseguem ultrapassar, não importa quantos níveis de "pensamento" possuam.

Aqui está a reviravolta: o artigo prova que, para certos tipos de robôs (especificamente aqueles que processam informações de uma forma "causal" ou "mascarada", o que significa que eles só podem olhar para o que veio antes deles e não para o que vem depois), resolver este enigma é matematicamente impossível se a lista de bits for longa e o número do índice aparecer no final. É como se você entregasse a um robô uma longa fila de pessoas, pedisse para ele memorizar o rosto de cada uma e, no final, sussurrasse: "Diga-me o nome da pessoa número 42". O artigo mostra que robôs como RNNs, Mamba e Transformers de atenção linear mascarada possuem um "gargalo de memória". Eles não conseguem comprimir toda essa informação em um pacote pequeno o suficiente para lembrar o bit específico quando o índice finalmente chega. Os autores provaram isso usando matemática rigorosa que permanece verdadeira mesmo se os robôs tiverem precisão infinita (ou seja, não se confundem com erros de arredondamento).

No entanto, a história muda se você inverter o roteiro. Se o número do índice aparecer no início da lista (dizendo ao robô "Lembre-se da pessoa 42" antes mesmo de você mostrar a fila de pessoas), os RNNs tornam-se os super-heróis. Eles podem resolver isso em um único passo, enquanto os outros robôs (incluindo os famosos Transformers) precisam de pelo menos dois passos para descobrir.

Os autores não fizeram apenas a matemática; eles também realizaram experimentos com modelos reais. Eles treinaram esses robôs em listas de até 64 bits. Os resultados foram uma correspondência perfeita com sua teoria. Os robôs que a matemática dizia que deveriam falhar (os causais tentando encontrar o bit no final de uma lista longa) consistentemente desistiam conforme as listas ficavam mais longas. Enquanto isso, os robôs que a matemática dizia que teriam sucesso aprenderam a tarefa facilmente.

Então, qual é a conclusão? Não é que um robô seja "melhor" que o outro em todos os aspectos. Em vez disso, o artigo revela que diferentes arquiteturas possuem diferentes "superpoderes" e diferentes "kriptonitas". A maneira como um robô processa a informação — se ele lê da esquerda para a direita, olha para tudo de uma vez ou tenta resumir o passado — determina exatamente quais enigmas ele pode resolver e quais o deixarão travado para sempre. Isso ajuda os cientistas a entender os limites fundamentais da IA, garantindo que, ao construirmos a próxima geração de máquinas inteligentes, saibamos exatamente o que elas podem e o que não podem fazer.

Resumo Técnico: Indexação: O Início e o Fim

Declaração do Problema

Este artigo investiga a expressividade e os gargalos de informação de arquiteturas modernas de aprendizado profundo — especificamente Redes Neurais Recorrentes (RNNs), Transformers de Softmax, Transformers de Atenção Linear e Modelos de Espaço de Estados (SSMs) — através da lente do primitivo de indexação.

A tarefa de indexação é definida da seguinte forma: dada uma sequência de $n$ bits $\sigma_1, \dots, \sigma_n \in \{0, 1\}$ e um índice $i \in \{1, \dots, n\}$ , o modelo deve produzir o valor do $i$ -ésimo bit, $\sigma_i$ . Os autores analisam duas variações específicas desta tarefa para sondar diferentes limitações arquiteturais:

Indexação à Direita (RHI - Right-Hand Indexing): O índice $i$ aparece no final da sequência de entrada (após os bits). O modelo deve recuperar $\sigma_i$ com base na informação processada dos $n$ bits precedentes.
Indexação à Esquerda (LHI - Left-Hand Indexing): O índice $i$ aparece no início da sequência de entrada (antes dos bits). O modelo deve carregar a informação do índice através da sequência para recuperar $\sigma_i$ ao final.

O estudo foca em arquiteturas "pequenas", definidas como tendo $o(1)$ parâmetros (número constante de parâmetros em relação ao comprimento da sequência $n$ ) e potencialmente aritmética de precisão infinita de números reais.

Metodologia

Os autores utilizam um framework teórico baseado em complexidade causal e dimensão VC para derivar limites inferiores incondicionais.

Complexidade Causal

Para arquiteturas causais (mascaradas), onde a saída na posição $k$ depende apenas das entradas $1$ através $k$ , os autores introduzem a noção de complexidade causal. Isso mede a dimensão mínima $s$ para a qual o histórico de entradas ( $x_1, \dots, x_{k-1}$ ) pode ser comprimido (via uma função de "impressão digital") de tal forma que a $k$ -ésima saída possa ser computada a partir desta representação comprimida e da entrada atual $x_k$ com baixa complexidade aritmética.

Insight Chave: Se uma arquitetura possui baixa complexidade causal (especificamente $o(1)$ ), ela não consegue comprimir o histórico necessário para resolver tarefas que exigem a recuperação de informações passadas específicas quando essa informação não está imediatamente acessível.

Ferramentas Teóricas

Dimensão VC: Os autores adaptam a técnica de Kozachinskiy et al. (2025) para mostrar que, se um modelo resolve a tarefa de indexação, a classe de conceitos associada deve ter uma dimensão VC de pelo menos $n$ .
Complexidade Aritmética: Eles utilizam a complexidade aritmética das funções computadas pelas camadas (incluindo exponenciais, operações aritméticas e condicionais) para limitar a dimensão VC.
Limites Incondicionais: Diferente de trabalhos anteriores que dependiam de suposições de precisão limitada, estes resultados sustentam-se mesmo para modelos que utilizam números reais de precisão infinita.

Validação Experimental

Os achados teóricos são validados através de experimentos em tarefas de indexação binária para comprimentos de sequência $n \in \{8, 16, 32, 64\}$ . Os autores comparam:

Variantes totais e causais de Transformers de Softmax e de Atenção Linear.
RNNs (especificamente GRUs).
SSMs (especificamente Mamba).
Todos os modelos são treinados do zero com hiperparâmetros fixos para observar a dinâmica de aprendizado conforme $n$ aumenta.

Contribuições Principais e Resultados

1. Indexação à Direita (Índice no Final)

Neste cenário, o modelo processa todos os $n$ bits antes de ver o índice. Para resolver a tarefa, o modelo deve comprimir toda a string de $n$ bits em um estado pequeno o suficiente para ser processado pelo token do índice.

Impossibilidade para Arquiteturas de Baixa Complexidade Causal: Os autores provam que nenhum número constante ( $O(1)$ $O (1)$ ) de camadas com $o(1)$ $o (1)$ de complexidade causal pode resolver a RHI.
- Arquiteturas Afetadas: Pequenas RNNs, SSMs (ex: Mamba) e Transformers de Atenção Linear causais possuem $o(1)$ de complexidade causal. Consequentemente, eles não podem resolver a RHI em um número constante de camadas, mesmo com precisão infinita.
- Confirmação Experimental: Modelos nesta categoria (Linear-Attention causal de 1 e múltiplas camadas, GRUs, Mamba) falham consistentemente em aprender a RHI conforme $n$ cresce, atingindo 0% de sucesso em $n=64$ .
Possibilidade para Arquiteturas de Alta Complexidade Causal:
- Transformers de Softmax: Uma única camada com $O(1)$ parâmetros pode resolver a RHI. Isso é atribuído à sua alta complexidade causal (via o mecanismo de softmax que permite atenção global).
- Atenção Linear Total: Duas camadas com $O(1)$ parâmetros podem resolver a RHI.
- Confirmação Experimental: Estas configurações aprendem a tarefa facilmente, com altas taxas de sucesso mesmo em $n=64$ .

2. Indexação à Esquerda (Índice no Início)

Neste cenário, o índice é processado primeiro e deve ser carregado através da sequência até a posição do bit relevante.

Dominância das RNNs: Pequenas RNNs podem resolver a LHI em uma única camada com $O(1)$ parâmetros. Elas mantêm naturalmente um estado oculto que pode carregar o índice $i$ e atualizar uma coordenada específica quando o $i$ -ésimo bit é encontrado.
Limitações de Outras Arquiteturas:
- SSMs e Atenção Linear: Nem SSMs de 1 camada, nem Atenção Linear de 1 camada (mascarada ou total) conseguem resolver a LHI com $o(1)$ parâmetros. A linearidade das atualizações de SSM impede que eles escrevam seletivamente o valor do bit em uma posição específica determinada pelo índice sem misturar a informação de uma forma que impeça a recuperação.
- Transformers de Softmax: Transformers de Softmax de 1 camada também falham na LHI com $o(1)$ parâmetros.
Resolução com Profundidade: Todas as arquiteturas (incluindo SSMs, Atenção Linear e Transformers de Softmax) podem resolver a LHI se receberem 2 camadas com $O(1)$ parâmetros. A primeira camada propaga o índice e a segunda pode recuperar o bit.
Confirmação Experimental: GRUs de 1 camada têm sucesso em todos os comprimentos. Modelos Mamba e de Atenção Linear de 1 camada falham para $n \ge 16$ . Versões de 2 camadas de todas as arquiteturas têm sucesso.

Tabela de Resumo de Camadas Mínimas Requeridas

Arquitetura	Indexação à Esquerda (LHI)	Indexação à Direita (RHI)
Softmax Total	2	1
Softmax Causal	2	1
Atenção Linear Total	2	2
Atenção Linear Causal	2	$\omega(1)$ (Impossível)
SSM (ex: Mamba)	2	$\omega(1)$ (Impossível)
RNN	1	$\omega(1)$ (Impossível)

(Nota: $\omega(1)$ indica que o número de camadas necessárias não é limitado por uma constante; isto é, cresce com $n$ .)

Significância e Alegações

O artigo afirma fornecer os primeiros limites inferiores de precisão infinita e múltiplas camadas para uma classe de arquiteturas com baixa complexidade causal, incluindo SSMs, RNNs e transformers de atenção linear mascarados.

Separação Arquitetural: O primitivo de indexação revela uma separação fundamental entre as arquiteturas. Enquanto Transformers de Softmax e modelos de Atenção Linear total podem resolver a RHI eficientemente, variantes mascaradas e SSMs não conseguem, destacando o papel específico dos mecanismos de atenção global para superar gargalos de informação.
Papel da Linearidade: Os resultados sugerem que as regras de atualização lineares dos SSMs, frequentemente elogiadas por sua eficiência, tornam-se um passivo em tarefas de LHI, onde a escrita seletiva não linear é necessária em um único passo.
Alinhamento Teoria-Prática: Os experimentos demonstram que os resultados de impossibilidade teórica (limites assintóticos inferiores) manifestam-se qualitativamente em configurações de treinamento finito. Configurações com soluções teóricas aprendem a tarefa de forma robusta, enquanto aquelas sem elas lutam conforme a sequência aumenta, mesmo que tenham sucesso em pequenos valores de $n$ .
Modéstia: Os autores declaram explicitamente que a falha no treinamento não é prova de impossibilidade, nem o sucesso em pequenos $n$ contradiz os limites assintóticos inferiores. No entanto, a forte correlação entre seus limites teóricos e o desempenho empírico sugere que a complexidade causal é um preditor robusto de aprendizado para tarefas de recuperação.

O trabalho estende a análise da expressividade de transformers (previamente focada em composição de funções e cabeças de indução) para alternativas modernas e eficientes, fornecendo justificativa matemática rigorosa para suas limitações em cenários específicos de recuperação de informação.