Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

1. Planteamiento del Problema

Si bien la indicación de Cadena de Pensamiento (CoT, por sus siglas en inglés) ha mejorado empíricamente el rendimiento de los Transformers y se ha demostrado teóricamente que aumenta su expresividad hasta la Completitud de Turing, persiste una brecha crítica: ¿Pueden los Transformers aprender a generalizar el razonamiento CoT a longitudes mayores que las observadas durante el entrenamiento?

La evidencia empírica existente sugiere que la precisión de los Transformers se degrada drásticamente a medida que aumenta la longitud de la traza CoT, incluso en tareas algorítmicas y lógicas. El artículo investiga si la afirmación teórica de completitud de Turing se mantiene bajo el requisito más estricto de aprendizabilidad generalizable en longitud. Específicamente, se pregunta:

• ¿Permiten los formatos estándar de CoT a los Transformers resolver problemas fuera de la clase de complejidad $\text{TC}^0$ (circuitos umbral de profundidad constante) al generalizar a secuencias más largas?
• ¿Qué barreras estructurales específicas impiden esta generalización?
• ¿Se pueden superar estas barreras mediante estrategias de formato específicas?

2. Metodología

Los autores emplean una combinación de formalismo teórico y validación empírica:

Marco Teórico

El estudio utiliza marcos teóricos recientes para la generalización de longitud en Transformers:

• C-RASP: Un formalismo para razonar sobre Transformers con alfabetos finitos y codificaciones posicionales. La pertenencia implica garantías de generalización en longitud.
• C-RASP:* Una extensión de C-RASP que permite un alfabeto infinito (específicamente, tokens de señalización o signpost no acotados) y predicados de coincidencia local.
• Modelo de Aprendizaje: Los autores adoptan un modelo de aprendizaje idealizado donde una secuencia de Transformers entrenados en longitudes de entrada crecientes converge a un único algoritmo subyacente. La generalización está garantizada si la tarea puede expresarse dentro de estos formalismos.

Configuración Empírica

• Tareas: Se seleccionaron tres tareas de razonamiento algorítmico:
  1. Paridad: Determinar si el número de 1s en una cadena binaria es par o impar.
  2. Evaluación Booleana: Evaluar el valor de verdad de fórmulas lógicas anidadas.
  3. Permutación S5: Rastrear el estado de 5 objetos después de una serie de operaciones de intercambio.
• Modelos:
  • Desde Cero: Modelos GPT-2 (25M parámetros) entrenados en trazas CoT con y sin formatos específicos.
  • LLMs Preentrenados: Experimentos de indicación zero-shot y few-shot en Qwen2.5-7B, Mistral-Small-24B y Llama-3.3-70B.
• Variantes de Formato:
  • CoT Ingenuo: Razonamiento secuencial estándar.
  • Tokens de Señalización (Signpost Tokens): Asignar identificadores únicos (por ejemplo, <34>) a posiciones u operaciones específicas para habilitar el direccionamiento arbitrario.
  • Codificación de Cambios de Valor: En lugar de registrar el estado completo en cada paso, el modelo registra solo los cambios en los valores (por ejemplo, 1 -> 0) o registra explícitamente cuándo un valor permanece sin cambios.

3. Contribuciones Clave y Resultados Teóricos

Contribución 1: El Límite de los Alfabetos Finitos (El Resultado Negativo)

Los autores demuestran que bajo codificaciones posicionales estándar y un alfabeto finito, los Transformers con CoT no pueden generalizar en longitud para resolver problemas fuera de $\text{TC}^0$.

• Teorema 3.4: Si un lenguaje $L$ tiene una traza CoT expresable en C-RASP (con primitivas posicionales), entonces $L$ es definible en $\text{TC}^0$.
• Implicación: Aunque el CoT teóricamente permite la completitud de Turing, la aprendizabilidad de tales simulaciones está acotada por $\text{TC}^0$ si el vocabulario es fijo. Los beneficios de expresividad no se traducen en aprendizabilidad generalizable en longitud.

Contribución 2: Superar Barreras con Alfabetos Infinitos (El Resultado Positivo)

El artículo identifica dos barreras centrales para la generalización en longitud:

1. Copiado Repetido: La dificultad de copiar cadenas arbitrarias a nuevas posiciones.
2. Recuperación de la Última Ocurrencia: La dificultad de recuperar el valor más reciente de una variable cuando ocurren múltiples actualizaciones (recuperación no única).

