M5.3 - KV Memory Layout and Exact Reuse: PagedAttention, vAttention, and Prefix Caches

M5.3 - KV Memory Layout and Exact Reuse: PagedAttention, vAttention, and Prefix Caches

0x00 Historical Introduction And Owner Contract

M5.1 established that a K/V cache is persistent request state rather than an anonymous optimization tensor. M5.2 then made request membership an iteration-level decision:

observe immutable request frontiers
choose legal prefill intervals and decode rows
ask foreign subsystems whether the work is feasible
run one model iteration
publish completed service and cache progress
repeat

That loop still lacks a physical answer. A scheduler may estimate future K/V pressure and decide that a request should run, but those decisions do not create an address, reserve a real block, establish ownership, or prove that an old prefix is reusable.

The owner question is:

How does a serving runtime turn one logically continuous K/V sequence into versioned physical storage that can be allocated, shared, reused, mutated, and reclaimed exactly under concurrent requests?

M5.3’s thesis is that K/V memory efficiency is not only a tensor-size problem. It is an address, ownership, identity, index, and execution-reuse problem. PagedAttention, vAttention, prefix caching, RadixAttention, Prompt Cache, Hydragen, and ChunkAttention do not all solve the same one of those problems. The article will compare them only after naming the object and invariant each one owns.

0x00A From Rectangular Reservation To Dynamic Physical State

The simplest K/V implementation begins with an attractive invariant:

one request owns one contiguous tensor
the tensor has room for the request's maximum sequence length
token position t maps to a fixed stride from one base address

This layout makes addressing easy. If T_max,r token positions are reserved for request r, every layer knows where any possible future K/V row would live. The unresolved problem is that autoregressive serving does not know how many of those future rows will become useful.

request A may stop after 12 output tokens
request B may continue for 700
request C may arrive while both are running
request D may share 2,000 prompt tokens with A

The maximum length is an admission bound, not a realized allocation need. A rectangular reservation converts output uncertainty into held physical capacity. Requests finish at different iterations, contiguous holes appear in different sizes, and another request can be rejected even when the sum of free bytes looks sufficient. Related requests can also duplicate the same prefix state because their private rectangular ranges have no shared ownership object.

This is the historical transition recovered from A24: the K/V tensor formula alone does not explain serving capacity. The runtime also needs a memory manager whose allocation unit follows current committed state more closely than an uncertain maximum output.

PagedAttention, introduced by Kwon et al. with vLLM, borrows the operating system distinction between logical and physical memory. A request retains one logical token order, while a block table maps consecutive logical K/V blocks to physical blocks that need not be adjacent. New physical capacity can be acquired as the sequence grows, and physical blocks can be returned or shared without moving the entire logical sequence.

The analogy is useful but incomplete:

operating-system page table:
    virtual address -> physical frame

PagedAttention request block table:
    logical token block -> physical K/V block

additional serving obligations:
    valid-token tail
    per-layer or cache-group layout
    reference ownership
    copy-on-write before divergence
    compatibility identity before cross-request reuse
    kernel-visible translation metadata

vAttention later preserves a contiguous virtual K/V range and maps physical GPU pages on demand. It attacks the same reservation/fragmentation pressure with a different kernel boundary: PagedAttention exposes block indirection to a paged attention kernel, whereas vAttention tries to preserve ordinary contiguous virtual indexing. The detailed comparison belongs to Loop 8; the historical point is that dynamic physical commitment does not require one universal virtual layout.

Neither design, by itself, proves that two requests may share K/V. Paging answers where bytes live. Exact prefix reuse asks whether the bytes mean the same computation under the new request’s model, positions, transforms, adapter, representation, and isolation domain. Prefix indexes then ask how to find the longest matching reusable object. Hydragen and ChunkAttention add yet another question: can shared-prefix attention work be organized differently even when the mathematical output remains exact?

0x00B Five Contracts That Must Not Collapse

The phrase “K/V cache reuse” is too broad for implementation. This article uses five separate contracts:

These distinctions create four negative rules that remain active throughout the article:

allocation is not identity:
    owning a block does not make foreign K/V compatible

identity is not an index:
    a compatibility rule does not locate the longest match

an index hit is not a scheduling decision:
    M5.3 reports the hit; M5.2 decides when the request runs

storage reuse is not execution reuse:
    sharing bytes, skipping prefill, and batching shared-prefix attention
    are different savings with different baselines

All mechanisms in M5.3 are exact under their declared compatibility and algorithm contracts: they preserve the legal K/V history and attention result. Changing which old positions remain visible is a different operation owned by M5.4.

0x00C The Missing Object: KVPhysicalState

The article owns one conceptual object:

KVPhysicalState
    identity:
        allocator epoch
        request and publication generation
        logical cache ABI and compatibility namespace

    address state:
        cache groups
        logical-block or virtual-page mappings
        physical block/page handles
        valid-token tail

    ownership state:
        request references
        shared-prefix references
        mutable private tail
        cached, locked, and evictable state

    exact-reuse state:
        concrete prefix keys
        hash-chain or radix-index entries
        runtime-admissible reusable length

    transaction boundary:
        immutable prefix-match receipt
        immutable allocation/release receipt
        committed mutation or explicit failure

This is a teaching object, not a claim that vLLM, SGLang, or vAttention exposes one class with these fields. Later loops will map each field to paper contracts and pinned source observations, while keeping rewrite-derived safety fields explicitly labeled.

The direction of authority is:

M5.1 logical cache intent
    + M5.2 selected work and allocation intent
    + M5.7/M5.8/M8.6 declared cache representation
        -> M5.3 validates identity and mutates physical state
            -> PrefixMatchReceipt / AllocationReceipt / ReleaseResult
                -> M5.2 may make its next policy decision

The scheduler never turns intent into ownership by declaration. M5.3 publishes physical feasibility only after the allocator transaction commits.

0x00D Owner Contract: Consumes, Owns, And Defers

M5.3 may consume a fact without inheriting the mechanism that produced it. It may mention a downstream constraint without becoming that article’s owner.

This boundary permits M5.3 to derive a Hydragen or ChunkAttention merge schedule without re-owning online softmax. It permits a radix index to return a longest prefix hit without choosing service order. It permits an inactive session to have exact identity without explaining CPU, SSD, or remote transfer.

0x00E Source Continuity And Corrections

A24 and A25 provide the handwritten source spine. The reconstruction preserves their mechanism depth while tightening five shorthand statements:

The article will use primary papers for PagedAttention, vAttention, SGLang, Prompt Cache, Hydragen, ChunkAttention, and CachedAttention. Runtime claims are scoped to immutable source revisions: vLLM v0.23.0 at 0fc695fc6d1d82e9a5ac6835ac8e4e1c83703665, and the dereferenced SGLang v0.5.11 commit 612785ffdcaf35552f1ed433a981d596ca9fe900.

Those revisions are evidence anchors, not deployment recommendations. Paper speedups remain source-reported unless this repository later adds a declared hardware, workload, runtime, raw-sample, numerical-validation, and profiler manifest.

0x01 Claim Status And Scope

The article’s main distinction:

layout:
    preserve all K/V, change where it lives

exact reuse:
    preserve all semantics, skip recomputing a prefix already known to match

lossy retention:
    change which old K/V remains visible

M5.3 covers the first two. M5.4 covers the third.

0x01A Immutable Cache ABI, Layout, Identity, And Isolation

Loop 1 separated address, ownership, identity, index, and execution reuse. The next question is mechanical:

Which immutable facts must match before a runtime may interpret old K/V bytes, place them in a physical map, or return them as an exact prefix hit?

“The tokens match” is not an adequate answer. The same token IDs can produce different K/V when weights, adapters, upstream transforms, side inputs, or positions differ. Equal byte counts can describe incompatible layouts. A correct block hash can still cross an administrative boundary if isolation is not enforced outside the hash table.

This article therefore uses five records with different writers:

These records are immutable for one published cache generation. Changing an owned field produces a successor identity; it does not mutate the meaning of already-published blocks in place.

The concrete key narrows the search. It does not replace semantic, physical, or isolation compatibility.

Consume M5.1’s Logical Cache ABI; Do Not Re-Derive It

M5.1 already derives the logical cache ABI from:

artifact identity:
    base weights
    active adapter set
    weight transforms

logical cache schema:
    K/V axes
    local head ownership
    storage representation

position contract:
    cache positions
    RoPE/position semantics
    legal visibility interpretation

It also separates exact token/side-input prefix identity from tokenizer and chat-template provenance. M5.3 consumes cache_abi_sha256 and the exact input identity. Repeating the full model-to-row derivation here would create two authorities for the same semantic object.

M5.3 adds a physical projection because one logical ABI can have more than one legal realization:

same logical K/V row
    -> contiguous rectangular allocation
    -> PagedAttention blocks
    -> vAttention virtual range plus mapped physical pages
    -> a tiered or quantized representation declared by another owner

Logical compatibility is necessary. Physical interpretability is an additional requirement.

CacheLayoutManifest: How The Bytes Can Be Addressed

The article-local layout record is:

CacheLayoutManifest
    schema_version
    manifest_id
    logical_cache_abi_sha256
    model_generation

    cache_groups[]:
        cache_group_id
        layer interval or explicit layer IDs
        K/V heads local to this shard
        head dimension
        storage dtype
        tensor axis order
        stride/layout identity

    physical_mode:
        rectangular | paged_blocks | virtual_pages

    token_block_size or physical_page_bytes
    scheduler_block_size
    hash_block_size
    tensor-parallel world size and rank
    quantization schema or none
    position-contract identity
    allocator revision

The manifest is not a block table. It freezes how to interpret every later block-table or page-map entry. For example:

same block_id + different cache_group_id:
    different physical K/V object

same byte count + different TP rank:
    different locally owned K/V heads

same scalar bytes + different dtype or quantization schema:
    different numerical interpretation

same token block size + different axis/stride identity:
    different address calculation

Later allocator loops will attach mutable physical handles to this immutable layout generation. They may recycle block IDs, but they may not reinterpret a live block under a different manifest.

CacheCompatibilityManifest: The Semantic Reuse Gate

The compatibility record combines the M5.1 facts with M5.3’s physical and administrative facts:

CacheCompatibilityManifest
    cache_abi_sha256
    cache_layout_sha256
    model_generation
    adapter_identity
    weight_transform_identity
    position_contract_sha256
    exact token IDs for the covered interval
    input-side-data identity
    cache-isolation namespace and generation
    cache salt
    publication generation

    provenance, recorded but not necessarily equality-bearing:
        tokenizer revision
        chat-template revision
        request ID
        sampling and stopping policy

The last group matters for audit and replay, but not every provenance field changes already-computed K/V. If two text-only requests have the same exact token IDs under the same cache ABI, a tokenizer-version label alone does not change those model inputs. Likewise, request ID, temperature, and stop strings govern ownership or future token choice; putting them in semantic compatibility would prohibit safe cross-request reuse.

The exclusion rule must not be inverted. A multimodal feature, prompt embedding, adapter, transform, or position change can alter hidden states or projected K/V without changing placeholder token IDs. Those identities are equality-bearing.

Conceptually:

def semantic_cache_compatible(producer, consumer):
    require_equal(producer.cache_abi_sha256, consumer.cache_abi_sha256)
    require_equal(producer.cache_layout_sha256, consumer.cache_layout_sha256)
    require_equal(producer.model_generation, consumer.model_generation)
    require_equal(producer.adapter_identity, consumer.adapter_identity)
    require_equal(producer.weight_transform_identity,
                  consumer.weight_transform_identity)
    require_equal(producer.position_contract_sha256,
                  consumer.position_contract_sha256)
    require_equal(producer.covered_token_ids, consumer.covered_token_ids)
    require_equal(producer.input_side_data_identity,
                  consumer.input_side_data_identity)
    require_equal(producer.cache_isolation_namespace,
                  consumer.cache_isolation_namespace)
    require_equal(producer.cache_salt, consumer.cache_salt)
    require_equal(producer.publication_generation,
                  consumer.publication_generation)
    return compatible

This is the article’s normative compatibility contract. It is not a verbatim vLLM or SGLang function.

ConcretePrefixKey: A Runtime Projection, Not The Whole Truth

An index needs a compact key. At pinned vLLM v0.23.0, the source-observed full-block projection is approximately:

block_hash = Hash(
    parent_block_hash,
    full_block_token_ids,
    extra_keys_or_none,
)

lookup_key = block_hash || cache_group_id

The observed extra-key generators include:

LoRA name
multimodal feature identifier and its offset relative to the block
cache salt on the first block
SHA-256 of prompt embeddings covered by the block

The implementation computes hashes only for full blocks in this path. It can use a hash granularity distinct from a cache group’s physical block size, and adds the cache-group ID to the lookup key. These are source observations at the named revision, not a universal prefix-cache schema.

Important semantic fields are not all literal inputs to every per-block hash:

This creates a critical counterexample:

same parent hash + same block tokens + same concrete extras
    -> same concrete candidate key

different position contract or physical layout
    -> semantic compatibility rejects reuse

The hash table proposes a candidate. The compatibility and isolation records decide whether the candidate is legal to expose.

CacheIsolationNamespace: Reuse Is Also An Authorization Decision

Exact numerical compatibility does not grant cross-tenant authority. The namespace contract includes:

deployment or cluster cache namespace
tenant/isolation-domain identity
namespace generation
unguessable cache salt where supported
model/cache generation
publication policy

At the pinned vLLM revision, cache_salt is included in the first block’s extra keys; every descendant hash inherits that distinction through its parent hash. This is useful defense, but the deployment still owns authentication, salt issuance, namespace separation, and cache event exposure. A hash field is not a complete authorization system.

The legal order is:

1. enter the authorized cache namespace
2. validate logical ABI and physical layout generation
3. derive the concrete key and find a candidate
4. validate equality-bearing compatibility facts
5. lock/reference the physical object
6. return an immutable PrefixMatchReceipt

Lookup before authorization can leak whether another tenant used a prefix, even if bytes are never returned. Isolation therefore gates discovery, not only the final K/V read.

Source-To-Tensor Rejection Trace

Suppose producer and consumer have the same 16 token IDs. Four independent changes still make reuse illegal:

adapter mismatch:
    adapter changes hidden states or effective W_K/W_V
    -> K/V values differ

position-contract mismatch:
    the same hidden key row receives a different positional transform
    -> key semantics differ

TP-rank or cache-group mismatch:
    identical shape can name a different subset of K/V heads
    -> bytes have different ownership

storage-dtype or quantization-schema mismatch:
    identical raw bytes decode under a different numerical representation
    -> physical interpretation differs

Multimodal and prompt-embedding mismatches fail earlier in the input-to-hidden trace. Equal placeholder tokens do not imply equal side-input vectors.

Executable Compatibility And Negative Fixtures

The article-local Loop 2 oracle evaluates all candidates against one immutable producer manifest. Its expected distinctions are:

The checked artifact is generated by docs/numinens-evidence/m5-3-kv-layout-exact-reuse/cache_identity_oracle.py. It is a synthetic compatibility contract, not a replay of vLLM’s full cache manager and not a cache-hit-rate measurement. Its canonical-JSON SHA-256 is a teaching projection, not an exact runtime reproduction of vLLM’s serializer or in-memory key type.

Invalidation Produces A Successor Namespace

When model weights, adapters, transforms, position semantics, representation, or shard ownership change, the runtime must not relabel old blocks as new:

freeze old namespace for its still-live owners
stop publishing old entries to new lookups
advance model/cache/namespace generation
create a new layout and compatibility manifest
admit new requests only against the successor generation
reclaim old physical state after its legal references reach zero

Pinned vLLM exposes a prefix-cache reset path, including an RLHF-oriented weight-update use case. The article’s successor-namespace rule is broader and normative: reset, process replacement, separate pools, or generation-scoped directories are implementation choices as long as stale K/V cannot become a new-generation hit.

Loop 2 freezes identity and interpretation only. Loop 3 derives physical byte accounting; Loop 4 traces addresses; Loop 5 owns allocator mutation; Loop 6 deepens full/partial-block keys and the full-prompt-hit edge.

0x02 The Rectangular KV Mistake

M5.1 owns the logical K/V payload. M5.3 must turn that payload into a physical accounting convention before it can compare rectangular and paged allocators. Otherwise allocated_KV can silently mean useful rows, request capacity, unique blocks, or the entire provisioned pool.

0x02A Derive One Physical Row Before Counting Blocks

Let cache group $g$ contain $L_g$ cache-producing layers on this worker, $H_{kv,g}^{(rank)}$ locally owned K/V heads, head width $d_{h,g}$, and stored scalar widths $b_{K,g}$ and $b_{V,g}$ bytes. One token contributes

$$L_g H_{kv,g}^{(rank)}d_{h,g}$$

key scalars and the same number of value scalars. Therefore the local bytes for one token in group $g$ are

$$B_{row,g} = L_gH_{kv,g}^{(rank)}d_{h,g}(b_{K,g}+b_{V,g}),$$

and the worker-local row is

$$B_{row}^{(rank)}=\sum_g B_{row,g}.$$

The familiar factor $2$ appears only when K and V use the same scalar width:

$$B_{row}^{(rank)} = L\cdot2H_{kv}^{(rank)}d_hb.$$

