🤖 machine learning

On the Expressiveness of State Space Models via Temporal Logics

Este artigo analisa o poder expressivo de modelos de espaço de estados (SSMs) utilizando lógicas temporais, revelando que suas capacidades variam de linguagens regulares a linguagens não regulares dependendo dos mecanismos de portão e da precisão aritmética, enquanto compara sistematicamente essas descobertas com arquiteturas transformer.

Autores originais: Eric Alsmann, Lowejatan Noori, Martin Lange

Publicado 2026-01-28

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Eric Alsmann, Lowejatan Noori, Martin Lange

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 ensinar um robô a ler uma história e entender a sequência de eventos. No mundo da Inteligência Artificial, existem dois tipos principais de "leitores" (arquiteturas) competindo pelo trabalho: os famosos Transformers (como os que alimentam os chatbots atuais) e as estrelas em ascensão chamadas Modelos de Espaço de Estados (SSMs).

Este artigo é uma investigação teórica sobre o "poder cerebral" dos SSMs. Os autores não estão perguntando o quão bem esses modelos performam em um teste específico; em vez disso, eles estão perguntando: "Qual é o limite absoluto do que esses modelos podem entender, não importa o quanto os treinemos?"

Para responder a isso, eles usam uma "linguagem lógica" especial (Lógica Temporal) como uma régua de medição. Aqui está um detalamento de suas descobertas usando analogias simples.

1. Os Dois Principais Tipos de SSMs

O artigo divide os SSMs em dois sabores principais baseados em como eles lidam com a informação:

SSMs de Diagonal-Gating (Os "Contadores Estritos"): Esses modelos têm uma regra onde seus "portões" internos (interruptores que controlam o fluxo de informação) podem mudar com base na palavra atual que estão lendo, mas devem permanecer "diagonais". Pense nisso como uma calculadora onde você pode mudar os números que está somando, mas não pode misturar as colunas.
SSMs Invariantes no Tempo (Os "Relógios Constantes"): Esses modelos têm portões que nunca mudam, não importa qual palavra estejam lendo. Eles são como um metrônomo ou um relógio; eles batem no mesmo ritmo, independentemente da história que está sendo contada.

2. O Problema da Precisão: Régua vs. Fita Métrica

Os autores também observaram o quão "precisa" é a matemática dentro desses modelos.

Precisão Fixa: Imagine usar uma régua que tem apenas 10 marcas. Não importa o quão longa seja a história, você não consegue medir nada menor que essas marcas. Isso é como a matemática padrão de computador (ponto flutuante).
Precisão Logarítmica: Imagine usar uma fita métrica que se torna automaticamente mais longa e detalhada conforme a história avança. Se a história tiver 100 palavras, sua régua terá 100 marcas; se tiver 1.000 palavras, terá 1.000 marcas. Isso permite uma contagem muito mais fina.

3. O Que Eles Realmente Podem Entender?

Os "Contadores Estritos" (SSMs Diagonais)

Com uma régua simples (Precisão Fixa): Eles são bons em entender a ordem dos eventos. Eles conseguem dizer "A aconteceu antes de B" ou "A aconteceu, depois B aconteceu, depois C aconteceu". No entanto, eles têm um ponto cego importante: Eles não conseguem contar em ciclos.
- A Analogia: Se você perguntar a eles para reconhecer um padrão como "um número par de 'a's" (ex: aa, aaaa, aaaaaa), eles falham. Porque sua matemática é monotônica (ela só sobe ou permanece igual), eles eventualmente ficam "presos" e não conseguem distinguir a diferença entre 2 'a's e 4 'a's.
Com uma fita métrica crescente (Precisão Logarítmica): Se você lhes der a habilidade de contar com precisão, eles se tornam muito mais inteligentes. Eles agora podem contar exatamente quantas vezes algo aconteceu no passado. Eles podem entender padrões complexos como "O número de 'a's é igual ao número de 'b's é igual ao número de 'c's".

Os "Relógios Constantes" (SSMs Invariantes no Tempo)

