03 — Engines Papers

Phase alignment: Months 8–12 (Phase 4). Read these while building your mini inference engine.

This is the heart of the roadmap and the literal syllabus of the job. The papers form a lineage: every paper fixes the failure mode of its predecessor. Read them in order.

1. Orca: A Distributed Serving System for Transformer-Based Generative Models

OSDI ‘22 · Yu et al. · https://www.usenix.org/conference/osdi22/presentation/yu · [HARD] · Prereqs: transformer basics

Key trick: Schedule at iteration granularity rather than request granularity — every decode step, finished sequences leave the batch and waiting sequences join, keeping the GPU full without waiting for the longest sequence.

What to extract:

  • Continuous batching (also called in-flight batching / iteration-level scheduling). This one idea gives 10–20× throughput and is the foundation of every engine after 2022.

  • Selective batching: attention is per-sequence but linear layers batch across all active sequences. Different ops have different batching rules — internalize this.

  • Request pool + batching engine + scheduler decomposition. This is the shape of every modern engine’s code.

  • No paged KV yet — Orca still had fragmentation issues, which sets up the next paper.

Cost: requires careful attention-kernel dispatch because sequences have different KV lengths (see FlashInfer, paper #7 in the kernels set).

2. Efficient Memory Management for Large Language Model Serving with PagedAttention (vLLM)

arxiv:2309.06180 · Kwon et al., SOSP ‘23 · [HARD] · Prereqs: paper #1, virtual memory concepts

Key trick: Store KV cache in fixed-size non-contiguous blocks (typically 16 tokens), with a per-sequence block table mapping logical positions to physical blocks — mimicking OS virtual memory. Fragmentation drops from 60–80% to <4%, effective batch size 2–4×, throughput 2–4×.

What to extract:

  • The waste taxonomy Section 3: internal fragmentation (unused slots in reserved buffer), external fragmentation (unreserved gaps), reservation waste (reserved-not-yet-used). PagedAttention eliminates all three.

  • The block table structure. Draw it.

  • Copy-on-write for beam search and parallel sampling — physical blocks shared across logical sequences with a refcount. This is the mechanism prefix caching later reuses.

  • The PagedAttention kernel: it must gather K/V from non-contiguous blocks. Look at vLLM’s csrc/attention/attention_kernels.cu (superseded by FlashInfer in V1 but read the original once).

  • The metric that matters: fraction of KV memory effectively used. vLLM hits >96%.

Read alongside: the vLLM V1 architecture docs at https://docs.vllm.ai/en/latest/design/arch_overview.html — the paper’s design has been refined significantly.

Implement it: your mini-engine’s block manager (Phase 4 capstone) is a direct exercise on this paper.

3. Sarathi / Sarathi-Serve: Chunked Prefill and Stall-Free Scheduling

arxiv:2308.16369 (Sarathi) + arxiv:2403.02310 (Sarathi-Serve) · Agrawal et al. · OSDI ‘24 · [HARD] · Prereqs: #2

Key trick: Split long prefills into fixed-size chunks and co-schedule them with decode steps of other sequences in one hybrid batch — trading a small TTFT increase for smooth per-decode-step latency (no more ITL spikes when a big prompt lands).

What to extract:

  • Why the naive vLLM had ITL spikes: during a large prefill nothing else could decode. Users saw the model “stall.”

  • The token budget per step: prefill contributes chunk_size tokens, decode contributes 1 token per running sequence. Balance these so each step is roughly compute-bound but latency-bounded.

  • The nuanced tradeoff: chunked prefill has slightly worse prefill throughput (fewer FLOPs per token attention because K/V of later chunks not yet present), but way better decode SLA. In production, decode SLA wins.

  • “Stall-free scheduling” is now the default in vLLM (--enable-chunked-prefill) and SGLang. This paper defines it.

Numbers to memorize: typical chunk_size 512–2048; token budget 8k–16k per step on H100.

4. SGLang: Efficient Execution of Structured Language Model Programs (RadixAttention)

arxiv:2312.07104 · Zheng et al., NeurIPS ‘24 · [HARD] · Prereqs: #2

Key trick: Store KV cache in a radix tree keyed by token sequence, with LRU eviction on internal nodes. Shared prefixes across requests (system prompts, few-shot exemplars, agentic tool-call history) get computed once — cache hit rates of 50–90% in real workloads.

What to extract:

  • The radix tree structure. Each edge holds a run of tokens; each node has KV blocks. Insertions match the longest common prefix.

  • LRU eviction at the leaf — the tree is a cache, not a database.

  • Why this is the paper for your agentic-harness day job: multi-turn tool-calling reuses 90%+ of previous KV. RadixAttention is why SGLang crushes vLLM on agentic workloads (until vLLM caught up with automatic prefix caching).

  • The frontend DSL is a separate contribution — skim it, focus on RadixAttention.

  • Automatic prefix caching (APC) in vLLM is a hash-based flavor of the same idea. Learn both.

Read the source: https://github.com/sgl-project/sglang/blob/main/python/sglang/srt/mem_cache/radix_cache.py. It’s 400 lines. Read it end to end.

5. Fast Inference from Transformers via Speculative Decoding (Leviathan et al.)

arxiv:2211.17192 · Leviathan, Kalman, Matias · ICML ‘23 · [MEDIUM] · Prereqs: sampling basics

Key trick: A small draft model proposes k tokens; the target model verifies them in one parallel forward pass; via rejection sampling you accept the longest correct prefix — mathematically identical output distribution, ~2–3× wall-clock speedup.

What to extract:

  • The rejection sampling math. It is not “trust the small model when it’s confident” — it is a proper sampler that preserves the target distribution exactly.

  • The parallel verification insight: one forward pass at seq_len = k+1 costs the same as one decode step (both memory-bound) but produces up to k+1 tokens. Free FLOPs used well.

  • Acceptance rate α, average token yield E[tokens] = (1 − α^(k+1))/(1 − α). For α=0.7, k=5: ~2.85 tokens/step.

  • The economics: speculation shines at low batch (decode is memory-bound, so verify is nearly free). At high batch decode becomes compute-bound and speculation stops paying. This asymmetry matters a lot for engine design.

Companion: Chen et al. “Accelerating Large Language Model Decoding with Speculative Sampling” (arxiv:2302.01318) — same idea, DeepMind version, more detailed sampling math.

6. Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads

arxiv:2401.10774 · Cai et al., 2024 · [MEDIUM] · Prereqs: #5

Key trick: Skip the separate draft model — bolt extra decoding heads onto the target model itself, each predicting a token k steps ahead. Verify tree of candidates in one forward pass.

What to extract:

  • The tree attention mask: multiple candidate token sequences merged into one batch via a carefully constructed causal mask. See Figure 3.

  • Medusa-1 (frozen backbone) vs Medusa-2 (joint training). Medusa-1 is what production engines usually adopt.

  • Tree pruning: not all candidate paths are worth verifying — top-k per position.

  • Superseded by EAGLE, but the tree-attention machinery is inherited.

7. EAGLE / EAGLE-2 / EAGLE-3 lineage

  • EAGLE-1: arxiv:2401.15077 (Li et al., 2024)

  • EAGLE-2: arxiv:2406.16858 (2024)

  • EAGLE-3: arxiv:2503.01840 (2025) · [HARD] · Prereqs: #5, #6

Key trick: Instead of drafting token IDs, draft the feature vector (second-to-last hidden state) autoregressively with a small drafter model, then project to logits. Features are lower-entropy than tokens, so acceptance rates soar (~0.8+).

What to extract per version:

  • EAGLE-1: Feature-level autoregressive drafter. Predicts hidden states, not tokens. One-step-ahead training. ~2× on top of Medusa.

  • EAGLE-2: Dynamic draft tree — the drafter’s own confidence scores decide which candidates to verify. Skip the fixed tree topology.

  • EAGLE-3: Multi-layer feature aggregation. Test-time training via training-time simulation. Current state of the art (2025–2026).

  • Production reality: EAGLE-2 and -3 are integrated in vLLM, SGLang, TensorRT-LLM. Ship models come with EAGLE weights (e.g., DeepSeek-V3.2 EAGLE heads).

Read alongside: vLLM’s speculative decoding docs (https://docs.vllm.ai/en/latest/features/spec_decode.html) — the paper explains the algorithm, the docs explain the config.

8. DeepSeek-V3 Multi-Token Prediction (MTP)

Part of arxiv:2412.19437 · DeepSeek-AI, 2024 · [MEDIUM] (this section only) · Prereqs: #5

Key trick: Train the model itself to predict k future tokens at each position via lightweight MTP heads. At inference these heads become the speculative drafter — no separate model, no separate training.

What to extract:

  • MTP heads share the transformer trunk. Very cheap to add.

  • The training loss: sum of k next-token losses, each conditioned on all preceding predicted tokens (properly causal).

  • Why DeepSeek did this: at 671B / 37B-active, running a separate draft model was untenable. Bake speculation in.

  • This is where speculative decoding becomes an architectural feature, not a serving-time hack. Expect more frontier models to ship with MTP heads.

9. Outlines / Efficient Guided Generation (Willard & Louf)

arxiv:2307.09702 · [MEDIUM] · Prereqs: regex / finite automata basics

Key trick: Compile the grammar / regex / JSON schema into an FSM, precompute per-state the set of allowed next tokens (a mask over the tokenizer), and at each decode step apply that mask to the logits — cost is a single lookup per step.

What to extract:

  • Why naive constrained decoding is slow: rechecking the whole grammar at every step is O(vocab × grammar). Outlines does it in O(1) amortized.

  • The tokenizer/grammar mismatch: BPE tokens don’t align with grammar symbols. The FSM must be lifted to token space via subset construction. Read Section 4.

  • Structured output = JSON schema → regex → NFA → DFA → per-state token mask. Each step is well-studied CS.

  • Practical: Outlines is a library, but the ideas are what you extract. XGrammar (below) has largely replaced it in the mainline engines.

10. XGrammar: Flexible and Efficient Structured Generation Engine for LLMs

arxiv:2411.15100 · Dong et al., 2024 · [HARD] · Prereqs: #9, pushdown automata

Key trick: Extend Outlines-style FSM masking to context-free grammars via pushdown automata, use bitmask token filtering with a persistent execution stack, and cache mask computation per grammar state.

What to extract:

  • Why CFG > regex for real workloads: recursive JSON (nested objects), mathematical expressions, code. FSMs can’t handle nesting.

  • The stack-based execution model: pushdown automaton state + a stack of grammar rules being expanded.

  • Two-level lookahead cache: (grammar state, prev token) → allowed token bitmask.

  • Numbers: near-zero overhead on top of unconstrained generation for typical JSON schemas (Table 4).

  • Used by SGLang and vLLM as the default structured-output backend since late 2024.

11. DistServe / Mooncake (preview only in this section — full read in Phase 6)

  • DistServe: arxiv:2401.09670 — split prefill and decode onto different GPU pools.

  • Mooncake: arxiv:2407.00079 — Kimi’s KV-cache-centric architecture. FAST ‘25 best paper.

Read now: just the abstracts and Figure 1 of each. You need to know the vocabulary (“disaggregation”, “KV transfer”, “goodput”) when reading vLLM/SGLang PD implementation code. Full engagement in 05_distributed_papers.md.

12. Cascade Inference / Multi-Query Cascade Attention (FlashInfer optimization)

Referenced in FlashInfer paper (kernels #7) · Blog: https://flashinfer.ai/2024/02/02/cascade-inference.html · [EASY] · Prereqs: #4, FlashInfer

Key trick: When many requests share a long prefix (system prompt), the attention over the shared prefix can be computed once (batched across all requests) and combined with each request’s private-suffix attention via log-sum-exp merging — turns memory-bound decode over the shared prefix into a compute-bound single-pass.

What to extract:

  • The two-level attention: shared-prefix (compute-bound at high batch) + private-suffix (memory-bound at low batch), merged via LSE.

  • Why this is unlocked by prefix caching plus FlashInfer — you can’t do it without both.

  • Numbers: 2–4× decode throughput improvement when prefix ratio > 90%.

The whiteboard test

At the end of Phase 4 you should be able to trace, on a whiteboard, a request’s life through vLLM V1:

HTTP arrives → tokenize → engine.add_request()
  → scheduler.schedule() (pick from waiting queue, token budget check)
  → block_manager.allocate() (paged, with prefix-cache hit check)
  → model_runner.execute_model()
     → FlashInfer plan (based on active seqs) → prefill (possibly chunked) → decode iter
     → speculative decoding: draft k, verify, accept
  → sampler + guided-decoding mask (if any)
  → new tokens → detokenize → SSE stream out
  → if EOS: block_manager.free() → engine.finish_request()
  → else: sequence stays in running queue for next iteration

Every arrow above is 1–2 of the papers in this section. If you can name which paper each arrow corresponds to, you own the engine.