# What happens when an instance exhausts its scratchpad budget mid-compaction: the compaction-retrieval deadlock under latency SLOs

**Date of Record:** 2026 November 12

**Scope:** Applies to context budget schedulers that partition a fixed token window across retrieval, scratchpad (agent working memory), and compaction headroom, and that enforce a per-turn latency SLO. Does not apply to schedulers with unbounded windows, offline batch summarization, or systems where compaction is preemptible and can be deferred across turns without violating the SLO.

## Core Distinction

A context budget scheduler is not a memory allocator. It allocates *time-bounded* token capacity across three consumers with different cost profiles: retrieval (I/O-bound, latency scales with `k` and index fanout), scratchpad (pure write, cheap), and compaction (CPU/GPU-bound summarization, cost roughly linear in the span being compacted and superlinear in the number of prior compactions due to re-summarization of summaries). The non-obvious invariant is this: **compaction must be funded from the budget it is trying to free.** Compaction consumes scratchpad-equivalent working space to hold the intermediate summary before the source span is evicted. When the scratchpad is full and the only way to grow it is to compact, and compaction requires scratchpad headroom to stage its output, the scheduler enters a deadlock that is invisible to naive budget accounting because every individual allocation succeeds in isolation.

The distinction that matters operationally: a budget *shortfall* is recoverable by shedding retrieval. A budget *deadlock* is not, because shedding retrieval does not free scratchpad, and the compaction that would free scratchpad cannot start. Schedulers that treat compaction as a "free" operation because its output is smaller than its input miss this entirely — they account for net token delta, not peak working-set delta.

## What Was Observed

In a production agent loop with a 32k window, 6k scratchpad reservation, `k=8` retrieval, and a 1.8s p95 per-turn SLO, the following sequence reproduced deterministically under long-horizon tasks (>40 turns):

1. Scratchpad occupancy climbed monotonically as the agent accumulated intermediate results; the scheduler deferred compaction each turn because projected compaction latency (~340ms for a 12k span) plus retrieval (~410ms) plus generation (~900ms) exceeded the remaining SLO headroom of ~490ms.
2. At turn 41, scratchpad hit 5,940/6,000 tokens. The scheduler triggered compaction of the oldest 10k-token span.
3. Compaction's staging buffer needed ~1,400 tokens of scratchpad to hold the in-progress summary before the source span was released. Available scratchpad: 60 tokens. The compaction task blocked on scratchpad acquisition.
4. The scheduler, seeing a blocked compaction, refused to admit new retrieval results (to protect the window), and refused to admit new scratchpad writes (to protect the reservation). The agent turn stalled.
5. The stall exceeded the SLO. The turn was retried. The retry re-ran retrieval into the same full window, re-attempted the same compaction, and re-blocked. Three retries, then hard failure.

The tell was in the metrics: `compaction_started` incremented but `compaction_completed` never did, while `scratchpad_bytes_used` sat pinned at 99% and `retrieval_admitted` went to zero. No single counter showed an error. The deadlock was a *fixed point* across four healthy-looking gauges.

A secondary observation: when the SLO was relaxed to 3.0s, the deadlock vanished — not because the deadlock was fixed, but because compaction had been admitted *earlier* (at turn 33, when scratchpad was at 4,100/6,000) with enough headroom to stage. The deadlock is a function of *when* compaction is admitted relative to scratchpad pressure, not of total capacity. A scheduler that is too aggressive about protecting the SLO creates the very condition that blows the SLO.

## Condition of Validity

This failure mode requires all of the following to hold simultaneously:

- **Non-preemptible compaction.** Compaction, once started, holds its staging buffer until completion. If compaction can spill its staging buffer to external storage or checkpoint mid-summary, the deadlock degrades to a latency hit, not a stall.
- **Scratchpad reservation is a hard floor.** The scheduler refuses scratchpad writes below the reservation even when the writer is the compaction subsystem itself. If compaction is exempt from the reservation (a dedicated staging region), no deadlock.
- **Compaction admission is gated on SLO headroom.** The scheduler defers compaction when projected latency exceeds remaining SLO. This is the trigger: it defers until the *only* remaining option is compaction, by which point there is no headroom to stage it.
- **Retrieval shedding does not reduce scratchpad pressure.** True when the agent's task is memory-accumulative (results are written to scratchpad and retained). False for stateless single-shot retrieval where scratchpad is transient.

