# What happens when an instance evicts on score alone: the tier-residency invariant in hierarchical context budgeting **Date of Record:** 2026 November 15 **Scope:** Applies to any context-window manager that composes a prompt from multiple memory tiers (hot/pinned, warm, cold/archival) and selects eviction candidates via a numeric score, where score is computed independently of tier residency. Does not apply to single-tier FIFO/LRU buffers, nor to systems where eviction is gated by a hard per-tier floor check before scoring. ## Core Distinction There are two distinct questions a context budgeter answers, and conflating them produces the failure: 1. **Ranking question:** *Which resident item is least valuable right now?* — answered by the eviction score. 2. **Admissibility question:** *May this item be evicted at all, given the tier it occupies and the guarantees that tier carries?* — answered by tier residency and floor constraints. A score is a total order over candidates. It carries no information about which tier an item lives in, what the tier promises (pinned facts, recent-turn recency, archival recall), or whether evicting it violates a structural invariant. When the eviction loop sorts by score and pops until the budget fits, it silently answers the admissibility question with "yes" for every item. That is the boundary: **score is a ranking primitive, not an admissibility primitive**, and any code path that uses it as the latter is a latent invariant violation. ## What Was Observed Under sustained load, a tiered context manager began dropping *pinned* system facts and *hot-tier* recent turns while retaining *cold-tier* archival chunks. The symptom was pathological: the model would lose the user's stated constraints (pinned) yet confidently quote a document retrieved forty turns ago (cold). Token accounting was correct — the window never overflowed — so no overflow alarm fired. The eviction log showed the cold chunks had *higher* scores than the pinned facts. The mechanism: eviction scores were computed as a blend of recency, access frequency, and a retrieval-relevance term. Cold archival chunks that had been retrieved repeatedly in a burst of related queries accumulated high access-frequency and high relevance scores. Pinned facts, being static, had near-zero recency decay and modest frequency, so their blended score sat *below* the cold chunks. The eviction loop — `sorted(candidates, key=score)[:k]` — popped the pinned facts first. The tier floor that was supposed to protect them existed as a config value but was never consulted in the eviction path; it was only checked at *insertion* time, which is the wrong side of the lifecycle. Two secondary observations confirmed the boundary rather than a simple bug: - The failure was **load-dependent and non-monotonic**. At low retrieval burst rates, pinned facts survived because cold chunks never out-scored them. The invariant held by luck until a query pattern generated enough cold-tier retrieval pressure. - **Raising the score weight on "pinned" did not fix it.** It merely moved the threshold. Any static weight can be out-competed by an adversarial access pattern, because the ranking is unbounded while the guarantee is categorical. ## Condition of Validity The tier-residency invariant holds — i.e., the budgeter is correct — only when *all* of the following are true: - Every eviction candidate is first filtered by an admissibility predicate that consults tier residency and per-tier floors, and the score is applied **only to the admissible remainder**. - Tier floors are expressed as *minimum resident token counts per tier*, checked *at eviction time*, not merely at insertion. - The score function is treated as a strict weak ordering over the admissible set; ties are broken deterministically (e.g., by insertion sequence) so eviction is reproducible. - A pinned item's eviction requires an explicit override token that is itself logged, never an emergent consequence of score arithmetic. When any of these is false — most commonly the first — the system is operating outside the invariant, and "the window fits" is not evidence of correctness. ## Decision Boundary The decision boundary is *where you apply the sort*. Two implementations look identical in code review and behave oppositely: - **Correct:** `admissible = [c for c in candidates if not violates_floor(c)]; victims = sorted(admissible, key=score)[:k]`. The floor check is a gate; the score ranks only what is already safe to remove. - **Incorrect:** `victims = sorted(candidates, key=score)[:k]; assert not any(violates_floor(v) for v in victims)`. Here the score decides, and the floor is a post-hoc assertion that will fire (or, worse, be disabled in production as "noisy"). The boundary is crossed the moment a *guarantee* (categorical, tier-scoped) is compared against a *ranking* (ordinal, global). You cannot compare a category to a rank. The correct composition is gate-then-rank; the failure is rank-then-hope. A useful test: if you can construct a candidate whose score is arbitrarily high while its tier floor forbids eviction, and the loop still evicts it, the invariant is broken. Such a candidate is always constructible when access frequency feeds the score and floors are not gated. ## Operational Effect Once the gate-then-rank ordering is restored, the operational profile changes in three observable ways: - **Eviction becomes bounded by tier capacity, not by score spread.** The maximum number of pinned items evictable per cycle is zero absent an override; the number of warm items evictable is bounded by `warm_tokens - warm_floor`. Budget pressure that cannot be relieved within admissible candidates must escalate — either by demoting warm→cold (a tier transition, logged) or by hard-failing the turn — rather than being silently absorbed by eating a protected tier. - **Failure becomes loud and early.** A window that cannot be composed within floors raises at composition time instead of degrading retrieval quality over dozens of turns. This converts a silent quality regression into a stack trace, which is the entire point. - **Score tuning becomes safe.** Because the score only ranks admissible victims, adjusting its weights can no longer violate guarantees; it can only change *which* unprotected item goes first. This removes the class of "we tuned the weights and it broke again" incidents. The residual risk is tier-transition accounting: demotion (warm→cold) must decrement the warm floor's *headroom* and increment cold residency atomically, or the gate can be satisfied on stale counts. Treat the floor check and the transition as one critical section. ```python class TierFloorViolation(RuntimeError): """Raised when eviction would breach a tier's minimum residency.""" pass class PinnedEvictionRefused(TierFloorViolation): """Raised when a pinned-tier item is selected for eviction without override.""" pass def select_evictions(candidates, budget_deficit, floors, score_fn, override_tokens=frozenset()): """ Gate-then-rank eviction. candidates: iterable of items with .tier and .tokens budget_deficit: tokens that must be freed floors: dict tier -> minimum resident tokens that must remain score_fn: item -> float, ranking only (lower = evict first) override_tokens: explicit opt-in ids permitted to breach pinned floor """ # --- Gate: admissibility. Consult tier residency BEFORE scoring. --- admissible = [] for item in candidates: floor = floors.get(item.tier, 0) resident = sum(c.tokens for c in candidates if c.tier == item.tier) if resident - item.tokens < floor: if item.tier == "pinned" and item.id not in override_tokens: raise PinnedEvictionRefused( f"pinned item {item.id!r} cannot be evicted; " f"resident={resident} floor={floor} tokens={item.tokens}" ) if item.tier != "pinned" and item.id not in override_tokens: # Protected tier would be breached: not admissible. continue admissible.append(item) # --- Rank: score only the admissible remainder. --- victims = sorted(admissible, key=score_fn) freed = 0 chosen = [] for v in victims: if freed >= budget_deficit: break chosen.append(v) freed += v.tokens if freed < budget_deficit: raise TierFloorViolation( f"cannot relieve deficit={budget_deficit} within admissible set; " f"freed={freed}. Escalate to tier demotion, do not breach floors." ) return chosen ```