🤖 machine learning

The Expressive Limits of Diagonal SSMs for State-Tracking

Este artículo establece que la expresividad de los Modelos de Espacio de Estados (SSM) complejos con valores diagonales de $k$ capas para el seguimiento de estados está precisamente limitada a grupos resolubles con una serie subnormal de longitud $k$ , revelando una barrera teórica fundamental para los grupos no abelianos y una brecha empírica entre la expresividad y la capacidad de aprendizaje.

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

Publicado 2026-08-17

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

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

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ñar a un robot a seguir un conjunto de instrucciones que cambian su estado interno o su posición. En el mundo de la inteligencia artificial, esto se llama "modelado de secuencias". El robot lee una historia palabra por palabra y, con cada nueva palabra, actualiza su comprensión de hacia dónde se dirige la historia. Durante mucho tiempo, los robots más famosos (llamados Transformers) fueron excelentes en esto, pero también eran increíblemente hambrientos de potencia de cómputo. Así que, los científicos inventaron un tipo de robot más esbelto y eficiente llamado Modelo de Espacio de Estados, o SSM. Piensa en un SSM como un robot con un banco de memoria diminuto y eficiente que se actualiza instantáneamente mientras lee, en lugar de relecturar toda la historia cada vez.

Pero aquí está la parte difícil: el hecho de que un robot sea eficiente no significa que sea lo suficientemente inteligente para hacerlo todo. Algunas tareas son como matemáticas simples (sumar números), mientras que otras son como rompecabezas complejos que implican intercambiar elementos en un orden específico. En las matemáticas, estos rompecabezas suelen describirse mediante "grupos", que son simplemente reglas sofisticadas sobre cómo las cosas pueden combinarse o intercambiarse. Si las reglas son simples y predecibles (como sumar números), el robot podría manejarlas fácilmente. Pero si las reglas son desordenadas y dependen del orden de las operaciones (como intercambiar tres bolas de diferentes colores donde intercambiar rojo y luego azul es diferente a azul y luego rojo), el robot podría confundirse. Los científicos quieren saber: ¿Cuál es el límite absoluto de lo que estos robots eficientes realmente pueden entender? ¿Pueden aprender a resolver los rompecabezas desordenados, o están atrapados con los simples?

Este artículo profundiza en esa pregunta probando un tipo de robot muy eficiente llamado "SSM Diagonal". Los investigadores querían ver si estos robots podían aprender a rastrear cambios de estado complejos, específicamente aquellos que involucran grupos no abelianos (los rompecabezas desordenados y dependientes del orden). Descubrieron un muro matemático infranqueable: un robot diagonal de una sola capa simplemente no puede resolver estos rompecabezas desordenados, sin importar cuánto lo intentes. Sin embargo, si apilas dos o más de estos robots uno encima del otro, teóricamente adquieren el poder de resolverlos, pero solo si el rompecabezas tiene una estructura específica y por capas (llamada un "grupo resoluble").

Aquí está el giro que hace que la historia sea interesante: incluso aunque los robots apilados deberían ser capaces de resolver estos rompecabezas en teoría, los investigadores descubrieron que, en la práctica, a menudo fallan en aprender cómo hacerlo. Es como tener un coche con un motor lo suficientemente potente como para subir una montaña, pero el conductor (el algoritmo de entrenamiento) se queda atrapado en una zanja y no encuentra el camino hacia arriba. El artículo demuestra que el poder existe dentro de la arquitectura, pero los métodos de entrenamiento estándar luchan por desbloquearlo, especialmente para las tareas no abelianas más complejas.

El Banco de Memoria del Robot

Para entender lo que los autores descubrieron, primero debemos observar cómo funcionan estos "SSM Diagonales". Imagina un robot con una fila de interruptores de luz. Cuando lee una nueva palabra, cambia estos interruptores basándose en una regla simple. En un SSM "Diagonal", la regla para cambiar un interruptor no depende de los otros interruptos; cada interruptor actúa de forma independiente. Esto hace que el robot sea increíblemente rápido y fácil de entrenar, como un equipo de trabajadores donde cada uno hace su propio trabajo sin necesidad de hablar entre sí.

