Transformer Expressivity

Transformers can represent surprisingly many functions because attention routes information between positions while depth and width trade off to buy memory, precision, and reasoning steps.

Width widens what one layer can memorize while depth lengthens the chain of reasoning steps it can compose

Why Does This Exist?

Transformers replaced recurrent nets almost everywhere, yet on paper they look weaker: no loop, fixed depth, each token looking at the rest in one shot. So what exactly can a stack of attention plus feedforward layers compute that an RNN cannot do as cheaply, and where does it hit a wall? The answers shape how you scale: wider for facts, deeper for multi-step reasoning.

Theory gives three crisp facts. With enough width, transformers are universal approximators over sequences. With fixed size, they sit inside shallow circuit classes, so some simple-looking tasks need growing depth. And depth buys sequential computation, which is why chain-of-thought prompting helps. This page collects those results without re-teaching attention itself.

The one idea you need first

A universal approximator can fit any continuous function on a bounded input region if given enough capacity. Attention computes weighted averages across positions, and the feedforward block applies a per-position nonlinearity. Together they route then compute, and routing plus computing turns out to be enough. The attention operation itself is covered wherever you learned it; here only its power matters.

Think of It Like This

A committee passing annotated notes

Each member (position) writes a note, reads everyone else's, and underlines the lines that matter to them. Then each member privately works through their annotated copy with a calculator (the feedforward net) before the next round.

Width is giving every member a bigger desk so they can spread out more notes at once. Depth is adding more rounds of read-then-calculate. A huge desk with one round memorizes phone books but cannot follow a ten-step recipe; ten rounds with tiny desks follows recipes but forgets names. Where the analogy stops: real attention weights come from learned dot products with limited precision, so very long chains accumulate rounding error.

How It Actually Works

Three results carry the story, each with its condition.

Universality with width. A transformer with one wide attention layer plus feedforward blocks approximates any continuous map from sequences to sequences on a compact domain. The proof routes each input region to a distinct attention pattern, then fits local pieces with the feedforward net. Width is doing memorization work here, and the required width grows with the fineness of the function.

Bounded-size limits. Fix depth, width, and precision while letting the sequence length $n$ grow, and transformers fall into shallow circuit classes (variants of TC0). Concretely, tasks like exact parity over $n$ bits or deep compositional reasoning need depth or width to grow with $n$ . A 2-layer net does not learn parity for all lengths; it memorizes lengths it saw.

Depth as sequential steps. Each layer is one parallel round. A $T$ -step serial computation needs on the order of $T$ layers unless the model writes intermediate steps to the output (chain of thought), which trades depth for generated tokens. That is the theoretical reason prompting a model to show work extends what fixed depth can do.

Worked example

Take binary parity over $n = 4$ bits: output 1 when the count of ones is odd. There are $2^4 = 16$ inputs; 8 have odd parity.

A width-16 attention head can dedicate one pattern per input and memorize the table exactly, using 16 slots for 16 cases. Halve the width to 8 and one head must share patterns across pairs, forcing errors on at least 2 of the 16 inputs by pigeonhole counting. Add a second layer instead, and the net can XOR pairs then XOR the results: 2 layers of width 2 compute parity for any $n$ that fits the precision, because depth composes. Width memorizes, depth composes.

Watch Out For

Reading universality as learnability

Universality says some setting of the weights represents the function. It says nothing about gradient descent finding it from random start with finite data. Parity is universal-friendly and gradient-hostile: wide nets memorize training lengths and fail the next length up.

If length generalization fails while in-distribution accuracy is perfect, suspect this gap before adding data. Test on longer inputs early.

Assuming depth and width substitute freely

A 1-layer net with 10,000 width and a 10-layer net with 100 width may hold similar parameter counts but compute different things. The wide shallow net stores associations; the narrow deep net chains operations. Swapping one for the other on a reasoning benchmark changes the outcome even at matched size.

Pick width for knowledge-heavy tasks and depth for step-heavy ones, then verify with ablations.

The Quick Version

Wide transformers are universal over sequences, but required width grows with function complexity.
Fixed-size transformers sit in shallow circuit classes, so parity and deep composition need growing size.
Depth supplies sequential steps; chain-of-thought output tokens extend fixed depth.
Width memorizes cases while depth composes operations, as the 4-bit parity count shows.
Representable does not mean learnable: test length generalization, not just training fit.