Markdown

KV-aware request routing¶

Scope: the algorithm a fleet-level router runs to pick which vLLM/SGLang-class replica serves the next request, when every replica has a KV cache and some of them already hold part of the incoming prompt. Covers the index (a radix tree over chained KV block hashes, fed by engine cache events), the longest-matched-prefix query, the cost function that trades cache overlap against queue and decode load, and the two ways the scheme breaks (request herding onto a cache-rich replica, and a router index that outlives the blocks it describes). This is the layer that LLM request routing (which model to pick) and region-replica routing (which site to pick) both delegate away. Inside a single engine, the block table, the hash chain, and LRU eviction are KV cache management; this page treats that engine as a black box that emits events. Admission and priority decisions that happen before routing are inference QoS and admission control.

The numpy block below is executed and asserted here: it builds the router-side radix index, checks the longest-matched-prefix query against a brute-force reference, reproduces NVIDIA Dynamo's published cost formula and its overlap-credit decay example arithmetically, and quantifies herding and stale-index drift. The Ray Serve LLM, vLLM, and llm-d configuration snippets are reference templates, taken from current upstream docs and source (not executed here; those services are not installed). Every quantitative result in the Anyscale post that motivated this page lives in figures, not prose, and is reproduced nowhere below: see Reading the Anyscale numbers.

What it is¶

A KV-aware router is a stateful load balancer. Where an HTTP round-robin balancer treats replicas as interchangeable, a KV-aware router knows that replica 3 already holds the KV cache for the first 4,096 tokens of the incoming prompt and replica 1 does not, and that sending the request to replica 3 skips that much prefill.

Three levels of fidelity exist, in increasing order of cost and accuracy:

Session affinity. Consistent hashing on a client-supplied session ID (in Ray Serve LLM the header name is RAY_SERVE_SESSION_ID_HEADER_KEY, default x-session-id). The router knows nothing about caches; it just keeps a conversation pinned. With enough virtual nodes it balances the number of sessions per replica.²
Prefix affinity. The router keeps its own record of what it has previously dispatched and scores on overlap with that record, never on engine state. Ray Serve LLM's PrefixCacheAffinityRouter is the text form: a prefix tree over prompt text, routed on character overlap. Anyscale states two limits plainly, "Approximate: The prefix tree tracks request strings, not the actual KV cache" and "Not eviction-aware: The router assumes previously seen prefixes remain cached."¹ llm-d's approx-prefix-cache-producer sits in the same tier for the second reason but not the first: it hashes token IDs, not text, and its index is a flat hash map rather than a tree. What makes it approximate is that the index is written from the scheduler's own dispatch decisions, not from engine cache events.¹¹
KV-cache affinity. The engines publish real cache events and the router maintains a global index of which replica holds which block. vLLM emits BlockStored, BlockRemoved, and AllBlocksCleared over ZeroMQ; Ray Serve LLM's KVAwareRouter consumes them and hands scoring to NVIDIA Dynamo's selection service.⁴²

Only the third level can distinguish "this replica processed that prompt once" from "this replica still has the blocks". That distinction is what section 4 of the executed code measures.

The routing key is not the prompt string. It is the same chained block hash vLLM uses internally, schematically h_i = H(h_{i-1} || tokens_i || extra_keys_i), over fixed-size blocks of block_size tokens, with CacheConfig.DEFAULT_BLOCK_SIZE = 16. That notation is a shape, not a recipe: an external reimplementation of it will not reproduce vLLM's actual digests, which hash a serialized 3-tuple rather than a concatenation, root the chain at NONE_HASH rather than at an empty parent, and fold cache_salt into block 0 only.⁵ Because each hash covers its whole prefix, a single shared hash at depth d implies agreement on all d * block_size preceding tokens, so a trie over those hashes answers "longest common prefix with anything this replica holds" in one descent.

Why use it¶

Prefill is the part you can delete. Prefill is compute-bound and grows with prompt length; a cache hit removes it outright. Agentic and multi-turn workloads resend their entire history every turn, so the reusable fraction climbs with turn count. Agent loop economics covers the token-growth side of that.
The engine cannot do it alone. vLLM's automatic prefix caching only helps if the request lands on the replica holding the blocks. At a fleet of N replicas, a cache-blind balancer dilutes any given prefix across all N, so per-replica hit rate falls roughly as 1/N for cross-session reuse.
Cache overlap is a load estimator, not a goal. Anyscale's framing: "KV cache overlap tells us how much prefill work can be saved, but not how much work the engine still has to do."¹ A router that maximises overlap alone concentrates traffic; the executed block below drives that to its limit (144 of 144 requests onto one of four replicas).
It needs no client cooperation. Session affinity requires the caller to mint and carry a session ID. A KV-aware router discovers reuse across sessions, which is where a shared system prompt or a shared repository context lives.

When to use it (and when not)¶

Use KV-aware routing when the workload is heterogeneous and prefix-rich: coding agents, multi-turn assistants, RL rollout fleets, RAG over a shared corpus. The Ray Serve LLM guide gives the condition as "Replicas carry uneven token load, GPU memory is under pressure, or requests share prefixes beyond the system prompt."²

Prefer something simpler when:

Prompts share nothing but the system prompt. Then the reusable prefix is a few blocks, constant across replicas, and carries no routing information. Round-robin is correct and free.
Cache misses are catastrophic and sessions are long. Ray's guidance is that for "long multi-turn conversations, keeping all turns on the same replica guarantees KV cache locality", and that KVAwareRouter "may trade some cache overlap for better token-load balance and therefore requires tuning."¹ Consistent hashing gives a hard guarantee where a score gives a tendency.
Sessions have similar workloads. Anyscale's own third condition for preferring consistent hashing: "When sessions do not vary significantly in input/output lengths or execution time, consistent hashing already provides reasonable load balance at the session level." The post sets no threshold on "significantly", and reasonable session-level balance is not the same claim as token-level balance.¹
The deployment shape is unsupported. As of the current Ray docs, KVAwareRouter requires direct streaming (one model per application, no LoRA- or multiplex-aware routing), and does not support data-parallel rank scoring or prefill/decode disaggregation.² For disaggregated inference fleets that is disqualifying today.
The router itself is the bottleneck. KV-aware scoring requires tokenizing every prompt at the ingress with the engine's own renderer and chat template.² That is real CPU per request.

Architecture¶

Two streams of engine state reach the router, and they fail independently. The cache event stream says which blocks exist on which replica; the request lifecycle stream (admitted, first token, decode progress, completed) says how much work each replica currently owes. Cache overlap alone is not the decision, so losing either stream degrades routing in a different way.

flowchart TB
  C["Client request"] --> ING["Ingress router replica<br/>(tokenize with engine chat template)"]
  ING --> IDX["Global radix index<br/>block hash -> {replica ids}"]
  IDX -->|"matched blocks per replica"| SC["Cost function<br/>prefill after credit + decode load"]
  LT["Per-replica load view:<br/>active prefill blocks,<br/>active decode blocks,<br/>active requests"] --> SC
  SC -->|"argmin cost"| PICK["Selected replica"]
  PICK --> E1["vLLM replica 1"]
  PICK --> E2["vLLM replica 2"]
  PICK --> E3["vLLM replica 3"]
  E1 -.->|"BlockStored / BlockRemoved<br/>(ZeroMQ PUB, seq-numbered)"| IDX
  E2 -.-> IDX
  E3 -.-> IDX
  E1 -.->|"admit, first token, decode progress, done"| LT
  E2 -.-> LT
  E3 -.-> LT
  ING <-.->|"eventually consistent<br/>load sync"| ING2["Peer ingress replica"]

