Length Generalization Bounds for Transformers

Este paper demuestra que no existen límites computables de generalización de longitud para CRASP (y por tanto para los transformers) incluso con dos capas, mientras que establece un límite computable óptimo de complejidad exponencial para el fragmento positivo de CRASP, equivalente a los transformers de precisión fija.

Lo esencial

Imagina que entrenas a un chef de cocina (el modelo de Inteligencia Artificial, o "Transformer") para que prepare un plato perfecto.

El problema que este artículo resuelve es el siguiente: ¿Cuántos ingredientes (datos de entrenamiento) necesitas darle al chef para que pueda cocinar un banquete gigante, aunque solo haya visto recetas pequeñas?

Aquí está la explicación sencilla de lo que descubrieron los autores, usando analogías:

1. El Gran Problema: "El Chef que se pierde en el laberinto"

Los autores se preguntaron: Si le enseñamos a un modelo de IA a reconocer patrones en textos cortos (como frases de 10 palabras), ¿podemos garantizar matemáticamente que funcionará perfectamente en textos infinitamente largos (como una novela entera)?

La respuesta corta y sorprendente es: No, no podemos garantizarlo para los modelos normales.

• La Analogía: Imagina que intentas enseñarle a un robot a contar hasta un número infinito. Le muestras ejemplos hasta el 100. El robot aprende el patrón. Pero, ¿cómo sabes si el robot realmente entendió la regla o si solo memorizó hasta el 100?
• El Hallazgo: Los autores demostraron que, para los modelos de IA estándar (como los que usamos hoy), es matemáticamente imposible calcular un "límite de seguridad". Es decir, no existe una fórmula mágica que te diga: "Si le das al modelo 1 millón de ejemplos de frases cortas, funcionará bien en frases largas".
• La Razón Profunda: Esto se debe a que estos modelos son tan poderosos que pueden resolver problemas matemáticos que ni siquiera los ordenadores más avanzados pueden resolver (llamados problemas indecidibles, como el "Décimo Problema de Hilbert"). Si el modelo puede hacer cosas que son imposibles de predecir, entonces no podemos predecir cuándo dejará de funcionar bien al alargar el texto.

2. La Solución Parcial: "El Chef con Reglas Estrictas"

Entonces, ¿todo está perdido? No. Los autores encontraron una forma de salvar el día, pero con una condición: limitar la precisión del chef.

• La Analogía: Imagina que le quitas al chef su capacidad de usar ingredientes infinitamente precisos (como "0.0000001 gramos de sal") y le obligas a usar solo medidas enteras y simples (como "1 cucharada", "2 cucharadas").
• El Resultado: Cuando limitamos la precisión de los modelos (llamados "Transformers de precisión fija"), ¡sí podemos calcular el límite!
• El Costo: El límite existe, pero es enorme.
  • Si quieres que el modelo funcione en textos largos, la cantidad de ejemplos de entrenamiento que necesitas no crece linealmente (10, 20, 30...), sino exponencialmente.
  • La Metáfora: Es como si para aprender a caminar en una habitación pequeña necesitaras 10 pasos, pero para aprender a caminar en un estadio, necesitaras un número de pasos igual a "todos los átomos del universo". Es computable (sabes cuánto necesitas), pero es una cantidad tan gigantesca que en la práctica es casi imposible de lograr.

3. ¿Por qué es importante esto?

Hasta ahora, muchos científicos creían que si simplemente hacíamos los modelos más grandes o les dábamos más datos, automáticamente aprenderían a generalizar (funcionar bien en textos largos).

Este papel nos dice:

1. No es solo cuestión de tamaño: Aumentar el modelo no garantiza que funcione en textos largos.
2. El "muro" matemático: Hay una barrera fundamental. Para los modelos actuales, es imposible saber con certeza cuándo han aprendido lo suficiente para generalizar.
3. La única salida: Para tener garantías matemáticas, debemos usar modelos más simples (con precisión limitada), pero eso requiere cantidades de datos tan absurdamente grandes que a menudo no vale la pena el esfuerzo.

