🤖 machine learning

The Expressive Limits of Diagonal SSMs for State-Tracking

Este artigo estabelece que a expressividade de Modelos de Espaço de Estados (SSMs) complexos de valores diagonais de $k$ camadas para rastreamento de estado é precisamente limitada a grupos solúveis com uma série subnormal de comprimento $k$ , revelando uma barreira teórica fundamental para grupos não-abelianos e uma lacuna empírica entre expressividade e aprendibilidade.

Autores originais: Mehran Shakerinava, Behnoush Khavari, Siamak Ravanbakhsh, Sarath Chandar

Publicado 2026-08-17

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Mehran Shakerinava, Behnoush Khavari, Siamak Ravanbakhsh, Sarath Chandar

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 seguir um conjunto de instruções que alteram seu humor interno ou sua posição. No mundo da inteligência artificial, isso é chamado de "modelagem de sequência". O robô lê uma história palavra por palavra e, com cada nova palavra, atualiza sua compreensão de para onde a história está indo. Por muito tempo, os robôs mais famosos (chamados de Transformers) foram ótimos nisso, mas também eram incrivelmente ávidos por poder computacional. Então, cientistas inventaram um tipo de robô novo e mais enxuto chamado Modelo de Espaço de Estados, ou SSM. Pense em um SSM como um robô com um banco de memória minúsculo e eficiente que se atualiza instantaneamente conforme ele lê, em vez de reler toda a história cada vez.

Mas aqui está a parte complicada: só porque um robô é eficiente não significa que ele seja inteligente o suficiente para fazer tudo. Algumas tarefas são como matemática simples (somar números), enquanto outras são como quebra-cabeças complexos envolvendo a troca de itens em uma ordem específica. Na matemática, esses quebra-cabeças são frequentemente descritos usando "grupos", que são apenas regras sofisticadas para como as coisas podem ser combinadas ou trocadas. Se as regras forem simples e previsíveis (como somar números), o robô pode lidar com elas facilmente. Mas se as regras forem bagunçadas e dependerem da ordem das operações (como trocar três bolas de cores diferentes onde trocar vermelho e depois azul é diferente de azul e depois vermelho), o robô pode ficar confuso. Os cientistas querem saber: qual é o limite absoluto do que esses robôs eficientes podem realmente entender? Eles conseguem aprender a resolver os quebra-cabeças bagunçados, ou estão presos aos simples?

Este artigo mergulha profundamente nessa questão, testando um tipo de robô muito específico e eficiente chamado "SSM Diagonal". Os pesquisadores queriam ver se esses robôs podiam aprender a rastrear mudanças de estado complexas, especificamente aquelas envolvendo grupos não-abelianos (os quebra-cabeças bagunçados e dependentes da ordem). Eles descobriram uma barreira matemática rígida: um robô diagonal de uma única camada simplesmente não consegue resolver esses quebra-cabeças bagunçados, não importa o quanto você tente. No entanto, se você empilhar dois ou mais desses robôs uns sobre os outros, eles teoricamente ganham o poder de resolvê-los, mas apenas se o quebra-cabeça tiver uma estrutura específica e em camadas (chamada de "grupo resolúvel").

Aqui está a reviravolta que torna a história interessante: mesmo que os robôs empilhados deveriam ser capazes de resolver esses quebra-cabeças na teoria, os pesquisadores descobriram que, na prática, eles frequentemente falham em aprender como fazê-lo. É como ter um carro com um motor potente o suficiente para subir uma montanha, mas o motorista (o algoritmo de treinamento) vive ficando preso em uma vala e não consegue encontrar o caminho para cima. O artigo prova que o poder existe dentro da arquitetura, mas os métodos de treinamento padrão lutam para desbloqueá-lo, especialmente para as tarefas não-abelianas mais complexas.

O Banco de Memória do Robô

Para entender o que os autores descobriram, primeiro precisamos olhar para como esses "SSMs Diagonais" funcionam. Imagine um robô com uma fileira de interruptores de luz. Quando ele lê uma nova palavra, ele aciona esses interruptores com base em uma regra simples. Em um SSM "Diagonal", a regra para acionar um interruptor não depende dos outros interruptores; cada interruptor age de forma independente. Isso torna o rob em incrivelmente rápido e fácil de treinar, como uma equipe de trabalhadores cada um fazendo seu próprio trabalho sem precisar conversar entre si.

