Multi-Turn KV Cache, in depth: keeping a conversation's attention state alive across turns, think time, routing and prompt rendering

Why every turn re-pays for the conversation

Take an assistant with a 1,500-token system prompt. Each user message averages 150 tokens and each reply 350. Turn k's prompt is the system prompt plus k-1 complete exchanges plus the new message, so it holds 1,650 + 500(k-1) tokens. Turn 1 prefills 1,650 tokens and turn 10 prefills 6,150.

Without reuse, the server prefills the sum of all ten prompts, 39,000 tokens. With perfect reuse it prefills only the new tokens of each turn. That is the 1,650 tokens of turn 1 plus 150 user tokens per later turn, about 3,000 tokens, because the reply tokens were already given keys and values during decode. The work is about thirteen times smaller, and the gap widens with conversation length: without reuse the total grows with the square of the turn count, with reuse it grows linearly.

Users feel this as time to first token. Prefill is compute-bound, so its latency scales roughly with the tokens processed. A turn that hits waits for 150 tokens of prefill; a turn that misses waits for the whole conversation, and gets slower the longer the user keeps talking.

What the server has to keep

Keys and values cost 2 x layers x KV heads x head dimension x bytes per element, per token; KV cache sizing derives this in full. For Llama 3.1 8B in 16-bit precision that is 2 x 32 x 8 x 128 x 2 = 131,072 bytes, 128 KiB per token. The 6,150-token conversation at turn 10 therefore holds about 770 MiB of KV.

Suppose the KV pool on one GPU is 40 GiB. That is about 327,000 tokens, or roughly 53 conversations of that size held at once. Now add think time. A user reads the reply, types, and sends the next message tens of seconds later. During that gap the conversation's blocks are not referenced by any running request. In vLLM's design they sit in the free queue with a reference count of zero, still hashed and still reusable, but first in line for eviction under the least-recently-used policy when running requests need room.

Under steady load this gives an eviction horizon: how long an idle block survives before LRU takes it. If it is shorter than your users' think time, the next turn misses however good the matching.

Measuring the eviction horizon

You can estimate the horizon from traffic. If the server admits new, uncached tokens at a rate R tokens per second and the pool holds P tokens of which A are pinned by running requests, idle blocks survive for about (P - A) / R seconds. With P = 327,000, A = 120,000 and R = 6,000 new tokens per second, the horizon is about 35 seconds. A median think time of 20 seconds would mostly hit; a long tail of users who come back after two minutes would mostly miss.

Check it empirically, because R includes every miss, so misses shorten the horizon and cause more misses. This probe replays a two-turn conversation with a controlled pause:

import time, statistics
from openai import OpenAI

client = OpenAI(base_url="http://localhost:8000/v1", api_key="unused")
MODEL = "meta-llama/Llama-3.1-8B-Instruct"
SYSTEM = open("system_prompt.txt").read()          # long, fixed system prompt

def ttft(messages):
    t0 = time.perf_counter()
    stream = client.chat.completions.create(model=MODEL, messages=messages,
                                            max_tokens=200, temperature=0, stream=True)
    first, text = None, []
    for chunk in stream:
        delta = chunk.choices[0].delta.content or ""
        if delta and first is None:
            first = time.perf_counter() - t0
        text.append(delta)
    return first, "".join(text)

for pause in (0, 10, 30, 60, 120):
    samples = []
    for trial in range(5):
        nonce = f"[probe {trial}-{pause}-{time.time()}]\n"   # unique first block
        msgs = [{"role": "system", "content": nonce + SYSTEM},
                {"role": "user", "content": "Summarise section 2."}]
        _, reply = ttft(msgs)
        time.sleep(pause)
        msgs += [{"role": "assistant", "content": reply},
                 {"role": "user", "content": "Now list the risks."}]
        samples.append(ttft(msgs)[0])
    print(f"pause={pause:>4}s  turn-2 TTFT median={statistics.median(samples)*1000:.0f} ms")

Run it under representative background load. Turn-2 latency stays near the cached floor while the pause is inside the horizon and jumps to the full-prefill cost once it is not. The pause at which it jumps is your horizon. The nonce at the very start makes every conversation unique, so other traffic cannot keep its blocks warm and a miss re-pays all of it.

Prompt rendering: the miss you cause yourself

A hit requires that turn N+1's token sequence begins with turn N's prompt followed by turn N's generated tokens. Anything that rewrites earlier text, even by one token, breaks the match from that block onward, and every block after the break is recomputed. Common causes:

• Dynamic content at the top. A system prompt that embeds the current time, a request ID or a shuffled list of tools changes the first block, so nothing after it can match. Put volatile content at the end of the prompt, or round timestamps to the day.
• Reasoning stripped from history. Some reasoning models' chat templates drop earlier assistant turns' thinking blocks when rendering the next prompt; Qwen3's official template does this for turns before the latest user query. That keeps context short, but the reply the server cached contained the thinking tokens and the re-rendered history does not, so the match ends at the start of that reply.
• Sliding-window truncation. Dropping the oldest exchange to stay under a context limit shifts every later token's position. The new prompt shares only the system prompt with the old one. If you must truncate, do it rarely and in large steps, so most turns are still pure appends.
• Summarise-and-replace. Replacing old turns with a summary is a deliberate full miss. Schedule it, do not let it happen every turn.
• Re-tokenisation drift. The client sends the reply back as text, and the server tokenises it again. Usually that reproduces the generated token IDs, but whitespace normalisation, a client that trims the reply, or a tokenizer that would have split the text differently can produce a different sequence. The match then stops partway through the reply.