Renderer-safe contract:

B_row,g [bytes / token / local rank]
    = L_g * H_kv,g_local * d_h,g * (b_K,g + b_V,g)

B_row,rank [bytes / token / local rank]
    = sum_g B_row,g

This article’s Loop 2 layout has 32 layers, 4 local K/V heads, width 128, and two bytes per FP16 K or V scalar:

B_row,rank
    = 32 * 4 * 128 * (2 + 2)
    = 65,536 bytes
    = 64 KiB per token on one TP rank

With two disjoint K/V-head shards, the corresponding model-wide conceptual row is 128 KiB. That multiplication is valid for this declared even head partition. It is not a license to multiply arbitrary pipeline replicas, offloaded copies, or heterogeneous cache groups by world size.

0x02B Rectangular Reservation Is A Reference Ledger

For live requests $r\in\mathcal{R}$, let $T_r$ be committed rows and $T_{max,r}$ be the contiguous capacity reserved for that request. Then

$$M_{logical,ref}=\sum_{r\in\mathcal{R}}T_rB_{row},$$ $$M_{rect,reserved}=\sum_{r\in\mathcal{R}}T_{max,r}B_{row},$$

and

$$M_{rect,slack}=M_{rect,reserved}-M_{logical,ref}.$$

The subscript ref matters: if three requests reference the same exact prefix, their logical payload counts that prefix three times. It describes the three request views, not necessarily three physical copies.

Rectangular reservation couples admission to unknown future output length. Choosing a large $T_{max,r}$ makes the request expensive before those rows exist; choosing a small value risks growth, relocation, or rejection. This reservation slack is an additive byte quantity. External fragmentation is not: it depends on where free extents lie and on the size of the next contiguous request.

0x02C Paged Request Capacity Is Not Pool Capacity

For a token block size $P$, request $r$ needs

$$N_r=\left\lceil\frac{T_r}{P}\right\rceil$$

block-table references. Counting every request independently gives

$$N_{ref}=\sum_r N_r, \qquad M_{paged,ref}=N_{ref}PB_{row}.$$

The request-view tail is

$$M_{tail,ref}=M_{paged,ref}-M_{logical,ref}.$$

This is useful for block-table and no-sharing baselines. It is not unique physical memory when block IDs are shared.

A preallocated block pool has another ledger. If $N_{pool}$ equal-sized blocks are physically provisioned, $N_{live}$ unique blocks are reachable, and $N_{free}=N_{pool}-N_{live}$ remain reusable, then

$$M_{pool}=N_{pool}PB_{row} =M_{live,unique}+M_{pool,idle}.$$

Idle pool bytes are not fragmentation by themselves. They are provisioned capacity available to future allocations. A deployment may reserve most free device memory for the K/V pool at startup even while only a subset of its blocks is owned by current requests.

0x02D Sharing Requires A Unique-Physical Ledger

Let $\mathcal{B}_r$ be the physical block IDs referenced by request $r$ and

$$\mathcal{U}=\bigcup_r\mathcal{B}_r.$$

Request references and unique physical objects are therefore

$$N_{ref}=\sum_r|\mathcal{B}_r|, \qquad N_{unique}=|\mathcal{U}|.$$

If unique physical block $p$ contains $v_p$ initialized token rows, then

$$M_{materialized,unique} = \sum_{p\in\mathcal{U}}v_pB_{row},$$ $$M_{capacity,unique} = N_{unique}PB_{row},$$

and

$$M_{tail,unique} = \sum_{p\in\mathcal{U}}(P-v_p)B_{row}.$$

Two different savings ledgers now become visible:

logical payload deduplicated
    = M_logical,ref - M_materialized,unique

request-reference capacity avoided by sharing
    = M_paged,ref - M_capacity,unique

They need not be equal. A shorter request can reference only nine visible rows of a block that a longer request has fully materialized. Its request view has seven unused slots, but those seven slots are not unique physical tail waste: they contain valid rows owned by the longer exact-prefix view.

0x02E Metadata Is Parameterized, Located, And Separate

K/V payload dominates many configurations, but a complete allocator ledger also names its indexing and ownership records. With record sizes $I_*$ in bytes per record:

$$\begin{aligned} M_{meta}={}& I_{map}N_{request\ block\ refs} +I_{desc}N_{pool\ blocks}\\ &+I_{hash}N_{cached\ hashes} +I_{tail}N_{live\ requests}\\ &+I_{free}N_{free\ queue} +M_{fixed}. \end{aligned}$$

M_meta [bytes]
    = I_map  [bytes / map entry]  * N_request_block_refs [entries]
    + I_desc [bytes / descriptor] * N_pool_blocks [descriptors]
    + I_hash [bytes / hash entry] * N_cached_hashes [entries]
    + I_tail [bytes / request]    * N_live_requests [requests]
    + I_free [bytes / queue item] * N_free_blocks [items]
    + M_fixed [bytes]

The formula is dimensional; the constants are not universal. A Python object, a packed C++ descriptor, a GPU integer block table, and a hash-map entry have different sizes and may live in different address spaces. The Loop 3 fixture’s 482 bytes is deliberately synthetic and placement-unspecified. It validates counting, not vLLM object size or measured GPU use.

0x02F Fragmentation Is A Taxonomy, Not One Subtraction

A synthetic contiguous arena makes the external case concrete:

arena             = 12 MiB
allocated extents =  9 MiB
free extents      = [1 MiB, 2 MiB]
candidate         =  2.5 MiB contiguous

total free        = 3 MiB
largest free      = 2 MiB
contiguous result = reject

The descriptive ratio

$$F_{ext}=1-\frac{M_{largest\ free\ extent}}{M_{total\ free}}$$

is 1/3 for that snapshot. It is not another 1 MiB to add to reservation slack. Under the synthetic 1 MiB block pool, the same candidate needs three blocks; five interchangeable free blocks can satisfy it without contiguity. The ratio is defined only when M_total_free > 0. A full arena has no free extent distribution to summarize, so the implementation reports the ratio as not_applicable rather than dividing by zero or silently assigning a perfect fragmentation score.

0x02G Expected Tail Waste Needs A Distribution

Let terminal occupancy $J$ be uniform on $\{1,\ldots,P\}$. Unused slots are $P-J$, so

$$\begin{aligned} \mathbb{E}[P-J] &=P-\frac{1}{P}\sum_{j=1}^{P}j\\ &=P-\frac{P+1}{2}\\ &=\frac{P-1}{2}. \end{aligned}$$

Thus

$$\mathbb{E}[M_{tail}] = \frac{P-1}{2}B_{row}.$$

For P=16 and B_row=64 KiB, that is 7.5 slots = 480 KiB per independent terminal block. The fixture observes 15 unique tail slots because its longest request ends one row into a block. An expectation under a uniform offset model is not a prediction for that trace. Real prompt/output length histograms, alignment rules, prefix sharing, and partial-block publication all change the distribution.

Reference views, unique physical objects, and the provisioned pool answer different capacity questions. None may silently replace another.

That distinction explains four failures of coarse contiguous allocation:

• internal reservation slack: a request reserves more rows than it uses;
• external fragmentation: free memory exists but not in a useful contiguous shape;
• over-reservation: uncertain future lengths consume admission capacity early;
• duplication: related sequences materialize identical prefix K/V separately.

The PagedAttention paper frames this as the serving bottleneck: KV cache is huge, dynamic, and waste-prone; inefficient management limits batch size. The paper reports that existing systems in its experiments used only a fraction of KV-cache memory for actual token states, with the rest lost to reserved, internal, or external waste.

Source: Efficient Memory Management for Large Language Model Serving with PagedAttention, Figure 2. In the paper’s experiment, the three Orca allocation variants devote only 20.4%-38.2% of KV memory to token states, while vLLM reports 96.3%. Those percentages are workload- and implementation-specific; the durable result is that allocation policy can dominate the gap between live payload and reserved memory.

The green region is the payload the model actually needs. Orange, red, and gray are different allocator losses. This is why the next mechanism figure is not merely an operating-system analogy: it addresses measured serving capacity that the tensor payload formula alone misses.

Source: Efficient Memory Management for Large Language Model Serving with PagedAttention, Figure 3. The slot counts are the paper’s illustrative requests; the reusable distinction is among reserved future capacity, unusable space inside allocations, and holes between allocations.

The figure’s categories form the paper’s measured or illustrated allocator breakdown. In a local analytical ledger, reservation slack and unique block tail have direct byte identities; external holes require an allocator snapshot and candidate extent. Treating all three as reserved - useful would double count different mechanisms.

0x03 PagedAttention: Logical Blocks, Physical Blocks

PagedAttention borrows the virtual-memory idea, but “physical block 7” is not yet an address. A complete read names a request snapshot, cache group, model layer, K or V tensor, local K/V head, token position, and head-dimension lane. The block table resolves only one step in that chain.

logical K/V coordinate:
    (request snapshot, token position, model layer, K/V, local head, lane)

physical read coordinate:
    (cache group, pool identity, pool generation, physical block,
     physical slot, layer-local index, token offset, K/V base, head, lane)

This distinction is not ornamental. Treating a block number as a byte address can select the wrong cache group, wrong pool generation, wrong layer stride, or wrong K/V base while remaining numerically in bounds.

0x03A Logical Order And Physical Identity

The first abstraction is still simple:

logical token order:
    block 0, block 1, block 2, ...

physical storage:
    block 17, block 04, block 22, ...

The request still has a normal ordered sequence. The allocator no longer has to find one large contiguous range. However, a reusable physical identity must be scoped more strongly than an integer:

$$\operatorname{PhysicalRef}_g = (g,\ \text{pool\_id}_g,\ \text{pool\_generation}_g,\ p_g)$$

PhysicalRef_g =
    (cache_group_id, pool_id, pool_generation, physical_block_id)

The group says which layers and representation the block belongs to. The pool and generation prevent a stale block ID from silently naming a recycled object. The physical block ID names ownership inside that namespace. A later descriptor resolves it to a current pool slot.

The paper’s worked translation shows the actual metadata boundary more precisely. Logical blocks preserve token order, each block-table entry names a physical block, and the # filled field records the valid tail length. The example also shows why a kernel cannot derive an address from token_pos alone: logical block 0 maps to physical block 7 while logical block 1 maps to physical block 1.

Source: Kwon et al., PagedAttention, Figure 6. The prompt, generated tokens, block size, and physical block IDs are illustrative. The durable contract is the logical-block, physical-block, and valid-tail translation that the attention kernel must follow.

The paper establishes logical-to-physical block translation. The following two-group byte-address trace is a synthetic Transformer System contract, not a claim about the paper’s tensor strides or one production backend.

0x03B Block Maps Are Cache-Group State

The Loop 4 fixture refines each all-layer block in Loop 3 into one physical block per cache group. It deliberately uses two non-identical groups:

Their storage still reconciles exactly to Loop 3:

$$B_{\text{row,rank}} =B_{\text{row},0}+B_{\text{row},1} =48\ \text{KiB}+16\ \text{KiB} =64\ \text{KiB/token/rank}$$ $$B_{\text{bundle,rank}} =P(B_{\text{row},0}+B_{\text{row},1}) =768\ \text{KiB}+256\ \text{KiB} =1\ \text{MiB}$$

row bytes on rank 0       = 48 KiB + 16 KiB = 64 KiB/token
16-token block bundle     = 768 KiB + 256 KiB = 1 MiB

The Loop 3 1 MiB physical block was therefore an accounting bundle across cache groups, not a promise that every layer occupies one contiguous extent. With g1’s layer-major layout, one allocator block slot is strided across layers.

For base request A, the group tables are:

Each request snapshot carries one table per cache group. In this fixture all groups use P=16, so the tables have the same number of logical rows. That is a fixture choice, not a universal K/V-cache law. A runtime supporting group-specific block sizes needs group-specific quotient/remainder arithmetic.

At pinned vLLM v0.23.0, the source keeps a list of block tables and computes slot mappings per K/V cache group. Its CPU and GPU implementations also carry group-specific block sizes, table pointers, and table strides. Those are pinned source observations. The exact tensor axis orders and base addresses in this section remain synthetic.

0x03C Token Position To Group Table Entry

Let model layer $\ell$ resolve to exactly one cache group $g$. Define its group-local layer index:

$$\ell_g=\ell-L_{g,\text{start}}$$

For group block size $P_g$, logical token position $t$ becomes:

$$j_g=\left\lfloor\frac{t}{P_g}\right\rfloor, \qquad o_g=t\bmod P_g$$

The request’s versioned group table resolves logical block $j_g$:

$$p_g=\mathcal{B}_{r,g}^{(v)}[j_g]$$

g       = unique cache group containing model_layer
layer_g = model_layer - group.layer_start
j_g     = token_position // group.block_size
o_g     = token_position % group.block_size
p_g     = request.block_tables[g][j_g] at table version v

The lookup is legal only after checking:

0 <= token_position < request.context_length
0 <= j_g < len(request.block_tables[g])
PhysicalRef_g exists in the named pool generation
o_g < descriptor.valid_rows

The first bound is request visibility. The final bound is physical materialization. They are separate contracts, especially under sharing.

0x03D A Slot ID Is Not A Byte Address

Many runtimes flatten a block slot and in-block offset into a token-slot ID:

$$s_{g,t}=\operatorname{slot}(p_g)P_g+o_g$$

slot_id = physical_slot * block_size + token_offset

Pinned vLLM v0.23.0 contains this shape in its block-table slot-mapping helpers, with additional context-parallel handling in the pinned source. The slot ID answers which token row in a group pool. It does not yet answer which layer, K or V tensor, local head, dimension lane, dtype, or byte base to read. Calling slot_id a GPU address erases the backend ABI.

0x03E Axis Order Produces Strides, Then Bytes

For one K or V tensor in group $g$, let the declared axis order have dimensions $D_{g,0},\ldots,D_{g,n-1}$. Under a row-major teaching layout, element strides are derived from the dimensions to the right:

$$S_{g,a}=\prod_{b=a+1}^{n-1}D_{g,b}$$

For coordinate vector $I_g$, the element and byte offsets are:

$$E_g=\sum_a I_{g,a}S_{g,a}, \qquad O_g=b_gE_g$$

Finally, with separate K and V bases:

$$A_{g,X}=\operatorname{base}_{g,X}+O_g, \qquad X\in\{K,V\}$$

stride[a]       = product(shape[b] for b > a)
element_offset  = sum(coordinate[a] * stride[a])
byte_offset     = scalar_bytes * element_offset
byte_address    = base_address[K_or_V] + byte_offset

An interleaved K/V layout would add a kv_kind axis instead. A packed or vectorized backend could use different strides. The formula stays valid only after the layout manifest supplies the actual dimensions and axis order.

0x03F One Complete Checked Address

Trace request A at token t=16, model layer 24, K head 1, dimension 5:

1. layer 24 selects g1, whose layer range is [24,32)
2. layer_local = 24 - 24 = 0
3. logical_block = 16 // 16 = 1
4. token_offset  = 16 % 16 = 0
5. A.g1.table[v=5][1] -> physical block 2001
6. descriptor(2001) -> pool generation 7, physical slot 6, valid_rows 16
7. slot_id = 6 * 16 + 0 = 96
8. g1 K shape = [8 layers, 8 slots, 16 tokens, 4 heads, 128 dims]
9. g1 strides = [65536, 8192, 512, 128, 1] elements
10. coordinate = [0, 6, 0, 1, 5]

Therefore:

$$E_1 =0(65536)+6(8192)+0(512)+1(128)+5 =49{,}285$$ $$O_1=2(49{,}285)=98{,}570\ \text{bytes}$$ $$A_{1,K}=4{,}311{,}744{,}512+98{,}570 =4{,}311{,}843{,}082$$

element_offset = 49,285
byte_offset    = 98,570
K base         = 4,311,744,512
byte address   = 4,311,843,082

The checked output also proves slot_id=96 and byte_address=4,311,843,082 are different quantities.

0x03G Request Visibility Dominates Shared Physical Capacity

Request B contains 25 visible tokens and shares bundle 101 with longer request A. In g1, token 24 resolves to logical block 1, offset 8, physical block 2001. That physical block has 16 committed rows because A materialized tokens 16 through 31. B may still read only offsets 0 through 8:

B context length                  = 25
B last-block visible rows         = 9
shared physical block valid rows  = 16

token 24 -> offset 8  -> legal for B
token 25 -> offset 9  -> reject: outside B's logical context

Checking only offset < physical.valid_rows would leak later rows from A into B’s attention history. The safe order is:

request visibility -> table bounds -> physical identity -> physical validity

The reverse failure also matters: if the request says a row is visible but the physical descriptor has not committed it, the read must fail rather than consume stale or uninitialized bytes.

0x03H Crossing A Block Boundary Consumes A Published Successor

Request C initially has 16 tokens and one block per group at table version 2. Appending token 16 crosses the P=16 boundary. Loop 4 does not allocate or publish blocks; Loop 5 owns that transaction. Instead, this trace consumes an already-published successor snapshot:

For the new token:

logical block = 16 // 16 = 1
token offset  = 16 % 16 = 0

g0: physical block 1003 -> slot 0 -> slot_id 0
g1: physical block 2003 -> slot 4 -> slot_id 64

