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

Prefill queueing under a prefix cache can keep both the median latency low and the tail short. While the queue is short, serve cheap requests with long cache hits first; move a request forward the longer it has waited relative to its own prefill time; and cap how much work cheap requests may place ahead of the oldest request. This is what Fairway does, as a hook in the vLLM scheduler. Agent and RAG requests often share a prefix and the cached part needs no recomputation, so the remaining work of requests in one queue can differ by about 100 times, and the serving order decides how long each request waits for its first token. In the 60-second traffic spikes of two dynamic traces of SEC (U.S. Securities and Exchange Commission) filing Q&A, Fairway's median time to first token is 0.82 seconds on both, with a p99 of 7.6 and 8.4 seconds, close to first-come-first-served; first-come-first-served lets the median rise to 5.1 to 5.9 seconds, and hit-leaning orderings such as LPM (longest prefix match) and RAGCache let the p99 reach 11 to 50 seconds.

What problem is it actually solving?

Take an illustrative case. A financial QA service puts a few retrieved report excerpts plus the user's question into every prompt. Excerpts from popular reports are mostly already in the KV cache, while those from rarely read reports must be computed from scratch. So the requests waiting at the same moment have very different amounts of work left:

The paper measured this in Mooncake's real agent traces: most requests are only partly cached, and the work left differs by about 100 times within one queue.

There are two standard orderings, each with one flaw. The first serves requests with long cache hits first, as SGLang's longest prefix match (LPM, the request with the longest cached prefix runs first) does. H1 and H2 finish fast and the median latency is lowest. But if popular requests keep coming, M never gets served. The second is first-come-first-served, the vLLM default. M is never starved, but H1 and H2, which need only 300 tokens each, must wait for M's 6,000, and the median rises.

Existing compromises add fairness to hit-first ordering, but they measure fairness in the wrong unit. Some count turns, for example letting the oldest request run once every few turns, yet one turn may be tens of tokens or thousands. Others add priority per second of absolute wait, yet two seconds of waiting is 20 times the prefill of a request that needs 0.1 seconds and less than one prefill of a request that needs 3 seconds. Fairness should be measured against each request's own work, not in turns or seconds, and this is the starting point of the paper.

Overall design: one queue, two orderings, taken in turns by work

Fairway is a hook in the vLLM scheduler. Before each scheduling step it reorders the waiting queue, and the engine first continues running requests, then admits waiting ones in that order within the step's remaining token budget (2,048 per step in the experiments, vLLM's default on a 48 GB GPU). The reordering has three parts:

Both lanes are virtual: they order the same requests in two different ways. The Fast lane lets cheap cache hits go first, and the Fair lane protects the oldest request. The parts are explained below.

How does the Fast lane score requests?

The Fast lane gives each request a score, and higher scores go first. The score is the sum of two terms:
$$s_r=\frac{h_r}{c_r}+\frac{{wait}_r}{{SLO}_r}$$
The first term is the reuse ratio. $h_r$ is the request's cached prefix length and $c_r$ is the number of tokens it still has to compute, so the ratio says how many tokens are saved per token computed. $c_r$ counts as at least 1: a full hit usually still computes its question, tens of tokens, and the floor of 1 just avoids division by zero if none is left. In the illustrative table, H1's reuse ratio is 6,000 divided by 300, which is 20, and M's is 0. Why not just rank by cached length? When two requests have the same cached prefix, the ratio puts the one with less work first. Ranking by cached length alone can let a long partial hit jump ahead of a cheap full hit and slow everyone behind it. Hoot says▾

Hoot saysSame cache, so why can the order still change?Close ✕

Reuse ratio is saved work ÷ work left; relative wait is time waited ÷ own patience: with equal cache, the one with less left to compute goes first; with equal waits, the one with shorter patience is pulled forward.

Cached length only

A's score

6,000

B's score

6,000

Result

a tie, B may go first

B computes 3,000 tokens and everyone behind it waits longer.

First term: reuse ratio h ÷ c

A

6,000 ÷ 300 = 20

B

6,000 ÷ 3,000 = 2

Result

A goes first

With equal cache, less remaining work ranks higher.

Second term: wait ÷ patience, both waited 2 s

Short request, patience 1 s

2 ÷ 1 = 2

