One idea from vLLM, rebuilt from first principles.
A from-scratch Rust and CUDA reimplementation of the core idea behind vLLM's PagedAttention: page KV-cache memory on demand instead of pre-allocating the worst case, measured against HuggingFace's own cache on a real GPU.
A scaled-down (64-page) replica of the same free-list algorithm the Rust allocator runs: a page is claimed the moment a sequence needs one, and returned to the pool the instant it finishes.
VRAM at 32 concurrent sequences
603.98 MB to 75.50 MB, decode step 50, GPT-2 124M fp16
Sequences served per GB VRAM
paged vs naive pre-alloc, decode step 50
Decode latency overhead
10.0ms vs 7.5ms against HF DynamicCache, reported, not hidden
Allocator stress test
500 alloc/free cycles, 16 seqs/cycle, 0 leaks, 0 OOM errors
This repository started as SymboLR, a genetic-programming engine evolving learning-rate schedules. Its own ablation study caught it gaming a synthetic proxy, so the project pivoted to a problem with a ground truth a real GPU can measure directly.
Same stack, Rust, CUDA, PyTorch, PyO3. Different problem, one where "does it work" has a hardware answer. The full story, with the ablation result that triggered it, is in Failures & iterations below.
A KV-cache that reserves the worst case, forever.
HuggingFace's default cache commits a fixed VRAM budget the moment a sequence starts, whether it generates 10 tokens or 500. PageForge pages that memory instead, on demand.
Naive pre-allocation reserves the worst case, always
HuggingFace's default KV-cache commits a full max_seq_len budget the moment a sequence starts. For GPT-2, that is 18.87 MB per sequence at a 512-token budget, held for the sequence's entire life regardless of how many tokens it actually generates.
603.98 MB
32 sequences, naive pre-alloc, decode step 50
Allocate in fixed pages, only on demand
A Rust allocator holds a free-list of 0.59 MB pages, 16 tokens each, and a per-sequence block table. A sequence claims a page only when it actually needs one, and returns every page the moment it finishes.
0.59 MB / page
16 tokens, allocated on demand, returned on free()
8x less VRAM for the identical workload
At decode step 50, the same 32 GPT-2 sequences that cost 603.98 MB under naive pre-allocation cost 75.50 MB paged, freeing the rest of a fixed pool for other requests to use.
75.50 MB
8x less, same 32 sequences, same decode step
Four layers, one pointer moving through all of them.
A page ID travels from Python, through a Rust allocator, into a CUDA gather kernel, and back, addressing GPU memory the same way an OS page table addresses RAM.
one call: model(prompt_ids, past_key_values=PagedKVCache(...), use_cache=True)
Subclasses HuggingFace's own DynamicCache, so transformers generation code calls it exactly the way it already calls any other cache: model(..., past_key_values=cache, use_cache=True).
A free-list VecDeque<u32> and a BlockTable HashMap<seq_id, Vec<page_id>>, unified behind one PageForge struct exposed to Python. alloc_for_seq and free_seq are both O(1).
CuPy RawKernel (NVRTC), not a compiled PyTorch C++ extension. gather_kv assembles scattered pages into a contiguous attention buffer; scatter_kv_layer writes new tokens back.
Shape (N_pages, page_size, n_layers x n_heads, d_head), K and V combined so every transformer layer shares one pool tensor instead of one tensor per layer.
1// pageforge-rs: the O(1) allocator PyO3 exposes to Python2pub struct PageAllocator { free_list: VecDeque<u32>, total: usize }3impl PageAllocator {4 pub fn alloc(&mut self, n: usize) -> PyResult<Vec<u32>> // O(1)5 pub fn free(&mut self, ids: Vec<u32>) // O(n)6 pub fn free_pages(&self) -> usize7}8 9// per-sequence page ownership10pub struct BlockTable { table: HashMap<u64, Vec<u32>> }11impl BlockTable {12 pub fn append(&mut self, seq_id: u64, page_ids: Vec<u32>)13 pub fn evict(&mut self, seq_id: u64) -> Option<Vec<u32>>14}Five techniques, one of them doing most of the work.
Page-table-style indirection borrowed from operating systems, applied to GPU memory: every technique here exists to move less data, or to move it less often.
- 01
Page-table-style indirection
Physical pages are allocated non-contiguously and addressed through a per-sequence block table, the same idea an OS uses to map virtual memory to physical memory.
- 02
O(1) free-list allocation
A VecDeque free-list means both claiming a page and returning one are O(1), independent of pool size or fragmentation history.
- 03
Gather / scatter kernels
Every decode step gathers a sequence's scattered pages into a contiguous view for attention, then scatters the new K/V back into the right physical pages.
- 04
Layer-combined pooling
Every transformer layer's heads are stacked into one pool tensor instead of one tensor per layer, so a single gather call reads every layer's K (or V) at once.
- 05
DLPack zero-copy bridge
Tensors move between PyTorch and CuPy through the open DLPack protocol: no host round-trip, no intermediate buffer, on every decode step.
Layer-combined pooling cut gather calls by 12x
gather calls / decode step
GPT-2 has 12 layers. A naive per-layer pool needs one K gather and one V gather per layer, 24 calls, every decode step. Stacking all layers into one tensor collapses that to 2.
Real numbers, measured on one real GPU.
GPT-2 124M, fp16, RTX 4070 Laptop, sm_89. Every figure below is recomputed directly from the project's own stated constants, not copied blind.
Kernel bandwidth, gather / scatter
measured on sm_89, peak bandwidth ~250 GB/s
Peak bandwidth utilisation
227 of ~250 GB/s, purely memory-bound, no arithmetic bottleneck
Allocator throughput
500 alloc/free cycles, 16 seqs/cycle, 0 leaks, 0 OOM
Pool recovery after every batch
pages free after free(), zero fragmentation, verified across 2 consecutive batches
hover to inspect any decode step
8.0x
savings at step 50
The savings multiplier is highest early and shrinks as sequences grow, 32x at step 5, 8x at step 50, 2.3x by step 200, because the naive line never moves while the paged curve grows only with real tokens generated. The full, honestly-degrading curve, not one cherry-picked number.
The advantage is largest for short, bursty workloads (32x at step 5) and converges toward parity as sequences approach the naive budget (1.0x at step 500). An honest degrading curve, not a single best case.
P50, median latency
P99, tail latency
P50 overhead
+33%
P99 overhead
+16%
Bottleneck: 24 scatter kernel dispatches plus 24 torch.cat calls per decode step, one pair per transformer layer. A fused scatter-attention kernel would eliminate the per-layer Python round-trip: a documented, not-yet-shipped roadmap item.
Does the pool actually come back to zero?
A single chart and two raw benchmark plots, not a claim taken on faith: run two batches back to back and check whether the second one gets the first one's pages back.
Naive VRAM (8 seqs)
151 MB
PageForge peak, batch 1
14.16 MB
% of naive budget
9.4%
Pages after free()
0
Batch 2's curve traces the same shape as batch 1's, shifted only in time, because it claims the exact physical pages batch 1 returned. The pool ends every cycle back at 0 pages used: no leaks, no growth.
VRAM efficiency: paged vs. naive, 32 concurrent sequences
Real matplotlib output, not a mockup: the naive baseline holds flat at 603.98 MB while the paged curve grows only with real tokens generated, still under half the naive budget at decode step 200.
Multi-sequence lifecycle: batch 1 vs. batch 2
Two independent batches of 8 sequences, run back to back. Batch 2's utilisation and VRAM curves sit exactly on top of batch 1's, the visual proof that freed pages are reused with zero fragmentation.
Memory efficiency
VRAM per sequence, at prompt
Naive static
18.87 MB
PageForge
0.59 MB
Delta
32x less
VRAM per sequence, decode step 50
Naive static
18.87 MB
PageForge
2.36 MB
Delta
8x less
Max concurrent sequences, 512-page pool
Naive static
16
PageForge
128 to 512
Delta
8x to 32x
Sequences served per GB, step 50
Naive static
53
PageForge
424
Delta
8x
Memory fragmentation
Naive static
zero
PageForge
zero
Delta
parity
Naive pre-allocates max_seq_len=512 tokens per sequence at start, regardless of actual generation length.
Decode latency
Decode P50 latency
HF DynamicCache
7.5 ms
PageForge
10.0 ms
Delta
+33%
Decode P99 tail latency
HF DynamicCache
10.3 ms
PageForge
11.9 ms
Delta
+16%
KV tensor layout
HF DynamicCache
contiguous
PageForge
paged
Delta
structural
Scatter overhead per step
HF DynamicCache
none
PageForge
24 ops
Delta
~2.5 ms
HF DynamicCache grows KV tensors with torch.cat each step. PageForge scatter-copies into non-contiguous pages instead, trading per-step speed for capacity.
What was chosen, and what it cost.
Five choices the repository actually supports, each with the alternative it gave up and the outcome it produced.
torch.utils.cpp_extension, the standard way to write custom CUDA ops for PyTorch, would not build under MSVC 14.41 + PyTorch 2.11 on the Windows development machine.
ReasoningCuPy's RawKernel compiles CUDA C at runtime via NVRTC, with no host C++ compiler in the loop, so kernel development stayed unblocked without switching platforms.
All four CUDA kernels ship as CuPy RawKernels, measured at 157 to 227 GB/s on sm_89, zero MSVC dependency anywhere in the stack.
The project this repository used to be, until it wasn't.
Two failures, verified against real git history rather than a retrospective paragraph: one that decided the whole problem, one that decided the whole build toolchain.
A genetic-programming engine's own ablation study caught it gaming the proxy, and that is why PageForge exists
SymboLR, a Rust and PyO3 genetic-programming engine using MAP-Elites search to evolve learning-rate schedules of the form lr = f(t, g, dl), scored well on its synthetic training proxy after 50-plus commits and 107 passing tests. A dedicated Phase 6 ablation study, a TokenFilteredEvaluator comparing t-only vs t+g vs t+g+dl terminal sets, showed why: the proxy tasks were easy enough that nearly any learning rate in a wide range converged fine, so evolution simply selected for aggressive, fast-converging formulas that did not generalize to real training runs.
Rather than keep patching the evaluation setup, the project pivoted to a problem with a ground-truth, hardware-measurable success criterion: does a KV-cache implementation use less VRAM and serve more sequences, measured directly on a GPU, no proxy in between. Same stack, Rust, CUDA, PyTorch, PyO3, a problem chosen specifically because its evaluation cannot be gamed the way SymboLR's was.
The standard PyTorch CUDA-extension path would not build on the development machine
torch.utils.cpp_extension, PyTorch's documented way to write custom CUDA ops, failed to compile under MSVC 14.41 + PyTorch 2.11 on Windows: the textbook tool was simply unavailable without a toolchain change.
Every kernel was routed through CuPy's RawKernel (NVRTC) instead, which compiles CUDA C at runtime independent of any C++ host compiler. All four kernels ship this way, measured at 157 to 227 GB/s with zero MSVC dependency anywhere in the build.
What this case study can't verify.
- -The Rust allocator, the CUDA kernel source, and the Python pool/cache/bridge modules are not tracked in this repository; the README says so directly, and this case study is built only from what is actually here: the CLI, the dashboard's data file, and two raw benchmark plots.
- -The repository reports two different, mutually inconsistent test counts: 56 Python plus 6 Rust (62 total) in the README's own table, versus a dashboard stat that reads 75 passing but whose own category breakdown only sums to 74. Neither is independently verifiable from this repository, so no specific test count is claimed here.
- -Page size (16 tokens) and pool size (512 pages) are reasoned from the mechanism, not swept experimentally; the CLI exposes both as free parameters, but no benchmark in the repository varies them.
- -Every number here is scoped to one GPU and one model, GPT-2 124M on an RTX 4070 Laptop, Ada Lovelace, sm_89; nothing claims to generalize to larger models or datacenter GPUs.
- -The +33% P50 / +16% P99 latency overhead against HF DynamicCache is a known, open cost. A fused scatter-attention kernel to close it is a documented next step, not yet shipped.
A proxy is only as good as its resistance to being gamed.
- A proxy evaluation is only trustworthy if it resists being gamed. SymboLR's own ablation study catching exactly that is the direct reason PageForge exists, and why it chose a hardware-measurable success criterion instead of another proxy.
- Reporting the number that does not favor you builds more credibility than omitting it: the +33% latency overhead sits next to the 8x VRAM win, with its root cause named rather than smoothed over.
- A platform limitation is a legitimate design input, not just an obstacle to route around quietly. The MSVC build failure became a documented, load-bearing reason to use CuPy RawKernel rather than an invisible workaround.
- A correctness claim underwrites a performance claim, not the other way around: VRAM savings only mean something once the cache is shown to produce the same outputs as the one it replaces.
One free-list allocator, hand-written gather and scatter kernels, benchmarked against the cache it would have to replace.