Autoregressive Generation

Autoregressive generation produces output one token at a time, feeding each generated token back as input for the next step.

Process:

Given prompt tokens $[t_1, \dots, t_n]$ , run forward pass → get probability distribution over next token
Sample or select $t_{n+1}$ from this distribution
Append $t_{n+1}$ to the sequence
Repeat until stop token or max length

Sampling strategies:

Method	Description	Effect
Greedy	Pick argmax at each step	Deterministic, often repetitive
Temperature $\tau$	Divide logits by $\tau$ before softmax	$\tau < 1$ : sharper (more deterministic). $\tau > 1$ : flatter (more random)
Top-k	Sample from the $k$ most probable tokens	Limits tail randomness
Top-p (nucleus)	Sample from smallest set with cumulative prob $\geq p$	Adaptive k — more tokens when distribution is flat

KV cache: at each step, only the new token's Q needs computation — K and V from previous positions are cached. This turns generation from $O(n^2)$ per step to $O(n)$ .

# Pre-allocate per-layer cache of shape (batch, num_heads, max_seq_len, head_dim)
def forward_with_cache(model, new_token, kv_cache, position):
    x = model.embed(new_token)              # (batch, 1, d_model) — just the new token
    for i, layer in enumerate(model.layers):
        q, k, v = layer.qkv_proj(x).chunk(3, dim=-1)
        kv_cache[i]['k'][:, :, position, :] = k.squeeze(2)   # write new K, V
        kv_cache[i]['v'][:, :, position, :] = v.squeeze(2)
        k_full = kv_cache[i]['k'][:, :, :position + 1, :]     # attend over all cached
        v_full = kv_cache[i]['v'][:, :, :position + 1, :]
        x = layer.ffn(attention(q, k_full, v_full))
    return model.lm_head(x)

Shrinking the KV cache (it scales as num_layers × num_kv_heads × seq_len × head_dim × 2):

MHA — every head has its own K, V (largest cache)
MQA — all heads share one K, V → cache shrinks by num_heads
GQA — heads grouped, each group shares K, V (middle ground; the modern default)
MLA (DeepSeek) — cache a small latent vector per token, project back up to full K, V at decode time (not compatible with RoPE)

Autoregressive = left-to-right generation. This is why decoder-only models need Causal Masking during training: it simulates the generation setting where future tokens are unavailable.

Limitation: sequential generation is slow. Each token requires a full forward pass. Test-Time Compute explores ways to use more compute per generation.

Speculative decoding speeds this up losslessly by exploiting that scoring (prefill) is cheaper than generation: a small draft model $q$ proposes $K$ tokens, then the target model $p$ verifies them in one parallel forward pass. Each draft token is accepted with probability $\min(1, p(x)/q(x))$ ; on the first rejection, resample from the normalized residual $\max(0, p(x) - q(x))$ . The acceptance rule is constructed so the emitted distribution is exactly $p$ — same output distribution as the target, but several tokens per target call when the draft agrees.

Autoregressive Generation

Linked from