Level 605 • Cache Architecture

Context Caching Economics & KV-Cache Eviction Algorithms

Analyzing the mathematical structures behind prefix caching: Radix trees, PagedAttention block mapping, LRU vs attention-score cache eviction policies, and how prompt caching slashes API run rates by up to 90%.

1. The Quadratic Prefill Tax in Long-Context Workloads

In multi-turn agentic conversations, retrieval-augmented generation (RAG), and software engineering benchmarks (like SWE-bench), LLM prompts contain massive static prefixes: system instructions, tool schemas, repository codebases, and historical conversation turns. In standard autoregressive serving, the prompt prefill phase processes these $N$ tokens through all transformer layers, incurring a computational complexity of $\mathcal{O}(N \cdot D^2 + N^2 \cdot D)$.

Because Key-Value ($K, V$) tensors computed for tokens $1 \dots N$ are deterministic (given identical prefix tokens and causal attention masks), recomputing them on every conversational turn wastes massive compute cycles and increases Time-to-First-Token (TTFT). Context caching persists these Key and Value tensors in GPU High-Bandwidth Memory (HBM) or host RAM, allowing subsequent requests to bypass matrix multiplications for matched token prefixes.

2. Radix Tree Prefix Caching & PagedAttention Mechanics

Modern inference engines (such as SGLang and vLLM) organize cached KV blocks using a Radix Tree (compact prefix trie). Each node represents a sequence of tokens associated with a physical GPU memory block allocated via PagedAttention. When a new prompt arrives:

L_{\text{hit}} = \text{MatchPrefix}(\text{PromptTokens}, \text{RadixTree})

If $L_{\text{hit}} > 0$, the server reuses the stored KV blocks directly. The prefill compute reduction $\Delta C$ scales linearly with parameter count $P$ and match length:

\Delta C \approx 2 \cdot P \cdot L_{\text{hit}} \quad \text{FLOPs}

Under enterprise prompt caching pricing (e.g. Anthropic's 90% discount on cache reads or OpenAI's 50% discount), the effective blended cost per token $C_{\text{eff}}$ given cache hit ratio $\alpha \in [0, 1]$ is governed by:

C_{\text{eff}} = (1 - \alpha) C_{\text{write}} + \alpha C_{\text{read}}

When $\alpha = 0.85$ (typical in multi-turn coding agent sessions), overall token expenditure collapses by over 75%, fundamentally changing the financial feasibility of autonomous agents.

3. KV-Cache Eviction: LRU vs. Attention Score Heuristics

GPU High-Bandwidth Memory is strictly bounded. When available physical pages are exhausted, the server must evict cached blocks. Three primary eviction policies dominate:

Least Recently Used (LRU): Evicts the leaf nodes of the radix tree that have gone longest without being matched. Highly effective for sequential agentic chat sessions.
Prefix-Biased Eviction: Prioritizes retaining the root and high-depth internal nodes of the radix tree (e.g. system prompts and tool schemas shared across all users) while aggressively discarding leaf nodes.
Attention-Score Heavy Hitters (H2O): During generation, retains only tokens that accumulate high cumulative attention weights $\sum_i A_{i, j}$, pruning low-impact context tokens from the active attention window.

4. Standalone Python Implementation: Radix Tree KV-Cache with LRU Eviction

The following production Python module simulates a Radix Tree prefix cache with physical block tracking and LRU eviction:

from dataclasses import dataclass, field
from typing import List, Dict, Optional
import time

@dataclass
class RadixNode:
    token_ids: List[int]
    block_id: int
    children: Dict[int, 'RadixNode'] = field(default_factory=dict)
    last_accessed: float = field(default_factory=time.time)

class RadixKVCache:
    """
    In-memory Radix Tree KV-Cache with capacity limit and LRU block eviction.
    """
    def __init__(self, max_blocks: int = 100):
        self.root = RadixNode(token_ids=[], block_id=-1)
        self.max_blocks = max_blocks
        self.allocated_blocks = 0
        self.block_counter = 0

    def match_prefix(self, tokens: List[int]) -> int:
        """Returns the number of matching prefix tokens found in cache."""
        curr = self.root
        matched = 0
        i = 0
        while i < len(tokens):
            first_tok = tokens[i]
            if first_tok not in curr.children:
                break
            child = curr.children[first_tok]
            child.last_accessed = time.time()
            node_len = len(child.token_ids)
            if tokens[i : i + node_len] == child.token_ids:
                matched += node_len
                i += node_len
                curr = child
            else:
                break
        return matched

    def insert(self, tokens: List[int]):
        """Inserts a token sequence into the prefix cache."""
        if self.allocated_blocks >= self.max_blocks:
            self._evict_lru()

        curr = self.root
        i = 0
        while i < len(tokens):
            first_tok = tokens[i]
            if first_tok not in curr.children:
                self.block_counter += 1
                self.allocated_blocks += 1
                curr.children[first_tok] = RadixNode(
                    token_ids=tokens[i:],
                    block_id=self.block_counter
                )
                break
            curr = curr.children[first_tok]
            curr.last_accessed = time.time()
            i += len(curr.token_ids)

    def _evict_lru(self):
        """Finds and evicts the oldest leaf node."""
        oldest_node = None
        oldest_parent = None
        oldest_key = None
        oldest_time = float('inf')

        for key, child in self.root.children.items():
            if not child.children and child.last_accessed < oldest_time:
                oldest_time = child.last_accessed
                oldest_node = child
                oldest_parent = self.root
                oldest_key = key

        if oldest_parent and oldest_key in oldest_parent.children:
            del oldest_parent.children[oldest_key]
            self.allocated_blocks -= 1

if __name__ == "__main__":
    cache = RadixKVCache(max_blocks=5)
    system_prompt = [101, 2054, 2003, 1037] # "You are a helpful"
    query_1 = [101, 2054, 2003, 1037, 5001, 5002]
    
    cache.insert(system_prompt)
    hit_len = cache.match_prefix(query_1)
    print(f"Matched Prefix Tokens: {hit_len} / {len(query_1)} ({(hit_len / len(query_1))*100:.1f}% hit)")

Next in Curriculum

Level 606: Open-Weights vs. Frontier API Total Cost of Ownership

Model CapEx vs OpEx economics: 36-month GPU depreciation, rack electricity contracts, colocation fees, and mathematical breakeven volume formulas.

Proceed to Level 606 →