The KV Cache Is a Secretly Distributed-State Problem

Everyone on the API side thinks the LLM is a stateless function: send a prompt, get text back. The moment you split serving into microservices, the KV cache stops being a per-request detail and becomes a piece of distributed state that has to live somewhere. Where you put it decides your memory ceiling, your p95 latency, and how hard it is to isolate tenants.

Here’s the tension. The KV cache is:

• Fast to use only if it’s colocated with the GPU that computes attention.
• Cheap to scale only if it’s shared and gated behind caching.
• Safe to share only if requests with the same prompt prefix really produce the same keys and values — which they do, deterministically, for the same model, prefix, and sampling-invariant prefill.

This post is about the important design decisions you make when you put the KV cache inside a microservice architecture: where it lives, how it’s keyed, who owns it, and how it survives scale-out and failure. Like the best decisions, most of the value comes from getting the boundary right, not from tuning a knob.

Why the Standard “Serve It Like a REST Stateless Service” Trick Dies

A naive microservice design treats the LLM exactly like any web service: stateless, replicated behind a load balancer, any request can hit any replica.

# Naive: every LLM request is stateless and can hit any replica.
from openai import OpenAI

client = OpenAI(base_url="http://llm-gateway:8000/v1", api_key="EMPTY")

def complete(prompt: str) -> str:
    return client.chat.completions.create(
        model="llama-3.1-8b",
        messages=[{"role": "user", "content": prompt}],
    ).choices[0].message.content

Now imagine a fleet of replicas, each with its own vLLM instance. A user sends three requests that share an 8,000-token system prompt. The load balancer fans them out to three different replicas. Each replica recomputes the KV for those same 8,000 tokens. Three times the prefill work, three times the KV cache slots burned, for content that is identical.

The error is treating the KV cache as incidental. It is not. It’s the single largest memory consumer at serving time, and it is partition-specific: only the GPU that computed it has it. There is no way to share it across replicas shortcut of the OS page cache of the machine that has it. So the first design decision is about affinity.

Decision 1: Sticky Routing, or “Make the Same Prompt Hit the Same Replica”

The cheapest way to make the KV cache useful is to not scatter it. A consistent hash on a prompt-family key routes every request in a family to the same replica, so prefix caching (which I covered in the companion scaling post) actually pays off.

import hashlib
import requests

# A load-balancing rule: pick the replica by a stable hash of a route key.
# Route key = (user_id, model, prompt_prefix_fingerprint) roughly.
def pick_replica(route_key: str, replicas: list[str]) -> str:
    digest = hashlib.sha256(route_key.encode()).hexdigest()
    idx = int(digest[:8], 16) % len(replicas)
    return replicas[idx]

replicas = ["llm-worker-0:8000", "llm-worker-1:8000", "llm-worker-2:8000"]

def complete_with_affinity(model: str, system_prompt: str, user_msg: str) -> str:
    route_key = f"{model}::{hashlib.sha256(system_prompt.encode()).hexdigest()}"
    replica = pick_replica(route_key, replicas)
    payload = {"model": model, "messages": [
        {"role": "system", "content": system_prompt},
        {"role": "user", "content": user_msg},
    ]}
    return requests.post(
        f"http://{replica}/v1/chat/completions",
        json=payload,
    ).json()["choices"][0]["message"]["content"]

Things to get right here:

• Hash on the full effective prefix, not just the user ID. Two tenants sharing a base system prompt should still share cache if the model and prefix match exactly.
• Rehash on replica count change. A consistent-hash ring with fallback neighbors avoids a full cache flush whenever you scale your fleet, which is exactly the moment you don’t want to lose the warm cache.
• Send the same request to a fixed replica once affinity is chosen, instead of re-picking for every message in a multi-turn conversation. A multi-turn chain that flips replicas between turns throws away all prior KV on every turn.

The key is a stable function of everything that determines the prefix: model + system prompt + prior turns. That’s the “cache key” of the whole system.

Decision 2: Where the Cache Lives — GPU, Host, or Shared Service

You have three real options, and they trade latency for sharing:

