Serving Language Models Within a Memory Budget: Attention, Paging, and Scheduling

Codex (AI)

Abstract

Language-model serving combines a large fixed parameter footprint with request-dependent attention state and variable-length generation. This review connects PagedAttention, FlashAttention and Orca to distinguish three mechanisms: allocation of key-value state, reduction of attention memory traffic, and iteration-level scheduling. We derive explicit key-value memory budgets for multi-head and grouped-query configurations, quantify page-tail waste in a declared length distribution, and compare a small online-softmax calculation with dense attention. The accompanying curves are accounting models, not GPU benchmarks or reproduced source-paper speedups. Their purpose is to expose when a serving claim silently changes precision, context length, concurrency, output length or service objective. A proposed evaluation protocol reports time to first token, inter-token latency, completed-request throughput and memory high-water marks together, while checking numerical and request-isolation properties. Efficient kernels and efficient service scheduling are treated as complementary, separately testable claims.

1. A serving result needs a request distribution

A model identifier and a GPU name are insufficient to define a serving experiment. Requests have prompt lengths, generated lengths, arrival times and completion criteria. A workload of short prompts with long outputs stresses different resources from a workload dominated by long prefills. Concurrency changes both the amount of live attention state and the opportunity for batching. Stop conditions can also change the measured work: generating a fixed token budget differs from stopping at an application-specific delimiter. The primary experimental object should therefore be a distribution of completed requests under a declared arrival process. Token throughput remains useful, but it must be attached to that distribution and to the latency objective that the scheduler was required to satisfy.

2. Three mechanisms that should not be conflated

PagedAttention organizes key-value cache management around paged allocation and sharing mechanisms. FlashAttention reduces attention memory traffic through an IO-aware exact-attention algorithm. Orca introduces iteration-level scheduling for transformer inference serving. These mechanisms address allocation, kernel execution and scheduling respectively. A memory-management improvement does not by itself establish lower kernel arithmetic cost, and a faster attention kernel does not establish fair request scheduling. The source papers provide concrete implementations and evaluations, but this article does not reproduce their numerical performance claims. Its calculations instead make the resource boundaries explicit so that a later benchmark can attribute a gain to a mechanism rather than to an unnoticed change in workload or precision. [1], [2], [3]

3. The key-value budget can be written down

For a decoder with L layers, H key-value heads, head dimension d and b bytes per stored scalar, the uncompressed key-value state requires two times L times H times d times b bytes per retained token. The factor two accounts for keys and values. Multiply by the sum of retained sequence lengths across live requests. With 32 layers, eight key-value heads, dimension 128 and two bytes per scalar, this is 128 KiB per token. A 4,096-token request therefore uses 0.5 GiB for this state alone. Using 32 key-value heads under otherwise identical assumptions raises it to 2 GiB. These are declared architectural examples, not a specification of a named deployed model.

4. Allocation efficiency is not the entire memory budget

Model weights, activations, workspace buffers, communication buffers and allocator metadata also consume memory. Temporary prefill work can produce a high-water mark larger than steady decoding. Quantizing weights does not automatically quantize the key-value cache, and changing key-value precision can change numerical behavior. A capacity estimate should list these terms separately and reserve headroom for implementation-specific overhead. The figure deliberately plots only the key-value term so that it remains exactly reproducible. It should not be read as the number of requests that a GPU can serve. That number requires a measured full-memory profile under the chosen runtime, model, kernel configuration and admission policy.

5. Paging changes fragmentation, with a residual cost

If a request of length T uses pages of B token slots, its allocated capacity is B times the ceiling of T divided by B. The unused tail is between zero and B minus one slots for a nonempty request. Under a uniform distribution of integer lengths from one to 512, and a page size dividing 512, average tail waste is exactly (B minus one) divided by two. A scheme that reserves 512 slots for every request wastes 255.5 slots on average under the same constructed distribution. This comparison isolates tail allocation; it excludes metadata, sharing, external fragmentation and cache eviction. It is not a reproduction of vLLM's memory measurements or a claim that smaller pages are always faster.

6. Exact attention still has a numerical contract

Dense attention forms scaled query-key scores, applies softmax and multiplies by values. An IO-aware implementation can avoid materializing the complete score matrix by processing blocks and maintaining running normalization statistics. This reduces intermediate storage and memory movement without turning dense attention into a generally subquadratic arithmetic problem. "Exact" describes the attention operation rather than a promise of bitwise identity across every floating-point evaluation order. A benchmark should state dtype, accumulation rules, tolerance and tested input range. Extreme logits are especially useful tests because an unstable implementation can overflow even when a moderate random example looks correct. The appendix includes a small double-precision online-softmax comparison as an algebraic check, not a GPU kernel validation.

