Skip to content
LLM Inference
S01The Model·137 lines

The Generation Loop

An inference engine is a while-loop that feeds a model's own output back into itself. Everything else in this course is an optimisation of that loop.

  • forward pass
  • autoregression
  • logits
  • EOS
  • prefill vs decode

Motivation

The problem

At inference time, a language model behaves like a function: give it a sequence of token IDs and it returns a score for every token in the vocabulary. For a modern model, each output row may contain roughly 130,000 scores. What the model will not do is assemble those scores into a sentence. It has no notion of when to stop, and it remembers nothing about an earlier call.

The inference engine supplies that missing behaviour. It calls the model, selects one token, appends it to the input, and calls the model again. The cycle continues until the model emits an end-of-sequence token or the request reaches a configured limit. This is autoregressive decoding, and every engine in this course starts from this loop.

Writing the loop takes a few lines. Running it efficiently is another matter: a direct implementation repeats an enormous amount of work, and the rest of the course removes that waste one bottleneck at a time.

Core idea

The solution

The essential engine fits into nine lines of whiteboard code:

the loop, in essencepython
def generate(model, tokenizer, prompt, max_tokens=64):
    ids = tokenizer.encode(prompt)

    for _ in range(max_tokens):
        logits = model(ids)          # (len(ids), vocab_size)
        next_logits = logits[-1]     # only the last position matters
        next_id = sample(next_logits)
        ids.append(next_id)

        if next_id == tokenizer.eos_id:
            break

    return tokenizer.decode(ids)

The highlighted lines expose two constraints that shape the rest of the course.

The model returns logits for every position, and we throw all but one away. On the first call the extra rows cost nothing: the model has to look at all N prompt tokens anyway, and all N output rows come out of the same parallel matmul. Every subsequent call is pure waste. We recompute the representation of tokens we already processed just to obtain one new row, and chapter S05 eliminates that work with the KV cache.

The loop's length is data-dependent and unknown in advance. You cannot tell how many iterations a request needs until it finishes. Because of that, batching LLM requests is hard. It is why the scheduler in S10 exists, and why continuous batching (S09) beats ordinary batching by several times.

Prefill and decode are different workloads

The first forward pass processes N tokens at once. Weights are loaded once and amortised over a great deal of arithmetic, so the GPU is compute-bound. Every pass after that processes a single token: you stream every weight in the model through the ALUs to perform a handful of multiply-accumulates, so the GPU is memory-bandwidth-bound and sits mostly idle. The two phases want opposite things from the hardware, and nearly every technique in this course exists because of it.

Mechanics

How it works

Diagramautoregressive generation
ONE ITERATION = ONE TOKENprompt"The cat"tokenizertext → idsforward passL × decoder blocklogits[vocab_size]samplerargmax / top-ptoken"sat"append to context — next pass sees one more tokenif EOSdetokenize + emitids → textCONTEXT AFTER 3 ITERATIONSThecatsatonthematgrey = prompt (computed once, in parallel — the prefill)orange = generated (one per forward pass — the decode)Every pass re-reads the whole context. That is the cost S05 removes.
The forward pass is the only expensive box. Everything to its left and right costs microseconds, and the loop back into it determines your tokens/second.

Why the naive version is quadratic

Self-attention at position i attends to all positions ≤ i. Running a forward pass over a context of length n therefore costs on the order of n² attention operations. Generating T tokens without a cache means running passes of length N, N+1, …, N+T, so the total attention work is:

total costtext
no cache:   Σ n²   for n = N..N+T   →  O((N+T)³)
with cache: Σ n    for n = N..N+T   →  O((N+T)²)

For a 2,000-token prompt followed by 500 generated tokens, the gap is roughly 500×, almost three orders of magnitude in arithmetic. No production engine runs the direct version. It survives as a small reference implementation, something to check every optimisation against.

The three numbers users actually feel

time to first token
TTFT
dominated by prefill: prompt length × model FLOPs
inter-token latency
ITL
one decode pass: model bytes ÷ memory bandwidth
throughput
tok/s
aggregate across all concurrent requests, not one

Throughput and latency trade against each other, and batch size controls that trade almost by itself. A batch of one gives the best inter-token latency and the worst throughput; a large batch gives the reverse. Chapters S09 through S11 are about holding both at once.

Explore

Try it

The simulator runs the same autoregressive loop, with a word-level bigram model standing in for a transformer. Advance it one token at a time and watch two signals: the context grows by one token per pass, while the cost bars grow quadratically because earlier work is never cached.

Simulatorautoregressive decode
prompt
step 0 / 14
context (what the model sees on the next pass)
thecat

Pass 1 will run the full 2-token context through every layer. Nothing here is cached yet.

