kv-cache-sim: A Discrete Event Simulator for LLM Inference Services

kv-cache-sim is a discrete event simulator for LLM inference services, focusing on the research and optimization of PagedAttention memory management and continuous batching techniques. It aims to address the challenge of balancing latency, throughput, and resource utilization in inference, providing researchers and engineers with a low-cost, repeatable, flexible, and highly visible experimental environment.

Large language model inference services need to strike a fine balance between latency, throughput, and resource utilization. KV cache management is a core issue: in Transformer autoregressive generation, key-value pairs of previous tokens need to be cached to avoid redundant computations, but the cache size easily becomes a memory bottleneck as sequence length and concurrent requests grow. vLLM's PagedAttention technology improves memory efficiency, and kv-cache-sim provides a simulation tool to support related research and optimization.

Discrete event simulation has four advantages over real hardware experiments: 1. Cost-effectiveness: Ordinary computing resources can quickly run a large number of scenarios; 2. Repeatability: A deterministic environment ensures consistent output for the same input, which is beneficial for algorithm comparison and regression testing; 3. Flexibility: Easily configure parameters such as request arrival rate and sequence length distribution; 4. Visibility: Expose internal metrics that are hard to obtain in real systems, such as queue length and memory fragmentation rate.

PagedAttention draws on the idea of virtual memory in operating systems, dividing the KV cache into fixed-size blocks (pages) and dynamically allocating and reclaiming them on demand. When a request generates a new token, a new block is allocated; when it completes, the block is reclaimed and reused, significantly reducing memory fragmentation and allowing more concurrent requests. The simulator can implement its core logic and analyze the impact of different block sizes and allocation strategies on performance.

Continuous batching solves the first-token latency problem of traditional static batching by dynamically adding new requests to running batches or removing completed ones. It needs to address: attention computation efficiency for sequences of different lengths, dynamic KV cache management, and minimizing the impact of adding new requests on computation. The simulator can explore the performance of scheduling strategies such as first-come-first-served and shortest job first in terms of latency, throughput, and fairness.

kv-cache-sim is applicable to multiple scenarios: 1. Algorithm researchers: Quickly verify new ideas for PagedAttention and continuous batching variants without modifying production code; 2. System engineers: Capacity planning, predicting GPU resource requirements under different loads, and assisting in hardware decisions; 3. Operation and maintenance teams: Fault scenario analysis, studying system behavior and the effect of degradation strategies when there are request bursts or node failures.

Implementing an accurate simulator requires modeling multiple components: 1. Request model: Define request arrival processes (e.g., Poisson process), service time distribution (related to input and output lengths), and priority/SLA requirements; 2. Memory model: Simulate KV cache usage, PagedAttention block management overhead, and GPU memory hierarchy (HBM vs DRAM); 3. Computation model: Model attention computation and feed-forward network execution time, considering batch processing efficiency improvements and the impact of memory bandwidth bottlenecks.

kv-cache-sim provides an important tool for the research and optimization of LLM inference services. Through discrete event simulation, it explores the optimization space of key technologies such as PagedAttention and continuous batching in a low-cost, highly controllable environment. As the scale of LLM applications expands, such simulation tools will play an increasingly important role in system design and capacity planning.