GPT & Autoregressive Language Modeling

An autoregressive language model defines a probability distribution over a sequence of tokens $x_1, x_2, \dots, x_n$ by applying the chain rule of probability:

Each factor $P(x_t \mid x_{<t})$ is a next-token distribution conditioned only on preceding tokens, never on future ones. This is the left-to-right or causal constraint that gives the family its name. Modeling the full joint distribution over a document directly is intractable — the vocabulary of possible documents is astronomically large — but modeling one conditional distribution over a fixed vocabulary at a time is a well-posed classification problem, solvable by a neural network trained with cross-entropy loss. GPT (Generative Pretrained Transformer) instantiates this idea with a decoder-only Transformer: a stack of Transformer blocks in which every self-attention layer is causally masked, so that the representation at position $t$ can only be a function of tokens $x_1, \dots, x_t$. This is what makes the same architecture usable both for computing all $n$ conditional distributions in one parallel forward pass during training, and for autoregressive generation at inference time, where tokens are produced one at a time and fed back as input. The term "pretraining" refers to the fact that this objective requires no labels beyond the raw text itself — it is trained once on a broad corpus and then adapted downstream, foreshadowing the Pretraining-Finetuning Paradigm.

Setup. Given a corpus, we first apply Tokenization at Scale (typically byte-pair encoding or a similar subword scheme) to convert raw text into sequences of integer token IDs from a fixed vocabulary $V$. Training sequences are fixed-length windows of $n$ tokens (e.g., $n=2048$ or larger) drawn from the corpus, often by concatenating documents with separator tokens and chunking.

Model. The decoder-only Transformer maps a token sequence to a sequence of probability distributions over $V$: 1. Token embeddings $E \in \mathbb{R}^{|V| \times d}$ and positional embeddings are added to form the input representations $h^{(0)}_t$. 2. $L$ Transformer decoder blocks are applied, each consisting of causally-masked multi-head self-attention followed by a position-wise feedforward network, with residual connections and layer normalization. 3. A final linear projection (often tied to $E^\top$) plus softmax converts the last layer's hidden state $h^{(L)}_t$ into $\hat{P}(x_{t+1} \mid x_{\le t})$.

The causal mask. In self-attention, each position computes attention scores over all positions in the sequence. To enforce the left-to-right constraint, GPT adds $-\infty$ (or a large negative number) to the attention scores for any key position $j > i$ before the softmax, exactly the Masked Self-Attention mechanism. This zeroes out attention probability to future tokens without changing the shape or asymptotic cost of the attention computation.

Training via teacher forcing. During training, the entire ground-truth sequence is fed into the model at once. Because the mask makes position $t$'s output depend only on inputs $1, \dots, t$, this single forward pass simultaneously computes the correct conditional distribution for every position, using the true (not model-generated) prefix as context — this is teacher forcing. The loss is the average negative log-likelihood of the true next token at every position:

This gives $n$ supervised signals per sequence from a single unlabeled example, which is the central efficiency trick behind self-supervised pretraining.