Com uma régua simples: Esses modelos são ruins em rastrear relações complexas de "desde então" (ex: "Desde a última vez que vimos um 'b', vimos um 'a'?"). No entanto, eles têm um superpoder: Eles conseguem contar em círculos.
- A Analogia: Como seu mecanismo interno é um ciclo constante, eles são excelentes em saber "Este é o 2º, 4º ou 6º termo?". Eles conseguem facilmente reconhecer o padrão de "número par de 'a's" que os Contadores Estritos não conseguiram.
Com uma fita métrica crescente: Eles podem fazer ambos: contar em círculos e contar números totais.

O "Híbrido" (SSMs Mistos)

Se você combinar ambos os tipos de camadas (algumas camadas de Contadores Estritos, algumas de Relógios Constantes), você obtém o melhor dos dois mundos. Eles podem entender ordem, ciclos e contagem. O artigo mostra que esses modelos híbridos podem reconhecer quase qualquer padrão "regular" que você possa imaginar, até um certo limite de complexidade.

4. Como Eles se Comparam aos Transformers?

Os autores compararam suas descobertas com o que já sabemos sobre os Transformers:

SSMs Diagonais (Precisão Fixa) são aproximadamente equivalentes a Transformers sem pistas posicionais (eles conhecem a ordem das palavras, mas não sua posição exata).
SSMs Invariantes no Tempo são equivalentes a Transformers com Codificações Posicionais (eles sabem exatamente onde estão na frase).
A Grande Diferença: Transformers com "atenção global" (como o tipo de Atenção Hard-Average) podem olhar para a história inteira de uma vez para contar coisas para frente e para trás. Os SSMs, por sua natureza, só olham para o passado (o que já leram). Portanto, os SSMs são estritamente menos poderosos que os Transformers mais avançados quando se trata de contar coisas que acontecem mais tarde na sequência.

5. As Tarefas "Impossíveis"

A lição mais importante é a lista de coisas que esses modelos não conseguem fazer, não importa o quanto você os treine:

Um SSM Diagonal de Precisão Fixa nunca conseguirá aprender a distinguir entre um número par e um número ímpar de itens repetidos (como aa vs aaa). Este é um limite arquitetural rígido, não uma falha de treinamento.
Para quebrar esse limite, você deve ou alterar a arquitetura (adicionar camadas invariantes no tempo) ou aumentar a precisão matemática (usar a fita métrica crescente).

Resumo

Pense nesses modelos como diferentes tipos de bibliotecários:

Diagonal (Fixo): Bom em ler um livro em ordem, mas fica confuso se for solicitado a contar padrões específicos.
Invariante no Tempo: Bom em contar páginas (par/ímpar), mas tem dificuldade com histórias complexas de "desde então".
Híbrido: O bibliotecário supremo que pode fazer ambos, mas ainda não consegue olhar para o próximo capítulo para contar as coisas.

O artigo prova que essas limitações estão construídas no DNA da arquitetura. Você não pode treinar um bibliotecário "Diagonal de Precisão Fixa" para se tornar um bibliotecário de "Contagem"; você tem que dar a ele uma ferramenta melhor (precisão logarítmica) ou uma estrutura cerebral diferente (camadas mistas) para alcançar isso.

Resumo Técnico: Sobre a Expressividade de Modelos de Espaço de Estados via Lógicas Temporais

Declaração do Problema

Os Modelos de Espaço de Estados (SSMs) emergiram como uma alternativa competitiva às arquiteturas Transformer para modelagem de sequências, particularmente em grandes modelos de linguagem. No entanto, enquanto o progresso empírico é rápido, os fundamentos teóricos referentes à capacidade expressiva dos SSMs permanecem subexplorados em comparação aos Transformers. O problema central abordado é determinar quais classes de linguagens e padrões diferentes variantes de SSM podem teoricamente representar, independentemente da dinâmica de treinamento. Especificamente, o artigo investiga como duas dimensões arquitetônicas influenciam a expressividade:

