Context Compaction Theory
Hayder Tirmazi, Sam Markelon, Allison Bishop, Michael Mitzenmacher
cs.DS, cs.AI
2026-08-02
Generation budget equals one-way communication complexity; selection can need Θ(log n) more bits. Opus 4.8 on 15k URLs hits 0.50–0.56 error vs ~1/3 for a same-size Bloom filter.
Every LLM call from an agent has to fit the agent's internal state into a bounded context window. That state mixes user messages, model replies, and tool output such as file reads and shell logs. When it no longer fits, the agent runs context compaction: it writes a shorter input and then continues from that compressed state.
Every major coding agent does this. Codex, Claude Code, Gemini CLI, and OpenCode all fire compaction once usage crosses a threshold, often around 95% of the window. Almost none of it has a formal account of what information survives. Empirical papers report downstream task accuracy and stop there.
Deployed agents also commit to the compacted state. They keep the raw transcript on disk, but they do not re-summarize the full history on every later call. The paper prices that alternative: an 800,000-token history summarized into 100,000 tokens on Claude Fable 5 costs $8 of input plus $5 of output, $13 for one query, and about 26 minutes of generation at 65 output tokens per second. Once compaction runs, discarded information is gone for the rest of the session.
Compaction is a two-player game. One player is the compaction algorithm. The other stands in for whatever the agent will need later. The state is a set of discrete items (an error message, a design decision, a tool result) rather than a token sequence.
Two games cover the two strategies used in production.
Queries come in two regimes. Under a stochastic regime, the state and the query are drawn together from a known distribution and the figure of merit is expected error. Under an oblivious adversary, the opponent fixes the state and then the query without seeing the compacted message; the figure of merit is worst-case error. An adaptive adversary that reads the compacted message before choosing the query is out of scope.
The main theorem: at target error ε, the minimum GEN budget equals the one-way randomized communication complexity of the induced problem. The condenser is Alice. The later LLM call that reads the compacted context is Bob. Existing communication-complexity bounds transfer as-is.
SELECT is a restricted one-way protocol: the message may only name a subset, and the interpreter may only look at that subset. Theorem 3 separates the two. Take n items of size log₂ n bits each, and ask for the exact subset X. GEN sends an n-bit indicator vector and is lossless. SELECT must retain every item, so the budget is at least n log₂ n. The gap is Θ(log n).
The equivalence is information-theoretic. A lower bound applies to every interpreter. An upper bound only says some GEN algorithm exists; it does not say an LLM summarizer can compute it.
The theory is the equivalence and the separation. The measurement is a production endpoint.
| Setting | Budget | Error |
| Opus 4.8 compaction, seed 42 | 14.3 Kbits | 0.505 (FP 0.04 / FN 0.97) |
| seed 43 | 13.6 Kbits | 0.535 (0.28 / 0.79) |
| seed 44 | 14.8 Kbits | 0.555 (0.48 / 0.63) |
| Bloom filter, same size | 14 Kbits | 1/3 |
| No compaction, full context | 7280 Kbits | 0.02 (0.00 / 0.04) |
The study writes 15,000 URLs sampled from a malicious-URL dataset into the conversation, about 500,000 tokens, which trips Anthropic's server-side compaction at a 50,000-token threshold. The prompt tells the endpoint that the compacted result will be used only for set membership. After compaction, 200 membership queries go out in isolation: 100 true members and 100 true non-members, across three seeds.
All three error rates sit on the random-guess line at 0.5. A Bloom filter with the same bit budget misses about a third of the queries. The information-theoretic lower bound is (1/2)·2^{-B/N}. A control that keeps all 15,000 URLs in context, with no compaction, drops Opus 4.8's error to 0.02. The failure is information lost in compaction, not an inability to answer membership questions.
The summaries say so in plain language. Tens of thousands of URLs will not fit losslessly, so the model describes the character of the set (phishing pages, Mozi botnet hosts, Quebec-themed sites) and guesses by resemblance.
A design corollary sits in the discussion. An agent that scans a repo and must later answer whether any recorded dependency appears on a CVE list is solving set disjointness. Answering that query correctly on every input takes Ω(N m) bits of compacted context, where N is the number of dependencies and m is the bit length of a package name, the same order as storing the list uncompressed. Swapping in a Bloom filter for approximate membership still costs Ω(N m) bits when the query set can be as large as the whole name universe.
Agent authors get a ruler. For a given family of future queries, the smallest compaction budget at a target error is the one-way communication complexity of that query family. On set membership, a Bloom filter is already optimal up to a constant (about 1.44 N log₂(1/ε) bits for false-positive rate ε) and is a fair baseline.
The taxonomy is useful on its own. Truncate-to-last-N is SELECT, and it is strictly weaker on the query in Theorem 3. LLM summarization is GEN and can, in principle, spend fewer bits. The appendix shows that knowing the workload is membership, and even using structured URLs, Anthropic's Opus 4.8 compaction endpoint still does not emit a sketch. It guesses.
For anyone shipping a long-running agent, the paper reads as a warning. A single compaction is the most favorable case for the agent. Later compactions only throw more information away, and production loops feed the previous summary forward. How error grows with repeated compaction is left open; there is no growth formula.
The authors list four gaps. The theorem does not cover adaptive adversaries. The SELECT/GEN gap is one Θ(log n) example; the general size of the gap is unknown. The model is a single compaction. The bounds are information-theoretic, so they do not guarantee that an LLM summarizer can approach the optimum, or that an LLM can decode a sketch sitting in context.
The experiment is narrow: one endpoint, one model (Opus 4.8), one workload (membership on malicious URLs), one prompt. The authors say this is not a claim that compaction is always worse than a Bloom filter. It is a demonstration of how to measure a deployed algorithm against the communication-complexity optimum. The prompt asked for whatever representation minimizes membership error. The model still wrote a prose sketch of the set's vibe and never emitted a bit array. That is a snapshot of current summarizers, not an upper bound on GEN.
Item granularity is a modeling choice. A whole message and a single token both count as SELECT, and moving the cut moves the SELECT/GEN boundary. Lossless compression is treated as a per-item black box. Joint encoding across items, which is exactly how GEN saves budget relative to SELECT, is left outside that box.