Inference / generation. At generation time there is no ground truth to condition on, so the process must be sequential: sample or pick $x_{t+1}$ from $\hat{P}(\cdot \mid x_{\le t})$, append it to the context, and repeat. Naively this recomputes attention over the whole growing prefix at every step; in practice, KV-caching stores previously computed key/value vectors so each new token only requires attention against the cache plus one new query, avoiding redundant computation. ```

# ---- TRAINING (teacher forcing, one gradient step) ---- function TRAIN_STEP(model, batch_of_token_sequences):

# batch_of_token_sequences: tensor of shape (B, n), integer token ids inputs = batch_of_token_sequences[:, 0 : n-1] # x_1 ... x_{n-1} targets = batch_of_token_sequences[:, 1 : n] # x_2 ... x_n (shifted by 1) logits = model.forward(inputs) # shape (B, n-1, |V|)

# internally: causal mask ensures logits[:, t, :] depends only on inputs[:, 0..t] loss = 0 for b in range(B): for t in range(n-1): probs = softmax(logits[b, t, :]) loss += -log(probs[targets[b, t]]) loss = loss / (B * (n-1)) gradients = backward(loss) optimizer.apply(gradients) return loss

# ---- CAUSAL SELF-ATTENTION (core mechanism enabling the above) ---- function CAUSAL_SELF_ATTENTION(X): # X: (n, d) hidden states Q = X @ W_Q # (n, d_k) K = X @ W_K # (n, d_k) V = X @ W_V # (n, d_v) scores = (Q @ K^T) / sqrt(d_k) # (n, n) for i in range(n): for j in range(n): if j > i: scores[i, j] = -infinity # mask future positions weights = softmax(scores, axis=-1) # row-wise softmax return weights @ V # (n, d_v)

# ---- INFERENCE (autoregressive generation with KV cache) ---- function GENERATE(model, prompt_tokens, max_new_tokens): cache = KVCache() # empty per-layer key/value store tokens = prompt_tokens

# prime the cache with the prompt in one forward pass logits, cache = model.forward(tokens, cache=cache) output = [] for step in range(max_new_tokens): next_token_probs = softmax(logits[-1, :]) # distribution for next token next_token = sample(next_token_probs) # greedy / top-k / nucleus output.append(next_token) if next_token == END_OF_SEQUENCE: break

# only the ONE new token needs a forward pass; cache holds the rest logits, cache = model.forward([next_token], cache=cache) return output ``` Notice the asymmetry: `TRAIN_STEP` processes an entire sequence of length $n$ in one parallel pass because all targets are known in advance (teacher forcing). `GENERATE` cannot do this, because token $t{+}1$ is not known until the model itself produces it — hence the loop.

Time complexity, training. For one sequence of length $n$ with model dimension $d$ and $L$ layers, the dominant costs per layer are:

• Self-attention score computation and weighted sum: $O(n^2 d)$, since every pair of positions computes a $d$-dimensional dot product and the value aggregation.
• Feedforward sublayers: $O(n d^2)$ (typically the hidden dimension is $4d$, a constant factor).

Total per sequence: $O(L(n^2 d + n d^2))$. Crucially, this entire cost is paid once per training step, not once per position, because the causal mask allows all $n$ positions' losses to be computed in a single forward/backward pass — this is the payoff of teacher forcing plus parallel matrix operations on a GPU/TPU. Without masking and parallel computation, one would need $n$ separate forward passes (one per prefix length), costing $O(n)$ times more.

Space complexity, training. Storing all attention matrices for backpropagation costs $O(L n^2)$ (or $O(Ln^2 h)$ per head before summation, though implementations often fuse heads). Activations for the backward pass cost $O(Lnd)$. Memory is the binding constraint that limits maximum context length $n$ in practice, motivating techniques like gradient checkpointing and, at inference, KV-caching.

Time complexity, inference. Generating $m$ new tokens with KV-caching costs $O(m \cdot L \cdot (n_{\text{ctx}} d + d^2))$ where $n_{\text{ctx}}$ is the current context length, since each step attends over the cached keys/values (linear in context length) rather than recomputing the full $O(n^2)$ attention from scratch. Without caching, naive re-processing of the whole growing sequence at every step costs $O(m^2 L d)$ overall — quadratically worse in the number of generated tokens. This is why KV-caching is not an optimization detail but a practical necessity for usable generation latency.

Correctness argument. The claim to justify is: does minimizing the average per-position cross-entropy loss over a large corpus actually recover a good approximation to the true conditional distribution of language? The argument proceeds in two parts: 1. Chain rule exactness. The factorization $P(x_1, \dots, x_n) = \prod_t P(x_t \mid x_{<t})$ is an identity of probability theory — it holds for any joint distribution, with no independence assumptions. So if the model's conditionals $\hat P(x_t \mid x_{<t})$ were exactly correct for every $t$ and every prefix, the induced joint distribution over sequences would be exactly correct too. This licenses reducing "model all of language" to "model one next token well," with no loss of expressiveness in principle. 2. Cross-entropy minimization recovers the true conditional. For a fixed context $c = x_{<t}$, minimizing $\mathbb{E}_{x_t \sim P^*}[-\log \hat P(x_t \mid c)]$ over all valid distributions $\hat P(\cdot \mid c)$ is minimized exactly when $\hat P(\cdot \mid c) = P^*(\cdot \mid c)$, the true data-generating conditional. This follows from Gibbs' inequality: the cross-entropy $H(P^*, \hat P) = H(P^*) + D_{KL}(P^* \| \hat P)$, and KL divergence is minimized (at zero) only when the two distributions coincide. Since the training loss averages exactly this cross-entropy over all observed contexts, gradient descent on it pushes the model toward the true conditional distribution, subject to the model's representational capacity and the finiteness of training data. The causal mask is what guarantees the induced factorization is valid — that $\hat P(x_t \mid x_{<t})$ genuinely does not depend on $x_{\ge t}$, so that sampling autoregressively at inference (where future tokens genuinely do not exist yet) matches the conditional structure the model was trained under. Without masking, a bidirectional model trained the same way would leak future information into position $t$'s prediction during training, making it inconsistent with — and far too optimistic compared to — the sequential generation process it must perform at test time.

