PaperlayerView exact revision on arXiv

Source-linked AI summary

What Formal Languages Can Transformers Express? A Survey

Lena Strobl, William Merrill, Gail Weiss, David Chiang, Dana Angluin

arXiv:2311.00208v3cs.LGcs.CLcs.FLcs.LO

TL;DR

The paper addresses how to characterize transformer expressivity relative to formal computational models, a question motivated by transformers’ prominence and the diversity of theoretical results. It surveys this literature and unifies its assumptions, finding that architectural choices and computation depth determine substantially different capability and limitation results.

  • Problem

    The central gap is a lack of unified characterization of what transformers can and cannot express as formal-language recognizers or generators relative to automata, circuits, and logic.

  • Method

    The paper provides a comprehensive survey that documents assumptions, formalizes transformer variants, and organizes results using a unified framework.

  • Results

    Unbounded intermediate decoder steps can make transformers Turing-complete, while encoder results range from AC0 limitations for leftmost-hard attention to TC0 containment for softmax and average-hard attention.

  • Takeaways & Limitations

    Expressivity conclusions depend strongly on architectural choices, including attention type, positional encodings, normalization, and special tokens.

  • Takeaways & Limitations

    The effects of several architectural variants on expressivity remain insufficiently clarified, including positional encodings, attention type, normalization, and BOS/EOS/CLS tokens.

Abstract

from arXiv · show

As transformers have gained prominence in natural language processing, some researchers have investigated theoretically what problems they can and cannot solve, by treating problems as formal languages. Exploring such questions can help clarify the power of transformers relative to other models of computation, their fundamental capabilities and limits, and the impact of architectural choices. Work in this subarea has made considerable progress in recent years. Here, we undertake a comprehensive survey of this work, documenting the diverse assumptions that underlie different results and providing a unified framework for harmonizing seemingly contradictory findings.

1 Introduction

This survey examines transformer expressivity through formal language theory, asking how transformers compare with automata, circuits, and logic. It organizes a diverse literature by documenting assumptions and providing a unified framework for apparently contradictory results.

  • 1 Introduction: The survey focuses on expressivity because it is a prerequisite for trainability, while applications such as predicting practical failures remain future work.
  • 1 Introduction: Formal language theory studies transformers as recognizers or generators of unbounded sequences over finite alphabets.This perspective differs from approximation theory, which treats transformers as approximators of function classes.
  • 1 Introduction: The central question is how transformer expressivity relates to formal models such as automata, Boolean circuits, and formal logic.
  • 1 Introduction: The paper provides a comprehensive, transformer-only survey that is narrower but deeper than earlier surveys covering CNNs, RNNs, and transformers.
  • 1 Introduction: A unified framework is needed because theoretical results depend on diverse transformer variants and assumptions, producing seemingly contradictory conclusions.

2 Overview

The surveyed literature divides transformer expressivity results into lower bounds describing what models can do and upper bounds describing what they cannot do. Decoder computation depth, attention discretization, precision, circuits, and logic shape these results.

  • 2 Overview: The survey summarizes these results as lower bounds on capabilities and upper bounds on limitations.
  • 2 Overview: Lower-bound work compares transformers with automata, counter machines, and Turing machines, especially across decoder variants with different numbers of intermediate steps.Allowing intermediate decoder steps can dramatically increase expressive power.
  • 2 Overview: Upper-bound work mainly uses circuit complexity, progressing from restricted transformer encoders toward more realistic variants and tighter bounds.
  • 2 Overview: Attention discretization and limited numerical precision are two principal ways of restricting transformers in upper-bound analyses.
  • 2 Overview: Formal logic offers finer control for characterizing transformer expressive power and may provide upper bounds, lower bounds, or both.

3 Preliminaries

The preliminaries establish notation for natural numbers, finite alphabets, sequences, vectors, affine maps, activations, and softmax. These definitions formalize the inputs, outputs, and operations used throughout the survey.

  • 3 Preliminaries: A finite alphabet Σ represents words or subwords, while Σ* denotes all finite sequences over that alphabet.
  • 3 Preliminaries: Vectors use bold lowercase notation, matrices use bold uppercase notation, and x_i or [x]_i denotes a vector component.
  • 3 Preliminaries: Sequences are indexed from 0, with |s| denoting length; strings use w and their length uses n.
  • 3 Preliminaries: An affine transformation maps x to W_Lx + b_L, becoming linear when its bias is zero.
  • 3 Preliminaries: The defined nonlinearities are ReLU and logistic sigmoid, while softmax converts a real-valued sequence into a probability distribution.

4 Transformers

This section defines transformers and the variants relevant to formal-language analysis. Transformers are modeled as layered sequence-to-sequence systems whose inputs and outputs are sequences of vectors.

  • 4 Transformers: The section defines transformer variants and explains how transformers are used to describe formal languages.
  • 4 Transformers: Transformers consist of an input layer, one or more hidden layers, and an output layer operating on sequences of vectors.

4.1 Input layer

