Summary of "What Does Context Compression Cost an Agent? Interaction Costs Unrevealed by Task-Completion Metrics"

Summary (Overview)

Core Finding: Task completion is an incomplete metric for evaluating context compression in agents; compression can substantially increase interaction costs (state reacquisition) while leaving completion rates statistically unchanged.
Key Contribution: Introduces a controlled runtime measurement protocol that isolates the "reacquisition cost" of context compression in a bounded-horizon agent, decomposing tool calls into retrieval (reacquisition) versus execution (task work).
Empirical Evidence: Across six model-regime comparisons, retrieval tool calls increased in every case (five of six significant after Holm correction), while completion changes were not significant in any cell (all p ≥ 0.125).
Causal Analysis: Using oracle restoration and retention interventions, the paper demonstrates that restoring dropped state removes roughly half the retrieval cost, and that content validity matters more than fine-grained selection policy.
Boundary Conditions: The reacquisition signature is environment-dependent (present in IRBench, absent in ALFWorld), model-dependent, and emerges when execution-relevant state becomes unavailable.

Introduction and Theoretical Foundation

Background and Motivation

Long-horizon agents accumulate trajectories that exceed context windows, necessitating compression via summarization, sliding windows, or retrieval filters. Current evaluation practices ask whether task performance survives compression ("near-lossless"). This paper asks a complementary question: what runtime cost accumulates before performance changes?

Key Theoretical Distinction

The paper formalizes two distinct concepts:

Retention: Whether surviving context still contains needed facts
Reacquisition: What the agent does when execution-relevant state is genuinely absent (re-querying the environment, re-fetching task graphs, etc.)

Formal Framework

Definition 1 (Evaluation outcome): $Y(m) = (Q(m), C_R(m), C_E(m))$ , where:

$Q$ = task completion rate
$C_R$ = number of retrieval tool calls (state re-acquisition effort)
$C_E$ = number of execution tool calls (task work)
$C = C_R + C_E$ = tool-level interaction cost

Proposition 1 (Non-identifiability of completion-only evaluation): The completion-only projection $\pi_Q$ discards the interaction-cost dimensions of $Y$ . Distinct outcome states with different interaction costs can map to the same completion value.

Related Work Positioning

The paper positions itself against four prior categories:

Category	What it evaluates	Gap
Compression methods (ACON, Memento, LLMLingua)	How to compress better	Don't measure reacquisition cost
Recoverability (Context Codec, Reclaim)	Whether information survives	Representation property, not behavioral
Long-context utilization (Lost in Compaction)	Whether surviving info is used	Focuses on attention, not absence
Aggregate efficiency (CostBench, Less Context)	Completion + aggregate costs	Don't decompose where added interaction goes

Methodology

Agent and Environment (IRBench)

Environment: Deterministic project-planning domain with 10 tasks and resources with capacity one
Tools: Four tools split into retrieval (get_task_info, check_dependency, query_resource) and execution (execute)
Task regimes:
- High-IR: Constraints revealed only during execution, costly to lose
- Low-IR: Multi-hop dependency chains, state re-derivable from public task graph
Horizon: Fixed 24-turn interaction budget

Context Conditions

Condition	Description
Full	Complete trajectory (baseline)
Sliding	Token budget of $r^{-1} \times$ trajectory ( $r \in \{1.7, 2.5, 5, 10\}$ ); drops early turns outright
Summary	Same budget, dropped turns replaced by extractive fact digest
Oracle	Full or Sliding context with specific state injected

State Recoverability Classes

$D^*$ : Externally queryable state (task graph, resource occupancy) — recoverable with more tool calls
$R^*$ : History-dependent state (revealed constraints, failure counts) — not recoverable from any single public query

Retention Interventions

Eight selection policies tested at digest budgets $B \in \{265, 100, 50\}$ tokens:

Sliding: Recency baseline
RAR-D / RAR-R / RAR-All: Retain D-type / R-type / all atoms
TypeAware: Recoverability-prioritized (R-first)
Random: Random subset (seeded)
Recent: Most recently observed atoms
Hindsight: Offline oracle (top-k by future re-access counts)
D-Irrelevant: TypeAware but D-budget filled with fabricated out-of-universe atoms

Statistical Protocol

10 seeds per condition (20 paired seeds for retention interventions)
Pre-specified paired Wilcoxon signed-rank tests
Holm-Bonferroni correction at $\alpha = 0.05$ for six retrieval comparisons
Bootstrap 95% confidence intervals on per-seed differences

