[RFC]: Cache-aware chat routing with exact-match session affinity

[wuhang2014]

Motivation.

Agent workloads are multi-turn: each turn sends the whole conversation to the
worker, and with vLLM prefix caching the KV cache pays for every token shared
with a previous turn on the same worker. On main, cache_aware chat routing
has three failure modes for this shape:

1. Session affinity is approximated by a prefix probe, not equality.
   main passes session_params.session_id as the routing text and probes
   the radix tree at cache_threshold (default 0.5). Two different sessions
   whose ids share a long string prefix (e.g. session-1 vs session-12,
   8/9 ≈ 89% match) count as the same affinity and pile onto one worker,
   while a session id that prefix-matches nothing gets no stickiness at all.
2. Requests without a session id have no cache affinity. The routing text
   is the session id and nothing else, so a chat request without
   session_params.session_id routes with an empty key — the tree probe
   always misses and the request goes to min-load, even when its system
   prompt and tool schemas are already cached on some worker.
3. The conversation prefix is never modeled. Cross-session prefix reuse
   (shared system prompt, tool schemas) is invisible to the policy, so the
   shared prefix is re-prefilled on every worker. There is also no
   observability of why a worker was chosen.

Proposed Change.

Extend the cache_aware policy so /v1/chat/completions requests route the
way a real agent session works: sticky to a worker by
session_params.session_id (exact-match affinity), falling back to
prefix-tree matching on the full serialized chat history when the session is
unknown, and falling back to min-load when neither key has affinity. Load
balancing still overrides affinity when workers are imbalanced past the
existing abs/rel gates.

Key design points:

• Session map (exact match). A per-model
  session_id → (worker_url, last_access_ms) map replaces the prefix probe
  for session keys. Session ids never enter the prefix tree, so session-1
  and session-12 can never collide. Entries are swept by TTL (1 h) plus a
  per-model capacity (max_tree_size), and dropped lazily on lookup and
  eagerly on worker removal.
• Session identity derivation. Session keys are derived the same way hash
  policies derive theirs (extract_hash_key: HTTP headers such as
  x-session-id/x-user-id, then body session_params.session_id / user /
  session_id / user_id fields), with the explicit routing text winning
  when present. Session-derived keys use exact-match semantics even without a
  fallback key; plain text keys keep prefix-tree semantics even when
  unrelated headers are present, so per-request-id headers (x-request-id,
  x-trace-id) cannot defeat prompt prefix affinity.
• History fallback key. The serialized chat history — name-sorted tool
  schemas first (stable across turns), then system/developer/user/assistant/
  tool messages — is prefix-matched at cache_threshold when the session map
  misses. A session miss therefore still lands on the worker whose KV cache
  holds the conversation prefix. With no extractable history (e.g.
  image-only chat), a session miss selects min-load directly.
• Teaching. Every selection teaches the state that produced it: session
  hits refresh the entry and insert the (grown) history key into the tree;
  history hits / min-load / imbalanced selections set the session entry and
  insert the history key.
• Observability. Exactly one final decision label per request
  (session_id_match, full_history_match, load_balance,
  empty_history_min_load, …) is emitted to
  vllm_router_cache_aware_decisions_total{decision=…} and echoed in the
  x-vllm-router-decision response header, alongside
  x-vllm-router-worker / x-vllm-router-base-worker / x-vllm-router-dp-rank.
• No new required configuration. cache_threshold, the balance gates and
  max_tree_size are reused; the session TTL is a compile-time constant.
  Hash-based policies keep seeing the raw session id, so rolling upgrades do
  not remap existing sessions.

Feedback Period.

One week, until 2026-08-25.

CC List.

@herotai214

Any Other Things.

• Implementation: PR [Feature]: cache-aware chat routing with session-id/full-history fallback #217 (feat/cache-aware-chat-routing), ready for review;
  unit/integration tests cover the new paths (cargo test --lib 502 passed,
  clippy/fmt clean).
• Performance evaluation (Qwen3.5-4B, Codex SWE-bench Pro replay, 25 sessions
  × 4 turns, max_tokens=256, session_serial, lb_mid preset): prompt-cache
  hit rate 20.5→59.5% (NPU C4), 20.7→50.1% (NPU C8), 38.0→50.1% (GPU H800);
  TTFT −1.31 s / E2E −3.87 s at C4 and TTFT −1.44 s / E2E −5.40 s at C8 on
  NPU; every measured column improves on GPU except queue time (unchanged).