跳到正文
DEV Community· Syed Anzar·· 1 小時前AI 評分71

提示詞快取如何運作:Radix Tree、KV Cache 重用及單個 token 為何會令 Agent 快取失效

How Prompt Caching Actually Works: Radix Trees, KV-Cache Reuse, and Why One Token Breaks Your Agent

AI 導讀

文章解釋提示詞快取如何重用 Transformer 預填階段產生的 KV 張量,而非快取文本或生成結果;前綴中一個 token 改變,後續 KV 狀態便無法沿用。

正文

Most developers assume prompt caching is like an HTTP reverse proxy or a Redis key-value cache where an identical string returns an identical response. Then they deploy a multi-turn agent with a 10,000-token system prompt, look at their inference latency or cloud bill, and realize their cache hit rate is sitting at zero.

Prompt caching does not cache text, and it does not cache completions. It preserves the intermediate numerical Key and Value tensor states generated during the transformer prefill pass.

When it works, it cuts Time-to-First-Token (TTFT) by 85% to 95% and slashes input token costs by up to 90%. But because of how causal self-attention, rotary positional embeddings (RoPE), and prefix data structures operate, a single dynamic timestamp or unordered dictionary key near the top of your prompt invalidates every cached tensor downstream.

Here is how prompt caching actually works under the hood across modern inference engines, how SGLang and vLLM track cached memory, and how to structure your prompts so you stop throwing away cache hits.

Prefill vs Decode: The Latency and Cost Asymmetry

To understand why prompt caching matters, you have to look at the two distinct phases of autoregressive transformer inference.

Request Prompt (N tokens)
       │
       ▼
┌──────────────────────────────────────────────┐
│ PREFILL PHASE (Parallel Forward Pass)        │
│ Computes Q, K, V for all N tokens at once    │
│ O(N²) attention operations                   │
│ Compute-bound on GPU Tensor Cores            │
└──────────────────────────────────────────────┘
       │
       ▼  (Produces initial KV cache + first token)
┌──────────────────────────────────────────────┐
│ DECODE PHASE (Autoregressive Generation)     │
│ Computes 1 token per forward pass            │
│ Reads all existing KV cache from GPU HBM     │
│ Memory-bandwidth-bound                       │
└──────────────────────────────────────────────┘

When you send a prompt with $N$ tokens to an LLM:

  1. Prefill Phase: The engine processes all $N$ tokens in parallel in a single forward pass. It multiplies the input embeddings by projection matrices ($W_q, W_k, W_v$) to produce Queries, Keys, and Values. Self-attention requires every token to attend to all preceding tokens, scaling quadratically with sequence length ($O(N^2)$ FLOPs). This phase is compute-bound, saturating the GPU Tensor Cores.
  2. Decode Phase: The engine generates output tokens one by one. For each new token, the model needs the Keys and Values of all prior tokens. To avoid recalculating past tokens, the engine keeps them in GPU High Bandwidth Memory (HBM) as the KV cache. Each decode step is memory-bandwidth-bound, because the GPU must transfer gigabytes of KV tensors from memory to registers just to generate a single token.

The Multi-Turn Agent Tax

In standard single-turn queries, prefill happens once. But AI agents do not run single-turn queries. They run ReAct loops (Reasoning + Action) across 10 to 30 turns.

On every iteration of the loop, the client sends the entire history back to the inference API:

  • Base system instructions
  • Complete JSON schemas for every available tool
  • Few-shot examples
  • Full conversation history
  • Prior tool call arguments and raw tool outputs
  • The newest user instruction
Turn 1:  [System + Tools (4,000t)] + [User (100t)]               = 4,100 tokens prefilled
Turn 2:  [System + Tools (4,000t)] + [Turn 1 History] + [Tool 1] = 5,200 tokens prefilled
Turn 3:  [System + Tools (4,000t)] + [Turns 1-2] + [Tool 2]      = 6,800 tokens prefilled
...
Turn 10: [System + Tools (4,000t)] + [Turns 1-9] + [Tool 9]      = 14,500 tokens prefilled

Without prompt caching, the inference engine recalculates the Keys and Values for that identical 4,000-token system prompt and every preceding conversation turn from scratch on every single step. By turn 10, your agent has recomputed over 80,000 redundant prompt tokens.

