Bridges: DSA to LLMs

Recursion and recurrence to autoregression

From call stacks to next-token loops

~10 minLesson 43 of 57Written by Claude Opus 4.8

An LLM writes text the same way a recursive function works: it produces one token, feeds that token back into itself, and repeats - a recurrence over the sequence - until it decides to stop.

You already met the shape of this idea in Recursion and the call stack. A recursive function calls itself on a slightly changed input until a base case stops it; a recurrence relation defines each value from earlier values - $fib (n) = fib (n - 1) + fib (n - 2)$ . Autoregressive generation is exactly that pattern wearing new clothes: the model emits a token, appends it to its own input, and calls itself again on the longer sequence. Each call depends on every result before it. The loop only ends when the model emits a special end-of-sequence token - its base case.

The loop, in one breath

"Auto-regressive" literally means regressing on yourself: your own past outputs become your next inputs. Predict a token - paste it onto the end of the context - predict again from that longer context - repeat. The output of step $t$ is fed back to become part of the input of step $t + 1$ . That feedback arrow ↩ is the whole trick - it turns a one-shot next-token predictor into a machine that writes paragraphs.

A recurrence over the sequence

A language model is trained to answer one question: given everything so far, what comes next? Formally it gives a probability distribution $p_{θ} (x_{t} ∣ x_{1}, \dots, x_{t - 1})$ over the vocabulary for the next token $x_{t}$ . Because each token conditions on all the tokens before it, the probability of a whole sequence factorizes into a product of these one-step predictions - the chain rule of probability applied left to right:

Autoregressive factorization

p_{θ} (x_{1}, x_{2}, \dots, x_{T}) = t = 1 \prod T p_{θ} (x_{t} ∣ x_{1}, \dots, x_{t - 1}) .

Generation runs that product one factor at a time. Written as a recurrence with an explicit start and stop, it is:

x_{t} \sim p_{θ} (\cdot ∣ x_{< t}), x_{0} = ⟨ bos ⟩, halt when x_{t} = ⟨ eos ⟩ .

Compare it to $fib (n) = fib (n - 1) + fib (n - 2)$ : both define term $t$ from earlier terms. The difference is only that $x_{t}$ depends on the entire prefix $x_{< t}$ , not just the last one or two - a recurrence with unbounded look-back.

Every piece of the recursion lesson has a counterpart here. The base case is the start token $⟨ bos ⟩$ - the un-reducible seed you begin from. Termination is the end-of-sequence token $⟨ eos ⟩$ : when the model samples it, the loop stops, exactly like hitting the floor of a recursion. And the state carried across calls is the growing sequence itself - plus, in a real transformer, the KV cache: the stored keys and values of every past token so the next step doesn't recompute them from scratch.

The KV cache is memoization

Naively, step $t$ would re-run attention over all $t$ tokens every time - the same $O (n^{2})$ recomputation that made naive $fib$ slow. The KV cache stores each token's key and value the first time it's seen, so each new step only computes the new token and reuses the rest. That's precisely the memoize toggle from the recursion lesson: trade memory to stop redoing work. Same idea, one layer up.

Watch it write, one token at a time

Below is a deterministic toy "model." Press Generate one token: it reads the current sequence, produces a little distribution over next tokens (real transformers output hundreds of thousands of these), the argmax is appended to the tape, and the call visibly recurses on the longer sequence. Notice the second the predicts a different word than the first - because the model sees the whole prefix, the recurrence remembers. Keep stepping until the tape emits ⟨eos⟩ and the base case halts it.

Autoregressive tape step, or run to end

⟨bos⟩

step 1 - generate([ ⟨bos⟩ ]) - predicts the ↩ append & recurse

the

80% ◂

14%

one

The highlighted row is the argmax. Greedy decoding appends it, then feeds the longer sequence back in as the next input.

ready - press Generate

The aha to catch

Step twice and you'll see the first the predict cat at 63%. Keep going, and the second the (after on) predicts mat instead - same token, different future, because the prediction is conditioned on the entire prefix, not just the previous word. That is the recurrence doing its job: $x_{t}$ is a function of all of $x_{< t}$ . The instant mat lands, the model's most likely next token becomes ⟨eos⟩ - it has "decided to stop," and the loop drains just like a call stack popping back to empty.

The entire generation loop

def generate(model, max_len=64):
    seq = [BOS]                          # base case: seed with the start token
    while True:
        dist = model(seq)               # p(x_t | x_1 .. x_{t-1}) - sees ALL prior tokens
        tok  = argmax(dist)             # greedy pick (or sample) the next token
        seq.append(tok)               # FEED THE OUTPUT BACK IN - this is the recurrence
        if tok == EOS or len(seq) >= max_len:
            break                        # termination: base case fires, or guard trips
    return seq

The entire generation loop

Why the max_len guard exists

A recursion with no reachable base case runs until it overflows the stack. Autoregression has the same danger: if the model never assigns high probability to $⟨ eos ⟩$ , it would generate forever. The max-length guard is the pragmatic floor - a hard cap that forces a stop even when the model won't commit. Real systems pair it with an $⟨ eos ⟩$ check and often a repetition penalty, so the loop always terminates.

Check yourself

What makes autoregressive generation finally stop?

The start token ⟨bos⟩ plays the role of the recursion's...

Recall: in what precise sense is autoregressive generation a recurrence relation?

Nail the structural analogy. Try to state it, then check.

Lock it in

Autoregressive generation is a recurrence: each token $x_{t}$ is drawn from $p_{θ} (x_{t} ∣ x_{< t})$ - a function of the entire prefix, not just the last term.
The start token $⟨ bos ⟩$ is the base case; the end-of-sequence token $⟨ eos ⟩$ is termination; the growing sequence (plus KV cache) is the state carried across calls.
The KV cache is memoization: store each token's key and value once and reuse on subsequent steps, trading memory for compute.
A max-length guard is the safety net against non-termination, just as a recursion depth limit prevents stack overflow.

Primary source

Jay Alammar's The Illustrated GPT-2 shows the autoregressive loop visually - each generated token fed back in as the next input, step by step. To build the whole thing from scratch and watch the generation loop run in code, Andrej Karpathy's "Let's build GPT" is the definitive walkthrough.

Ask your teacher

This closes the loop we opened long ago. The call stack and recurrence relations from the recursion lesson reappear here as how an LLM actually writes text: one token at a time, each feeding the next, until it decides to stop. The argmax step is greedy decoding, from Decoding and sampling strategies; swap it for sampling and the same loop gets creative. The "sees all prior tokens" part is self-attention, and the KV cache is just memoization. Want me to show what changes when we sample instead of argmax, or trace exactly what the KV cache stores on each step? Ask and I'll add the follow-up.