Most of these show up offline by rendering consecutive turns with the model's template and comparing token sequences:

from transformers import AutoTokenizer

tok = AutoTokenizer.from_pretrained("meta-llama/Llama-3.1-8B-Instruct")

def common_prefix(a, b):
    n = 0
    for x, y in zip(a, b):
        if x != y:
            break
        n += 1
    return n

def check_append_only(conversation, block_size=16):
    """conversation: list of message dicts as your app sends them, turn by turn."""
    prev = None
    for i in range(1, len(conversation) + 1):
        msgs = conversation[:i]
        if msgs[-1]["role"] != "user":
            continue
        ids = tok.apply_chat_template(msgs, add_generation_prompt=True)
        if prev is not None:
            shared = common_prefix(prev, ids)
            reusable = shared // block_size * block_size
            print(f"turn ending at msg {i}: {len(ids)} tokens, prefix shared {shared}, "
                  f"full blocks reusable {reusable} ({reusable / len(prev):.0%} of last prompt)")
        prev = ids

A healthy conversation reuses nearly all of the previous prompt; a collapse to the system prompt's share shows which turn rewrote history. Stripped reasoning and re-tokenisation drift are invisible here, because both renders agree; catch them by comparing against the server's logged generated token IDs.

Routing: sending turn N+1 where turn N ran

With several replicas behind a load balancer, round-robin or least-connections routing sends turn 2 to a replica that has never seen the conversation. With eight replicas, seven out of eight later turns miss even if every cache is large. Two families of fix exist.

Session affinity hashes a conversation or user identifier to a replica, with consistent hashing so that adding a replica moves only a fraction of sessions. It is simple and needs no knowledge of cache contents. Its weakness is load: a few long, busy conversations can pile onto one replica while others idle, and affinity has no idea a shared system prompt is already cached everywhere.

KV-aware routing keeps an index of which block hashes each replica holds, fed by events from the engines or approximated from the router's own routing history, and scores each candidate by expected cached tokens minus a load penalty. Several open-source serving stacks now include a router of this kind. The scoring idea is small:

def route(request_block_hashes, replicas, alpha=1.0, beta=0.5):
    best, best_score = None, float("-inf")
    for r in replicas:
        hit_tokens = 0
        for h in request_block_hashes:          # hashes are chained, so stop at first miss
            if h not in r.cached_hashes:
                break
            hit_tokens += r.block_size
        new_tokens = len(request_block_hashes) * r.block_size - hit_tokens
        # cost estimate: prefill we would still pay here, plus queueing on this replica
        score = -alpha * new_tokens - beta * r.queued_prefill_tokens
        if score > best_score:
            best, best_score = r, score
    return best

The load term matters: pure cache maximisation piles traffic onto whichever replica holds a popular prefix. The index also goes stale, so treat a predicted hit as a probability.

Surviving think time with offload tiers

If the GPU pool cannot hold idle conversations long enough, move them rather than drop them. A tiered cache copies evicted blocks to host memory, then to local NVMe or a shared store, and copies them back on the next hit. The engine's paged block layout makes this practical, because blocks are fixed-size units that can be moved independently.

Whether reloading beats recomputing depends on the ratio of bytes to FLOPs. For the 8B example, 6,000 tokens of KV is about 750 MiB. Over a PCIe link sustaining 25 GB/s that is roughly 30 ms. Recomputing it costs about 2 x 8 billion x 6,000, roughly 10^14 floating-point operations, which at an achieved 400 TFLOP/s is about 250 ms before counting attention. Reload from host memory wins clearly; slow tiers narrow the margin. Measure on your hardware rather than trusting round numbers.

The same transfer machinery underlies disaggregated serving, where prefill and decode run on different GPUs and KV moves between them; peer-to-peer KV transfer covers the transport. For multi-turn traffic the important property is that a conversation's blocks can outlive their stay in one GPU's pool.

Isolation and tenancy

A shared prefix cache is a shared resource. If two tenants send the same prefix, the second gets a faster first token, and that timing difference can reveal that someone else sent it. vLLM's prefix caching supports an optional per-request cache salt that is mixed into the first block's hash, so only requests carrying the same salt can share blocks. Set it per tenant, or per user for sensitive workloads, and accept that common system prompts are then cached once per salt.

A KV-aware router must use the salted hashes, or it will predict hits that cannot happen. In vLLM's V1 engine prefix caching is on by default, so this decision applies whether or not you enabled caching.

Failure modes

Trade-offs

• Larger KV pools lengthen the eviction horizon but leave less room for decode batches.
• Affinity is cheap; KV-aware routing finds more hits but needs an index and can create hotspots.
• Keeping reasoning in history preserves the prefix but spends context on old thinking.

What to do next

1. Confirm prefix caching is enabled on every replica and record the engine version.
2. Run the append-only checker on twenty real transcripts and fix any turn that reuses less than 90 percent of the previous prompt.
3. Move timestamps, request IDs and per-call tool lists out of the system prompt or to the end.
4. Run the turn-2 probe at several pauses under production-like load to find your eviction horizon.
5. Compare the horizon with your users' think-time distribution from request logs.
6. Add session affinity or KV-aware routing, and track the share of later turns that land on their previous replica.
7. If the horizon is still too short, trial a host-memory offload tier and measure reload against recompute.
8. Decide on cache salting per tenant and document it.