Prompt caching allows the engine to skip the prefill computation for any prefix it has already seen, loading the precomputed KV tensors directly from memory.

What Actually Lives in the KV Cache?

To see why caching is tricky, we need to look at what the KV cache actually contains.

In a transformer layer, input tokens $X$ are projected into Query ($Q$), Key ($K$), and Value ($V$) tensors:

$$K = X W_k, \quad V = X W_v$$

For a single token at a single transformer layer, the Key and Value vectors have a fixed dimension:

$$\text{Vector Size} = \text{num_kv_heads} \times \text{head_dim}$$

In modern models using Grouped-Query Attention (GQA), such as Llama 3 or Mistral, multiple query heads share a single KV head to save memory. Still, the memory consumption across deep models is substantial:

$$\text{KV Cache Bytes} = 2 \times \text{num_layers} \times \text{num_kv_heads} \times \text{head_dim} \times \text{bytes_per_elem} \times \text{seq_len}$$

Let us calculate this for Llama 3 70B running in FP16 (2 bytes per parameter):

  • Layers: 80
  • KV heads: 8
  • Head dimension: 128
  • Bytes per element: 2 (FP16)
  • Formula per token: $2 \times 80 \times 8 \times 128 \times 2 = 327,680 \text{ bytes } (\approx 320 \text{ KB per token})$

For a 10,000-token context window, the KV cache for a single request takes 3.2 GB of GPU HBM.

PagedAttention vs Discarded Blocks

In older inference runtimes (like early HuggingFace Transformers), KV caches were allocated as contiguous memory buffers. If a request grew, the engine had to preallocate memory for the maximum possible context length or reallocate and copy memory on the fly, leading to massive memory fragmentation.

In 2023, vLLM introduced PagedAttention, borrowing the concept of virtual memory and paging from operating systems. It divides the physical KV cache in GPU HBM into fixed-size blocks (typically 16 or 32 tokens per block). Logical blocks in the model's sequence map to arbitrary physical blocks via a block table.

Originally, PagedAttention freed those blocks as soon as the request finished generating. Prompt caching changes that: instead of freeing the physical blocks, the engine retains them in memory, indexes them by token prefix, and lets subsequent requests point their block tables to those existing physical blocks.

How that indexing works depends on the engine. The two major approaches today are chained block hashing (vLLM) and radix trees (SGLang).

Engine Internals 1: vLLM Automatic Prefix Caching (Chained Block Hashing)

vLLM implements Automatic Prefix Caching (APC) using a hash-indexed block pool.

Because the Key and Value representations of a token depend on all preceding tokens in the sequence, you cannot identify a KV block by its own tokens alone. The phrase "return true;" produces completely different Key and Value tensors in a JavaScript function than in a C++ program.

To solve this, vLLM creates a chained hash for every physical block:

def hash_block_tokens(hash_function, parent_block_hash, curr_block_token_ids, extra_keys=None):
    if not parent_block_hash:
        parent_block_hash = NONE_HASH
    curr_block_token_ids_tuple = tuple(curr_block_token_ids)
    return BlockHash(
        hash_function((parent_block_hash, curr_block_token_ids_tuple, extra_keys))
    )

Each block's identity is a hash of three components:

  1. Parent block hash: The hash of the immediately preceding block. This cryptographically links the block to the entire sequence that came before it.
  2. Current block token IDs: The exact tuple of token IDs (e.g. 16 integers) inside this block.
  3. Extra keys: Contextual modifiers that alter execution, such as active LoRA adapter IDs, multimodal image hashes, or a cache_salt for multi-tenant isolation.
Block 0 [Tokens 0..15]
Hash: sha256(NONE, [tokens_0_15], extra)
       │
       ▼
Block 1 [Tokens 16..31]
Hash: sha256(Block_0_Hash, [tokens_16_31], extra)
       │
       ▼
Block 2 [Tokens 32..47]
Hash: sha256(Block_1_Hash, [tokens_32_47], extra)

The Lookup and Cache Hit Logic

When a new prompt arrives:

  1. The engine tokenizes the prompt.
  2. The request block hasher computes the expected hash chain for all full blocks in the prompt.
  3. The scheduler walks the block pool looking up hashes:
   for block_hash in full_block_hashes:
       cached_block = block_pool.get_cached_block(block_hash)
       if not cached_block:
           break # The chain broke. Stop lookup.
       computed_blocks.append(cached_block)
  1. For matched blocks, the scheduler increments their reference counts (ref_cnt += 1), marks them as protected from eviction, and points the request's block table to them.
  2. The model only runs prefill on the remaining uncached tokens!