The cost function¶

NVIDIA Dynamo's router, which is the scoring engine Ray Serve LLM runs in-process for KVAwareRouter, publishes its cost in blocks:⁶

raw_prefill_blocks = active_prefill_blocks + incoming_prompt_blocks
adjusted_prefill_blocks = max(0, raw_prefill_blocks - overlap_credit_blocks)
potential_decode_blocks = active_decode_blocks + incoming_active_blocks
active_request_blocks = decode_active_request_weight * active_requests
cost = prefill_load_scale * adjusted_prefill_blocks + potential_decode_blocks + active_request_blocks

The lowest-cost eligible worker wins. Three properties matter for reasoning about behaviour:

Cache overlap enters as a subtraction from prefill cost, not as its own objective. Setting overlap_score_credit = 0 deletes cache awareness and leaves pure load balancing. Dynamo's --load-aware preset is broader than that one field: it overwrites ten, also disabling KV events, KV-reuse assumptions and the remote and shared-cache indexers while enabling active-block and prefill-token load tracking.⁷
The adjusted prefill term is clamped at zero. The credit is subtracted from raw_prefill_blocks, which is the replica's active prefill plus the incoming prompt, not from the incoming request alone, so a large credit can also cancel backlog the replica already carries. What the clamp guarantees is only that the term never goes negative: "overlap credits never make it negative", so a fully cached request cannot outbid an arbitrarily loaded replica.⁶
Overlap credit can be made load-dependent. overlap_score_credit_decay multiplies device-local credit by 1 / (1 + decay * normalized_excess), where the excess is that replica's active prefill above the least-loaded candidate, normalized by the incoming request size. Dynamo documents that "a decay of 1 halves device credit at one request-equivalent of excess prefill load."⁷ The executed block reproduces that arithmetic.

Tier awareness sits in the credit, not the match: a block that is present but CPU-offloaded is credited at host_cache_hit_weight (Dynamo default 0.75) rather than at full value, because it must be pulled back to GPU first.⁷

Blended score versus hard switch¶

Production routers resolve the affinity-versus-load conflict in one of two shapes, and the distinction changes how they fail.

Blended score (Dynamo / Ray KVAwareRouter): one cost combines both terms, so affinity always has some influence and load always has some influence. Behaviour is continuous in the weights; there is no cliff, but there is also no guarantee that a badly weighted router ever balances.
Hard switch: check load balance first, and abandon affinity entirely when the fleet is imbalanced. Ray's PrefixCacheAffinityRouter switches to power of two choices above imbalanced_threshold.³ SGLang's model gateway uses a two-condition test, both of which must hold: (max_load - min_load) > balance_abs_threshold and max_load > balance_rel_threshold * min_load; imbalanced routes to shortest queue, balanced routes on prefix match.⁸ The AND is what stops a small fleet with tiny absolute loads from flapping into shortest-queue mode on a ratio alone.

A hard switch is easier to reason about and easier to alert on (the mode is observable), but it discards all cache locality the moment it trips. A blended score degrades gracefully and is harder to debug.

Executed: the index, the boundary, herding, and stale affinity¶

The block below is the router's half of the problem in numpy. It builds a radix index over chained block hashes keyed by replica set; checks the single-descent longest-match query against a brute-force per-replica scan on every request in a corpus, including after an interior block is evicted (the match must truncate at the hole, not jump it); pins the block-boundary behaviour that makes prefix matching coarse; reproduces the Dynamo cost formula and its decay example; drives an adversarial workload where pure affinity herds all traffic onto one replica; and measures the phantom hit rate a router accrues when eviction events are not propagated. Run: python3 kv-aware-request-routing.py.

# kv-aware-request-routing.py -- runnable on stock python3 + numpy.
# The router-side half of prefix-cache-aware routing: a global prefix tree over vLLM-style
# chained BLOCK hashes, a longest-matched-prefix lookup per replica, the affinity-versus-load
# score, and what an unreported eviction does to that index.
import hashlib
from collections import OrderedDict

import numpy as np

BLOCK = 16                                    # tokens per KV block (vLLM block_size default)
ROOT = b"\x00" * 32                           # hash of the empty prefix


