Average Attention Transformers and Arithmetic Circuits

Resumen Técnico: Transformadores de Atención Promedio y Circuitos Aritméticos

Enunciado del Problema
Los análisis teóricos existentes sobre la expresividad de los Transformadores se han centrado principalmente en problemas de decisión sobre alfabetos finitos, comparando los Transformadores con clases de circuitos booleanos (por ejemplo, $AC^0$, $TC^0$) o formalismos lógicos. Estos resultados se limitan al reconocimiento de lenguajes. Este artículo aborda una brecha en la comprensión del poder computacional de los Transformadores como funciones de secuencia a secuencia que operan sobre vectores de números reales o racionales. Los autores buscan caracterizar la expresividad de los codificadores de Transformadores comparándolos directamente con circuitos aritméticos, que calculan funciones sobre semianillos utilizando operaciones como la suma, la multiplicación y la función de signo.

Metodología
Los autores adaptan un modelo de Transformador generalizado (basado en Hao et al., 2022) para operar sobre semianillos arbitrarios. Las elecciones metodológicas clave incluyen:

1. Definición del Modelo: Definen "transformadores de circuitos de atención promedio", donde las redes neuronales feed-forward estándar son reemplazadas por circuitos aritméticos, y el mecanismo de atención utiliza "atención dura promedio" (atendiendo a todos los vectores con puntuaciones de atención máximas).
2. Familias de Circuitos: Analizan tres clases de familias de circuitos aritméticos con profundidad constante y tamaño polinómico:
   • $FNC^0_R$: Entrada acotada.
   • $FSAC^0_R$: Entrada semi-acotada (suma ilimitada, multiplicación binaria).
   • $FAC^0_R$: Entrada ilimitada (suma y multiplicación ilimitadas).
     Estas clases se extienden con la función sign para manejar operaciones discontinuas.
3. Construcción de la Simulación:
   • Circuitos a Transformadores: Para simular un circuito, los autores codifican la estructura gráfica del circuito (puertas y aristas) en una secuencia de vectores. Cada vector representa una arista o una puerta, conteniendo índices para predecesores/sucesores, tipos de puerta y valores.
   • Mecanismos de Atención: Diseñan funciones de atención específicas ($f^{att}_E$ y $f^{att}_V$) que permiten a los vectores atender a sus predecesores basándose en la coincidencia de índices.
   • Agrupación y Activación: Utilizan la agrupación de atención dura promedio para agregar valores de los predecesores. Crucialmente, construyen funciones de activación que seleccionan la operación apropiada (suma, multiplicación o identidad) basándose en el tipo de puerta codificado en el vector.
   • Manejo de la Escala: Dado que la atención promedio escala los resultados por $1/k$ (donde $k$ es el número de vectores atendidos), la construcción incluye mecanismos para contar predecesores y reescalar la salida para recuperar el valor aritmético correcto.

Resultados Clave
El artículo establece una correspondencia precisa entre el poder computacional de estos Transformadores específicos y las clases de circuitos aritméticos:

1. Límite Superior: Para cualquier semianillo $R$, las funciones calculadas por transformadores de circuitos de atención promedio están contenidas dentro de la clase $FSAC^0_R[\text{sign}]$. Esto se cumple incluso para Transformadores estándar con atención promedio típica, siempre que sus funciones de activación estén restringidas a la misma clase de circuitos.
2. Límite Inferior (Simulación): Si el semianillo subyacente $R$ es una extensión ordenada por $\mathbb{Z}$ de los racionales ($\mathbb{Q}$), entonces para cualquier familia de circuitos en $FSAC^0_R[\text{sign}]$ con profundidad $K$, existe un Transformador con $2K$ capas que puede simular a toda la familia.
   • La simulación funciona para circuitos de entrada ilimitada utilizando atención promedio.
   • Para circuitos de entrada semi-acotada, la construcción puede adaptarse para usar atención estándar de producto punto.
   • Para circuitos de entrada acotada, la construcción puede restringirse aún más para usar atención dura izquierda o derecha.
3. Teoremas Específicos:
   • Teorema 4.5: Un Transformador con dimensión 7 y $2K$ capas puede simular cualquier circuito $R$ de entrada ilimitada de profundidad $\le K$ (donde $R$ es una extensión ordenada por $\mathbb{Z}$ de $\mathbb{Q}$).
   • Teorema 4.11: Un Transformador con dimensión 9 y $2K$ capas puede simular cualquier circuito $FSAC^0_R[\text{sign}]$.

Significado y Afirmaciones
Los autores afirman que sus resultados proporcionan una nueva perspectiva sobre la expresividad de los Transformadores al conectar los campos de la teoría del aprendizaje automático y el cálculo algebraico.

• Equivalencia Teórica: Demuestran que los Transformadores de atención promedio son computacionalmente equivalentes a la clase de circuitos aritméticos de profundidad constante con suma ilimitada, multiplicación binaria y puertas de signo ($FSAC^0_R[\text{sign}]$).
• Limitaciones: El artículo señala explícitamente que esta equivalencia depende de que el Transformador utilice circuitos aritméticos (o funciones equivalentes) como funciones de activación. Los Transformadores estándar con redes feed-forward no pueden simular estos circuitos porque las redes feed-forward no pueden realizar inherentemente la multiplicación de dos entradas arbitrarias requerida para la simulación.
• No Uniformidad: Los autores aclaran que, aunque los Transformadores pueden simular familias de circuitos específicas, esto no implica que cada función en $FSAC^0_R[\text{sign}]$ sea calculada por un solo Transformador, ya que las familias de circuitos son un modelo de computación no uniforme.
• Potencial Futuro: El artículo sugiere que los avances teóricos en el cálculo algebraico podrían beneficiar a la teoría del aprendizaje automático y viceversa, y que los resultados teóricos podrían inspirar desarrollos prácticos, aunque no se proponen aplicaciones específicas.

El trabajo se presenta como un prepublicación (mayo de 2026) del Instituto de Ciencias de la Computación Teórica de la Universidad de Leibniz Hannover.