The input layer maps strings to length-preserving sequences of vectors by combining word and positional embeddings. Theoretical studies allow flexible word embeddings and explore several positional-embedding choices.

  • 4.1 Input layer: Strings are mapped to vector sequences by a length-preserving function combining word and positional embeddings.The notation emphasizes variable sequence length rather than fixed-size matrices.
  • 4.1 Input layer: Theoretical constructions may use any computable word-embedding function.
  • 4.1 Input layer: The original transformer introduced a positional embedding that differs from the survey’s sequence-oriented notation.
  • 4.1 Input layer: Theoretical work explores positional embeddings including i, i/n, 1/i, and 1/i^2.

4.2 Hidden layers

Hidden layers are built from length-preserving attention, feed-forward, and normalization components, with architectural variants differing in normalization, masking, and attention aggregation. The survey distinguishes hard-attention choices from scaled dot-product attention and relates these components to transformer computation.

  • 4.2 Hidden layers: Each transformer layer is length-preserving and combines multi-head self-attention, a feed-forward network, and layer normalization.Post-norm and pre-norm variants differ in the placement of layer normalization.
  • 4.2 Hidden layers: Scaled dot-product attention maps a query and a sequence of vectors to a vector, while cross-attention obtains them from decoder and encoder outputs.
  • 4.2 Hidden layers: Future masking restricts each position to attend to preceding positions, with strict, past, and strict-past variants also used.
  • 4.2 Hidden layers: Multi-head attention sums H attention modules, each using d_kv key/value dimensions, while the original formulation concatenated heads before a shared output projection.
  • 4.2 Hidden layers: Hard attention replaces softmax with rules selecting maximal positions, including leftmost, rightmost, or equally weighted maxima.Average-argmax is described as softmax’s low-temperature limit and can approximate trained-transformer behavior.
  • 4.2 Hidden layers: The feed-forward component is an affine-transformation network with component-wise activation R.
  • 4.2 Hidden layers: Layer normalization is parameterized by scale, bias, and epsilon; analyses may omit it or choose epsilon to induce specific effects.With epsilon greater than zero, layer normalization is Lipschitz-continuous.

4.3 Networks and output layers

The survey defines encoder, decoder, and encoder–decoder transformers and explains how output layers turn encoder representations into recognition decisions or next-token probabilities. Intermediate decoding steps substantially increase recognizer power.

  • 4.3 Networks and output layers: An encoder maps strings through D transformer layers to a sequence of vectors, then an output layer converts a distinguished position into an acceptance probability.Recognition may use the last position or a prepended CLS position.
  • 4.3 Networks and output layers: Bounded cross-entropy recognition requires low negative log probability for members and low negative log non-membership probability for non-members.
  • 4.3 Networks and output layers: A decoder is an encoder with future masking in its attention, typically used for generation rather than recognition.
  • 4.3 Networks and output layers: A decoder uses future masking to predict the next symbol from previously generated prefixes and samples autoregressively until EOS.BOS and EOS are special symbols, and each sampled symbol becomes input at the next step.
  • 4.3 Networks and output layers: Decoders can recognize strings or generate entire strings under multiple generation criteria, including epsilon-generation and KL-divergence formulations.An epsilon-generator can be converted into a recognizer.
  • 4.3 Networks and output layers: An encoder–decoder adds decoder cross-attention over encoder outputs, and intermediate steps can vastly increase recognition power.The surveyed encoder–decoder constructions and some decoder-only models use such intermediate steps.

4.4 Uniformity and precision

Theoretical analyses must account for unbounded lengths, input-length dependence, and numeric precision because these choices affect the formal expressivity attributed to transformers. Limited precision introduces unresolved design choices about rounding intermediate activations.

  • 4.4 Uniformity and precision: Allowing unbounded string lengths is crucial because fixing a maximum length makes every language finite and collapses language classes.Practical context windows are growing, and some theoretical consequences may matter at modest lengths.
  • 4.4 Uniformity and precision: Some analyses permit position embeddings, parameters, or model dimension to depend on input length, introducing increasing degrees of non-uniformity.Length-dependent parameters require learning different transformers for different maximum lengths.
  • 4.4 Uniformity and precision: Studies use limited-precision numbers because unrestricted real or rational representations can encode arbitrary amounts of information and make models appear theoretically stronger than practically.
  • 4.4 Uniformity and precision: O(log n) bits of precision is common because O(1)-precision attention weights can all round to zero on sufficiently long strings.Some work instead uses the set F = {a/2^b | a ∈ Z, b ∈ N}.
  • 4.4 Uniformity and precision: Rounding intermediate activations can affect expressivity, and the effects of when and how rounding occurs remain an area for future research.For example, summations may round after each addition or only at the end.

4.5 Summary

