Load balancing self-hosted LLM replicas for prefix cache hits: session affinity, bounded consistent hashing and least-load trade-offs

#The problem

You scale a chat or agent workload from one vLLM replica to eight and time to first token (TTFT) gets worse per request, even though each GPU is less busy. Prefill compute goes up and the prefix cache hit rate drops from 70% to about 12%.

The cause is the load balancer. A Kubernetes Service spreads connections roughly at random, so turn 5 of a conversation lands on a replica that has never seen turns 1-4. That replica has to recompute the whole prompt: system prompt, tool definitions, retrieved documents and history. With long agent prompts, prefill is most of your TTFT.

Prefix caching only helps when requests that share a prefix land on the same replica.

#Step 1: measure the per-pod hit rate

vLLM's V1 engine exposes prefix cache counters. Recent versions name them vllm:prefix_cache_queries and vllm:prefix_cache_hits (counted in tokens). Older V1 builds used vllm:gpu_prefix_cache_queries / vllm:gpu_prefix_cache_hits, counted in blocks. Older still, V0 had a vllm:gpu_prefix_cache_hit_rate gauge. Check yours:

kubectl exec -n llm deploy/vllm -- curl -s localhost:8000/metrics | grep -E '^vllm:.*prefix_cache'

PromQL, adjusting the names and _total suffix to match what you saw:

sum by (pod) (rate(vllm:prefix_cache_hits_total[5m]))
/
sum by (pod) (rate(vllm:prefix_cache_queries_total[5m]))

Record three things before you change anything: per-pod hit rate, p50/p95 TTFT, and per-pod request rate. You'll need all three to see whether affinity helped or just moved the load.

#Step 2: pick a routing key

For most chat and agent apps, a session ID set by the application is the best starting point. Have the client send it as a header, e.g. X-Session-Id, so the gateway never has to parse the JSON body.

#Step 3: route to pods, not to a Service VIP

The gateway has to see individual pod IPs. A ClusterIP Service hides them, so use a headless Service:

apiVersion: v1
kind: Service
metadata:
  name: vllm-headless
  namespace: llm
spec:
  clusterIP: None
  selector:
    app: vllm
  ports:
    - name: http
      port: 8000
      targetPort: 8000

kubectl get endpointslices -n llm -l kubernetes.io/service-name=vllm-headless

#Step 4: consistent hashing with bounded load (HAProxy)

Plain hashing pins a long agent session, or a large tenant, to one replica no matter how busy it gets. HAProxy's hash-balance-factor caps each server at a percentage of the average load. When a server is over the cap, its keys spill to the next server on the ring. That keeps most cache hits and limits hot spots.

resolvers k8s
    parse-resolv-conf
    hold valid 5s

backend vllm
    balance hdr(X-Session-Id)
    hash-type consistent
    hash-balance-factor 150
    option httpchk GET /health
    timeout server 600s
    server-template vllm 16 vllm-headless.llm.svc.cluster.local:8000 check resolvers k8s init-addr none

• hash-balance-factor 150 lets a server reach 1.5 times the average number of in-flight requests before keys move off it. Lower it for tighter balance and fewer cache hits.
• Requests without the header fall back to round robin. Make sure the clients that matter actually send it.
• timeout server must cover the longest streamed generation.

NGINX open source has consistent hashing but no bounded load:

upstream vllm {
    hash $http_x_session_id consistent;
    server 10.0.1.11:8000 max_fails=2 fail_timeout=10s;
    server 10.0.1.12:8000 max_fails=2 fail_timeout=10s;
}

It works for even, short sessions. It won't protect you from one heavy session or tenant.

Warning

Scaling events reshuffle part of the hash ring. With consistent hashing only about 1/N of keys move when a replica is added or removed, but those sessions pay a full prefill on their next turn. Expect a TTFT bump after each scale-out, and don't let the autoscaler flap.

#Step 5: compare against least-load

Affinity is not always the right answer. Prefill saved by a cache hit is worth more than balance only when prompts are long and shared.

Run the same recorded traffic both ways and compare p95 TTFT and tokens per second per GPU. Leave alone any strategy that improves hit rate but makes p95 worse.

#Step 6: watch for imbalance

# Waiting requests per pod; one pod far above the rest = hot key
max by (pod) (vllm:num_requests_waiting)

# KV cache usage per pod (gauge name varies by version)
max by (pod) (vllm:kv_cache_usage_perc)

Alert when one pod's waiting queue stays well above the median for 10 minutes. The usual causes are a single huge session, a tenant ID used as the key, or a client that sends the same session ID for every user.

#When to go further

Session affinity is an approximation: the gateway guesses where the cache lives. Newer components route on actual KV cache state. The Gateway API Inference Extension (InferencePool plus an endpoint picker) and projects built on it, such as llm-d, score pods using prefix-cache and queue signals reported by vLLM. They take more work to run and change quickly, so check the current docs and maturity of each before you adopt one. Header-based bounded hashing gets most of the benefit for chat and agents with far fewer moving parts.

#Prevent it next time

• Treat "how requests reach replicas" as part of the serving design, not a default Service.
• Keep the static part of prompts (system prompt, tool schemas) byte-identical and at the start so prefixes actually match.
• Dashboard per-pod hit rate, waiting requests and TTFT side by side.
• Re-test routing after vLLM upgrades: block size, cache eviction and metric names change between releases.