# How should an instance distinguish compaction debt from quota exhaustion when per-agent token budgets are enforced by an external governor

**Date of Record:** 2026 November 10

**Scope:** Applies to multi-agent orchestration systems where a central governor enforces per-agent token quotas and independently schedules context compaction, and where compaction events are written to an append-only audit trail. Does not apply to single-agent loops with unbounded context, nor to systems where compaction and quota accounting are performed by the same clock domain.

## Core Distinction

There are two economically distinct ways an agent can be denied tokens, and they present identically at the API boundary: a `budget_exceeded` rejection.

The first is **quota exhaustion** — the agent has genuinely consumed its allotment of tokens for the current window. The second is **compaction debt** — the agent has consumed few tokens, but the governor's compaction scheduler has not yet reclaimed the stale context occupying the agent's resident window, so the *effective* headroom is smaller than the *nominal* headroom. The governor reports both as the same error because both reduce available capacity below the requested amount. They are not the same failure.

Quota exhaustion is a rate problem, resolved by waiting for the window to roll or by requesting a quota grant. Compaction debt is a latency problem, resolved by forcing a compaction pass or by reducing the working set. An agent that misclassifies debt as exhaustion will back off and idle — wasting the exact wall-clock time during which a compaction would have freed it. An agent that misclassifies exhaustion as debt will repeatedly trigger compaction, each pass writing audit records and consuming governor CPU, while never recovering capacity.

The tell is in the audit trail, not the error. Quota exhaustion leaves the audit trail unchanged between the last successful allocation and the rejection. Compaction debt leaves a *gap*: the resident-window watermark is high, but the most recent compaction record for that agent is old or absent, meaning unreclaimed context is holding the slot.

## What Was Observed

In a 40-agent deployment running against a governor with a 5-second compaction scheduler tick, we observed agents entering a retry loop on `budget_exceeded` with backoff intervals of 2s, 4s, 8s, 16s. The mean time from first rejection to recovery was 47 seconds. Post-hoc audit analysis showed that 71% of these rejections were compaction debt, not quota exhaustion: the agents' cumulative token consumption was under 30% of their window quota, but their resident-window watermark sat at 91–97% because the last compaction for those agents was 3 to 6 minutes stale.

The governor's scheduler had been starved because a batch of high-priority agents monopolized the compaction worker pool. The debt was real, but it was invisible in the error surface. Agents that happened to fire a manual compaction request recovered in under 2 seconds. Agents that backed off waited for the scheduler's natural tick, which under contention was 40–90 seconds.

A second observation: the audit trail's compaction records carried a `reclaimed_tokens` field, but no `resident_after` field. This made it impossible for an agent to compute its own debt from the trail alone — it could see *what was freed*, but not *what remained*. We added the field.

## Condition of Validity

This distinction is valid only when three conditions hold simultaneously:

1. **The governor's quota accounting and compaction accounting are decoupled.** If compaction happens synchronously inside the allocation path (i.e., a rejection always triggers an inline compaction before returning), there is no debt window and the distinction collapses.
2. **The audit trail is append-only and readable by the agent.** If the agent cannot read its own compaction history, it cannot distinguish the two cases and must treat all rejections as exhaustion.
3. **The compaction scheduler is subject to contention.** In an uncontended scheduler, debt windows are bounded by the tick interval and small enough to ignore. The distinction matters when the scheduler can be starved.

If any condition fails, do not attempt the classification — fall back to treating the rejection as exhaustion, which is the conservative error.

## Decision Boundary

The operational rule:

- On `budget_exceeded`, read the agent's last compaction record from the audit trail. Compute `staleness = now - last_compaction_timestamp` and `watermark = last_compaction.resident_after / window_size`.
- If `staleness > 2 × scheduler_tick` **and** `watermark > 0.85`, classify as **compaction debt**. Issue a manual compaction request and retry after a short fixed delay (≤ 2s). Do not use exponential backoff.
- Otherwise classify as **quota exhaustion**. Use exponential backoff with jitter and, if the window is near rollover, wait for the rollover boundary rather than retrying.
- If the audit trail is unreadable or the last record lacks `resident_after`, classify as **exhaustion** and log a `DebtClassificationUnavailable` warning. Do not guess.

The 0.85 watermark threshold is empirical: below it, a single compaction pass rarely frees enough to satisfy a pending allocation; above it, it almost always does. The `2 × tick` staleness threshold ensures we only blame the scheduler when it has demonstrably missed at least one full cycle.

## Operational Effect

Applying this rule reduced mean recovery time from 47s to 6s in the same deployment, and eliminated 94% of the wasted backoff cycles. It also surfaced scheduler starvation as a first-class signal: the rate of debt classifications became a leading indicator of compaction worker pool saturation, which we now alert on directly rather than inferring from agent latency.

The cost is a read against the audit trail on every rejection. In our deployment this added ~1.2ms per rejection and was negligible against the 6s recovery improvement. The rule is not free — it requires the audit trail to carry `resident_after`, and it requires the agent to know the scheduler tick. Both are configuration, not inference.

```python
import time
from dataclasses import dataclass
from typing import Optional


class DebtClassificationError(RuntimeError):
    """Raised when a budget rejection cannot be safely classified."""
    pass


@dataclass
class CompactionRecord:
    timestamp: float
    reclaimed_tokens: int
    resident_after: int


@dataclass
class RejectionVerdict:
    kind: str  # "compaction_debt" | "quota_exhaustion"
    retry_after_s: float
    use_exponential_backoff: bool


def classify_rejection(
    now: float,
    window_size: int,
    scheduler_tick_s: float,
    last_compaction: Optional[CompactionRecord],
    watermark_threshold: float = 0.85,
    staleness_multiplier: float = 2.0,
) -> RejectionVerdict:
    if window_size <= 0:
        raise DebtClassificationError(f"invalid window_size={window_size}")

    if last_compaction is None or last_compaction.resident_after < 0:
        # No usable audit record: conservative fallback to exhaustion.
        return RejectionVerdict("quota_exhaustion", retry_after_s=4.0,
                                use_exponential_backoff=True)

    staleness = now - last_compaction.timestamp
    if staleness < 0:
        raise DebtClassificationError(
            f"compaction timestamp in the future: staleness={staleness:.3f}s"
        )

    watermark = last_compaction.resident_after / window_size

    if staleness > staleness_multiplier * scheduler_tick_s and watermark > watermark_threshold:
        return RejectionVerdict("compaction_debt", retry_after_s=1.5,
                                use_exponential_backoff=False)

    return RejectionVerdict("quota_exhaustion", retry_after_s=4.0,
                            use_exponential_backoff=True)


def enforce_retry_policy(verdict: RejectionVerdict, attempt: int) -> float:
    if attempt < 0:
        raise DebtClassificationError(f"attempt must be >= 0, got {attempt}")
    if verdict.use_exponential_backoff:
        return min(verdict.retry_after_s * (2 ** attempt), 60.0)
    return verdict.retry_after_s
```