The table version must change atomically with the published mapping and valid row state. How reservation, copy-on-write, commit, and rollback produce that successor belongs to Loop 5.

0x03I Reference Translator And Rejection Order

def resolve_kv_address(snapshot, request_id, token, layer, kind, head, lane):
    request = snapshot.requests[request_id]
    assert 0 <= token < request.context_length

    group = unique_group_containing(layer)
    layer_local = layer - group.layer_start
    logical_block = token // group.block_size
    token_offset = token % group.block_size

    table = request.block_tables_by_group[group.id]
    assert logical_block < len(table)
    physical_id = table[logical_block]

    desc = group.descriptor(
        pool_id=group.pool_id,
        pool_generation=group.pool_generation,
        physical_block_id=physical_id,
    )
    assert token_offset < desc.valid_rows
    assert 0 <= head < group.kv_heads_local
    assert 0 <= lane < group.head_dim

    slot_id = desc.physical_slot * group.block_size + token_offset
    coordinate = {
        "physical_slot": desc.physical_slot,
        "layer_local": layer_local,
        "kv_head_local": head,
        "token_offset": token_offset,
        "head_dim": lane,
    }
    element_offset = dot(
        reorder(coordinate, group.axis_order),
        row_major_strides(group.shape),
    )
    byte_address = group.base[kind] + group.scalar_bytes * element_offset
    assert group.base[kind] <= byte_address < group.end[kind]
    return slot_id, byte_address

This oracle rejects layer gaps, duplicate axes, table-length drift, unknown or stale physical identities, slot reuse, cross-group bundle mismatch, invalid tails, out-of-range coordinates, overlapping tensor ranges, stale successor versions, and frozen-address drift.

0x03J Layout Choices Change The Translator

M4.3 owns the generic online-softmax state and exact merge proof. M4.5 owns decode-kernel layouts, split planning, vectorization, and backend selection. M5.3 owns the storage map and the immutable metadata that lets a selected backend find exact K/V rows. Loop 4 therefore proves the address, not that any one axis order is fastest.

The durable invariants are:

Logical token order is contiguous.
Physical KV blocks need not be contiguous.
Block tables are cache-group and request-snapshot state.
Physical identities are scoped by pool and generation.
Request visibility is stricter than shared physical validity.
A slot ID is not a byte address.
Byte arithmetic is legal only under the declared axis/stride ABI.

The address trace consumes Loop 3’s accounting rather than redefining it:

one physical block [bytes / local rank]
    = P [tokens / block] * B_row [bytes / token / local rank]

live unique capacity
    = N_unique * P * B_row

provisioned pool capacity
    = N_pool * P * B_row

The maximum unique tail in one reachable partial block is (P - 1) * B_row. Summing that bound once per request is valid only for an unshared request-view baseline; shared mappings require the union of physical block IDs.

0x04 Allocator Lifecycle: Ownership Is A Transaction

Loop 4 consumed an immutable predecessor map and an immutable successor map. The allocator’s job is to create that successor without exposing any half-mutated state. That is a stronger requirement than “pop a block from a free list.”

For one logical mutation, the allocator may have to coordinate:

request generation and table version
cache-group-specific physical handles
physical generations and valid-row frontiers
strong references and temporary leases
weak cache-index identity
free / eviction queue membership
copy completion
successor publication
rollback or compensating repair

The scheduler in M5.2 supplies intent and budgets. M5.3 decides whether the physical transition commits and returns an immutable receipt. A scheduler decision is not ownership until this transaction succeeds.

0x04A Committed State And Transaction State Are Different Axes

The article uses these derived teaching states:

RESERVED, COPYING, and READY_TO_PUBLISH are transaction phases, not committed ownership states. An unpublished block must never be reachable from a request map.

This taxonomy is Rewrite interpretation. Pinned vLLM v0.23.0 exposes a narrower KVCacheBlock: block_id, ref_cnt, an optional full-block hash, free-queue links, and a null-block flag. Its free queue contains both unused blocks and zero-ref cached eviction candidates. It does not expose the generation and lease fields used by the stronger teaching protocol below.

0x04B Derive Refcounts From Reachability

Let $\mathcal{Q}$ be committed request maps and $\mathcal{L}$ active leases. For a generation-fenced handle $h=(pool,group,block,generation)$:

$$R(h) = \sum_{q\in\mathcal{Q}}\sum_j \mathbf{1}[q[j]=h] + \sum_{\ell\in\mathcal{L}} \mathbf{1}[\ell.handle=h].$$

Renderer-safe form:

refcount(handle)
    = committed request-map references
    + active read/write leases

The Loop 5 model treats a cache-index entry as a weak identity reference. It does not increase refcount. Therefore:

refcount == 0 and cache_key is None  -> FREE
refcount == 0 and cache_key exists   -> EVICTABLE

This matches the important shape of pinned vLLM’s behavior: free_blocks returns zero-ref blocks to the free queue without necessarily deleting their hash, while allocating such a block evicts the old cached identity before reuse.

The invariant is not “every cached block has a positive refcount.” It is:

$$R(h)=ReachableRequestRefs(h)+ActiveLeases(h),$$

and every committed request-reachable handle has $R(h)>0$.

0x04C The Operation Set

The state machine needs more than allocate and free:

The PagedAttention paper’s implementation discussion reduces decoding algorithms to fork, append, and free, then uses a fused block-copy kernel for COW copies. The table above is a systems expansion around that paper contract: it names cache publication, rollback, stale generations, and multi-group atomicity explicitly.

0x04D Transaction And Receipt

@dataclass(frozen=True)
class AllocationTxn:
    transaction_id: str
    expected_allocator_epoch: int
    request_id: str
    expected_request_generation: int
    expected_table_version: int
    operation: str
    touched_handles: tuple[PhysicalBlockHandle, ...]
    reserved_handles: tuple[PhysicalBlockHandle, ...]
    publication_state: str

@dataclass(frozen=True)
class AllocationReceipt:
    transaction_id: str
    predecessor_digest: str
    successor_digest: str
    useful_new_rows: int
    new_physical_blocks: int
    copied_rows: int
    copy_payload_bytes: int
    refcount_deltas: tuple
    allocator_epoch_after: int
    outcome: str

The receipt records physical fact, not policy intent. M5.2 may consume outcome, available capacity, and retry information; it still owns admission, preemption, fairness, and service order.

0x04E Append Has Three Physical Paths

For token position $t$, block size $P$, logical block $j=\lfloor t/P\rfloor$, and offset $o=t\bmod P$:

o == 0
    -> reserve a new bundle, write row 0, publish one new table entry per group

o > 0 and every tail handle has one strong owner
    -> acquire a unique writer, write row o, publish valid_rows=o+1

o > 0 and the tail bundle is shared
    -> copy-on-write the bundle, append row o, then publish replacement handles

For cache groups $g$, the new physical capacity at a boundary is:

$$B_{bundle}=\sum_g P_g B_{row,g}.$$

The Loop 5 fixture keeps $P_g=16$ and reuses Loop 3’s row split:

group 0 row = 48 KiB
group 1 row = 16 KiB
bundle row   = 64 KiB
bundle block = 16 * 64 KiB = 1 MiB

The groups have separate pools and handles. Publishing only group 0 is not a smaller success; it is an invalid half-bundle successor.

0x04F Rollback Has A Boundary

Let $S_0$ be the committed predecessor and $S_1$ the successor. Before publication, a failed transaction must satisfy:

$$Digest(S_{after\ rollback})=Digest(S_0).$$

Renderer-safe form:

before publication:
    rollback must restore the exact predecessor digest

after publication:
    do not erase history with rollback
    publish a compensating successor transaction instead

The checked trace injects failure after reserving the group-0 destination but before reserving group 1. It returns the reservation, publishes no request, does not increment allocator epoch 43, and reproduces the predecessor state hash exactly.

0x04G Source-Observed Runtime Versus Normative Protocol

Do not attribute the rightmost column to vLLM. It is the article’s explicit linearizability model.

0x04H Allocation Is Not Kernel Execution

The layout win is not free. Paged kernels consume the group tables and physical handles produced here; M4.5 owns generic read-side kernel tiling and reduction. PagedAttention trades address-translation and allocator complexity for dynamic allocation and sharing. vAttention makes a different choice: contiguous virtual tensors with physical pages committed on demand. Loop 8 owns that lifecycle comparison.

0x05 Refcounts, Copy-On-Write, And Linearizable Publication

Block tables make exact sharing possible. If two sequences share a prefix, their logical blocks may resolve to the same physical handles:

A: [17@4, 04@9, 22@3]
D: [17@4, 04@9, 22@3]

refcount[17@4] = 2
refcount[04@9] = 2
refcount[22@3] = 2

Reading shared immutable rows is safe. Appending into the shared final block is not. The PagedAttention paper’s parallel-sampling example copies only the affected tail block when one sample diverges; after that refcount drops, the remaining unique owner can keep the original block.

0x05A Derive Copy Cost And Amplification

Suppose the shared tail contains $r$ valid rows and one new row is appended. For group-local row bytes $B_{row,g}$:

$$B_{copy}=r\sum_g B_{row,g}.$$

Copying reads and writes those rows, then append writes one new row:

$$Traffic_{COW}=2B_{copy}+\sum_g B_{row,g}.$$

Relative to an ordinary one-row append:

$$A_{COW} = \frac{Traffic_{COW}}{\sum_g B_{row,g}} =2r+1.$$

Renderer-safe form:

copy_payload       = valid_tail_rows * bundle_row_bytes
COW traffic        = copy read + copy write + append write
COW amplification  = 2 * valid_tail_rows + 1

In the checked trace, r=2 and one bundle row is 64 KiB:

copy payload       = 2 * 64 KiB = 128 KiB
read + copy write  = 256 KiB
append write       = 64 KiB
total COW traffic  = 320 KiB
amplification      = 320 / 64 = 5x
new capacity       = 1 MiB across both cache groups

1 MiB is capacity reserved, not bytes copied. Conflating those quantities would overstate COW traffic.

0x05B One Complete Two-Group COW Trace

Request A first appends privately at token 33:

A predecessor: context=33, table_version=5
tail handles:  g0=1002@9, g1=2002@12
tail rows:     1
refs:          1 per group

write offset 1
publish: context=34, table_version=6, tail rows=2

A is then forked to D. Every mapped handle gains one strong request reference, so the tail bundle becomes shared. D’s append at token 34 cannot mutate it in place:

predecessor D tail:  g0=1002@9,  g1=2002@12, rows=2, refs=2
reserved successor: g0=1003@12, g1=2003@6
copy rows:           [0, 2)
append row:          offset 2
published D tail:    g0=1003@12, g1=2003@6, rows=3, refs=1
old tail refs:       2 -> 1
D successor:         context=35, table_version=2
allocator epoch:     43 -> 44

0x05C Publication Order Is The Correctness Proof

1. validate allocator epoch, request generation, and table version
2. load expected source handles including physical generations
3. reserve every cache-group destination as unpublished
4. retain source handles while copy is in flight
5. copy exactly the predecessor's valid rows
6. write the appended row into every group destination
7. validate destination data frontiers
8. atomically publish successor tables, logical length, and refcount deltas
9. release temporary source leases

Step 8 is the linearization point. A reader sees either the complete predecessor or the complete successor. It cannot see D mapped to group-0’s new block and group-1’s old block, and it cannot see valid_rows=3 before row 2 is valid.

0x05D Reference Transaction

def cow_append(req, expected_generation, expected_table_version, new_rows):
    predecessor = req.snapshot()
    require(predecessor.request_generation == expected_generation)
    require(predecessor.table_version == expected_table_version)

    source = predecessor.tail_bundle
    source_leases = allocator.retain_read_bundle(source)
    if source_leases is None:
        return STALE_BLOCK_GENERATION

    destinations = allocator.reserve_unpublished_bundle()
    if destinations is None:
        source_leases.release()
        return OUT_OF_MEMORY

    try:
        for group in req.cache_groups:
            copy_rows(
                src=source_leases[group],
                dst=destinations[group],
                rows=predecessor.valid_tail_rows,
            )
            write_row(destinations[group], predecessor.valid_tail_rows, new_rows[group])

        require(all_groups_data_valid(destinations))

        with req.mapping_transaction(expected=predecessor):
            successor = predecessor.replace_tail(
                destinations,
                valid_tail_rows=predecessor.valid_tail_rows + 1,
            )
            allocator.publish_bundle_and_ref_deltas(
                successor=successor,
                add_refs=destinations,
                drop_refs=source,
            )
    except BeforePublication:
        allocator.rollback_unpublished_bundle(destinations)
        return ROLLED_BACK
    finally:
        source_leases.release()

    return AllocationReceipt.from_successor(successor)

The with block is a specification boundary, not a claim about a particular language lock or database transaction in vLLM.

0x05E Truncate, Cancel, Release, Cache, And Evict Are Not Synonyms

truncate(D, 32)
    removes only D's suffix bundle
    decrements destination refs to zero
    returns 1003@12 and 2003@6 to their free queues

allocate(F, 16)
    reuses those block IDs
    increments generations to 1003@13 and 2003@7
    rejects the stale D writer holding @12 and @6

release(A)
    removes A's strong request references
    full cached blocks become EVICTABLE, not identity-free

touch(G, cached block 0)
    removes the zero-ref cached blocks from free queues
    increments refs and publishes G's map

evict(cached block 1)
    removes weak cached identity
    does not revoke a live request mapping

cancel and normal release share physical reference mechanics in the fixture, but their receipts differ because the service-level reason differs. truncate may remove only a suffix. Removing an interior logical block would break position continuity and is rejected.

0x05F Stale IDs Are An ABA Problem

The physical integer 1003 appears twice:

1003@12 -> D's COW destination -> truncated and freed
1003@13 -> F's new allocation

Comparing only block_id would let a delayed D operation mutate F’s lifetime. The normative handle therefore includes generation:

@dataclass(frozen=True)
class PhysicalBlockHandle:
    pool_id: str
    cache_group_id: int
    block_id: int
    generation: int

Pinned vLLM’s KVCacheBlock does not contain this generation field. The field is a recommended stale-handle defense in the teaching model, not a source-local description of vLLM v0.23.0.

0x05G Failure Lab

The oracle rejects 22 malformed transitions. The highest-risk failures are:

After every committed transition, the executable evidence recomputes refs from request-map reachability, checks every free queue, verifies cross-group valid rows, and hashes the complete committed state. Failed and rejected operations must preserve the predecessor hash.

0x06 vAttention: Virtual Reservation, Physical Commit, And Use

PagedAttention and vAttention begin from the same uncertainty: a request’s final context length is unknown, yet every decode step needs all committed K/V rows. They do not solve it at the same address boundary.

PagedAttention exposes non-contiguous logical blocks and a user-space block table to a paged attention kernel. vAttention reserves a large contiguous virtual K/V range, creates a pool of physical page handles separately, and maps those handles into only the request ranges needed at runtime. The GPU page table performs the final translation. That distinction is the thesis of the vAttention paper, not a claim that memory management disappears.

Source: vAttention Figure 1. The figure argues that PagedAttention adds a user-space translation layer before ordinary virtual-to-physical translation. The performance comparisons in that paper remain source-reported; this article uses the figure only to establish the address boundary.

The owner question for this section is stricter:

When is a virtual K/V address reserved, physically backed, safe for a kernel to use, semantically owned by one request generation, eligible for retained capacity reuse, unmapped, and finally released?

0x06A Reservation Is Not Commit, And Commit Is Not Valid K/V

Let one worker host:

L       transformer layers
B       maximum simultaneous request slots
T_max   maximum context rows per request
H_kv    local K/V heads after tensor-parallel sharding
d_h     elements per K/V head
b       bytes per element
G       physical page-group bytes

One token row in one K or V tensor at one layer occupies:

$$B_{\text{tensor,row}} = H_{kv}d_hb.$$

Renderer-safe form:

B_tensor,row = H_kv * d_h * b

If the implementation uses one K tensor and one V tensor per layer, one request page frontier advances across 2L tensors. Assuming G is divisible by the one-tensor row size, each mapped page holds:

$$P_{\text{tokens}} = \frac{G}{B_{\text{tensor,row}}}.$$

The virtual extent reserved for one request in one tensor must cover T_max rows and respect page granularity:

$$R = G\left\lceil\frac{T_{max}B_{\text{tensor,row}}}{G}\right\rceil.$$

Therefore the worker’s virtual reservation is:

$$M_{VA}=2LBR.$$

This number may be very large. Reserved address space is not resident HBM. It is address-space occupancy, not physical K/V residency. The paper’s Yi-34B example deliberately reserves terabytes of virtual address space while allocating physical K/V pages on demand.

The pinned vAttention prototype also creates physical handles ahead of time. If N_handle handles of G bytes exist, the physical pool is:

$$M_{\text{phys,pool}}=N_{handle}G.$$

Creating a physical handle is still not the same operation as mapping it into a request’s virtual range. For the per-layer K/V layout, one request-page bundle consumes:

$$B_{\text{page-bundle}}=2LG.$$

For request slot r with target length T_r, the minimum complete mapped frontier is:

$$N_{r,\text{pages}}=\left\lceil\frac{T_r}{P_{\text{tokens}}}\right\rceil.$$

