La compensación del paralelismo: Limitaciones de los transformadores de precisión logarítmica

William Merril
Centro de ciencia de datos de Nueva York
Universidad, Nueva York, Nueva York, EE.UU
willm@nyu.edu

Ashish Sabharwal
Instituto Allen para la IA
seattle, Washington, EE.UU
ashishs@allenai.org

Abstracto

A pesar de su omnipresencia en la PNL moderna,
caracterizando el poder computacional de
Las redes neuronales transformadoras siguen siendo de interés.-
pregunta abierta. Probamos que los transformadores
cuya precisión aritmética es logarítmica en
el número de tokens de entrada (y cuyo alimento-
Las redes de protección son computables utilizando el espacio lineal en
su aporte) Puede ser simulado por profundidad constante.
circuitos de umbral uniforme en el espacio logarítmico. este profesional-
proporciona información sobre la potencia de los transformadores
utilizando resultados conocidos en la teoría de la complejidad. Para
ejemplo, si l (cid:2)=P (es decir., no todos los problemas poli-tiempo-
Los problemas se pueden resolver usando el espacio logarítmico.),
entonces los transformadores ni siquiera pueden resolver con precisión
igualdades lineales o comprobar la pertenencia a una
gramática arbitraria libre de contexto con vacío
producciones. Nuestro resultado
emerge intuitivamente
del alto nivel de la arquitectura del transformador-
alelizabilidad. Introducimos así especulativamente
la idea de un comercio de paralelismo fundamental-
apagado: cualquier arquitectura modelo tan paralelizable como
el transformador obedecerá limitaciones similares
lo. Dado que el paralelismo es clave para entrenar mod-
els a escala masiva, esto sugiere un potencial
Debilidad inherente del paradigma de escala..

1

Introducción

en grande

avances recientes

Este trabajo tiene como objetivo caracterizar el sistema computacional.
modelo implícito en redes neuronales transformadoras
(Vaswani et al., 2017), que forman la base
idioma
de
modelos como BERT (Devlin et al., 2019), T5
(Rafael y col., 2020), y GPT-3 (Brown y cols.,
2020). ¿Qué primitivas computacionales puede
Implementación de los componentes del transformador., y qué
Problemas que el sistema completo puede resolver en conjunto.?
Estas preguntas son importantes para interpretar
transformadores de forma basada en principios, comprensión
limitaciones potenciales de su capacidad de razonamiento-
corbatas, y generar confianza en el transformador implementado-
sistemas basados ​​en.

Trabajos teóricos iniciales sobre transformadores.-
estableció su integridad Turing, aunque con
supuestos como precisión infinita y arbitrariamente

531

potentes subredes de avance (P´erez et al., 2019;
Dehghani et al., 2019). Por otro lado, una hebra
de trabajos más recientes utiliza técnicas de cir-
Teoría de la complejidad de Cuit para derivar fuertes limitaciones.
sobre los tipos de problemas que los transformadores pueden resolver
dadas restricciones sobre la forma de atención permitida
en el transformador. Específicamente, Hahn (2020)
y Hao et al.. (2022) mostró que se transforma-
Los que se limitan a prestar mucha atención son muy limitados.:
Sólo pueden resolver problemas en una comunidad débil.-
clase de complejidad (AC0 no uniforme) eso ni siquiera
Contiene problemas básicos como la mayoría de n bits..
Merrill y otros. (2022) Extendió esto a un nivel más general.
clase de transformadores de "atención saturada" con una
tipo de datos de punto flotante, y mostró una clase más grande
de problemas (TC0 no uniforme) como límite superior.
Esto motiva a analizar un escenario que impacta
término medio: ¿Podemos caracterizar los transformadores?
cuya precisión y cálculo de redes de avance-
El poder nacional está realmente limitado., pero donde
La atención también es realista y expresiva.?

Una limitación práctica importante de estos anteriores
resultados es la naturaleza "no uniforme" de la convención.-
clases de circuito consideradas, lo que hace que estas clases
no realizables y los hallazgos son difíciles de implementar.-
Él esta asustado. Esto se debe a que AC0 y
TC0, aunque muy limitado en el cálculo, también
contienen algunos problemas que ni siquiera están decididos-
capaz, es decir., para el cual no existe ninguna exacta
algoritmo. De este modo, las clases no uniformes no pueden ser
comparado directamente con la comunicación algorítmica estándar-
clases de complejidad como P, notario público, etc.. esto motiva
nuestra segunda pregunta clave: ¿Podemos derivar uniforme?
límites superiores en transformadores?

Mostramos que se pueden lograr ambas cosas.
objetivos haciendo la modesta suposición de que todos
los valores en el transformador tienen O(iniciar sesión sustantivo, masculino—) el producto-
sión (donde n es el número de tokens de entrada),
y, similarmente, las subredes de ese transformador son
computable en O(iniciar sesión sustantivo, masculino—) espacio. La precisión del registro es
suficiente para representar las codificaciones posicionales en
la capa de entrada del transformador, y codificar
punteros a todas las demás posiciones en la secuencia en

Transacciones de la Asociación de Lingüística Computacional, volumen. 11, páginas. 531–545, 2023. https://doi.org/10.1162/tacl a 00562
Editor de acciones: Daniel Gildea. Lote de envío: 8/2022; Lote de revisión: 12/2022; Publicado 6/2023.
C(cid:3) 2023 Asociación de Lingüística Computacional. Distribuido bajo CC-BY 4.0 licencia.

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

capas transformadoras posteriores. Suponiendo precisión logarítmica
en todas las capas captura la idea de que lo oculto-
Las representaciones den contienen un número constante de
estados ocultos cuya precisión (16 o 32 bits) es
pequeño en relación con la longitud de la entrada (2048 en
GPT-3). En secuencias largas, la precisión no
ser suficiente para codificar sin pérdidas la entrada completa se-
secuencia en un solo vector. En cambio, el procesamiento
de la secuencia debe de alguna manera distribuirse en
cada capa y realizado en paralelo.

Límite superior en transformadores. Nuestro principal
contribución es demostrar que la transmisión de precisión logarítmica-
Los formadores pueden simularse mediante una constante uniforme.-
circuitos de umbral de profundidad. De este modo, tales transformadores
sólo puede resolver problemas en uniforme TC0. Este
La caracterización es sorprendentemente débil en comparación con la
Turing-completitud de trans de precisión infinita-
formadores. Dado que creemos que la precisión logarítmica es más
realista para transformadores prácticos que infinito
precisión, estos resultados apuntan a la conclusión
eso
Los transformadores no son Turing-completos en
práctica.

A diferencia de resultados pasados, nuestro límite superior en
Los transformadores son una clase de circuito uniforme., habilitando
comparación directa de transformadores de precisión logarítmica con
muchas clases de complejidad natural. Estos se conectan-
revelan problemas específicos que definen la parte superior
límites de las capacidades de los transformadores de precisión logarítmica,
como se analiza más adelante en el §2.

nuestro

dice

atado

Intuitivamente,

eso
superior
Los transformadores de precisión logarítmica son computacionalmente
poco profundo, y eso
la superficialidad puede ser
este
entendido como surgido de su paralelización.
El paralelismo inherente de los transformadores es útil para
entrenándolos eficientemente a escala masiva, pero puede
limitar la complejidad de los cálculos que
puede expresar. Introducimos el término paralelismo.
compensación para capturar esta idea, que representa
una potencial debilidad fundamental del actual
paradigma de modelos de lenguaje escalable. Formalmente
caracterizar las capacidades de razonamiento relevantes para
modelos de lenguaje y comprender si
probablemente caigan fuera de los límites superiores implícitos en el
La compensación aclararía las implicaciones prácticas.
de esta limitación de escala.

Seguimiento de instrucciones y transformación de consejos-
ers. También consideramos una instrucción siguiente
configuración (Brown y cols., 2020) donde el transformador
Se proporciona la descripción de una tarea junto con un
entrada en la que ejecutar la instrucción. Nosotros estafamos-
construir un transformador prácticamente parametrizable
que puede ejecutar instrucciones perfectamente si son
proporcionado en forma de circuitos TC0. esta com-
Complementa trabajos recientes que estudian los transformadores.
capacidad de seguir otras formas de instrucciones como
como expresiones regulares (Finlayson et al., 2022).

Basado en la propiedad fundamental de que trans-
Los formadores pueden evaluar correctamente cualquier TC0 dado.
circuito en una entrada dada, Introducimos la noción de
Transformadores de consejos similares a Turing que toma consejos
máquinas. Demostramos que los transformadores pueden reconocer-
personalizar cualquier (no uniforme) Idioma TC0 si se proporciona
consejos de politamaño apropiados.

En resumen, nuestros hallazgos aportan novedades-
la mirada tanto en las capacidades como en las limitaciones
de transformadores, y resaltar la precisión limitada,
cálculos de umbral, y el paralelismo como clave no-
ciones para comprender el proceso computacional implícito
modelo de transformadores en la práctica.

Mapa vial. Antes de profundizar en los detalles técnicos,
Discutimos en el §2 las implicaciones de nuestros resultados.
tanto en habilidades fundamentales como prácticas
de transformadores. §3 proporciona una breve introducción a cir-
cuits como modelo de computación. Luego se discute
una forma de serializar un circuito en una cadena; nosotros luego
mostrar cómo generar tales serializaciones utilizando un
algoritmo limitado por recursos, cual es la clave para
Probando la contención de transformadores en uniforme.
clases de circuito. §4 define nuestro modelo formal de
transformadores de precisión limitada. §5 deriva nuestra
Primer compromiso formal sobre transformadores de precisión logarítmica..
Este límite involucra familias de circuitos no uniformes.,
similar en espíritu a resultados anteriores en esta área. §6
demuestra nuestro resultado principal más técnico: la primera
Límite superior de complejidad de circuito uniforme para trans-
formadores (específicamente, uniforme TC0). Finalmente, §7
proporciona un límite inferior para los transformadores, introducción-
duce la noción de un transformador de asesoramiento, y
los conecta con los problemas de aprendizaje automático
de instrucción, aprendizaje y seguimiento.

