Fairway improves scheduling to speed up large language model responses

Fairway: Load-Aware KV Cache Reuse for LLM Prefill Scheduling

Distributed, Parallel, and Cluster Computing

Summary

Large language models often build responses using parts of previous computations stored in a cache called the key-value (KV) cache. When multiple requests share similar starting points, the system can reuse this cache to work faster. The authors found that prioritizing requests with larger cache reuse reduces wait times for many but can delay more complex requests. They created Fairway, a smart scheduler that balances quick responses and fairness, helping all requests get served faster during busy times.

What this means in practice

  • For llm platform engineers: Optimize request handling to reduce response delays by balancing cache reuse and fair scheduling under varied load conditions.
  • For cloud service operators: Improve user experience for AI-driven applications during traffic spikes by managing server queues to lower slowest response times.

Authors

Hamidreza Alikhani, Nazmul Takbir, Matin Khajavi, Rajat Bhattacharjya, Sangeetha Abdu Jyothi, Nikil Dutt

Abstract

LLM-based applications often employ agentic workflows and retrieval-augmented generation (RAG), which build long prompts from shared context. When prefixes are shared across requests, serving engines reuse the key-value (KV) cache to skip parts of the prefill computation. Reuse is typically graded: the uncached work of requests in a queue can differ by up to 100x. In this setting, the order of scheduling determines the time-to-first-token (TTFT) for the queued requests. KV reuse-first scheduling, which prioritizes the requests with the longest KV cache hit, gives the lowest median TTFT but starves expensive requests under load spikes; first-come-first-served (FCFS) scheduling bounds the tail but raises the median TTFT. We present Fairway, a prefill scheduler built on adaptive reuse prioritization: it favors KV cache reuse while queues are short, and shifts toward fair allocation as requests wait longer relative to their own prefill time. Fairway employs a virtual dual lane model: a KV reuse-first Fast lane and a Fair lane atop the serving engine's waiting queue that enables speeding up of cheap reuse requests without starving expensive ones. This model automatically adapts to the workload without any per-workload tuning. Fairway lowers the tail TTFT at no cost to the median in transient overload. Across workloads and load levels, Fairway matches or beats the best baseline, with a p99 TTFT up to 8.6x lower than prior prefix-aware schedulers. During load spikes, it keeps the tail of FCFS at a 6x lower median TTFT.