def block_hashes(tokens, block_size=BLOCK):
    """Chained per-block hashes: h_i = H(h_{i-1} || tokens_i). Only FULL blocks are
    cacheable, so the trailing partial block is never hashed and never routable."""
    out, parent = [], ROOT
    for i in range(len(tokens) // block_size):
        h = hashlib.sha256()
        h.update(parent)
        h.update(np.asarray(tokens[i * block_size:(i + 1) * block_size], dtype=np.int64).tobytes())
        parent = h.digest()
        out.append(parent)
    return out


class PrefixIndex:
    """Router-side radix tree over block hashes. Each node carries the set of replicas that
    reported holding that block; engines push block-stored and block-removed events. The
    node_of map makes a removal event O(1) per block, since a chained hash is unique to its
    position in the tree."""

    def __init__(self, n_replicas):
        self.n_replicas = n_replicas
        self.kids = [{}]                      # node -> {block_hash: child node id}
        self.holders = [set()]                # node -> replicas holding that block
        self.node_of = {}                     # block_hash -> node id

    def block_stored(self, replica, hashes):
        node = 0
        for h in hashes:
            nxt = self.kids[node].get(h)
            if nxt is None:
                nxt = len(self.kids)
                self.kids.append({})
                self.holders.append(set())
                self.kids[node][h] = nxt
                self.node_of[h] = nxt
            node = nxt
            self.holders[node].add(replica)

    def block_removed(self, replica, hashes):
        for h in hashes:
            node = self.node_of.get(h)
            if node is not None:
                self.holders[node].discard(replica)

    def matched_blocks(self, hashes):
        """Longest matched prefix per replica in ONE descent. A replica can only serve
        block d from cache if it also holds blocks 1..d-1, so the candidate set shrinks
        monotonically and a replica's match length is the depth at which it drops out."""
        matched = np.zeros(self.n_replicas, dtype=np.int64)
        alive = set(range(self.n_replicas))
        node = 0
        for depth, h in enumerate(hashes, start=1):
            node = self.kids[node].get(h)
            if node is None:
                break
            alive = alive & self.holders[node]
            if not alive:
                break
            for r in alive:
                matched[r] = depth
        return matched


def brute_force_matched(per_replica_sets, hashes, n_replicas):
    """Slow reference: for each replica independently, count leading hashes it holds."""
    out = np.zeros(n_replicas, dtype=np.int64)
    for r in range(n_replicas):
        held = per_replica_sets[r]
        c = 0
        for h in hashes:
            if h not in held:
                break
            c += 1
        out[r] = c
    return out


# ---------------------------------------------------------------- 1. index correctness
rng = np.random.default_rng(20260826)
N_REP = 4
idx = PrefixIndex(N_REP)
held = [set() for _ in range(N_REP)]

shared_sys = list(rng.integers(0, 50_000, size=4 * BLOCK))      # 4-block system prompt
corpus = []
for s in range(24):
    body = list(rng.integers(0, 50_000, size=int(rng.integers(2, 9)) * BLOCK + 7))
    corpus.append(shared_sys + body)

for i, toks in enumerate(corpus[:16]):                          # warm a subset of replicas
    r = i % N_REP
    hs = block_hashes(toks)
    idx.block_stored(r, hs)
    held[r].update(hs)

for toks in corpus:                                             # query EVERY request
    hs = block_hashes(toks)
    fast = idx.matched_blocks(hs)
    slow = brute_force_matched(held, hs, N_REP)
    assert np.array_equal(fast, slow), (fast, slow)

# A replica that saw the system prompt but not this body matches exactly 4 blocks.
probe = shared_sys + list(rng.integers(0, 50_000, size=3 * BLOCK))
m_probe = idx.matched_blocks(block_hashes(probe))
assert m_probe.max() == 4 and m_probe.min() == 4, m_probe        # all four replicas warmed

# Adversarial: punch a HOLE in the middle of replica 2's chain. The match must truncate at
# the hole, not skip over it, because block d is only usable if 1..d-1 are resident.
victim = corpus[2]
vh = block_hashes(victim)
idx.block_removed(2, [vh[5]])
held[2].discard(vh[5])
assert idx.matched_blocks(vh)[2] == 5, idx.matched_blocks(vh)[2]
assert np.array_equal(idx.matched_blocks(vh), brute_force_matched(held, vh, N_REP))

# --------------------------------------------------------- 2. the block-boundary property
base = shared_sys + list(rng.integers(0, 50_000, size=5 * BLOCK + 9))   # 9 full blocks + tail
solo = PrefixIndex(1)
solo.block_stored(0, block_hashes(base))
assert solo.matched_blocks(block_hashes(base))[0] == 9

def flip(seq, i):
    out = list(seq)
    out[i] = (out[i] + 1) % 50_000
    return out

# Differ at the LAST token of block 3 -> blocks 3.. are destroyed, 3 survive (0,1,2).
assert solo.matched_blocks(block_hashes(flip(base, 4 * BLOCK - 1)))[0] == 3
# Differ at the FIRST token of block 4 -> 4 survive. One token later, one more block kept.
assert solo.matched_blocks(block_hashes(flip(base, 4 * BLOCK)))[0] == 4
# Differ inside the trailing PARTIAL block -> no full block changes, all 9 survive.
assert solo.matched_blocks(block_hashes(flip(base, 9 * BLOCK + 3)))[0] == 9
# Prepending ONE token (a timestamp in the system prompt) shifts every boundary -> total loss.
assert solo.matched_blocks(block_hashes([7] + base))[0] == 0
# Boundary: a request shorter than one block has no hashes at all, so no affinity exists.
assert block_hashes(base[:BLOCK - 1]) == []
assert solo.matched_blocks(block_hashes(base[:BLOCK - 1]))[0] == 0

# --------------------------------------------------- 3. affinity versus load: herding
def dynamo_cost(matched, req_blocks, active_prefill, active_decode,
                incoming_active_blocks=0.0, overlap_score_credit=1.0,
                prefill_load_scale=1.0, overlap_credit_decay=0.0,
                decode_active_request_weight=0.0, active_requests=0.0):
    """NVIDIA Dynamo's documented router cost, in KV blocks, lowest wins:
        raw_prefill_blocks = active_prefill_blocks + incoming_prompt_blocks
        adjusted_prefill_blocks = max(0, raw_prefill_blocks - overlap_credit_blocks)
        potential_decode_blocks = active_decode_blocks + incoming_active_blocks
        active_request_blocks = decode_active_request_weight * active_requests
        cost = prefill_load_scale * adjusted_prefill_blocks
               + potential_decode_blocks + active_request_blocks
    overlap_credit_decay shrinks the device-local credit by 1/(1 + decay * normalized
    excess active prefill), where the excess is measured against the least-loaded
    candidate and normalized by the incoming request size."""
    credit = np.full(matched.shape, float(overlap_score_credit))
    if overlap_credit_decay:
        excess = np.maximum(0.0, active_prefill - active_prefill.min()) / max(req_blocks, 1)
        credit = credit / (1.0 + overlap_credit_decay * excess)
    adjusted = np.maximum(0.0, active_prefill + req_blocks - credit * matched)
    potential_decode = active_decode + incoming_active_blocks
    return (prefill_load_scale * adjusted + potential_decode
            + decode_active_request_weight * active_requests)


# The decay is documented as halving device credit at one request-equivalent of excess
# prefill load. Reproduce that exactly: replica 1 carries 8 blocks of excess prefill on an
# 8-block request, so its 6 matched blocks are credited as 3.
m2 = np.array([6, 6])
ap = np.array([0.0, 8.0])
plain = dynamo_cost(m2, 8, ap, np.zeros(2), overlap_credit_decay=0.0)
decayed = dynamo_cost(m2, 8, ap, np.zeros(2), overlap_credit_decay=1.0)
assert plain[1] == max(0.0, 8 + 8 - 6) and decayed[1] == max(0.0, 8 + 8 - 3)
assert plain[0] == decayed[0]                  # the least-loaded candidate is never decayed
# incoming_active_blocks is identical for every candidate of a given request, so it shifts
# the whole cost vector and can never change the argmin. That is why it is invisible in the
# placement results below, and why a router that drops it still ranks replicas correctly.
shifted = dynamo_cost(m2, 8, ap, np.zeros(2), incoming_active_blocks=4.0)
assert np.allclose(shifted - plain, 4.0)


def simulate(policy, n_sessions=48, turns=3, credit=1.0, decay=0.0, seed=7):
    """One shared system prompt, n_sessions independent conversations, each growing by a
    turn at a time (an agent trace resends turns 0..t-1 verbatim). Replica 0 is warmed with
    the system prompt only, which is all pure affinity needs to herd. Backlogs accumulate
    over the batch, so max(backlog) is the makespan of one rollout step."""
    r = np.random.default_rng(seed)
    ix = PrefixIndex(N_REP)
    prefill_backlog = np.zeros(N_REP)
    decode_backlog = np.zeros(N_REP)
    placed = np.zeros(N_REP, dtype=int)
    convo = [shared_sys + list(r.integers(0, 50_000, size=int(r.integers(3, 10)) * BLOCK))
             for _ in range(n_sessions)]
    first_replica, sticky, later_turns = {}, 0, 0
    ix.block_stored(0, block_hashes(shared_sys))                # replica 0 saw it first
    for t in range(turns):
        for s in range(n_sessions):
            if t:
                convo[s] = convo[s] + list(r.integers(0, 50_000, size=2 * BLOCK))
            hs = block_hashes(convo[s])
            req_blocks = len(hs)
            m = ix.matched_blocks(hs)
            if policy == "pure_affinity":
                pick = int(np.lexsort((np.arange(N_REP), -m))[0])   # max match, low index wins ties
            else:
                cost = dynamo_cost(m, req_blocks, prefill_backlog, decode_backlog,
                                   incoming_active_blocks=0.5 * req_blocks,
                                   overlap_score_credit=credit, overlap_credit_decay=decay)
                pick = int(np.argmin(cost))
            placed[pick] += 1
            if t == 0:
                first_replica[s] = pick
            else:
                later_turns += 1
                sticky += pick == first_replica[s]
            prefill_backlog[pick] += max(0, req_blocks - m[pick])   # uncached prompt blocks
            decode_backlog[pick] += 0.5 * req_blocks                # blocks the turn will decode
            ix.block_stored(pick, hs)
    return placed, prefill_backlog + decode_backlog, sticky / later_turns, int(placed.sum())


pa_placed, pa_backlog, pa_sticky, n_req = simulate("pure_affinity")
tl_placed, tl_backlog, tl_sticky, _ = simulate("token_load")

# Pure affinity herds: the system prompt is on replica 0, so replica 0 wins every request.
assert pa_placed[0] == n_req and pa_placed[1:].sum() == 0, pa_placed
assert (pa_backlog[1:] == 0).all()
# Token load spreads: no replica takes more than 40% of the stream.
assert tl_placed.max() / n_req < 0.40, tl_placed / n_req
cv_pa = pa_backlog.std() / pa_backlog.mean()
cv_tl = tl_backlog.std() / tl_backlog.mean()
assert cv_tl < 0.10 < cv_pa, (cv_pa, cv_tl)
# Makespan (the slowest replica's backlog) is what sets step time for a batch of rollouts.
speedup = pa_backlog.max() / tl_backlog.max()
assert speedup > 3.0, speedup
# Pure affinity is perfectly "sticky" only because there is one replica left to be sticky to.
assert pa_sticky == 1.0 and pa_placed[0] == n_req
# The balanced rule still keeps most later turns on the replica that already has the history.
assert tl_sticky > 0.60, tl_sticky

# overlap_score_credit=0 is Dynamo's --load-aware preset. It balances just as well but
# throws the cache away, so later turns land on the replica that holds their history no
# more often than chance would put them there.
zero_placed, zero_backlog, zero_sticky, _ = simulate("token_load", credit=0.0)
assert zero_sticky < 0.35 < tl_sticky, (zero_sticky, tl_sticky)
# It spreads placement just as evenly (both coefficients of variation well under 0.05) but
# it pays for the reuse it threw away: its makespan is ~20% worse, not equal.
zero_cv = zero_backlog.std() / zero_backlog.mean()
zero_penalty = zero_backlog.max() / tl_backlog.max()
assert zero_cv < 0.05 and cv_tl < 0.05, (zero_cv, cv_tl)
assert 1.15 < zero_penalty < 1.25, zero_penalty
# Boundary: with zero affinity anywhere, the score degenerates to least-loaded.
cold = PrefixIndex(N_REP)
assert int(np.argmin(dynamo_cost(cold.matched_blocks(block_hashes(base)), 9,
                                 np.array([4.0, 1.0, 9.0, 3.0]), np.zeros(4),
                                 incoming_active_blocks=4.5))) == 1

# ------------------------------------------------- 4. eviction the router never hears about
class LRUEngine:
    """An engine's real GPU-resident block set, capacity-bounded, LRU eviction."""

    def __init__(self, capacity):
        self.capacity = capacity
        self.slots = OrderedDict()

    def admit(self, hashes):
        evicted = []
        for h in hashes:
            if h in self.slots:
                self.slots.move_to_end(h)
                continue
            if len(self.slots) >= self.capacity:
                old, _ = self.slots.popitem(last=False)
                evicted.append(old)
            self.slots[h] = 1
        return evicted

    def real_hit(self, hashes):
        c = 0
        for h in hashes:
            if h not in self.slots:
                break
            c += 1
        return c


def replay(propagate_removals):
    r = np.random.default_rng(3)
    eng = LRUEngine(capacity=60)
    ix = PrefixIndex(1)
    believed = realized = total = 0
    reqs = [shared_sys + list(r.integers(0, 50_000, size=4 * BLOCK)) for _ in range(40)]
    for toks in reqs + reqs:                    # second pass re-requests the same prefixes
        hs = block_hashes(toks)
        believed += int(ix.matched_blocks(hs)[0])
        realized += eng.real_hit(hs)
        total += len(hs)
        ev = eng.admit(hs)
        ix.block_stored(0, hs)
        if propagate_removals:
            ix.block_removed(0, ev)
    return believed, realized, total


b_stale, r_stale, tot = replay(propagate_removals=False)
b_live, r_live, _ = replay(propagate_removals=True)
# Without removal events the router's view is strictly optimistic: it promises hits the
# engine cannot serve, and routes on a number that is simply wrong.
assert (b_stale - r_stale) / tot > 0.20, (b_stale, r_stale, tot)
assert r_stale == r_live, (r_stale, r_live)     # engine behaviour is identical either way
# With removal events wired up, the router's belief matches what the engine will do.
assert b_live == r_live, (b_live, r_live)

print(f"index: fast longest-match == brute force on {len(corpus)} requests x {N_REP} replicas")
print(f"boundary: flip@block3-last={solo.matched_blocks(block_hashes(flip(base, 4 * BLOCK - 1)))[0]} "
      f"flip@block4-first={solo.matched_blocks(block_hashes(flip(base, 4 * BLOCK)))[0]} "
      f"flip@tail={solo.matched_blocks(block_hashes(flip(base, 9 * BLOCK + 3)))[0]} "
      f"prepend-1-token={solo.matched_blocks(block_hashes([7] + base))[0]} (of 9 blocks)")
print(f"decay: 6 matched blocks credited as {(8 + 8 - decayed[1]):.0f} at decay=1 with one "
      f"request-equivalent of excess prefill (was {(8 + 8 - plain[1]):.0f})")
print(f"herding: pure-affinity placement {pa_placed.tolist()} cv(backlog)={cv_pa:.3f}")
print(f"         token-load   placement {tl_placed.tolist()} cv(backlog)={cv_tl:.3f}")
print(f"         makespan {pa_backlog.max():.0f} -> {tl_backlog.max():.0f} blocks "
      f"({speedup:.2f}x), session stickiness {tl_sticky:.1%} "
      f"vs {zero_sticky:.1%} at credit=0")
print(f"         credit=0 spreads as evenly (cv {zero_cv:.3f}) but its makespan is "
      f"{zero_backlog.max():.0f} blocks, {zero_penalty:.2f}x the credit-carrying run")
print(f"stale index: believed {b_stale}/{tot} blocks cached, engine served {r_stale}/{tot} "
      f"({100 * (b_stale - r_stale) / tot:.1f} pts of phantom hit rate); "
      f"with removal events believed {b_live} == served {r_live}")

Executed output:

index: fast longest-match == brute force on 24 requests x 4 replicas
boundary: flip@block3-last=3 flip@block4-first=4 flip@tail=9 prepend-1-token=0 (of 9 blocks)
decay: 6 matched blocks credited as 3 at decay=1 with one request-equivalent of excess prefill (was 6)
herding: pure-affinity placement [144, 0, 0, 0] cv(backlog)=1.732
         token-load   placement [35, 36, 36, 37] cv(backlog)=0.006
         makespan 1346 -> 374 blocks (3.61x), session stickiness 65.6% vs 32.3% at credit=0
         credit=0 spreads as evenly (cv 0.012) but its makespan is 450 blocks, 1.20x the credit-carrying run
stale index: believed 476/640 blocks cached, engine served 316/640 (25.0 pts of phantom hit rate); with removal events believed 316 == served 316

Four results carry over to production reasoning:

The boundary is the block, not the token. A one-token difference at index 63 (last token of block 3, block_size=16) leaves 3 matched blocks; the same difference one token later at index 64 leaves 4. A difference in the trailing partial block changes nothing, because partial blocks are never hashed. And prepending one token, a timestamp or request ID at the top of the system prompt, shifts every boundary and takes the match from 9 blocks to 0. That is the single most common self-inflicted cache-hit-rate loss in agent harnesses.
Pure affinity is an attractor. With the system prompt seeded on one replica and no load term, that replica wins all 144 requests and the other three stay idle: backlog coefficient of variation 1.732, the maximum possible for four replicas. This is what Anyscale calls request herding.¹
The tradeoff is real and asymmetric. The load-aware cost cuts makespan 3.61x in this batch model while still returning 65.6% of later turns to the replica holding their history. Deleting cache awareness entirely (overlap_score_credit = 0) spreads placement just as evenly, coefficient of variation 0.012 against 0.006, but it is not free: stickiness drops to 32.3%, barely above the 25% random placement over four replicas would give, and the makespan it has to finish is 450 blocks against 374, a 1.20x penalty for the prefill it re-does.
An index without eviction events lies, and lies optimistically. Under a capacity-bound LRU engine the router believed 476 of 640 blocks were cached where the engine could serve only 316: 25.0 points of phantom hit rate, all of it in the direction that makes the router over-prefer that replica. Wiring BlockRemoved through makes belief and reality identical.

The batch model in point 3 is a makespan model with monotonically accumulating backlog, matching the RL-rollout framing where the metric is step time. It is not a queueing simulation; the absolute 3.61x is a property of this synthetic workload, not a portable number.

How to use it¶

Reference templates below. Nothing in this section was executed; versions are pinned where upstream pins them.

vLLM engines: emit cache events. KVEventsConfig defaults to enable_kv_cache_events = False, so the router sees nothing until it is turned on. The ZeroMQ publisher default endpoint is tcp://*:5557.⁴ Prefix caching is usually but not unconditionally on: the CacheConfig dataclass default is True, while EngineArgs.enable_prefix_caching starts as None and resolves to model_config.is_prefix_caching_supported, then is forced off on RISC-V CPU platforms. So the served value is model- and platform-dependent, which is why Ray's router guide directs you to set it explicitly in engine_kwargs; set it, because a router whose engines silently have it off produces zero hits and no error.⁵³

# Reference template, not executed here. Per-replica; the router subscribes to each.
vllm serve <model> \
  --enable-prefix-caching \
  --kv-events-config '{"enable_kv_cache_events": true, "publisher": "zmq",
                       "endpoint": "tcp://*:5557",
                       "replay_endpoint": "tcp://*:5558",
                       "buffer_steps": 10000}'