También podría ser que las limitaciones de par-
El alelismo no es una maldición sino una bendición., si ellos
restringir el espacio de hipótesis de una manera útil para
aprendiendo. No tenemos pruebas de que esto sea cierto.,
pero menciónelo como una interpretación alternativa de la
resultados que podrían aclararse en futuros trabajos.

2 Implicaciones de nuestros hallazgos

Antes de profundizar en los detalles técnicos, discutimos
las implicaciones generales de nuestros hallazgos sobre la
Habilidades y limitaciones de los transformadores.. Lo haremos
Centrarse aquí en nuestro resultado principal. (Teorema 2), cual

532

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

muestra que los transformadores de precisión logarítmica están en el
clase de complejidad logspace-uniforme TC0.

La compensación del paralelismo. Una interpretación
de clases de complejidad como NC0, AC0, y
TC0 son conjuntos de problemas que se pueden resolver en múltiples tiempos y que
son paralelizables en un grado muy alto:
se puede resolver en paralelo en tiempo constante con
suficientes procesadores paralelos. Esto da algo de-
explicación intuitiva de nuestro resultado: precisión logarítmica
Los transformadores terminan en TC0 porque fueron
diseñado para ser altamente paralelizable. Desde por-
El alelismo es una propiedad importante de
de hoy
paradigma dominante de los modelos de entrenamiento en mas-
escala sive,
esto lleva a la conclusión de que
cualquier modelo ampliado masivamente (transformador o
de lo contrario, probablemente obedecerá restricciones similares a
los derivados aquí para la transformación de precisión logarítmica-
ers. Por tanto, existe un importante equilibrio entre
La paralelización masiva de las redes actuales.
y su poder de representación.

Qué pueden o no pueden calcular los transformadores.
Nuestro resultado coloca a los transformadores de precisión logarítmica en
logspace-uniforme TC0.
la clase de complejidad
Esto tiene implicaciones inmediatas sobre los tipos
de problemas que tales transformadores pueden y no pueden
resolver con precisión.

Considere cualquier problema X que esté completo para un
clase de complejidad C que contiene logspace-uniform
TC0. Por definición de integridad, cada problema-
Los transformadores de precisión logarítmica pueden resolver perfectamente
es eficientemente reducible a X y por lo tanto no es más difícil
que X. Esto implica que, a pesar de su enorme
tamaño: el cálculo realizado por dicha trans-
formadores es, por ejemplo, no es más difícil que resolver
Problemas básicos L-completos como conexión gráfica.-
idad: el problema de comprobar si existe una
camino entre dos nodos en un gráfico no dirigido
(Lewis y Papadimitriou, 1982; Reinoro, 2008).
De la misma manera, si C es estrictamente mayor que
logspace-uniforme TC0,
entonces tales transformadores
no puede resolver perfectamente X. De este modo, precisión logarítmica
Los transformadores no pueden resolver perfectamente lo siguiente.
problemas de razonamiento:

• Igualdades lineales: encontrar x st. hacha = b1
• Reconocimiento universal sin contexto1,2

• Satisfabilidad proposicional (SE SENTÓ)3

• Satisfacibilidad de la cláusula de cuerno (BOCINA-SAT)1

• Planificación de IA (Tierras de la ciudad, 1991)

• Computación permanente4

Esto resalta los límites de los transformadores prácticos.
con aritmética de precisión limitada, Indicando que
están lejos de ser universales o todopoderosos
como lo sugieren algunos estudios previos.

Una advertencia importante sobre estas re negativas-
resultados es que son de naturaleza asintótica:
solicitar un tamaño de entrada “suficientemente grande” n. Es posible-
Es posible que los transformadores de precisión logarítmica resuelvan tales problemas.
problemas fácilmente cuando n es pequeño. Más, estos
Los resultados negativos se refieren a soluciones exactas., pero
a menudo también se extienden más allá cuando se trata de acuerdos formales.
Se conocen los resultados de dureza de aproximación..

Limitaciones de nuestro modelo formal. Antes de-
Las malas caracterizaciones de los transformadores hacen
suposiciones irrealmente fuertes (P´erez et al.,
2019; Dehghani et al., 2019) o lugar poco realista
restricciones (Hahn, 2020; Hao y cols., 2022;
Merrill y cols., 2022). A diferencia de, hacemos solo
una suposición, a saber, todos los valores intermedios
en el transformador están limitados a O(iniciar sesión sustantivo, masculino—) bits,
donde n es el número de tokens de entrada. nosotros el siguiente
discutir algunas implicaciones de esta suposición y
Qué significan nuestros hallazgos para los transformadores prácticos.
Como se ha mencionado más arriba, nuestros límites son asintóticos
en la naturaleza y por lo tanto se aplican cuando n es suficientemente
grande. En la práctica, Los transformadores utilizan precisión fija.-
sión en cada nodo de cálculo, Cual es más
restrictivo que el crecimiento de precisión con la entrada
longitud de secuencia sustantivo, femenino—, como O(iniciar sesión sustantivo, masculino—) bits. Sin embargo,
esta constante podría ser grande y por lo tanto, para rel-
ativamente pequeño sustantivo, masculino—, nuestros resultados no descartan
Transformadores prácticos que resuelven problemas difíciles..
Nuestros resultados, sin embargo, Demuestre que a medida que n crece
suficientemente largo, Los transformadores de precisión logarítmica son
fundamentalmente limitado a problemas dentro de TC0
y no puede resolver con precisión varios problemas comunes
problemas estudiados mencionados anteriormente en "¿Qué
Los transformadores no pueden calcular''. Ampliando nuestra
El análisis a n pequeño ayudará a cerrar la brecha con
práctica.

1Suponiendo TC0 uniforme en el espacio de registro (cid:2)=P. Sigue porque

3Suponiendo TC0 uniforme en el espacio de registro

(cid:2)= NP. Sigue

estos problemas son P-completos (Greenlaw et al., 1991).

2Toma tanto una gramática como una cadena como entrada y retorno.
si la gramática genera la cadena. Jones y Laaser
(1976) demostrar integridad P.

porque el SAT es NP-completo (cf. Beere et al., 2009).

4Suponiendo TC0 uniforme en el espacio de registro (cid:2)=#P. sigue ser-
porque permanente es #P-completo (Valiente, 1979). alender
(1999) muestra permanente no está en logtime-uniforme TC0.

533

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Nuestro modelo formal se basa en una clasificación binaria.-
vista catiónica de transformadores. Sin embargo, nuestros resultados
aplicar directamente a la clasificación de clases múltiples también
y puede extenderse a problemas de generación mediante
visita, por ejemplo, Predicción de la siguiente palabra en PNL
como un problema de clasificación de clases múltiples. Sin embargo,
si se permite que el decodificador del transformador acondicione
en su producción anterior en un problema de generación,
entonces esto violaría nuestra configuración formal.

2.1 Aplicaciones potenciales

Extracción de circuitos de transformadores. Elhage
et al. (2021) proponer extraer circuitos5 que
capturar la estructura computacional de la transformación-
ers. Nuestros resultados sugieren familias de circuitos de umbral.
son un buen formalismo para expresar mecanismos
extraído de transformadores. Constructivamente-
Convertir transformadores a circuitos de umbral está más allá
El alcance del presente documento., aunque esperamos
explorar esto con más detalle en trabajos futuros.

Pruebas de candidatos de separación en complejidad
Teoría. Teorema 2 también motiva un paradigma
para probar rápidamente conjeturas de la teoría de la complejidad.
Si se cree que existe un problema que separa TC0 y
NC1, Se puede entrenar a un transformador sobre el problema.
instancias. Si el transformador se generaliza perfectamente.
a instancias más difíciles de las que fue entrenado, este
da una pista empírica de que el problema está en TC0,
proporcionando evidencia contra la conjetura.

3 Computación de circuitos

Dejar {0, 1}∗ sea el conjunto de cadenas binarias finitas. Para
x ∈ {0, 1}∗, dejar |X| ser su longitud. Nos referimos a un
función de {0, 1}∗ a {0, 1}∗ como función booleana-
ción. Las funciones booleanas pueden implementar aritmética
operaciones si definimos una semántica para binario
cadenas como números. Trataremos el intermedio.
valores en un transformador como cadenas binarias, y el
operaciones internas como funciones booleanas.

Los circuitos son un modelo de cálculo para com-
poner funciones booleanas de binario de longitud fija
cuerdas.6 Formalmente, un circuito es un acíclico dirigido
gráfico de cálculo. Los nodos de hoja representan bi-
variables binarias y sus negaciones. El interno
los nodos representan funciones en algún conjunto G, y el

5Su sentido de “circuito” no es exactamente el formal.
sentido que utilizamos en este artículo, aunque el objetivo de capturar
El mecanismo computacional implícito de los transformadores es el mismo..
6Para ver un minitutorial sobre la teoría de la complejidad de los circuitos y sus

relevancia para los transformadores, ver Merrill et al.. (2022).

Los bordes dirigidos representan el flujo de función hacia afuera.-
pone en entradas de otras funciones. Uno o mas
Los nodos del circuito están marcados de manera que sus
El valor es la salida del circuito..
Definición 1. Para un conjunto de funciones G, un circuito G
es un gráfico de cálculo acíclico dirigido donde
los nodos internos tienen etiquetas de G.

Medidas de complejidad. El tamaño de un circuito es
el número total de puertas en él, incluyendo la negación.
La profundidad de un circuito es la longitud del más largo.
ruta desde cualquier nodo de entrada a cualquier nodo de salida.

Familias de circuitos. Una familia de circuitos se generaliza.
un circuito para tomar cadenas binarias de longitud variable como
aporte. Formalmente, una familia de circuitos es una secuencia
de circuitos Cn : {0, 1}norte → {0, 1} para norte ∈ norte.
Una familia de circuitos reconoce implícitamente una
lenguaje definido de la siguiente manera:

Definición 2. Una familia de circuitos Cn reconoce L ⊆
{0, 1}∗ si, para todo x ∈ {0, 1}∗, C|X|(X) = 1 si y
sólo si x ∈ L.

Ahora definimos clases de idiomas por con-
forzar la complejidad de las familias de circuitos
necesario reconocerlos:

Definición 3. Sea AC0 no uniforme el conjunto de
L ⊆ {0, 1}∗ tal que L es reconocible por un poli-
tamaño, profundidad constante {¬, ∧, ∨}-familia de circuitos.

Para k ∈ norte, una puerta umbral θ≤k toma m entrada
(cid:2)
metro
i=1xi≤k. Definimos
bits y devuelve si
θ≥k de manera análoga. Por ejemplo, θ≤3(110011) = 0.

Definición 4. Sea TC0 el conjunto de L ⊆ {0, 1}∗
tal que L es reconocible por un poli-tamaño,
profundidad constante {θ≤k, θ≥k}k∈N-circuito.

Las puertas ¬, ∧, y ∨ son solo casos especiales
de umbrales, entonces podemos imaginar circuitos TC0 para
tener acceso a estos también. De este modo, circuitos TC0
puede implementar circuitos AC0.

Serialización de circuitos. Identificamos un circuito con
su serialización en un lenguaje formal que identifica
la etiqueta de cada nodo y la lista de adyacencia. Lo haremos
adoptar una gramática específica para la concreción, pero
Nuestra construcción se puede adaptar a otras cuerdas.
representaciones de circuitos.

Definimos una serialización de circuito como un recorrido.
de un circuito ordenado por algún tipo topológico.
En esta serialización, nodos de hoja (variables) son
representado por la cadena X. Un nodo interno (puerta)
está representado en notación polaca por la función que

534

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

calcula (Y, O, O no) seguido de una lista de
sugerencias a sus argumentos. Cada argumento &1j de
puerta i codifica (en unario) un puntero indexado a cero
a la puerta j-ésima del circuito, donde j < i. The final node is interpreted as the circuit output. To serialize {∧, ∨}-circuits, we use the follow- ing grammar, where the i parameter is passed through Gate[i] nonterminals to track the index of the gate in left-to-right order: Circuit → Gate[1] Gate[2] · · · Gate[g] Gate[i] → X | NOT Arg[i] Arg[i] → &1j s.t. j < i | Op Arg[i]∗ Op → AND | OR In the Arg[i] rule, we enforce that j < i so that arguments must be pointers to already defined gates. As an example of this serialization language, the circuit for x1 ∨ ¬x2 ∨ x3 is represented as7 X X X NOT &1 OR & &111 &11 By convention (cf. §3), negations in AC0 circuits are usually taken to occur at the beginning of the circuit, rather than after ∧ or ∨ nodes.8 Our seri- alization grammar does not enforce this property, but of course any circuit with this property can be serialized by our grammar. It is a bit more complicated to serialize threshold circuits. Formally, a threshold circuit serialization is generated by the following grammar: Circuit → Gate[1] Gate[2] · · · Gate[g] Gate[i] → X | Dir 1k0m−k Arg[i]m Arg[i] → &1j s.t. j < i Dir → <= | >=

En la regla de reescritura de Gate[i], m ∈ N es la aridad
de la puerta, y k ≤ m es su umbral. El lapso de 1k
después de Dir puede interpretarse semánticamente como unario
codificación del parámetro k para una puerta umbral,
rellenado con 0 hasta el número total de argumentos
de la puerta i. Por simplicidad, imaginamos que las puertas son
representado como puertas unarias θ≤0. De este modo, el circuito
θ≥1(x1, ¬x2) sería representado como

X X <= 00 &1 >= 10 & &11

7Espacios aquí (y en la gramática) se agregan para lectura-
capacidad. Ignoraremos estos espacios al pasar por el circuito.
serializaciones como entradas a un transformador en la Sección 7.

8Podemos aplicar las leyes de De Morgan para forzar cualquier circuito AC0.

tener esta propiedad.

535

Uniformidad. Las familias de circuitos que tenemos-
Las multas anteriores no son uniformes., lo que significa que nosotros
no haga cumplir que los circuitos que procesan dif-
Los diferentes tamaños de entrada deben estar relacionados de alguna manera..
En casos degenerados, familias de circuitos no uniformes
pueden resolver problemas indecidibles9 porque
tener una longitud de descripción infinita, haciéndolos un
modelo de computación físicamente irrealizable.
Los teóricos de la complejidad han introducido así la uni-
formar familias de circuitos. Las familias de circuitos uniformes son
un modelo realizable de computación con relaciones
a clases de complejidad computacional y formal
teoría del lenguaje.

Intuitivamente, en una familia de circuitos uniforme, el circuito-
Los cortes para diferentes tamaños de entrada deben ser "algo
similares entre sí. Formalizamos esto (cf.
Arora y Barak, 2009) diciendo que existe
una máquina de Turing con recursos limitados que mapea
la entrada 1n a una serialización del circuito Cn.

Definición 5. Una lengua L es (S(norte), I(norte))-espacio
uniformemente computable mediante un modelo de circuito M iff
existe una máquina de Turing que, para todo norte ≥
0, utiliza S(norte) espacio para asignar 1n a un circuito M
reconocer L en entradas de tamaño I(norte).

Esta noción de uniformidad es más general que
la noción estándar en el sentido de que el tamaño de entrada I(norte) es un
función de la complejidad del problema f. La razón
para esto es que aplicaremos uniformidad a subcom-
putaciones con diferentes tamaños de entrada I(norte) Dentro de un
cálculo más grande del tamaño de entrada n. El estandar
la noción de uniformidad corresponde a I(norte) = norte.

Además, Nos referiremos a una familia de circuitos.
como uniforme si es uniformemente computable con
S(norte) =O(iniciar sesión sustantivo, masculino—) (cf. Arora y Barak, 2009).
Podemos definir versiones uniformes de AC0 y TC0.
adoptando exactamente las definiciones anteriores, pero
también haciendo cumplir la uniformidad. Para el resto del documento
Aclararemos si nos referimos al uniforme o
variante no uniforme de TC0 cuando no está claro a partir de
contexto, ya que ambas clases surgirán.

4 Transformadores de precisión limitada

un transformador (Vaswani et al., 2017) es un nuevo-
arquitectura de red ral formada por una constante
número de capas del transformador. un transformador
La capa es un módulo que calcula la autoatención.

9Considere el lenguaje unario 1n tal que la máquina de Turing
norte (bajo alguna enumeración arbitraria) se detiene. Este problema es
en AC0 no uniforme ya que podemos codificar la respuesta correcta
para cada n en Cn.

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

sobre una secuencia seguida por un elemento
transformación de los vectores de salida.

4.1 Precisión y espacio

Supondremos que cada transformador es un recurso.
acotado en términos de la precisión de cada valor que
calcula y, para algunos de nuestros resultados, el espacio
usos para el cálculo de operaciones clave como
incrustar, atención, y activación. Específicamente,
asumiremos precisión p, es decir., los valores en absoluto
capas, así como las salidas de todos los intermedios clave.
operaciones en el (atención, activación, aritmética
operadores, etc.), se representan usando p bits. Este
es una suposición realista ya que, en la práctica, de hoy
Los transformadores suelen estar limitados a 64 bits.
precisión del hardware subyacente. Formalmente,
definimos la precisión p de la siguiente manera:
Definición 6. Una función k-aria f : x1, . . . , xk (cid:12)→
y es p-precisión si x1, . . . , xk, y ∈ {0, 1}∗ tener
tamaño como máximo p bits, y f se puede calcular mediante a
Máquina de Turing con espacio p limitado.

Esto dice el tamaño de

la entrada de función
y la salida están limitadas por debajo de p. Similarmente,
el espacio intermedio utilizado por el cálculo
también debe estar acotado por debajo de p. De este modo, mayor pre-
Los cálculos de decisión no se pueden ocultar de alguna manera.
dentro f .

Definición 6 naturalmente se aplica a funciones con
aridad limitada k. También necesitaremos definir
p precisión para el operador de suma en el
transformador, que suma n flotadores diferentes de tamaño
p.10 Agregar n flotadores puede aumentar la precisión
necesario para representar su suma. Por ejemplo, imagen-
ine sumando los puntos flotantes 1 · 20 + 1 · 2c. Nosotros
obtener (2C + 1) · 20, cuya mantisa toma c + 1
bits para representar. En la práctica, las computadoras no
preservar la precisión total en tales situaciones: en cambio,
términos pequeños como 1 · 20 son descartados. De este modo, nosotros
definir la operación de suma del transformador ⊕
ser igualmente aproximado (y así preservar
precisión); ver un.

4.2 Definición de transformador

4.3 Cabezas de atención

El componente central de un transformador es un
cabeza de atencion. Definimos esto en un alto nivel de
abstracción de la siguiente manera:

10Nuestra prueba también se realiza si el transformador pesa

son números enteros, como a veces se hace (Dettmers et al., 2022).

536

Definición 7. Se especifica un cabezal de atención de precisión P.-
ificado por una función de similitud binaria de precisión p
s : {0, 1}pag × {0, 1}pag → {0, 1}pag.

Sea h1, . . . , hn ∈ {0, 1}p sea la secuencia de entrada
a un cabezal de atención de precisión p, y deja ⊕ ser
suma aproximada de punto flotante (§A).
Definición 8. Para todos (cid:3) ≥ 0, una atención de p-precisión
∈ {0, 1}pag vía
cabeza h (cid:2)+1

calcula un vector a(cid:2)+1
yo

h

a(cid:2)+1
yo =

norte(cid:3)

j=1

s(h(cid:2)
i, h(cid:2)
j)
Día

·h(cid:2)
j,

(cid:4)

j).