The survey organizes transformer expressivity around architectural and modeling choices that can materially affect theoretical claims. These choices include model architecture, recognition or generation procedures, attention and positional mechanisms, residual design, and uniformity.

  • Transformer expressivity results can depend on architecture, recognition or generation definitions, positional embeddings, attention, masking, residual connections, and uniformity.The survey distinguishes encoder-only, decoder-only, and encoder–decoder architectures, alongside several implementation and computational assumptions.
  • Encoder analyses require a definition of recognition, while decoder analyses require a definition of generation and the number of intermediate steps.These distinctions determine what computation is attributed to the transformer before a decision or output is produced.
  • Position embeddings and residual connections are additional architectural choices, with residuals distinguished as pre-norm or post-norm.
  • Attention assumptions include leftmost-hard, rightmost-hard, average-hard, or softmax patterns, with masking specified as none, future, or past.The survey treats attention pattern and masking as separate dimensions of model variation.
  • Uniformity concerns whether parameter values or the number of parameters depend on input length n.

5 Languages and Language Classes

The survey introduces formal languages, circuit families, circuit complexity classes, and logics as frameworks for analyzing transformer expressivity. It emphasizes that these frameworks cut across the Chomsky hierarchy and identify problems beyond fixed-depth transformer capabilities under standard complexity assumptions.

  • Circuits: Circuit families assign a circuit C_n to each input length n, and the recognized language contains strings whose corresponding circuit outputs 1.Circuit depth and size are defined as functions of input length across the family.
  • Uniformity: Uniformity restricts how circuit descriptions are constructed, with L-uniformity and DLOGTIME-uniformity defined through direct-connection queries.Without uniformity, even undecidable unary languages can be recognized by small constant-depth circuit families.
  • Circuit complexity classes: Constant-depth circuit classes central to the survey include AC0, ACC0, TC0, and NC1, differing in gates, fan-in, and depth.AC0 uses unbounded fan-in and constant depth; ACC0 adds modular gates, TC0 adds majority gates, and NC1 uses fan-in at most 2 with logarithmic depth.
  • Beyond TC0: The permutation-group word problem is regular yet NC1-complete under AC0 reductions, so it lies outside TC0 if TC0 ⊊NC1.This makes it an example of a regular language that transformer encoders probably cannot recognize under that assumption.
  • Beyond TC0: Systems of linear equalities and universal context-free grammar recognition are P-complete under L reductions, placing them outside TC0 if L ⊊P.

6 Current Results

The survey organizes transformer expressivity results into three levels shaped by architectural assumptions, especially intermediate decoding steps and attention type. Decoders or encoder–decoders with intermediate steps reach Turing-machine-level power, leftmost- or rightmost-hard encoders are limited to logical or AC0 classes, and average-hard or softmax encoders lie between AC0 and TC0.

  • 6.1 Decoders with intermediate steps: Without intermediate steps, O(log n)-precision decoders cannot solve NC1-hard arithmetic or linear-equation problems unless TC0 = NC1, nor universal CFG recognition unless L = P.The surveyed constructions solve these problems when polynomially many intermediate steps are permitted.
  • 6.1 Decoders with intermediate steps: Decoders or encoder–decoders with intermediate steps can simulate Turing machines, with polynomially many steps yielding exactly the languages in P for decoders.Encoder–decoders allowed arbitrarily many steps can recognize recursively enumerable languages; bounded simulations use logarithmic precision and a number of steps proportional to the simulated runtime.
  • 6.2 Hard attention: Leftmost-hard attention yields at most AC0 expressivity, while rightmost-hard attention corresponds exactly to FO, FO[MOD], or FO[Mon] depending on positional encodings.Leftmost-hard models cannot recognize PARITY or DYCK-1; rightmost-hard models require strict future masking for the stated characterizations.
  • 6.3 Average-hard and softmax attention: Average-hard and softmax attention can count and recognize languages such as MAJORITY beyond AC0, but are no more powerful than DLOGTIME-uniform TC0.The survey treats these attention types together because existing theory does not clearly separate their expressivity.
  • 6.3.1 Lower bounds: particular languages: Specific positional encodings and attention assumptions permit recognition or generation of PARITY and DYCK variants, but differing criteria and regularity assumptions can produce apparently conflicting results.The survey notes near-perfect length generalization for SHUFFLE-DYCK-k, while other DYCK results depend strongly on positional encoding and evaluation conditions.

7 Conclusions

The survey highlights distinct expressivity results across transformer variants and identifies open questions about how architectural choices affect these results. It concludes that decoder expressivity, encoder circuit complexity, and the roles of specific design choices remain central directions for research.

  • Unbounded-step transformer decoders can simulate Turing machines and are Turing-complete.
  • Circuit complexity and logic are promising frameworks for analyzing transformer encoder expressivity.
  • Leftmost-hard-attention encoders lie in AC0 and cannot solve PARITY or MAJORITY.
  • Softmax and average-hard attention enable counting but remain within TC0 and likely cannot evaluate closed Boolean formulas.
  • Future work should clarify how positional encodings, attention variants, normalization, and special tokens affect expressivity.
  • The expressivity of softmax-attention transformers and decoder-only transformers remains insufficiently characterized by logic and circuit analysis.
Loading 2311.00208v3…