En resumen

Imagina que estás entrenando a un perro para que busque una pelota.

• El problema: No hay forma de saber cuántas veces debes lanzar la pelota en un jardín pequeño para garantizar que el perro la encontrará en un bosque gigante. Podría ser que nunca lo logre, y no hay forma de predecirlo.
• La solución: Si le pones al perro unas gafas especiales que le hacen ver el mundo en "píxeles" (precisión fija), entonces sí puedes calcular cuántas veces debes lanzar la pelota. Pero el cálculo te dirá que necesitas lanzarla más veces que el número de estrellas en el cielo para estar seguro.

Conclusión: Los modelos de IA actuales son tan complejos que, matemáticamente, no podemos garantizar que funcionen bien en textos largos basándonos solo en datos cortos. Y si intentamos simplificarlos para tener garantías, el costo de entrenamiento se vuelve astronómico.

Resumen técnico

Resumen Técnico: Límites de Generalización de Longitud para Transformers

1. Planteamiento del Problema

La generalización de longitud es la capacidad de un algoritmo de aprendizaje para realizar predicciones correctas en entradas de cualquier longitud, habiendo sido entrenado únicamente con datos finitos de longitudes acotadas. Aunque los Transformers han mostrado capacidades empíricas en esta área, su comportamiento es inconsistente y altamente sensible a hiperparámetros (inicialización, tasas de aprendizaje, codificaciones posicionales).

El problema central abordado en este trabajo es la computabilidad de los límites de generalización de longitud. Específicamente, se busca determinar si existe un algoritmo que pueda calcular un límite computable $N$ tal que, si un modelo se entrena con cadenas de longitud hasta $N$, se garantice que generalizará correctamente a cadenas más largas.

Anteriormente, se sabía que para Transformers de una capa (y bajo restricciones para dos capas) existían límites computables. Sin embargo, la existencia de tales límites para Transformers más profundos (dos o más capas) y para la clase general de lenguajes que definen (C-RASP) permanecía como un problema abierto.

2. Metodología y Marco Teórico

Los autores utilizan un enfoque basado en la Teoría del Aprendizaje Computacional y la Teoría de la Computabilidad, vinculando los Transformers con lenguajes formales.

• C-RASP (Counting RASP): Se utiliza la clase de lenguajes C-RASP, que es expresivamente equivalente a los Transformers con precisión fija fuera de la atención. C-RASP es un lenguaje de programación diseñado para capturar la potencia expresiva de los Transformers.
• Complejidad de Longitud: Se define la complejidad de longitud como la longitud mínima de una cadena necesaria para distinguir entre dos hipótesis (programas) diferentes. Si esta complejidad es computable, entonces la generalización de longitud es posible.
• Reducción a Problemas de Decidibilidad: Siguiendo trabajos previos (Chen et al., 2025), los autores establecen que la existencia de un límite computable de generalización de longitud es equivalente a la decidibilidad del problema de equivalencia de lenguajes para la clase de hipótesis considerada.
• Análisis de Vacío (Emptiness): Para probar la indecidibilidad, reducen el problema de equivalencia al problema de vacuidad (¿define un programa C-RASP el lenguaje vacío?).

3. Contribuciones Clave y Resultados

El papel presenta dos resultados principales que responden al problema abierto:

A. Resultado de No Existencia (Incomputabilidad) para C-RASP General

• Teorema Principal: No existe ningún algoritmo que pueda aprender perfectamente un programa C-RASP (y por ende, un Transformer) con una garantía de generalización de longitud computable, incluso si el programa tiene solo dos capas.
• Mecanismo de Prueba:
  1. Los autores demuestran que el problema de vacuidad para lenguajes definidos por C-RASP es indecidible.
  2. Logran esto mediante una reducción desde el 10º Problema de Hilbert (la insolubilidad de las ecuaciones diofánticas, demostrada por Matiyasevich).
  3. Codifican ecuaciones diofánticas ($x=c$, $x+y=z$, $x \cdot y = z$) dentro de lenguajes definidos por C-RASP. La existencia de una solución para la ecuación corresponde a la no vacuidad del lenguaje.
  4. Dado que la vacuidad es indecidible, la equivalencia de lenguajes también lo es. Por lo tanto, la complejidad de longitud no está acotada por ninguna función computable (crece más rápido que cualquier función computable, incluida la función de Ackermann).