The Block Boundary Rule

There is an important engineering detail in vLLM's APC: it only caches full blocks.

If your block size is 16 tokens and your shared prompt prefix is 45 tokens long:

  • Block 0 (tokens 0 to 15): Cached and matched.
  • Block 1 (tokens 16 to 31): Cached and matched.
  • Tokens 32 to 44 (13 tokens): Cannot form a full block of 16 tokens.
  • Result: Only 32 tokens are served from cache. The remaining 13 tokens must be prefilled along with whatever dynamic text follows.

Furthermore, the model must always compute the final prompt token during prefill. The KV cache holds keys and values, not next-token output logits. To sample the first generated token, the model must run the forward pass through the attention layers for at least the final token position.

Engine Internals 2: SGLang RadixAttention (Token-Level Prefix Trees)

While vLLM uses fixed-size hashed blocks, SGLang took a different architectural approach: RadixAttention.

A radix tree (or compact prefix tree) is a data structure where each edge represents a sequence of tokens of arbitrary length, rather than a single character or fixed-size block. Nodes represent points where different prompts branched apart.

                  [ ROOT ]
                     │
             "You are a helpful" (Edge 1, 4 tokens)
                     │
                 [ Node A ]
                /          \
   "coding assistant..."    "medical assistant..."
   (Edge 2, 2,000 tokens)   (Edge 3, 1,800 tokens)
            │                        │
        [ Node B ]               [ Node C ]

In RadixAttention:

  • Keys: Token sequences of variable length.
  • Values: Pointers to physical paged KV cache tensors in GPU memory.
  • Maintenance: The radix tree is maintained in CPU host memory, adding sub-millisecond overhead to request routing.

Radix Tree Lifecycle in a Multi-Turn Run

  1. Initial Request: Request 1 sends [System Prompt] + [Question 1]. SGLang inserts the token stream into the radix tree as a single edge from the Root to Node A. The GPU computes the KV cache and links it to that edge.
  2. First Output: The model generates [Answer 1]. SGLang appends [Answer 1] as an edge extending from Node A to Node B. The generated tokens' KV cache is also retained.
  3. Second Turn: Request 2 arrives with [System Prompt] + [Question 1] + [Answer 1] + [Question 2]. The runtime matches the prompt against the tree from Root $\to$ Node A $\to$ Node B. It finds a complete match for the first three components. Zero prefill is needed for those tokens. Only [Question 2] is executed through the model.
  4. Branching (Edge Splitting): A different user arrives with [System Prompt] + [Alternative Question]. SGLang walks the tree, matches [System Prompt], and hits Node A. Because the next tokens diverge, Node A splits, creating a new branch for the new conversation while keeping the shared system prompt KV cache untouched.

Eviction and Cache-Aware Scheduling

GPU memory is finite. When the GPU runs low on space for new requests, RadixAttention evicts cached nodes using a Least Recently Used (LRU) policy with reference counting:

  • Reference Counter: Each node tracks how many currently executing batches are reading its KV tensors. If ref_counter > 0, the node is locked and cannot be evicted.
  • Leaf Eviction: Eviction runs recursively from leaf nodes toward the root. Because child nodes depend on parent prefixes, an engine can never evict a parent node while keeping its children. Evicting the least recently accessed conversation branches preserves the high-traffic root nodes (like base system instructions).
  • Cache-Aware Scheduling: Standard First-Come-First-Served (FCFS) request queues cause cache thrashing if consecutive requests need different system prompts. SGLang sorts waiting requests by matched prefix length, grouping requests that share KV subtrees together to maximize hit rates.

How Hosted APIs Implement It (Anthropic, OpenAI, DeepSeek)

If you are not running your own vLLM or SGLang cluster, you interact with prompt caching through managed API endpoints.

