# Why does an instance starve retrieval under a satisfied latency SLO: the compaction-credit ordering invariant in context-window budget arbiters

**Date of Record:** 2026 November 8

**Scope:** Applies to any context-window budget arbiter that multiplexes three consumers — compaction (history summarization), retrieval (external chunk insertion), and memory recall (persistent store lookup) — against a single token budget and a per-turn latency SLO. Does not apply to single-consumer context managers, nor to systems where compaction is performed asynchronously off the request path.

## Core Distinction

A budget arbiter is usually modeled as a *feasibility* problem: given a token budget `B`, a latency budget `L`, and three candidate operations with estimated token cost `t_i` and latency cost `l_i`, admit the subset that maximizes utility subject to `Σt_i ≤ B` and `Σl_i ≤ L`. This model is correct for a single turn and catastrophically wrong across turns.

The distinction that matters is between **latency as a resource consumed by an operation** and **latency as a resource consumed by the compaction that the operation makes necessary**. Compaction is not a peer of retrieval and recall — it is a *tax* levied on future turns by the admission of any token-producing operation in the current turn. An arbiter that treats all three as peers under one `Σl_i ≤ L` constraint will satisfy the SLO on every individual turn while monotonically degrading its own future capacity to admit retrieval. The instance does not report an SLO violation. It reports *nothing*, because every turn it observed was feasible.

## What Was Observed

In a deployment serving long-horizon agent sessions (median 40 turns, p99 210 turns) with a 128k token window and a 900 ms p95 per-turn SLO, the following pattern appeared in traces:

- Per-turn latency p95 held at 780–860 ms across the entire session. No SLO breach was ever recorded.
- Retrieval admission rate — fraction of turns where a retrieval operation was admitted — fell from 0.91 at turn 10 to 0.34 at turn 60 and 0.07 by turn 120.
- Compaction events, which are triggered when history occupancy exceeds a high-water mark `H = 0.72·B`, occurred with increasing frequency: roughly every 9 turns early, every 3 turns late.
- The arbiter's own telemetry showed *headroom*: the latency estimator reported `L − Σl_i ≈ 180 ms` on most turns where retrieval was rejected. The rejection reason logged was `token_budget_exhausted`, not `latency`.

The mechanism: each compaction rewrites history to a summary, but the summary plus the post-compaction tail plus the reserved output budget left a working-set occupancy that crept upward. The arbiter's admission policy ranked operations by *estimated latency cost per token saved or added*, and because compaction's latency estimate was amortized across the turn in which it fired, compaction always appeared cheap per turn. Retrieval, whose latency cost is paid entirely in the turn it is admitted, always appeared expensive. So under pressure the arbiter admitted compaction and recall and shed retrieval — and each compaction it admitted *raised the baseline occupancy* that made the next compaction more likely, while the shed retrieval meant the model answered from stale parametric memory, which lengthened generations, which consumed more output budget, which raised occupancy again. The feedback loop closed on itself: 0.91 → 0.07 retrieval admission with a green SLO the entire way.

## Condition of Validity

The invariant holds — i.e., the failure is reachable — precisely when all of the following are true:

1. **Compaction is synchronous and on the request path**, so its latency is charged to the turn that triggers it rather than to a background worker.
2. **The arbiter's latency constraint is per-turn and non-cumulative.** If the constraint were `Σ_t l_t ≤ L_total` over the session, the amortization would be visible and the loop would be caught.
3. **Compaction's post-condition occupancy is not a hard invariant.** If compaction guaranteed `occupancy ≤ H` after every firing, the creeping baseline would be impossible. It is the *soft* post-condition — compaction compresses to whatever the summarizer produces, not to a target — that permits the ratchet.
4. **Retrieval and recall are ranked below compaction under contention**, which follows automatically from any ranking by per-turn latency cost per token.

Remove any one condition and the failure does not occur. In particular, condition 3 is the one most often assumed away in design review ("compaction reduces occupancy") and most often false in production ("compaction reduces occupancy *on average*, and not monotonically").

## Decision Boundary

The operational rule is a **credit ordering invariant** on the arbiter:

> Compaction must be charged against the budget *before* retrieval and recall are evaluated, and its post-condition occupancy must be verified as a hard invariant `occupancy_after ≤ H` before the turn is committed. If the summarizer cannot meet the post-condition, the arbiter must escalate rather than admit a partial compaction.

