Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Autoregressive Generation › Why Naive Generation is Expensive

Michael BrenndoerferUpdated July 30, 20253 min read

Language AI HandbookAll chapters

Part 28 of 67GPT Architecture

Chapter 201Autoregressive Generation › Why Naive Generation is Expensive

Reading section 3 of 12 · Why Naive Generation is Expensive · 3 minSection 3 of 12 · 3 min

Section 3 of 12 · 3 min read

Autoregressive Generation › Why Naive Generation is ExpensiveOne section · Sections in this chapter3 / 12 ↓

Sections in this chapter12

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

The generation loop seems straightforward, but the naive implementation hides a severe performance problem. At each step, we feed the entire sequence, prompt plus all previously generated tokens, back through the model from scratch. The model recomputes every QKV projection for every token it has already processed. None of those computations change between steps: if token 5 is "cat", its key and value projections are identical whether we are computing step 6 or step 106. Yet the naive implementation throws away all this prior work at the end of each step and recomputes it from scratch at the next.

Think of naive generation as a student who, every time they need to answer the next question on an exam, re-reads the entire question paper from the beginning rather than remembering what they already read. The cost of each question answer grows linearly with how many questions have already been answered, making the total exam time grow quadratically with the number of questions. Key-value caching is the insight that you only need to read the new question, not the entire paper again.

Consider generating 100 tokens after a 50-token prompt. With naive generation, each step requires a full forward pass through the model. The first generated token requires processing 50 tokens. The second requires processing 51 tokens. The hundredth requires processing 149 tokens.

The total computation scales quadratically with sequence length because attention at each position must attend to all previous positions. To see why, consider that at generation step $i$ , we must compute attention over a sequence of length $i$ . The total number of attention operations across all $T$ generation steps is:

\text{Total attention operations} \propto \sum_{i=1}^{T} i = \frac{T(T+1)}{2} = O(T^2)

where:

$T$ : the total number of tokens generated
$\sum_{i=1}^{T} i$ : the sum of sequence lengths processed at each step (1 + 2 + 3 + ... + T)
$\frac{T(T+1)}{2}$ : the closed-form solution for this arithmetic series
$O(T^2)$ : big-O notation showing quadratic growth with sequence length

This quadratic relationship means that generating 1000 tokens requires roughly 1,000,000 attention operations proportionally, while generating just 100 tokens requires only about 10,000. The cost grows much faster than the output length.

Out[12]:

Visualization

Line plot showing quadratic growth of attention operations with sequence length for naive generation. — Computational cost of naive autoregressive generation. Each step requires recomputing attention over the entire sequence, leading to quadratic growth. For a 1000-token generation, the naive approach performs over 500,000 attention operations versus 1000 with proper caching.

For practical deployments where latency matters, this quadratic scaling is unacceptable. Generating a single response could take tens of seconds even on powerful hardware. The solution is to cache intermediate computations and reuse them across generation steps.