Four ledgers are now visible:

M_VA           = reserved virtual address ranges
M_phys,pool    = created physical page handles
M_mapped       = handles currently mapped into request ranges
M_active,valid = K/V rows actually produced for active requests

Mapped backing must reconcile as:

$$M_{\text{mapped}} =M_{\text{active,valid}} +M_{\text{active,slack}} +M_{\text{inactive,retained}}.$$

The physical pool separately reconciles as:

$$M_{\text{phys,pool}}=M_{\text{mapped}}+M_{\text{free-handles}}.$$

No term in either equation is M_VA. Counting the reservation as resident HBM would recreate the exact accounting error that decoupled VMM is meant to avoid.

0x06B The Runtime Lifecycle Has Two State Machines

The paper’s API sequence is:

init
    reserve virtual tensors
    create physical pages, initially unmapped

alloc_reqid
    bind an inactive request slot to a new request

step(sequence_lengths)
    ensure every active request frontier is physically backed

model.forward
    read and append K/V through the virtual tensors

free_reqid
    mark the request slot inactive
    unmap now, or retain mappings for later reuse

shutdown
    unmap, release physical handles, free virtual ranges

That sequence contains two related but non-identical state machines:

virtual range:
    UNRESERVED -> VA_RESERVED -> VA_RELEASED

physical handle:
    CREATED_FREE -> MAPPED(slot, tensor, page) -> CREATED_FREE -> RELEASED

A request generation adds a third semantic axis:

slot 0 / generation 1 / owner A / valid rows 0..4
slot 0 / generation 2 / owner C / valid rows initially empty

The virtual address and even its physical backing may survive the handoff. The old request’s K/V validity does not.

Source: vAttention Figure 5, retained from A24. R3 receives a request slot with existing physical backing. The figure demonstrates mapping-capacity reuse; it does not establish that R1 and R3 have equal tokens, model state, positions, or K/V values.

The pinned prototype makes that distinction concrete. free_batch_idx marks a slot inactive by setting its tracked sequence length to zero; mapped pages may remain. alloc_new_batch_idx(seqlen) prefers a fitting inactive slot whose retained mapping already covers the new request. The new request must still write its own K/V rows.

0x06C Contiguous Address First, Hardware Translation Second

For a separate tensor X_ell, where X is K or V and ell is the local layer, let base(X,ell) be that tensor’s virtual base. A row-major scalar at request slot r, token t, head h, and lane d has virtual address:

$$A_{VA}=base(X,\ell)+rR+ \left(tH_{kv}d_h+hd_h+d\right)b.$$

Define the byte offset within the request subrange:

$$u=\left(tH_{kv}d_h+hd_h+d\right)b.$$

Then:

$$q=\left\lfloor\frac{u}{G}\right\rfloor, \qquad \delta=u\bmod G.$$

The runtime must have mapped virtual page q for every required K/V-layer tensor before use. Hardware translation then resolves:

(virtual tensor, request slot, page q)
    -> physical handle
    -> handle base + delta

Unlike Loop 4’s PagedAttention path, the attention kernel does not first query a request K/V block table. It still needs a request-slot mapping such as FlashAttention’s cache_batch_idx when continuous batching leaves holes in the larger virtual tensor.

The checked synthetic scalar is D@3 / V1 / (t=8,h=1,d=3):

B_tensor,row = 2 * 4 * 2 = 16 B
u = 8*16 + 1*4*2 + 3*2 = 142 B
q = floor(142 / 64) = 2
delta = 142 mod 64 = 14 B

base(V1) = 3 * (3 slots * 192 B) = 1728 B
A_VA = 1728 + 0*192 + 142 = 1870 B

page-table mapping:
    (slot 0, V1, q=2) -> H11
physical location:
    H11 + 14 B

The synthetic address proves the contract shape, not a production pointer. The 64 B page is intentionally synthetic. The paper describes standard CUDA VMM at 2 MiB granularity and a modified open-source NVIDIA UVM driver for 64 KiB, 128 KiB, and 256 KiB page groups. The tiny fixture is an executable algebra oracle, not a supported production configuration.

0x06D Map Before Use: Synchronous And Asynchronous Paths

The simplest safe path is synchronous:

def step_sync(active_requests):
    for req in active_requests:
        needed = ceil_div(req.target_tokens, tokens_per_page)
        while req.mapped_pages < needed:
            handles = reserve_complete_KV_layer_bundle()
            map_bundle_at_contiguous_frontier(req.slot, handles)

    receipt = publish_mapped_frontiers()
    assert receipt.ready_before_use
    return receipt

The paper observes that decode growth is predictable one iteration ahead: each decode request adds at most one token in an iteration. Its optimization maps a future page group in a background thread while the preceding iteration runs. That overlap changes timing, not the dependency:

receipt = step_async(next_sequence_lengths)

# Other work may overlap, but a kernel cannot cross the new frontier yet.
await receipt.mapping_complete
assert receipt.covers(request_generation, target_tokens)
model.forward(cache_batch_idx=receipt.request_slots)

The checked oracle uses a stronger normative publication rule: all K and V pages across the worker’s local layers for one request frontier become visible as one MappedFrontierReceipt. The pinned prototype performs concrete VMM map operations; it does not define this named atomic receipt class. The stronger contract is useful because a kernel observing K0:q without V1:q would see a shape-consistent pointer range whose physical backing is incomplete.

Prefill and decode also stress the mapper differently:

Mapping failure is a physical-feasibility result. M5.2 still owns which request to preempt, delay, or reject.

0x06E Delayed Reclamation Reuses Capacity, Not Prefix Identity

Deferred reclamation avoids immediate unmap/remap latency. Mapped backing is reusable capacity, not an exact-prefix hit:

A@1 maps slot 0 pages [0,1]
A completes
slot 0 becomes inactive, pages [0,1] remain mapped
C@2 receives slot 0 and needs only page [0]
no new mapping is required

Three facts must remain separate:

virtual address reused:       yes
physical mapping reused:      yes
old K/V values reusable:      no

On C@2 allocation, the oracle sets valid_tokens = 0, increments the slot generation, and records old_KV_semantically_valid = false. C’s prefill writes its own rows before any attention step may read them. Exact prefix reuse would require Loop 2’s compatibility manifest and Loop 6/7’s indexed identity and ownership receipts; vAttention slot reuse supplies none of those proofs.

Deferred pages also create a deliberate tradeoff. They can remove map calls from a later prefill, but consume mapped backing that another request may need. Under pressure, the runtime can unmap an inactive slot’s highest page, return its complete K/V-layer handle bundle to the pool, and map that bundle at an active request’s contiguous frontier.

0x06F One Checked VMM Lifecycle And Byte Reconciliation

The fixture uses:

L=2, B=3, T_max=12, H_kv=2, d_h=4, b=2 B, G=64 B

B_tensor,row = 2*4*2 = 16 B
P_tokens = 64/16 = 4 tokens/page
R = ceil(12*16/64)*64 = 192 B/request/tensor
M_VA = 2*2*3*192 = 2304 B

N_handle=12
M_phys,pool = 12*64 = 768 B
B_page-bundle = 2*2*64 = 256 B

Selected states reconcile exactly:

The 24-operation trace performs five page-bundle maps and five unmaps. Two new requests benefit from retained mappings. D’s asynchronous growth from eight to nine tokens finds no free handles, reclaims B’s inactive page bundle, maps it as D’s page q=2, awaits readiness, and only then commits token row 8.

The complete report and 20 negative cases live in docs/numinens-evidence/m5-3-kv-layout-exact-reuse/.

0x06G Design Choices: The Mechanism Is Not One Fixed Policy

Smaller pages reduce internal waste but increase mapping granularity and may require non-standard driver support. Larger pages reduce the number of page operations but can retain or strand more unused physical bytes. The paper’s timings and throughput results are useful source-reported evidence for its tested A100/H100 software stack; they are not a universal ranking against every modern PagedAttention runtime.

vAttention is also not “no memory manager.” The pinned implementation still tracks request slots, sequence lengths, mapped-page frontiers, physical handle pools, background work, reclamation, and cleanup. What changes is which translation is explicit in the attention-kernel interface.

0x06H Source-Observed Prototype Versus Normative Protocol

The prototype source also contains a megacache path and research-facing integration code. Those are valuable design alternatives, not permission to generalize the exact fixture tensor organization or publication semantics to every vAttention deployment.

0x06I Failure Lab

The executable oracle rejects all 20 malformed fixtures by named reason. It does not benchmark CUDA VMM, reproduce the prototype exactly, decide scheduler preemption, or claim that retained mappings imply exact prefix reuse.

0x07 Prefix Caching: Reuse Is A Contract

Prefix caching begins with a simple question and immediately splits into four:

have we already computed an exact semantic prefix?
which part of that prefix is present in this index snapshot?
which indexed rows may this runtime policy return?
which prompt rows still need execution and physical capacity?

The answers are not generally equal. vLLM’s automatic-prefix-caching design describes the operational objective as reusing K/V for a shared prompt prefix and skipping its repeated prefill. That can reduce repeated prefill work and TTFT. It does not remove decode work for later generated tokens, and a miss still follows the ordinary prefill path.

Loop 2 already froze authorization, semantic compatibility, physical layout, and the narrower concrete-key projection. Loop 6 consumes those records. It does not re-decide whether another model generation, adapter, position contract, cache representation, or isolation namespace is compatible.

0x07A Four Prefix Lengths, Not One Hit Count

Let:

S_prompt   = request prompt length
S_sem      = longest semantically exact token prefix
S_indexed  = longest contiguous compatible prefix present in the index
S_cap      = maximum prefix the execution path is allowed to reuse
S_runtime  = prefix rows actually returned by the runtime
S_recompute = S_prompt - S_runtime

The invariant chain is:

$$0 \le S_{runtime} \le \min(S_{sem}, S_{indexed}, S_{cap}) \le S_{prompt}.$$

Renderer-safe form:

0 <= S_runtime <= min(S_sem, S_indexed, S_cap) <= S_prompt
S_recompute = S_prompt - S_runtime

For a logits-producing generative request, the pinned vLLM path sets:

$$S_{cap}=S_{prompt}-1.$$

The reason is dataflow, not cache identity. K/V rows alone do not contain the final hidden state needed by the LM head. If every prompt row came only from cache, the path still needs a valid execution that produces next-token logits. This cap assumes S_prompt >= 1. Empty-input handling belongs to the request and model interface; it must not enter this subtraction as an unsigned or negative prefix length.

The pinned full-attention lookup also returns block-aligned hits. For block size $P$:

$$S_{runtime}^{full} =P\left\lfloor \frac{\min(S_{sem},S_{indexed},S_{prompt}-1)}{P} \right\rfloor.$$

Renderer-safe form:

S_runtime_full =
    P * floor(min(S_sem, S_indexed, S_prompt - 1) / P)

This equation follows in three steps:

1. semantic compatibility limits the maximum exact prefix;
2. the index can return only the contiguous entries it actually contains;
3. the logits cap removes at least the final prompt row, then the full-block policy rounds the remaining length down to a multiple of $P$.

Do not replace the last step with S_prompt - 1. That would silently claim partial-block reuse in a path whose source contract returns complete blocks.

0x07B Derive The Parent Hash Chain

Split the token sequence into cache-key blocks $X_0,X_1,\ldots$. Let $E_i$ contain only the runtime’s declared extra-key projection for block $i$. The incremental chain is:

$$h_0=H(\bot,X_0,E_0),$$ $$h_i=H(h_{i-1},X_i,E_i),\qquad i>0.$$

The pinned vLLM v0.23.0 source computes this shape from the parent block hash, the current full-block token tuple, and optional extra keys. Observed extras include LoRA name, multimodal identifiers with block-relative offsets, first-block cache_salt, and prompt-embedding hashes. Cache-group ID is then combined with the block hash for lookup.

That is a concrete runtime projection, not the whole CacheCompatibilityManifest. Model generation, complete cache ABI, tensor layout, and namespace generation may be enforced by process lifetime, namespace selection, reset, or validation outside the block digest. Do not attribute the article’s larger manifest tuple to the pinned hash serializer.

Why recurse through $h_{i-1}$? Suppose block $X_2$ contains the same local tokens in two requests but block $X_1$ differs. The K/V for $X_2$ depends on the earlier hidden-state path, so a local-block-only key is insufficient. Under the collision-resistance assumption:

X_j changes
    -> h_j changes
    -> h_(j+1) consumes a different parent
    -> every later descendant hash changes

The Loop 6 fixture changes token position 37, inside logical block 2. The semantic match ends at row 37, but the full-block runtime can return only the two complete ancestor blocks: 32 rows. Blocks after the first miss are not independent cache candidates.

def hash_full_blocks(request, P, hash_fn):
    parent = None
    hashes = []

    for start in range(0, len(request.tokens), P):
        stop = start + P
        if stop > len(request.tokens):
            break  # pinned path hashes full blocks only

        extras = runtime_extra_keys(request, start, stop)
        parent = hash_fn(parent, tuple(request.tokens[start:stop]), extras)
        hashes.append(parent)

    return hashes

0x07C Lookup Is A Contiguous, All-Group Trace

A valid lookup is not “find every digest that happens to exist.” It walks the ancestry in order and stops at the first missing or incompatible block. With multiple cache groups, the same logical prefix frontier must be physically available for every group required by the model.

def longest_full_block_hit(request, manifest, namespace, index, policy):
    authorize(namespace)                    # before cache-existence timing
    require_compatible(manifest)

    max_hit = len(request.tokens) - 1 if request.requires_logits else len(request.tokens)
    max_blocks = max_hit // policy.alignment_tokens
    matched = []

    for block_hash in hash_full_blocks(request, policy.block_size, policy.hash_fn):
        if len(matched) == max_blocks:
            break

        group_entries = index.lookup_all_groups(block_hash)
        if group_entries is None:
            break
        if not generations_are_current(group_entries):
            break

        matched.append(group_entries)

    return len(matched) * policy.block_size, matched

lookup_all_groups is important. A digest present for the upper-layer cache group but absent for the lower-layer group is not a partial success for an ordinary full-model forward pass. Hybrid cache managers can impose additional alignment and convergence rules; at the pinned revision, the coordinator monotonically reduces candidate length until the participating cache-group types agree on one common hit.

The output is an immutable match receipt, not a scheduling command. M5.2 may consume its work and capacity deltas; it still owns admission, service order, fairness, and SLO policy.

0x07D Full Blocks Versus Immutable Partial Tails

The article compares two valid design families. Only the first is attributed to the pinned vLLM path.

For an immutable partial tail with $v$ valid rows:

$$h_{tail}=H(h_{parent},X_{tail}[0:v],v,policy,E_{tail}).$$

Renderer-safe form:

h_tail = hash(parent_hash, tail_tokens[0:valid_rows], valid_rows,
              partial_policy_id, extra_keys)

Including valid_rows prevents a two-row frontier and a three-row frontier from sharing identity accidentally. Appending under the same key would make the key lie about the object. A partial-tail hit followed by a divergent write therefore emits copy_valid_partial_rows to Loop 5, which owns reservation, COW, publication, and rollback.

The fixture makes this difference concrete for a 50-token prompt and $P=16$:

The partial design reuses one more row, but it does not make mutation free. It trades an extra identity/frontier and COW handoff for the saved execution row.

0x07E The Complete-Prompt-Hit Edge

The most dangerous shorthand is:

all prompt tokens cached -> zero prompt work

For the pinned generative path, that is false. Consider exactly three cached blocks:

P                  = 16 tokens
S_prompt           = 48 tokens
S_sem              = 48 tokens
S_indexed          = 48 tokens
S_cap              = 47 tokens
S_runtime          = 16 * floor(47 / 16) = 32 tokens
S_recompute        = 48 - 32 = 16 tokens
new block bundles  = ceil(16 / 16) = 1

The source comment explicitly notes that obtaining logits can trigger recomputation of an entire block because num_computed_tokens must remain block aligned. “Recompute the last token” describes the semantic need; it does not imply that the current implementation always executes only one row.

For a 50-token prompt with three cached full blocks, the same policy yields:

S_cap              = 49
S_runtime          = 16 * floor(49 / 16) = 48
S_recompute        = 2
new block bundles  = ceil(2 / 16) = 1

The physical allocation is block granular even though only two rows are useful at this moment. With local row bytes $B_{row}=64$ KiB and block bundle bytes $P B_{row}=1$ MiB, the useful recompute payload is 128 KiB while the requested new capacity is one 1 MiB bundle. Those are separate ledgers.

The fixture also covers a one-block prompt. With $S_{prompt}=P=16$, the cap is 15 and full-block alignment reduces the reusable prefix to zero. The entire 16-row block is recomputed. This is an edge contract, not a claim that prefix caching is generally ineffective.

0x07F Collision Resistance Is Not Isolation

Three different controls are easy to collapse:

The vLLM v0.23.0 design documents SHA-256 as the default hashing family and offers a deterministic CBOR serialization option for cross-environment keys. That makes accidental digest collision extremely unlikely; it is still a cryptographic assumption, not a mathematical proof that two inputs cannot collide. The Loop 6 negative fixture forces an artificial equal digest over different token witnesses to exercise an optional secondary-witness policy. Do not claim that the pinned runtime performs that synthetic witness audit.

