🤖 machine learning

Indexing: the Beginning and the End

Este artículo introduce el concepto de complejidad causal para demostrar que las arquitecturas de aprendizaje profundo con enmascaramiento, como las RNN y los transformadores de atención lineal, están fundamentalmente limitadas para resolver la primitiva de indexación cuando el índice aparece al final de la entrada, mientras que los transformadores con softmax y de atención lineal sin enmascaramiento pueden resolverla eficientemente, una separación teórica que es corroborada por experimentos empíricos.

Autores originales: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

Publicado 2026-07-27

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

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 construir un robot superinteligente que pueda leer una historia y responder preguntas sobre ella. Este es el mundo de la inteligencia artificial, específicamente un campo llamado "aprendizaje profundo" (deep learning), donde las computadoras aprenden patrones observando cantidades masivas de datos. Durante mucho tiempo, los robots más populares para este trabajo se llamaron "Transformers". Son como bibliotecarios brillantes que pueden hojear instantáneamente un libro entero para encontrar un dato específico. Pero hay un inconveniente: a medida que el libro se vuelve más largo, el bibliotecario se vuelve cada vez más lento, y construirlos requiere mucha energía y dinero.

Para solucionar esto, los científicos inventaron nuevos tipos de robots, como los "RNN" (que leen historias palabra por palabra, como un humano) y los "SSM" (que intentan leer toda la historia a la vez pero de una manera muy optimizada). La gran pregunta que todos se hacen es: "¿Son estos nuevos robots, más rápidos, tan inteligentes como los viejos y lentos, o tienen puntos ciegos ocultos?". Para encontrar la respuesta, los investigadores no solo adivinan; les dan a los robots acertijos diminutos y complicados para resolver. Estos acertijos son como la "tarea de matemáticas" del mundo de la IA. Si un robot no puede resolver un simple problema de tarea, demuestra que el cerebro del robot tiene un límite fundamental, sin importar cuánto lo entrenes.

Este artículo, titulado "Indexing: the Beginning and the End" (Indexación: el principio y el fin), toma un acertijo muy específico y simple llamado "Indexación" y lo utiliza para probar los cerebros de estas diferentes arquitecturas de robots. El acertijo es engañosamente fácil: imagina que tienes una lista de $n$ bits (una cadena de 0s y 1s) y un número $i$ que te indica qué bit elegir. El objetivo es simplemente devolver el valor de ese bit específico. Es como si te entregaran una fila de 64 interruptores de luz y un número, digamos "17", y te preguntaran: "¿El interruptor 17 está encendido o apagado?".

Los investigadores, Alexander Kozachinskiy, Vicente Opazo y Felipe Urrutia, descubrieron que el orden en el que el robot ve la información lo cambia todo. Encontraron que algunos robots son increíblemente rápidos en esta tarea, mientras que otros chocan contra un muro que simplemente no pueden escalar, sin importar cuántas capas de "pensamiento" tengan.

Aquí está el giro: el artículo demuestra que para ciertos tipos de robots (específicamente aquellos que procesan la información de una manera "causal" o "enmascarada", lo que significa que solo pueden mirar lo que vino antes de ellos y no lo que viene después), resolver este acertijo es matemáticamente imposible si la lista de bits es larga y el número de índice aparece al puro final. Es como si le entregaras a un robot una larga fila de personas, le pidieras que recordara la cara de cada una y luego, al final, le susurraras: "Dime el nombre de la persona número 42". El artículo muestra que los robots como los RNN, Mamba y los Transformers de atención lineal enmascarada tienen un "cuello de botella de memoria". No pueden comprimir toda esa información en un paquete lo suficientemente pequeño como para recordar el bit específico cuando llega el índice. Los autores demostraron esto utilizando matemáticas rigurosas que se mantienen constantes incluso si los robots tienen una precisión infinita (es decir, que no se confunden por errores de redondeo).

Sin embargo, la historia cambia si inviertes el guion. Si el número de índice aparece al principio de la lista (diciéndole al robot "Recuerda a la persona 42" antes de que siquiera le muestres la fila de personas), los RNN se convierten en los superhéroes. Pueden resolver esto en un solo paso, mientras que los otros robots (incluidos los famosos Transformers) necesitan al menos dos pasos para resolverlo.

Los autores no solo hicieron las matemáticas; también realizaron experimentos con modelos reales. Entrenaron a estos robots con listas de hasta 64 bits. Los resultados coinciden perfectamente con su teoría. Los robots que las matemáticas decían que deberían fallar (los causales que intentan encontrar el bit al final de una lista larga) consistentemente se rindieron a medida que las listas se hacían más largas. Mientras tanto, los robots que las matemáticas decían que deberían tener éxito aprendieron la tarea fácilmente.