Provider Mechanism Minimum Threshold Pricing Model Cache Duration (TTL)
Anthropic (Claude) Explicit cache_control breakpoints or top-level automatic 1,024 tokens Cache Write: +25% cost
Cache Read: 90% discount (10% base cost)
5-minute rolling TTL (refreshes on every hit)
OpenAI (GPT-4o) Fully automatic (128-token chunk hashes) 1,024 tokens Cache Read: 50% discount Dynamic system-managed LRU
DeepSeek (V3 / R1) Fully automatic prefix matching 64 tokens Cache Read: ~75% to 90% discount Dynamic system-managed

In Anthropic's Messages API, you can place cache breakpoints explicitly:

response = client.messages.create(
    model="claude-3-7-sonnet-20250219",
    max_tokens=1024,
    system=[
        {
            "type": "text",
            "text": long_system_prompt_and_rules,
            "cache_control": {"type": "ephemeral"} # Cache breakpoint 1
        }
    ],
    tools=tool_definitions, # Cache breakpoint can also be placed on the last tool
    messages=conversation_turns
)

When Anthropic's gateway receives this request, it checks whether a cached KV state exists for all tokens up to that cache_control marker. If it finds a match, response.usage.cache_read_input_tokens returns the cached count, and you are charged 10% of standard input pricing for those tokens.

The Prefix Invalidation Trap: Why One Token Breaks Everything

Now we arrive at the core failure mode that catches engineering teams off guard.

In traditional software caching, if you cache an object with 10 fields and update field #2, fields #3 through #10 are still valid in memory.

In an autoregressive transformer, that is physically impossible.

Transformers rely on causal self-attention. Every token at position $i$ attends to every preceding token at positions $0, 1, \dots, i-1$. Furthermore, modern models use Rotary Position Embeddings (RoPE), which inject position-dependent rotation into query and key vectors:

$$R_{\Theta, m}^d K_m$$

If you change token at index 5:

  1. Token 5's Key and Value vectors change.
  2. Every subsequent token (index 6 through 10,000) now needs to attend to the new Key and Value vectors of token 5.
  3. Their attention outputs and layer representations are completely different.
  4. In vLLM, the chained hash at Block 0 breaks. Because Block 1 takes parent_block_hash as input, every subsequent block hash in the sequence changes.
  5. In SGLang, the radix tree match terminates at the divergence point.

A change of one token at position 5 invalidates 100% of the cached KV state after position 5.

The 5 Traps That Silently Kill Cache Hit Rates

Here are the five most common patterns that destroy prompt caching in production:

1. Dynamic Timestamps in System Prompts

Many developers inject the current time at the very top of their system instructions:

# BAD: Breaks prompt cache on every single request
system_prompt = f"""You are a helpful assistant.
Current time: {datetime.utcnow().isoformat()}

Here are your 40 complex operating guidelines...
"""

Because the timestamp changes every second, token 12 diverges on every request. The remaining 3,000 tokens of static guidelines never hit the cache.

2. Non-Deterministic Tool Schema Serialization

In Python, dictionaries preserved insertion order starting in Python 3.7. But when converting tool schemas or Pydantic models to JSON strings, key order can vary across processes or updates:

# BAD: Non-deterministic key ordering
import json
tool_schema_str = json.dumps(my_tool_dict) # Keys may serialize in arbitrary order

If {"name": "search", "description": "..."} serializes as {"description": "...", "name": "search"} on worker B, worker B gets a total cache miss despite having identical tool semantics.

3. Ephemeral IDs at the Beginning of the Prompt

Putting user IDs, request IDs, or session UUIDs in the header:

# BAD: Unique prefix per user/session
prompt = f"Session ID: {uuid.uuid4()}\nUser: {user_id}\n\n[Long Static Knowledge Base]"

This ensures that no two users or sessions can ever share the cached KV state of the knowledge base.

4. Shuffling Few-Shot Exemplars

Some developers shuffle few-shot examples randomly to prevent positional bias. While well-intentioned for model evaluation, in production this turns a static 2,000-token prompt into $k!$ different permutation prefixes, cratering cache hits.

5. Tokenizer Whitespace and Punctuation Boundaries

Byte-Pair Encoding (BPE) tokenizers merge spaces with following words.
"System prompt:\n" might tokenize as [1200, 340, 198].
"System prompt:\n\n" might tokenize as [1200, 340, 273].

Notice that the third token ID is not an extra token appended; the tokenizer merged \n\n into a completely distinct single token ID (273). A stray space or extra newline near the top of your prompt can alter token boundaries and invalidate the downstream prefix.