norte
j=1 s(h(cid:2)

donde Zi =

i, h(cid:2)
Cabezales de atención de transformadores estándar (Vaswani
et al., 2017) son un caso especial de esta definición
donde s es la similitud escalada del producto escalar entre
claves y consultas. Los transformadores estándar también tienen
una función de valor lineal o afín aplicada a cada
h(cid:2)
j en la suma sobre j. Por su afinidad, el valor
la función puede, sin pérdida de generalidad, ser re-
Se apartó de la cabeza de atención y consideró
ser parte de la capa transformadora (es decir., aplicado a la
salida del cabezal de atención).

4.4 Capas de transformador

Una capa de transformador de precisión p es entonces una tupla de
cabezas y una función f usada para combinarlas.

Definición 9 (capa de transformador de precisión p). A
La capa del transformador de precisión p es una tupla L.(cid:2)+1 =
(cid:14)H1, · · · , HK, F (cid:15), donde cada Hh es una atención
cabeza y f : ({0, 1}pag)k× {0, 1}pag → {0, 1}p es un
función de activación de precisión p.

1, . . . , h(cid:2)

Una capa de transformador de precisión p puede ser un-
entendido como definir una secuencia de vectores
h(cid:2)+1
, . . . , h(cid:2)+1
en términos de una secuencia de entrada
norte
1
de vectores h(cid:2)
norte (viniendo de la anterior-
capa viscosa en el transformador) por primera computación
k cabezas de atención en paralelo y luego combinar-
ing su salida usando f . Las primeras k entradas a f
Corresponderá a las salidas del cabezal de atención., y
la entrada adicional es la entrada original del
capa anterior. Recuerde que un(cid:2)+1
es la salida de
yo
cabeza h (cid:2)+1
ih en la entrada h(cid:2) en la posición i. La función
calculado por una capa de transformador se puede describir
formalmente de la siguiente manera.

Definición 10 (Cálculo de la capa de transformador).
Para (cid:3) ≥ 0, un transformador de precisión p
capa
l(cid:2)+1 calcula de forma recurrente la secuencia de salida
h(cid:2)+1
las entradas
1

como una función de

, . . . , h(cid:2)+1

norte

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

norte, dónde, para 1 ≤ yo ≤ norte,

h(cid:2)
1, . . . , h(cid:2)
El componente se calcula de acuerdo con
I , h(cid:2)
yo = f (a(cid:2)+1
h(cid:2)+1
i).

i1 , . . . , a(cid:2)+1

el i

Se puede entender que f encapsula la norma de capa.,
conexiones residuales, y el sub feedforward-
capa de un transformador estándar (Vaswani et al.,
2017). h(cid:2)
i se da a f para permitir la conexión residual-
ciones. Como se menciona en §4.3, f también puede encapsular
la función de valor para cada cabeza.

4.5 Codificador de transformador

Finalmente, definimos un transformador de profundidad d como un
cascada de capas de transformador d:

transformador). A
Definición 11
(precisión p
El transformador de precisión p sobre el alfabeto Σ es un par
que consiste en una incrustación de posición de precisión p
función11 φ : Σ×N → {0, 1}p y una d-tupla de
capas de transformador de precisión p (cid:14)L1, . . . , Ld(cid:15).

Para una función de incrustación de posición φ y w ∈
Σn, sea ​​φ(w) ser la posición transmitida
incrustación de w: para 1 ≤ yo ≤ norte, φi(w) (cid:2) Fi(Wisconsin, i).

(cid:5)

Definición 12 (Cálculo del transformador). A
calcula el siguiente-
transformador
función baja de una cuerda w ∈ Σ∗:

Fi, (cid:14)L1, · · · Ld(cid:15)

(cid:6)

t (w) = (Ld ◦ Ld−1 ◦ · · · ◦ L1)(Fi(w)).

Usaremos n para denotar la longitud de w, y
tome la profundidad del transformador d para fijarla w.r.t. norte.
La entrada al transformador puede así ser
representado con N = n log |S| bits usando un bi-
ninguna codificación para el vocabulario. los circuitos
en secciones posteriores a simu-
nosotros construimos
Los transformadores tardíos también tendrán tamaño de entrada N. .
Supondremos que los transformadores tienen precisión logarítmica.
en relación con el tamaño de la entrada, específicamente,
oh(registro norte )-precisión. Desde |S| está arreglado (típicamente
30000 en la práctica), pensaremos en términos de
oh(iniciar sesión sustantivo, masculino—)-precisión. De este modo, por definición 6, todo
las funciones intermedias de tales transformadores
son computables en O(iniciar sesión sustantivo, masculino—) espacio y salida (en
mayoría) estos muchos bits. Tenga en cuenta que esto es suficiente
precisión para representar codificaciones posicionales y para
cada posición para apuntar a un número constante de otras
valores, pero no hay suficiente precisión para no tener pérdidas
agrupación de toda la entrada en un solo valor.

11Aplicar la noción normal de precisión p a las entradas
afuera {0, 1}∗, imaginamos que los elementos de Σ están codificados como
números enteros ≤ |S| en binario, y los números naturales están representados
como números enteros ≤ n. De este modo, asumimos registro |S| + iniciar sesión norte ≤ p.

537

Relación con los transformadores prácticos. Nuestro
Los transformadores de precisión logarítmica no exigen que
s (Definición 7) yf (Definición 9) seguir
la estructura del transformador. Sin embargo, un alimento para-
red de barrio cuyas operaciones primitivas (p.ej., escalar
multiplicación) se definen sobre O(iniciar sesión sustantivo, masculino—)-tamaño
los números se pueden calcular en O(iniciar sesión sustantivo, masculino—) espacio.
De este modo, transformadores prácticos de precisión limitada
son un caso especial de nuestra transformación de precisión logarítmica-
ers. Esto hace que nuestra configuración sea apropiada para demostrar
límites superiores en transformadores, cual es nuestro principal
contribución.

5 Transformadores de precisión logarítmica como

Circuitos de umbral no uniformes

Primero mostramos que los transformadores de precisión logarítmica pueden
ser simulado por circuitos de umbral no uniformes,
antes de presentar la versión uniforme más técnica-
sión de los resultados en §6. La no uniforme inicial
El resultado amplía los hallazgos de Merrill et al.. (2022),
quien demostró que la atención saturada transforma-
ers12 se puede simular en TC0. Aquí, quitamos
el supuesto simplificador de atención saturada y
otras restricciones sobre el tipo de datos subyacente. En-
lugar, demostramos que nuestro supuesto de precisión logarítmica
es suficiente para demostrar que un transformador puede ser
simulado en TC0 con cualquier función de atención.

Hao y otros. observó que cualquier función booleana
de O(iniciar sesión sustantivo, masculino—) Los bits pueden ser calculados por un poli.(norte)
circuito de tamaño. Extendemos esto a salidas de m bits.,
que es más conveniente y más eficiente
que construir m circuitos booleanos separados:

Lema 1 (Ampliado de Hao et al., 2022). Dejar
F : {0, 1}∗ → {0, 1}m ser una función. Para todos
c ∈ R+ y n ∈ N, existe un Y/O
circuito de tamaño como máximo nc + c iniciar sesión sustantivo, masculino— + m y profundidad
3 que calcula f en entradas de tamaño c log n.

Prueba. Como Hao y otros. (2022), construimos un
circuito que utiliza una representación DNF de f en las entradas
de tamaño c log n, excepto que usamos un DNF combinado
representación para todos los bits de salida de f . El abandono
la fórmula tiene como máximo 2c log n = nc términos. El circuito
tiene una puerta NOT para cada bit de entrada, un Y
puerta para cada término DNF, y, para cada uno de los m
bits de salida, una puerta OR que combina las salidas
de esas puertas Y (es decir., Términos de abandono) para cual
esa parte es 1.

12La atención saturada es una atención uniforme sobre un subconjunto de

los nodos de la capa anterior.

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ahora usamos Lema 1 para demostrar lo siguiente
resultado no uniforme. Observamos que la prueba va
incluso si la noción de precisión p (Definir-
ción 6) está relajado para no requerir computabilidad en
espacio pag. Este requisito, sin embargo, convertirse
importante para nuestro resultado posterior en §6.

Teorema 1 (No uniforme). Cualquier c log n-precisión
transformador de profundidad d que opera en entradas en Σn puede
ser simulado por una familia de circuitos de umbral de profundidad
3 + (9 + 2d⊕)d.

el

entrada de

Prueba. Sea w ∈ Σn
a
transformador de precisión c log n. Nosotros
mostrar por
inducción de que podemos construir una composición
de profundidad constante, circuitos de umbral de tamaño múltiple para
calcular cada capa de este transformador. De este modo, cualquier
El transformador de profundidad constante será computable por
un circuito de umbral de profundidad constante.

En el caso base de la capa 0 y token yo, nosotros estafamos-
puertas de estructura que representan la constante i codificada en
binario. Entonces podemos calcular h0
yo = f(Wisconsin, i) usando
Lema 1, produciendo un circuito de profundidad 3 de tamaño polivinílico.

i

i, h(cid:2)

i, h(cid:2)

En el caso inductivo de la capa informática h(cid:2)+1
para 1 ≤ (cid:3) + 1 ≤ d, observamos que cada salida vectorial
de capa h(cid:2)
tengo talla (a lo sumo) c log n bits porque
del supuesto de precisión logarítmica.
Primero arreglamos una cabeza(cid:2)+1
I

(Definición 8) a
simular. Aplicando el lema 1, podemos calcular
s(h(cid:2)
j) con un circuito de profundidad 3 de tamaño polivinílico, en par-
alelo para todos j. Dado que n flota con precisión c log n
se puede agregar aproximadamente en TC0 (§A), podemos
construir un circuito TC0 de profundidad d⊕ para calcular
j), Día, yh(cid:2)
Zj. desde s(h(cid:2)
todos tengo c log n
s(h(cid:2)
i ,h(cid:2)
j )
h(cid:2)
j con un tamaño poli
bits, podemos calcular
Día
circuito de profundidad 3;13 Hacemos esto en paralelo para todos los j..
Próximo, volvemos a utilizar el hecho de que el anuncio aproximado-
La condición de n flotadores está en TC0 para calcular un(cid:2)+1
yo como el
suma aproximada sobre j con un circuito de profundidad d⊕.
(Definición 10)
en términos de sus jefes constituyentes. Dado que todos discuten-
Los elementos de g tienen tamaño c log n., aplicamos el lema 1 a
calcular g con un circuito de profundidad 3 de tamaño polivinílico, producir-
ingh(cid:2)+1
. Repetimos esto en paralelo para todos los i.. Este
completa el paso inductivo nuevo para calcular todos
valores en el (cid:3) + 1-primera capa con una profundidad de circuito de
9 + 2d⊕.

Ahora simulamos una capa h(cid:2)+1

i

i

Agregando el circuito en todas las d capas., el

La profundidad total del circuito es 3 + (9 + 2d⊕)d.

13Esto puede parecer contradictorio ya que la multiplicación de
dos números de n precisión están fuera de AC0. Sin embargo, Aquí nosotros
aprovechar el hecho de que la precisión es c log n.

538

Corolario 1.1 (No uniforme). Cualquier precisión logarítmica
El transformador se puede simular mediante un método no uniforme.
Familia de circuitos TC0.14

6 Transformadores de precisión logarítmica como
Circuitos de umbral uniforme

Ahora ampliaremos el argumento del último
sección para mostrar que O(iniciar sesión sustantivo, masculino—)-transformación de precisión-
ers pueden ser simulados por uniforme de profundidad constante
circuitos de umbral aprovechando el supuesto-
ción que φ, s, y f son de precisión logarítmica, y así puede
calcularse en O(iniciar sesión sustantivo, masculino—) espacio. La prueba general
la idea es similar, pero debido a la condición de uniformidad,
la prueba se vuelve sustancialmente más técnica.
No debemos simplemente mostrar la existencia de un umbral
familia de circuitos que calculan un transformador, pero también
Demuestre que esta familia de circuitos puede generarse mediante
una máquina de Turing en el espacio logarítmico.

Primero ampliamos el Lema 1 respetar la uniformidad:
Lema 2. sea ​​f : {0, 1}∗ → {0, 1}Seré un
función computable en espacio lineal. Existe
una máquina de Turing que, para todo n ∈ N y c ∈ R+,
utiliza como máximo c log n + log m espacio para asignar la entrada
1n a un circuito de tamaño como máximo nc + c iniciar sesión sustantivo, masculino— + metro
y profundidad 3 que calcula f en entradas de tamaño en
la mayoría de c iniciar sesión n.

Prueba. Damos la prueba en forma de algo.-
ritmo para construir un circuito en función de n y
luego justifique su corrección y complejidad espacial.

Algoritmo. Primero imprimimos 2c log n nodos
que representan nodos de entrada negados y no negados.15
Ahora, Necesitamos mostrar cómo construir nodos.
correspondiente a términos nc DNF. Para tal fin, nosotros
recorrer todas las entradas posibles x ∈ {0, 1}c iniciar sesión n por
manteniendo la representación binaria c log n bits
de x (inicializado con 0c log n) e incrementándolo
por 1 en cada paso del bucle. Creamos un nuevo ∧
nodo i con argumentos c log n, definido de la siguiente manera.
Para j ∈ [c iniciar sesión sustantivo, masculino—], creamos un puntero de argumento
a (no negado) nodo j si xj = 1 y para (negado)
nodo c registro n + j de lo contrario.

14Aquí, una familia de circuitos TC0 es una profundidad constante, tamaño poli
familia de circuitos que calculan alguna función {0, 1}∗ → {0, 1}∗.
Mientras definimos TC0 para problemas de decisión en Definición 4,
es estándar y está bien definido extender el mismo término
para referirse a familias de circuitos y funciones informáticas
(Hesse, 2001).

15Ignoramos los nodos de entrada iniciales no negados cuando

considerando el tamaño del circuito.

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ahora, construimos nodos que calculan cada uno de los
m nodos de salida. Hacemos un bucle sobre k ∈ [metro], construir-
haciendo un solo nodo para cada k. Recorremos todo
x ∈ {0, 1}c log n de manera análoga arriba para construir
una lista de argumentos. Por nuestra com de espacio lineal-
supuesto de putabilidad y porque x tiene c log n
bits, podemos calcular f (X) como una subrutina en
oh(iniciar sesión sustantivo, masculino—)-espacio para obtener fk(X). si joder(X) = 1, nosotros
imprimir nodo 2c log n + j como argumento del nodo k.

Exactitud. Demostramos que esta máquina de Turing
asigna la entrada n a un circuito serializado que calcula f
en entradas de tamaño n. La primera capa simplemente produce
valores de entrada negados y no negados. El segundo
La capa luego produce todos los términos DNF posibles.. Finalmente,
el nodo k de la tercera capa calcula la disyunción
sobre todos los términos x tales que fk(X) = 1. De este modo, nodo
k de la tercera capa calcula fk.

Espacio de registro. Para completar la prueba, nosotros justificamos
que M usa O(iniciar sesión n+log m) espacio. dando vueltas
x ∈ {0, 1}c log n se logra tratando x como
un número binario inicializado a 0 e incrementando
eso en cada paso. De este modo, el puntero de bucle para construir
los términos DNF ocupan espacio c log n para almacenarse. Para
construyendo los m nodos de salida, mantenemos un similar
puntero de bucle así como un índice k ≤ m, tomando
c iniciar sesión sustantivo, masculino— + log m espacio. De este modo, el algoritmo general
utiliza c iniciar sesión n + log m espacio.

De este modo, M usa c log n + log m espacio para mapear 1n
a un circuito de tamaño como máximo nc + c iniciar sesión sustantivo, masculino— + m y
profundidad 3 que calcula f en entradas de tamaño c log n.

Podemos aprovechar este lema para derivar la

análogo uniforme del teorema 1, como sigue.

resultado). Cualquier
Teorema 2
(Uniforme, principal
c log n-precisión profundidad-d operación del transformador-
El funcionamiento de entradas en Σn se puede simular mediante un
familia de
circuito de umbral uniforme en el espacio logarítmico
profundidad 3 + (9 + 2d⊕)d.

Prueba. Proporcionaremos una prueba por inducción sobre
capas de transformador (cid:3) que hay una máquina de Turing
M operando en O(iniciar sesión sustantivo, masculino—) espacio que, en la entrada 1n,
genera un circuito que simula el funcionamiento del transformador.
cálculo de entradas de tamaño n. Este circuito es
idéntico al de la demostración del teorema 1, y
por lo tanto tiene la misma profundidad de circuito.

En el caso base, Usamos el espacio de registro para rastrear un
contador que mantiene el token actual i (entre
1 y N) durante toda la construcción del circuito. Nosotros
construir puertas que codifiquen la constante i en binario.

Luego podemos aplicar el Lema 2 construir un Tur-
máquina que mapea 1n a una profundidad constante
cálculo del circuito umbral h0

yo = f(Wisconsin, i).

En el caso inductivo, asumimos que podemos generar
en O(iniciar sesión sustantivo, masculino—) espaciar un circuito calculando cada valor
h(cid:2)
en la capa anterior (cid:3). mostraremos que
i
podemos, en O(iniciar sesión sustantivo, masculino—) espacio, ahora genera un circuito
calcular cada valor en la capa (cid:3) + 1.

Como en el teorema 1, Primero arreglamos una cabeza.(cid:2)+1
yo

simular. Recordar (Definición 8) eso

a

a(cid:2)+1
yo =

norte(cid:3)

j=1

s(h(cid:2)
i, h(cid:2)
j)
Día

·h(cid:2)
j.

i, h(cid:2)

Por Lema 2, Podemos generar un circuito de profundidad 3.
de tamaño como máximo z = nc(cid:17)
+ C(cid:17) iniciar sesión sustantivo, masculino— + 1, dónde
C(cid:17) = 2c (ya que la entrada a f es de tamaño 2c log n)
que calcula s(h(cid:2)
j) para yo específico, j. Hacemos
esto secuencialmente para 1 ≤ j ≤ n y 1 ≤ h ≤ k,
Rellenar cada circuito con nodos no utilizados para que
cada uno tiene talla exactamente z, y el nodo z-ésimo
corresponde a la salida. De este modo, los índices de
los nodos de salida para cada una de las columnas serán
w(cid:2) + z(jk + h) para 1 ≤ j ≤ norte, donde w(cid:2) es el
índice del último nodo de salida h(cid:2)
n de la anterior
capa.

En este punto, utilizamos el hecho de que para p = c log n,
la suma aproximada de precisión p de n precisión p
Los números se pueden calcular mediante un umbral uniforme.
circuito (§A). Por tanto, podemos utilizar una máquina de Turing como
subrutina para generar, en la entrada 1n, un umbral k
circuitos, donde cada uno tiene tamaño z(cid:17) que calcula un
⊕ puerta sobre n elementos de precisión p cada uno. Establecimos
las entradas del circuito h serán nodos w(cid:2) + z(jk +
h) para 1 ≤ j ≤ norte. Por construcción, esto produce
j),
las constantes de normalización Zi =
cuyo valor se encuentra en el nodo en el índice w(cid:2) +
znk + z(cid:17) para la cabeza h.