Long request, patience ≈4 s

2 ÷ 4 = 0.5

Result

the short one is pulled forward

This term is small when the queue is short and matters once a queue builds.

Illustrative numbers: requests A and B each have 6,000 cached tokens; A has 300 left to compute and B has 3,000. The waiting column reuses the text's example, with both requests having waited 2 seconds. Source: paper method section, Fast-lane score s = h/c + wait/SLO; numbers are illustrative, 6,000 and 300 reuse the text's example table.

The second term is the relative wait. ${wait}_r$ is how long the request has waited, and ${SLO}_r$ is its patience (only a number the scheduler uses, not an evaluation target): the expected prefill time on an idle GPU, times 3, and never less than 1 second. The expected time is estimated from the full prompt length, using a table measured once per GPU type with a short profiling run. It deliberately uses the full length rather than the remaining work: the full length is fixed for a request, while the remaining work changes with the cache and already enters the reuse ratio in the first term. Once a request has waited for its full patience, this term reaches 1 and the request becomes urgent. For requests whose prefill takes more than a third of a second, the patience is exactly three times their prefill time.

Why divide by its own patience? Serving a short request first delays others a little, while serving a long one first delays them a lot. Again illustratively: a short request has a patience of 1 second and a long one about 4 seconds; after both wait 2 seconds, the short request's second term is 2 and the long one's only 0.5, so the short request moves up first. When the queue is short, everyone waits a fraction of a second, the second term is small, and the order follows the reuse ratio. When a queue builds, the second term grows and long-waiting requests move forward, with no mode switch.

Why a multiplier of 3? The authors set it from GPU profiling: with 3, and ignoring the 1-second floor, a miss that has waited three times its own prefill time scores the same as a newly arrived request with half its prompt cached, both at 1. A smaller multiplier pushes the order toward first-come-first-served, and a larger one toward hit-first.

Why is a Fair lane still needed?

The relative wait alone still fails in one case: many highly cached requests arriving together. Every newcomer has a high reuse ratio and still outscores misses that have waited a long time. So Fairway adds a second lane ordered purely by arrival time, oldest first.

The two lanes are merged by work accounting, which the paper calls work charges. Each lane keeps a ledger. The ledger starts with the work of the request at the front of that lane, and each time the lane places a request, that request's work is added; all Fast-lane work is counted four times. The lane with the smaller ledger places the next request. Both lanes order the same requests, so once one lane has placed a request, the other skips it. The ledgers reset at every scheduling step.

The example in the figure can be worked by hand. The Fast lane's ledger starts at 300 times 4, which is 1,200, and the Fair lane's starts at M's 6,000. The Fast lane is smaller, so it places H1 and its ledger rises to 2,400. It then places H2, H3 and H4, reaching 6,000. On a tie the Fast lane still goes, so it places H5 and reaches 7,200. Now the Fair lane is smaller and places M. Five hits go first, with only 1,500 tokens in total, exactly a quarter of M's own work. In general, the work placed ahead of the oldest request is at most a quarter of its own plus the overshoot of one request; in the example all hits are the same size, so it is exactly a quarter. However many hits are waiting, the work that can jump ahead of the oldest request is limited.

How is the order executed? The engine processes at most 2,048 tokens per step, and a request that does not fit can be split into chunks. In the figure, this step runs the 1,500 tokens of the five hits and then the first 548 tokens of M; M is now running and continues first in the following steps.

Experiments: how does it hold up in spikes and floods?

The experiments run Llama-3.1-8B on vLLM on one A6000, acting as the prefill node of a disaggregated deployment. Each request generates only one token, so the measured time is queueing plus prefill. The KV cache holds only a quarter to a third of the reusable content in each trace, so eviction is frequent. Workloads include QA over quarterly filings published by the SEC (the US Securities and Exchange Commission), MuSiQue multi-hop QA, and Mooncake's real agent traces. The authors tuned the three parameters (Fast-lane weight 4, patience multiplier 3, patience floor 1 second) on SEC traces drawn with one random seed, froze them, and reused them unchanged on a new seed, MuSiQue and Mooncake.