Os pesquisadores testaram esses robôs em um jogo chamado "rastreamento de estado". Neste jogo, o robô recebe uma sequência de comandos (como "troque a bola vermelha", "gire a bola azul") e deve lembrar a disposição final das bolas. Se os comandos forem simples e comutarem (o que significa que a ordem não importa, como somar 2 + 3 que é o mesmo que 3 + 2), o robô é um mestre. Mas se os comandos não comutarem (como colocar meias antes de sapatos versus sapatos antes de meias), o robô enfrenta um desafio muito maior.

A Barreira Teórica: Uma Camada vs. Muitas

O artigo começa com uma prova matemática robusta sobre o que um robô de uma única camada pode fazer. Os autores mostraram que um SSM diagonal de uma única camada é fundamentalmente limitado a resolver apenas quebra-cabeças "abelianos" — aqueles onde a ordem das operações não importa. Não importa o quanto você ajuste o robô, se ele tiver apenas uma camada desses interruptores independentes, ele não pode rastrear o estado de um grupo não-abeliano complexo (como as permutações de três objetos, conhecido como o grupo $S_3$ ).

No entanto, a história fica mais emocionante quando você empilha camadas. Os autores provaram que, se você empilhar $k$ camadas desses robôs diagonais, a equipe pode resolver um quebra-cabeça se, e somente se, o quebra-cabeça puder ser decomposto em uma cadeia de $k$ etapas abelianas mais simples. Pense nisso como uma corrida de revezamento. Se o quebra-cabeça for complexo demais para um corredor, você pode passar o bastão para um segundo corredor, que o passa para um terceiro. Desde que o quebra-cabeça possa ser fatiado em um número específico de etapas simples e ordenadas, uma equipe desse número de robôs pode teoricamente resolvê-lo. Isso significa que a profundidade (adicionar mais camadas) é a chave para desbloquear uma inteligência mais complexa, mas isso vem com uma regra estrita: você precisa de exatamente tantas camadas quanto o quebra-cabeça possui de "fatias" de complexidade.

O Hiato de Aprendizado: Teoria vs. Realidade

É aqui que o enredo se intensifica. Os autores não pararam apenas na matemática; eles construíram esses robôs e tentaram treiná-los. Eles testaram modelos de camada única e de duas camadas em várias tarefas, incluindo adição simples (Abeliana) e o difícil quebra-cabeça de permutação $S_3$ (não-Abeliana).

Os resultados foram uma mistura de sucesso e frustração. Para as tarefas simples, os robôs aprenderam rapidamente e conseguiram lidar com sequências muito longas. Mas para a tarefa complexa de $S_3$ , embora o robô de duas camadas devesse ser poderoso o suficiente para resolvê-la (de acordo com a matemática deles), ele falhou na maioria das vezes. O robô simplesmente não conseguia aprender o padrão correto, mesmo após milhares de tentativas.

Os pesquisadores descobriram que o problema não era que o robô não podia fazer isso; a solução existia dentro do design do robô. Era mais como se o robô estivesse procurando uma agulha em um palheiro, e o método de treinamento padrão (gradiente descendente) continuava perdendo a agulha. Em um experimento, eles tentaram "ajudar" o robô começando-o muito perto da resposta correta. Quando fizeram isso, o robô subitamente aprendeu a tarefa e conseguiu lidar com sequências muito mais longas do que as que havia visto antes. Isso sugere que a solução está lá, escondida no "espaço de pesos" do robô, mas o caminho para encontrá-la é incrivelmente estreito e difícil de navegar com o treinamento padrão.

A Conclusão

O artigo conclui que, embora os SSMs diagonais sejam eficientes e teoricamente capazes de resolver problemas de rastreamento de estado complexos se você empilhar camadas suficientes, existe um enorme abismo entre o que eles podem fazer e o que eles realmente aprendem. A matemática diz que um robô de duas camadas pode resolver o quebra-cabeça $S_3$ , mas na prática, ele geralmente falha. Isso destaca uma lição crucial para a pesquisa em IA: só porque um modelo tem o potencial de ser inteligente não significa que ele aprenderá a ser inteligente facilmente. Os autores sugerem que, para preencher esse abismo, talvez precisemos mudar a forma como treinamos esses modelos ou talvez ajustar levemente sua arquitetura (como permitir um pouco mais de interação entre os interruptores) para tornar o caminho para a solução menos escorregadio.