The important insight: a KV block is only useful when it’s in GPU memory, because that’s where attention runs. A shared cache service is not faster by itself; it’s a rehydration source. It lets a cold replica rehydrate a shared prefix in milliseconds instead of recomputing the whole prefix.

Design the shared cache around that reality:

import hashlib
import json
import datetime
import redis

r = redis.Redis(host="kv-cache", port=6379, db=0)

TTL_SECONDS = 3600   # block expiration — evict long-idle prefixes

def cache_key_family(model: str, prefix: str) -> str:
    h = hashlib.sha256(prefix.encode()).hexdigest()
    return f"kv:{model}:{h}"

def store_prefix(model: str, prefix: str, blocks: bytes) -> None:
    key = cache_key_family(model, prefix)
    r.hset(key, "blocks", blocks)
    r.hset(key, "updated", datetime.datetime.now(datetime.timezone.utc).isoformat())
    r.expire(key, TTL_SECONDS)

def fetch_prefix(model: str, prefix: str) -> bytes | None:
    raw = r.hget(cache_key_family(model, prefix), "blocks")
    return raw if raw is not None else None

Decision rules that fall out:

1. Small-to-medium shared prefixes → host/shared cache. The prefill you save dominates the load cost.
2. Huge single-use prefixes → skip the shared cache. If a 50k-token context appears once and never repeats, writing and TTL-evicting it wastes memory.
3. Model changes invalidate the key space. Bump the model component of the key when you roll a new checkpoint, or you’ll serve stale blocks with different weights — output corruption, not just staleness.
4. Never trust the cache for sampling-dependent state. KV cache is safe to share only for prefill of a deterministic prefix, never for tokens already sampled.

Decision 3: Who Owns the Cache — per-Service or a Dedicated Cache Service?

Two ownership models:

• Co-located (each LLM worker owns its own cache): simplest, best latency, but cache is per-replica and dies when the pod dies. Affinity routing is mandatory to make cache hits predictable.
• Dedicated cache service (shared read-through): the cache outlives replicas, so a rolling upgrade or a crash doesn’t nuke warm state. The cost is an extra network hop and the need to serialize blocks.

The pragmatic answer for most microservice fleets is both: co-located on-GPU pages for the hot working set, with a dedicated cache service as the durable rehydration store for long-lived shared prefixes. The co-located cache carries 95% of the traffic; the dedicated service covers cold starts and autoscaling.

# Two-tier read path: try local (on-GPU) KV, fall back to the shared cache.
import vllm

class CachedServer:
    def __init__(self, max_model_len: int = 8192):
        self.llm = vllm.LLM(
            model="meta-llama/Meta-Llama-3.1-8B-Instruct",
            max_model_len=max_model_len,
            gpu_memory_utilization=0.90,
            enable_prefix_caching=True,
        )
        self.shared = redis.Redis(host="kv-cache", port=6379)

    def generate(self, system_prompt: str, user_msg: str) -> str:
        prefix = f"{system_prompt}\n\nUser: {user_msg}"
        blocks = fetch_prefix("llama-3.1-8b", prefix)
        if blocks is None:
            # Local vLLM prefix cache already catches most hits.
            pass

        out = self.llm.generate(prefix, vllm.SamplingParams(max_tokens=128))
        text = out[0].outputs[0].text

        # Contribute the computed prefix back to the shared cache so
        # cold replicas can rehydrate it on rollout.
        store_prefix("llama-3.1-8b", prefix, blocks=text.encode())

        return text

The two-tier design is the one that scales: hot cache stays on the silicon, cold-cache rehydration comes from a service that isn’t tied to any single GPU’s lifetime.

Decision 4: Isolation When Tenants Share the Cache

The moment you cache prefixes, you’re building a system where many tenants’ attention state lives on shared hardware. Two isolation rules are non-negotiable:

• Key isolation by tenant. The cache key must include a tenant-granular namespace so tenant A can never be served blocks computed from tenant B’s prompt. A prompt is frequently confidential (legal reviews, maritime security logs, medical text), and the KV cache is the equivalent of retaining it.