norte
j=1 s(h(cid:2)

i, h(cid:2)

(cid:4)

i, h(cid:2)

Uso de circuitos de operadores aritméticos de precisión p,
ahora también podemos generar un circuito para calcular
s(h(cid:2)
i ,h(cid:2)
j )
j para cada uno 1 ≤ j ≤ n y 1 ≤ h ≤ k,
h(cid:2)
Día
usando el índice w(cid:2) + z(jk + h) como antes para el
j) y el índice w(cid:2) + znk + z(cid:17)h
valor de s(h(cid:2)
para la constante de normalización Zi de la cabeza h. Aquí
También utilizamos circuitos de idéntico tamaño z.(cid:17)(cid:17), haciendo
w(cid:2) + k(zn + z(cid:17) + z(cid:17)(cid:17)i) el índice de la salida
nodos de estos n circuitos. Próximo, empleamos nuevamente un
⊕ circuito de tamaño z(cid:17), similar al cálculo de
Día, para calcular la suma de estos n valores. Finalmente,
calculamos h(cid:2)+1

aplicando f vía Lema 2.

i

Tenga en cuenta que esto requiere mantener sólo (cid:3), i, y N

en memoria, cada uno de los cuales toma O(iniciar sesión sustantivo, masculino—) bits.

539

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Repetimos este proceso para todos. 1 ≤ yo ≤ n a
calcular el total (cid:3) + 1 capa, que termina el
paso inductivo: si podemos generar un circuito computacional
capa (cid:3) en O(iniciar sesión sustantivo, masculino—) espacio, entonces podemos hacer lo mismo
para capa (cid:3) + 1.

Porque la profundidad derivada del teorema 2 es

constante con respecto a n, resulta que:

Corolario 2.1 (Uniforme, resultado principal). Cualquier
El transformador de precisión logarítmica se puede simular mediante
una familia de circuitos TC0 uniforme.

7 Límites inferiores para la instrucción

Seguimiento y asesoramiento de transformadores.

Hasta ahora, Hemos demostrado que el TC0 uniforme es un
límite superior para transformadores de precisión logarítmica. Es
este límite superior apretado, es decir., también un límite inferior?
Si bien no respondemos a esta pregunta aquí, nosotros
abordar una pregunta relacionada como primer paso: nosotros estafamos-
Construir un transformador que pueda evaluar circuitos TC0.
en entradas binarias, demostrando que los transformadores pueden
calcular cualquier función TC0 cuando su entrada es
aumentado con las “instrucciones” correctas.

Más formalmente, consideramos el valor del circuito
Problema (CVP) (escalera, 1975), también referido
como el problema de evaluación del circuito, donde la entrada
es un circuito booleano C y una cadena x ∈ {0, 1}norte, y
la tarea es devolver el valor de C(X) ∈ {0, 1}.
Se sabe que este problema está completo para el
clase P bajo reducciones AC0 (escalera, 1975). Nosotros
asumirá que C está serializado como se describe en §3 y
demostrar que los transformadores de precisión logarítmica pueden evaluar
cualquier circuito TC0. Tenga en cuenta que esta es una extensión de
el CVP típico ya que el circuito tiene un umbral
puertas, no sólo puertas estándar Y/O.

Se sabe que los LSTM no pueden evaluar Bool-
fórmula ean (Merril, 2020), un caso especial del
CVP. A diferencia de, demostramos que los transformadores pueden.
Para demostrar la practicidad de nuestro sistema inferior.
construcción encuadernada, no solo probaremos el
existencia de transformadores que puedan evaluar TC0
circuitos, sino que también especifican opciones concretas para
esquema de incrustación posicional y la clase de
funciones de atención que son suficientes para hacerlo.

Incrustaciones posicionales fraccionarias. por una vez-
dejar (cid:14)X, y(cid:15) ser el vector
tor x y escalar y,
añadiendo y a x.16 Para σ ∈ Σ, deja v(pag) ser
la codificación one-hot de σ en R|S|. Para w ∈ Σ∗,

16Es decir., (cid:14)X, y(cid:15)yo = xi para 1 ≤ yo ≤ |X|, y y si i = |X| + 1.

definimos la incrustación posicional fraccionaria en
token yo como

Fi(Wisconsin, i) = (cid:14)v(Wisconsin), en(cid:15).

i , h(cid:2)

Atención saturada. Nos imaginamos f (h(cid:2)
j) es
calculado a través de atención saturada (cf. Merrill y cols.,
2022), que proporciona un modelo simple de los tipos
de atención que podemos esperar
ser aprendido en
transformadores (Merrill y cols., 2021). Primero, consultas
se calculan como qi = Qh(cid:2)
i, y luego llaves
kj = Kh(cid:2)
j. Definir la atención del producto punto
puntuación σij = q(cid:18)
yo kj. Entonces podemos definir saturado
atención como

(cid:7)

s(h(cid:2)

i, h(cid:2)

j) =

1 si σij = maxk σik
0 de lo contrario.

Después de la normalización, La atención saturada crea una
distribución que es uniforme sobre un subconjunto de posiciones-
ciones. De este modo, es capaz de parametrizar duro
atención, Atención uniforme durante toda la secuencia.,
y varios patrones de atención en el medio.

Funciones de agrupación simples. Por simplicidad, nosotros
asumir que las funciones de agrupación f tienen un umbral lineal
funciones de sus entradas. De este modo, Ellos pueden ser
implementado por una red neuronal feedforward. Sin
pérdida de generalidad, dejamos que las cabezas de atención tengan
una función de valor, que se puede plegar en el
función de agrupación de la última capa (ver §4).

Ahora, Estamos listos para presentar el resultado principal..
Nuestra construcción a continuación es específica del circuito.
esquema de serialización discutido en §3, pero puede ser
extendido a otras serializaciones también.

Lema 3. para todos d, existe un transformador
con incrustaciones posicionales fraccionarias, saturado
atención, funciones de agrupación lineal con umbral,
y profundidad 2d que, para cualquier circuito umbral C de
profundidad d, entrada de mapas (cid:14)C, X(cid:15) al valor C(X).

Prueba. Construiremos un par de dos transformadores.
capas que evalúan todos los nodos en profundidad (cid:3) en
el circuito umbral, para cualquier (cid:3). De ello se deduce que un
transformador de profundidad 2d puede calcular el valor
C(X).

Nos referimos a un token de tipo X como nodo de entrada..
Similarmente, A un token de tipo Dir lo llamamos nodo de puerta..
Finalmente llamamos a un token de tipo & un argumento.

Caso base: Nodos de entrada. Construimos uno en-
capa de tensión que atiende uniformemente sobre todo
posiciones cuyo valor regresa 1 si wi = X y
0 de lo contrario. De este modo, esta cabeza calcula #(X)/norte,

540

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

dónde #(X) es el número de apariciones de X en
w. Luego definimos una segunda capa que, en la entrada
nodo i, recupera el token en la posición j definida por

j =

1 − #(X) + i
norte

.

j es el índice del i-ésimo valor de entrada. De este modo, después
esta capa, cada nodo de entrada i almacena su valor xi.

En el caso base, también construimos una atención
dirígete a eso, en el iésimo nodo de puerta, cuenta la fracción
de nodos (fuera de n) que son nodos de puerta a la izquierda
del nodo actual. De este modo, este cabezal calcula i/n.
También en el nodo de puerta i, construimos una cabeza de atención
que cuenta la fracción de nodos a su derecha antes
el siguiente & nodo que tiene valor 1. Esta cabeza así
tiene valor ki/mi donde ki es el valor umbral
de la i-ésima puerta y mi es su aridad. Aplicamos el
misma construcción en cada argumento & para contar el
1que siguen hasta el siguiente símbolo distinto de 1.

Finalmente, usando la primera capa de atención, tenemos
cada nodo J atiende al primer símbolo de argumento
& a su izquierda y recuperar su índice j/n. Entonces, en
la segunda capa de atención, cada argumento asiste
uniformemente en todos los nodos con valores j/n. La red
El efecto es que cada nodo de argumento almacene j/n., es decir.,
el puntero que está codificando en unario como &1j.

Caso inductivo: Nodos de puerta. Por nuestro inductivo
suposición sobre capas anteriores, todos los tokens corren-
correspondiente a nodos de circuito a una profundidad ≤ (cid:3) contener
su valor apropiado. ahora construimos 2 trans-
capas anteriores para evaluar los nodos de la puerta en profundidad
(cid:3) + 1.

En la primera capa de atención., cada argumento j
atiende al nodo de puerta más cercano i a su izquierda,
cual es la puerta a la que pertenece. Recordar de la
caso base en el que el argumento j ya almacena j/n. Cada
argumento &0j atiende con la tecla de posición j/n a
nodo de puerta j y recupera su valor en el anterior
capa.

La segunda capa de atención se aplica en los nodos de puerta.,
no argumentos. En la puerta i de arity mi, fijamos el
atención f(i, j) para indicar si el argumento j
pertenece al nodo de puerta i, que es válido exactamente para m
argumentos. Establecemos el valor de atención como el
valor binario del referente del argumento j. De este modo,
la cabeza de atención calcula ci/mi, donde ci es
el número de argumentos del nodo i que son 1. Nosotros
repita esto para todos los nodos de puerta.

En este punto, para el i-ésimo nodo de puerta, tenemos
calculado tanto ci/mi como ki/mi. Umbral
(ci - ki)/mi en 0 nos permite decidir, Residencia en

si Dir es <= or >=, si la puerta actual
El nodo debe generar un 0 o un 1. Repitiendo esto para todos.
puertas en capa (cid:3) + 1 completa el paso inductivo:
Podemos evaluar todos los nodos de puerta en esta capa..

Teorema 3. Los transformadores de profundidad 2d pueden resolver
CVP para circuitos TC0 de profundidad d.

7.1 Instrucciones siguientes

CVP está estrechamente relacionado con el aprendizaje por instrucción.
(Brown y cols., 2020) y seguir instrucciones
tareas (Finlayson et al., 2022). La última tarea
La configuración proporciona un transformador de dos entradas.: un habitual
expresión r como una "instrucción", y z ∈ {0, 1}∗.
El objetivo de la tarea es determinar si z pertenece
al lenguaje regular representado por r. Visto
desde esta lente, la configuración de evaluación del circuito pregunta:
¿Pueden los transformadores seguir las instrucciones proporcionadas en
la forma de un circuito? Como se analiza a continuación, nuestro
El resultado dice que la respuesta es sí para todas las constantes.
circuitos de umbral de profundidad. Este, a lo mejor de nuestro
conocimiento, proporciona la primera baja no trivial
con destino a transformadores en la instrucción aprendizaje
configuración.

Formalmente, una instrucción I es cualquier descripción17
de una función fI de {0, 1}∗. decimos trans-
El primero sigue correctamente una instrucción I si, para
todo x ∈ {0, 1}∗, calcula correctamente fI (X) en
aporte (cid:14)I, X(cid:15). Una descripción de instrucción no uniforme.-
ción es una familia de descripciones de longitud específica
{En}∞
norte=1. Decimos que un transformador sigue correctamente
una familia de instrucción no uniforme {En} si, para todos norte
y todo x ∈ {0, 1}norte, calcula correctamente fI (X) en
aporte (cid:14)En, X(cid:15). La descripción no uniforme {En}
puede tomar cualquier forma. Cuando forma un circuito TC0
familia, Nos referimos a ella como una descripción de instrucción TC0.-
ción. Desde el teorema 3 construye un transformador
que puede evaluar cualquier circuito TC0, resulta que:

Corolario 3.1. Existe una trans de profundidad 2d.-
primero que puede seguir correctamente cualquier TC0 de profundidad
descripción de la instrucción.

De este modo, transformadores con posición simple em-
camas, atención, y las funciones de agrupación pueden
simular cualquier instrucción proporcionada en forma de
un circuito TC0. Observamos que si bien se desconoce
si la clase de lenguajes regulares, consideró
por Finlayson et al.. (2022), está contenido en TC0,
el otro lado es conocido: Hay problemas com-
putable por circuitos TC0 que no son computables

17Formalmente, una descripción de función es un programa de tamaño fijo
calcular esa función bajo algún modelo de cálculo.

541

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

por un lenguaje regular. Estos incluyen problemas en-
conteo volutivo y aritmética, que están más allá
idiomas regulares. Nuestros resultados amplían así la
tipos conocidos de instrucciones que los transformadores pueden
seguir, al menos con pesas hechas a mano.

7.2 Transformadores de asesoramiento

También podemos ver las capacidades de evaluación del circuito.
de transformadores (Lema 3) desde la lente de
máquinas de Turing que toman consejos y que,
en anuncio-
aporte, también se proporcionan
dición a su habitual
una entrada
india-
pendiente) cadena de consejos. Por ejemplo, P/poli es
la clase de problemas decidibles en polinomio
Momento en el que se le da un consejo a la máquina de Turing.
cadena de tamaño polinomio en la longitud de entrada (cf.
Arora y Barak, 2009).