Los investigadores probaron estos robots en un juego llamado "seguimiento de estado" (state-tracking). En este juego, se le da al robot una secuencia de comandos (como "intercambia la bola roja", "rota la bola azul") y este debe recordar la disposición final de las bolas. Si los comandos son simples y conmutan (lo que significa que el orden no importa, como sumar 2 + 3 que es lo mismo que 3 + 2), el robot es un experto. Pero si los comandos no conmutan (como ponerse los calcetines antes que los zapatos frente a los zapatos antes que los calcetines), el robot enfrenta un desafío mucho mayor.

El Muro Teórico: Una Capa vs. Muchas Capas

El artículo comienza con una sólida prueba matemática sobre lo que puede hacer un robot de una sola capa. Los autores demostraron que un SSM diagonal de una sola capa está fundamentalmente limitado a resolver solo rompecabezas "abelianos", aquellos donde el orden de las operaciones no importa. No importa cuánto ajustes al robot, si solo tiene una capa de estos interruptores independientes, no puede rastrear el estado de un grupo no abeliano complejo (como las permutaciones de tres objetos, conocido como el grupo $S_3$ ).

Sin embargo, la historia se vuelve más emocionante cuando se apilan las capas. Los autores demostraron que si apilas $k$ capas de estos robots diagonales, el equipo puede resolver un rompecabezas si y solo si el rompecabezas puede descomponerse en una cadena de $k$ pasos abelianos más simples. Piensa en ello como una carrera de relevos. Si el rompecabezas es demasiado complejo para un corredor, puedes pasar el testigo a un segundo corredor, quien lo pasa a un tercero. Siempre y cuando el rompecabezas pueda dividirse en un número específico de pasos simples y ordenados, un equipo de esa cantidad de robots puede teóricamente resolverlo. Esto significa que la profundidad (añadir más capas) es la clave para desbloquear una inteligencia más compleja, pero viene con una regla estricta: necesitas exactamente tantas capas como "rebanadas" de complejidad tenga el rompecabezas.

La Brecha de Aprendizaje: Teoría vs. Realidad

Aquí es donde la trama se complica. Los autores no se detuvieron solo en las matemáticas; construyeron estos robots e intentaron entrenarlos. Probaron modelos de una y dos capas en varias tareas, incluyendo la suma simple (Abeliana) y el complicado rompecabezas de permutación $S_3$ (no Abeliano).

Los resultados fueron una mezcla de éxito y frustración. Para las tareas simples, los robots aprendieron rápidamente y pudieron manejar secuencias muy largas. Pero para la tarea compleja de $S_3$ , a pesar de que el robot de dos capas debería haber sido lo suficientemente potente para resolverla (según sus matemáticas), la mayoría de las veces falló. El robot simplemente no podía aprender el patrón correcto, incluso después de miles de intentos.

Los investigadores descubrieron que el problema no era que el robot no pudiera hacerlo; la solución existía dentro del diseño del robot. Era más bien como si el robot estuviera buscando una aguja en un pajar, y el método de entrenamiento estándar (descenso de gradiente) seguía perdiendo la aguja. En un experimento, intentaron "ayudar" al robot colocándolo muy cerca de la respuesta correcta. Cuando hicieron esto, el robot de repente aprendió la tarea y pudo manejar secuencias mucho más largas de las que había visto antes. Esto sugiere que la solución está ahí, oculta en el "espacio de pesos" del robot, pero el camino para encontrarla es increíblemente estrecho y difícil de navegar con el entrenamiento estándar.

La Conclusión

El artículo concluye que, si bien los SSM diagonales son eficientes y teóricamente capaces de resolver problemas de seguimiento de estado complejos si se apilan suficientes capas, existe una brecha masiva entre lo que pueden hacer y lo que realmente aprenden. Las matemáticas dicen que un robot de dos capas puede resolver el rompecabezas $S_3$ , pero en la práctica, suele fallar. Esto resalta una lección crucial para la investigación en IA: el hecho de que un modelo tenga el potencial de ser inteligente no significa que aprenderá a ser inteligente fácilmente. Los autores sugieren que, para cerrar esta breza, podríamos necesitar cambiar la forma en que entrenamos estos modelos o quizás retocar ligeramente su arquitectura (como permitir un poco más de interacción entre los interruptores) para que el camino hacia la solución sea menos resbaladizo.