next-token distribution · 14 logits
  • sat54%
  • ate14%
  • chased14%
  • slept14%
  • .0%

Temperature divides the logits before the softmax. At 0 the bars collapse onto one token; above 1 they flatten.

forward passes
1
tokens out
0
attn work, no cache
4
with KV cache
4
cost per pass

Each bar is one forward pass, height ∝ n². The last token costs the most, when it should have cost the least.

Drop temperature to 0 and the loop becomes deterministic greedy decoding: the same seed and prompt always produce the same sentence. Raise it past 1.2 and the distribution flattens until the model starts to wander. S04 is about that one knob.

Build it

Implementation

The runnable file for this chapter has three parts: a tiny model, a sampler, and the loop. Here is the loop, written the way the rest of the course will extend it. Making it an object with explicit state lets later chapters slot a cache and a scheduler into the same shape.

code/s01_generation_loop.py (excerpt)python
class Engine:
    """The smallest thing that deserves the name."""

    def __init__(self, model, tokenizer, max_context=512):
        self.model = model
        self.tok = tokenizer
        self.max_context = max_context

    def generate(self, prompt, max_tokens=64, temperature=1.0, seed=0):
        rng = np.random.default_rng(seed)
        ids = self.tok.encode(prompt)
        prompt_len = len(ids)
        stats = Stats(prompt_len=prompt_len)

        for step in range(max_tokens):
            # THE forward pass. Recomputes every position, every time.
            logits = self.model.forward(ids)      # (T, vocab)
            stats.record_pass(len(ids))

            next_id = sample(logits[-1], temperature, rng)
            ids.append(next_id)

            if next_id == self.tok.eos_id:
                stats.stopped = "eos"
                break
            if len(ids) >= self.max_context:
                stats.stopped = "context_full"
                break
        else:
            stats.stopped = "max_tokens"

        return self.tok.decode(ids[prompt_len:]), stats

Three things are worth noticing about that shape, because they recur for the next nineteen chapters:

  • Stopping is a policy, not an event. EOS, a token budget, a context limit, a stop string, a client disconnect: the engine checks all of them on every iteration. Real engines accumulate a dozen stop conditions here.
  • The stats object earns its place. You cannot optimise what you do not measure, and per-pass context length is the single most useful number to log. Every later chapter compares against it.
  • `logits[-1]` is where the waste lives. Keep an eye on that index. It becomes logits[0] in S05, and by then the engine is a hundred times faster.
Run it locally
Runs the naive loop on a bigram model and prints the generated text, followed by a cost table that compares the attention work actually performed against what a cached engine would have done.
$ python code/s01_generation_loop.py
Expect: A short generated sentence, followed by a table showing the no-cache/with-cache gap widening with every token.

Only NumPy is required — setup instructions.

Production notes

In production

In vLLM this loop lives in EngineCore.step(), where it is almost unrecognisable. Each of the five boxes in the diagram has grown into a subsystem, but the structure survives:

  • vLLM: EngineCore.step() calls the scheduler, then the model executor, then the output processor. (In the pre-V1 engine the same loop was LLMEngine.step(), which is the name most older write-ups use.) One call is still one iteration of this loop, serving many requests at once.
  • llama.cpp / picoLM: a literal C while loop that calls forward() and sample() and appends to a token array. Nothing else in production use stays this close to the whiteboard version.
  • TensorRT-LLM: the loop is compiled into the engine graph itself, so every shape must be known ahead of time.

The `for … else` is doing real work

Python's for…else clause runs only when the loop was not break-ed, which is exactly the "we hit max_tokens" case. Get it wrong and you have a classic off-by-one bug in finish-reason reporting: the field OpenAI-style APIs call finish_reason, which clients read to decide whether to continue.

Exercises

  1. 1
    Add a stop parameter accepting a list of strings. Stop strings are defined over text while you generate tokens, so you must detokenize incrementally and handle a stop string that straddles a token boundary.
  2. 2
    Make generate a generator that yields tokens as they are produced. This is the entire difference between a blocking API and a streaming one; see S19.
  3. 3
    Instrument the loop to print wall-clock time per pass. Confirm the growth is quadratic in context length, then predict how long a 4,000-token generation would take.

Continue

What's next

The loop calls tokenizer.encode and tokenizer.decode as if they were free and obvious. They are neither. S02 builds a byte-pair encoder, explains why streaming detokenization needs a buffer, and shows why your token counts never quite match the bill.

Check yourself

Questions

Answer before you look. A wrong answer tells you more than a right one, because the explanation points at the part of the chapter to reread.

Check yourselfQuestion 1 of 6

During decode (not prefill), why is the GPU mostly idle?

Score 0/6