Entonces, ¿cuál es la conclusión? No es que un robot sea "mejor" que otro en todos los sentidos. En cambio, el artículo revela que las diferentes arquitecturas tienen diferentes "superpoderes" y diferentes "kriptonitas". La forma en que un robot procesa la información —ya sea que lea de izquierda a derecha, mire todo a la vez o intente resumir el pasado— determina exactamente qué acertijos puede resolver y cuáles lo dejarán perplejo para siempre. Esto ayuda a los científicos a comprender los límites fundamentales de la IA, asegurando que, cuando construyamos la próxima generación de máquinas inteligentes, sepamos exactamente qué pueden y qué no pueden hacer.

Resumen Técnico: Indexación: El Principio y el Fin

Planteamiento del Problema

Este artículo investiga la expresividad y los cuellos de botella de información de las arquitecturas modernas de aprendizaje profundo —específicamente Redes Neuronales Recurrentes (RNN), Transformers de Softmax, Transformers de Atención Lineal y Modelos de Espacio de Estados (SSM)— a través de la lente del primitivo de indexación.

La tarea de indexación se define de la siguiente manera: dado una secuencia de $n$ bits $\sigma_1, \dots, \sigma_n \in \{0, 1\}$ y un índice $i \in \{1, \dots, n\}$ , el modelo debe devolver el valor del $i$ -ésimo bit, $\sigma_i$ . Los autores analizan dos variaciones específicas de esta tarea para sondear diferentes limitaciones arquitectónicas:

Indexación por la Derecha (RHI - Right-Hand Indexing): El índice $i$ aparece al final de la secuencia de entrada (después de los bits). El modelo debe recuperar $\sigma_i$ basándose en la información procesada de los $n$ bits precedentes.
Indexación por la Izquierda (LHI - Left-Hand Indexing): El índice $i$ aparece al principio de la secuencia de entrada (antes de los bits). El modelo debe transportar la información del índice a través de la secuencia para recuperar $\sigma_i$ al final.

El estudio se centra en arquitecturas "pequeñas", definidas como aquellas con $o(1)$ parámetros (un número constante de parámetros en relación con la longitud de la secuencia $n$ ) y potencialmente con aritmética de precisión infinita.

Metodología

Los autores emplean un marco teórico basado en la complejidad causal y la dimensión VC para derivar cotas inferiores incondicionales.

Complejidad Causal

Para arquitecturas causales (enmascaradas), donde la salida en la posición $k$ depende solo de los inputs $1$ hasta $k$ , los autores introducen la noción de complejidad causal. Esta mide la dimensión mínima $s$ a la que se puede comprimir la historia de los inputs ( $x_1, \dots, x_{k-1}$ ) (mediante una función de "huella digital") de tal manera que la $k$ -ésima salida pueda ser computada a partir de esta representación comprimida y el input actual $x_k$ con baja complejidad aritmética.

Perspectiva Clave: Si una arquitectura tiene baja complejidad causal (específicamente $o(1)$ ), no puede comprimir la historia necesaria para resolver tareas que requieren la recuperación de información pasada específica cuando dicha información no es inmediatamente accesible.

Herramientas Teóricas

Dimensión VC: Los autores adaptan la técnica de Kozachinskiy et al. (2025) para demostrar que si un modelo resuelve la tarea de indexación, la clase de conceptos asociada debe tener una dimensión VC de al menos $n$ .
Complejidad Aritmética: Utilizan la complejidad aritmética de las funciones computadas por las capas (incluyendo exponenciales, operaciones aritméticas y condicionales) para acotar la dimensión VC.
Cotas Incondicionales: A diferencia de trabajos previos que dependían de supuestos de precisión acotada, estos resultados se mantienen incluso para modelos que utilizan números reales de precisión infinita.

Validación Experimental

Los hallazgos teóricos se validan mediante experimentos en tareas de indexación binaria para longitudes de secuencia $n \in \{8, 16, 32, 64\}$ . Los autores comparan:

Variantes completas y causales de Transformers de Softmax y de Atención Lineal.
RNN (específicamente GRUs).
SSMs (específicamente Mamba).
Todos los modelos son entrenados desde cero con hiperparámetros fijos para observar la dinámica de aprendizaje a medida que $n$ aumenta.

Contribuciones Clave y Resultados

1. Indexación por la Derecha (Índice al Final)

En este escenario, el modelo procesa todos los $n$ bits antes de ver el índice. Para resolver la tarea, el modelo debe comprimir toda la cadena de $n$ bits en un estado lo suficientemente pequeño como para ser procesado por el token del índice.