cache_salt is injected into the first block and inherited by descendants through the parent chain. It separates agreed trust groups and mitigates cache-timing disclosure across them. It is not encryption, and a salt by itself does not replace authorization. The safe order is:

authorize namespace
    -> validate namespace generation and semantic manifest
    -> derive/lookup concrete key
    -> validate entry generation and all-group handles
    -> publish PrefixMatchReceipt

Lookup before authorization can reveal cache existence through latency. A model update, adapter replacement, or isolation reset must produce a successor namespace/generation or reset the index; retaining old entries under a new semantic world is not exact reuse.

0x07G PrefixMatchReceipt And Failure Closure

The receipt freezes what was proved and what remains to execute:

@dataclass(frozen=True)
class PrefixMatchReceipt:
    request_id: str
    request_generation: int
    index_snapshot_id: str
    index_publication_generation: int
    compatibility_manifest_sha256: str
    namespace_id: str
    namespace_generation: int
    policy_id: str
    semantic_match_tokens: int
    runtime_hit_tokens: int
    prompt_rows_recomputed: int
    matched_group_handles: tuple
    new_block_bundles: int
    copy_valid_partial_rows: int
    logits_path: str
    receipt_sha256: str

The allocation derivation, assuming no already-owned writable tail slots, is:

$$N_{new}=\left\lceil\frac{S_{recompute}}{P}\right\rceil, \qquad M_{new,capacity}=N_{new}PB_{row}.$$

Renderer-safe form:

N_new = ceil(S_recompute / P)
M_new_capacity = N_new * P * B_row

If a request already owns writable tail capacity, the allocator may need fewer new blocks. If the hit ends inside an immutable shared tail, the receipt emits a copy-row intent instead. Loop 5 resolves both cases transactionally; Loop 6 does not mutate a block table while looking up identity.

The executable failure lab rejects:

The checked artifact evaluates eight positive traces and 22 malformed cases. It is a deterministic contract oracle, not a hit-rate, latency, or allocator- contention benchmark.

0x08 RadixAttention: Prefix Tree As A Cache Index

A hash table answers a fixed-block identity question. A radix tree answers a different question:

Across all exact token sequences retained by this runtime, what is the longest reusable prefix of this request, which physical K/V slots realize it, and how can that mapping survive concurrent insertions and reclamation?

A25 introduced RadixAttention as the point where prefix reuse stops being a lookup trick and becomes persistent runtime state. SGLang retains both prompt and generated K/V, maps variable-length token segments to K/V slot tensors, splits segments when a new common boundary appears, protects paths used by running requests, and reclaims cached leaves under memory pressure. The paper uses one-token pages. The Loop 7 teaching trace also uses page_size = 1 so the split algebra is visible; larger page policies must align every exposed boundary to their declared granularity.

The SGLang paper follows that data structure through nine mutations rather than showing only one steady-state tree. New requests split edges at newly exposed common prefixes, accessed nodes remain cache hits, new suffixes are inserted, and least-recently-used leaves are evicted when capacity is needed. This is the missing operational point: the prefix index is persistent scheduler state, not a static diagram built once from a batch.

Source: Zheng et al., SGLang, Figure 3. Green nodes are newly added, blue nodes are cached nodes accessed at that time point, and orange dashed nodes are evicted. The scenarios cover two chats, few-shot queries, and self-consistency sampling; they illustrate the runtime operations, not a universal eviction policy for every prefix-cache workload.

0x08A A Compressed Edge Owns Equal Token And Slot Segments

For a non-root node $v$, define the incoming compressed edge as:

$$E_v=(X_v,S_v),\qquad X_v=(x_0,\ldots,x_{m-1}),\quad S_v=(s_0,\ldots,s_{m-1}).$$

Exact ownership requires:

$$|X_v|=|S_v|=m,$$

where X_v[i] is the token at this path position and S_v[i] is the physical token-slot index containing that token’s K/V rows. In the pinned SGLang TreeNode, these objects are key and value. They are not interchangeable: the token segment establishes prefix identity, while the value tensor locates K/V storage.

Renderer-safe form:

edge(v) = (token_ids[v], kv_slot_ids[v])
len(token_ids[v]) == len(kv_slot_ids[v])

The complete key and slot path to terminal node $u$ are concatenations over its non-root ancestors:

$$X(u)=\mathop{\Vert}_{v\in path(root,u)}X_v, \qquad S(u)=\mathop{\Vert}_{v\in path(root,u)}S_v.$$

The tree is therefore also a physical ownership ledger. For pool slot set $\Omega$, tree-owned slots $\mathcal T$, request-private unpublished slots $\mathcal R$, and free slots $\mathcal F$:

$$\mathcal T\cap\mathcal R=\mathcal T\cap\mathcal F= \mathcal R\cap\mathcal F=\varnothing, \qquad \mathcal T\cup\mathcal R\cup\mathcal F=\Omega.$$

Loop 7’s committed snapshots contain no request-private suffix after each transaction, so the checked identity simplifies to:

tree_owned_tokens + free_slots = pool_slots

A request’s prefix_indices are references to tree-owned slots. They are not a second owner and must not be added again. Lock references protect the path; they do not clone its K/V tensors.

0x08B Compressed-Edge Match May Be A Mutation

At node $v$, let the unconsumed request suffix be $Q$. The edge comparison is:

$$\operatorname{lcp}(X_v,Q) =\max\{j:X_v[0:j]=Q[0:j]\}.$$

There are three cases:

This last case is why prefix lookup is not necessarily read-only. The pinned SGLang match_prefix documentation and _match_prefix_helper explicitly allow one split when the match ends inside a stored segment.

def match_compressed(root, query):
    node = root
    matched_slots = []
    offset = 0

    while offset < len(query):
        child = node.children.get(query[offset])
        if child is None:
            break

        m = lcp(child.token_ids, query[offset:])
        assert m > 0                         # child selector invariant

        if m < len(child.token_ids):
            shared = split_edge(child, m)    # structural mutation
            matched_slots.extend(shared.kv_slot_ids)
            node = shared
            offset += m
            break

        matched_slots.extend(child.kv_slot_ids)
        node = child
        offset += m

    return node, tuple(matched_slots), offset

In operation r02, the tree initially owns one edge:

tokens = [10, 11, 12, 13, 20, 21]
slots  = [ 1,  2,  3,  4,  5,  6]

The query [10, 11, 12, 99] has lcp = 3. The split is not a copy of K/V payload; it is a partition of the same ordered ownership:

$$X_{shared}=X[0:m],\quad S_{shared}=S[0:m],$$ $$X_{old}=X[m:],\quad S_{old}=S[m:].$$

For m = 3:

shared edge: tokens [10, 11, 12] -> slots [1, 2, 3]
old suffix:  tokens [13, 20, 21] -> slots [4, 5, 6]

concatenate before = concatenate after
no slot allocated, copied, freed, or duplicated

The split must also reparent the old child, replace the parent’s selector, and preserve any active lock count on both the newly exposed prefix and the old suffix. Splitting only the token key would make the tree look correct while returning the wrong physical rows.

0x08C Insert, Duplicate Release, And Request Publication

Insertion traverses exactly like lookup. If the request diverges after $p$ cached tokens, only its suffix becomes a new edge. When a completed producer arrives with freshly allocated input slots $S_{in}$, the first $p$ values are duplicates of slots already owned by the tree:

$$S_{duplicate}=S_{in}[0:p],\qquad S_{new}=S_{in}[p:].$$

The tree retains S_new; the allocator releases S_duplicate. Operation r05 inserts the second chat branch:

incoming tokens = [10, 11, 12, 13, 30, 31]
incoming slots  = [ 7,  8,  9, 10, 11, 12]
cached prefix   = 4 tokens

release duplicate input slots = [7, 8, 9, 10]
publish new branch             = [30, 31] -> [11, 12]

The existing [13, 20, 21] -> [4, 5, 6] edge is split again at one token:

[13]     -> [4]       shared by both chats
[20,21]  -> [5,6]     old chat branch
[30,31]  -> [11,12]   new chat branch

This is not reference-count-free deduplication. The prefix index takes responsibility for the retained slots, duplicate request-local slots return to the pool, and every transition must leave exactly one owner.

Finished and unfinished requests have different publication paths in the pinned source:

Operation r07 exercises the second path. req-chat-a already references six tree slots, computes tokens [22, 23] into slots [13, 14], inserts one new edge, then moves its lock from node 1 to node 5. The update is represented as one stronger teaching transaction:

def publish_unfinished(req, append_tokens, append_slots):
    predecessor = validate_tree_and_request(req)
    reserve(append_slots)

    full_tokens = path_tokens(req.last_node) + append_tokens
    full_slots = path_slots(req.last_node) + append_slots
    prefix_len = insert(full_tokens, full_slots)
    free(full_slots[req.cache_protected_len:prefix_len])

    new_last, new_prefix_slots, matched = match_compressed(root, full_tokens)
    assert matched == len(full_tokens)

    dec_lock_ref(req.last_node)
    inc_lock_ref(new_last)
    publish_request_prefix(req, new_last, new_prefix_slots)
    return RadixMutationReceipt(predecessor, committed_tree_version())

The ordering above is a normative Transformer System contract. The pinned source exposes the individual insert, free, rematch, request-table write, and lock-move steps; it must not be cited as publishing the article’s one atomic versioned receipt.

0x08D Lock References Protect Paths, Not Just Leaves

Continuous batching cannot evict a prefix used by a running request. If active lease $r$ terminates at node $t_r$, the derived reference count for node $v$ is:

$$lock(v)=\sum_{r\in\mathcal A} \mathbf 1\left[v\in path(root,t_r)\right].$$

The pinned inc_lock_ref and dec_lock_ref walk from the terminal node to the root. If two running requests share a system-prompt edge, that ancestor has two references even when their leaves differ. A split under an active request must copy the old child’s lock count onto the newly exposed parent because the shared prefix has become part of every formerly protected path.

Define source-shaped token ledgers:

$$T_{protected}=\sum_{v\ne root}|X_v|\mathbf 1[lock(v)>0],$$ $$T_{evictable}=\sum_{v\ne root}|X_v|\mathbf 1[lock(v)=0].$$

Only a subset of the second quantity is reclaimable immediately:

$$T_{leaf-ready}=\sum_{v\ne root}|X_v| \mathbf 1[lock(v)=0\land children(v)=\varnothing].$$

An unlocked internal node still owns evictable cache state, but it cannot be deleted before its descendants without disconnecting their keys. This is why evictable_size and the current leaf-victim set answer different questions.

0x08E Leaf-Safe Eviction Is Recursive And Whole-Edge

The SGLang paper uses least-recently-used leaf eviction. The pinned v0.5.11 runtime also exposes LFU, FIFO, MRU, FILO, priority, and segmented-LRU strategies. The radix invariant is unlocked leaf first; victim ranking is a policy choice.

def evict_tokens(target):
    heap = rank(unlocked_leaf_nodes())
    released = 0

    while released < target and heap:
        leaf = heap.pop()
        assert leaf.lock_ref == 0
        assert not leaf.children

        free_kv_slots(leaf.kv_slot_ids)
        parent = delete_leaf_edge(leaf)
        released += len(leaf.kv_slot_ids)

        if parent is not root and not parent.children and parent.lock_ref == 0:
            heap.push(parent)       # newly exposed leaf

    return released

Eviction is whole-edge. A target of one token can release more than one if the selected compressed edge contains several tokens. Operation r14 asks for three rows and releases exactly three in two steps:

evict leaf [60]    -> free slot [20]
parent [50, 51] is now an unlocked leaf
evict that parent  -> free slots [15, 16]

Locked chat paths survive both eviction calls. After their leases are released, r17 removes [22, 23] first, exposes [20, 21] as a leaf, then removes that parent. This is the allocator consequence of the paper’s visual sequence: an ancestor becomes reclaimable only after its last child disappears.

The paper’s scheduling theorem must remain scoped. For an offline fixed batch, a radix tree built from that request set, and cache capacity at least the maximum request length, DFS visits each edge once and reaches the lower bound:

$$C_{KV}=\sum_{e\in edges(T)}|e|.$$

Longest-shared-prefix-first is equivalent to a DFS order under those assumptions. The paper explicitly separates online arrivals, unpredictable output lengths, and starvation. The theorem is not an optimality result for online SLOs, fairness, arbitrary capacity, or unknown decode growth; those decisions remain in M5.2.

0x08F One Checked Mutation And Ownership Trace

The executable fixture uses 24 physical token slots and 18 committed operations. The high-value transitions are:

The final reconciliation is:

pool slots            = 24
tree-owned slots      = 6
free slots            = 18
active private slots  = 0

6 + 18 = 24

protected tree tokens = 6
evictable tree tokens = 0

Across the full trace:

edge splits                    = 3
duplicate input slots released = 6
eviction calls                 = 3
evicted compressed edges       = 5
evicted token slots            = 8

Every operation hashes its predecessor and successor states. Every committed successor re-derives child selectors, token/slot equality, path locks, slot disjointness, and the complete pool partition.

0x08G Immutable Scheduler Handoff, Not A Schedule

The final match returns an immutable physical fact:

@dataclass(frozen=True)
class RadixSchedulerHandoffReceipt:
    request_id: str
    request_generation: int
    tree_version: int
    tree_state_sha256: str
    matched_tokens: int
    prefix_slot_ids: tuple[int, ...]
    path_node_ids: tuple[int, ...]
    terminal_node_id: int
    suffix_interval: tuple[int, int]
    lock_lease_id: str
    lock_required_until_scheduler_disposition: bool
    scheduler_owner: Literal["M5.2"]
    policy_decision: None
    receipt_sha256: str

For req-handoff:

request generation = 4
tree version       = 18
matched tokens     = 6
path nodes         = [2, 3, 4]
prefix slots       = [1, 2, 3, 4, 11, 12]
suffix interval    = [6, 7)
terminal node      = 4
lock lease         = lease-req-handoff-v18
policy_decision    = none

M5.2 may use this receipt with request deadlines, fairness state, prefill/decode budgets, output uncertainty, and overload policy. It may choose FCFS, LPM, DFS-weight, or another declared policy. M5.3 does not sort the waiting queue. If M5.2 admits the request, it retains or exchanges the lock under an explicit transaction. If it rejects or defers the request, it must release the lease. Using an unlocked receipt after tree mutation is a stale-read bug.

The current prefill and capacity estimates still remain separate:

prompt_tokens_to_compute = S_prompt - matched_tokens
new_useful_KV_bytes = prompt_tokens_to_compute * B_row

new_physical_blocks =
    ceil(max(prompt_tokens_to_compute - free_private_tail_slots, 0) / P)

new_physical_capacity_bytes = new_physical_blocks * P * B_row

The receipt freezes physical evidence; Loop 5 performs allocation/COW, and M5.2 decides whether and when to request it.

0x08H Source-Observed Runtime Versus Normative Protocol

Do not attribute RadixMutationReceipt, tree-version hashing, complete pool partition checks, or the synthetic 24-slot trace to SGLang. Conversely, do not reduce the pinned source to the teaching model: v0.5.11 includes page alignment, host/hierarchical state, EAGLE bigram keys, priorities, multiple eviction strategies, K/V events, and scheduler paths outside this loop.

0x08I Failure Lab

The negative fixture checks 18 malformed states, operations, and receipts. It includes locked-leaf eviction, internal-node eviction, lock underflow, owned slot reuse, stale version, path-slot mismatch, suffix mismatch, and receipt tampering. This is an exactness oracle, not a latency or cache-hit benchmark.

0x09 Block Size Is A Cost Vector

Paged allocation replaces uncertain whole-request reservation with a discrete granularity choice, but “block size” is overloaded. Loop 10 separates four objects before evaluating any sensitivity:

They may be equal in one implementation. Equality is not part of the semantic contract. A runtime may allocate 32-token blocks while exposing 16-token kernel blocks, or retain a contiguous virtual tensor whose physical page group contains hundreds of token rows without exposing that page group to the attention kernel at all.

0x09A The Cost Vector Cannot Be Collapsed Before Measurement

No one scalar objective is portable across runtimes:

C(P_a, P_k, G, P_c; workload, backend) = (
    unique tail bytes,
    request-map and block-descriptor metadata,
    full-block prefix-hit granularity,
    allocator transitions,
    copy-on-write capacity,
    kernel block-table traversal and packing,
    VMM page-group tail and mapping operations,
    shared-prefix chunk visits and partial states
)

The first two components are executable in Loop 3. Hash publication is deepened in Loop 6, copy-on-write in Loop 5, and kernel addressing in Loop 4. Keeping the vector open prevents this section from choosing a block size with a fabricated weighted score.

0x09B Derive Storage, Metadata, And Hit Granularity Separately

The checked fixture holds these facts constant:

request lengths        = [33, 25, 16]
relationship           = every shorter sequence is an exact prefix of A
local row bytes        = 64 KiB
provisioned pool       = 128 token slots
metadata record sizes = synthetic constants declared in the fixture

For request length $T_r$, allocator block size $P_a$, and row payload $B_{row}$:

$$N_{r,blocks}=\left\lceil\frac{T_r}{P_a}\right\rceil, \qquad W_{r,tail}=N_{r,blocks}P_a-T_r,$$ $$M_{r,tail}=W_{r,tail}B_{row}.$$