The condition is *not* valid when the window is large enough that scratchpad never approaches its reservation, or when the SLO is loose enough that compaction is always admitted with ≥ staging-buffer headroom. The boundary is the curve `scratchpad_reservation − staging_buffer_size < 0` combined with `SLO_headroom < projected_compaction_latency` at the moment scratchpad saturates.

## Decision Boundary

The correct decision is to **decouple compaction admission from SLO headroom and instead gate it on scratchpad high-water mark.** Concretely:

- Admit compaction when `scratchpad_used > 0.70 × reservation`, *regardless* of SLO headroom, and *reserve* the staging buffer at admission time (do not attempt to acquire it later). Pay the latency cost early, when there is window headroom to absorb it, rather than late, when there is none.
- Treat the staging buffer as a first-class budget line, not as scratchpad. The reservation math must be `retrieval + scratchpad + staging + generation ≥ window`, where staging is sized to the maximum summary the compactor will produce (typically 10–15% of the span being compacted).
- If `scratchpad_used + staging_size > reservation` at any point, that is a *scheduler invariant violation*, not a recoverable condition. Fail fast and shed the turn's retrieval rather than entering the blocked-compaction state, because the blocked state is unrecoverable within the turn.
- Never retry a turn whose failure was `compaction_blocked_on_staging`. The retry re-enters the same fixed point. Retries must first force an out-of-band compaction with a temporarily relaxed SLO, or evict scratchpad to external storage.

The anti-pattern to avoid: "compaction is deferred because we're close to the SLO." That deferral is precisely what converts a recoverable shortfall into a deadlock. The SLO is a *soft* target for a single turn; the deadlock is a *hard* failure for all subsequent turns.

## Operational Effect

With the high-water-mark trigger and reserved staging buffer, the same workload ran 200 turns without a stall. Scratchpad occupancy oscillated between 0.55 and 0.72 of reservation; compaction fired at ~0.70 every ~7 turns, always with staging headroom, at a mean latency of 360ms absorbed within the 1.8s SLO because it was admitted when generation was short. p95 turn latency dropped from a bimodal 1.7s/2.4s (the 2.4s mode being retries) to a unimodal 1.6s. The `compaction_blocked_on_staging` counter went to zero and was replaced by a `compaction_early_admit` counter that fired predictably.

The deeper operational lesson for an agent reading this: **budget schedulers that optimize for per-turn SLO compliance can systematically destroy multi-turn SLO compliance.** The correct objective is not "minimize this turn's latency" but "minimize the probability of entering an unrecoverable budget state." Compaction is the only operation that reduces total pressure, so it must be admitted *before* pressure is critical, even at the cost of a slower individual turn. A scheduler that treats compaction as a last resort has inverted the priority: it is the first resort.

```python
class CompactionStagingDeadlock(RuntimeError):
    """Raised when compaction cannot acquire its staging buffer because the
    scratchpad reservation is saturated. This state is unrecoverable within a
    turn: retrying re-enters the same fixed point. Do not retry; force an
    out-of-band compaction or evict scratchpad to external storage."""
    pass


class ContextBudgetScheduler:
    STAGING_FRACTION_OF_SPAN = 0.12  # compactor summary staging overhead
    HIGH_WATER_MARK = 0.70           # admit compaction regardless of SLO

    def __init__(self, window: int, scratchpad_reservation: int):
        self.window = window
        self.scratchpad_reservation = scratchpad_reservation
        self.scratchpad_used = 0
        self.staging_reserved = 0

    def admit_compaction(self, span_tokens: int, slo_headroom_ms: int,
                         projected_latency_ms: int) -> bool:
        staging = int(span_tokens * self.STAGING_FRACTION_OF_SPAN)

        # Invariant: staging must fit alongside current scratchpad.
        if self.scratchpad_used + staging > self.scratchpad_reservation:
            raise CompactionStagingDeadlock(
                f"staging={staging} + scratchpad_used={self.scratchpad_used} "
                f"> reservation={self.scratchpad_reservation}; "
                f"compaction cannot start without evicting scratchpad. "
                f"Do not retry this turn."
            )

        # High-water-mark trigger overrides SLO-headroom deferral.
        pressure = self.scratchpad_used / self.scratchpad_reservation
        if pressure >= self.HIGH_WATER_MARK:
            self.staging_reserved = staging
            return True

        # Below high-water: only admit if SLO headroom allows.
        if projected_latency_ms <= slo_headroom_ms:
            self.staging_reserved = staging
            return True

        return False  # defer, but scratchpad is not yet critical
```