• Implicación: Para Transformers generales (con dos o más capas), es imposible garantizar teóricamente que se haya visto suficiente datos de entrenamiento para lograr una generalización perfecta.

B. Resultado de Existencia (Límite Computable) para el Fragmento Positivo (C-RASP+)

• Definición: Se introduce C-RASP+, un subconjunto restringido de C-RASP donde las ecuaciones/inecuaciones solo permiten contar hasta un umbral (sin restas complejas que permitan contar hacia atrás ilimitadamente). Este fragmento es equivalente a los Transformers de precisión fija (fixed-precision transformers).
• Teorema Secundario: Para C-RASP+ (y Transformers de precisión fija), la complejidad de longitud es computable y exponencial.
• Mecanismo de Prueba:
  1. Se demuestra que C-RASP+ puede reducirse a la lógica temporal unaria TL[-3] (que solo utiliza el operador "estrictamente en el pasado").
  2. Esta traducción implica un "estallido" (blow-up) exponencial en el tamaño del programa.
  3. Se utiliza un lema conocido sobre TL[-3]: si una fórmula es satisfacible, existe una cadena testigo de longitud polinómica respecto al tamaño de la fórmula.
  4. Combinando la traducción exponencial y el límite polinómico de TL[-3], se obtiene un límite de generalización de longitud exponencial para C-RASP+.
• Optimalidad: Se prueba que este límite exponencial es óptimo en el peor de los casos (no se puede mejorar a polinómico).

4. Implicaciones para los Transformers

• Transformadores Generales: Debido a la equivalencia de profundidad-preservación entre C-RASP y los Transformers, el resultado de indecidibilidad se aplica directamente. Esto significa que no existe un algoritmo de aprendizaje que pueda determinar si un Transformer ha visto suficientes datos para generalizar perfectamente a longitudes arbitrarias. La longitud necesaria para la generalización podría crecer más rápido que cualquier función computable.
• Transformadores de Precisión Fija: Si se restringe la precisión dentro del mecanismo de atención (fixed-precision), el modelo cae en la clase C-RASP+. En este caso, la generalización de longitud es posible, pero requiere ver cadenas de entrenamiento de longitud exponencial respecto al tamaño del modelo (precisión, dimensión y profundidad).

5. Significado y Conclusión

Este trabajo proporciona una explicación teórica fundamental a las dificultades observadas empíricamente en la generalización de longitud de los modelos de lenguaje actuales:

1. Límites Fundamentales: La dificultad no es solo un problema de optimización o de arquitectura, sino una barrera computacional inherente. En el caso general, la generalización perfecta es teóricamente inalcanzable con garantías finitas.
2. Sensibilidad a Parámetros: La necesidad de longitudes de entrenamiento exponenciales (o incomputables) explica por qué la generalización es tan sensible a la inicialización y a los hiperparámetros; el espacio de búsqueda para encontrar la "hipótesis correcta" que generaliza es extremadamente vasto y complejo.
3. Diferenciación de Modelos: El trabajo distingue claramente entre modelos teóricos ilimitados (incomputables) y modelos con precisión finita (computables pero costosos), ofreciendo un marco para entender por qué ciertas variantes de Transformers (como los de precisión fija) podrían ser más robustos teóricamente, aunque requieran recursos masivos.

En resumen, el paper establece que, para los Transformers generales, no se puede garantizar la generalización de longitud mediante un límite computable, mientras que para versiones de precisión fija, dicha garantía existe pero requiere un costo exponencial en la longitud de los datos de entrenamiento.