The first experiment changes the load: a calm period, a burst, then a 60-second spike beyond capacity. Among the baselines, RAGCache ranks by reuse ratio; Preble groups requests by cache ratio and lets the groups take turns; PEEK (a cache-aware scheduler) ranks by the prefill its cache saves and protects the cache blocks waiting requests need from eviction. Below is time to first token inside the spike window on two dynamic SEC traces, from Section 5.2 of the paper:

This shows Fairway gets the strength of both orderings at once: a median like hit-first and a tail like first-come-first-served. The authors set two targets for each of the calm, burst and spike phases: a median at most 10% above LPM's and a p99 at most 10% above first-come-first-served's, so each trace has six targets. Fairway meets all six on both traces, and no baseline meets more than four.

The second experiment compares p99 across 11 scenarios. The best baseline changes from case to case: first-come-first-served wins 4, k-LPM letting the oldest request run once every 4 turns wins 4, and once every 8 turns wins 3. In 10 scenarios, Fairway's p99 is 2% to 18% lower than the best of the baselines that do not starve requests (starving is the paper's evaluation criterion: a worst TTFT above 3 times the scheduler's own p99), and it ties in the eleventh. This means one setting is enough, with no need to pick an ordering per workload.

The third is a flood stress test: a backlog of misses builds up, then a large stream of highly cached requests arrives. LPM, PEEK (a scheduler that adds fairness on top of hit-first ordering) and RAGCache let every cheap newcomer pass the backlog, and the worst miss waits 66 to 201 seconds. Fairway holds it at 22 seconds, the same as first-come-first-served. The cost is that the flood requests' own median rises from 1.6 seconds under LPM to 18 seconds; they are delayed but never starved.

The ablation swaps the relative wait back to an absolute wait. When requests have similar lengths, the two differ by under 3%; the gap appears only when lengths are mixed. On SEC long-document QA, the p99 of short prompts falls from 13.6 to 8.6 seconds, while across the mixed-length scenarios the p99 of long prompts rises by 6% to 31%. So the gain of the relative wait comes from letting short requests go first, and the longest requests pay for it.

Limitations as I see them

First, under persistent overload where hits are only slightly cheaper than misses, the median gets worse. In the overloaded MuSiQue scenario, Fairway's median is 3.0 seconds against 0.9 for LPM, bought with a p99 of 12.6 seconds, only a little better than LPM's 14.2.

Second, the experiments are small. All results come from an 8B model on one A6000, with one generated token per request. The authors scale load and cache size to the GPU and argue the conclusions carry over to larger GPUs, but larger models, multi-GPU prefill instances and deployments that run prefill and decode on the same machine were not tested.

Third, the Fair lane's protection only acts within one step. At most a quarter of the oldest request's work, plus the overshoot of one request, goes ahead of it, and it starts in that step only if the remaining budget and KV memory allow. As a rough estimate of 4 times 2,048, this protection covers oldest requests with up to about 8k uncached tokens. Longer requests rely on the relative wait: their score keeps growing while they wait, while a newly arrived request scores little more than its reuse ratio, so they eventually rise to the top of the Fast lane. In the authors' experiments, with prompts of up to 16k tokens, no request starved by that evaluation criterion, and Fairway's worst wait stayed within 2.3 times its p99.

How a RAG or agent serving team could try it

1. Measure your own queue first. From serving logs, take each request's cached and uncached lengths and see how many times the work of concurrently queued requests differs. If it differs by only a few times, ordering matters little and you can leave it alone.
2. Add only the relative wait. On top of an existing hit-first ordering, add a term of wait divided by patience, with patience at 3 times the expected prefill time and at least 1 second. Check whether p99 and the worst wait drop during bursts while the median stays the same. Note Table 2 of the paper: without the Fair lane, the relative wait alone gives long prompts a worse p99 than an absolute wait (20.2 vs 15.1 seconds) and a worse worst-case flood wait (59 vs 33 seconds), so watch the long-request tail.
3. Then add the Fair lane. If popular documents cause floods, add the second lane ordered by arrival with fourfold accounting, and watch the worst wait of backlogged requests.
4. Accept it with spike replay. Replay a real traffic spike at its original timing and check both the median and p99 targets, not only the mean.

Verdict

The key lesson: once prefix caching makes the true cost of requests differ by a hundred times, queue fairness must be measured in that true cost, and counting turns or seconds will fail on some workload.