llm-router: A KV Cache-Aware Intelligent LLM Request Routing System

A cache-aware LLM router implemented in Go, which routes requests to workers that have cached their KV prefixes using per-worker radix trees, significantly improving inference efficiency in multi-turn conversation scenarios.

• Original Author/Maintainer: zxuhan
• Source Platform: GitHub
• Original Title: llm-router
• Original Link: https://github.com/zxuhan/llm-router
• Publication Date: May 24, 2026

In LLM inference services, the Key-Value (KV) Cache is a core mechanism to improve multi-turn conversation performance. When users interact with the model in multiple turns, the system caches previously computed key-value pairs to avoid re-computing them in subsequent requests, thus significantly reducing the Time to First Token (TTFT) latency.

However, in distributed deployment scenarios, traditional load balancing strategies (such as round-robin, random, least connections) often ignore the locality characteristics of KV cache. When multiple workers process requests in parallel, subsequent requests of the same conversation may be routed to different workers, leading to cache invalidation and the need to re-compute prefixes, resulting in severe waste of computing resources.

llm-router was born to solve this problem. It intelligently identifies the prompt prefix of requests and always routes requests with the same prefix to the worker holding the cache, enabling cross-worker KV cache sharing.

llm-router is implemented in Go and deployed as a reverse proxy layer for OpenAI-compatible APIs before inference engines (e.g., vLLM, llama.cpp). The system maintains a compressed radix tree for each backend worker to track recently distributed prompt prefixes.

The routing decision process is as follows:

1. Prefix Hashing: Hash the request prompt in 32-byte chunks
2. Longest Match Query: Query each radix tree for the longest prefix match
3. Conflict Resolution: Break ties via randomization when there's a draw
4. Sorting Strategy: Sort by (descending match length, ascending number of in-flight requests)
5. Safety Valve Mechanism: Apply a saturation threshold for in-flight requests to prevent overload
6. Transparent Transmission: Expose routing decisions via X-Router-Backend and X-Router-Reason response headers

Strategy	Decision Rule
roundrobin	Round-robin counter
random	Uniform random
leastloaded	Minimum number of in-flight requests
prefixaware	Longest prefix match + random tie-breaking + saturation safety valve

It's worth noting that llm-router is not a competitor to SGLang's RadixAttention or vLLM's --enable-prefix-caching, but rather a complementary two-layer architecture:

• Engine Layer: Solves the problem of prefix sharing within a single engine
• Routing Layer (llm-router): Solves the problem of request distribution across multiple independent engine instances

The two can be used together: Deploying llm-router in front of vLLM or SGLang allows you to gain both intra-engine and cross-worker cache locality advantages.

The project was fully evaluated on RunPod's 4×A100 80GB SXM cluster using vLLM 0.6.4 + Qwen2.5-{7B,14B} models. The test scenario simulated 4 to 24 concurrent sessions, each with 8 turns of conversation and sharing a 6KB system prompt.

Core Metrics: TTFT Slope (4→24 Sessions)

Strategy	7B Model Slope	14B Model Slope
random	+49 ms	+98 ms
round-robin	+31 ms	+36 ms
least-loaded	+35 ms	+50 ms
prefix-aware	+16 ms	+25 ms

Compared to the prefix-aware strategy, the slope multiples of other strategies are: random (3.0×/3.9×), least-loaded (2.2×/2.0×), round-robin (1.9×/1.4×). This indicates that in high-concurrency scenarios, the prefix-aware strategy has the most gradual latency growth.

Production Scenario Performance (24 Sessions, 14B Model)

Strategy	KV Cache Hit Rate	TTFT p50	TTFT p95	TTFT p99	RPS
roundrobin	91.10%	193 ms	2.40 s	2.72 s	25.2
random	90.69%	265 ms	2.36 s	2.74 s	23.4
leastloaded	94.22%	171 ms	2.12 s	2.29 s	27.6
prefixaware	94.88%	166 ms	2.13 s	2.25 s	26.8

prefix-aware is 3% faster than the optimal baseline (least-loaded) in p50 latency, 14% faster than round-robin, and 37% faster than random; its p99 latency is the best among the four strategies (2.25s vs. 2.29s).

Local validation was conducted on an M1 Pro Mac using llama.cpp + Qwen2.5-1.5B (Q4_K_M quantization):

Strategy	KV Cache Hit Rate	TTFT p50	TTFT p95	RPS
roundrobin	57.56%	2.01 s	8.21 s	1.67
random	62.34%	1.70 s	8.06 s	1.84
leastloaded	61.94%	0.82 s	8.29 s	1.85
prefixaware	75.00%	2.10 s	3.70 s	2.36

Compared to the least-loaded baseline, the prefix-aware strategy increases cache hit rate by 13.1 percentage points, reduces p95 latency by 55%, and improves throughput by 28%. Although the p50 latency is slightly higher (because prefix-aware serializes subsequent requests to the same worker), it has obvious advantages in long-tail latency and throughput.