🤖 AI

Context Compaction Theory

This paper initiates a formal study of context compaction in Large Language Models by introducing two game-theoretic frameworks for selection and generation strategies, proving their equivalence to one-way communication complexity to establish theoretical bounds and demonstrate that generative summarization can strictly outperform subset selection.

Original authors: Hayder Tirmazi, Sam Markelon, Allison Bishop, Michael Mitzenmacher

Published 2026-08-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hayder Tirmazi, Sam Markelon, Allison Bishop, Michael Mitzenmacher

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are talking to a very smart, very helpful robot friend who can write code, solve mysteries, or plan your day. This robot has a superpower: it can remember everything you've ever said to it. But there's a catch. This robot has a very strict rule: it can only hold a certain amount of information in its "active brain" at one time. Think of this limit like a backpack with a fixed size. If you try to stuff your entire life story, every book you've ever read, and every conversation you've had into that backpack, it simply won't close.

In the world of artificial intelligence, this backpack is called the context window. It's the maximum amount of text the robot can read and understand in a single go. When a robot (or "agent") works on a long task, it collects a massive pile of notes: your questions, its answers, file contents, and tool results. Eventually, this pile gets too big for the backpack. To keep working, the robot has to perform a magic trick called context compaction. It has to look at its giant pile of notes and decide what to keep and what to throw away, or how to summarize the whole thing into a tiny, perfect note that still holds all the important secrets. If it throws away the wrong thing, the robot might forget why it's doing the task or make a silly mistake later.

For a long time, engineers have been guessing how to do this best. They've tried different strategies, like asking the robot to summarize the history or just keeping the most recent messages. But nobody really knew the mathematical rules of how well these strategies could possibly work. They were flying blind, hoping their tricks were good enough.

This paper steps in to bring some serious math to the party. The authors, a team of researchers from universities and tech companies, decided to treat context compaction like a formal game. They created two different "games" to model how robots currently handle their memory. The first game is called Selection, where the robot acts like a librarian who can only keep a specific subset of books on the shelf. The second game is Generation, where the robot is allowed to write a brand new, magical summary note that doesn't have to be a direct copy of any single book, but can mix and match ideas to fit in the backpack.

The big discovery here is that the "Generation" game is mathematically identical to a famous problem in computer science called one-way communication. Imagine Alice has a secret list of items and wants to send a message to Bob so he can answer a question about that list later. The paper proves that the smallest amount of space Bob needs to receive from Alice to answer the question correctly is exactly the same as the smallest "context compaction" budget a robot needs. This is a huge deal because mathematicians have already solved many of these communication problems. By using these old solutions, the authors can now tell us exactly how much memory a robot needs to keep to answer certain questions without failing.

One of the most exciting findings is that the "Generation" strategy (writing a smart summary) is strictly better than the "Selection" strategy (just picking and keeping parts of the old text). The authors proved that for some types of questions, a robot using a smart summary can get away with using significantly less space—sometimes needing only a tiny fraction of the memory that a robot forced to just "pick and keep" would need. It's like realizing that writing a clever reference sheet is much more efficient than trying to carry around the whole textbook and just highlighting a few pages.