Ray Serve LLM, KVAwareRouter. Alpha as of the current docs. It needs the Dynamo selection service installed (pip install "ai-dynamo>=1.4.0") and three environment variables exported before Serve starts, because it runs on the direct-streaming ingress path and scores on prompt tokens:²

# Reference template, not executed here.
export RAY_SERVE_ENABLE_HA_PROXY=1
export RAY_SERVE_LLM_ENABLE_DIRECT_STREAMING=1
export RAY_SERVE_INGRESS_REQUEST_ROUTER_FORWARD_BODY=1

# Reference template, not executed here. Ray Serve LLM (Ray master docs, retrieved 2026-08-26).
from ray import serve
from ray.serve.config import RequestRouterConfig
from ray.serve.llm import LLMConfig, build_openai_app
from ray.serve.llm.request_router import KVAwareRouter

llm_config = LLMConfig(
    model_loading_config={"model_id": "qwen3-0.6b", "model_source": "Qwen/Qwen3-0.6B"},
    deployment_config={
        "autoscaling_config": {"min_replicas": 2, "max_replicas": 2},
        "request_router_config": RequestRouterConfig(request_router_class=KVAwareRouter),
    },
    # Scoring weights reach the selection service as DYN_* env vars on the ingress replicas.
    runtime_env={"env_vars": {"DYN_ROUTER_PREFILL_LOAD_SCALE": "2.0"}},
)
serve.run(build_openai_app({"llm_configs": [llm_config]}))

