Reference Document

Autoregressive Models

A citable reference on autoregression in machine learning and natural language processing: mathematical formulation, causal masking, sequential inference bottlenecks, and KV caching.

Jump to Section

Definition & Probability Chain · Causal Masking & Transformers · Inference Bottlenecks · KV Caching Mechanics · Autoregressive vs. Non-Autoregressive · Sources

1. Definition & Mathematical Formulation

An autoregressive (AR) model is a statistical or machine learning model that forecasts future values in a sequence as a function of its own preceding past values. In natural language processing, autoregressive language modeling decomposes the joint probability distribution of a sequence of tokens $X = (x_1, x_2, \dots, x_T)$ using the probabilistic chain rule:

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

At each step $t$, the model conditions strictly on the prefix $x_{\lt t}$ to emit a probability distribution over the vocabulary $V$, samples or selects token $x_t$, appends $x_t$ to the sequence, and repeats the forward pass.

2. Causal Masking in Decoder Transformers

Modern autoregressive LLMs (such as GPT-4, Claude, and Llama) utilize the decoder-only Transformer architecture (Vaswani et al., 2017). During parallel training across full sequences, future tokens must be hidden to prevent the model from "cheating" by looking ahead.

This is enforced via a causal attention mask (lower-triangular matrix), setting attention weights to $-\infty$ for all positions $j > i$:

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

3. The Sequential Inference Bottleneck

While training can process all $T$ tokens in parallel using matrix multiplication and causal masks, inference is inherently sequential ($O(N)$):

Prefill Phase (Prompt Evaluation): Parallel forward pass evaluating all prompt tokens simultaneously. Compute-bound (high arithmetic intensity). Measured by Time to First Token (TTFT).
Decode Phase (Generation): Sequential loop generating one token per forward pass. Memory-bandwidth bound (low arithmetic intensity, constantly reading weights from VRAM to compute a single token). Measured by Time Per Output Token (TPOT).

4. Key-Value (KV) Caching

Without optimization, generating token $t$ would require re-computing the Key ($K$) and Value ($V$) vectors for all preceding $t-1$ tokens, resulting in quadratic $O(N^2)$ computational complexity during generation.

KV Caching stores previously computed $K$ and $V$ projection tensors in GPU memory. On each step, the model computes $Q, K, V$ only for the newest token, concatenates the new $K, V$ to the cache, and computes attention over the cached history in $O(N)$ linear time.

5. Autoregressive vs. Non-Autoregressive Models

Architecture	Attention Direction	Generation Complexity	Primary Applications
Autoregressive (Causal / Decoder)	Left-to-Right (Unidirectional)	$O(N)$ sequential turns	Text generation, code synthesis, conversational agents, mathematical reasoning (LLMs).
Masked Language Models (Encoder)	Bidirectional (Full Context)	$O(1)$ single forward pass	Text classification, named-entity recognition, semantic search embeddings (e.g. BERT).
Non-Autoregressive (Diffusion / Flow)	Iterative Denoising / Parallel	Fixed $K$ denoising steps	Image generation (Stable Diffusion), speech synthesis, continuous control.

Architecture	Attention Direction	Generation Complexity	Primary Applications
Autoregressive (Causal / Decoder)	Left-to-Right (Unidirectional)	\(O(N)\) sequential turns	Text generation, code synthesis, conversational agents, mathematical reasoning (LLMs).
Masked Language Models (Encoder)	Bidirectional (Full Context)	\(O(1)\) single forward pass	Text classification, named-entity recognition, semantic search embeddings (e.g. BERT).
Non-Autoregressive (Diffusion / Flow)	Iterative Denoising / Parallel	Fixed \(K\) denoising steps	Image generation (Stable Diffusion), speech synthesis, continuous control.