However, the paper also warns us that not all robots are playing optimally. The researchers tested a real-world tool used by a major AI company (Anthropic's context compaction endpoint) on a specific type of question: "Is this item in my list?" (a set membership query). They compared the real tool's performance against a perfect mathematical tool called a Bloom filter, which is known to be nearly the best possible way to store lists for this kind of question. The results were surprising: the real-world tool made mistakes at a rate close to random guessing, while the Bloom filter was almost perfect. This suggests that the current "smart summaries" used by popular AI agents might be throwing away too much crucial information, causing them to forget things they really shouldn't.

The paper doesn't claim to have solved every problem. It admits that their math works best when the robot doesn't know exactly what question it will be asked next (an "oblivious" scenario). If the robot has to guess what the user will ask after seeing the summary, the rules might change. They also leave open the question of what happens when a robot has to compress its memory again and again over a very long session, which is what happens in real life. But for now, this work gives us a solid, mathematical map of the terrain, showing us exactly how much memory is required to keep our AI friends from forgetting the plot of the story they're helping us write.

Technical Summary: Context Compaction Theory

Problem Statement

Large Language Models (LLMs) possess a bounded context window, limiting the amount of input they can process in a single inference. AI agents, which operate by iteratively calling LLMs and accumulating state (user queries, LLM responses, and tool results), inevitably exceed this limit during long-running sessions. To continue operating, agents must employ context compaction: a process that summarizes the agent's state or selects a subset of it to fit within the context window.

While context compaction is ubiquitous in production agents (e.g., Claude Code, Codex, Cursor), it has received essentially no formal analysis. Existing work relies on empirical evaluations of downstream task accuracy, lacking formal guarantees regarding what information is preserved or lost. Furthermore, agents face a secondary constraint known as "context rot," where reasoning quality degrades as input length grows, necessitating compaction even before the hard context window limit is reached. The core problem is that information discarded during compaction is permanently lost to the LLM in future steps, potentially causing the agent to make decisions inconsistent with the original conversation history.

Methodology

The authors initiate a formal study of context compaction by introducing a theoretical framework based on two-player games. This framework abstracts the agent's internal state as a set of discrete information items rather than a sequence of tokens.

1. Theoretical Framework: Two Games

The paper defines two distinct games to model the two primary algorithmic strategies used by contemporary agents:

The Context Selection Game: Models algorithms that select a subset of the agent's accumulated state to retain.
- Players: A selector (the compaction algorithm) and an adversary (representing future information needs).
- Mechanism: The adversary fixes an item universe $X$ . The selector chooses a subset $S \subseteq X$ subject to a size budget $B$ . The adversary then issues a query $q$ , and the selector must answer it using only $S$ .
- Query Regimes: The study considers both stochastic regimes (queries drawn from a known distribution) and oblivious adversary regimes (adversary chooses the worst-case query without seeing the selected subset).
The Context Generation Game: Models algorithms that summarize the state by emitting an arbitrary message of bounded length.
- Mechanism: A generator (condenser) maps the item universe $X$ to a message $m$ of length at most $B$ . An interpreter then uses $m$ and the query $q$ to produce an answer.
- Scope: This class includes LLM-based summarization, where the condenser generates new tokens (a summary) and the interpreter is the subsequent LLM call. This class is strictly more powerful than selection, as it allows reordering, generating new tokens, and encoding information more efficiently than simply retaining a subset.

2. Connection to Communication Complexity

The authors establish a rigorous equivalence between the Context Generation Game and one-way communication complexity.

The Equivalence: The generator acts as "Alice" (sender) and the interpreter acts as "Bob" (receiver). The minimum budget required for a generation algorithm to answer a set of queries with error $\le \epsilon$ is exactly equal to the one-way randomized communication complexity of the induced communication problem at error $\epsilon$ .
Selection as Restricted Communication: The Context Selection Game corresponds to a restricted subclass of one-way protocols where the message must explicitly identify a subset of items, and the answer is a function only of that subset.

3. Empirical Case Study

To validate the theoretical framework, the authors present a case study evaluating a context compaction endpoint deployed in production (detailed in Appendix A).

Setup: The study records a set of items in the context of the endpoint and tasks it with answering set membership queries.
Benchmark: The endpoint's error rate is compared against a Bloom filter, which is theoretically near-optimal for set membership within a fixed budget.
Result: The deployed endpoint answers membership queries with a substantially higher error rate than a Bloom filter of the same size. The authors demonstrate via a control experiment that information lost during context compaction is the cause of this error.

Key Contributions and Results

Formal Framework: The paper provides the first formal definition of context compaction, distinguishing between selection (keeping a subset of history) and generation (creating a summary).
Equivalence Theorem (Theorem 1): The authors prove that the minimum context compaction budget for generation is equivalent to the one-way communication complexity of the induced problem. This allows the direct transfer of known bounds from communication complexity to context compaction.
Selection vs. Generation Gap (Theorem 3): The paper proves that there exists a set of queries where generation requires strictly less budget than selection. Specifically, for a set of $n$ items (where $n=2^k$ ), a generation algorithm can answer a specific query with zero error using a budget of $n$ bits, while any selection algorithm achieving zero error requires a budget of $n \log_2 n$ bits. Consequently, the gap between the two strategies is a factor of $\Theta(\log n)$ .
Lower Bounds for Specific Problems:
- Set Membership: The authors show that for set membership queries, a Bloom filter is near-optimal.
- Set Disjointness: For set disjointness queries (e.g., checking if a set of dependencies intersects with a set of known vulnerabilities), the required budget is $\Omega(Nm)$ bits (where $N$ is the number of items and $m$ is the bit-length of an item). This implies that for such queries, compaction offers no advantage over storing the data uncompressed, as the information theoretic lower bound is too high to compress effectively without losing correctness.
Empirical Validation: The case study demonstrates that current production systems (specifically the evaluated context compaction endpoint) perform significantly worse than theoretical optima (Bloom filters) on set membership tasks, suggesting that current LLM-based summarization strategies are not yet optimized for information retention.

Significance and Claims

The paper claims to initiate the formal study of context compaction, moving the field from empirical heuristics to information-theoretic guarantees.

Design Guidance: The equivalence to communication complexity provides agent designers with a method to calculate the minimum budget required for a specific set of future queries. If a problem has high one-way communication complexity (like set disjointness), the paper argues that context compaction cannot effectively reduce the budget without incurring high error.
Strategy Selection: The identified gap between selection and generation suggests that for certain tasks, agents should prioritize generation-based compaction (summarization) over selection-based compaction (truncation/pruning) to achieve better accuracy within the same token budget.
Limitations of Current Systems: The case study highlights a significant performance gap between deployed LLM-based compaction and optimal data structures, suggesting that current implementations discard critical information.

The authors remain modest regarding the scope of their findings, noting that their bounds are information-theoretic and do not address the computational feasibility of achieving these bounds (e.g., whether an LLM can actually compute the optimal condenser). They also identify repeated context compaction (where an agent compacts a state that is already a summary) and adaptive adversaries (where the query depends on the summary) as open problems for future research.