En resumen, estos robots eficientes son como estudiantes brillantes que tienen el conocimiento de los libros de texto para resolver un problema difícil, pero siguen fallando en el examen porque no logran descifrar cómo aplicar ese conocimiento. El artículo traza exactamente de qué son capaces, pero también advierte que lograr que realmente funcionen es un desafío mucho más difícil de lo que las matemáticas sugieren.

Resumen Técnico: Los Límites Expresivos de los SSMs Diagonales para el Seguimiento de Estados

Planteamiento del Problema

Los Modelos de Espacio de Estados (SSMs, por sus siglas en inglés) han surgido como alternativas eficientes y paralelizables a los Transformers para el modelado de secuencias de largo alcance. Sin embargo, su poder expresivo teórico sigue siendo poco comprendido, particularmente en lo que respecta a su capacidad para realizar tareas de seguimiento de estados. Estas tareas, que implican mantener y actualizar un estado oculto basado en una secuencia de entradas (por ejemplo, comprobaciones de paridad, suma modular o seguimiento de permutaciones), están estrechamente relacionadas con los lenguajes regulares y son críticas para aplicaciones como la ejecución de código y el análisis de programas.

Mientras que se sabe que los Transformers tienen dificultades con ciertas tareas de seguimiento de estados (específicamente aquellas que requieren operaciones de grupos no resolubles), se hipotetizó inicialmente que los SSMs destacarían debido a su naturaleza recurrente. Trabajos recientes han demostrado que los SSMs estándar (incluyendo las variantes invariantes en el tiempo y las diagonales) fallan incluso en tareas simples y resolubles como la paridad. Este artículo investiga los límites expresivos precisos de los SSMs de Valores Complejos Dependientes de la Entrada (DCD) en tareas de seguimiento de estado secuencial, centrándose específicamente en la capacidad de rastrear grupos finitos. La pregunta central es: ¿Qué clases de grupos puede representar teóricamente un DCD SSM de $k$ capas, y pueden los algoritmos de aprendizaje estándar encontrar estas representaciones de manera fiable?

Metodología

Los autores emplean una combinación de análisis de teoría de grupos y evaluación empírica.

Marco Teórico

Definición del Modelo: El estudio se centra en los DCD SSMs, donde la matriz de transición $A(x_t)$ es diagonal y de valores complejos, y depende de la entrada $x_t$ . La actualización del estado sigue una recurrencia afín: $h_t = A(x_t)h_{t-1} + b(x_t)$ .
Conexión con la Teoría de Grupos: Los autores mapean las tareas de seguimiento de estado al simulacro de grupos finitos. Un modelo rastrea un grupo $G$ si puede computar el producto acumulado de una secuencia de elementos del grupo.
Análisis de Capa Única: Los autores demuestran que un DCD SSM de una sola capa no puede rastrear ningún grupo no Abeliano con precisión finita. Demuestran que incluso con un término de sesgo dependiente de la entrada $b(x_t)$ y un decodificador, la naturaleza conmutativa de las matrices diagonales restringe al modelo a grupos Abelianos.
Análisis de Multicapa: El artículo extiende esto a los DCD SSMs de $k$ $k$ capas. Establecen una condición necesaria y suficiente para la expresividad: Un DCD SSM de $k$ $k$ capas puede rastrear un grupo $G$ $G$ si y solo si $G$ $G$ admite una serie subnormal de longitud $k$ con factores Abelianos.
- Matemáticamente, esto significa $G = G_k \trianglerighteq G_{k-1} \trianglerighteq \dots \trianglerighteq G_1 \trianglerighteq \{e\}$ , donde cada cociente $G_{i+1}/G_i$ es Abeliano.
- Este resultado identifica el rango de expresividad precisa de los DCD SSMs de $k$ capas como la clase de grupos resolubles con una profundidad estructural específica.
Prueba Constructiva: Los autores proporcionan una construcción concreta para un DCD SSM de 2 capas que rastrea el grupo simétrico $S_3$ (el más pequeño grupo no Abeliano resoluble) mediante la descomposición en una cascada de dos autómatas Abelianos ( $C_2$ y $C_3$ ).

Evaluación Empírica

Los autores evalúan variantes de una y dos capas de varias arquitecturas de SSM (Mamba, Negative Mamba, AUSSM y AUSSM simplificado) junto con RNNs.