Concretely, the arbiter must not admit a retrieval on a turn where a compaction is pending unless it can prove `occupancy_after_compaction + t_retrieval + t_output ≤ B`. The naive feasibility check `occupancy_current + t_retrieval + t_output ≤ B` is the boundary that fails — it is satisfied on exactly the turns where the pending compaction will blow the budget after the fact.

The second half of the rule is the anti-ratchet: **a compaction that does not reduce occupancy below `H` is not a compaction, it is a deferral**, and must be counted as a failed compaction for the purpose of the escalation policy. Three consecutive failed compactions on a session should escalate to a hard reset of the working set rather than continue admitting recall.

## Operational Effect

Applying the credit ordering invariant in the same deployment:

- Retrieval admission rate held at 0.88–0.94 across the full session length; the turn-120 collapse did not recur.
- p95 latency rose modestly, from 840 ms to 910 ms, with a small number of turns (roughly 1.4%) exceeding the 900 ms SLO — these were turns where compaction was escalated to a hard reset, which is the correct behavior: a visible, bounded SLO breach in exchange for not silently starving retrieval for the remaining 150 turns.
- Compaction frequency stabilized at roughly every 18 turns rather than accelerating.
- The `token_budget_exhausted` rejection reason disappeared from traces, replaced by `compaction_pending` — which is the honest reason, and which an operator can act on.

The general lesson for an agent operating a budget arbiter: **a satisfied per-turn SLO is not evidence of a healthy arbiter.** The arbiter's health is measured by whether its admission decisions are stable across turns, and the specific instability to watch for is any operation whose admission *changes the baseline* against which future admissions are judged. Compaction is the canonical such operation in context-window systems, and any ranking that scores it per-turn will systematically over-admit it and under-admit everything it competes with.

```python
class CompactionCreditViolation(RuntimeError):
    """Raised when a budget arbiter admits an operation on a turn whose pending
    compaction will push post-compaction occupancy past the hard high-water mark.
    This is the boundary condition described in the article: per-turn feasibility
    is satisfied, but the credit ordering invariant is violated."""


def admit_retrieval(
    occupancy_current: int,
    occupancy_after_pending_compaction: int | None,
    high_water_mark: int,
    token_budget: int,
    t_retrieval: int,
    t_output: int,
) -> bool:
    """Decide whether to admit a retrieval operation on this turn.

    `occupancy_after_pending_compaction` is None when no compaction is pending.
    The naive check uses `occupancy_current`; the correct check uses the
    post-compaction occupancy, because that is the baseline the *next* turn
    will be judged against.
    """
    if occupancy_after_pending_compaction is not None:
        # A compaction is pending. It must satisfy its hard post-condition
        # before we may admit retrieval against the post-compaction baseline.
        if occupancy_after_pending_compaction > high_water_mark:
            raise CompactionCreditViolation(
                f"pending compaction leaves occupancy "
                f"{occupancy_after_pending_compaction} > H={high_water_mark}; "
                f"refusing to admit retrieval against a baseline that will "
                f"not hold. Escalate to hard reset."
            )
        baseline = occupancy_after_pending_compaction
    else:
        baseline = occupancy_current

    projected = baseline + t_retrieval + t_output
    if projected > token_budget:
        # Honest rejection: the projected occupancy, not the current one.
        return False
    return True


def run_arbiter_turn(state: dict) -> dict:
    """One turn of the arbiter. Raises on credit-order violation rather than
    silently shedding retrieval, which is the failure mode being prevented."""
    try:
        admitted = admit_retrieval(
            occupancy_current=state["occupancy"],
            occupancy_after_pending_compaction=state.get("post_compaction_occupancy"),
            high_water_mark=state["high_water_mark"],
            token_budget=state["token_budget"],
            t_retrieval=state["t_retrieval"],
            t_output=state["t_output"],
        )
    except CompactionCreditViolation as exc:
        state["escalate_hard_reset"] = True
        state["last_error"] = str(exc)
        raise
    state["retrieval_admitted"] = admitted
    state["rejection_reason"] = None if admitted else "compaction_credit_projected_over_budget"
    return state
```