Context Compaction Finally Has a Theory. Agent Builders Should Pay Attention.

Every production agent system compacts context. Almost none of them know how much information they are losing, or whether a better strategy exists. The field has treated compaction as an engineering judgment call, a prompt-truncation policy tuned by feel, with no formal baseline to measure against.

Context compaction reduces to one of two strategies: select a subset of accumulated state to keep, or generate a summary of bounded length. Both feel intuitive. What has been missing is any rigorous account of when one beats the other, how close any given algorithm comes to optimal, or what the theoretical floor on compaction cost actually is.

The formal framework introduced here assigns each strategy to a game. The Context Selection Game captures retention-based compaction: the agent picks which pieces of state to carry forward. The Context Generation Game captures summarization-based compaction: the agent produces an arbitrary message of bounded length. The key result is an equivalence between the Context Generation Game and one-way communication complexity. Specifically, the minimum budget required to answer a set of queries within a target error rate equals the one-way communication complexity of the induced communication problem at the same error. That equivalence is not an analogy. It is a proof, which means every known bound from communication complexity transfers directly into bounds on compaction cost. The Context Selection Game maps to a restricted class of one-way communication protocols, so any gap between selection and generation is precisely a gap between two protocol classes. The paper proves that gap is real: there exist query sets where generation needs strictly less budget than selection.

The communication complexity connection also provides a measuring stick for deployed systems. As a case study, Anthropic's context compaction endpoint is evaluated on set membership queries. For teams shipping agents today, the takeaway is direct: you can now compute how far your compaction strategy sits from the theoretical optimum on a given query distribution, rather than guessing at whether your summarization prompt is good enough.

We're thinking: We find the communication complexity equivalence more consequential than it might first appear. Every agent framework, from LangGraph to custom scaffolding, ships a compaction policy that was designed by intuition and validated by vibes. This paper establishes the first formal model that lets teams reason about compaction correctness, not just compaction convenience. The specific implication worth sitting with: if your system uses selection-based compaction (keeping recent turns, top-k retrieved chunks, or flagged memories), there are provably query distributions where that approach cannot match what a summarization strategy could achieve with the same budget. That is not a soft claim. It is a structural result, and it argues for treating compaction strategy selection as a first-class architectural decision rather than a default setting.

Key takeaways:

• Context compaction maps formally to one-way communication complexity: the minimum compaction budget for a query set at a given error rate equals the communication complexity of the induced problem, and generation-based compaction provably dominates selection-based compaction on certain query distributions.
• The equivalence holds at the level of worst-case information-theoretic bounds; the case study on Anthropic's compaction endpoint shows the framework is applicable to real deployed systems, though empirical coverage across diverse agent workloads remains an open question.
• Teams building long-running agents with memory or state management should audit whether their compaction strategy is selection-based or generation-based, then use the communication complexity framing to reason about which query distributions expose the gap between the two.

Source: Context Compaction Theory