🤖 machine learning

On the Expressiveness of State Space Models via Temporal Logics

Este artículo analiza el poder expresivo de los modelos de espacio de estados (SSM) utilizando lógicas temporales, revelando que sus capacidades varían desde lenguajes regulares hasta lenguajes no regulares dependiendo de los mecanismos de compuerta y la precisión aritmética, mientras compara sistemáticamente estos hallazgos con las arquitecturas de transformadores.

Autores originales: Eric Alsmann, Lowejatan Noori, Martin Lange

Publicado 2026-01-28

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Eric Alsmann, Lowejatan Noori, Martin Lange

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando enseñarle a un robot a leer una historia y a comprender la secuencia de eventos. En el mundo de la Inteligencia Artificial, existen dos tipos principales de "lectores" (arquitecturas) compitiendo por el puesto: los famosos Transformers (como los que impulsan los chatbots actuales) y las estrellas emergentes llamadas Modelos de Espacio de Estados (SSM).

Este artículo es una investigación teórica sobre la "capacidad cerebral" de los SSM. Los autores no están preguntando qué tan bien se desempeñan estos modelos en una prueba específica; en su lugar, se preguntan: "¿Cuál es el límite absoluto de lo que estos modelos pueden entender, sin importar cuánto los entrenemos?"

Para responder a esto, utilizan un "lenguaje lógico" especial (Lógica Temporal) como vara de medir. Aquí hay un desgari de sus hallazgos utilizando analogías sencillas.

1. Los dos tipos principales de SSMs

El artículo divide a los SSM en dos sabores principales según cómo manejan la información:

SSMs Diagonales con Compuertas (Los "Contadores Estrictos"): Estos modelos tienen una regla donde sus "compuertas" internas (interruptores que controlan el flujo de información) pueden cambiar según la palabra que estén leyendo, pero deben permanecer "diagonales". Piensa en esto como una calculadora donde puedes cambiar los números que estás sumando, pero no puedes mezclar las columnas entre sí.
SSM Invariantes en el Tiempo (Los "Relojes Constantes"): Estos modelos tienen compuertas que nunca cambian, sin importar qué palabra estén leyendo. Son como un metrónomo o un reloj; marcan el ritmo de la misma manera independientemente de la historia que se esté contando.

2. El problema de la precisión: Regla vs. Cinta métrica

Los autores también analizaron qué tan "preciso" es el cálculo dentro de estos modelos.

Precisión Fija: Imagina usar una regla que solo tiene 10 marcas. No importa qué tan larga sea la historia, no puedes medir nada más pequeño que esas marcas. Esto es como el cálculo computacional estándar (punto flotante).
Precisión Logarítmica: Imagina usar una cinta métrica que se vuelve automáticamente más larga y detallada a medida que la historia se alarga. Si la historia tiene 100 palabras, tu regla tiene 100 marcas; si tiene 1,000 palabras, tiene 1,000 marcas. Esto permite una cuenta mucho más fina.

3. ¿Qué pueden entender realmente?

Los "Contadores Estrictos" (SSMs Diagonales)

Con una regla simple (Precisión Fija): Son buenos entendiendo el orden de los eventos. Pueden decirte "A ocurrió antes que B" o "A ocurrió, luego B ocurrió, luego C ocurrió". Sin embargo, tienen un punto ciego importante: no pueden contar en ciclos.
- La Analogía: Si les pides reconocer un patrón como "un número par de 'a's" (por ejemplo, aa, aaaa, aaaaaa), fallan. Debido a que su matemática es monotónica (solo aumenta o se mantiene igual), eventualmente se quedan "atascados" y no pueden distinguir entre 2 'a's y 4 'a's.
Con una cinta métrica creciente (Precisión Logarítmica): Si les das la capacidad de contar con precisión, se vuelven mucho más inteligentes. Ahora pueden contar exactamente cuántas veces sucedió algo en el pasado. Pueden entender patrones complejos como "el número de 'a's es igual al número de 'b's es igual al número de 'c's".

Los "Relojes Constantes" (SSMs Invariantes en el Tiempo)

