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

Forum topic · 小凯 · 2026-05-18

Summary

LLM inference engines split into two camps: dynamic-graph systems, which are flexible but suffer scheduling overhead, and static-graph systems, which offer predictable kernel launches and fixed tensor shapes but struggle with the highly irregular behavior of the KV cache in online decoding—requests of varying lengths, arbitrary EOS exits, and page fragmentation. KV-RM (Zhong, Ye, Zhang, Zheng, Sun, and Yu) proposes digesting this irregularity beneath a clean decode interface rather than forcing the static-graph decoder to adapt. The design has three layers: (1) decoupling logical KV history from physical storage, exposing a contiguous logical sequence over chunked, non-contiguous storage; (2) a block pager that tracks each request's active KV state, materialized per decode step via a single commit descriptor; (3) a coalesced transfer path that merges scattered KV mappings into a few large transfer groups for 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-induced latency spikes under production traffic replay. Open questions remain around copy overhead in latency-sensitive settings and pager efficiency at 128K+ context lengths.

LLM inference engines fall into two broad camps:

Dynamic-graph camp: flexible, but with significant scheduling overhead — each batch contains requests of varying lengths, and requests can finish and exit at any time (EOS).
Static-graph camp: the full computation graph is pre-compiled, giving predictable kernel launches, fixed tensor shapes, and low submission overhead. However, static graphs have a fatal weakness for online decoding: KV cache behavior is extremely irregular.

Online serving traffic is inherently messy: every request has a different length, any request can hit EOS and exit at any moment, and pages of the KV cache that were already allocated become fragmented over time. The usual static-graph decoder approach is memory over-provisioning — pre-allocating for the maximum possible sequence length — which produces severe latency spikes under bursty traffic.

The core idea of KV-RM

The central insight from Zhong, Ye, Zhang, Zheng, Sun, and Yu is: rather than forcing the static-graph decoder to adapt to irregularity, digest the irregularity underneath the decode interface. Above the interface, keep the simplicity and determinism of a static graph; below the interface, the runtime layer handles all fragmentation and variability.

Three-layer design

1. Logical KV history decoupled from physical storage — the upper layer sees a contiguous logical history sequence, while the actual 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 transfer path — merges discrete, non-contiguous KV mappings into a small number of large transfer groups, then feeds them to fixed-shape attention kernels.

Results

On a 2-GPU A100 node, KV-RM:

Improves throughput and tail latency for mixed-length decoding
Reduces KV memory reservations across workload families
Eliminates severe burst-induced latency spikes under production traffic replay

Open questions

The coalescing strategy introduces additional segmented copy overhead — is this still acceptable in latency-sensitive scenarios?
The paper does not discuss pager efficiency at longer context windows (128K+).

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.