Session Affinity

Notes

Session affinity is the serving policy that routes all turns of an interactive trajectory to the same decode replica, or at least to a replica that already holds the trajectory’s reusable prefix state, instead of load-balancing each HTTP request independently. For a session $s$ with turns $t=\mathrm{1..}T$, let $P_t$ be the token prefix of turn $t$ that is identical to material already prefetched or decoded on some worker, and $N_t$ the total prefill input tokens for that turn. The session-level prefix-cache hit rate is $H_s=\frac{{\sum }_t|P_t|}{{\sum }_t{N}_t}$, but the scheduling objective is not just a scalar hit rate: the avoided work is approximately ${\sum }_t|P_t|\cdot L\cdot c_{\text{attn+mlp}}$ plus avoided KV writes, and the latency penalty on a miss is bounded below by $T_{\text{prefill miss}}\ge \frac{\text{bytes read for weights and activations}}{\text{effective bandwidth}}$. In agent serving, the second turn often contains the full chat transcript, tool outputs, and system prompt; if it lands on a cold replica, the prefix cache is semantically available in the cluster but physically absent where the request runs. vLLM’s PagedAttention paper and implementation made block-granular KV reuse practical, SGLang’s RadixAttention paper made tree-structured prefix matching explicit, and TensorRT-LLM’s inflight batching and KV cache reuse features expose the same issue at engine level.

A concrete measurement loop is to log, per session turn, the canonicalized token IDs submitted to prefill, the block hashes found in the local prefix cache, and the worker chosen by the router. Suppose an agent trajectory starts with a 1,200-token system/developer prefix plus a 3,000-token user document, then the model emits 700 tokens; the second turn sends the same 4,200-token prefix, the 700-token assistant answer, and a 200-token follow-up, so $N_2=5,100$ and the reusable prefix is $P_2=4,900$ if the same replica still has the blocks. If request-level round-robin sends turn 2 to a different replica, $|P_2|=0$ locally and the measured two-turn hit rate falls from $H_s=\frac{4,900}{4,200+5,100}=52.7\%$ to $0\%$, even though a cluster-wide cache directory would say the data exists. This is why NVIDIA Dynamo’s disaggregated serving release and llm-d’s Kubernetes-oriented inference stack discuss routing and KV locality as placement problems, not merely cache-lookup problems; the cache hit is only useful if it avoids prefill on the GPU that is about to decode.

The miss cost can be carried through with realistic numbers. Take a 70B FP16 model on one 80GB H100 with $3.35$ TB/s HBM bandwidth, grouped-query attention with $8$ KV heads and head dimension $128$, and assume $80$ transformer layers. The KV stored per token is $2\text{ tensors}\times 8\text{ heads}\times 128\text{ dim}\times 2\text{ bytes}\times 80=327,680$ bytes, about $320$ KiB/token, so caching the 4,900-token prefix occupies $4,900\times 327,680=1.606\times 10^9$ bytes, or about $1.50$ GiB. The weights are roughly $70\text{B}\times 2=140$ GB, so a prefill microbatch that cannot reuse the prefix must stream very large fractions of the model while computing 4,900 extra token positions. A crude lower bound from weights alone is $140\text{ GB}/3.35\text{ TB/s}=41.8$ ms for one full pass, but prefill is not a single token pass; attention and MLP matmuls over thousands of tokens make the actual penalty commonly hundreds of milliseconds depending on batching and tensor parallelism. The affinity win is therefore trading about $1.5$ GiB of resident KV and some routing constraint for eliminating thousands of prompt-token forwards on turn 2.

The arithmetic also shows where affinity stops working. If the active session count per replica is high enough that sticky placement keeps cold but reserved KV resident, the cache becomes a memory-fragmentation and admission-control problem: with the same 70B example, an 80GB H100 cannot hold $140$ GB of FP16 weights on one GPU at all, and even under tensor parallel sharding the KV budget may be only tens of GiB after weights, CUDA graphs, workspaces, and fragmentation. At $1.50$ GiB per 4,900-token session prefix, $20$ GiB of usable KV holds only about $13$ such sessions before eviction; pinning the session to a replica after its blocks have been evicted buys nothing and can make queueing worse than a cold prefill elsewhere. Affinity is also harmful when turns are separated by minutes and the reuse probability $p_{\text{return}}$ is lower than the probability that the blocks survive eviction, or when a replica is saturated decoding long generations and another replica is idle. A practical router should compare $p_{\text{hit}}\cdot T_{\text{saved}}$ against the observed extra queueing delay $\Delta Q$ from stickiness, and break affinity when $\Delta Q>p_{\text{hit}}{T}_{\text{saved}}$.

The implementation details are system-specific. In vLLM, the relevant unit is the PagedAttention block, introduced in the vLLM SOSP 2023 paper “Efficient Memory Management for Large Language Model Serving with PagedAttention”; session affinity should route by a stable session key to a worker whose block table contains the chat prefix hashes, while prefix caching verifies exact token-block equality. In SGLang, the RadixAttention paper and runtime organize shared prefixes in a radix tree, so the scheduler can observe the longest-prefix match for an agent state and prefer that executor. TensorRT-LLM’s paged KV cache, in-flight batching, and KV reuse support from NVIDIA’s TensorRT-LLM releases give the engine primitives, but the front-end still needs to preserve session locality unless Dynamo is used to coordinate prefill/decode placement and KV transfer. llm-d, from the Kubernetes-native LLM serving effort, makes this visible at cluster scope: a Gateway or scheduler can choose among pods using prefix-cache metrics rather than treating all replicas as interchangeable. FlashAttention is adjacent rather than a router: the Dao et al. FlashAttention papers reduce the IO cost of attention within prefill/decode, but they do not remove the cost of recomputing a prefix that was cached on the wrong worker.

For a walkthrough, run one real agent trajectory twice and report per-turn locality rather than aggregate server QPS. First, disable sticky routing and send turn 1 and turn 2 through the normal load balancer; collect worker ID, input token count, matched prefix tokens, prefill time, decode time, and KV-cache bytes allocated. Then force a cookie, header, or scheduler key such as $\text{session\_id}$ so both turns land on the same vLLM, SGLang, TensorRT-LLM, Dynamo, or llm-d-backed replica, and repeat with identical tokenization and sampling disabled. The table should make the failure mode obvious: turn 1 has no prefix hit in either run; turn 2 has a large local prefix hit only in the affinity run; the latency delta is concentrated in prefill, not decode. If speculative decoding with EAGLE, from “EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty,” is enabled, keep it fixed across both runs, because EAGLE changes accepted draft tokens during decode but does not make a cold replica know the prior turn’s KV. The lesson is operationally precise: schedule the session state, not the stateless request envelope, and price every misplaced turn as a prefix-cache miss with a measurable token and HBM cost.