Research note 2
Cache-aware routing for multi-turn chat
Abstract
In multi-turn chat each turn resends the conversation so far. A turn that reaches the worker which served the previous turn can reuse that worker’s cached state. We compared a router that seeks this, here called KV-aware, with round-robin and least-loaded routing on four GPUs. KV-aware routing reduced the time to complete 64 concurrent chats by 16% for six-turn chats and 27% for twenty-turn chats against round-robin, and by 3 to 6% against least-loaded routing. The gain is bounded by the prefill that would otherwise be repeated, which was small in this workload.
Question
A serving engine keeps the result of prefill in its KV cache. When a new prompt begins with text the worker has already processed, the worker reuses that part and computes only the remainder [2, 4]. The cache belongs to one worker. With several workers, whether a turn finds its conversation depends on where the router sends it [1].
We asked how much a router that sends each turn to the worker holding its conversation gains over two common policies, and what limits the gain.
Method
| Model | Qwen2.5-7B |
|---|---|
| Engine | vLLM 0.11.0 |
| Hardware | 4 × RTX A6000, one worker per GPU |
| Traffic | 64 chats at once |
| Prompts | A 600-word system prompt shared by every chat, 150-word user turns, 128-token replies |
| Chat length | 6 turns and 20 turns |
| Policies | Round-robin, least-loaded, KV-aware |
| Runs | Three for the six-turn chats |
Round-robin sends each request to the next worker in turn. Least-loaded sends it to the worker with the least work in progress. KV-aware sends it to the worker that already holds the chat’s cached state.
Results
| Measure | Round-robin | KV-aware | Change |
|---|---|---|---|
| Time to complete, 6-turn chats | 29.2 s | 24.4 s | −16% |
| Time to complete, 20-turn chats | 123.8 s | 90.0 s | −27% |
| Time to first token on later turns, 6-turn chats | 153 ms | 114 ms | −25% |
| Time to first token on later turns, 20-turn chats | 223 ms | 136 ms | −39% |
| Cache hit rate | 61 to 75% | 89 to 95% |
Against least-loaded routing the gain was smaller: 3 to 6% less time to complete. The tail improved more. In the twenty-turn chats the 90th-percentile time to first token was 33% lower.
| Arrangement | Time to complete | Later-turn first token | Cache hit rate |
|---|---|---|---|
| Two workers sharing the GPU, round-robin | 24.2 s | 117 ms | 72.8% |
| Two workers sharing the GPU, KV-aware | 22.4 s | 75 ms | 89.4% |
| One worker with the whole GPU | 12.3 s |
Analysis
Routing can remove only repeated prefill
For a single request, prefill is small beside decode. A turn spent about four seconds in decode, 128 tokens at about 30 tokens per second per user, and 100 to 200 ms in prefill of a history of about 1,000 tokens. Under load a miss costs more than its own duration, because a recomputed prefill occupies steps on which the other chats’ decodes are waiting. That is why the saving against round-robin exceeds the prefill share of one turn.
The saving is bounded all the same. Once nearly every turn finds its cache, nothing further can be recovered. Least-loaded routing already reached a hit rate of about 86% in this workload, which left 3 to 6% for a cache-aware policy to add. The effect grows with the length of the history and shrinks with the length of the reply.
A shared system prompt helps every policy
All 64 chats began with the same 600 words. Any worker that had served any chat already held that prefix, which is why round-robin reached a hit rate of 61 to 75%. KV-aware routing added only the part of the prompt that is particular to one chat. The arithmetic is set out in technical note 4.
The gain grows with the number of workers
With n workers, round-robin returns a turn to the worker that holds its chat one time in n. Prefix caching does most of the work in this experiment. Routing keeps that saving from being lost as workers are added.
Engineering observations
- The gateway was at first slower than the effect under study. Redis writes executed one after another added 50 ms to every later turn. After the correction the gateway adds about 1 ms. The API server adds about 100 ms per request before the engine starts.
- Two workers on one GPU halve throughput, as Table 3 shows. We run one worker per GPU.
- CUDA graphs, which record a sequence of GPU operations once and replay it, were worth 7 to 8%.
Limitations
- The measure is the time to complete a burst of chats. Goodput at a service class and cost per token were not measured.
- The engine version is older than that of research note 1, and the two results should not be combined.
- Short histories and long replies are the case in which routing matters least.
Further work
- Histories of 8,000 to 32,000 tokens with short replies, as in agent traffic, where rereading the history costs seconds per turn.
- Eight workers, one per GPU.
- Results reported as goodput at a service class, with intervals over three rounds.
References
- V. Srivatsa, Z. He, R. Abhyankar, D. Li, Y. Zhang. Preble: Efficient Distributed Prompt Scheduling for LLM Serving. 2024.
- I. Gim, G. Chen, S. Lee, N. Sarda, A. Khandelwal, L. Zhong. Prompt Cache: Modular Attention Reuse for Low-Latency Inference. 2023.
- R. Qin, Z. Li, W. He, et al. Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving. 2024.
- W. Kwon, Z. Li, S. Zhuang, et al. Efficient Memory Management for Large Language Model Serving with PagedAttention. SOSP 2023.
Write to us about this note.