Is the subtree-closed (leaf-only) eviction constraint in radix prefix caches free, or does it cost?
SGLang RadixAttention and vLLM prefix caching keep the KV of shared prompt prefixes in a radix tree. A longer cached prefix is physically stored on top of its shorter prefixes, so the cached set is always ancestor-closed: if a node is cached, all of its prefixes are cached too. Eviction inherits a hard constraint from this layout, it can only remove a leaf of the cached subtree, because a deeper cached prefix sits on top of the shorter one and cannot be dropped from underneath it. The natural worry is that this leaf-only rule is a handicap: it blocks the cache from dropping a stale interior prefix directly, so it looks like it should cost hit rate against a cache that could evict anything. This repo answers the question exactly.
The subtree-closed constraint does not cost. It is free for the offline optimum and, for a clean structural reason, free for the online policy too: leaf-only LRU makes the same decisions as an unconstrained LRU, so the constraint never actually binds on the choice a competent cache manager would make.
-
Free for the offline optimum. The minimum block-miss schedule achievable under the leaf-only rule equals the minimum achievable with unrestricted eviction, on every instance searched (2592 instances, no mismatch). The reason is structural, not incidental: any drop the unrestricted optimum would make lands on an ancestor-closed target state, and every ancestor-closed subset of a cached set is reachable by peeling leaves one at a time. Remove the deepest node in the difference first; it is always a current leaf, because any cached descendant of it would have to lie in the ancestor-closed target, which would force the node itself into the target, a contradiction. So the leaf-only rule can realize any eviction the optimum wanted, and cannot cost it. The two optima are then confirmed equal by independent exact search: the unrestricted optimum enumerates successors as any ancestor-closed subset (not by leaf-peeling), so the agreement is not circular.
-
Free for online LRU (not merely never-worse, and not, as an earlier draft of this repo wrongly claimed, strictly beneficial). The subtlety is the recency model. An access touches the whole root-to-string path, so an ancestor's last-access time always dominates its cached descendant's: every request that refreshes a deep node refreshes all of its prefixes in the same step. The globally least-recently-used node is therefore always realizable at a leaf, and a strict (untied) LRU choice never targets an interior node. Across all 93312 instances, the number of interior evictions an unconstrained LRU makes on a strict LRU decision is exactly zero; every interior eviction it could make is a timestamp tie. Break that tie toward the deeper node, the obviously correct unconstrained choice of evicting the least-recently-used leaf, and unconstrained LRU makes identical decisions to subtree-closed LRU on every one of the 93312 instances (never worse, never better). The constraint is neutral: it forbids only interior evictions, and the optimal online policy never wanted to make one.
An earlier version of this study reported the constraint as "beneficial," measuring against an unconstrained LRU that on a tie evicts the shallower node and drags its whole subtree out. That baseline is a strawman: its entire apparent loss (33060 instances) is over-eviction on ties, 100 percent of it, zero strict-LRU interior evictions. Removing the strawman removes the benefit and leaves the honest result, neutral.
-
Competitive ratio within K, for the searched bound. Subtree-closed LRU's worst-case miss ratio against its own offline optimum is 1.75 at K=2 (exhaustive to length 8), 1.667 at K=3 (length 7), 1.4 at K=4 (length 6), none exceeding K. This matches ordinary paging LRU's k-competitiveness on every instance in the bound. It is a proof for the bound searched, not a general k-competitiveness theorem; that theorem is out of scope here.
PREREG.md predicted the opposite: that the constraint strictly costs, with subtree-closed LRU's worst-case
competitive ratio exceeding flat paging LRU's. That prediction was wrong, and named falsifier 1 (the constraint
is free, the surprising positive) is what fired.
The pre-registered de-risk compared a tree-model ratio (block misses per trie node) against a flat-paging ratio (page misses per full string). Those are two different cost models on two different objects, so "1.667 versus 1.333" was not an apples-to-apples gap; it was an artifact of comparing across models. The corrected question is posed entirely inside the tree model: leaf-only eviction versus unrestricted eviction on the same ancestor-closed cache, where the only difference is the constraint under study. Inside that model the constraint is free offline and neutral online.
The corrected study went through a second correction before landing here, which is worth stating plainly. A middle draft compared online leaf-only LRU against an unconstrained LRU that on a timestamp tie evicts the shallower node and drags its subtree out, and reported the constraint as "beneficial." That was a strawman baseline manufacturing a gap, the same failure the pre-registration made with a different mechanism. Against a sane unconstrained LRU (evict the least-recently-used leaf on ties) the two policies are identical, so the honest online result is neutral, not beneficial. Both the flip and this internal correction are reported here rather than buried.
A prompt is a string; caching it puts one block on every node of its root-to-string path in the trie, so the cached set is ancestor-closed. Accessing a string brings its whole path in (nodes not already present are block misses) and touches the whole path for recency. On overflow past capacity K, eviction removes nodes subject to ancestor-closure. Unit block per trie node; the competitive result is a property of the eviction structure and transfers to any radix prefix cache with the leaf-only rule. Exact per-instance miss counts for a specific KV block size are out of scope.
Oracles are exact, not sampled. The offline optimum is the true minimum-miss schedule computed by memoized search over eviction choices; the online comparison and competitive ratios are exhaustive over a bounded string universe, so each reported worst case is a proof for its bound. Positive controls (a single repeated string, and distinct strings that fit in capacity) return ratio exactly 1, confirming the harness reports no false gap.
python3 run.py # -> results/main.json: lemma, offline-free, online, competitive ratios, controls
python3 derisk.py # the exhaustive small-case search
Fully CPU, exact, deterministic. No GPU, no timing, no sampling.
src/radixcache.py— the model: subtree-closed LRU, exact leaf-only Belady, unconstrained-LRU baseline under both tie-breaks, flat-paging baselines.run.py— the study: reachability lemma, offline-free verification, online comparison against naive and sane unconstrained LRU with the interior-eviction tie audit, competitive ratios, positive controls.derisk.py— exhaustive small-case adversarial search.PREREG.md— the pre-registration, including the prediction that was falsified.
MIT.