Tradeoffs. The quadratic-in-$n$ attention cost is the well-known scalability bottleneck of vanilla Transformers, motivating a large literature on sparse, linear, and windowed attention. Autoregressive generation is fundamentally sequential and cannot be parallelized across the output length the way training can, which is the main latency bottleneck of deployed generative systems (encoder-only or masked models like BERT trade this generative capability away for cheaper bidirectional training).

Take the toy corpus sentence `"the cat sat on the mat"`, tokenized (for simplicity) at the word level into IDs:

Training input/target pairs (shift-by-one), with $n=6$:

All five rows are produced from a single 6-token sentence, and — thanks to the causal mask — a single forward pass through the model computes all five predicted distributions simultaneously. Suppose after some training the model assigns these (illustrative) probabilities to the correct next token at each position:

Average loss $\mathcal{L} = (3.00+1.20+0.69+0.36+2.30)/5 = 7.55/5 = 1.51$ nats/token. Notice position 1 has low confidence (0.05) because "the" alone is a weak predictor of the next word — many words can follow "the." Position 4 is highly confident (0.70) because after "the cat sat on," the word "the" is a very likely continuation (English strongly favors an article there). This illustrates that the loss is not measuring memorization of this one sentence, but the model's calibrated uncertainty given limited context — exactly what a good conditional probability model should produce. Perplexity, a standard reporting metric, is simply $\exp(\mathcal{L}) = \exp(1.51) \approx 4.5$, interpretable as the model being as "confused" as if choosing uniformly among about 4.5 equally likely tokens per position. At generation time, given the prompt `"the cat"`, the model would sample from $\hat P(\cdot \mid \text{the, cat})$ — say it draws `"sat"` — then feed `"the cat sat"` back in (using the KV cache from the prompt plus one new key/value for "sat") to get $\hat P(\cdot \mid \text{the, cat, sat})$, and so on, never seeing ahead of where it currently is, matching exactly the conditional structure it was trained on.

Shannon's early framing of language modeling as sequential prediction — measuring how well a model anticipates the next symbol — is the direct conceptual ancestor of the cross-entropy objective used to train GPT. What changed over seven decades was not the objective itself but the representational power available to model $P(x_t \mid x_{<t})$: from fixed-order n-gram counts, to neural embeddings, to deep self-attention over the entire preceding context.

Every modern general-purpose text-generation system — chatbots, coding assistants, drafting tools, and API-based completion services — is built on a decoder-only Transformer trained with this exact autoregressive objective. The pretrained model produced by this process is rarely used in isolation: it is the starting point for the Pretraining-Finetuning Paradigm, where the same weights are further adapted via supervised finetuning, instruction tuning, or reinforcement learning from human feedback to make outputs more useful and safe, without discarding the linguistic and world knowledge acquired during pretraining. The predictable improvement in this pretraining loss as model size, data size, and compute grow is precisely the empirical regularity formalized by Scaling Laws, which now guide the design and budget allocation of frontier model training runs. Beyond natural language, the same left-to-right factorization underlies autoregressive models of code, protein sequences, symbolic music, and even images represented as token sequences, making it one of the most widely reused algorithmic templates in modern machine learning.

Ask the tutor: How does the causal mask interact with positional encodings to determine how far a GPT model can generalize beyond its trained context length?