How LLM Inference Works
Prefill vs decode, the KV cache, and why the first token is slow but the rest are fast.
Introduction
LLM inference is the process that turns a prompt into a generated response. The model is not writing a whole answer in one pass. It predicts one next token, appends that token to the context, then repeats the same operation until a stop condition fires.
In interviews, this lesson is where transformer knowledge becomes production knowledge. A strong answer explains why the prompt stage feels different from the generation stage, what the key-value cache stores, why long context and long output affect different latency metrics, and how serving engines keep GPUs busy.
This lesson follows the complete serving loop: tokenize the prompt, run prefill, build the KV cache, decode one token at a time, sample from logits, stream partial text, and stop safely. The goal is to reason about time-to-first-token, tokens per second, memory pressure, batching, and cost with enough precision to design real LLM systems.
Where this shows up in production
LLM inference shows up anywhere a product calls a generative model.
- Chat assistants and copilots use streaming inference so users see tokens before the full answer is ready.
- Search and RAG systems care about time-to-first-token because retrieval already added front-end latency.
- Coding agents and document tools often pay heavily for long prompts and long generated outputs.
- Model serving teams tune batching, quantization, and KV cache layout to reduce GPU cost.
- API platform teams expose max tokens, stop sequences, and streaming because they map directly to the inference loop.
Learning Objectives
Explain autoregressive generation as a loop that predicts one token and feeds it back into the next step.
Distinguish prefill from decode and connect each phase to time-to-first-token and inter-token latency.
Describe what the KV cache stores and why it avoids recomputing attention over past tokens.
Reason about compute-bound prefill, memory-bandwidth-bound decode, throughput, and tokens per second.
Compare static batching with continuous or in-flight batching for serving many requests.
Identify the main latency and cost levers: model size, quantization, context length, output length, and streaming.
Theory & Concepts
Autoregressive generation is a feedback loop
A decoder-only LLM generates text from left to right. Given a prompt, it produces logits for the next token, a decoding strategy chooses one token, and that token is appended to the context. The enlarged context becomes the input for the next prediction.
This loop is why output length is such a direct cost driver. A 500 token answer requires roughly 500 decode iterations after the prompt has been processed. The model can process the prompt in parallel, but it cannot generate token 200 until token 199 has been chosen.
Prefill processes the prompt and builds the KV cache
The prefill phase runs the full prompt through the transformer. Because all prompt tokens are already known, the GPU can process many positions in parallel and compute the key and value tensors for every layer. Those tensors become the KV cache.
Prefill also produces the first next-token logits. From a user perspective, prefill is the main contributor to time-to-first-token. Long prompts, large models, and high batch sizes all increase this first visible delay.
Decode reuses the cache one token at a time
After prefill, each decode step receives only the latest token plus the existing KV cache. The model computes new query, key, and value projections for the new position, attends over cached keys and values from prior positions, appends the new key and value to the cache, and emits logits for the next token.
This reuse is the reason inference is practical. Without the KV cache, every generated token would require rerunning the entire prompt and all previous output tokens through the model, wasting huge amounts of attention work.
Prefill and decode stress the GPU differently
Prefill is usually compute-bound. It performs large matrix multiplications over a full prompt and can keep tensor cores busy, especially when requests are batched together. Decode is often memory-bandwidth-bound because each step does relatively little new compute but must read model weights and a growing KV cache for each token.
That distinction explains two different user metrics. Time-to-first-token measures how long the prefill path takes before the first token can be streamed. Inter-token latency measures the gap between generated tokens during decode, and tokens per second is its throughput view.
Sampling and stopping sit after logits
The transformer does not directly output text. It outputs logits over the vocabulary. A decoding strategy such as greedy decoding, temperature sampling, top-p, or top-k chooses the next token from those logits. The sampling-and-decoding lesson covers those policies in depth.
The generation loop stops when the sampler picks an EOS token, when the request reaches its max tokens budget, or when the detokenized output matches a configured stop sequence. Serving systems need all three because model-native stopping, product limits, and application-specific delimiters solve different problems.
Architecture Diagram
The diagram separates logical responsibilities rather than physical processes. In a real serving engine, prefill, decode, logits projection, sampling, and cache writes may be fused or scheduled across multiple GPUs, but the control flow is the same: process the prompt once, then generate one token at a time.
The KV cache is drawn as a first-class cache because it is the central state object during inference. It stores key and value tensors for every layer and every active sequence position. As context grows, cache memory grows linearly with batch size and sequence length, which is why the context-windows-and-kv-cache lesson is a direct follow-up.
The loop edge from next token back to decode is the autoregressive dependency. It is also the source of inter-token latency: the system cannot start the next decode step for a request until sampling has selected the current token and stop checks have passed.
Request Flow
- 1
1. Tokenize the prompt
The client text is converted into token ids. The server also records request settings such as max tokens, temperature, stop sequences, stream mode, and any batching priority metadata.
- 2
2. Schedule the request
The serving engine places the request into a prefill batch. Static batching waits for a fixed group or timeout, while continuous batching can insert work as GPU slots become available. The scheduler is trying to raise utilization without adding too much queueing delay.
- 3
3. Run prefill over all prompt tokens
The model processes the prompt positions in parallel through every transformer layer. This phase performs large dense matrix operations, builds key and value tensors for all prompt tokens, and produces logits for the first generated token.
- 4
4. Store the KV cache
For each layer, the engine stores the key and value tensors that future tokens will attend to. Cache allocation can be simple contiguous memory or a paged layout that avoids wasting memory when sequences have different lengths.
- 5
5. Sample the first token
The logits are adjusted by the configured decoding strategy. Greedy decoding may pick the largest logit, while temperature, top-k, or top-p sampling inject controlled randomness. The selected token is appended to the generated output.
- 6
6. Decode the next token using the cache
The model receives only the newest token for this request. It computes that token query, key, and value, reads cached keys and values for the full prior context, writes the new key and value, and emits another logits vector.
- 7
7. Stream and check stop conditions
The server can detokenize and stream text chunks as tokens arrive. After each token, it checks for EOS, max tokens, stop sequences, cancellation, or safety gates. If none apply, the decode loop continues.
- 8
8. Finalize the response
When generation stops, the server flushes any buffered text, returns usage metadata such as prompt tokens and completion tokens, releases KV cache blocks, and records latency metrics for prefill, decode, and total request time.
Deep Dive
Why prefill is compute-bound
Prefill looks like training forward pass without the backward pass. The model evaluates many prompt positions at once, so matrix multiplications are large enough to use GPU tensor cores efficiently. Attention over the prompt is also parallel because every prompt token is known before generation starts.
This is why prompt length has a strong effect on time-to-first-token. More prompt tokens mean more dense compute before the first streamed token can appear. Batching several prompts can improve GPU utilization, but it can also increase queueing delay if the scheduler waits too long to form a batch.
Why decode is memory-bandwidth-bound
Decode performs one position per active request at a time. Each step still has to read model weights and scan cached keys and values, but it does not have enough arithmetic work per request to fully occupy the GPU. The limiting factor often becomes moving bytes from GPU memory rather than raw floating point operations.
This is why tokens per second improves with batching up to a point. More active sequences give the GPU more work per decode iteration, but the KV cache also grows and consumes memory bandwidth. A serving system is constantly balancing throughput, latency, and memory headroom.
KV cache mechanics and growth
The KV cache stores the key and value projections generated inside self-attention for every layer. During decode, the new token query attends to all previous keys and uses the corresponding values to build the attention output. Cached keys and values avoid recomputing projections for past tokens.
Cache size grows linearly with batch size, number of layers, KV heads, head dimension, and total sequence length. It also grows as output tokens are generated. This is the practical reason long context windows are expensive even when attention compute has been optimized, and the context-windows-and-kv-cache lesson covers the memory math in more detail.
Static batching versus continuous batching
Static batching groups requests at a fixed boundary, runs them together, and usually waits for the whole group to finish. It is simple, but it wastes GPU slots when short generations finish while long generations continue.
Continuous batching, also called in-flight batching, lets new requests join between decode steps and removes completed requests immediately. This keeps the GPU busier for mixed workloads and is a major reason modern LLM serving engines can deliver high throughput without requiring every request to have the same length.
Serving engines and PagedAttention
Engines such as vLLM and TensorRT-LLM optimize the same logical loop with specialized kernels, scheduling, memory planners, tensor parallelism, and fast sampling paths. They try to keep the GPU doing useful work while minimizing cache fragmentation and wasted memory copies.
PagedAttention is the idea of managing the KV cache in fixed-size blocks, similar to virtual memory pages. Instead of reserving one large contiguous buffer for every request, the engine maps each sequence to cache pages. This improves memory utilization when request lengths vary and makes continuous batching easier to schedule.
Production Considerations
Latency metrics need phase boundaries
Track queue time, prefill time, time-to-first-token, inter-token latency, output tokens per second, and total latency separately. A system can have a fast decode loop but poor user experience if requests wait too long in a batch queue, or if long prompts dominate prefill.
Cost levers are mostly token and model levers
Larger models increase weight memory and per-token compute. Longer prompts increase prefill work and KV cache size. Longer outputs increase the number of decode steps. Quantization can reduce memory and bandwidth, but it must be tested for quality regressions on the product workload.
Streaming improves perceived latency, not total work
Streaming sends detokenized chunks as soon as the decode loop produces them, which makes the application feel responsive after time-to-first-token. It does not reduce the number of model steps. It can even add application complexity because clients must handle partial text, cancellation, and final usage metadata.
Operational guardrails protect the serving pool
Production systems enforce max context, max output tokens, request timeouts, admission control, and per-tenant quotas. These limits prevent a small number of very long requests from monopolizing KV cache memory and reducing throughput for everyone else.
Interview Perspective
What interviewers look for
- ✓A crisp explanation that generation is autoregressive and sequential after the prompt has been processed.
- ✓Correct distinction between prefill, decode, time-to-first-token, inter-token latency, and tokens per second.
- ✓Understanding of the KV cache as stored keys and values, not a generic response cache.
- ✓Ability to connect batching, quantization, context length, and output length to concrete latency and cost tradeoffs.
Alternative designs
No KV cache
A naive implementation could rerun the whole prompt and generated prefix for every next token. It is simpler to explain but far too expensive in production because it recomputes attention projections for every past token on every step.
Speculative decoding
A smaller draft model proposes several tokens, and the larger target model verifies them. When the draft is accurate, the server accepts multiple tokens per target-model pass. This can reduce latency, but it adds model coordination complexity and does not remove the need for KV cache management.
Likely follow-up questions
Why does the first token often take longer than later tokens?
The first token waits for tokenization, queueing, prefill, and sampling. Prefill processes the entire prompt through all transformer layers and builds the KV cache, so a long prompt can be expensive before any output is visible. Later tokens reuse the cache and only run one new position at a time, so the user sees smaller inter-token gaps.
Why does decode become memory-bandwidth-bound?
Each decode step has limited new arithmetic because it processes only the latest token for each active sequence. However, it still reads model weights and the KV cache, and the cache grows with sequence length. The bottleneck often becomes moving those bytes through GPU memory fast enough, not doing more floating point math.
How would you improve throughput for a high-traffic chat API?
Use continuous batching so new requests can join between decode steps, cap prompt and output lengths, choose an appropriately sized model, quantize if quality allows, and use a serving engine with efficient KV cache management. Then monitor time-to-first-token and tokens per second separately because optimizations can improve one while hurting the other.
Common mistakes
- ×Saying the model generates the whole answer in parallel instead of one token at a time.
- ×Describing the KV cache as cached final text rather than cached attention keys and values.
- ×Optimizing only total latency while ignoring time-to-first-token and inter-token latency.
- ×Assuming larger batches always help, without considering queueing delay, cache memory, and tail latency.
- ×Forgetting that stop sequences are checked on detokenized text, while EOS is a model token.
Visual Learning
Prefill versus decode
| Phase | What it processes | Main bottleneck | User-facing metric |
|---|---|---|---|
| Prefill | All prompt tokens in parallel | Compute | Time-to-first-token |
| Decode | One new token per active request | Memory bandwidth | Inter-token latency |
| Sampling | One logits vector | Policy and filtering overhead | Per-token choice quality |
Latency and cost levers
| Lever | Primary effect | Tradeoff | Common mitigation |
|---|---|---|---|
| Model size | More weights and compute per token | Higher quality but higher latency and cost | Use the smallest model that meets quality |
| Context length | More prefill work and KV cache memory | Better grounding but slower first token | Retrieve and trim to relevant context |
| Output length | More decode iterations | More complete answer but higher total latency | Set max tokens and concise instructions |
| Quantization | Lower memory and bandwidth | Possible quality or accuracy loss | Evaluate on production-like prompts |
Batching strategies
| Strategy | How it works | Strength | Risk |
|---|---|---|---|
| Static batching | Runs a fixed group together | Simple and predictable | Wastes slots when requests finish at different times |
| Continuous batching | Adds and removes requests between decode steps | Higher utilization for mixed lengths | Requires more complex scheduling |
| Priority batching | Schedules by tier or deadline | Controls latency for important traffic | Can starve low-priority workloads without quotas |
Decision guide
How to tune an inference path
Use a smaller or quantized model when latency and serving cost matter more than marginal quality. Validate quality with the same prompt shapes your product will send.
Use prompt trimming and retrieval discipline when time-to-first-token is high. Long prompts expand prefill work and KV cache memory before the user sees anything.
Use continuous batching when traffic is high and request lengths vary. It usually improves GPU utilization more than static batching, especially during decode.
Use streaming responses when perceived responsiveness matters. Streaming does not reduce compute, but it turns a long wait into visible progress after the first token.
Use output caps and stop sequences to control cost. The decode loop runs once per generated token, so unbounded generation is both a latency and budget problem.
Hands-on Examples
Estimate KV cache memory
This rough estimator shows why sequence length and batch size matter. It counts keys and values for every layer, token, and active sequence. Real engines add alignment and paging overhead, but the scaling relationship is the important lesson.
kv_cache_estimate.py
def kv_cache_gib(layers, kv_heads, head_dim, tokens, batch, bytes_per_value=2):
values = 2 * layers * kv_heads * head_dim * tokens * batch * bytes_per_value
return round(values / (1024 ** 3), 2)
small_batch = kv_cache_gib(layers=32, kv_heads=8, head_dim=128, tokens=4096, batch=4)
large_batch = kv_cache_gib(layers=32, kv_heads=8, head_dim=128, tokens=16384, batch=16)
print("small batch GiB:", small_batch)
print("large batch GiB:", large_batch)Simulate the autoregressive loop
This pseudocode-like Python keeps the key pieces visible: logits are produced, a sampler chooses a token, the token is appended, and stop conditions are checked after each step.
decode_loop.py
def model_step(context_tokens, kv_cache):
logits = {"hello": 3.2, "world": 2.1, "<eos>": 0.4}
kv_cache.append("new_key_value")
return logits, kv_cache
def greedy_sample(logits):
return max(logits, key=logits.get)
context = ["Prompt:"]
kv_cache = []
output = []
max_tokens = 5
stop_sequences = ["hello world"]
for _ in range(max_tokens):
logits, kv_cache = model_step(context, kv_cache)
token = greedy_sample(logits)
if token == "<eos>":
break
output.append(token)
context.append(token)
text = " ".join(output)
if any(text.endswith(stop) for stop in stop_sequences):
break
print("generated:", " ".join(output))Quiz
0/6 answered
1.What does autoregressive generation mean for a decoder-only LLM?
2.What is the main job of the prefill phase?
3.Why does the KV cache improve decode efficiency?
4.Which metric is most directly tied to the decode loop after generation has started?
5.Why do modern serving engines use continuous or in-flight batching?
6.Which stop condition is model-native rather than application-defined?
Flashcards
Cheat Sheet
LLM inference cheat sheet
The loop
- Tokenize the prompt.
- Run prefill over the full prompt.
- Build the KV cache.
- Produce logits for the next token.
- Sample one token.
- Append the token to context and output.
- Decode the next token using the cache.
- Stop on EOS, max tokens, stop sequence, timeout, or cancellation.
Prefill
- Processes all prompt tokens in parallel.
- Builds key and value tensors for every layer.
- Drives time-to-first-token.
- Usually compute-bound.
- Gets more expensive as prompt length grows.
Decode
- Processes one new token per active request.
- Reuses the KV cache for prior positions.
- Drives inter-token latency and tokens per second.
- Often memory-bandwidth-bound.
- Gets more expensive as output length and active batch size grow.
KV cache
- Stores attention keys and values, not final text.
- Avoids recomputing attention projections for past tokens.
- Grows with layers, KV heads, head dimension, batch size, and total sequence length.
- Needs careful memory management for long contexts and mixed request lengths.
Serving levers
- Model size: larger usually means better quality but more latency and cost.
- Quantization: lowers memory and bandwidth, with possible quality tradeoffs.
- Context length: increases prefill and cache memory.
- Output length: increases decode iterations.
- Batching: improves GPU utilization but can add queueing delay.
- Streaming: improves perceived responsiveness after the first token.
Interview one-liner
LLM inference is a two-phase autoregressive serving loop: prefill computes the prompt and builds the KV cache, then decode repeatedly reuses that cache to generate one sampled token at a time.
References
- PaperEfficient Memory Management for Large Language Model Serving with PagedAttention — Kwon et al.
- DocsTensorRT-LLM Documentation — NVIDIA
- DocsHugging Face Text Generation Strategies — Hugging Face
- PaperOrca: A Distributed Serving System for Transformer-Based Generative Models — Yu et al.