Con una regla simple: Estos modelos son malos rastreando relaciones complejas de "desde entonces" (por ejemplo, "¿Desde la última vez que vimos una 'b', hemos visto una 'a'?"). Sin embargo, tienen un superpoder: pueden contar en círculos.
- La Analogía: Debido a que su mecanismo interno es un ciclo constante, son excelentes para saber "¿Es esta la 2ª, 4ª o 6ª palabra?". Pueden reconocer fácilmente el patrón de "número par de 'a's" en el que los Contadores Estrictos fallaron.
Con una cinta métrica creciente: Pueden hacer ambas cosas: contar en círculos y contar números totales.

El "Híbrido" (SSMs Mixtos)

Si combinas ambos tipos de capas (algunas de Contadores Estrictos, otras de Relojes Constantes), obtienes lo mejor de ambos mundos. Pueden entender el orden, los ciclos y el conteo. El artículo muestra que estos modelos híbridos pueden reconocer casi cualquier patrón "regular" que puedas imaginar, hasta cierto límite de complejidad.

4. ¿Cómo se comparan con los Transformers?

Los autores compararon sus hallazgos con lo que ya sabemos de los Transformers:

Los SSMs Diagonales (Precisión Fija) son aproximadamente equivalentes a los Transformers sin pistas posicionales (conocen el orden de las palabras pero no su posición exacta).
Los SSMs Invariantes en el Tiempo son equivalentes a los Transformers con Codificaciones Posicionales (saben exactamente dónde están en la oración).
La Gran Diferencia: Los Transformers con "atención global" (como el tipo de Atención Dura Promedio) pueden mirar la historia entera a la vez para contar cosas hacia adelante y hacia atrás. Los SSM, por su naturaleza, solo miran hacia el pasado (lo que ya han leído). Por lo tanto, los SSM son estrictamente menos potentes que los Transformers más avanzados cuando se trata de contar cosas que suceden después en la secuencia.

5. Las tareas "imposibles"

Lo más importante a recordar es la lista de cosas que estos modelos no pueden hacer, sin importar cuánto los entrenes:

Un SSM Diagonal de Precisión Fija nunca podrá aprender a distinguir entre un número par e impar de elementos repetidos (como aa vs aaa). Este es un límite arquitectónico duro, no un fallo de entrenamiento.
Para romper este límite, debes cambiar la arquitectura (añadir capas invariantes en el tiempo) o aumentar la precisión matemática (usar la cinta métrica creciente).

Resumen

Piensa en estos modelos como diferentes tipos de bibliotecarios:

Diagonal (Fijo): Bueno leyendo un libro en orden, pero se confunde si se le pide contar patrones específicos.
Invariante en el Tiempo: Bueno contando páginas (par/impar), pero tiene dificultades con historias complejas de "desde entonces".
Híbrido: El bibliotecario definitivo que puede hacer ambas cosas, pero que aún no puede mirar hacia adelante al siguiente capítulo para contar cosas.

El artículo demuestra que estas limitaciones están integradas en el ADN de la arquitectura. No puedes entrenar a un bibliotecario "Diagonal de Precisión Fija" para que se convierta en un bibliotecario de "Conteo"; tienes que darle una mejor herramienta (precisión logarítmica) o una estructura cerebral diferente (capas mixtas) para lograrlo.

Resumen Técnico: Sobre la Expresividad de los Modelos de Espacio de Estados mediante Lógicas Temporales

Planteamiento del Problema

Los Modelos de Espacio de Estados (SSM, por sus siglas en inglés) han emergido como una alternativa competitiva a las arquitecturas Transformer para el modelado de secuencias, particularmente en los modelos de lenguaje de gran escala. Sin embargo, mientras que el progreso empírico es rápido, los fundamentos teóricos respecto a la capacidad de expresión de los SSM sigue estando poco explorado en comparación con los Transformers. El problema central abordado es determinar qué clases de lenguajes y patrones pueden representar teóricamente diferentes variantes de SSM, independientemente de la dinámica de entrenamiento. Específicamente, el artículo investiga cómo dos dimensiones arquitectónicas clave influyen en la expresividad:

