Learn AI Create the Future — with Pranay
Main site

Scaling and Traffic Management

Prefix-aware and sticky routing

Sending requests that share a long prompt to the same server lets it reuse work it already did, instead of repeating it.

Read these first

On this page 8
  1. The short answer
  2. The analogy you have already lived
  3. Why it exists
  4. How it works
  5. A real example you have seen
  6. The honest part
  7. Remember this
  8. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

The short answer

Prefix-aware routing sends requests that share the same starting text to the same server. That server can then reuse work it already did, instead of redoing it.

The analogy you have already lived

You have gone back to the same tailor for a second shirt. The tailor already has your measurements written down from last time. They do not measure you all over again. They pull out the same notes and get straight to the cutting.

A new tailor with no notes would have to measure you from scratch. That is real extra time before any cutting starts. The measurements were the expensive part; reusing them is what saves the second visit.

Why it exists

Large language models process every word of a prompt before they can answer. That includes the parts that never change. Think of a long system prompt, a set of instructions, a block of background text pasted at the top of every request.

Two requests can share that same starting text — the prefix. If they land on two different servers, both redo that expensive first pass from nothing. If they land on the same server, that server remembers its earlier work. Only the new part at the end needs processing.

How it works

   request 1: [ long system prompt ] + "what is the refund policy?"
   request 2: [ long system prompt ] + "how do I reset my password?"

   without prefix-aware routing:
     request 1 -> server A   (processes the whole prompt)
     request 2 -> server B   (processes the whole prompt again, from nothing)

   with prefix-aware routing:
     request 1 -> server A   (processes the whole prompt, remembers it)
     request 2 -> server A   (reuses the remembered part, processes only the question)

The "remembering" a server does is called a cache. It is a place the server keeps recent work, so it does not repeat it. Sticky routing is the general name for sending related requests to the same server on purpose. The reason might be a shared prompt prefix, a shared user session, or state that only lives on one machine.

A real example you have seen

A customer-support chat assistant on a shopping app reuses the same long instructions on every conversation. Company policies, tone rules, product categories, all repeated. Prefix-aware routing is why a busy assistant like that answers quickly, even under heavy traffic. Most of each prompt was never new.

The honest part

This only helps when a real, meaningful chunk of traffic actually shares a prefix. A service where every request starts with completely different text gets nothing from this — there is nothing to reuse. Check what your prompts actually look like before reaching for it.

Remember this

  • A long shared prompt prefix is expensive to process once. It is free to reuse, if the same server sees it again.
  • Sticky routing sends related requests to the same machine on purpose, instead of spreading them out evenly.
  • It only pays off when real traffic actually shares real prefixes — measure that before building for it.

What to learn next

Developer — Code and libraries.

Setup

No installs needed beyond the standard library.

Simulating the effect of routing choice on cache reuse

This is a simplified model of the idea, not a real language model. It counts "tokens" (small chunks of text) that would need processing, to compare two routing policies honestly. A real system's savings depend on its actual cache implementation, covered in the researcher section below.

prefix_routing.py
import random

random.seed(4)

NUM_SERVERS = 16
NUM_PREFIXES = 5           # e.g. 5 different system prompts in use
PREFIX_TOKENS = 500         # a long, shared system prompt
SUFFIX_TOKENS_RANGE = (20, 80)  # the part unique to each user message
NUM_REQUESTS = 300

requests = [
    (random.randrange(NUM_PREFIXES), random.randint(*SUFFIX_TOKENS_RANGE))
    for _ in range(NUM_REQUESTS)
]


def simulate(policy):
    # each server "remembers" which prefixes it has already computed and cached
    cached = [set() for _ in range(NUM_SERVERS)]
    tokens_computed = 0
    cache_hits = 0

    for prefix_id, suffix_tokens in requests:
        if policy == "random":
            server = random.randrange(NUM_SERVERS)
        elif policy == "prefix_aware":
            server = hash(prefix_id) % NUM_SERVERS  # same prefix, same server, every time

        if prefix_id in cached[server]:
            cache_hits += 1
            tokens_computed += suffix_tokens              # prefix reused from cache
        else:
            tokens_computed += PREFIX_TOKENS + suffix_tokens
            cached[server].add(prefix_id)

    return tokens_computed, cache_hits