Em resumo, esses robôs eficientes são como estudantes brilhantes que têm o conhecimento do livro didático para resolver um problema difícil, mas continuam falhando no exame porque não conseguem descobrir como aplicar o conhecimento. O artigo mapeia exatamente o que eles são capazes de fazer, mas também nos alerta que fazer com que eles realmente desempenhem é um desafio muito mais difícil do que a matemática sugere.

Resumo Técnico: Os Limites Expressivos de SSMs Diagonais para Rastreamento de Estado

Declaração do Problema

Os Modelos de Espaço de Estados (SSMs) emergiram como alternativas eficientes e paralelizáveis aos Transformers para modelagem de sequências de longo alcance. No entanto, seu poder expressivo teórico permanece mal compreendido, particularmente em relação à sua capacidade de realizar tarefas de rastreamento de estado. Essas tarefas, que envolvem manter e atualizar um estado oculto com base em uma sequência de entradas (por exemplo, verificações de paridade, adição modular ou rastreamento de permutação), estão intimamente relacionadas a linguagens regulares e são críticas para aplicações como execução de código e análise de programas.

Embora se saiba que os Transformers têm dificuldade com certas tarefas de rastreamento de estado (especificamente aquelas que exigem operações de grupos não solucionáveis), os SSMs foram inicialmente hipotetizados como excelentes devido à sua natureza recorrente. Trabalhos recentes mostraram que SSMs padrão (incluindo variantes invariantes no tempo e diagonais) falham até mesmo em tarefas simples e solucionáveis, como a paridade. Este artigo investiga os limites expressivos precisos de SSMs Complexos Dependentes de Entrada (DCD) sobre tarefas de rastreamento de estado sequencial, focando especificamente na capacidade de rastrear grupos finitos. A questão central é: Quais classes de grupos um DCD SSM de $k$ camadas pode teoricamente representar, e podem os algoritmos de aprendizado padrão encontrar essas representações de forma confiável?

Metodologia

Os autores empregam uma combinação de análise da teoria dos grupos e avaliação empírica.

Estrutura Teórica

Definição do Modelo: O estudo foca em DCD SSMs, onde a matriz de transição $A(x_t)$ é diagonal e de valores complexos, e depende da entrada $x_t$ . A atualização do estado segue uma recorrência afim: $h_t = A(x_t)h_{t-1} + b(x_t)$ .
Conexão com a Teoria dos Grupos: Os autores mapeiam tarefas de rastreamento de estado para a simulação de grupos finitos. Um modelo rastreia um grupo $G$ se ele puder computar o produto cumulativo de uma sequência de elementos de grupo.
Análise de Camada Única: Os autores provam que um DCD SSM de camada única não pode rastrear nenhum grupo não-abeliano com precisão finita. Eles demonstram que, mesmo com um termo de viés dependente da entrada $b(x_t)$ e um decodificador, a natureza comutativa das matrizes diagonais restringe o modelo a grupos abelianos.
Análise de Múltiplas Camadas: O artigo estende isso para DCD SSMs de $k$ $k$ camadas. Eles estabelecem uma condição necessária e suficiente para a expressividade: Um DCD SSM de $k$ $k$ camadas pode rastrear um grupo $G$ $G$ se, e somente se, $G$ $G$ admite uma série subnormal de comprimento $k$ com fatores abelianos.
- Matematicamente, isso significa $G = G_k \trianglerighteq G_{k-1} \trianglerighteq \dots \trianglerighteq G_1 \trianglerighteq \{e\}$ , onde cada quociente $G_{i+1}/G_i$ é Abeliano.
- Este resultado identifica o intervalo de expressividade preciso de DCD SSMs de $k$ camadas como a classe de grupos solucionáveis com uma profundidade estrutural específica.
Prova Construtiva: Os autores fornecem uma construção concreta para um DCD SSM de 2 camadas rastreando o grupo simétrico $S_3$ (o menor grupo não-abeliano solucionável) através da decomposição em um cascata de dois autômatos abelianos ( $C_2$ e $C_3$ ).

Avaliação Empírica

