03 — PagedAttention & the vLLM V1 Architecture

Paper: Kwon, Li, Zhuang, Sheng, Zheng, Yu, Gonzalez, Zhang, Stoica — “Efficient Memory Management for Large Language Model Serving with PagedAttention” (SOSP ‘23). arXiv: <phone_number_or_numberic_id_or_random_id_29>. Repo: https://github.com/vllm-project/vllm (~66K stars as of mid-2026, V1 architecture).

The problem: KV cache fragmentation kills throughput

Recall from Phase 1: KV cache size scales as 2 × layers × kv_heads × head_dim × bytes × seq_len × batch. For Llama-3-70B at 4k context in fp16 that’s ~2.5GB per sequence. Multi-tenant serving is fundamentally a KV-cache-capacity problem.

Pre-vLLM engines allocated KV cache contiguously per sequence, and had to reserve the max possible length upfront (you don’t know how long the model will generate). Consequences:

  1. Internal fragmentation. A sequence with max_tokens=2048 that generates 300 tokens has reserved 1748 tokens of KV memory for nothing.

  2. External fragmentation. Different sequences with different reservations create holes in GPU memory that can’t be reused.

  3. No sharing. Two requests with the same 500-token system prompt each store their own copy of the prefix KV.

Measured effective KV utilization in the vLLM paper: often 20-40%. The other 60-80% is fragmentation. That’s not an optimization opportunity, that’s a scandal.

The insight: KV cache is virtual memory

Operating systems solved a structurally identical problem in the 1960s. Don’t allocate contiguous physical memory per process; instead:

  • Split physical memory into fixed-size pages (blocks).

  • Give each process a page table mapping virtual addresses → physical pages.

  • Allocate pages on-demand as the process grows.

  • Share pages between processes when their contents match (copy-on-write).

PagedAttention is exactly this, for KV cache.

  • KV cache memory is chopped into fixed-size blocks (default: 16 tokens’ worth of K + V, all layers).

  • Each sequence has a block table: an array of block IDs, indexed by logical block number (i.e., by which chunk of the sequence).

  • New tokens allocate new blocks on-demand from a free pool.

  • Shared prefixes point to the same physical block from multiple sequences’ block tables. Copy-on-write when a diverging write comes in.

  • The attention kernel is modified to gather from non-contiguous blocks using the block table — hence “Paged”Attention.

Result: KV memory utilization jumps to ~96-99%. Effective batch size doubles or triples on the same hardware. Throughput follows.

The block table walkthrough

Make this picture concrete. Say block size = 4 tokens (real vLLM default is 16; 4 fits on a page). Assume 2 sequences share a prefix.

Sequence A has tokens (positions 0..11): [The, cat, sat, on, the, mat, and, purred, softly, at, dawn, .]

Sequence B has tokens (positions 0..9): [The, cat, sat, on, the, mat, but, meowed, instead, .]

Both share the first 6 tokens: The cat sat on the mat. That’s 2 blocks (0-3, 4-7 partially).

