Autoregressive Models

Autoregressive models predict the next value in a sequence using earlier values. In language models, those values are tokens: units of text such as words.[1]

In this illustrative example, a model given The cat might select sat. It then uses The cat sat to predict the next token.

Last updated 20260909 · Previous version (archived 20260909)

1. First principles and definitions

An autoregressive language model assigns a probability to each next token conditioned on the preceding tokens. For a sequence $X = (x_1, x_2, \dots, x_T)$, the probability chain rule gives:[1]

$$P(X) = \prod_{t=1}^{T} P(x_t \mid x_1, x_2, \dots, x_{t-1})$$

$T$ is the sequence length and $x_t$ is its token at position $t$. The first factor is $P(x_1)$. A model learns estimates of these conditional probabilities, often using a limited context window.[1]

Autoregression describes a prediction dependency. It does not require a particular neural architecture. The original Transformer uses an encoder and an autoregressive decoder; the original GPT uses a Transformer decoder for language modeling.[2][3]

2. Causal masking in Transformers

During training, a Transformer decoder can process known sequence positions in parallel. A causal attention mask prevents each position from attending to later positions. Inputs and next-token targets are shifted by one position.[2]

The mask adds $-\infty$ to future-position attention scores before softmax. Their resulting attention weights are zero:[2]

$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}} + M\right)V$$ $$M_{ij} = \begin{cases} 0 & i \ge j \\ -\infty & i \lt j \end{cases}$$

$Q$, $K$, and $V$ are the query, key, and value matrices. $d_k$ is the key dimension; $i$ and $j$ index query and key positions. Each query can attend to its own position and earlier positions.[2]

3. Sequential generation

Ordinary autoregressive decoding selects or samples a token, appends it to the context, and repeats. Generating $N$ output tokens requires $N$ token-selection steps. This counts sequential steps, not total computational work.[4]

Prefill: the model processes the prompt and produces the distribution used to select the first output token.
Decode: subsequent calls process the newly selected token and predict the next one. A cache reuses calculations for earlier tokens.[4]

Speculative sampling can accept several tokens per target-model call. A draft model proposes tokens that the target model verifies together. Chen et al.'s acceptance procedure preserves the target sampling distribution, subject to numerical precision.[5]

4. Key-value caching and computational work

A key-value (KV) cache stores keys and values computed at each attention layer. During decoding, the model computes queries, keys, and values for the newest input token, adds its keys and values to the cache, and attends over the stored history.[4]

These bounds count dense self-attention arithmetic. They assume fixed model dimensions, layer count, and batch size, with a growing context and no sliding window. Let $L$ be the number of positions attended to in one cached decode call.

Per cached decode call: one query attends to $L$ keys and values, requiring $O(L)$ attention work.
Across generation: let $P$ be the prompt length and $N$ the number of output tokens. Prefill costs $O(P^2)$ attention work and yields the first token distribution. The remaining $N-1$ calls cost $O(PN + N^2)$. For fixed $P$, attention work grows quadratically with $N$.
Without a cache: an implementation that reruns dense attention over the full prefix in every call costs $O(L^2)$ attention work per call. Summing over growing prefixes gives $O(N^3)$ for fixed prompt length.

These bounds are derived from dense attention's query-key pairs and the cached decoding procedure.[2][4] They exclude other model operations and do not predict wall-clock latency. KV storage grows linearly with the retained context length when model dimensions and batch size are fixed.[4]

5. Comparison of prediction procedures

The examples perform different tasks; the table does not rank their speed.

Model or objective	Available context	Prediction procedure
Autoregressive language model	Earlier output tokens; an encoder-decoder model can also condition on an encoded input.	Predicts the next token from its prefix. Ordinary decoding repeats this process; speculative methods can verify several candidates together.[2][5]
Masked language model (BERT)	Visible tokens on both sides of masked positions.	Predicts masked tokens and learns representations for downstream tasks. One encoder pass is not a complete procedure for arbitrary-length text generation, and its work grows with input length.[6]
Denoising diffusion model (DDPM)	The current noisy sample and diffusion timestep.	Generates a sample through repeated denoising steps. The sampling schedule determines the number of steps; each step has its own computational cost.[7]