dependiente de la longitud

aporte

(pero

En la misma vena, sea ​​T/poly la clase de
precisión logarítmica, transformadores de profundidad constante con
cadenas de consejos polinómicos. En otras palabras, en
una entrada de tamaño n, permitimos que el transformador
recibir un poli adicional(norte) bits de entrada que
no puede depender de la entrada estándar. Ahora deja
{cn}∞
n=1 sea una familia de circuitos que demuestre que a
El problema está en TC0 no uniforme.. Entonces, pasando
la descripción de Cn como consejo para la longitud de entrada n,
se sigue inmediatamente del Lema 3 ese consejo
Los transformadores pueden simular TC0 no uniforme.:
Corolario 3.2. TC0 no uniforme ⊆ T/poli.

Dado que el TC0 no uniforme incluso contiene algunos
lenguajes indecidibles (Arora y Barak, 2009,
Afirmar 6.8), T/poly es claramente una clase muy poderosa
y un superconjunto estricto de T, la clase de decisión
Problemas reconocidos por los transformadores. (cuales son
todo decidible). De este modo, un problema en T/poly no puede
siempre se soluciona con un transformador solo.
Sin embargo, si se le da una descripción de cómo hacerlo
(''consejo'') en forma de circuito TC0, nuestro resultado
muestra que un transformador podría resolver ese problema.

8 Conclusión

Respondiendo a dos preguntas abiertas de Merrill et al..
(2022), Probamos transformadores de precisión logarítmica con
cualquier (incluyendo suave) La atención se puede simular.
mediante circuitos de umbral uniformes de profundidad constante. Este
establece la suma umbralizada como fundamento-
operación tal para comprender el proceso computacional
modelo de transformadores: Cualquier trans de precisión logarítmica-
El primero se puede reexpresar como un polinomio.
número de puertas de umbral apiladas a una constante

542

profundidad. Este resultado también establece límites potenciales-
se trata del poder computacional de la precisión logarítmica
transformadores; p.ej., si L ⊂ P, los transformadores no pueden
calcular todas las funciones poli-tiempo. son cer-
Ciertamente muy lejos de ser universal.. la intuición
En el centro de este resultado está que forzar un modelo
ser altamente paralelizable probablemente sacrifique su ex-
presividad. Dado que el paralelismo parece esencial para
preentrenamiento de cualquier modelo masivo a escala, cualquier grande
modelo de lenguaje, transformador o no, puede
sufrir una compensación similar.

Expresiones de gratitud

Los autores agradecen los valiosos comentarios.
de los revisores anónimos y del TACL
editor de acciones. También agradecen a Paul Beame y
colegas de AI2, incluido Kyle Richardson,
Michal Guerquín, Peter Clark, Tushar Khot, y
especialmente matthew finlayson, cuyo empírico
Hallazgos sobre la instrucción aprendizaje inspirado §7.
Comentarios de Sam Bowman, Arya McCarthy,
Roma Patel, y Lena Strobl, y discusiones
con el FLaNN, ML para código (MILA), y
Fundamentos del procesamiento del lenguaje (Ume˚a) re-
Los grupos de búsqueda ayudaron a mejorar los borradores anteriores.. El
Los autores también aprecian el feed de Rahul Santhanam.-
atrás. Este trabajo fue financiado en parte por el premio NSF.
1922658. William Merrill contó con el apoyo de un
Beca de investigación de posgrado de NSF y AI2.

Referencias

Eric Allender. 1999. Lo permanente requiere grandes
circuitos de umbral uniforme. Diario de Chicago de
Informática Teórica.

Sanjeev Arora y Boaz Barak. 2009. Com-
Complejidad putacional: Un enfoque moderno.
Prensa de la Universidad de Cambridge. https://doi
.org/10.1017/CBO9780511804090

Cervezas Arin, Marijn Heule, Hans van Maaren, y
Toby Walsh. 2009. Manual de satisfacibilidad:
Volumen 185 Fronteras de la inteligencia artificial
y aplicaciones. Prensa IOS.

Tom Brown, Benjamín Mann, Nick Ryder,
Melanie Subbiah, Jared D.. Kaplan, Prafulla
Dhariwal, Arvind Neelakantan, Pranav Shyam,
Girish Sastry, Amanda Askell, sandhi
agarwal, Ariel Herbert-Voss, Gretchen
krüger, Tom Henighan, niño rewon, Aditya

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Ramesh, Daniel Ziegler, Jeffrey Wu, Clemenes
Invierno, Chris Hesse, Marcos Chen, eric
Sigler, Mateusz Litwin, Scott Gris, Benjamín
Ajedrez, Jack Clark, Christopher Berner, Sam
McCandlish, Alec Radford, Ilya Sutskever,
y Darío Amodei. 2020. Modelos de lenguaje
son aprendices de pocas oportunidades. En avances en neurología
Sistemas de procesamiento de información, volumen 33,
páginas 1877-1901. Asociados Curran, Cª.

Tom Bylander. 1991. Resultados de complejidad para
la interna-
En procedimientos de
planificación.
Conferencia Conjunta Nacional sobre Artificial
En-
inteligencia. https://doi.org/10.1016
/B978-0-08-049944-4.50008-2

Andrés Chiu, Jorge I. David, y Bruce E..
litow. 2001. División en logspace-uniforme nc1.
RAIRO Informática Teórica y Aplica-
ciones, 35:259–275. https://doi.org/10
.1051/ita:2001119

Mostafa Dehghani, Stephan Gows, Oriol
Viñales, Jakob Uszkoreit, y Lukasz Káiser.
2019. Transformadores universales. En internacional
Conferencia sobre Representaciones del Aprendizaje.

Tim Dettmers, mike lewis,

y lucas
Zettlemoyer. 2022. GPT3.int8(): 8-matriz de bits
multiplicación para transformadores a escala. En
Avances en el procesamiento de información neuronal
Sistemas.

Jacob Devlin, Ming-Wei Chang, Kenton Lee, y
Kristina Toutanova. 2019. BERT: Pre-entrenamiento
de transformadores bidireccionales profundos para el lenguaje
comprensión. En Actas de la 2019 Estafa-
el Capítulo Norteamericano de
diferencia de
la Asociación de Lingüística Computacional:
Tecnologías del lenguaje humano.

Nelson Elhage, Neel Nanda, Catherine Olsson,
Tom Henighan, Nicolás José, hombre ben,
Amanda Askell, Yuntao Bai, Anna Chen,
Tom Conerly, Nova Das Sarma, Drenaje del amanecer,
Gangul profundo, Zac Hatfield-Dodds, danny
Hernández, Andy Jones, Jackson Kernion,
Liane Lovitt, Kamal Ndousse, Dario Amodei,
Tom Brown, Jack Clark, Jared Kaplan, Sam
McCandlish, y Chris Olah. 2021. una matematica-
Marco emático para circuitos de transformadores..
Hilo de circuitos de transformadores.

Mateo Finlayson, Kyle Richardson, Ashish
Sabharwal, y peter clark. 2022. ¿Qué hace?
instrucción aprendiendo duro? una investigación y

un nuevo desafío en un entorno sintético. En
Actas de la 2022 Conferencia sobre el Imperio-
Métodos icales en el procesamiento del lenguaje natural.

Raymond Greenlaw, James M.. Aspiradora, y
Walter L.. Ruzzo. 1991. un compendio de
problemas completos para P. Reporte técnico
TR91-11, Universidad de Alberta.

Michael Hahn. 2020. Limitaciones teóricas de
autoatención en modelos de secuencia neuronal. Trans-
acciones de la Asociación de Computación
Lingüística, 8:156–171. https://doi.org
/10.1162/tackle_a_00306

Yiding Hao, Fondo Angluin, y robert frank.
2022. Reconocimiento formal del lenguaje por duro en-
transformadores de tensión: Perspectivas desde el circuito
complejidad. Transacciones de la Asociación
para Lingüística Computacional, 10:800–810.
https://doi.org/10.1162/tacl a 00490

Guillermo Hesse. 2001. La división es

en la universidad-
formulario TC 0. En el Coloquio Internacional sobre
Autómatas, Idiomas, y programación,
104–114. https://doi.org/10
paginas
.1007/3-540-48224-5_9

Neil Immerman. 2012. Complejidad descriptiva.

Ciencia Springer & Medios comerciales.

Neil D..

jones

y William T.. un láser.
para que usted determine-
1976. problemas completos
tiempo. Computadora Teórica
polinomio tic
Ciencia, 3(1):105–117. https://doi.org
/10.1016/0304-3975(76)90068-2

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Richard E.. escalera. 1975. El problema del valor del circuito-
lem es el espacio logarítmico completo para P. ACM SIGACT
Noticias, 7(1):18–20. https://doi.org/10
.1145/990518.990519

harry r.. Lewis y Christos H.. Papadimitrio.
1982. Cálculo simétrico delimitado por el espacio.
Informática Teórica, 19:161–187.
https://doi.org/10.1016/03045
-3975(82)90058-

William Merril, Vivek Ramanujan, Yoav
Goldberg, Roy Schwartz, y Noé A.. Herrero.
2021. Efectos del crecimiento normal del parámetro durante
entrenamiento transformador: Sesgo inductivo de gra-
descenso de dientes. En procedimientos de
el 2021
Jornada sobre Métodos Empíricos en Natural
Procesamiento del lenguaje. https://doi.org
/10.18653/v1/2021.emnlp-main.133

543

William Cooper Merrill. 2020. sobre lo lingüístico
capacidad de los autómatas contadores en tiempo real. ArXiv,
abs/2004.06866.

William Cooper Merrill, Ashish Sabharwal,
y Noé A.. Herrero. 2022. Trans saturada-
Los formadores son circuitos de umbral de profundidad constante..
Transacciones de la Asociación de Compu-
lingüística nacional, 10:843–856. https://
doi.org/10.1162/tacl a 00493

Jorge Pérez,

Javier Marinkovic, y pablo
barceló. 2019. Sobre la plenitud de Turing
de las arquitecturas modernas de redes neuronales. En
Conferencia Internacional sobre Aprendizaje Repre-
sentaciones.

Colin Raffel, Noam M.. shazeer, Adam Roberts,
Katherine Lee, Sharan Narang, Miguel
mañana, Yanqi Zhou, wei li, y Pedro J.. Liu.
2020. Explorando los límites del aprendizaje por transferencia
con un transformador unificado de texto a texto. Diario
de Investigación sobre Aprendizaje Automático, 21(140).

Omer Reingold. 2008. Conectividad no dirigida en
espacio de registro. Revista de la ACM, 55:17:1–17:24.
https://doi.org/10.1145/1391289
.1391291

leslie g. Valiente. 1979. La complejidad de com-
poniendo lo permanente. Computadora Teórica
8:189–201. https://doi.org
Ciencia,
/10.1016/0304-3975(79)90044-6

Ashish Vaswani, Noam Shazeer, Niki Parmar,
Jakob Uszkoreit, Leon Jones, Aidan N.. Gómez,
lucas káiser, y Illia Polosukhin. 2017. En-
La atención es todo lo que necesitas.. En avances en neurología
Sistemas de procesamiento de información, volumen 30.
Asociados Curran, Cª.

Una adición flotante de precisión p iterada

Interpretamos una cadena x de p bits como un flotante de precisión p
tomando los primeros p/2 bits18 de x como un inicio de sesión-
teger m que codifica la mantisa y el resto
p/2 bits de x como otro entero con signo e codificado-
ing el exponente. Un flotador con mantisa m y
exponer e, denotado (cid:14)metro, mi(cid:15), codifica m · 2e.

Calcular la suma de n enteros de n bits (conocido
como suma iterada o simplemente suma) es
conocido por estar en uniforme TC0 (Hesse, 2001;
a
Chiu et al., 2001). Aprovechamos este hecho

18Suponemos w.l.o.g. que p es par.

lo mismo vale para la suma de n
muestra esa
oh(iniciar sesión sustantivo, masculino—)-flotadores de precisión. Una sutileza de agregar
flotadores de precisión p es que su suma puede requerir
más de p bits para representar con precisión como un flotante.
Por ejemplo, mientras que cada uno de 2r y 1 es representante-
resentido con un (firmado) mantisa de solo 2
bits, su suma exacta, 2r + 1, requires a mantissa
de r + 1 bits. Por eso, transformadores de precisión p
debe sacrificar algo de precisión al realizar
suma.

Definimos la suma de flotadores mapeando los flotadores.
a números enteros, sumando los números enteros exactamente, y luego
mapear la suma nuevamente a un flotador (con posible
= 2q − 1 ser el
pérdida de precisión). Déjame maximizar
q = −I máx.
mayor entero con signo de q bits, y yo min
.
Sea F máx.
ser el mayor valor representable por
un flotador de precisión p. Dado que el exponente de un flotador
φ puede ser negativo y representar una fracción, nosotros
reescalar φ por 2
p/2 al asignarlo a un inte-
gp ger(Fi):

−Yo mínimo

pag

q

q

Definición 13. El mapeo de enteros de un p-bit
flotador φ = (cid:14)metro, mi(cid:15) se define como gp(Fi) = m · 2e−I mín
p/2.

Definición 14. El mapeo flotante p-truncado de
un número entero z se define como fp(z) = (cid:14)metro, mi(cid:15) donde19

m = rdesplazamiento(z, máximo{0, tamaño de(z) −p/2})
e = tamaño de(z) − tamaño de(metro) + Estoy dentro
p/2

cuando e ≤ I máx
establecemos m = e = I max

p/2 ; de lo contrario (es decir., when z > F max
),
p/2 para manejar adecuadamente el desbordamiento.

pag

Definición 15 (Suma flotante iterada de precisión p).
Definimos la suma de k flotadores de precisión p como

(cid:8)

k(cid:9)

(cid:10)

φi = fp

GP(φi)

.

yo=1

k(cid:3)

yo=1

Primero verificamos que Definición 14 de cerca-

suma exacta aproximada.

Lema 4. Sea φ = (cid:14)mi, metro(cid:15) ser un flotador tal que
|Fi| ≤ F máx.
y e ≥ I min
p/2 . Entonces φ y fp(GP(Fi))
difieren en un factor de como máximo 1 ± 2−p/2+2.

pag

Prueba. Sea z = gp(Fi), que está bien definido ser-
causa de la condición previa e ≥ I min
p/2 del lema.
Sea φ(cid:17) = (cid:14)metro(cid:17), mi(cid:17)(cid:15) = fp(z).

19por x (cid:2)= 0, tamaño de(X) = (cid:21)registro |X|(cid:22) + 2; tamaño de(0) = 2.

Para y ≥ 0, cambio de marcha(X, y) desplaza a la derecha x por y bits.

544

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
5
6
2
2
1
3
1
1
9
1

/

/
t

yo

a
C
_
a
_
0
0
5
6
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
9
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Consideremos primero el caso sencillo en el que sizeof(z) ≤
p/2. Entonces m(cid:17) = z y e(cid:17) = yo mínimo
p/2 de Definicion-
ción 14. Dado que z = m · 2e−I min
p/2 por definición 13,
se deduce que φ y φ(cid:17) tener exactamente lo mismo
valor.

pag

Ahora supongamos tamaño de(z) > p/2. Se sigue de
la condición previa |Fi| ≤ F máx.
del lema que
no hay desbordamiento al aplicar Definición 14
computar (cid:14)metro(cid:17), mi(cid:17)(cid:15). Así m(cid:17) consiste en el p/2
bits de orden más alto (incluyendo el bit de signo) de z y
mi(cid:17) = (cid:3) + Estoy dentro
p/2 , dónde (cid:3) = tamaño de(z) − p/2 es el
número de bits truncados desde z para obtener m(cid:17). Dejar
δ denota el (no negativo) número entero formado por el
(cid:3) bits de orden más bajo de z que están truncados. Entonces
re ≤ 2(cid:2) − 1 = 2tamaño de(z)−p/2− 1 < z · 2−p/2+2. −I min Recall that the value of φ is gp(φ) · 2 −I min p/2. By the above argument, we also have that p/2, which is p/2. Thus, φ and φ(cid:17) are z·2 the value of φ(cid:17) is within (z ± δ) · 2 within z · (1 ± 2−p/2+2) · 2 within a factor of 1 ± 2−p/2+2 of each other. p/2 = −I min −I min Finally, we show that, with log precision, computing ⊕ (Definition 14) is in uniform TC0. k Lemma 5. Let p ≤ c log n and φ = i=1 φi, where k ≤ n and each φi is p-precision. Then φ is computable by a constant-depth uniform threshold circuit of size poly(n). (cid:4) Proof. Let N = c log n + 2nc. We first use Lemma 1 to map each φi = (cid:14)mi, ei(cid:15) to the integer zi = mi · 2ei−I min p/2, which has size sizeof(mi) + (ei − I min) ≤ p/2 + 2 · 2p/2 ≤ c log n + 2nc = N . For 1 ≤ i ≤ k, we pad zi to N bits, and for k < i ≤ N , we create an N -bit integer k zi = 0. We can then compute z = i=1 zi with a constant-depth uniform threshold circuit of size poly(N ) using the classical construction to sum N N -bit integers (cf. Immerman, 2012, exercise 5.29). The size of this circuit is also poly- nomial in n by the definition of N . Finally, we compute f †(z) using a constant-depth AND/OR circuit. (cid:2) l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . e d u / t a c l / l a r t i c e - p d f / d o i / . 1 0 1 1 6 2 / t l a c _ a _ 0 0 5 6 2 2 1 3 1 1 9 1 / / t l a c _ a _ 0 0 5 6 2 p d . f b y g u e s t t o n 0 9 S e p e m b e r 2 0 2 3 545
Descargar PDF