for policy in ["random", "prefix_aware"]:
    tokens, hits = simulate(policy)
    print(f"{policy:13s} tokens computed: {tokens:7d}   prefix cache hits: {hits:3d}/{NUM_REQUESTS}")
Output
random        tokens computed:   52743   prefix cache hits: 224/300
prefix_aware  tokens computed:   17243   prefix cache hits: 295/300

Deterministic with the fixed seed — this reproduces exactly on any machine.

Walking through it

hash(prefix_id) % NUM_SERVERS is the entire routing decision. The same prefix_id always maps to the same server. Once that server has cached a prefix, every future request sharing it lands there and finds it.

Random routing still gets some hits — 224 out of 300 — by accident. With only 5 distinct prefixes spread across 16 servers, chance alone occasionally repeats a server. Prefix-aware routing is not zero reuse versus some reuse. It is accidental reuse versus guaranteed reuse.

Tokens computed is roughly 3x lower with prefix-aware routing — 17,243 against 52,743 — for the same 300 requests. Every token not recomputed is real work a real server did not have to do.

Common mistakes

Treating this as free. Routing by prefix concentrates related traffic onto fewer servers. That can create hotspots — one server handling a popular prefix while others sit idle. It trades even distribution for cache reuse, and that trade is not free.

Hashing the whole prompt instead of only the shared prefix. Two requests with the same system prompt but different user questions must route to the same server. Hashing the entire prompt — including the part that changes — defeats the purpose, because it never produces a repeat.

Never expiring the cache. A server that remembers every prefix it has ever seen, forever, eventually runs out of memory. Real systems evict old entries, usually least-recently-used first — a real cache management problem, not a one-time setup.

Try it yourself

Change NUM_PREFIXES to 20 and rerun, keeping NUM_SERVERS at 16. Watch the gap between the two policies shrink. With more distinct prefixes than servers, even prefix-aware routing cannot stop some servers holding several prefixes.

What to learn next

Researcher — Mathematics and papers.

KV caching, the mechanism this routes around

A transformer's attention mechanism computes a key and value vector for every token it has processed. Caching those vectors — the KV cache — is what lets a model continue generating the next token without recomputing attention over tokens it has already seen. A shared prompt prefix means a shared, reusable stretch of that cache, which is exactly what this lesson's simulation stands in for at a much coarser level.

Radix-tree prefix caching

Production systems implement this far more precisely than the toy hash-based routing above. SGLang (Zheng et al., Efficient Execution of LLM Programs Using RadixAttention, 2023) organises cached prefixes in a radix tree — a tree structure keyed on shared token sequences. This lets any two requests sharing any prefix length find and reuse the longest matching cached prefix automatically, not only a handful of predefined system prompts. vLLM's PagedAttention (Kwon et al., SOSP 2023, also covered in the researcher section of model serving) provides the underlying non-contiguous memory layout that makes storing many partial, reusable caches practical without fragmenting GPU memory.

The routing-versus-caching trade-off, formally

Let $h$ be the hit rate under a given routing policy, $c_p$ the cost of processing a prefix from scratch, and $c_s$ the cost of processing only the suffix. Expected per-request cost is:

$$E[\text{cost}] = h \cdot c_s + (1 - h)(c_p + c_s)$$

Prefix-aware routing raises $h$ directly, by design. Load balancing (the previous lesson) optimises a different quantity — evenness of load across servers — and the two objectives actively conflict: perfect load evenness scatters related requests, which minimises $h$.

Consistent hashing as the routing substrate

The hash(prefix_id) % NUM_SERVERS scheme above breaks badly when NUM_SERVERS changes — every prefix remaps to a new server, invalidating the entire cache at once. Production sticky routers use consistent hashing (Karger et al., STOC 1997, also referenced in the researcher section of load balancing inference traffic) specifically to keep most keys mapped to their original server even as the server count changes.

Papers

  • Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention (vLLM), SOSP 2023 — arxiv.org/abs/2309.06180
  • Zheng et al., Efficiently Programming Large Language Models using SGLang, 2023/2024 — arxiv.org/abs/2312.07104
  • Karger et al., Consistent Hashing and Random Trees, STOC 1997.

What to learn next