Para superar esto, los autores proponen una construcción utilizando C-RASP*:

• Tokens de Señalización: Asignar un token único y no acotado (de un alfabeto infinito) a cada posición de la cinta o paso de operación. Esto resuelve la barrera de copiado al permitir la indexación arbitraria sin memorizar identidades absolutas.
• Codificación de Cambios de Valor: En lugar de registrar el estado completo, el CoT registra solo las transiciones (por ejemplo, "el valor cambió de $x$ a $y$"). El estado actual se recupera contando los cambios netos en relación con el estado inicial. Esto resuelve la barrera de recuperación al hacer que el valor actual sea una función de conteos en lugar de una búsqueda de la última ocurrencia.
• Teorema 3.8: Los Transformers con CoT pueden generalizar en longitud para simular cualquier Máquina de Turing si utilizan un alfabeto infinito de tokens de señalización y codifican los cálculos mediante cambios de valor. La longitud de la traza CoT permanece lineal en el tiempo de ejecución simulado.

4. Resultados Empíricos

Entrenamiento desde Cero

• Paridad: El CoT estándar falló al generalizar más allá de las longitudes de entrenamiento. La codificación de cambios de valor permitió una generalización robusta hasta $2\times$ la longitud de entrenamiento.
• Evaluación Booleana y Permutación S5: Estas tareas más difíciles (fuera de $\text{TC}^0$) fallaron con CoT ingenuo. Añadir tokens de señalización mejoró significativamente la generalización en longitud, aunque S5 siguió siendo desafiante debido a posibles "atajos" (heurísticas) que el modelo podría explotar.
• Permutación Binaria: Una variante de S5 con alta repetición. Los CoTs ingenuos y solo con señalización fallaron debido a errores de "recuperación no única". Combinar Señalización + Cambios de Valor produjo los mejores resultados, confirmando la necesidad teórica de ambos mecanismos.

Indicaciones en LLMs Preentrenados

• Señalización: El uso de números naturales como pistas de señalización en indicaciones few-shot mejoró el rendimiento en tareas booleanas y S5 para todos los LLMs probados (de 7B a 70B), especialmente en longitudes de secuencia más largas.
• Cambios de Valor: En una tarea de ejecución de código (rastreo de asignaciones de variables), proporcionar comentarios en línea que registraran explícitamente los cambios de valor (por ejemplo, # nodo a: 9 -> 0) mejoró significativamente la precisión de la respuesta final en comparación con el formato de código estándar, incluso sin pasos de razonamiento intermedios.

5. Significado y Conclusión

• Redefinición del Éxito del CoT: El artículo argumenta que el éxito del CoT no es inherente al proceso de "pensamiento" en sí mismo, sino que depende en gran medida del formato de la traza. Los formatos estándar de CoT a menudo fallan en generalizar porque violan las restricciones requeridas para la aprendizabilidad (localidad e invarianza de traducción).
• Límites Teóricos: Aclara que la completitud de Turing para los Transformers es condicional. Se cumple para la expresividad (codificar una solución a mano) pero no para la aprendizabilidad (entrenar un modelo para generalizar) a menos que se proporcionen ayudas estructurales específicas (alfabetos infinitos/señalización).
• Directrices Prácticas: Los hallazgos ofrecen principios accionables para mejorar el rendimiento de los LLMs en tareas de razonamiento difíciles:
  1. Usar Pistas de Índice: Marcar explícitamente posiciones o pasos con identificadores únicos para ayudar a la recuperación.
  2. Registrar Cambios, No Estados: Formatear las trazas de razonamiento para resaltar las transiciones de estado en lugar de volcados completos de estado para evitar ambigüedades en la recuperación.
• Futuras Direcciones: El trabajo sugiere que los futuros datos de preentrenamiento y esquemas de CoT deben diseñarse teniendo en cuenta estas restricciones teóricas para desbloquear el potencial computacional completo de los Transformers en tareas de razonamiento de largo alcance.

En resumen, el artículo demuestra que, aunque los Transformers son teóricamente capaces de un razonamiento universal, realizar esta capacidad de manera generalizable en longitud requiere superar barreras arquitectónicas y de formato específicas mediante el uso de tokens de señalización y codificaciones de cambios de valor.