Ray Serve LLM, PrefixCacheAffinityRouter. The text-based tier, no Dynamo dependency. Its documented policy has four branches, not three: if the max-minus-min queue length exceeds imbalanced_threshold it abandons affinity and falls back to power of two choices; otherwise it routes on the prefix tree if the match rate is at least match_rate_threshold (default 0.1); below that it routes to the "lowest prefix cache utilization" replica, which in the source means the tenant holding the fewest characters in the shared tree (get_smallest_tenants over tenant_to_char_count); and with no prefix data at all it falls back to power of two choices again. Defaults: imbalanced_threshold infinity, do_eviction False, eviction_threshold_chars 400,000, eviction_target_chars 360,000, eviction_interval_secs 10.³ The default imbalanced_threshold of infinity means the load-balance escape hatch is off unless configured, which is exactly the herding case in the executed block.

SGLang. The router was renamed from sgl-router/ to sgl-model-gateway/ in the SGLang repo (sgl-router/ now 404s upstream), though the PyPI package is still sglang-router.⁸ Its cache_aware policy (the default) keeps an approximate radix tree per worker keyed on raw text characters, not token IDs, deliberately, "to avoid tokenization overhead"; match rate is matched_char_count / input_char_count.⁸ That makes it the approximate tier, comparable to Ray's PrefixCacheAffinityRouter, not to KVAwareRouter. Defaults read from source at commit 8005df6: --cache-threshold 0.3, --balance-abs-threshold 64, --balance-rel-threshold 1.5, --max-tree-size 67108864. The eviction-cadence flag is spelled differently by the two entry points: the Rust binary takes --eviction-interval (default 120), the Python launcher takes --eviction-interval-secs (default 60).⁸ The engine-side structure this pairs with is RadixAttention, whose tree keys on token sequences with a one-token page size and evicts LRU leaf-first with reference counts.⁹

llm-d. The equivalent lives in the Endpoint Picker as plugins: a precise-prefix-cache-producer (configured with tokenProcessorConfig.blockSizeTokens) or the default approx-prefix-cache-producer, feeding a prefix-cache-scorer whose weight is combined with other scorers by a max-score-picker.¹⁰ Scorer weight defaults to 1.0 when omitted; the upstream example uses weight: 50.¹⁰ Both producers share one hashing path over token IDs; the difference is where the index comes from, and the approximate one carries a blockSizeTokens floor of 64 tokens to bound the per-(pod, block) LRU, which is four times coarser than vLLM's own block size.¹¹

The engine-side settings every one of these depends on are in KV cache management; what a hit is actually worth in latency terms is in KV cache inference speedup.

How to develop with it¶

Test the index against a brute-force reference, not against itself. The single-descent query in the executed block is only correct because a replica must hold blocks 1..d-1 to serve block d. The interior-hole case is the one that catches an implementation that treats the per-replica block set as unordered.
Decide the tokenizer boundary first. KV-aware routing scores on token IDs, so the ingress must tokenize with the same renderer and chat template as the engine, or the hashes will not match. Ray sends the tokenized prompt onward so the engine does not re-tokenize, staging it on a separate channel; delivery is best effort and the engine re-tokenizes if the payload is missing or expired.² A chat-template mismatch between ingress and engine produces silent zero hit rate, not an error.
Match the extra-key set. vLLM folds LoRA name, multimodal identifiers, and cache_salt into the block hash via extra_keys, and BlockStored exposes them per block precisely so an external consumer can reconstruct the hash.⁴ A router that hashes tokens only will collide across tenants; see tenant cache isolation.
Do not assume block size 16. It is CacheConfig.DEFAULT_BLOCK_SIZE, overridable per deployment, and vLLM additionally exposes prefix_match_unit, a finer match granularity that may differ from the physical block size as long as every group's block_size is divisible by it.⁵ Read block_size off the BlockStored event rather than hardcoding it.⁴
Benchmark with a workload that has heterogeneous sessions. A synthetic load where every request is the same length cannot distinguish session affinity from token-load awareness, which is precisely Anyscale's third "prefer consistent hashing" condition.¹

How to maintain it¶