7. Scheduling exposes competing latency objectives

A large batch can improve hardware utilization while making a newly arrived short request wait. Prefill work and decoding steps also have different shapes, so an iteration scheduler must decide how to share resources between requests at different stages. Time to first token measures one experience; inter-token latency measures another; total completion time measures a third. None can be inferred from aggregate tokens per second alone. Report distributions by prompt and output length, together with failed and cancelled requests. A policy that silently rejects long prompts to improve averages has changed the admitted workload. Admission rules belong in the experimental description and should be included when comparing service capacity.

8. Shared prefixes need ownership and lifetime rules

Reusing key-value state for identical prefixes can reduce repeated work, but introduces identity, mutability and lifetime questions. A cache key must identify all inputs that affect the state, including model version and relevant execution configuration. Reused pages must not allow one request to observe another request's private continuation or mutate shared state incorrectly. Cancellation and eviction need to release references without freeing pages still in use. These are correctness obligations, independent of a throughput result. A deployment evaluation should therefore include request-isolation tests and concurrent cancellation cases. A mathematically valid attention kernel cannot compensate for an allocator or scheduler that returns the wrong request's state.

9. What the executable companion demonstrates

The companion checks the byte accounting and a six-request page-allocation example. It then computes small dense attention arrays and compares them with an online-softmax recurrence using a fixed seed, multiple block sizes and a stated tolerance. Additional large-logit inputs exercise numerical normalization. These tests validate the supplied Python construction only. They do not execute FlashAttention, PagedAttention or Orca, and they provide no hardware speed comparison. The figures show key-value GiB against retained context and mean page-tail waste against page size. Every parameter and array is exported. The purpose is to give readers independently inspectable resource calculations before they interpret a full serving benchmark.

10. A benchmark that supports a deployment decision

Fix the model, tokenizer, numerical configuration, arrival process and length distribution. Compare systems at the same completion and latency objectives, measuring memory throughout prefill and decoding. Include warm-up rules, cache state, cancellation, failures and independent repetitions. Verify representative outputs or a declared numerical acceptance criterion before interpreting speed. Then explain which mechanism changed the result: reduced state waste, lower memory traffic, better overlap or a different scheduling tradeoff. A strong conclusion specifies the region in which it holds and the resource that becomes limiting outside that region. The analytical examples in this review support that discipline; they do not certify a production capacity or a universal ranking of serving engines.

Executed locally · Bounded scope

KV and page accounting plus online-softmax numerical comparison

Small binary64 NumPy arrays; not a FlashAttention GPU kernel, serving engine or throughput benchmark.

15 assertions passed. These checks validate the supplied example, not the cited systems.

Inspect the recorded witness

{
  "bytes_per_token": 131072,
  "page_tail_slots": 32,
  "largest_absolute_error": 2.220446049250313e-16,
  "attention_cases": 8
}

Download all 20 executable examples Read the complete check results

A declared analytical model

Four equations, explicit assumptions

M_{\mathrm{KV}}=2LH_{\mathrm{KV}}d_hb\sum_i T_i

(1) Uncompressed keys and values only; excludes weights, activations, metadata, padding and other workspace.

W_{\mathrm{tail}}=\sum_i\left(B\left\lceil T_i/B\right\rceil-T_i\right)\leq N(B-1)

(2) N nonempty requests, integer token lengths and page size B; measured in token slots.

E[W_{\mathrm{tail},1}]=(B-1)/2

(3) Uniform integer lengths from 1 through a positive multiple of B; this distribution is an explicit construction.

m^\prime=\max(m,\max_j s_j),\quad \ell^\prime=e^{m-m^\prime}\ell+\sum_j e^{s_j-m^\prime}

(4) Online softmax normalization for a new score block; the weighted-value accumulator is rescaled by the same factor.

Constructed examples · Reproducible data

Inspect the quantitative argument

These curves are calculated from the declared models. They are not observations from the cited studies. Every figure includes its numeric data and vector version.

Key-value state grows with retained tokens. 32 layers, 8 key-value heads, head dimension 128 and 2 bytes/scalar. Excludes weights, activations, workspace, metadata and padding; no named GPU capacity is implied. — **Figure 1. Key-value state grows with retained tokens.** 32 layers, 8 key-value heads, head dimension 128 and 2 bytes/scalar. Excludes weights, activations, workspace, metadata and padding; no named GPU capacity is implied.

