Flow Control Scheduling Framework: Providing Provable Stability Guarantees for LLM Inference

This paper proposes a flow control scheduling framework to address memory growth and system instability issues in LLM inference caused by unknown decoding lengths. The core of the framework is to control the rate at which prompts enter the active set, drawing on network flow control ideas; through theoretical derivation, it obtains necessary conditions for a stable system and sufficient conditions for the algorithm, providing provable stability guarantees. Experiments show that this method outperforms common strategies in throughput, latency, and KV cache stability, and is of great value for the reliable and efficient operation of large-scale LLM services.

LLM inference is directly related to user experience and operational costs, but its generation process has the characteristic of unknown decoding length, leading to complex memory management. The pre-filling phase computes KV caches, and the decoding phase generates tokens autoregressively—memory usage grows linearly with the number of tokens. When handling multiple requests simultaneously, overly long sequences easily exhaust KV caches and cause memory overflow, leading to system instability issues such as latency spikes and service interruptions.

The core of the flow control framework is to regulate the access rate of new requests based on system status, drawing on network flow control mechanisms to monitor KV cache usage. Theoretical analysis derives necessary conditions for a stable system (revealing the relationship between request arrival patterns and service capacity) and sufficient conditions for the algorithm's stability (mathematically ensuring the system does not fall into instability). It also reveals the trade-off between flow control and performance, providing guidance for optimal strategies.

Compared with common strategies in experiments, the flow control framework shows significant improvements in multiple metrics: 1. Throughput: Both token and request throughput are increased due to avoiding overload and improving resource utilization; 2. Latency: Average latency is reduced, and tail latency is significantly decreased (suppressing extreme latency); 3. KV Cache: Usage fluctuations are greatly smoothed, maintaining a stable level and improving resource predictability.

The framework design considers actual deployment needs—its algorithm logic is concise, implementation overhead is low, and it is easy to integrate into existing inference services. Parameter configuration is highly interpretable; engineers can adjust thresholds according to memory capacity and load characteristics, and the theoretical sufficient conditions provide a safety boundary, reducing the cost of parameter tuning and trial-and-error.

The flow control framework is complementary to technologies such as continuous batching, dynamic batching (improving GPU utilization), and paged attention (memory optimization). Future expansion directions include: implementing adaptive flow control combined with load prediction, adapting to heterogeneous hardware, and exploring applications in distributed inference scenarios.