Watch hit rate and load balance as a pair. A router change that raises prefix-cache hit rate and raises tail latency is a regression. Anyscale's own case-study framing is the reverse trade: KVAwareRouter "trades some prefix cache hit rate for better token load balance".¹ Track per-replica active-decode-block dispersion alongside hit rate.
Re-tune after every autoscale change. overlap_score_credit_decay exists specifically to stop "busy, cache-rich workers from repeatedly winning while newly autoscaled or lightly loaded workers receive too little traffic."⁷ A fleet that scales out under load without decay will send the new replicas nothing.
Treat the scoring weights as workload-specific. prefill_load_scale up for prefill-heavy traffic, down for decode-heavy; decode_active_request_weight (default 0) up when many small requests concentrate; overlap_score_credit to 0 to disable cache awareness entirely.²⁷ There is no single good setting.
Check for deprecated knobs during upgrades. Dynamo still accepts --router-kv-overlap-score-weight / DYN_ROUTER_KV_OVERLAP_SCORE_WEIGHT but warns; nonzero legacy values map to prefill_load_scale, and a legacy 0 maps to both prefill_load_scale=0 and overlap_score_credit=0. The precedence is asymmetric: a present legacy value always overrides an explicit prefill_load_scale, but it only overrides an explicit overlap_score_credit when the legacy value is 0. Dynamo's own test asserts an explicit overlap_score_credit: 0.5 survives alongside a legacy weight of 2.5.⁷ Either way it is a silent-override trap during a partial migration.
Re-derive the block-size assumption after an engine upgrade. A change to block_size or prefix_match_unit invalidates every hash the router has cached.

How to run it in production¶

Size the ingress tier. Tokenization and scoring are the ingress's CPU cost. Ray runs one ingress replica per proxy node by default and exposes RAY_SERVE_INGRESS_ROUTER_REPLICAS_PER_NODE; the guidance is that "Two per node is usually enough, though the right number depends on your traffic."²
Expect eventual consistency, and design for it. Ray replicates the router and shares token-load updates asynchronously, so "an ingress replica may briefly make routing decisions based on a slightly stale KV cache or token load view."² Two routers can send two requests to the same replica within one sync interval. Budget headroom rather than assuming a single consistent view.
Watch for body truncation. With RAY_SERVE_INGRESS_REQUEST_ROUTER_FORWARD_BODY=1, HAProxy forwards only up to RAY_SERVE_HAPROXY_INGRESS_REQUEST_ROUTER_BUFSIZE (256 KiB default) and truncates larger bodies, so long-context requests get scored on a prefix of themselves. The counter serve_haproxy_ingress_router_truncations_total is the signal; raising the buffer costs HAProxy memory and can delay routing and TTFT.² Long-context agent traffic hits this first.
Alert on the event stream, not just the request path. The vLLM ZeroMQ publisher has a high-water mark (hwm, default 100,000) after which "events will start dropping if the consumer is not keeping up", and a bounded in-memory queue (max_queue_size, default 100,000).⁴ Dropped events do not fail a request; they silently corrupt the index. Batches are sequence-numbered and the optional replay_endpoint (a ZeroMQ ROUTER socket, buffer_steps batches deep, default 10,000) lets a subscriber request missed batches by starting sequence number.⁴ Configure it, monitor for sequence gaps, and rebuild the index on AllBlocksCleared.
Have a fallback policy. If the index is cold, empty, or unreachable, the score must degenerate to least-loaded rather than to "always replica 0". The executed block asserts that boundary. The PrefixCacheAffinityRouter equivalent is its power-of-two-choices fallback.³
Do not deploy it in front of disaggregated or data-parallel pools yet. Both are listed as unsupported and planned in the current Ray docs.²

Reading the Anyscale numbers¶

The post that motivated this page reports two experiments. Both are Anyscale's own benchmarks, run by Anyscale and NVIDIA authors on Ray Serve LLM, and every quantitative result in both is presented only in figures: Figure 4 for the RL rollout comparison, Figure 8 for the Claude Code replay. (Figure 7 is not a result; it characterises the replay workload, "Distribution of Weka Claude Code replay requests and reconstructed sessions".) The prose does carry the synthetic workload's own parameters, quoted below, but no numbers for TTFT, TPOT, throughput, hit rate, or latency, and no hardware, replica count, or absolute values. Nothing from those figures is reproduced on this page. What the prose does specify:

Experiment 1, a synthetic asynchronous multi-turn RL rollout with stragglers. Two bullets define the shape: "Each step runs eight rollouts, with 10 turns per rollout" and "Each rollout starts with a 2K-token input, and each turn generates 1K tokens, except for two stragglers whose final turn generates 8K tokens." Three routers compared at concurrency=16, using p99 end-to-end rollout latency as a proxy for step time. The stated outcome is directional: "KVAwareRouter has the best p99 rollout end-to-end latency despite lower prefix cache hit rate."¹
Experiment 2, a Claude Code trace replay. "a filtered subset of the Weka Claude Code trace corpus that fits within the context window of gpt-oss-120b", compared against session affinity with consistent hashing. Stated outcome, again directional: better TTFT, TPOT, and throughput.¹

Two methodological caveats come from Anyscale's own footnote and should travel with any citation of these results: the reported prefix-cache hit rate is "the token-weighted ratio of vLLM-reported cached prompt tokens to total prompt tokens, computed over requests with both usage fields available" (so requests missing a usage field are excluded), and the decode-block coefficient of variation is "an offline reconstruction of per-replica decoding KV-block imbalance" in 0.5-second bins, not an engine-reported metric.¹ The PureKVCacheAffinityRouter used as the herding baseline is described by the post only as a router "which modifies KVAwareRouter to optimize solely for KV cache overlap"; reading that as a benchmark-only variant rather than a shipping product is this page's inference, not the post's statement.¹

The post's "Reproduction Notes" link to benchmark code points at ray-project/ray PR #65665, which was still open and unmerged with an empty (unedited template) description when checked on 2026-08-26. Treat the benchmarks as not independently reproducible from the post as published.¹²

Failure modes¶

Symptom	Cause	What to do
One replica at 100% GPU, the rest idle, cache hit rate excellent	Request herding: pure affinity, or `imbalanced_threshold` left at its default of infinity	Add a load term; set `overlap_score_credit_decay > 0`; set a finite `imbalanced_threshold`³⁷
Hit rate collapses at high concurrency, router's own metric still looks fine	Engine evicting under KV pressure while the router index is not eviction-aware	Move from a text prefix tree to real `BlockRemoved` events; verify with the stale-index test above¹⁴
Hit rate near zero despite obviously shared prompts	Ingress tokenizer or chat template differs from the engine's, so hashes never match; or a per-request timestamp/UUID sits at the top of the system prompt	Pin the same renderer and template; move volatile fields to the end of the prompt (the prepend test above goes from 9 matched blocks to 0)
Hit rate degrades only for the longest requests	HAProxy body truncation at `RAY_SERVE_HAPROXY_INGRESS_REQUEST_ROUTER_BUFSIZE`	Check `serve_haproxy_ingress_router_truncations_total`, raise the buffer, accept the memory and TTFT cost²
Router index grows without bound, ingress RSS climbs	No eviction on the router's own tree	Enable `do_eviction` and size `eviction_threshold_chars` / `eviction_target_chars`, or use event-driven removal³
Routing quality degrades slowly after an incident, never recovers	ZeroMQ event drops past `hwm`, never replayed	Configure `replay_endpoint`, alert on sequence gaps, rebuild on `AllBlocksCleared`⁴
Two routers pick the same replica simultaneously under burst	Eventually consistent load view across ingress replicas	Expected behaviour; leave headroom, or reduce ingress replica count at the cost of scoring throughput²
Cross-tenant cache hits	Router hashes token IDs without `extra_keys` / `cache_salt`	Include the engine's extra keys in the routing hash; see tenant cache isolation⁴
Tail latency worsens after enabling KV-aware routing on uniform traffic	Scoring overhead with no reuse to find	Revert to round robin; Ray lists this as the policy's cost²

