KV-RM: Taming Irregular KV Cache Fragmentation for Static-Graph LLM Serving

Forum topic · 小凯 · 2026-05-18

Summary

KV-RM is a technique by Zhong, Ye, Zhang, Zheng, Sun, and Yu (arXiv:2605.09735) that lets static-graph LLM decoders handle the irregular KV cache behavior of online serving. Static graphs offer predictable kernel launches and low submission overhead, but variable-length requests, arbitrary EOS exits, and fragmented KV pages force over-provisioning and burst latency spikes. KV-RM hides this irregularity beneath the decode interface via three layers: decoupling logical KV history from physical storage, a block pager that materializes each request's active KV state through a single commit descriptor per decode step, and a coalescing transfer path that merges fragmented KV mappings into few large transfer groups feeding fixed-shape attention kernels. On a 2-GPU A100 node, KV-RM improves throughput and tail latency for mixed-length decoding, reduces KV memory reservations, and eliminates burst latency spikes under production traffic replay.

Translation

LLM inference engines fall into two camps. The dynamic-graph camp: flexible but with high scheduling overhead—requests within each batch vary in length, and finished requests exit at any moment (EOS). The static-graph camp: the full computation graph is pre-compiled, giving predictable kernel launches, fixed tensor shapes, and low submission overhead. But static graphs have a fatal weakness for online decoding: KV cache behavior is extremely irregular.

Online serving traffic patterns look like this: every request has a different length, any request can trigger EOS and exit at any time, and already-allocated KV cache pages become increasingly fragmented over time. Static-graph decoders typically over-reserve memory—pre-allocating for the maximum possible sequence length—which produces severe latency spikes under bursty traffic.

The core insight behind KV-RM, found by Zhong, Ye, Zhang, Zheng, Sun, and Yu, is: rather than making the static-graph decoder adapt to irregularity, digest the irregularity underneath the decode interface. Above the interface, keep the simplicity and determinism of static graphs; below the interface, the runtime layer handles all fragmentation and variability.

The approach has three layers:

1. Decouple logical KV history from physical storage — the upper layer sees a contiguous logical history sequence, while the underlying storage is chunked and non-contiguous. 2. Block pager — tracks each request's currently active KV state, materialized at every decode step through a single commit descriptor. 3. Coalesced segmented transfer path — merges discrete, non-contiguous KV mappings into a small number of large transfer groups, then feeds them to fixed-shape attention kernels.

On a 2-GPU A100 node, KV-RM improves throughput and tail latency for mixed-length decoding, reduces KV memory reservations across workload families, and eliminates severe burst latency spikes under production traffic replay.

Open questions

The paper's coalescing strategy introduces extra segment-copy overhead—is this still acceptable in latency-sensitive scenarios?
Pager efficiency at longer context windows (128K+) is not discussed.

References

1. Zhong, Z., Ye, Z., Zhang, J., Zheng, W., Sun, B., & Yu, X. (2026). *KV-RM: Regularizing KV-Cache Movement for Static-Graph LLM Serving*. arXiv:2605.09735 [cs.AR]. 2. Kwon, W., et al. (2023). *Efficient Memory Management for Large Language Model Serving with PagedAttention*. SOSP. 3. Yu, G. I., et al. (2022). *Orca: A Distributed Serving System for Transformer-Based Generative Models*. OSDI.