Resumen Técnico: Distribuciones de Probabilidad Computadas por Transformadores Autoregresivos

Enunciado del Problema

El trabajo teórico existente sobre la expresividad de los transformadores trata predominantemente a los transformadores como reconocedores de lenguaje (clasificadores), donde la entrada es una cadena completa y la salida es una clasificación binaria (aceptar/rechazar). Sin embargo, la aplicación práctica principal de los transformadores es como modelos de lenguaje (autoregresivos), que generan cadenas token a token prediciendo una distribución de probabilidad sobre el siguiente símbolo dado un prefijo.

Este artículo aborda una brecha fundamental: no está claro qué resultados teóricos sobre la expresividad de los transformadores en el contexto de reconocimiento se trasladan al contexto de modelado de lenguaje. Específicamente, los autores investigan si las clases de equivalencia establecidas para los transformadores como clasificadores booleanos (por ejemplo, equivalencia con Lógica Temporal Lineal o autómatas sin contadores) se mantienen cuando los transformadores se utilizan como autoregresivos con pesos reales o booleanos.

Metodología

Los autores desarrollan un marco formal para comparar los transformadores como clasificadores versus autoregresivos en dos dominios de pesos:

1. Semianillo Booleano ($\mathbb{B}$): Los pesos son $\{0, 1\}$ (Falso/Verdadero).
2. Semianillo Real ($\mathbb{R}_{\geq 0}$): Los pesos son números reales no negativos (probabilidades).

Definen un codificador de estados como una función que mapea un prefijo de cadena a una secuencia de estados, donde el estado en la posición $i$ depende únicamente del prefijo $w_{\leq i}$. Utilizando esta abstracción, analizan cuatro configuraciones específicas:

• Clasificadores Booleanos: Mapean una cadena completa a un valor booleano.
• Autoregresivos Booleanos: Mapean un prefijo a una distribución sobre el siguiente token (pesos booleanos).
• Clasificadores Reales: Mapean una cadena completa a un peso real.
• Autoregresivos Reales: Mapean un prefijo a una distribución de probabilidad sobre el siguiente token.

El estudio se centra en Transformadores de Atención Dura Única (UHATs) y Transformadores de Atención Softmax (SMATs) con precisión fija. Estos se comparan con:

• Lógica Temporal Lineal (LTL) y sus fragmentos (por ejemplo, $TL[P]$, $TL[H]$).
• Autómatas Finitos Deterministas sin Contadores (cfDFAs) y Autómatas Finitos No Deterministas sin Contadores (cfNFAs).

La metodología central implica construir reducciones entre estos formalismos para determinar si uno puede simular al otro tanto en modo clasificador como en modo autoregresivo.

Contribuciones y Resultados Clave

1. Equivalencia en Clasificadores Booleanos vs. Autoregresivos

• LTL Completo: En el semianillo booleano, los clasificadores LTL y los autoregresivos LTL son equivalentes. Un transformador actuando como autoregresivo booleano puede definir los mismos lenguajes que uno actuando como clasificador, siempre que la lógica incluya los operadores "Ayer" ($Y$) y "Históricamente" ($H$).
• Complejidad de la Conversión: Aunque son equivalentes, convertir un autoregresivo a un clasificador (específicamente eliminando el operador $Y$) puede requerir un aumento exponencial en el tamaño de la fórmula. El artículo demuestra que es improbable construir una transformación equivalente en tiempo polinómico para ciertos fragmentos, a menos que $P = PSPACE$o$P = NP$.

2. Divergencia en Fragmentos Restringidos (Booleano)

Al restringir el conjunto de operadores temporales (por ejemplo, a $TL[H]$o$TL[P]$ sin $Y$), los autoregresivos se vuelven estrictamente más expresivos que los clasificadores.

• Ejemplo: El lenguaje $(ab)^*$ es definible por un autoregresivo booleano $TL[\emptyset]$, pero no puede ser definido por ningún clasificador $TL[H]$o$TL[Y]$.
• Implicación: Los transformadores con mecanismos de atención específicos (como UHATs de izquierda o SMATs de precisión fija, que corresponden a estos fragmentos) pueden reconocer lenguajes como autoregresivos que no pueden reconocer como clasificadores.

3. Divergencia en Entornos con Pesos Reales

En el semianillo real, el panorama de la expresividad cambia significativamente:

• Clasificadores vs. Autoregresivos: Son incomparables.
  • Existen lenguajes ponderados expresables por autoregresivos reales pero no por clasificadores reales (por ejemplo, $(\frac{1}{2}a)^*$, que requiere infinitos pesos distintos).
  • Existen lenguajes ponderados expresables por clasificadores reales pero no por autoregresivos reales (por ejemplo, $(1a)^*$, que no es una distribución de probabilidad normalizada).
• UHATs y cfDFAs: En el entorno real, los UHATs (y LTL) como autoregresivos son equivalentes a DFA sin contadores. Sin embargo, son estrictamente menos expresivos que los NFA ponderados sin contadores.
  • El artículo demuestra un NFA ponderado sin contadores que no es determinizable (no puede convertirse en un DFA ponderado equivalente), mostrando que el no determinismo en el entorno con pesos reales añade expresividad que los transformadores (modelados como codificadores de estados deterministas) no pueden capturar.

4. Impacto de los Operadores de Conteo

El artículo revisa los resultados sobre transformadores con capacidades de conteo (por ejemplo, SMATs con precisión arbitraria dentro de la atención, equivalentes a $TL[\#]$).

• Trabajos anteriores mostraron que estos transformadores reconocen lenguajes específicos como clasificadores.
• Este artículo muestra que como autoregresivos, estos modelos son ligeramente más potentes, capaces de reconocer lenguajes (como $L_{k+2}$) que no pueden reconocer como clasificadores (limitados a $L_k$). Esto explica las discrepancias entre los límites teóricos de reconocimiento y el rendimiento empírico de predicción de símbolos en la literatura anterior.

Significado y Afirmaciones

El artículo afirma proporcionar una forma principista de interpretar los experimentos existentes sobre la expresividad de los transformadores.

• Validación: En muchos casos (específicamente LTL booleano completo), los resultados de la literatura sobre reconocimiento de lenguajes sí se transfieren a los modelos de lenguaje. Por ejemplo, dado que los UHATs no pueden reconocer la PARIDAD como clasificadores, tampoco pueden hacerlo como autoregresivos.
• Advertencias: Los autores enfatizan que no se puede asumir ciegamente que los resultados de reconocimiento se aplican a la generación.
  • Pesos Reales: El cambio de pesos booleanos a reales rompe las equivalencias encontradas en el caso booleano (por ejemplo, entre DFA y NFA).
  • Autoregresión vs. Clasificación: La autoregresión puede aumentar estrictamente la expresividad en fragmentos lógicos restringidos (booleano) y cambia la clase de lenguajes ponderados expresables (real).
• Direcciones Futuras: Los autores sugieren que el trabajo futuro debería extender estos resultados a la atención softmax de precisión logarítmica, codificaciones posicionales y el razonamiento de "cadena de pensamiento" en entornos con pesos reales, señalando que las técnicas actuales para probar la inexpresividad en autoregresivos son limitadas.

En resumen, el artículo establece que, aunque los transformadores como modelos de lenguaje comparten gran parte de su fundamento teórico con los transformadores como reconocedores, el cambio hacia la autoregresión y las probabilidades de valor real introduce diferencias sutiles pero críticas en la expresividad computacional, particularmente en lo que respecta al poder del no determinismo y a los operadores temporales específicos disponibles.