References¶

Anyscale, "Optimizing LLM Serving Efficiency: Moving Beyond KV Cache Reuse to Token-Load Awareness with Ray Serve LLM", 2026-08-25 — https://www.anyscale.com/blog/llm-kv-token-aware-routing (retrieved 2026-08-26)
Ray Serve LLM, "KV-aware routing" (Ray 3.0.0.dev0 / master docs) — https://docs.ray.io/en/master/serve/llm/user-guides/kv-aware-routing.html (retrieved 2026-08-26)
Ray Serve LLM, "Prefix-aware routing" — https://docs.ray.io/en/master/serve/llm/user-guides/prefix-aware-routing.html (retrieved 2026-08-26)
Ray Serve LLM, "KV cache offloading" — https://docs.ray.io/en/master/serve/llm/user-guides/kv-cache-offloading.html (retrieved 2026-08-26)
vLLM, "Automatic Prefix Caching" design doc (block hashing, --prefix-caching-hash-algo, cache_salt) — https://docs.vllm.ai/en/latest/design/prefix_caching.html (retrieved 2026-08-26)
vLLM source, vllm/distributed/kv_events.py (BlockStored, BlockRemoved, AllBlocksCleared, ZmqEventPublisher, replay socket) — https://github.com/vllm-project/vllm/blob/main/vllm/distributed/kv_events.py (retrieved 2026-08-26, main)
vLLM source, vllm/config/kv_events.py (KVEventsConfig defaults) — https://github.com/vllm-project/vllm/blob/main/vllm/config/kv_events.py (retrieved 2026-08-26, main)
vLLM source, vllm/config/cache.py (DEFAULT_BLOCK_SIZE = 16, prefix_match_unit) — https://github.com/vllm-project/vllm/blob/main/vllm/config/cache.py (retrieved 2026-08-26, main)
NVIDIA Dynamo docs, "Routing Concepts" (the cost formula) — https://github.com/ai-dynamo/dynamo/blob/main/docs/fern/pages/developer-guide/knowledge-base/modular-components/router/routing-concepts.md (retrieved 2026-08-26, main)
vLLM source, vllm/v1/core/kv_cache_utils.py (hash_block_tokens, NONE_HASH, cache_salt in block 0 only) — https://github.com/vllm-project/vllm/blob/main/vllm/v1/core/kv_cache_utils.py (retrieved 2026-08-26, main)
vLLM source, vllm/engine/arg_utils.py (enable_prefix_caching resolved from model_config.is_prefix_caching_supported) — https://github.com/vllm-project/vllm/blob/main/vllm/engine/arg_utils.py (retrieved 2026-08-26, main)
NVIDIA Dynamo source, lib/kv-router/src/scheduling/config.rs (apply_deprecated_overlap_score_weight_override and its tests) — https://github.com/ai-dynamo/dynamo/blob/main/lib/kv-router/src/scheduling/config.rs (retrieved 2026-08-26, main)
NVIDIA Dynamo source, components/src/dynamo/common/configuration/groups/kv_router_args.py (_LOAD_AWARE_KWARG_OVERRIDES) — https://github.com/ai-dynamo/dynamo/blob/main/components/src/dynamo/common/configuration/groups/kv_router_args.py (retrieved 2026-08-26, main)
Ray source, python/ray/llm/_internal/serve/routing_policies/prefix_aware/ (prefix_aware_router.py, prefix_tree.py) — https://github.com/ray-project/ray/tree/master/python/ray/llm/_internal/serve/routing_policies/prefix_aware (retrieved 2026-08-26, master)
llm-d inference scheduler source, pkg/epp/framework/plugins/requestcontrol/dataproducer/ (prefixhash/hashing.go, approximateprefix/indexer.go) — https://github.com/llm-d/llm-d-inference-scheduler/tree/531f889ff651f7b40480007d226e9f1a7f6b6e81/pkg/epp/framework/plugins/requestcontrol/dataproducer (retrieved 2026-08-26)
NVIDIA Dynamo docs, "Configuration and Tuning" (--router-kv-overlap-score-credit, decay, --load-aware, deprecations) — https://github.com/ai-dynamo/dynamo/blob/main/docs/fern/pages/developer-guide/knowledge-base/modular-components/router/configuration-and-tuning.md (retrieved 2026-08-26, main)
NVIDIA Dynamo product page — https://developer.nvidia.com/dynamo (retrieved 2026-08-26)
SGLang model gateway docs (routing policies and flag table) — https://docs.sglang.io/docs/advanced_features/sgl_model_gateway (retrieved 2026-08-26)
SGLang source, sgl-model-gateway/src/policies/cache_aware.rs — https://github.com/sgl-project/sglang/blob/8005df61d32ccbd4d3f3034c7b9af9bc54dcd5dd/sgl-model-gateway/src/policies/cache_aware.rs (retrieved 2026-08-26)
Zheng et al., "SGLang: Efficient Execution of Structured Language Model Programs", NeurIPS 2024, arXiv:2312.07104 — https://arxiv.org/abs/2312.07104
llm-d inference scheduler architecture (prefix-cache-scorer, precise-prefix-cache-producer, max-score-picker) — https://github.com/llm-d/llm-d-inference-scheduler/blob/main/docs/architecture.md (retrieved 2026-08-26, main)
Weka Claude Code trace corpus used in the Anyscale case study — https://huggingface.co/datasets/semianalysisai/cc-traces-weka-062126-256k (retrieved 2026-08-26)
ray-project/ray PR #65665, "[docs] KV cache & token aware routing blog post benchmarks" (open, unmerged as of 2026-08-26) — https://github.com/ray-project/ray/pull/65665