Mecanismos de Gating (Portas): A distinção entre portas invariantes no tempo (matrizes constantes, ex: S4), mecanismos de gating diagonal (matrizes diagonais dependentes da entrada, ex: S6) e portas arbitrárias.
Precisão Aritmética: A distinção entre aritmética de largura fixa (bits constantes, ex: ponto flutuante padrão) e aritmética de precisão logarítmica (precisão escalonando logaritmicamente com o comprimento da entrada).

Os autores visam mapear essas variantes para fragmentos de lógica formal e classes de complexidade para estabelecer limites inferiores rigorosos e identificar gargalos arquitetônicos fundamentais.

Metodologia

Os autores empregam um arcabouço lógico e de teoria da complexidade para analisar a expressividade dos SSMs, espelhando trabalhos fundamentais recentes sobre Transformers (ex: Strobl et al., 2024; Yang et al., 2024a).

Modelo Formal: Os SSMs são formalizados como camadas que transformam sequências de entrada via recorrências lineares ( $h_t = \text{gate}(x_t) \cdot h_{t-1} + \text{inc}(x_t)$ ) seguidas por funções de saída não lineares (modeladas como Redes Neurais Feedforward com ativação ReLU).
Arcabouço Lógico: A análise utiliza a Lógica Temporal Linear sobre traços finitos (LTLf), especificamente o fragmento de passado puro (PLTLf). Esta lógica captura propriedades baseadas na ordenação de eventos sem contagem.
- Extensões: A lógica é estendida com predicados modulares (para rastrear posições periódicas) e operadores de contagem de olhar para trás ( $\overleftarrow{\#}$ ) para analisar a capacidade de contar ocorrências.
Provas Construtivas: Os autores fornecem provas construtivas demonstrando como traduzir fórmulas lógicas em arquiteturas SSM. Eles mostram como operadores temporais específicos (ex: Ontem, Previamente, Desde que) e mecanismos de contagem podem ser implementados via estruturas de gating específicas e configurações aritméticas.
Provas de Impossibilidade: Inversamente, o artigo estabelece resultados de não-expressividade usando propriedades como monotonicidade em SSMs diagonais de precisão fixa para provar que certas linguagens não-star-free (ex: $(aa)^*$ ) não podem ser reconhecidas.

Contribuições Principais

1. Hierarquia de Expressividade de Variantes de SSM

O artigo estabelece uma hierarquia detalhada das capacidades dos SSMs baseada em gating e precisão:

SSM de Gating Diagonal (Precisão Fixa):
- Capacidade: Reconhecer todas as linguagens definíveis em PLTLf (equivalente a linguagens star-free e Lógica de Primeira Ordem com ordem, $FO[<]$).
- Limitação: Não pode reconhecer linguagens não-star-free como $(aa)^*$ devido a uma propriedade de monotonicidade onde entradas idênticas repetidas fazem o estado estabilizar.
SSM de Gating Diagonal (Precisão Logarítmica):
- Capacidade: Reconhecer linguagens em PLTLf[ $\overleftarrow{\#}$ ], estendendo a expressividade para incluir linguagens não-regulares e até não-livres de contexto (ex: $\{a^n b^n c^n\}$ ) via contagem de olhar para trás.
SSM Invariante no Tempo (Precisão Fixa):
- Capacidade: Reconhecer linguagens em UN-PLTLf[MOD] (PLTLf Unária com predicados modulares). Eles podem rastrear posições periódicas (ex: distinguir índices pares/ímpares) usando matrizes de permutação cíclica, permitindo que reconheçam $(aa)^*$ .
- Limitação: Conjectura-se serem incapazes de reconhecer linguagens que exigem o operador Desde que (ex: $L(a \mathcal{S} b)$ ) porque carecem de portas dependentes da entrada para combinar informações atuais e passadas dinamicamente.
SSM Misto (Diagonal + Invariante no Tempo):
- Capacidade: Reconhecer PLTLf[MOD], capturando efetivamente a união das capacidades diagonal e invariante no tempo. Isso corresponde à classe de linguagens regulares em $AC^0$ .
- Extensão de Precisão Logarítmica: Com precisão logarítmica, reconhecem PLTLf[ $\overleftarrow{\#}$ , MOD].

2. Precisão Aritmética como um Determinante Crítico

O artigo demonstra rigorosamente que a precisão logarítmica é estritamente necessária para reconhecer linguagens de contagem não-regulares. A aritmética de largura fixa restringe os SSMs a linguagens regulares (ou star-free), enquanto a precisão logarítmica permite a acumulação de contagens necessárias para linguagens como $a^n b^n c^n$ .

3. Comparação Sistemática com Transformers

Os autores mapeiam as variantes de SSM diretamente para resultados conhecidos de expressividade de Transformers:

SSM Diagonal (Precisão Fixa) $\approx$ Transformers de Atenção Hard Única (UHAT) sem codificações posicionais (ambos capturam $FO[<]$).
SSM Invariante no Tempo $\approx$ UHAT com Codificações Posicionais (UHAT+PE) (ambos capturam $FO[<, MOD]$).
SSM Misto (Precisão Logarítmica) $\approx$ Transformers de Atenção Hard Média (AHAT) (ambos capturam capacidades de contagem, embora os SSMs sejam limitados à contagem de olhar para trás).
Gates Arbitrários: SSMs com gates arbitrários podem reconhecer todas as linguagens regulares, correspondendo aos limites superiores de variantes mais complexas de Transformers.

Principais Resultados

Teorema 1: SSMs diagonais com precisão fixa reconhecem todas as linguagens em PLTLf.
Teorema 3: SSMs diagonais com precisão fixa não podem reconhecer $(aa)^*$ , provando uma separação estrita de SSMs invariantes no tempo a este respeito.
Teorema 4: SSMs diagonais com precisão logarítmica reconhecem todas as linguagens em PLTLf[ $\overleftarrow{\#}$ ].
Teorema 7: SSMs invariantes no tempo com precisão fixa reconhecem todas as linguagens em UN-PLTLf[MOD].
Corolário 8: SSMs mistos com precisão fixa reconhecem todas as linguagens regulares em $AC^0$ .
Impossibilidade: O artigo fornece provas de impossibilidade mostrando que escolhas arquitetônicas específicas (ex: diagonal de precisão fixa) criam gargalos fundamentais que nenhum volume de dados de treinamento ou otimização pode superar.

Significância e Alegações

O artigo afirma fornecer a primeira conexão entre o poder expressivo de SSMs e a lógica formal, oferecendo garantias estruturais sobre quais padrões são teoricamente aprendíveis ou provadamente impossíveis para variantes específicas de SSM.

Insights Fundamentais: Ao delinear as tarefas "impossíveis" (ex: padrões não-monotônicos para diagonal de precisão fixa), o trabalho complementa benchmarks empíricos ao identificar limites arquitetônicos independentes da dinâmica de treinamento.
Clareza Arquitetônica: Os resultados esclarecem a relação entre SSMs e Transformers, mostrando que os SSMs codificam inerentemente informações posicionais através de recorrência (análogo às codificações posicionais em Transformers), mas diferem em seus mecanismos de contagem (olhar para trás vs. atenção global).
Alinhamento de Complexidade: As descobertas sugerem que SSMs restritos (diagonal/invariante no tempo com precisão fixa) provavelmente operam dentro de $AC^0$ , um subconjunto próprio do limite superior $TC^0$ estabelecido anteriormente por Merrill et al. (2024). Isso implica que essas arquiteturas podem não ser capazes de reconhecer paridade ou outras linguagens fora de $AC^0$ sem modificações específicas.

Os autores concluem que seu trabalho estabelece uma base teórica rigorosa, revelando que a escolha do mecanismo de gating e da precisão aritmética dita fundamentalmente a classe de linguagens que um SSM pode modelar, independentemente do procedimento de treinamento específico utilizado.