Os autores avaliam variantes de uma e duas camadas de várias arquiteturas de SSM (Mamba, Negative Mamba, AUSSM e AUSSM simplificado) junto com RNNs.

Tarefas: Rastreamento de estado em vários grupos, incluindo grupos abelianos ( $C_2, C_6, C_{24}, C_{60}$ ), produtos de grupos cíclicos ( $C_2 \times C_4, C_3 \times C_6$ ) e grupos não-abelianos solucionáveis ( $S_3, A_4$ ). O grupo não-solucionável $A_5$ é incluído como controle.
Protocolo: Modelos são treinados em sequências de até comprimento 60 usando aprendizado por currículo e testados para generalização em sequências de até comprimento 1000.

Principais Contribuições

Caracterização Teórica: O artigo fornece a primeira caracterização precisa do poder expressivo de SSMs diagonais. Eles provam que:
- DCD SSMs de camada única são limitados a grupos abelianos.
- DCD SSMs de $k$ camadas são limitados a grupos solucionáveis com uma série subnormal de comprimento $k$ .
- Isso estabelece um benefício teórico estrito de profundidade para modelar dinâmicas não-abelianas dentro da restrição diagonal.
Identificação do Gap de Aprendizado: Embora a teoria prove que DCD SSMs de 2 camadas podem representar grupos não-abelianos como $S_3$ , os resultados empíricos mostram que a otimização baseada em gradiente padrão falha em aprender essas soluções. Os modelos consistentemente falham em generalizar para sequências longas para $S_3$ e $A_4$ , apesar da capacidade teórica para fazê-lo.
Insight de Inicialização: Os autores demonstram que inicializar um modelo próximo à solução analítica (derivada de sua construção teórica) permite que ele aprenda e generalize. Isso sugere que a falha não é devida à falta de capacidade no espaço de pesos, mas sim à dificuldade do cenário de otimização em encontrar essas codificações sem orientação.

Resultados

Grupos Abelianos: Modelos de camada única (especificamente Negative Mamba e AUSSM) aprendem e generalizam com sucesso em tarefas abelianas (ex: paridade, contagem modular).
Grupos Não-Abelianos Solucionáveis: Modelos multi-camadas (2 camadas) teoricamente capazes de rastrear $S_3$ e $A_4$ falham em generalizar na prática. Eles alcançam alta precisão em comprimentos de treinamento, mas colapsam em sequências de teste mais longas.
Grupos Não-Solucionáveis: Como esperado, nenhum modelo (incluindo DCD SSMs multi-camadas) aprende o grupo não-solucionável $A_5$ .
Comparação com RNNs: RNNs, que não possuem barreira teórica de expressividade para essas tarefas, geralmente têm sucesso em aprender e generalizar, destacando que a falha dos SSMs é específica de suas restrições arquiteturais e dinâmicas de otimização, não apenas da dificuldade da tarefa.

Significância e Alegações

O artigo afirma estabelecer uma distinção nítida entre expressividade e aprendizado em SSMs diagonais.

Expressividade: A profundidade fornece um caminho disciplinado e teoricamente provável para aumentar o poder expressivo de SSMs diagonais de grupos abelianos para grupos solucionáveis. Os autores definem o limite exato dessa capacidade usando a teoria dos grupos.
Aprendizado: Os autores argumentam que, embora esses modelos possuam a capacidade teórica de resolver tarefas complexas de rastreamento de estado, os algoritmos de treinamento padrão lutam para descobrir as configurações de pesos necessárias. Isso sugere que o "viés indutivo" da diagonalidade, embora eficiente, pode dificultar ativamente a descoberta de estruturas não-abelianas.
Implicações: O trabalho sugere que simplesmente empilhar camadas diagonais é insuficiente para um desempenho confiável em tarefas não-abelianas sem melhores estratégias de otimização ou modificações arquiteturais (ex: estruturas bloco-diagonais). Ele clama por uma separação de preocupações ao avaliar novas arquiteturas de sequência: a capacidade teórica de um modelo não garante sua utilidade prática.

Os autores concluem que o progresso futuro requer não apenas expandir a fronteira expressiva (ex: transições bloco-diagonais), mas também desenvolver métodos de treinamento capazes de navegar de forma confiável pelo cenário de perda para encontrar soluções que existem em princípio.