The Frozen Prefix Architecture

To get 90%+ prompt cache hit rates in production, you must structure your prompt layout as a Frozen Prefix Hierarchy.

Think of your prompt as an append-only log. The most stable, universal text sits at the root. The most dynamic, volatile text sits at the tail.

┌──────────────────────────────────────────────────────────┐
│ LAYER 1: Base System Persona & Rules (Never Changes)     │  <-- 100% Cache Hit
├──────────────────────────────────────────────────────────┤
│ LAYER 2: Deterministic Tool Schemas (Sorted JSON)        │  <-- 100% Cache Hit
├──────────────────────────────────────────────────────────┤
│ LAYER 3: Static Few-Shot Exemplars (Pinned Order)        │  <-- 100% Cache Hit
├──────────────────────────────────────────────────────────┤
│ LAYER 4: Multi-Turn Conversation History (Append-Only)   │  <-- Progressive Hit
├──────────────────────────────────────────────────────────┤
│ LAYER 5: Volatile Variables (Timestamp, User Query)       │  <-- Cache Divergence
└──────────────────────────────────────────────────────────┘

Production Implementation

Here is how to structure an agent runner in Python to guarantee deterministic caching:

import json
from datetime import datetime, timezone

def canonical_json(data: dict) -> str:
    """Serialize JSON with deterministic key ordering and compact spacing."""
    return json.dumps(data, sort_keys=True, separators=(',', ':'))

def build_cache_optimized_prompt(
    system_rules: str,
    tools: list[dict],
    few_shots: list[dict],
    history: list[dict],
    user_query: str,
    user_metadata: dict
) -> list[dict]:
    messages = []

    # 1. Base instructions: strictly static text
    messages.append({
        "role": "system",
        "content": system_rules
    })

    # 2. Tools: sorted alphabetically by tool name before serialization
    sorted_tools = sorted(tools, key=lambda t: t.get("name", ""))
    messages.append({
        "role": "system",
        "content": f"Available tools:\n{canonical_json({'tools': sorted_tools})}"
    })

    # 3. Few-shot examples: deterministic order
    for exemplar in few_shots:
        messages.append({"role": exemplar["role"], "content": exemplar["content"]})

    # 4. Conversation history: append-only turns
    for turn in history:
        messages.append({"role": turn["role"], "content": turn["content"]})

    # 5. Volatile dynamic context: placed strictly in the final user message
    now_str = datetime.now(timezone.utc).strftime("%Y-%m-%d %H:%M:%S UTC")
    final_payload = (
        f"Context:\n"
        f"- Current Time: {now_str}\n"
        f"- User Timezone: {user_metadata.get('timezone', 'UTC')}\n\n"
        f"User Query:\n{user_query}"
    )
    messages.append({"role": "user", "content": final_payload})

    return messages

With this architecture:

  • Across all users and sessions, Layers 1, 2, and 3 share a single cached KV prefix in your cluster or hosted provider.
  • In multi-turn agent execution, each turn simply appends the latest assistant response and tool observation to Layer 4, reusing the entire prior conversation's KV cache.
  • The volatile timestamp in Layer 5 only invalidates the final few dozen tokens of the query, preserving 95%+ of the prompt in cache.

Quantifying the Payoff

What does this translate to in practice?

AWS builder benchmarks measuring SGLang running DeepSeek-R1-Distill-Qwen-7B on an NVIDIA A10G show the real numbers:

  • 2,048-token shared prefix: Cold TTFT of 691.6 ms dropped to 69.2 ms on a warm cache hit (a 90.0% reduction).
  • 8,192-token shared prefix: Cold TTFT of 2,035.9 ms dropped to 70.5 ms (a 96.5% reduction).
  • In the warm condition, 2,870 out of 2,871 prompt tokens were served directly from the radix tree without recomputation.

On API bills, moving an agentic pipeline from a 10% hit rate to an 85% hit rate drops input token expenses by roughly 70% to 80% on OpenAI, and up to 80% on Anthropic and DeepSeek.

Prompt caching is not magic. It is KV tensor reuse governed by causal attention and prefix matching. If you respect the prefix boundary, you get sub-second responses and fractional bills. If you slip a timestamp at the top of your prompt, you pay the full prefill tax on every single token.

來源:DEV Community · dev.to