Physical KV block pool (with contents shown as token position ranges):

 Block ID | Refcount | Contents (logical positions)
     0    |    2     | positions 0..3    "The cat sat on"
     1    |    1     | positions 4..7    "the mat and purred"       (A's continuation)
     2    |    1     | positions 4..7    "the mat but meowed"       (B's continuation, diverged)
     3    |    1     | positions 8..11   "softly at dawn ."         (A)
     4    |    1     | positions 8..9    "instead ."                (B, partially filled)

Block tables:

Seq A block table: [0, 1, 3]
Seq B block table: [0, 2, 4]

Block 0 is shared (refcount 2). Note the divergence: position 4 is “the” for both, but position 6 is “and” vs “but”, so the block containing positions 4-7 had to fork — that’s the copy-on-write at the point of divergence. Block 0 remained shared because both sequences agree on all its tokens.

(In practice CoW is done at block boundaries — you copy the whole block when a write inside it would diverge. This is why prefix caching benefit is discretized in units of block-size tokens.)

The attention kernel side

When the model runs attention for a sequence, it needs to compute softmax(Q · K^T / √d) · V over all past K, V. In vLLM this becomes:

  1. Look up the sequence’s block table.

  2. For each block in the table, fetch the K and V tiles from the physical block pool at that block ID’s memory address.

  3. Compute attention over the gathered tiles (this is what FlashInfer / the paged attention kernels do — they take the block table as an input tensor and index into it internally).

The cost of this indirection is one extra pointer lookup per block per attention op — essentially free in practice.

Preemption & eviction

With paged KV you can also preempt running sequences when memory pressure spikes. Two strategies:

  • Swap — write the sequence’s blocks out to CPU RAM, free the GPU blocks, later swap them back. Used at high memory pressure.

  • Recompute — free the blocks entirely, re-run prefill later when scheduled. Cheaper if the sequence is short (recompute < swap-in time).

vLLM’s scheduler picks between them by heuristic on sequence length.

The vLLM V1 architecture (verified as of mid-2026)

vLLM was fundamentally re-architected between V0 and V1 (V1 alpha released Jan 27, 2025 at https://vllm.ai/blog/2025-01-27-v1-alpha-release, now default). The V1 process model:

┌──────────────────────────────────────────────────────────────────────┐
│                     API Server Process                               │
│  FastAPI/uvicorn ▸ tokenizer ▸ request queue ▸ streaming detokenize  │
│  (vllm/v1/engine/async_llm.py:AsyncLLM)                              │
└──────────────────────────────────────────────────────────────────────┘
                              ▲   │ (ZMQ IPC)
                              │   ▼
┌──────────────────────────────────────────────────────────────────────┐
│                    EngineCore Process                                │
│  ┌─────────────┐  ┌──────────────────┐  ┌────────────────────────┐   │
│  │  Scheduler  │──│  KV Cache Mgr    │  │  Model Executor        │   │
│  │  (iteration │  │  (block table,   │──│  (dispatches forward   │   │
│  │   loop)     │  │   prefix cache)  │  │   to workers)          │   │
│  └─────────────┘  └──────────────────┘  └────────────────────────┘   │
│  (vllm/v1/engine/core.py:EngineCore.run_busy_loop)                   │
└──────────────────────────────────────────────────────────────────────┘
                              ▲   │ (ZMQ/NCCL)
                              │   ▼
┌──────────────────────────────────────────────────────────────────────┐
│                  GPU Worker Process(es) (TP/PP)                      │
│  Model weights ▸ paged KV blocks ▸ attention kernels                 │
│  (vllm/v1/worker/gpu_model_runner.py:GPUModelRunner)                 │
└──────────────────────────────────────────────────────────────────────┘

Why multi-process? V0 had the scheduler, engine, tokenizer, and worker on the same Python process, and the GIL + tokenizer overhead capped throughput. V1 isolates: the API server can do tokenization and HTTP handling while the EngineCore is blocked in a scheduling decision; the worker never waits for the API server.

The engine loop, in six lines

# vllm/v1/engine/core.py (simplified)
def run_busy_loop(self):
    while True:
        new_requests = self._pull_from_ipc_queue()
        for r in new_requests:
            self.scheduler.add_request(r)
        scheduler_output = self.scheduler.schedule()   # WHAT runs this step
        model_output = self.model_executor.execute_model(scheduler_output)
        engine_output = self.scheduler.update_from_output(model_output)
        self._push_to_ipc_queue(engine_output)         # streaming tokens

Everything in vLLM V1 lives inside that loop. When the loop runs 200-500 times per second you have a working LLM server.

The scheduler’s schedule() step

vllm/v1/core/sched/scheduler.py:Scheduler.schedule() (method around line <phone_number_or_numberic_id_or_random_id_30> in current code). Simplified logic:

def schedule(self) -> SchedulerOutput:
    # 1. Determine token budget for this step (max-num-batched-tokens)
    token_budget = self.max_num_batched_tokens

    # 2. Continue running sequences (decode + resumed prefill chunks)
    for req in self.running:
        if not self.can_allocate(req):    # KV pressure → preempt
            self.preempt(req)
            continue
        num_new_tokens = min(req.num_pending, token_budget)
        token_budget -= num_new_tokens
        scheduled.append((req, num_new_tokens))

    # 3. Admit new waiting requests within remaining budget
    while self.waiting and token_budget > 0:
        req = self.waiting[0]
        num_prefill_tokens = min(req.prompt_len, token_budget)
        # Prefix cache lookup: does this prompt share blocks with something cached?
        cached_blocks = self.kv_cache_manager.get_computed_blocks(req)
        if not self.can_allocate(req, cached=cached_blocks):
            break
        self.allocate(req, cached_blocks)
        token_budget -= num_prefill_tokens
        scheduled.append((req, num_prefill_tokens))
        self.waiting.popleft()

    return SchedulerOutput(scheduled)

Read this until every branch makes sense. This is what you’re reimplementing in the capstone (file 09).

File-by-file map: vLLM V1 source (verified paths, mid-2026)

Read these in the order given. Total: about 4000 lines of dense Python that is the modern inference stack.

Order

Path

Read for

1

vllm/v1/engine/async_llm.py

Entry point. AsyncLLM.generate() (line ~315), output_handler (line ~366). Async streaming abstraction.

2

vllm/v1/engine/core.py

The heart. EngineCore, run_engine_core, run_busy_loop, _process_engine_step, step.

3

vllm/v1/engine/core_client.py

IPC between API server and EngineCore. get_output_async.

4

vllm/v1/core/sched/scheduler.py

Scheduler.schedule() around line <phone_number_or_numberic_id_or_random_id_30>. Iteration-level admission and preemption logic.

5

vllm/v1/core/kv_cache_manager.py

KVCacheManager.get_computed_blocks (line ~157). Prefix cache lookup, block allocation.

6

vllm/v1/core/single_type_kv_cache_manager.py

find_longest_cache_hit (line ~236). The hash-chain trie that powers prefix caching.

7

vllm/v1/worker/gpu_model_runner.py

Forward-pass orchestration: execute_model, _prepare_inputs, CUDA graph capture, attention metadata construction.

8

vllm/v1/attention/backends/

Attention backend abstraction. FlashInfer, FlashAttention paged, TritonAttention live here.

9

vllm/v1/executor/

Multi-worker orchestration (TP/PP).

10

vllm/v1/spec_decode/

Speculative decoding integration (EAGLE, ngram, MTP).

File 10 (10_vllm_source_map.md) expands this table with the actual question you should be asking as you read each file. This one is the quick-reference version.

Key V1 people to follow on GitHub

From the V1 tracking issue https://github.com/vllm-project/vllm/issues/8779:

  • WoosukKwon — vLLM co-creator (original PagedAttention paper author), V1 architect

  • zhuohan123 — co-creator, big contributor to scheduler design

  • youkaichao — V1 core, torch.compile integration

  • simon-mo — co-lead, community/ops

  • LiuXiaoxuanPKU — speculative decoding lead

  • njhill (RedHat) — chunked prefill + engine core; reviewer of Aleksa Gordić’s Inside vLLM blog

  • comaniac, robertgshaw2-neuralmagic, alexm-neuralmagic, rkooo567 — core reviewers

Watching their PR activity is a free master class.

Good-first-issue areas (as of mid-2026)

Issues tagged good first issue on vllm-project/vllm tend to cluster in:

  1. Benchmark scripts / bench_serving edge cases — dataset loaders, metric reporting bugs. Highest signal: perf regressions.

  2. Docs for V1 features — large surface area, chronically understaffed. Great first PR.

  3. New model support — template-heavy but formulaic once you’ve done one. Highest engagement in the community.

  4. Structured output / logit processor tests — XGrammar integration has edge cases you can find and fix.

  5. Metrics / observability — adding Prometheus counters, tracing spans. Directly aligned with your production/harness background.

Rule: use → benchmark → file a great issue → fix a small one → own a feature area. Path to “the credential in this field.”

The intuition to internalize

Once upon a time KV cache lived in one big slab per sequence, worst-case reserved, and 60% of it was air. Now KV cache lives in a page pool, is allocated per-block on-demand, is shared across sequences by block-table indirection, and is copy-on-written on divergence.

That is the entire trick. Everything else in vLLM — the multi-process architecture, the chunked prefill, the spec decoding integration, the torch.compile hooks — is an elaboration on that OS-inspired paging foundation. When you can explain the block table walkthrough above at a whiteboard from memory, you understand PagedAttention.