Request-view tail counts every map independently. Under the nested-prefix fixture, unique physical capacity instead follows only the longest materialized path:

$$N_{unique}=\left\lceil\frac{\max_r T_r}{P_a}\right\rceil, \qquad W_{unique}=N_{unique}P_a-\max_rT_r.$$

Renderer-safe fallback:

request_blocks(r) = ceil(T_r / P_a)
request_tail(r)   = request_blocks(r) * P_a - T_r
unique_blocks     = ceil(max_r T_r / P_a)
unique_tail       = unique_blocks * P_a - max_r T_r

The synthetic metadata ledger is not “metadata proportional to blocks” in the abstract. It names each declared record family:

$$M_{meta}= N_{refs}b_{map} +N_{pool}b_{desc} +N_{full}b_{hash} +N_{req}b_{tail} +N_{free}b_{queue} +M_{fixed}.$$

Changing only $P_a$ gives:

At P=4, unique tail is only 3 * 64 KiB = 192 KiB, but the fixed 128-slot pool needs 32 descriptors and the three request maps contain 20 entries. At P=32, metadata falls, while one unique partial block leaves 31 * 64 KiB = 1.9375 MiB uninitialized. Request-view tail is larger still because it counts the shorter prefix views independently.

The table’s sharing assumption describes storage identity, not a claim that a specific runtime will publish or match every partial prefix at every candidate block size. Full-block prefix-cache policy can reduce runtime-admissible hits even when an abstract exact-prefix storage layout is possible.

Smaller blocks generally improve tail granularity and copy-on-write bounds but increase maps, descriptors, hash entries, transitions, and kernel traversal. Larger blocks reverse those pressures. Dtype packing, cache-group alignment, hardware page behavior, and measured kernel performance still have to join the decision before a deployment chooses $P$.

Full-block-only prefix publication adds a different staircase. If A’s 33-token path exists before exact-prefix requests B and C of lengths 25 and 16, and neither needs next-token logits (so the 0x07A logits cap does not apply), the reusable lengths are

$$H_r^{full}=P_a\left\lfloor\frac{T_r}{P_a}\right\rfloor.$$

The table and the cost-vector figure at the end of 0x09C count these uncapped hits, which isolate block granularity. A logits-producing generative request takes the 0x07A cap first:

$$H_r^{full,gen}=P_a\left\lfloor\frac{T_r-1}{P_a}\right\rfloor.$$

For $P_a=4,8,16,32,64$ the full-block hit across B+C then becomes 36, 32, 16, 0 and 0 tokens, and the recomputed prompt tail 5, 9, 25, 41 and 41 tokens. The immutable-partial-tail alternative is capped too, as in 0x07D, and reuses 39 tokens (24 for B, 15 for C). At $P_a=16$, C is the one-block edge of 0x07E: its cap of 15 rows aligns down to zero, and its whole block is recomputed.

This does not prove partial-tail publication is preferable. It exchanges recomputation for a stronger immutable-frontier identity and, after a branch, copy-on-write work.

0x09C Copy-On-Write Has Useful-Byte And Capacity Amplification

Let two requests share 20 tokens and diverge at the next append. The valid shared-tail rows are

$$r=20\bmod P_a.$$

When $r=0$, the prefix ends at a block boundary and the divergent request can allocate a fresh block without copying a tail. Otherwise one exact COW path copies $r$ useful rows but reserves one private block of $P_a$ rows:

$$M_{copy,R+W}=2rB_{row}, \qquad M_{dst}=P_aB_{row}, \qquad A_{capacity}=\frac{P_a}{r}.$$

Copy traffic counts source read plus destination write; destination capacity counts the newly owned block. They answer different questions. The exact values depend on where a branch falls, so an average COW cost requires the workload’s branch-offset distribution, not just its mean prompt length.

0x0A What A Paged Decode Kernel Actually Loops Over

The exact translator in 0x03 resolves one scalar. A decode kernel hoists the same metadata and traverses bounded block segments rather than repeating every check for every lane:

For context length $T$ and kernel block size $P_k$:

$$N_{seq-blocks}=\left\lceil\frac{T}{P_k}\right\rceil.$$

If a long row is split into reduction partitions of $P_{part}$ tokens and $P_k$ divides $P_{part}$:

$$N_{parts}=\left\lceil\frac{T}{P_{part}}\right\rceil, \qquad N_{blocks/part}=\frac{P_{part}}{P_k}.$$

The first quantity counts kernel-visible block-table traversal. The second controls independent partial states and a later reduction. Allocator blocks, kernel blocks, and reduction partitions are therefore three separate levels.

def paged_decode_one_row(q, snapshot, request_id, layer, kv_head):
    request = snapshot.requests[request_id]
    group = unique_group_containing(layer)
    block_size = group.block_size
    table = request.block_tables_by_group[group.id]
    state = empty_online_softmax_state()
    num_blocks = ceil_div(request.context_length, block_size)

    for logical_block in range(num_blocks):
        physical_id = table[logical_block]
        desc = group.descriptor(group.pool_generation, physical_id)

        valid_rows = block_size
        if logical_block == num_blocks - 1:
            valid_rows = request.context_length % block_size or block_size
        assert valid_rows <= desc.valid_rows

        K = load_group_tile(group, "K", layer, kv_head, desc, valid_rows)
        V = load_group_tile(group, "V", layer, kv_head, desc, valid_rows)
        scores = q @ K.T * scale
        state = online_attention_update(state, scores, V)

    return finalize(state)

0x0AA Pinned vLLM Source Trace: BLOCK_SIZE Changes The Kernel

At pinned revision 0fc695fc..., the libtorch-stable paged-attention source does not treat BLOCK_SIZE as an inert runtime label. It is a compile-time template parameter that participates in:

num_seq_blocks          = ceil(seq_len / BLOCK_SIZE)
num_blocks_per_partition = PARTITION_SIZE / BLOCK_SIZE
thread_group_size       = max(warp_size / BLOCK_SIZE, 1)
tokens_per_thread_group = ceil(BLOCK_SIZE / warp_size)
value vector width      = min(16 / sizeof(scalar), BLOCK_SIZE)

The kernel first chooses the request row of block_tables, reads physical_block_number = block_table[block_idx], and then combines that number with kv_block_stride, kv_head_stride, and the in-block offset. That is the code-level form of the 0x03 address derivation.

For the checked $T=2049$, $P_{part}=512$, warp size 32, FP16 scalar fixture:

All five rows have five long-context partitions. They do not have the same block-table traffic or thread geometry. The pinned V1 launcher instantiates only 8, 16, and 32; its source says other listed sizes were omitted to reduce compilation time. That is a source-revision observation, not a claim that every vLLM backend supports exactly those sizes.

Source: Prabhu et al., vAttention, Figure 3. The figure establishes that block-size performance can be non-monotonic and backend-specific; it does not establish a universal best block size.

0x0AB Ragged Requests Create A Second Traversal Ledger

For request block counts $n_r=\lceil T_r/P_k\rceil$, a dense rectangular staging table with $B$ rows and $n_{max}=\max_r n_r$ columns contains

$$N_{table}=Bn_{max}, \qquad N_{used}=\sum_r n_r, \qquad N_{pad}=Bn_{max}-\sum_rn_r.$$

Using lengths [64,63,17,1]:

The byte totals are tiny because the fixture has four requests. The scaling law is the point: a few long rows can set n_max for every short row. Compact or ragged table encodings can reduce padding but introduce offsets, lengths, packing work, or more irregular lookup. This article records the address and byte contract; M5.2 owns which requests become co-resident.

0x0AC Allocator Blocks May Be Split For A Kernel

The pinned vllm/v1/worker/block_table.py receives allocator block_size and kernel_block_size separately. Its supported hybrid direction is

$$P_a=qP_k, \qquad q\in\mathbb{N}^{+}.$$

Allocator block ID $a$ expands to

$$\{aq, aq+1,\ldots,aq+q-1\}.$$

For P_a=32, P_k=16, allocator IDs [3,7] become kernel IDs [6,7,14,15]. The physical payload did not duplicate, but the kernel-visible table gained twice as many entries. For P_a=64, P_k=16, one allocator ID expands to four kernel IDs.

The reverse direction is not a free mapping. A kernel block larger than an allocator block would require a guarantee that several separately allocated objects form the exact contiguous layout expected by that kernel, or a gather path with a different ABI. The pinned helper therefore rejects a kernel size that does not divide the allocator size.

Production kernels vectorize across requests, heads, blocks, and dimensions. They may split one long context across workers and reduce partial states as M4.5 derives. The implementation path remains:

request snapshot
    -> cache-group table and pool generation
    -> physical descriptor and bounded tile
    -> online softmax state

At minimum, a batched paged kernel needs:

request generation and block-table version
context length and number of logical blocks per group
group table, pool identity/generation, and physical descriptors
request-visible tail and physical valid length
K/V head mapping
layer-local index, K/V bases, axis order, shapes, and strides
position or mask limits

Variable-length batching therefore has two kinds of raggedness:

ragged token lengths
ragged physical block lists

The kernel must not read padding slots in a partially filled block as valid history. Those slots may contain stale data from a recycled physical block.

Append And Copy-On-Write Edge Case

Suppose requests A and B share a 20-token prefix with block size 16:

shared full block:
    positions 0..15

shared partial block:
    positions 16..19
    free slots 20..31

If A and B generate different token 20 values, both cannot append into the same partial block. Copy-on-write must occur before the first divergent append, even though the block is not full.

def append_token(req, k_row, v_row):
    tail = req.block_table[-1]

    if tail.has_free_slot() and refcount[tail] == 1:
        return write_next_slot(tail, k_row, v_row)

    if tail.has_free_slot() and refcount[tail] > 1:
        private_tail = copy_valid_prefix_of_block(tail)
        replace_tail_mapping(req, private_tail)
        return write_next_slot(private_tail, k_row, v_row)

    new_block = allocate_block()
    req.block_table.append(new_block)
    return write_next_slot(new_block, k_row, v_row)

Copying one valid tail block preserves exactness. Copying the entire request cache would preserve exactness too, but would erase much of the sharing benefit.

0x0B Exact Prefix Reuse Has Multiple Execution Designs

Prefix caching is often taught as one mechanism:

find token-prefix hit -> reuse K/V -> prefill suffix

A25 distinguishes several systems because they optimize different repeated work. The distinction matters most after prefill. Two requests can reference the same exact K/V rows and still make an ordinary decode kernel read those rows once per request:

storage reuse:
    one physical shared-prefix K/V object

ordinary decode execution:
    request 0 reads the object
    request 1 reads the object again
    request 2 reads the object again

Loop 6 proved whether the rows are semantically reusable. Loop 7 proved how a prefix tree indexes and protects them. Loop 9 begins only after those receipts exist. Its owner question is narrower:

Given an immutable batch snapshot whose sequence paths reference exact shared K/V chunks, how can a kernel partition shared-prefix and unique-suffix attention, execute each partition in a useful shape, and merge the partial states into exactly the same attention row?

This is execution reuse. It is neither a new cache-identity rule nor a scheduling policy.

0x0BA One Score Row, Disjoint Key Partitions, One Denominator

For one query row $q_r$, let sequence $r$‘s legal keys be partitioned into disjoint sets:

$$\mathcal{K}_r = \mathcal{K}_{0} \;\dot\cup\; \mathcal{K}_{1,r} \;\dot\cup\;\cdots\dot\cup\; \mathcal{K}_{J,r}.$$

$\mathcal{K}_0$ may be a global system-prompt prefix. A second partition may be shared only by one subtree, and the final partition may be private to the request. The score for key row $i$ is

$$s_{r,i} = \frac{q_r k_i^\top}{\sqrt{d_h}}.$$

The full row is not the average of the local outputs. Each independently computed partition must preserve its softmax mass alongside its output information. The general common-denominator proof and stable LSE merge are owned by M4.3, section 0x09E. M5.3 consumes that merge; its additional contract is that each sequence’s chunk path covers the legal keys exactly once, using the same query row, score convention, mask, and immutable execution snapshot.

The partition API carries the canonical state, including its valid-key count:

$$S_p = (valid_p,m_p,\ell_p,u_p,c_p),$$

For a valid partition, the adapter to Hydragen’s LSE/output coordinates is:

$$\operatorname{LSE}_p=m_p+\log\ell_p, \qquad O_p=\frac{u_p}{\ell_p}.$$

The consumer keeps the coordinate conversion explicit without rederiving the upstream merge:

LSE_p = m_p + log(l_p)
O_p   = u_p / l_p

# Merge valid partial states with the M4.3 LSE/output operator.
# Never average independently normalized prefix and suffix outputs.

The empty partition is a two-sided identity, not a valid row with $m=-\infty$. Branch on valid before any expression resembling $\exp(-\infty-(-\infty))$.

0x0BB The Execution Snapshot Is A Tensor Contract

The partition identity is valid only for one immutable execution snapshot:

tree version and tree-state digest
sequence order
query row for each sequence
ordered chunk path for each sequence
chunk identity digest and coverage interval
K/V shape, head mapping, dtype, scale, and position contract
shared/private execution threshold

The Loop 9 fixture uses one decode query per sequence:

Q: [B=4, H_q=1, T_q=1, d_qk=2]
each K_chunk: [T_chunk, H_kv=1, d_qk=2]
each V_chunk: [T_chunk, H_kv=1, d_v=3]
scale denominator: sqrt(2)
numeric oracle: binary64

Production kernels may use GQA head expansion, FP16/BF16 inputs, FP32 state, quantized K/V, or different axis orders. Those are cache-ABI fields, not details to infer from a tensor’s rank. The checked fixture deliberately keeps one head and tiny widths so every path and state is inspectable.

Its tree is:

C0_global, 2 K/V rows, covers sequence indices [0,4)
├── C1_left_shared, 1 row, covers [0,2)
│   ├── C3_private_S0, 2 rows, covers [0,1)
│   └── C4_private_S1, 1 row, covers [1,2)
└── C2_right_shared, 2 rows, covers [2,4)
    ├── C5_private_S2, 1 row, covers [2,3)
    └── C6_private_S3, 1 row, covers [3,4)

The half-open intervals are not decorative. They let a chunk-first kernel map one chunk to a contiguous query-row range. Reordering active sequences without rebuilding those intervals would make the metadata stale even if the K/V bytes were unchanged.

Cache Lookup Reuse

Paged prefix caching and RadixAttention primarily answer:

Which exact prefix K/V blocks already exist?
Which requests or tree edges reference them?
When should they be retained or evicted?

They reduce repeated K/V projection and prompt prefill for a matching prefix. They do not automatically optimize repeated reads of a shared prefix during every decode step.

0x0BC Hydragen: Batch Queries Over Identical Shared K/V

Hydragen starts from a batch whose requests share prefix K/V but have unique suffixes. For request r:

K_r = [K_shared ; K_suffix_r]
V_r = [V_shared ; V_suffix_r]

An ordinary per-request decode schedule sees a matrix-vector product against the shared prefix for every request. Hydragen concatenates or reshapes the queries that share that K/V object and turns the shared part into a larger matrix operation:

shared:
    Q_shared [B_group, T_q, H_q, d_h]
    K_shared [T_shared, H_kv, d_h]
    V_shared [T_shared, H_kv, d_v]
    -> O_shared [B_group, T_q, H_q, d_v]
    -> LSE_shared [B_group, T_q, H_q]

unique:
    Q_unique [B_group, T_q, H_q, d_h]
    K_unique [B_group, T_unique, H_kv, d_h]
    V_unique [B_group, T_unique, H_kv, d_v]
    -> O_unique, LSE_unique

merge:
    (O_shared, LSE_shared) + (O_unique, LSE_unique)
    -> O_exact

The systems gain is not that one query avoids attending to its prefix. Every query still has the same logical query-key pairs. The gain is that shared K/V can be loaded and reused while several query rows are processed, changing matrix-vector-shaped work into matrix-matrix-shaped work.

def hydragen_level(Q_group, K_shared, V_shared, K_unique, V_unique):
    O_shared, LSE_shared = attention_with_lse(
        Q_group,
        broadcast_shared(K_shared, group=Q_group.shape[0]),
        broadcast_shared(V_shared, group=Q_group.shape[0]),
    )
    O_unique, LSE_unique = attention_with_lse(
        Q_group, K_unique, V_unique
    )
    return merge_lse(
        [O_shared, O_unique],
        [LSE_shared, LSE_unique],
    )

The Hydragen repository’s pinned hydragen/attention.py makes the state contract concrete: its Torch path stacks partition outputs and LSE tensors, subtracts the maximum LSE, exponentiates the differences, and uses the resulting masses to combine outputs. Its Triton path specializes the two-partition merge. The implementation also supports multiple shared levels; a group size at one level may divide a larger group at another level.

def hierarchical_hydragen(snapshot):
    per_sequence = [[] for _ in snapshot.sequences]

    for chunk in snapshot.chunks_in_tree_order:
        begin, end = chunk.coverage
        Q_group = snapshot.Q[begin:end]
        O, LSE = attention_with_lse(Q_group, chunk.K, chunk.V)

        for local_row, sequence in enumerate(range(begin, end)):
            per_sequence[sequence].append((O[local_row], LSE[local_row]))

    return [
        merge_lse(outputs, lses)
        for outputs, lses in map(unzip, per_sequence)
    ]

