Characterizing the Expressivity of Local Attention in Transformers

1. Planteamiento del Problema

La arquitectura Transformer se basa en un mecanismo de atención global, que agrupa información de todos los tokens precedentes, resultando en una complejidad computacional cuadrática ($O(N^2)$). Para mitigar esto, la atención local restringe la agregación a una ventana de tamaño fijo de predecesores, reduciendo la complejidad a lineal ($O(N)$).

Si bien la atención local se motiva principalmente por la eficiencia, estudios empíricos han demostrado que a menudo mejora la calidad del modelo (por ejemplo, en traducción automática y modelado de lenguaje) incluso cuando los presupuestos computacionales se mantienen constantes. Esto presenta un acertijo teórico: ¿Por qué restringir el campo receptivo (un mecanismo aparentemente "más débil") a veces conduce a un mejor rendimiento?

Los autores buscan resolver esto caracterizando formalmente la expresividad de diferentes patrones de atención (global, local e híbrida) en términos de los lenguajes formales que pueden reconocer.

2. Metodología

El artículo emplea un enfoque de teoría de lenguajes formales, conectando las arquitecturas Transformer con la Lógica Temporal Lineal (LTL) y la teoría de autómatas algebraicos.

• Marco Teórico:

  • Los autores analizan los Transformers de precisión fija como reconocedores de lenguajes.
  • Mapean los mecanismos de atención a fragmentos de LTL:
    • Atención Global: Corresponde a LTL[P] (operador Pasado), que permite mirar hacia atrás arbitrariamente lejos pero solo a la existencia de un evento pasado.
    • Atención Local (tamaño de ventana $k$): Corresponde a LTL[$Y_{\le k}$] (operador Ayer Acotado), que verifica si una condición se mantuvo dentro de los últimos $k$ pasos.
    • Atención Híbrida: Corresponde a LTL[P, $Y_{\le k}$], combinando ambos operadores.
  • Utilizan caracterizaciones algebraicas (semigrupos sintácticos, monoides sintácticos) y propiedades teóricas de autómatas (configuraciones de DFA) para probar separaciones estrictas entre estos fragmentos lógicos.

• Validación Experimental:

  • Reconocimiento de Lenguajes Formales: Los autores entrenaron Transformers para reconocer clases específicas de lenguajes formales (por ejemplo, cadenas que terminan en 'a', cadenas que contienen 'ab', lenguajes Dyck acotados) con longitudes variables para probar la generalización.
  • Modelado de Lenguaje Natural: Realizaron experimentos ligeros de predicción del siguiente token en el conjunto de datos WikiText-2 utilizando arquitecturas al estilo de GPT-2-small.
  • Variables: Compararon tres patrones de atención (Solo Global, Solo Local, Híbrido) a través de diferentes tamaños de ventana ($k \in \{1, 2, 4, \dots\}$) y codificaciones posicionales (Aprendida, RoPE, SiPE).

3. Contribuciones Clave

A. Caracterización Teórica

1. Atención Global = LTL[P]: Reafirma que la atención global corresponde a la lógica con un único operador pasado, capaz de reconocer polinomios left-deterministas pero fallando en ciertas tareas basadas en sufijos.
2. Atención Local = LTL[$Y_{\le k}$]: Demuestra que la atención local corresponde a la lógica temporal acotada. Crucialmente, muestran que LTL[P] y LTL[$Y_{\le k}$] son incomparables.
   • La atención global no puede reconocer lenguajes definidos por sufijos específicos (por ejemplo, cadenas que terminan en 'a').
   • La atención local no puede reconocer lenguajes definidos por prefijos específicos (por ejemplo, cadenas que comienzan con 'a').
3. Atención Híbrida = LTL[P, $Y_{\le k}$]: Demuestra que combinar atención global y local amplía estrictamente la clase de lenguajes regulares reconocibles. El modelo híbrido puede reconocer Lenguajes Localmente Testables (un superconjunto de lenguajes definidos), que ni la atención global pura ni la local pura pueden capturar completamente.
4. Optimalidad del Tamaño de Ventana $k=1$: Demuestra teóricamente que dentro de la familia de atención local, un tamaño de ventana de $k=1$ (mirar solo al predecesor inmediato) es estrictamente más expresivo que ventanas más grandes ($k > 1$) cuando faltan codificaciones posicionales. Esto se debe a que $k=1$ introduce el operador "Ayer" ($Y$), que es el operador local más potente.

B. Hallazgos Empíricos

1. Generalización en Lenguajes Formales:

   • Los modelos híbridos (específicamente con $k=1$) lograron una generalización perfecta (100% de precisión) en todos los lenguajes definibles en LTL[P, Y], incluidos aquellos que fallaron para los modelos solo globales o solo locales.
   • Los modelos Solo Global fallaron en tareas basadas en sufijos (LTL[Y]).
   • Los modelos Solo Local fallaron en tareas basadas en prefijos (LTL[P]).
   • Tamaño de Ventana: $k=1$ superó consistentemente a $k=2$ y $k=4$ en ausencia de codificaciones posicionales.

2. Lenguaje Natural (WikiText-2):

   • La atención híbrida con $k=1$ logró consistentemente la menor perplejidad en todos los esquemas de codificación posicional (Aprendida, RoPE, SiPE).
   • La brecha de rendimiento entre los modelos híbridos y los solo globales fue significativa (por ejemplo, una reducción de ~69 puntos de perplejidad bajo incrustaciones aprendidas).
   • Curiosamente, los modelos solo locales a veces superaron a los modelos solo globales, apoyando la teoría de que son complementarios en lugar de que uno sea estrictamente "mejor".

3. Rol de las Codificaciones Posicionales:

   • Las brechas teóricas entre la atención local $k=1$ y $k>1$ pueden cerrarse si las codificaciones posicionales actúan como "predicados modulares" (permitiendo al modelo contar pasos).
   • Sin embargo, en la práctica, las codificaciones estándar (RoPE, SiPE) no compensaron completamente la falta de atención local, y los modelos híbridos permanecieron superiores.

4. Significado

• Resolución de la "Paradoja de la Atención Local": El artículo proporciona la primera explicación formal de por qué la atención local mejora el rendimiento. No es meramente una optimización de velocidad; introduce un sesgo inductivo complementario (la capacidad de rastrear predecesores inmediatos a través del operador $Y$) que la atención global carece.
• Directrices de Diseño: Los resultados sugieren fuertemente que las arquitecturas híbridas (mezclando cabezas globales y locales) son teórica y empíricamente superiores. Además, abogan por usar un tamaño de ventana de 1 para las cabezas locales, ya que maximiza la expresividad capturando el predecesor inmediato sin la sobrecarga de profundidad de ventanas más grandes.
• Puente Teórico: El trabajo solidifica la conexión entre el diseño de arquitecturas neuronales y la lógica formal, ofreciendo una lente rigurosa para predecir las capacidades del modelo en tareas que requieren tipos específicos de dependencias de largo alcance o locales.

En resumen, los autores demuestran que la atención local no es una degradación de la atención global, sino un complemento necesario. Al combinar la visión global (existencia pasada) con la visión local (historia inmediata), los transformers híbridos logran el fragmento más rico de reconocimiento de lenguajes regulares, lo que conduce a un rendimiento superior tanto en tareas formales como en modelado de lenguaje natural.