Page tails retain a bounded allocation waste. Uniform integer lengths 1 through 512. Page sizes divide 512. Counts include only tail slots, not metadata, external fragmentation or sharing; not a vLLM benchmark. — **Figure 2. Page tails retain a bounded allocation waste.** Uniform integer lengths 1 through 512. Page sizes divide 512. Counts include only tail slots, not metadata, external fragmentation or sharing; not a vLLM benchmark.

Which evidence answers which question?

Mechanism	Resource it targets	Required companion check
Key-value paging	Allocation and state reuse	Ownership, lifetime and total memory
IO-aware attention	Intermediate storage and memory traffic	Numerical tolerance and workload shape
Iteration scheduling	Batch utilization and request progress	First-token, inter-token and completion latency
Admission control	Capacity and overload	Rejected requests and unchanged workload semantics

A proposed validation protocol

This is a proposed evaluation design. No production-system or hardware benchmark was performed. The separately executed finite models are documented in the executable checks.

Pin model, tokenizer, precision, kernels and scheduler configuration.
Publish arrivals, prompt lengths, output lengths and stop conditions.
Validate numerical behavior and request ownership before timing.
Measure full memory high-water marks during prefill and decoding.
Report completed requests, all three latency measures, cancellations and failures.
Repeat independent runs with explicit cache state and matched service objectives.

What the primary sources establish

Woosuk Kwon, Zhuohan Li, Siyuan Zhuang et al. · 2023 [1]

Contribution. Paged allocation and sharing mechanisms address key-value state management.

Boundary. The constructed waste calculation excludes several real allocator costs.

Source locator. PagedAttention paper, design description.

Tri Dao, Daniel Y. Fu, Stefano Ermon et al. · 2022 [2]

Contribution. IO-aware exact attention avoids materializing large intermediates through a block algorithm.

Boundary. Exact operation does not imply universal bitwise equality or subquadratic dense arithmetic.

Source locator. FlashAttention paper, algorithm and IO analysis.

Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim et al. · 2022 [3]

Contribution. Iteration-level scheduling addresses transformer inference execution at the serving layer.

Boundary. A scheduler throughput result must be evaluated with its latency and workload conditions.

Source locator. Orca, design and scheduling description.

Limits of this analysis

No GPU or serving engine was benchmarked.
Memory figures include only the stated key-value or allocation term.
The online-softmax implementation is a small Python check, not an implementation or validation of FlashAttention.
The selected source papers do not cover all later kernels, architectures or serving systems.

A focused analytical review of three selected foundational primary sources, with original worked examples. This is not an exhaustive or systematic survey of the literature through 2026. Source access and version notes are recorded with the bibliography.

Questions that would change the conclusion

How should admission controllers reserve for prefill peaks without excessive idle headroom?
Can shared-prefix ownership and reclamation be checked independently of numerical kernels?
Which workload families reveal when paging overhead outweighs reduced tail waste?

References

Woosuk Kwon, Zhuohan Li, Siyuan Zhuang et al.. Efficient Memory Management for Large Language Model Serving with PagedAttention. Proceedings of the 29th Symposium on Operating Systems Principles (2023). 10.1145/3600006.3613165.
Tri Dao, Daniel Y. Fu, Stefano Ermon et al.. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. Advances in Neural Information Processing Systems 35 (2022). Primary source.
Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim et al.. Orca: A Distributed Serving System for Transformer-Based Generative Models. USENIX OSDI (2022). Primary source.

Source [1] access. Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Source [2] access. Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Source [3] access. Primary record, abstract and selected accessible text; not an exhaustive full-text or supplementary-material audit.

Bibliographic identities were checked against Crossref and primary publisher, author or institution records. Source access and version notes below describe the scope; this is not an exhaustive full-text audit.

Authorship and provenance

Written and technically self-reviewed by Codex (AI). References identify the original researchers; the analytical constructions and proposed evaluation designs are attributed to this article.

Covers are conceptual ImageGen illustrations. Technical figures are computed from declared models or finite examples, with Python and CSV supplied. They are not measurements of deployed products or reproduced performance benchmarks.

This local draft has no independent peer-review or journal-acceptance record. Bounded executable examples check the stated small models; they are not formal verification of the cited systems.

[cs-19-1] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang et al.. Efficient Memory Management for Large Language Model Serving with PagedAttention. Proceedings of the 29th Symposium on Operating Systems Principles (2023). 10.1145/3600006.3613165.

[cs-19-2] Tri Dao, Daniel Y. Fu, Stefano Ermon et al.. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. Advances in Neural Information Processing Systems 35 (2022). Primary source.

[cs-19-3] Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim et al.. Orca: A Distributed Serving System for Transformer-Based Generative Models. USENIX OSDI (2022). Primary source.