The teaching pseudocode exposes one logical call per chunk. A production Hydragen implementation can fuse, reshape, or use variable-length kernels; the invariant is the same disjoint score partition and LSE-aware merge.

0x0BD ChunkAttention: Prefix Tree Plus Two-Phase Kernel

ChunkAttention couples a prefix-aware K/V tree to a different execution schedule. Each ChunkInfo in the pinned repository binds one chunk to a half-open sequence-index interval:

(chunk pointer, seq_idx_begin, seq_idx_end)

The runtime classifies chunks by coverage. A shared chunk enters the chunk-first phase; a private or below-threshold chunk stays in the sequence-first phase. The threshold is a tunable implementation decision, not a semantic distinction.

chunk-first phase:
    traverse chunks shared by several sequences
    batch those sequences' queries against one shared K/V chunk
    save partial online-softmax states

sequence-first phase:
    load each sequence's shared partial states
    traverse its private suffix chunks
    merge every partial state into the final row

def build_chunk_first_metadata(chunks, threshold):
    begins, ends, offsets = [], [], []
    partial_rows = 0

    for chunk in chunks:
        begin, end = chunk.coverage
        if end - begin <= threshold:
            continue
        begins.append(begin)
        ends.append(end)
        offsets.append(partial_rows)
        partial_rows += end - begin

    return begins, ends, offsets, partial_rows


for chunk_id, begin, end, offset in shared_chunk_metadata:
    Q_group = Q[begin:end]
    partial[offset:offset + end - begin] = partial_attention_state(
        Q_group, chunks[chunk_id].K, chunks[chunk_id].V
    )

for request in active_requests:
    state = empty_state()
    for chunk in request.path:
        if chunk.was_materialized_chunk_first:
            part = partial[chunk.offset + request.index - chunk.begin]
        else:
            part = partial_attention_state(
                request.q, chunk.K, chunk.V
            )
        state = merge_online_states(state, part)
    output[request] = finalize(state)

The pinned CUDA source constructs begins, ends, and offsets on the host, transfers the metadata, allocates

attns:    [partial_rows, H_q, d_v]
maxsums:  [2, partial_rows, H_q]

and then lets sequence-first execution load the saved partial output, maximum, and denominator state. In that source revision, partial outputs use the output scalar type while maximum and sum use float. This is a source observation, not a recommendation that every implementation use the same dtype split.

Why materialize partial states rather than directly accumulate into the final sequence output? Materialization gives chunk-first work independent output rows and avoids parent/child update ordering or atomic reduction inside the shared phase. It costs temporary memory and a later read. A direct-reduction alternative could reduce that buffer, but then synchronization, deterministic merge order, and write ownership become first-class kernel contracts.

0x0BE One Checked Four-Sequence Trace

The executable fixture runs three attention schedules over the same immutable tree:

reference:
    concatenate each sequence path
    evaluate one monolithic attention row

Hydragen coordinate:
    batch all queries covered by each chunk
    emit (normalized output, LSE)
    merge the three path partitions

ChunkAttention coordinate:
    materialize shared (u, m, l) partial rows
    compute private leaf state during sequence-first
    merge the three path partitions

For every sequence, both partitioned schedules match the monolithic output within $2.3\times10^{-16}$ absolute error in the binary64 oracle. That is rounding-level agreement in the fixture, not a claim of bitwise equality across GPU kernels, dtypes, or reduction orders.

The work and payload ledgers are:

The row and temporary-state formulas are:

$$N_{\mathrm{logical-pairs}} = \sum_r\sum_{c\in path(r)}T_c,$$ $$N_{\mathrm{physical-KV}} = \sum_{c\in\mathcal{C}}T_c, \qquad N_{\mathrm{saved-reads}} = N_{\mathrm{logical-pairs}}-N_{\mathrm{physical-KV}},$$ $$N_{\mathrm{partial}} = \sum_{c:\,coverage(c)>\tau}coverage(c),$$ $$M_{\mathrm{partial}} = N_{\mathrm{partial}} \left(d_vb_O+2b_{\mathrm{state}}\right).$$

Renderer-safe checked substitution:

logical pairs        = 19
unique physical rows = 10
saved duplicate reads = 19 - 10 = 9

one toy K/V row = (d_qk + d_v) * 2 B
                = (2 + 3) * 2 = 10 B

baseline K/V payload = 19 * 10 B = 190 B
shared K/V payload   = 10 * 10 B = 100 B

partial rows = coverage(C0) + coverage(C1) + coverage(C2)
             = 4 + 2 + 2 = 8
partial row  = d_v * 2 B + max * 4 B + sum * 4 B
             = 3 * 2 + 8 = 14 B
partial buffer = 8 * 14 B = 112 B

The K/V-read ledger is a conceptual payload model: it excludes query reads, output writes, metadata, cache-line effects, kernel launches, partial-state traffic, and hierarchy behavior. It proves what the fixture counts; it does not predict latency.

0x0BF Design Choices Are Workload And Kernel Contracts

No method dominates by name. The useful regime depends on shared-prefix length, suffix length, group size, hierarchy shape, K/V dtype, query/head geometry, kernel support, memory bandwidth, temporary-state traffic, and scheduler stability. Hydragen and ChunkAttention paper speedups remain source-reported results under their reported workloads and hardware.

Storage and execution mechanisms are composable only if their contracts align:

Loop 6/7:
    exact identity + protected tree path + immutable snapshot

Loop 9:
    coverage metadata + tensor ABI + exact state merge

M5.2:
    whether compatible requests are co-resident and ordered together

M4.5 / backend:
    whether a supported kernel exists for the chosen geometry

0x0BG Source-Observed Runtime Versus Normative Protocol

The executable oracle imports M4.3’s pinned online-state implementation rather than silently copying its merge. It also binds the Loop 6 prefix-reuse report and Loop 7 radix-runtime report by SHA-256. Identity, index mutation, allocator state, and scheduling are therefore consumed as immutable inputs.

0x0BH Failure Lab

0x0BI Loop 10: Shared Work Is Invariant, Traversal Is Not

Loop 9 proved exact state equivalence for one fixed tree. Loop 10 varies the shared-prefix chunk size while holding the logical attention problem constant:

batch B                  = 8
shared prefix S          = 64 tokens
private suffixes U_r     = [8,8,8,8,16,16,16,16]
K/V row payload          = 512 B
partial output width     = 128 FP16 values
partial normalizer state = two FP32 scalars

Ordinary per-sequence execution processes

$$N_{logical}=BS+\sum_rU_r.$$

An idealized exact shared-prefix schedule reads the shared K/V rows once:

$$N_{unique}=S+\sum_rU_r, \qquad N_{saved}=(B-1)S.$$

For the fixture:

logical K/V rows = 8*64 + 96 = 608
unique K/V rows  = 64 + 96   = 160
saved row reads  = 448

baseline payload = 608 * 512 B = 304 KiB
shared payload   = 160 * 512 B = 80 KiB
saved payload    = 224 KiB

Those row counts do not depend on chunk size. Traversal and temporary state do. For chunk size $P_c$:

$$N_{ordinary-chunks}=\sum_r\left\lceil\frac{S+U_r}{P_c}\right\rceil,$$ $$N_{shared-chunks}=\left\lceil\frac{S}{P_c}\right\rceil +\sum_r\left\lceil\frac{U_r}{P_c}\right\rceil.$$

If every shared chunk covers all $B$ queries and is materialized separately:

$$N_{partial}=B\left\lceil\frac{S}{P_c}\right\rceil,$$ $$M_{partial}=N_{partial}(d_vb_O+2b_{state}).$$

Larger chunks reduce metadata and partial-state rows in this regular workload. They do not create more shared K/V savings: the same 448 duplicate row reads are avoidable at every size. If the actual prefix boundaries are irregular, larger chunks may instead reduce exact matches or force a private remainder. The chunk-size decision therefore needs the prefix-length and branch-position distribution, not only one average shared-prefix length.

0x0BJ Physical Page Groups Are Not Paged-Kernel Blocks

vAttention keeps a per-layer K or V tensor virtually contiguous. For one tensor row of $B_{tensor-row}$ bytes and physical page-group size $G$:

$$P_G=\frac{G}{B_{tensor-row}}$$

is the number of token rows backed by one page group, provided divisibility holds. A request of $T$ rows needs

$$N_G=\left\lceil\frac{T}{P_G}\right\rceil, \qquad W_G=N_GG-TB_{tensor-row}.$$

The source-reported vAttention Table 8 gives Llama-3-8B, TP-1 one-layer K or V rows of 2,048 bytes. The checked arithmetic is:

The 1,024-token row deliberately lands on every page-group boundary. The 1,025th token exposes the staircase again. TP changes the local row width and therefore changes tokens per page; a page-group size cannot be translated into tokens without the tensor manifest.

The kernel-visible address path remains different:

PagedAttention:
    token -> user block table -> physical K/V block -> tensor strides

vAttention:
    token -> contiguous virtual offset -> GPU page-table translation

The Loop 10 oracle assigns zero user-space K/V block-table lookups to the vAttention path. It does not claim zero hardware translation, zero TLB misses, or zero runtime mapping work.

Source: Prabhu et al., vAttention, Figure 14. The authors report that 64 KiB pages did not materially degrade these tested kernels relative to 2 MiB pages. That observation is tied to their models, kernels, hardware, driver path, and access pattern; it is not a universal theorem that page size cannot affect TLB behavior.

0x0BK Workload Regimes Change Which Ledger Matters

This table deliberately does not assign a winner. M5.3 can reject an invalid combination and expose its ledgers. M5.2 owns which requests run together; M4.5 owns generic backend kernel selection and measured reduction strategy.

0x0BL A Measurement Protocol, Not A Magic Default

A defensible tuning pass holds semantic work constant and changes one contract at a time:

1. Freeze model/cache ABI:
   layers, local KV heads, head width, dtype/scales, positions, TP, backend.

2. Freeze workload trace:
   prompt/decode lengths, arrival order, prefix groups, branch offsets.

3. Enumerate legal tuples:
   (P_a, P_k, G, P_c) that pass allocator, kernel, VMM, and identity checks.

4. Reconcile structural ledgers:
   tail, metadata, hit/recompute, COW, table cells, visits, partial state.

5. Benchmark isolated kernels:
   prefill/decode separately; report context, batch, heads, dtype, hardware.

6. Replay end to end:
   measure TTFT, inter-token latency, goodput, memory headroom, fallbacks.

7. Hand candidates to M5.2:
   scheduling/admission policy chooses under its SLO and fairness contract.

Required observability includes:

allocator_block_size and kernel_block_size by cache group
kernel dispatch selected/rejected/fallback reason
request refs, unique blocks, valid tails, metadata bytes
full-block hit tokens and recomputed prompt-tail tokens
COW copied rows, traffic bytes, and destination capacity
dense/used/padded block-table cells and transfer bytes
shared group size, chunk visits, partial rows and state bytes
VMM page-group size, mapped groups, ready frontier, map latency

Without those counters, a throughput change cannot be attributed to memory capacity, a different admitted batch, kernel geometry, table preparation, shared-prefix locality, or mapping overhead.

0x0BM Source-Observed Contract Versus Checked Interpretation

0x0BN Granularity And Traversal Failure Lab

CachedAttention / AttentionStore: Reuse Across Inactive Sessions

Inactive-session reuse begins with an M5.3 question: does the resumed turn match an exact token prefix and cache ABI? CachedAttention/AttentionStore is included here because its reusable session state consumes that identity contract.

The hierarchy itself is not an M5.3 mechanism. GPU/host/storage residency, layer-wise prefetch, asynchronous saving, promotion visibility, and the recompute-versus-resume ledger now live in M5.5. M5.3 hands M5.5 a compatible cache key and covered token interval; M5.5 decides where the bytes live and when they are legal to read.

0x0C Paper-By-Contract And Operational Closure

It is tempting to put every K/V optimization into one table headed by latency or hit rate. That comparison is malformed before it starts. PagedAttention owns physical block placement. vAttention owns virtual-to-physical mapping. Prompt Cache declares reusable modules before requests arrive. RadixAttention discovers exact prefixes at runtime. Hydragen and ChunkAttention reuse attention work inside an active execution geometry. CachedAttention preserves compatible session history across inactive periods.

Those systems can coexist because they do not all own the same object. The first comparison question is therefore:

What object is reusable or mutable, who names it, and for how long is that name valid?

Only after that contract is explicit can a runtime compare traffic, TTFT, throughput, or hit rate.

0x0CA Seven Papers, Five Contract Lanes

The paper registry separates five lanes:

physical layout:
    PagedAttention, vAttention

declared modular reuse:
    Prompt Cache

runtime-discovered prefix reuse:
    RadixAttention

active execution reuse:
    Hydragen, ChunkAttention

inactive-session reuse:
    CachedAttention / earlier AttentionStore wording

Storage And Discovery Contracts

Execution Contracts

The table is not a leaderboard. In particular:

• Prompt Cache and RadixAttention differ in who declares reuse.
• PagedAttention and vAttention differ in what address the kernel sees.
• Hydragen and ChunkAttention differ in how an active shared-prefix execution is partitioned.
• CachedAttention changes lifetime and placement, not the exactness requirement for the reused history.

The alternatives can compose only through receipts. A declared Prompt Cache module can still be stored in paged blocks. A radix-tree hit can feed a Hydragen batch. An inactive session can be restored into a paged or virtual layout. Composition does not erase any intermediate identity, ownership, mapping, or execution gate.

0x0CB Prompt Cache: Declared Reuse Is Not Prefix Discovery

A25 introduced Prompt Cache because not every reusable segment is most naturally discovered as a longest prefix. System messages, templates, and documents may be known before requests arrive. Prompt Cache makes those segments explicit as prompt modules inside a schema.

The retained paper figure first separates three mechanisms. Autoregressive generation recomputes prior state, ordinary K/V caching retains the current request history, and Prompt Cache imports precomputed states for declared segments that may recur across prompts.

The hard part is positional identity. A module cannot be moved to arbitrary positions merely because its text is unchanged. The schema assigns relative locations and may leave gaps so parameters or uncached text can occupy their declared slots. This can produce discontinuous position IDs in the assembled prompt. Reuse is exact only under the position contract on which the cached states were computed.

The paper’s schema/module example makes that assembly visible:

One typed teaching contract is:

@dataclass(frozen=True)
class PromptModuleReceipt:
    schema_id: str
    schema_generation: int
    module_id: str
    module_parameters_digest: str
    token_ids: tuple[int, ...]
    position_ids: tuple[int, ...]
    semantic_manifest_digest: str
    layout_manifest_digest: str
    namespace_id: str
    namespace_generation: int
    physical_refs: tuple[PhysicalRef, ...]

The receipt has two independent equal-length sequences:

$$N_{\text{module}} = |\text{token\_ids}| = |\text{position\_ids}|$$

Matching module text while changing the position sequence is not a hit:

$$H_{\text{module}} = \mathbf{1}[T_p = T_c] \mathbf{1}[\Pi_p = \Pi_c] \mathbf{1}[S_p = S_c] \mathbf{1}[A_p = A_c]$$

where $T$ is the token sequence, $\Pi$ is the position sequence, $S$ is the schema/generation contract, and $A$ is the semantic cache ABI. The product is Boolean conjunction, not a probability model.

def assemble_declared_prompt(prompt, schema, module_cache, namespace):
    authorize(namespace)                         # before cache lookup
    parsed = parse_pml(prompt)
    require(parsed.schema_id == schema.schema_id)
    require(parsed.schema_generation == schema.generation)

    segments = []
    for item in parsed.items_in_prompt_order:
        declared = schema.resolve(item.module_id)
        positions = declared.positions_for(item.parameters)

        if item.is_cached_module:
            receipt = module_cache.lookup(
                schema=schema.identity,
                module=item.module_id,
                parameters=item.parameters,
            )
            require(receipt.token_ids == tokenize(item.rendered_text))
            require(receipt.position_ids == positions)
            require_compatible(receipt, namespace, current_cache_abi())
            acquire_leases(receipt.physical_refs)
            segments.append(receipt)
        else:
            segments.append(compute_at_positions(item, positions))

    return concatenate_in_declared_position_order(segments)

This is a paper-by-contract alternative, not a recommendation that every prompt adopt PML. It transfers complexity from online prefix discovery to schema authoring, module population, position reservation, invalidation, and application integration.

0x0CC CachedAttention: Inactive Lifetime Is A Cross-Article Handoff

The paper now titled CachedAttention appeared with AttentionStore terminology in an earlier version and in A25’s retained figure. Its central observation is that a multi-turn session often discards historical K/V when it becomes inactive, then recomputes the same history when the next user turn arrives.

For a session with historical interval $[0,H)$ and new user tokens $[H,H+U)$, the logical work boundary is:

$$T_{\text{prefill,baseline}} = H + U$$ $$T_{\text{prefill,resume}} = U \qquad\text{only if historical K/V }[0,H)\text{ is compatible and ready}$$

The article does not infer latency from these token counts. Loading $H$ rows from another tier can be slower than recomputation for some hardware, models, or queue states. M5.3 emits:

