Feather: Optimizing Prefix Homogeneity via Reinforcement Learning to Achieve 2-10x LLM Inference Throughput Improvement

Feather is a prefix-aware scheduler whose core uses reinforcement learning to find the optimal trade-off between batch size and prefix homogeneity, and introduces a Chunked Hash Tree (CHT) for fast prefix detection. In integration tests with vLLM and SGLang, Feather achieves a 2-10x throughput improvement, and its performance is not inferior to existing solutions in scenarios without prefix sharing.

Memory Bottlenecks in LLM Inference

Autoregressive generation of large language models relies on KV caching. As sequence length increases, memory access overhead grows linearly, and the decoding phase is a memory-bound operation. The mainstream optimization in the industry is batching, but it ignores the prefix sharing phenomenon in real workloads.

Problems with Existing Schedulers

1. Suboptimal batch formation: Pursues maximum batch size instead of efficient combinations;
2. Expensive prefix detection: Relies on radix tree traversal, with CPU overhead comparable to GPU execution time.

Innovation 1: Reinforcement Learning for Optimal Trade-off

• State Representation: Observes prefix features, sequence lengths, waiting times, etc., of the pending request queue;
• Action Space: Decides request grouping strategies (prioritize batch size/homogeneity/balance point);
• Reward Design: Integrates objectives such as throughput, latency, and fairness;
• Online Learning: Adaptive adjustment without manual parameter tuning.

Innovation 2: Chunked Hash Tree (CHT)

• Fast prefix detection: Uses hashing instead of tree traversal, reducing complexity from O(sequence length) to O(1);
• Efficient request selection: Quickly filters candidate sets with the same prefix;
• Low maintenance overhead: Insertion/deletion operations are efficient and adapt to high-concurrency scenarios.

1. End-to-end Throughput: 2-10x improvement over prefix-aware baselines, changing the cost structure of LLM inference services;
2. Robustness: Performance is not inferior to current solutions when there is insufficient prefix sharing;
3. Beyond Kernel Optimization: Benefits come from reducing the total number of KV cache accesses, complementing underlying kernel optimization.

• Workload Characteristics: Depends on the degree of prefix sharing; significant benefits in templated query/system prompt scenarios;
• Latency Sensitivity: CHT overhead is small, but extreme scenarios need evaluation;
• Integration Adaptation: Already supports vLLM/SGLang; other engines require additional adaptation;
• Hardware Resources: RL decision-making requires a small amount of CPU resources, which is controlled within an acceptable range by CHT.

• Dynamic Environment Adaptation: RL online learning handles workload changes;
• Multi-objective Optimization: Balances conflicting objectives like throughput and latency;
• Exploration-Exploitation Balance: Automatically avoids local optima;
• Interpretability: Understands decision logic through behavioral pattern analysis.

• Limitations: Simple workload modeling; only supports single-GPU scheduling; not combined with speculative decoding; fixed learning rate for RL training;
• Future Directions: Fine-grained user behavior modeling, multi-GPU expansion, integration with speculative decoding, adaptive learning rate optimization.

Feather reveals a system design principle: When optimizing complex systems, 'smarter' is more important than 'bigger'. By using RL to balance batch size and homogeneity, it achieves efficiency improvements far beyond traditional batching, providing practical value for LLM inference services and inspiration for similar scheduling problems. As the scale of AI services expands, intelligent scheduling will become a core part of infrastructure.