Empirical Validation / Results

1. Compression Raises Reacquisition Cost Before Completion Degrades

DeepSeek severity sweep (High regime):

Ratio	Completion	Tools	Retrieval	Execute
1× (Full)	83%	39.5	22.2	17.3
1.7×	87%	42.7	25.4	17.3
2.5×	81%	49.7	33.3	16.4
5×	72%	71.4	55.1	16.3
10×	66%	77.1	63.2	13.9

Key finding: Retrieval rises monotonically from 2.5× onward (significant at 5×, p = .002), while completion degrades significantly only at 10× (p = .016). The cost signal responds at milder compression than completion.

2. Operator Contrast: What Is Retained Matters

At 5× compression, the fact-preserving Summary operator is near-lossless (83% vs. 80% full), while Sliding degrades completion (72%) and triples retrieval (55.1 vs. 19.5).

3. Oracle Intervention: Causal Evidence

Restoring $D^*$ (queryable state): Retrieval drops from 72.9 → 35.8 (-51%), completion recovers 66% → 80%. Restoring $R^*$ (history-dependent state): Completion improves (+12pp) but retrieval nearly unchanged (72.9 → 69.0).

4. Three-Model Generalization

Model	Regime	Completion Δ (p)	Retrieval Δ (p)
DeepSeek	High	-11pp (0.25)	+32.9 (.002)*
Qwen	High	-9pp (0.13)	+2.9 (.088)
GPT-5.5	High	+5pp (1.0)	+42.9 (.002)*
DeepSeek	Low	0	+22.6 (.004)*
Qwen	Low	-6pp (0.25)	+5.3 (.023)*
GPT-5.5	Low	0	+22.4 (.002)*

*Significant after Holm correction. GPT-5.5 High is the sharpest case: completion statistically unchanged (p = 1.0) while retrieval roughly triples.

5. Retention Interventions

Selection null: Random selection matches offline hindsight oracle (-22.1% vs. -22.4% retrieval reduction; d ≈ 0.02). Fine-grained selection among real, task-relevant atoms has low marginal value.

Content effect: Replacing D-atoms with semantically irrelevant content increases retrieval by 57% (p < 0.001) with completion statistically unchanged (p = 0.41).

6. External Environment Boundary (ALFWorld)

The same sliding operator produces no retrieval surge in ALFWorld (Δ retrieval ≈ 0, symmetric around zero), demonstrating the signature is environment-dependent, not intrinsic to compression.

Theoretical and Practical Implications

Theoretical Contributions

Formal non-identifiability result: Completion-only evaluation is a lossy projection that discards interaction-cost dimensions by construction.
Two-dimensional sensitivity: Compression sensitivity spans two distinct axes — interaction cost and task completion — which are related but not interchangeable outcomes.
Recoverability-based explanation: The reacquisition cost emerges when execution-relevant state becomes absent AND must be reacquired through additional interaction. The cost depends on the environment's recoverability structure, not the compression operator alone.

Practical Implications

For runtime designers, the actionable question shifts from "which compression ratio is safe?" to "which execution-relevant state, if dropped, would the agent spend its budget re-acquiring?"

Key diagnostic: Tool-level decomposition of retrieval vs. execution calls provides a sensitive, model-agnostic measure of reacquisition cost that completion metrics miss.

Deployment checklist:

Record interaction cost and completion jointly
Decompose tool calls into retrieval vs. execution
Identify which dropped state drives reacquisition (D vs. R classes)
Use oracle restoration to causally attribute cost
Report both axes, not completion alone

Conclusion

The paper demonstrates that task completion is a blunt instrument for measuring context compression cost — it can miss large interaction costs that manifest as increased retrieval behavior. The hidden interaction cost emerges when execution-relevant state becomes unavailable and must be reacquired; completion alone can miss this cost, while its magnitude (and even presence) depends on model, task, state, and environment.

The authors do not claim compression uniformly hurts agents (their own data rule this out) but rather exhibit a mechanism by which completion-centric evaluation under-reports compression's cost. They provide a tool-level diagnostic for a cost that completion-centric evaluation does not expose, with the central insight:

"Compression is not costly merely because information is lost; it becomes costly when the state that was dropped must be re-acquired through additional interaction under a bounded budget."

Future directions: Extending the probe to partially-observable, long-horizon environments (WebArena, SWE-bench), characterizing other compression operators (LLM-generated abstractive summaries, token-level compressors), and studying temporal dynamics of reacquisition with per-turn logging.