Imposibilidad para Arquitecturas de Baja Complejidad Causal: Los autores demuestran que ningún número constante ( $O(1)$ $O (1)$ ) de capas con $o(1)$ $o (1)$ de complejidad causal puede resolver la RHI.
- Arquitecturas Afectadas: Las RNN pequeñas, los SSMs (ej. Mamba) y los Transformers de Atención Lineal causales tienen una complejidad causal de $o(1)$ . En consecuencia, no pueden resolver la RHI en un número constante de capas, incluso con precisión infinita.
- Confirmación Experimental: Los modelos en esta categoría (Atención Lineal causal de 1 y múltiples capas, GRUs, Mamba) fallan consistentemente en aprender la RHI a medida que $n$ crece, alcanzando un éxito del 0% en $n=64$ .
Posibilidad para Arquitecturas de Alta Complejidad Causal:
- Transformers de Softmax: Una sola capa con $O(1)$ parámetros puede resolver la RHI. Esto se atribuye a su alta complejidad causal (mediante el mecanismo de softmax que permite la atención global).
- Atención Lineal Completa: Dos capas con $O(1)$ parámetros pueden resolver la RHI.
- Confirmación Experimental: Estas configuraciones aprenden la tarea fácilmente, con altas tasas de éxito incluso en $n=64$ .

2. Indexación por la Izquierda (Índice al Principio)

En este escenario, el índice se procesa primero y debe transportarse a través de la secuencia hasta la posición del bit relevante.

Dominio de las RNN: Las RNN pequeñas pueden resolver la LHI en una sola capa con $O(1)$ parámetros. Naturalmente mantienen un estado oculto que puede portar el índice $i$ y actualizar una coordenada específica cuando se encuentra el $i$ -ésimo bit.
Limitaciones de otras Arquitecturas:
- SSMs y Atención Lineal: Ni los SSMs de 1 capa ni la Atención Lineal de 1 capa (tanto enmascarada como completa) pueden resolver la LHI con $o(1)$ parámetros. La linealidad de las actualizaciones de los SSM impide que puedan "escribir" selectivamente el valor del bit en una posición específica determinada por el índice sin mezclar la información de una forma que impida su recuperación.
- Transformers de Softmax: Los Transformers de Softmax de 1 capa también fallan en la LHI con $o(1)$ parámetros.
Resolución mediante Profundidad: Todas las arquitecturas (incluyendo SSMs, Atención Lineal y Transformers de Softmax) pueden resolver la LHI si se les otorgan 2 capas con $O(1)$ parámetros. La primera capa propaga el índice y la segunda puede recuperar el bit.
Confirmación Experimental: Las GRUs de 1 capa tienen éxito en todas las longitudes. Los modelos Mamba y de Atención Lineal de 1 capa fallan para $n \ge 16$ . Las versiones de 2 capas de todas las arquitecturas tienen éxito.

Tabla Resumen de Capas Mínimas Requeridas

Arquitectura	Indexación por la Izquierda (LHI)	Indexación por la Derecha (RHI)
Softmax Completo	2	1
Softmax Causal	2	1
Atención Lineal Completa	2	2
Atención Lineal Causal	2	$\omega(1)$ (Imposible)
SSM (ej. Mamba)	2	$\omega(1)$ (Imposible)
RNN	1	$\omega(1)$ (Imposible)

(Nota: $\omega(1)$ indica que el número de capas requeridas no está acotado por una constante; es decir, crece con $n$ .)

Significado y Afirmaciones

El artículo afirma proporcionar las primeras cotas inferiores de múltiples capas y de precisión infinita para una clase de arquitecturas con baja complejidad causal, incluyendo SSMs, RNNs y Transformers de atención lineal enmascarados.

Separación Arquitectónica: El primitivo de indexación revela una separación fundamental entre arquitecturas. Mientras que los Transformers de Softmax y los modelos de Atención Lineal completos pueden resolver la RHI eficientemente, las variantes enmascaradas y los SSMs no pueden, resaltando el papel específico de los mecanismos de atención global para superar los cuellos de botella de información.
Papel de la Linealidad: Los resultados sugieren que las reglas de actualización lineales de los SSM, a menudo elogiadas por su eficiencia, se convierten en un lastre en las tareas de LHI donde se requiere una escritura selectiva no lineal en un solo paso.
Alineación entre Teoría y Práctica: Los experimentos demuestran que los resultados de imposibilidad teórica (cotas asintóticas inferiores) se manifiestan cualitativamente en entornos de entrenamiento finitos. Las configuraciones con soluciones teóricas aprenden la tarea de forma robusta, mientras que aquellas que carecen de ellas presentan dificultades a medida que la longitud de la secuencia aumenta, incluso si tienen éxito en valores pequeños de $n$ .
Modestia: Los autores declaran explícitamente que el fallo en el entrenamiento no es prueba de imposibilidad, ni el éxito en valores pequeños de $n$ contradice las cotas inferiores asintóticas. Sin embargo, la fuerte correlación entre sus cotas teóricas y el rendimiento empírico sugiere que la complejidad causal es un predictor robusto de la capacidad de aprendizaje para tareas de recuperación.

El trabajo extiende el análisis de la expresividad de los Transformers (previamente centrado en la composición de funciones y los cabezales de inducción) hacia alternativas modernas y eficientes, proporcionando una justificación matemática riguroya de sus limitaciones en escenarios específicos de recuperación de información.