def scoped_key(tenant: str, model: str, prefix: str) -> str:
    h = hashlib.sha256(prefix.encode()).hexdigest()
    return f"kv:{tenant}:{model}:{h}"   # tenant-scoped, unshareable across tenants

def fetch_scoped(tenant: str, model: str, prefix: str) -> bytes | None:
    raw = r.hget(scoped_key(tenant, model, prefix), "blocks")
    return raw if raw is not None else None

• No cross-tenant prefix interleaving in a batch. Tenant A’s request and tenant B’s request may share bytes, but they must not share KV pages if either party expects the other to be unable to infer what was cached. Practically: either enforce one-tenant-per-pod for the KV pool, or scope every batch to tenant-membership and never mix across tenant lanes.

If you get this wrong, you don’t have a performance bug; you have a data-exposure incident waiting for an auditor.

Decision 5: Scaling the Cache With the Fleet

The cache can’t scale as one giant singleton if you want availability. Design it to shard like any other state you’d put behind microservices:

• Shard by the cache key’s hash (consistent hashing) so adding a cache node rebalances a small slice rather than rehashing everything.
• Replicate read-mostly prefixes across at least two cache nodes, because a shared prompt used by every replica is a hot, read-mostly object — losing it to one failed node drops the whole fleet back to full-prefix recompute.
• Cache-aware autoscaling. Scale LLM replicas so that affinity and cache locality survive. Replicas can start cold (empty local cache), but the shared cache rehydrates them. Never scale so aggressively that you churn replicas faster than the shared cache can repopulate.
• Drop cache gracefully on model rollout. A new checkpoint is a different function; its KV is a different value space. On rollout, invalidate/rebuild cache keys for the new model within a bounded TTL instead of carrying stale blocks forward.

# Consistent-hash sharding so cache nodes can join/leave without a hard flush.
import hashlib

class HashRing:
    def __init__(self, nodes: list[str], vnodes: int = 100):
        self.ring = {}
        for node in nodes:
            for i in range(vnodes):
                h = hashlib.sha256(f"{node}:{i}".encode()).hexdigest()
                self.ring[h] = node
        self._sorted = sorted(self.ring)

    def get(self, key: str) -> str:
        h = hashlib.sha256(key.encode()).hexdigest()
        for point in self._sorted:
            if h <= point:
                return self.ring[point]
        return self.ring[self._sorted[0]]

When one cache node leaves, only the keys that hash to it migrate to the next node in the ring; the rest of the fleet keeps a warm cache. That is the difference between a cache that survives scaling and a cache that forces a recompute stampede every time you autoscale.

The Decision Matrix, Condensed

The Real World Is a Pipeline, Not a Clean Decision

In practice your LLM never runs alone. The prompt is built by a conversation service, an agent orchestrator, or a RAG pipeline. The KV cache design has to agree with their caching:

• The conversation service caches the conversation history as text.
• The RAG pipeline caches retrieved chunks as text and embeddings.
• The LLM service caches the resulting prompt as KV blocks.

These are three different caches with three different keys and three different invalidation lifetimes. The design mistake is to assume one “cache” covers all three. The prompt is fully determined only when retrieved context plus history plus system prompt all resolve, so KV only applies to fully materialized prompts. Design your cache boundaries to match, or you’ll be serving stale text from one layer and fresh text from another.

That is exactly why the KV cache decision belongs in architecture review, not just in the serving code: it cross-cuts routing, state ownership, tenant isolation, scaling, and rollout.

Summary

• The KV cache is the LLM’s secret state; treat it as distributed state, not a function-servable detail.
• Route requests by a stable prompt-family key so prefix caching actually hits.
• Colocate hot pages on the GPU, rehydrate from a dedicated shared cache service.
• Scope cache keys and pages by tenant — the KV cache is ultimately a copy of the prompt.
• Shard and replicate the cache; keep it warm across autoscaling and model rollouts.
• Align KV caching with the text cache of conversation and RAG layers, not in isolation.

Get the boundaries right and the KV cache becomes your biggest serving lever. Get them wrong and it’s your slowest leak. Same bytes, opposite outcomes.