Autoregressive Transformer (LLM)
Autoregressive2018 · OpenAI / Google BrainParallel teacher-forced causal training; sequential KV-cached token decoding
Execution Paradigm:Two-Phase Prefill + Serial KV-Cached Decoding
Serial O(T) Token-by-Token LoopInteractive Stage (INFERENCE)Prompt tokens populate the initial KV Cache slots in a single parallel pass.
Phase 1: Prompt PrefillProcessing prompt tokens in one parallel batch to initialize KV cache
Step 1 of 3Active Token Stream & Memory AllocationTotal Tokens: 3
Prompt"The"K, V cached
Prompt"cat"K, V cached
Prompt"sat"K, V cached
GPU High Bandwidth Memory (HBM) — KV Cache Pool
Avoids O(T²) recomputation · Memory Bandwidth BoundSlot 0
"The"
[K_cache, V_cache]
Slot 1
"cat"
[K_cache, V_cache]
Slot 2
"sat"
[K_cache, V_cache]
Slot 3
"on"
Unallocated
Slot 4
"the"
Unallocated
Slot 5
"mat"
Unallocated
⚠️ Memory Bandwidth Bottleneck:During autoregressive decoding, the GPU must stream tens of gigabytes of weights and cached KV vectors from VRAM to compute the next token distribution for a single token query. Generating 1,000 tokens requires 1,000 serial rounds of memory reads.
Step 1 of 3
1. Parallel Prompt Prefill & KV Cache Init
Process all prompt tokens in one parallel batch (just like training) and store their Keys and Values in GPU HBM memory (K_cache, V_cache) so they never have to be recomputed.
💡 Takeaway: Prefill is compute-bound and saturates GPU Tensor Cores cleanly.
Active Tensor Dimensions & Memory Shapes
prompt[B, P]
User prompt tokensK_cache, V_cache[L, B, H, P, d_k]
Cached prompt keys & valuesgenerate_kv_cache.py
1
def generate_autoregressive(prompt, model, max_new_tokens, temp=0.8):
2
kv_cache = init_empty_kv_cache(model.num_layers)
3
# Phase 1: Parallel Prefill over entire prompt [B, P]
4
logits = model.forward(prompt, kv_cache=kv_cache, use_cache=True)
5
next_tok = sample_top_p(logits[:, -1, :] / temp)
6
# Phase 2: Sequential Autoregressive Loop (O(T) serial steps)
7
for step in range(max_new_tokens):
8
logits = model.forward(next_tok, kv_cache=kv_cache) # Input is [B, 1]!
9
next_tok = sample_top_p(logits[:, -1, :] / temp)
10
prompt = torch.cat([prompt, next_tok], dim=1)
Click code line to jump to corresponding stepPyTorch Reference
Why This Architecture Matters
Powers GPT-4, Claude, Gemini, and Llama. Understanding the asymmetry between parallel training and serial memory-bandwidth-bound inference explains why modern research focuses on KV compression, speculative decoding, and parallel hierarchies like NCM.
Runtime Complexity & Bottlenecks
Training Objective:Next-Token Cross-Entropy Loss: L = -∑ log P_θ(x_t | x_<t)
Inference Bottleneck:O(T) serial forward passes (memory-bandwidth bound)
Foundational & Breakthrough Papers for Autoregressive Transformer (LLM)
NeurIPS 2017 · 2017
Attention Is All You Need
Vaswani et al. (Google Brain)
Core Contribution:Introduced multi-head scaled dot-product self-attention and causal decoder masking.
OpenAI Technical Report · 2019
Language Models are Unsupervised Multitask Learners (GPT-2)
Radford et al. (OpenAI)
Core Contribution:Demonstrated that scaling decoder-only next-token prediction yields zero-shot task transfer.
arXiv:1911.02150 · 2019
Fast Transformer Decoding: One Write-Head is All You Need (MQA / KV Cache)
Noam Shazeer
Core Contribution:Analyzed the memory-bandwidth bottleneck of KV-cached autoregressive decoding.