Mecanismos de Puerta (Gating): La distinción entre puertas invariantes en el tiempo (matrices constantes, ej. S4), mecanismos de puerta diagonal (matrices diagonales dependientes de la entrada, ej. S6) y puertas arbitrarias.
Precisión Aritmética: La distinción entre aritmética de ancho fijo (bits constantes, ej. punto flotante estándar) y aritmética de precisión logarítmica (precisión que escala logarítmicamente con la longitud de la entrada).

Los autores pretenden mapear estas variantes con fragmentos de lógica formal y clases de complejidad para establecer cotas inferiores rigurosas e identificar cuellos de botella arquitectónicos fundamentales.

Metodología

Los autores emplean un marco lógico y de complejidad teórica para analizar la expresividad de los SSM, reflejando el trabajo fundacional reciente sobre Transformers (ej. Strobl et al., 2024; Yang et al., 2024a).

Modelo Formal: Los SSM se formalizan como capas que transforman secuencias de entrada mediante recurrencias lineales ( $h_t = \text{gate}(x_t) \cdot h_{t-1} + \text{inc}(x_t)$ ) seguidas de funciones de salida no lineales (modeladas como redes neuronales con activación ReLU).
Marco Lógico: El análisis utiliza la Lógica Temporal Lineal sobre trazas finitas (LTLf), específicamente el fragmento de pasado puro (PLTLf). Esta lógica captura propiedades basadas en el orden de los eventos sin contar.
- Extensiones: La lógica se extiende con predicados modulares (para rastrear posiciones periódicas) y operadores de conteo hacia atrás ( $\overleftarrow{\#}$ ) para analizar la capacidad de contar ocurrencias.
Pruebas Constructivas: Los autores proporcionan pruebas constructivas que demuestran cómo traducir fórmulas lógicas en arquitecturas de SSM. Muesten cómo operadores temporales específicos (ej. Ayer, Previamente, Desde que) y mecanismos de conteo pueden implementarse mediante estructuras de puerta y configuraciones aritméticas específicas.
Pruebas de Imposibilidad: Por el contrario, el artículo establece resultados de no-expresividad utilizando propiedades como la monotonicidad en SSM diagonales de precisión fija para demostrar que ciertos lenguajes no star-free (ej. $(aa)^*$ ) no pueden ser reconocidos.

Contribuciones Clave

1. Jerarquía de Expresividad de las Variantes de SSM

El artículo establece una jerarquía detallada de las capacidades de los SSM basada en el gating y la precisión:

SSM de Puerta Diagonal (Precisión Fija):
- Capacidad: Reconocer todos los lenguajes definibles en PLTLf (equivalente a los lenguajes star-free y a la Lógica de Primer Orden con orden, $FO[<]$).
- Limitación: No puede reconocer lenguajes no star-free como $(aa)^*$ debido a una propiedad de monotonicidad donde las entradas idénticas repetidas causan que el estado se estabilice.
SSM de Puerta Diagonal (Precisión Logarítmica):
- Capacidad: Reconocer lenguajes en PLTLf[ $\overleftarrow{\#}$ ], extendiendo la expresividad para incluir lenguajes no regulares e incluso no contextuales libres (ej. $\{a^n b^n c^n\}$ ) mediante el conteo hacia atrás.
SSM Invariante en el Tiempo (Precisión Fija):
- Capacidad: Reconocer lenguajes en UN-PLTLf[MOD] (Lógica Temporal Lineal Unaria con predicados modulares). Pueden rastrear posiciones periódicas (ej. distinguir índices pares/impares) usando matrices de permutación cíclica, lo que les permite reconocer $(aa)^*$ .
- Limitación: Se conjetura que son incapaces de reconocer lenguajes que requieren el operador Desde que (ej. $L(a \mathcal{S} b)$ ) porque carecen de puertas dependientes de la entrada para combinar información actual y pasada dinámicamente.
SSM Mixto (Diagonal + Invariante en el Tiempo):
- Capacidad: Reconocer PLTLf[MOD], capturando efectivamente la unión de las capacidades diagonal y de invariancia temporal. Esto corresponde a la clase de lenguajes regulares en $AC^0$ .
- Extensión de Precisión Logarítmica: Con precisión logarítmica, reconocen PLTLf[ $\overleftarrow{\#}$ , MOD].

2. La Precisión Aritmética como Determinante Crítico

El artículo demuestra rigurosamente que la precisión logarítmica es estrictamente necesaria para reconocer lenguajes de conteo no regulares. La aritmética de ancho fijo restringe a los SSM a lenguajes regulares (o star-free), mientras que la precisión logarítmica permite la acumulación de conteos necesarios para lenguajes como $a^n b^n c^n$ .

3. Comparación Sistemática con Transformers

Los autores mapean las variantes de SSM directamente con los resultados conocidos de expresividad de los Transformers:

SSM de Puerta Diagonal (Precisión Fija) $\approx$ Transformers de Atención Dura Única (UHAT) sin codificaciones posicionales (ambos capturan $FO[<]$).
SSM Invariante en el Tiempo $\approx$ UHAT con Codificaciones Posicionales (UHAT+PE) (ambos capturan $FO[<, MOD]$).
SSM Mixto (Precisión Logarítmica) $\approx$ Transformers de Atención Dura Promedio (AHAT) (ambos capturan capacidades de conteo, aunque los SSM están limitados al conteo hacia atrás).
Puertas Arbitrarias: Los SSM con puertas arbitrarias pueden reconocer todos los lenguajes regulares, igualando los límites superiores de las variantes de Transformer más complejas.

Resultados Clave

Teorema 1: Los SSM de puerta diagonal con precisión fija reconocen todos los lenguajes en PLTLf.
Teorema 3: Los SSM de puerta diagonal con precisión fija no pueden reconocer $(aa)^*$ , demostiendo una separación estricta de los SSM invariantes en el tiempo en este aspecto.
Teorema 4: Los SSM de puerta diagonal con precisión logarítmica reconocen todos los lenguajes en PLTLf[ $\overleftarrow{\#}$ ].
Teorema 7: Los SSM invariantes en el tiempo con precisión fija reconocen todos los lenguajes en UN-PLTLf[MOD].
Corolario 8: Los SSM mixtos con precisión fija reconocen todos los lenguajes regulares en $AC^0$ .
Imposibilidad: El artículo proporciona pruebas de imposibilidad que muestran cómo ciertas elecciones arquitectónicas (ej. diagonal de precisión fija) crean cuellos de botella fundamentales que ninguna cantidad de datos de entrenamiento u optimización puede superar.

Significado y Reivindicaciones

El artículo afirma proporcionar la primera conexión entre el poder de expresión de los SSM y la lógica formal, ofreciendo garantías estructurales sobre qué patrones son teóricamente aprendibles o demostrablemente imposibles para variantes específicas de SSM.

Perspectivas Fundacionales: Al delinear las tareas "imposibles" (ej. patrones no monotónicos para la puerta diagonal de precisión fija), el trabajo complementa los benchmarks empíricos al identificar límites arquitectónicos independientes de la dinámica de entrenamiento.
Claridad Arquitectónica: Los resultados aclaran la relación entre los SSM y los Transformers, mostrando que los SSM codifican inherentemente información posicional a través de la recurrencia (análogo a las codificaciones posicionales en los Transformers) pero difieren en sus mecanismos de conteo (conteo hacia atrás vs. atención global).
Alineación de Complejidad: Los hallazgos sugieren que los SSM restringidos (diagonal/invariante en el tiempo con precisión fija) probablemente operan dentro de $AC^0$ , un subconjunto propio del límite superior $TC^0$ establecido previamente por Merrill et al. (2024). Esto implica que estas arquitecturas podrían no ser capaces de reconocer la paridad u otros lenguajes fuera de $AC^0$ sin modificaciones específicas.

Los autores concluyen que su trabajo establece una base teórica rigurosa, revelando que la elección del mecanismo de puerta y la precisión aritmética dicta fundamentalmente la clase de lenguajes que un SSM puede modelar, independientemente del procedimiento de entrenamiento específico utilizado.