From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP

Resumen Técnico: De la expresividad a la complejidad de muestreo: Profesores estrechos para Transformers mediante C-RASP

Planteamiento del problema
Si bien la investigación teórica ha caracterizado extensamente la expresividad de los modelos Transformer —específicamente qué tareas pueden codificar en sus pesos utilizando marcos como RASP y C-RASP—, existe una brecha significativa en la comprensión de la aprendibilidad de estas capacidades. El trabajo existente determina mayoritariamente qué tareas están dentro de la clase de hipótesis de los Transformers, pero deja abierta la cuestión de cómo se adquieren tales soluciones expresivas durante el entrenamiento. Este artículo aborda el desafío de cerrar la brecha entre los resultados de expresividad y los límites de la complejidad de muestreo, investigando específicamente cómo los Transformers aprenden a implementar construcciones de C-RASP.

Metodología
Los autores se basan en el análisis reciente del paisaje de pérdida, específicamente en el marco propuesto por Buzaglo et al. [3] y Chiang et al. [4], que postula que la generalización en el aprendizaje profundo es impulsada por el volumen de soluciones "buenas" en el paisaje de la pérdida. La metodología central consiste en:

1. Marco Profesor-Estudiante: Los autores definen una red de "profesor estrecho" ($h^*$) que implementa perfectamente un programa C-RASP específico. Luego, consideran una red de "estudiante ancho" ($h$) con dimensiones (ancho y profundidad) mayores que las del profesor.
2. Conteo de Restricciones: La contribución técnica central es un argumento de conteo de restricciones. Los autores demuestran que una red estudiante ancha puede implementar un profesor estrecho imponiendo restricciones específicas a sus parámetros para anular activaciones "interferentes" mientras preservan la lógica del profesor en un subconjunto de sus dimensiones.
3. Supuesto de Q-Cuantización: El análisis asume modelos de precisión fija donde todos los parámetros están restringidos a un conjunto finito $Q$ (Q-cuantizado). Esto permite el cálculo de la probabilidad de muestrear aleatoriamente un modelo "equivalente al profesor" (TE) a partir de un prior uniforme.
4. Integración de C-RASP: El artículo utiliza C-RASP (Counting-RASP), una variante del lenguaje RASP capaz de compilar lógica de conteo temporal en Transformers de softmax sin restricciones de longitud de entrada. Los autores mapean la complejidad estructural de un programa C-RASP (profundidad $n$, número de variables $m$) a las dimensiones requeridas de un Transformer para implementarlo.

Contribuciones Clave
El artículo realiza dos contribuciones principales:

1. Extensión del Marco de Buzaglo a los Transformers: Los autores extienden el marco de "profesor estrecho" a las arquitecturas Transformer. Proporcionan una derivación rigurosa que muestra cómo las redes estudiante anchas pueden incrustar profesores estrechos, calculando el número exacto de restricciones de parámetros ($M$) necesarias para asegurar que el estudiante se comporte idénticamente al profesor en la distribución de datos.
2. Puente entre Expresividad y Aprendibilidad: Este trabajo es uno de los primeros en transformar los resultados de expresividad (lo que los Transformers pueden hacer) en resultados de complejidad de muestreo (cuántas muestras se necesitan para aprender lo que pueden hacer). Al derivar límites basados en la probabilidad de muestrear un modelo TE, los autores establecen que si un programa C-RASP puede ser implementado por un Transformer estrecho, un Transformer más ancho puede aprenderlo con una complejidad de muestreo específica.

Resultados
El principal resultado teórico (Teorema 2.1) proporciona un límite superior en la complejidad de muestreo $N$ requerida para aprender un programa C-RASP con alta probabilidad.

• Límite de Complejidad de Muestreo: Para un programa C-RASP de profundidad $n$, con $m$ variables, implementado por un profesor de una sola cabeza de ancho $2m + c$, un Transformer estudiante de profundidad $L \ge n$ y ancho $d \ge 2m + c$ requiere:
  $$N \ge O\left(\frac{1}{\varepsilon} L d \log Q\right)$$
  muestras para lograr un riesgo real menor a $\varepsilon$ con una probabilidad de $1-\delta$.
• Comparación con la Navaja de Occam: Los autores señalan que este límite ($O(Ld)$) es más ajustado que los límites derivados de argumentos tipo Navaja de Occam, que típicamente producirían $O(Ld^2)$.
• Aplicación de Ejemplo: El artículo ilustra el teorema utilizando el lenguaje Dyck-1 (paréntesis balanceados). Para un programa con $n=7$ operaciones y $m=9$ variables, la complejidad de muestreo derivada es $O(Ld/\varepsilon)$, demostrando que las construcciones de tamaño constante son teóricamente aprendibles por los Transformers.

Significancia y Reivindicaciones
El artículo afirma proporcionar un "marco simple pero principista" para derivar límites de complejidad de muestreo para Transformers aprovechando los resultados de expresividad existentes. Su significancia radica en:

• Avance Teórico: Es el primer trabajo en estudiar la aprendibilidad de C-RASP en Transformers a través de la lente de la complejidad de muestreo, yendo más allá del análisis estático de expresividad.
• Explicación de la Aprendibilidad: Los resultados arrojan luz sobre por qué ciertas construcciones de tamaño constante (como Dyck-1 y $a^nb^n$) son fácilmente aprendidas por los Transformers, atribuyéndolo a la existencia de "profesores estrechos" dentro del paisaje de pérdida que las redes anchas pueden muestrear aleatoriamente.
• Modestia y Limitaciones: Los autores declaran explícitamente que el trabajo es preliminar. Reconocen una falta de validación empírica sobre cómo el volumen del paisaje de pérdida impacta la generalización de longitud en Transformers o Modelos de Espacio de Estados (SSM). Además, señalan que los límites de probabilidad actuales para el muestreo de un modelo TE podrían potencialmente ajustarse, ya que el enfoque actual solo contabiliza una codificación del profesor dentro del estudiante.

El artículo concluye que, si bien establece una vía teórica desde la expresividad hacia la aprendibilidad, se necesita trabajo futuro para validar estas hipótesis basadas en el paisaje de forma empírica y para refinar los límites de probabilidad.