Measured: scattered-token KV eviction frees zero pages under paged allocation

[athanase-matabaro]

Sharing a measurement that may be relevant to RadixAttention and cache
management here.

Under honest paged accounting (a page returns memory only when fully empty),
scattered-token KV eviction of the H2O family frees zero pages across the
entire operational range of memory ceilings I tested (0.60 to 0.25 of FP16
footprint) on Llama-3.2-1B. Real held memory stays at 100%. Eviction on
contiguous 16-token windows, aligned to the default page size, converts
exactly instead.

Results, protocol and limitations: https://athanase-matabaro.github.io/kivu-site/
DOI: https://doi.org/10.5281/zenodo.21527757

Caveats stated up front: accounting simulator rather than a real engine, and
the allocation mechanism is proprietary. I am looking for a partner with GPU
access to validate the page accounting inside an actual serving stack.

[rehan243]

so i actually dealt with this when i was messing with kv cache eviction for a custom llama v2 inference server. not gonna lie, the scattered-token eviction sounded clever at first, but in practice with paged allocators (i used both cudaMallocAsync and a hacked-together slab allocator), i saw the exact thing you measured: physical memory never drops unless the whole page empties. the allocator just marks freed tokens, but the OS doesn't touch the actual GPU memory unless all the slots in a page go unused.

for contiguous windows, memory gets freed reliably, guess the alignment lets the allocator reclaim those pages. i tried something like:

# Evicting a full window aligned to 16 tokens
evict_window(start=page_start, length=16)

and that worked, but scattered evicts just left the memory hanging. i even dumped stats from nvidia-smi, nothing moved.

honestly, i started thinking about bitmaps for page occupancy and tried grouping token eviction by page index, but it got messy and added latency. radix-style attention could maybe batch up evicts, but haven't found a clean solution.

are you planning to test with real GPU allocators like Triton or FasterTransformer? i'd be super curious if their page accounting differs.

[athanase-matabaro]

This is genuinely the best response I could have hoped for, because it's independent confirmation on real hardware. I measured this in an accounting simulator; you just told me you saw the identical behavior on nvidia-smi with real GPU memory. That closes a gap I couldn't close myself.

To your question directly: no, I haven't tested against Triton or FasterTransformer, and I don't have GPU access at all right now, everything I've published was built and measured on a CPU-only laptop. That's exactly the wall I'm at. Whether the page accounting differs across allocators is precisely the kind of question I can't answer alone.

Your bitmap-by-page-index idea is close to what my page-aligned decision does, except mine decides before eviction which pages are worth freeing, rather than tracking occupancy after the fact and untangling it later. That ordering is probably why yours got messy: deciding post-hoc means you're fighting fragmentation you already created.

Given you've already got a working eviction path and real allocator experience, would you be open to a short call? I'd like to see whether the page-alignment result holds up against a real cudaMallocAsync allocator, not just my simulator's model of one. Happy to work around your schedule, and there's no pressure either way if this isn't something you have time for.