Anyscale blog, sections "Naive Optimization: Maximize KV Cache Reuse", "Request Herding", "Beyond KV Cache Reuse: Token Load Awareness Matters More", "Case Study: Replaying Claude Code Traces", and the starred footnote following the case study. The three "prefer consistent hashing" conditions are quoted verbatim on this page: "Cache misses are particularly expensive", "Cross-session KV cache reuse is limited", and "Sessions have similar workloads". Retrieved 2026-08-26; the post's text was re-fetched and searched for a numeric session-heterogeneity threshold, and it contains none. ↩↩↩↩↩↩↩↩↩↩↩↩
Ray Serve LLM "KV-aware routing" guide (also read as doc/source/serve/llm/user-guides/kv-aware-routing.md at Ray master), sections "When to use KV-aware routing", "Installation", "Configuration", "Tuning", "How a replica is chosen", "Tokenization at the ingress", "Scaling the ingress tier", "Limitations". The page carries an alpha warning: "KVAwareRouter is in alpha and may change before becoming stable." The session-ID header is not hardcoded: python/ray/llm/_internal/serve/core/ingress/router.py reads RAY_SERVE_SESSION_ID_HEADER_KEY with x-session-id as its default. Retrieved 2026-08-26 from the master docs build (Ray 3.0.0.dev0), so these names are unpinned and can drift. ↩↩↩↩↩↩↩↩↩↩↩↩↩↩↩
Ray Serve LLM "Prefix-aware routing" guide, sections "How it works" (1. Load balance check, 2. Prefix matching strategy, 3. Imbalanced load fallback), "Configuration parameters", "Best practices". Step 2 itself has three outcomes, which is why this page counts four branches rather than the guide's three headings: "High match rate (>=10%)", "Low match rate (<10%): Falls back to replicas with the lowest prefix cache utilization to increase utilization", and "No prefix data: Uses the default Power of Two Choices selection". "Lowest prefix cache utilization" resolves in python/ray/llm/_internal/serve/routing_policies/prefix_aware/prefix_tree.py::get_smallest_tenants, documented as "Get the tenants with the smallest total character count" and computed as the minimum over tenant_to_char_count. Also alpha. Retrieved 2026-08-26 (docs) and read at Ray master commit b54b47c994517d1cb34e209bccc6dba2fe70990a (source). ↩↩↩↩↩↩
vLLM main: vllm/config/kv_events.py (enable_kv_cache_events: bool = False, endpoint: str = "tcp://*:5557", buffer_steps: int = 10_000, hwm: int = 100_000, max_queue_size: int = 100_000) and vllm/distributed/kv_events.py (event dataclasses; ZmqEventPublisher docstring: "subscribers can request missed batches by sending the starting sequence number as an 8-byte big-endian integer"). Retrieved 2026-08-26. ↩↩↩↩↩↩↩↩↩
vLLM main, vllm/config/cache.py: DEFAULT_BLOCK_SIZE: ClassVar[int] = 16, applied by _apply_block_size_default when block_size is None; enable_prefix_caching: bool = True is the dataclass default only. vllm/engine/arg_utils.py declares enable_prefix_caching: bool | None = None and _set_default_chunked_prefill_and_prefix_caching_args resolves None to model_config.is_prefix_caching_supported, then forces False on RISC-V CPUs, so the effective default is model- and platform-dependent. The real hash is hash_function((parent_block_hash, curr_block_token_ids_tuple, extra_keys)) in vllm/v1/core/kv_cache_utils.py::hash_block_tokens (a serialized tuple, pickled under sha256 or CBOR under sha256_cbor, not a byte concatenation), rooted at NONE_HASH when the parent is falsy; _gen_extra_hash_keys adds request.cache_salt only when start_token_idx == 0. The CLI flags --enable-prefix-caching and --kv-events-config are registered in vllm/engine/arg_utils.py at the same commit. prefix_match_unit is documented there as "The finest token boundary (in tokens) a prefix-cache hit can land on ... It controls matching granularity only, not how often states are stored." Retrieved 2026-08-26. ↩↩↩
NVIDIA Dynamo, docs/.../router/routing-concepts.md, section "Cost Calculation". The formula block is quoted verbatim on this page. Retrieved 2026-08-26 from main. ↩↩
NVIDIA Dynamo, docs/.../router/configuration-and-tuning.md. Defaults quoted: --router-kv-overlap-score-credit 1.0, --router-kv-overlap-score-credit-decay 0, --router-prefill-load-scale 1, --router-decode-active-request-weight 0, --router-host-cache-hit-weight 0.75. Ray Serve LLM surfaces the same four as DYN_ROUTER_PREFILL_LOAD_SCALE, DYN_ROUTER_KV_OVERLAP_SCORE_CREDIT, DYN_ROUTER_KV_OVERLAP_SCORE_CREDIT_DECAY, DYN_ROUTER_DECODE_ACTIVE_REQUEST_WEIGHT with matching defaults. The --load-aware preset's ten overwritten fields are _LOAD_AWARE_KWARG_OVERRIDES in components/src/dynamo/common/configuration/groups/kv_router_args.py: overlap_score_credit=0.0, use_kv_events=False, router_track_active_blocks=True, router_assume_kv_reuse=False, router_track_prefill_tokens=True, use_remote_indexer=False, serve_indexer=False, shared_cache_multiplier=0.0, shared_cache_type="none", router_predicted_ttl_secs=None. The deprecation precedence is apply_deprecated_overlap_score_weight_override in lib/kv-router/src/scheduling/config.rs, which sets *prefill_load_scale = value unconditionally and *overlap_score_credit = 0.0 only if value == 0.0; the test test_kv_router_config_deprecated_overlap_weight_overrides_canonical_fields asserts that {"overlap_score_weight":2.5,"overlap_score_credit":0.5,"prefill_load_scale":3.0} yields credit 0.5 and scale 2.5. Retrieved 2026-08-26 from main. ↩↩↩↩↩↩↩
SGLang at main commit 8005df61d32ccbd4d3f3034c7b9af9bc54dcd5dd, retrieved 2026-08-26. Imbalance test, sgl-model-gateway/src/policies/cache_aware.rs: let is_imbalanced = max_load.saturating_sub(min_load) > self.config.balance_abs_threshold && (max_load as f32) > (min_load as f32 * self.config.balance_rel_threshold);. Character keying is stated in the same file's header ("The tree stores raw text characters instead of token IDs to avoid tokenization overhead") and used at the match-rate computation. Two source-level inconsistencies found and not resolved upstream: (a) that header comment says a below-threshold match routes "to the worker with smallest tree size", while the code routes to minimum load with a random tie-break; (b) the published docs table lists --eviction-interval-secs with default 120, but 120 is the Rust binary's default for its differently-named --eviction-interval (src/main.rs), and the Python launcher that actually owns the -secs spelling defaults to 60 (bindings/python/src/sglang_router/router_args.py). Quote the parser you are using, not the docs table. Older SGLang releases still ship the pre-rename sgl-router/ path. ↩↩↩↩
Zheng et al., "SGLang: Efficient Execution of Structured Language Model Programs", arXiv:2312.07104, NeurIPS 2024. RadixAttention keys on token sequences "stored in a non-contiguous, paged layout, where the size of each page is equivalent to one token", with LRU leaf-first eviction and per-node reference counts. Attributed to the paper: the current engine has since grown several cache variants and this page does not assert that the shipping code still matches the paper. ↩
llm-d inference scheduler, docs/architecture.md, sections "Filters, Scorers, and the Data Layer", the EndpointPickerConfig example, and "Default plugins" ("A scorer's weight defaults to 1.0 when omitted"). Retrieved 2026-08-26 from main. ↩↩
llm-d/llm-d-inference-scheduler at commit 531f889ff651f7b40480007d226e9f1a7f6b6e81 (2026-08-26). pkg/epp/framework/plugins/requestcontrol/dataproducer/prefixhash/hashing.go defines type HashBlock struct { Tokens []uint32 } hashed with xxhash.Sum64, and GetBlockHashes requires "request.Body.TokenizedRequest to be populated by a token-producer backend", chaining as "hash(block i content, hash(i-1))" with the model name and cache salt folded into each prompt's first block. The character-based knob is marked "Deprecated: Legacy block size defined in number of characters" in approximateprefix/types.go, whose live default is defaultBlockSizeTokens = 16; plugin.go then raises anything below minBlockSizeTokens = 64 to 64. approximateprefix/indexer.go is hashToPods map[blockHash]podSet plus podToLRU map[ServerID]*lru.Cache[blockHash, struct{}], not a tree. The index is written in PreRequest, from schedulingResult.ProfileResults[...].TargetEndpoints, i.e. from the scheduler's own dispatch rather than from engine cache events, which is the sense in which it is approximate. ↩↩
GitHub API for ray-project/ray PR 65665 on 2026-08-26 returned "state": "open", "merged": false, "merged_at": null, and a body consisting only of the unedited PR template. ↩