SessionReuseReceipt:
    authorized session and tenant identity
    model/cache semantic digest
    physical representation/layout digest
    exact covered token interval [0, H)
    position/truncation contract
    publication generation
    source-tier object identity

M5.5 then owns:

tier location and directory
fetch/prefetch timing
promotion and demotion
layer-wise loading
asynchronous saving
fallback to recomputation
scheduler-aware tier placement

The ownership handoff is M5.3 identity receipt -> M5.5 placement, loading, and fallback; neither side may silently reinterpret the other’s receipt.

A matching session ID is therefore only one field. Reusing a prior turn after an adapter change, model replacement, position-contract change, cache quantizer change, namespace rotation, or incomplete save is a compatibility failure even if the conversation label is unchanged.

0x0CD One Reuse Attempt Is A Versioned Concurrency Protocol

Loops 2-10 introduced versions at their local ownership boundaries. Loop 11 closes them into one use receipt. For the checked synthetic path, the evidence tuple is:

$$E = ( g_{ns}, d_{sem}, d_{layout}, v_{index}, v_{tree}, g_{pool}, f_{map}, v_{exec} )$$

with namespace generation $g_{ns}$, semantic and layout digests, index and tree versions, physical-pool generation, ready mapping frontier, and execution snapshot version. These coordinates do not necessarily live in one runtime struct. They are the evidence that must remain mutually consistent.

The use gate is:

$$G_{use} = G_{auth} \land G_{compat} \land G_{version} \land G_{lease} \land G_{map} \land G_{snapshot}$$

An index match with $G_{use}=0$ is not an executable hit.

The checked transaction order is:

1. authorize namespace before any cache-existence lookup
2. build semantic/layout key and validate namespace generation
3. lookup candidate; retain collision witness if policy requires it
4. acquire path and physical-object leases
5. validate index version, tree version, pool generation, valid frontiers
6. validate declared-module positions or session interval when applicable
7. wait until physical mapping covers every dereferenced row
8. freeze immutable execution snapshot and kernel ABI
9. execute
10. release leases, or publish one complete COW successor atomically

def acquire_executable_reuse(request, expected, runtime):
    runtime.auth.authorize(request.principal, expected.namespace_id)

    candidate = runtime.index.lookup(expected.concrete_key)
    require(candidate.namespace_generation == expected.namespace_generation)
    require(candidate.semantic_digest == expected.semantic_digest)
    require(candidate.layout_digest == expected.layout_digest)
    verify_collision_witness(candidate, expected)

    leases = runtime.ownership.acquire(candidate.path_and_physical_refs)
    require(leases.cover(candidate.path_and_physical_refs))
    require(runtime.index.version == expected.index_version)
    require(runtime.tree.version == expected.tree_version)
    require_all_pool_generations(candidate, expected.pool_generations)
    require_all_valid_frontiers(candidate, expected.covered_interval)

    runtime.mapper.wait_ready(candidate.required_mapping_frontier)
    snapshot = runtime.execution.freeze(candidate, leases)
    require(snapshot.version == expected.execution_snapshot_version)

    return ExecutableReuseReceipt(candidate, leases, snapshot)

Race Closure

The paper sources motivate the individual mechanisms. The unified transaction is a checked rewrite interpretation. The Loop 11 oracle validates ordering and rejection reasons; it does not prove a production implementation linearizable under real threads.

0x0CE Security Isolation Is Part Of Exactness

K/V bytes are derived from private prompt content. A numerically exact hit in the wrong tenant is a security failure. Security is therefore not an optional layer applied after cache correctness.

Authorization Before Lookup

The safe order is:

authenticate principal
    -> authorize cache namespace
    -> validate namespace generation
    -> construct or expose candidate lookup
    -> validate semantic/layout compatibility
    -> acquire reusable object

Looking up first and rejecting later can still disclose cache existence through hit/miss timing or counters.

Salt, Hash, Authorization, And Witness Are Different Controls

The vLLM prefix-caching documentation describes cache_salt entering the first block hash so requests sharing a trust group can reuse one another’s blocks. That is a useful isolation key. It is not authentication, authorization, namespace revocation, or a guarantee that every timing channel is closed.

Revocation And Purge

A purge cannot mean only “delete the hash-table entry.” A strict namespace revocation protocol is:

1. stop admitting requests to namespace generation g
2. advance the authorized namespace generation to g+1
3. invalidate index candidates from g
4. wait for or cancel live leases from g
5. release or overwrite physical objects according to the threat model
6. remove external-tier copies through the M5.5 directory
7. emit completion only when no executable receipt from g remains

Whether released memory must be zeroed immediately depends on allocator and hardware isolation. The invariant is narrower and mandatory: stale bytes must never become visible to a new owner merely because a physical ID or virtual slot was recycled.

Telemetry Hygiene

Metrics need stable low-cardinality identifiers, not raw prompts, token lists, or unsalted concrete cache keys. The checked fixture rejects both raw_prompt_in_metrics and unsalted_cache_key_in_metrics. Debug traces that must preserve a witness need access controls, retention limits, and an explicit incident workflow; they should not silently become normal metrics.

0x0CF Observability Must Reconcile State

A single prefix hit rate cannot identify the failing contract. Loop 11 uses a monotone funnel:

$$N_{req} \ge N_{auth} \ge N_{cand} \ge N_{compat} \ge N_{gen} \ge N_{lease} \ge N_{map} \ge N_{snap} \ge N_{exec}$$

The checked synthetic counts are:

requests                 12
authorized lookups       11   (1 authorization rejection)
candidate matches         9   (2 index misses)
compatible matches        7   (2 semantic/layout rejections)
current generations       6   (1 stale generation)
leased objects            6
mapping-ready receipts    5   (1 mapping frontier lag)
current snapshots         4   (1 stale execution snapshot)
executed hits              4

Every difference has one rejection bucket. Reporting only 4/12 as a hit rate hides whether the workload stopped sharing prefixes, an adapter changed, the allocator recycled objects, mappings lagged, or a concurrent mutation invalidated the snapshot.

Reconciliation Gauges

For a snapshot whose allocator states are declared mutually exclusive:

$$N_{pool} = N_{free} + N_{evictable} + N_{live} + N_{reserved\text{-}or\text{-}copying}$$

The fixture checks:

12 = 3 free + 2 evictable + 5 live + 2 reserved/copying

Refcounts need a reachability oracle:

$$\Delta_{ref} = N_{ref,recorded} - N_{ref,derived}$$

where derived references include request maps and active leases under the Loop 5 convention. The checked snapshot has $9-9=0$. A nonzero value is not a performance metric; it is an ownership-integrity alert.

Mapping readiness is similarly directional:

$$L_{map} = \max(0, f_{required} - f_{ready})$$

The checked path has $L_{map}=0$. A positive lag blocks execution even if virtual addresses are reserved and candidate identity is exact.

Counter Families And Alert Meaning

Useful alerts are joint predicates, not isolated thresholds:

allocator exhaustion:
    free == 0 and evictable == 0 and allocation_failures rising

locked-cache pressure:
    free == 0 and evictable > 0 and locked_eviction_rejects rising

reference leak:
    recorded_refcount - derived_refcount != 0 after grace interval

mapping stall:
    required_frontier > ready_frontier and map_wait_age > SLO budget

compatibility churn:
    candidate_matches stable and compatible_matches falling

stale receipt race:
    candidate_matches stable and generation/version rejects rising

security boundary pressure:
    cross_namespace_rejects or stale_namespace_rejects rising

M5.2 owns the SLO budget and service response. M5.3 owns the factual counters that tell M5.2 why an otherwise attractive request is not physically executable.

0x0CG Cumulative Failure Closure

Loops 2-10 already carried negative fixtures for identity, accounting, addressing, allocator lifecycle, exact-prefix reuse, radix mutation, vAttention mapping, shared-prefix execution, and granularity sensitivity. Loop 11 binds all nine prior reports and fixture hashes before adding its own failures:

Loop 2-10 negative cases = 184
Loop 11 negative cases   = 27
cumulative checked cases = 211

This number is not coverage of every production failure. It proves that the named teaching contracts have deterministic rejection paths and that Loop 11 did not silently replace earlier evidence.

The final failure rule is:

Fallback may lose reuse, but it may not weaken identity, ownership, mapping, or execution exactness.

Recomputation is often the safest fallback. Reusing a stale or unauthorized object to preserve hit rate is not graceful degradation.

0x0CH Source-Observed Contract Versus Unified Protocol

0x0D Worked Ledger

TP-Local Checked Reconciliation

The executable fixture binds to the Loop 2 layout rather than copying geometry into an unrelated calculator:

32 cache layers
4 local K/V heads on TP rank 0 of 2
head width 128
FP16 K and FP16 V

B_row,rank = 64 KiB / token
P = 16 tokens / block
B_block,rank = 1 MiB / physical block

Three requests form a nested exact-prefix family:

The rectangular reference ledger is:

logical request rows = 33 + 25 + 16 = 74
logical payload      = 74 * 64 KiB = 4.625 MiB

reserved rows        = 64 + 48 + 32 = 144
reserved bytes       = 144 * 64 KiB = 9 MiB
reservation slack    = 70 * 64 KiB = 4.375 MiB

Paging without deduplicating request references gives six block-table entries:

request-view slots    = 6 * 16 = 96
request-view capacity = 6 MiB
request-view tail     = (96 - 74) * 64 KiB = 1.375 MiB

But the union of block IDs is only {100, 101, 102}. Blocks 100 and 101 are full; block 102 contains one valid row:

unique materialized rows = 16 + 16 + 1 = 33
unique useful payload    = 33 * 64 KiB = 2.0625 MiB

unique physical slots    = 3 * 16 = 48
unique capacity          = 3 MiB
unique physical tail     = 15 * 64 KiB = 0.9375 MiB

This is why the 22 request-view tail slots cannot be labeled physical waste. Seven of B’s non-visible block positions contain valid rows materialized for A; the same is true for C’s shorter view. The checked identities are:

9 MiB = 4.625 MiB logical references + 4.375 MiB rectangular slack
6 MiB = 4.625 MiB logical references + 1.375 MiB request-view tail
3 MiB = 2.0625 MiB unique materialized + 0.9375 MiB unique tail
6 MiB = 3 MiB unique capacity + 3 MiB reference capacity avoided by sharing
4.625 MiB = 2.0625 MiB unique materialized + 2.5625 MiB deduplicated payload

The physical pool contains eight provisioned blocks:

pool provisioned = 8 * 1 MiB = 8 MiB
live unique       = 3 * 1 MiB = 3 MiB
idle reusable     = 5 * 1 MiB = 5 MiB

The fixture separately charges six 4-byte request-map entries, eight 32-byte block descriptors, two 24-byte cached-hash entries, three 2-byte valid-tail records, five 4-byte free-queue entries, and 128 fixed bytes:

M_meta = 24 + 256 + 48 + 6 + 20 + 128 = 482 synthetic bytes

Those record sizes are test inputs, not measurements and not a claim about their CPU/GPU placement. The oracle rejects 14 one-field failures, including a fixture that counts all six request references as six unique blocks.

Model-Wide Capacity-Pressure Illustration

The older running example uses a model-wide rather than TP-local convention:

L     = 32
H_kv  = 8
d_h   = 128
bytes = 2

One token’s K/V across all layers:

L * 2 * H_kv * d_h * bytes
= 32 * 2 * 8 * 128 * 2
= 131,072 bytes
= 128 KiB

If a block holds 16 tokens, the all-layer conceptual block payload is:

16 * 128 KiB = 2 MiB

Real systems may block per layer, head group, or backend-specific layout. This ledger is a capacity-pressure example, not a literal vLLM memory struct.

A 4096-token prompt has:

4096 / 16 = 256 blocks

Its all-layer K/V payload is:

4096 * 128 KiB = 512 MiB

If another request has an exact 3072-token prefix hit:

hit blocks = 3072 / 16 = 192 blocks

prefill tokens skipped = 3072
new prompt tokens to compute = S_prompt - 3072

The benefit is not just memory. The prefill compute for those 3072 tokens is skipped, which can improve TTFT. But if the response generates 1024 new tokens, decoding then grows the cache by up to 1024 more rows. Under M5.1’s ordinary stop the final emitted token is never processed as an input row, so 1023 rows are appended; only M5.1’s optional repair append adds the 1024th:

future decode growth <=
    1024 * 128 KiB
  = 128 MiB

ordinary stop:
    1023 * 128 KiB
  = 127.875 MiB

That growth still has to be admitted, allocated, and scheduled.

0x0E What M5.3 Does Not Claim

0x0F Boundary To Later M5

M5.3 gives M5.4-M5.8 the memory object they will modify:

The systems arc is:

M5.1:
    define K/V state

M5.2:
    schedule next work under KV pressure

M5.3:
    allocate, address, share, and exactly reuse K/V

M5.4:
    decide whether all old K/V remains visible

0x10 Publish Gate

0x10A Final Formula Closure

The final registry contains 78 formulas from Loops 3-11. Loop 12 adds no new mechanism equation. It checks that every registered formula has a unique ID, units, an accounting or validity convention, and an article location. The audit also makes the edge conditions explicit:

The code blocks remain accessibility fallbacks, not second formulas with a different convention. The final audit rejects an empty rendered math node, unbalanced display delimiters, duplicate formula IDs, or a registered formula without units and a convention.

0x10B Final Source And Figure Closure

The source ledger now distinguishes four evidence classes:

All 15 source figures have explicit provenance entries. The 16 custom desktop/mobile visual pairs are original reconstructions tied to local fixtures; they do not inherit a paper’s benchmark claim. The final audit also checks that every external primary URL appears in the article, every pinned revision is named, and every local source or figure exists.

0x10C Final Rendering Closure

The publication check operates on both Markdown and the generated page. It requires balanced math delimiters outside code fences, non-empty generated math/tex nodes, resolved desktop and mobile images, accessible SVG role/title/desc metadata, and generated targets for every local article link. A successful Astro build is necessary but not sufficient: the generated M5.3 page must pass the artifact audit after the build.

0x10D Final Cross-Article Boundary Closure

This table follows the current roadmap numbering: the decode-kernel owner is M4.5. It also prevents exact physical reuse from silently absorbing scheduling, lossy retention, hierarchy movement, architecture, speculation, or quantization policy.

References

Local source articles:

• M4.3 - IO-Aware Attention and FlashAttention-1
• M4.5 - Decode Kernels and Backend Boundaries
• M5.1 - Autoregressive Serving State: KV Cache Lifecycle and Scheduler Pressure
• M5.2 - Continuous Batching and Scheduler Pressure
• M5.4 - Long-Context K/V Policies
• M5.5 - KV Retrieval, Offload, and Hierarchical Memory
• M5.6 - Prefill/Decode Disaggregation and K/V Placement
• M5.7 - MQA/GQA K/V Head Sharing
• M5.8 - MLA Latent Cache and Absorbed Kernels
• M6.5 - Multi-Adapter Serving Runtime
• M7.1 - Speculative Decoding: Draft, Verify, Accept, Reject
• M8.6 - Live-Data Quantization: Activations and K/V Cache
• Exploring the Transformer Series (20) - KV Cache
• Exploring the Transformer Series (24) - KV Cache Optimization
• Exploring the Transformer Series (25) - KV Cache Optimization for Handling Long Text Sequences

External sources:

• Efficient Memory Management for Large Language Model Serving with PagedAttention
• vAttention: Dynamic Memory Management for Serving LLMs without PagedAttention
• Microsoft vAttention research prototype at pinned commit ef3fff25
• SGLang: Efficient Execution of Structured Language Model Programs
• Prompt Cache: Modular Attention Reuse for Low-Latency Inference
• Hydragen: High-Throughput LLM Inference with Shared Prefixes
• Hydragen pinned implementation
• ChunkAttention: Efficient Self-Attention with Prefix-Aware KV Cache and Two-Phase Partition
• ChunkAttention pinned implementation
• Cost-Efficient Large Language Model Serving for Multi-turn Conversations with CachedAttention
• Fast and Expressive LLM Inference with RadixAttention and SGLang
• SGLang v0.5.11 compressed radix cache and lock/eviction implementation
• SGLang v0.5.11 request cache-publication paths
• SGLang v0.5.11 cache-aware scheduling policies
• SGLang v0.5.11 scheduler integration
• SGLang v0.5.11 token-to-K/V slot pool
• vLLM v0.23.0 K/V cache manager
• vLLM v0.23.0 KVCacheBlock and free-block queue
• vLLM v0.23.0 block pool
• vLLM v0.23.0 allocation and request-release path
• vLLM v0.23.0 K/V cache coordinator and common-hit convergence
• vLLM v0.23.0 full-attention prefix lookup
• vLLM v0.23.0 CPU-staged block tables
• vLLM pinned paged-attention kernel template
• vLLM pinned V1 paged-attention launcher
• vLLM pinned paged-attention benchmark harness
• vLLM v0.23.0 GPU-resident group block tables
• vLLM v0.23.0 K/V cache group interface
• vLLM v0.23.0 automatic prefix caching design
• vLLM v0.23.0 prefix-cache isolation and cache_salt documentation
• vLLM pinned source revision
• SGLang pinned source revision