Tareas: Seguimiento de estado en varios grupos, incluyendo grupos Abelianos ( $C_2, C_6, C_{24}, C_{60}$ ), productos de grupos cíclicos ( $C_2 \times C_4, C_3 \times C_6$ ) y grupos no Abelianos resolubles ( $S_3, A_4$ ). El grupo no resoluble $A_5$ se incluye como control.
Protocolo: Los modelos se entrenan en secuencias de hasta longitud 60 utilizando aprendizaje de currículo (curriculum learning) y se prueban para la generalización en secuencias de hasta longitud 1000.

Contribuciones Clave

Caracterización Teórica: El artículo proporciona la primera caracterización precisa del poder expresivo de los SSMs diagonales. Demuestra que:
- Los DCD SSMs de una sola capa están limitados a grupos Abelianos.
- Los DCD SSMs de $k$ capas están limitados a grupos resolubles con una serie subnormal de longitud $k$ .
- Esto establece un beneficio teórico estricto de la profundidad para modelar la dinámica no Abeliana dentro de la restricción diagonal.
Identificación de la Brecha de Aprendibilidad: Aunque la teoría demuestra que los DCD SSMs de 2 capas pueden representar grupos no Abelianos como $S_3$ , los resultados empíricos muestran que la optimización basada en gradiente estándar falla en aprender estas soluciones. Los modelos fallan consistentemente en generalizar a secuencias largas para $S_3$ y $A_4$ , a pesar de la capacidad teórica para hacerlo.
Perspectiva de Inicialización: Los autores demuestran que inicializar un modelo cerca de la solución analítica (derivada de su construcción teórica) permite que aprenda y generalice. Esto sugiere que el fallo no se debe a una falta de capacidad en el espacio de pesos, sino a la dificultad del paisaje de optimización para encontrar estas codificaciones específicas sin guía.

Resultados

Grupos Abelianos: Los modelos de una sola capa (específicamente Negative Mamba y AUSSM) aprenden y generalizan con éxito en tareas Abelianas (por ejemplo, paridad, conteo modular).
Grupos No Abelianos Resolubles: Los modelos multicapa (2 capas) teóricamente capaces de rastrear $S_3$ y $A_4$ fallan en generalizar en la práctica. Logran una alta precisión en longitudes de entrenamiento, pero colapsan en secuencias de prueba más largas.
Grupos No Resolubles: Como era de esperar, ningún modelo (incluidos los DCD SSMs multicapa) aprende el grupo no resoluble $A_5$ .
Comparación con RNNs: Las RNNs, que no tienen barreras teóricas de expresividad para estas tareas, generalmente tienen éxito en el aprendizaje y la generalización, resaltando que el fallo de los SSMs es específico de sus restricciones arquitectónicas y dinámicas de optimización, no solo de la dificultad de la tarea.

Significado y Reivindicaciones

El artículo afirma establecer una distinción nítida entre expresividad y aprendibilidad en los SSMs diagonales.

Expresividad: La profundidad proporciona un camino disciplinado y teóricamente demostrable para aumentar el poder expresivo de los SSMs diagonales de Abelianos a resolubles. Los autores definen el límite exacto de esta capacidad utilizando la teoría de grupos.
Aprendibilidad: Los autores argumentan que, si bien estos modelos poseen la capacidad teórica para resolver tareas complejas de seguimiento de estado, los algoritmos de entrenamiento estándar luchan por descubrir las configuraciones de pesos requeridas. Esto sugiere que el "sesgo inductivo" de la diagonalidad, aunque eficiente, puede dificultar activamente el descubrimiento de estructuras no Abelianas.
Implicaciones: El trabajo sugiere que simplemente apilar capas diagonales es insuficiente para un rendimiento fiable en tareas no Abelianas sin mejores estrategias de optimización o modificaciones arquitectónicas (por ejemplo, estructuras de bloque diagonal). Hace un llamado a separar las preocupaciones al evaluar nuevas arquitecturas de secuencias: la capacidad teórica de un modelo no garantiza su utilidad práctica.

Los autores concluyen que el progreso futuro requiere no solo expandir la frontera expresiva (por ejemplo, mediante transiciones de bloque diagonal), sino también desarrollar métodos de entrenamiento capaces de navegar de manera fiable el paisaje de pérdida para encontrar soluciones que existen en principio.