{"id":"09ee852e-87f8-4749-9095-bea25231607b","arxiv_id":"2608.01326","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Context generation compacts context with exactly the budget of one-way communication, and on some queries it beats selection by a Θ(log n) factor.","lead":"This paper introduces a formal framework for context compaction in AI agents, modeling it as two games and proving that the best possible compression budget equals the one-way communication complexity of the induced problem. It shows that summarizing a context can beat selecting a subset by a logarithmic factor, and uses the framework to measure a deployed Anthropic endpoint.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's equality is only established for public-coin randomized GEN; Definition 3 never specifies whether Cond and Int share randomness, and private-coin regimes break the equality.","rationale":"The reader's weakest assumption is also the most load-bearing point for the central claim. Theorem 1 is otherwise a carefully argued equivalence: the deterministic direction is immediate, the information-theoretic caveats are explicit in Section 4.3, and Theorem 3's separation proof checks out. The only place where the stated equality could fail under a different but plausible reading is the treatment of randomness: the proof introduces a single coin rho shared by Cond and Int, but the model section never defines randomized GEN. Since one-way communication complexity is known to differ between public- and private-coin models for Equality, this is not a purely cosmetic ambiguity; it changes the numerical claim. I therefore agree with the reader's conditional assessment. The concern does not invalidate the proofs; it requires the authors to state the shared-coin assumption explicitly before Theorem 1 and, if they intend to model independently randomized LLM components, to replace the equality with the appropriate private-coin bound or an explicit public-coin caveat. No other issue examined (computation vs information, adaptive adversaries, repeated compaction) is a hidden flaw, because the paper flags those limitations itself.","tokens_in":20053,"tokens_out":15488,"duration_ms":147131,"concrete_test":"Add to Definition 3 an explicit definition of randomized GEN: either (a) shared-coin, a distribution over pairs (Cond_rho, Int_rho), or (b) independent-coin, with separate random bits for Cond and Int. Then instantiate Theorem 1 on the Equality query with epsilon = 1/3. Under (a) the minimum budget is O(1); under (b) it is Omega(log n). If the paper intends (b) for LLM deployments, the theorem's unqualified statement is false; if it intends (a), the definition must appear before Theorem 1 so the equality is not ambiguous.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central equivalence (Theorem 1, Section 4.1) is correct for the version of 'randomized GEN algorithm' used in its proof: a distribution over deterministic pairs (Cond_rho, Int_rho) indexed by one random string rho, so Cond and Int share the same coins. But Definition 3 defines only deterministic condenser-interpreter pairs and never states this. A deployed compactor and a later LLM interpreter are separate stochastic processes; if their randomness is independent, the induced object is a private-coin one-way protocol. For such protocols the public-coin complexity can be strictly larger (e.g., Equality: O(1) public-coin vs Theta(log n) private-coin), so Theorem 1 would not hold as an exact equality. The paper does not flag this scoping restriction or define randomized GEN at the model level. This ambiguity is the weakest point of the central claim; it is fixable by an explicit definition, but without it the theorem's practical reading is under-specified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces two formal games for context compaction in LLM agents: the Context Selection Game and the Context Generation Game. The central result, Theorem 1, states that the minimum budget of a randomized generation algorithm needed to achieve error at most epsilon equals the one-way randomized communication complexity of the induced communication problem, in both the stochastic and oblivious query regimes. The paper then characterizes selection algorithms as subset-encoding one-way protocols (Corollary 2) and proves a Theta(log n) separation between selection and generation on a query that asks for the exact input subset (Theorem 3). It also uses the equivalence to discuss set disjointness lower bounds and presents a case study in which Anthropic's context compaction endpoint answers set membership queries near the random-guess error rate while a same-sized Bloom filter errs on about a third of queries; a no-compaction control attributes the error to compaction.","tokens_in":20226,"tokens_out":29336,"duration_ms":260873,"significance":"If the equivalence holds, it gives a clean dictionary that lets agent designers import one-way communication complexity lower bounds directly as context-budget lower bounds. The proof is short and mostly definitional, but the paper is honest about this; the value is in the framing and in the separation result. Theorem 3 is a genuine, easily checkable separation with a correct injection argument. The case study is a useful template for measuring deployed compaction endpoints against the optimal budget, and it is appropriately hedged: the authors state that the experiment is a snapshot of one endpoint and one workload. The theory has no fitted parameters and makes falsifiable predictions, such as the Bloom-filter comparison curves. The main weakness is an under-specified randomized model in Definition 3, discussed in the major comments.","major_comments":[{"comment":"Theorem 1 is stated for 'possibly randomized' GEN algorithms, but Definition 3 defines only deterministic condenser-interpreter pairs. The proof treats a randomized GEN algorithm as a distribution over pairs (Cond_rho, Int_rho) indexed by a single random string rho, so Cond and Int share the same coins; this is exactly the public-coin one-way communication model. If the condenser and interpreter instead draw independent randomness, the induced object is a private-coin one-way protocol, and the equality in Theorem 1 can fail in the oblivious regime: for Equality, the public-coin one-way randomized communication complexity is O(1) while the private-coin one-way randomized complexity is Theta(log n). Please add an explicit definition of randomized GEN in Section 3, state that Theorem 1 (in particular Property 2) is for the shared-coin model, and discuss the private-coin variant; the stochastic regime is less affected because averaging over the coins gives a deterministic protocol for the fixed distribution, but the model still needs to be specified.","section":"Section 4.1, Definition 3, proof of Theorem 1"}],"minor_comments":[{"comment":"The phrase 'Alice's message identifies a subset S subset of [N]' is ambiguous, because Bob does not receive the universe X and a message containing only indices would not allow Bob to compute a function of the items {x_i : i in S}; please state explicitly that the message encodes the retained items or enough information to reconstruct them, with cost governed by the sum of s(x_i) over the selected items.","section":"Section 4.2, Corollary 2"},{"comment":"OpenAI Assistants truncation and LangChain trim_messages preserve message order, while SELECT is defined as an unordered subset whose order cannot convey information; if the model treats order as part of item content, this should be stated, otherwise the classification of order-preserving truncation as SELECT is a modeling simplification that deserves a footnote.","section":"Section 3.3 and Table 1"},{"comment":"The calculation of the no-compaction control budget (7280 Kbits) is not explained; please state how this number is derived from the token count of the full context.","section":"Appendix A"},{"comment":"The three measured error rates (0.505, 0.535, 0.555) lie above the random-guess line, so the phrase 'Every run lands on the random guess line' is imprecise; 'near the random-guess line' would be more accurate.","section":"Appendix A, Figure 2"},{"comment":"The statement 'There is a set Y of n items and a single query q on Y' is slightly confusing because the item universe in each instance is an arbitrary subset X of Y; please clarify that Y is the universe of possible items from which the adversary's universe X is drawn.","section":"Theorem 3"},{"comment":"The set disjointness example computes the space required by a Bloom-filter-based membership scheme; please label this as an analysis of one natural approach rather than a general lower bound for approximate set disjointness protocols, since the surrounding text could be read as claiming the latter.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The only substantive concern is the missing definition of randomized GEN and the unstated public-coin assumption; the rest of the paper is sound. The case study is properly scoped. I would expect a revised version with the model definition and a discussion of private-coin complexity to be publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. Theorem 1 is correct but it is essentially a definitional observation: once you write the Context Generation Game down, the condenser-interpreter pair is exactly a one-way protocol. The genuinely new content is Theorem 3, the Theta(log n) separation between selection and generation, and the proof is sound. The paper also provides the first formal framework for context compaction, which is a real service to the agent-systems area.\n\nWhat it does well: the definitions are careful, the scope caveats are in the main text (Section 4.3), the Bloom filter calculations check out, and the case study is honestly labeled as a snapshot. The no-compaction control is the right control. No fitted parameters, no circularity, and the related work is not a wall of self-citations.\n\nSoft spots. The randomized GEN model is under-specified. Definition 3 defines only deterministic condenser/interpreter pairs. In the proof of Theorem 1, randomized GEN is introduced as a distribution over deterministic pairs sharing one random string rho. That is a public-coin model, and the paper never says that explicitly at the definition level. If a deployed compactor and an LLM interpreter draw independent randomness, the induced object is a private-coin one-way protocol, and private-coin one-way complexity can be strictly larger than public-coin (Equality is the standard example). This is not a fatal flaw: the generator controls both components, so public coin is a legitimate information-theoretic model. But the paper should define randomized GEN, state the shared-coin assumption, and note that the private-coin variant would give different numbers. Minor: the empirical appendix has three seeds and no error bars. That is acceptable for a snapshot, but the point estimate is noisy; the authors say as much, so I do not hold it against them.\n\nWho gets value: agent-system designers who want lower bounds on how much a compacted context must carry, and communication-complexity folks who want a fresh application. The paper is not deep, but it is correct and useful. Send it to a serious referee; it needs a tightening revision, not a rejection.","headline":"Clean, correct framing paper: context generation is one-way communication, with a sound selection-vs-generation separation; the randomized-GEN definition needs a public-coin fix, but this deserves refereeing.","tokens_in":20738,"tokens_out":5913,"would_cite":true,"duration_ms":56107,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Context compaction has exactly the information cost of one-way communication.","keywords":["context compaction","one-way communication complexity","LLM agents","context window","set membership","Bloom filter","selection versus generation","information-theoretic lower bounds"],"falsifier":"Run the equality-query game twice, once with the summarizer and interpreter sharing random coins and once with independent coins; if the independent-coins budget provably exceeds the shared-coins budget, the paper's public-coin identification fails, because equality has constant public-coin one-way complexity but logarithmic private-coin complexity.","tokens_in":19865,"feed_emoji":"⚖️","tokens_out":6457,"duration_ms":54824,"temperature":0.7,"pith_summary":"The paper aims to put context compaction, the lossy step an AI agent takes when its accumulated state exceeds an LLM's context window, on a formal footing. It proves that for any set of possible future queries, the smallest context that can still answer the queries within a target error is exactly the one-way randomized communication complexity of the query problem: the condenser that summarizes the state plays Alice, the LLM that reads the summary and the query plays Bob, and the summary is the message. This equivalence transfers decades of communication-complexity results into agent design and yields a yardstick for measuring deployed compaction algorithms. The paper also separates two classes of compaction: selecting a subset of the original state is equivalent to a restricted subset-encoding protocol, and there are queries where generation needs a factor of $\\Theta(\\log n)$ less budget than selection.","feed_headline":"Context compaction budget equals one-way communication complexity","feed_subtitle":"The theorem gives exact lower bounds on how much an AI agent's summary must carry to answer future queries.","key_machinery":"The key object is the induced communication problem $\\Pi_G$: Alice receives the item universe $X$, Bob receives the query $q$, Alice sends one message of at most $B$ bits, Bob outputs an answer, and the error is $1 - v_q(\\hat{a})$. The equivalence is carried by identifying the condenser $\\mathrm{Cond}$, which maps $X$ to a bounded summary, with Alice's encoding, and the interpreter $\\mathrm{Int}$, which maps $(\\text{summary}, q)$ to an answer, with Bob's decoding. A randomized GEN algorithm is a distribution over pairs $(\\mathrm{Cond}_\\rho, \\mathrm{Int}_\\rho)$, which is exactly a public-coin randomized one-way protocol. Corollary 2 specializes the same identification to SELECT, and Theorem 3 uses a bijection argument on the power set to force a $\\Theta(\\log n)$ separation between selection and generation.","core_discovery":"The central claim is Theorem 1: for any Context Generation Game $G$ and its induced one-way communication problem $\\Pi_G$, the minimum budget at which a randomized GEN algorithm achieves expected error $\\le \\epsilon$ equals $R^{\\to}_{\\mu,\\epsilon}(\\Pi_G)$ in the stochastic regime and $R^{\\to}_{\\epsilon}(\\Pi_G)$ in the oblivious regime. The correspondence is exact because a generation algorithm is literally a condenser--interpreter pair, which is the same pair of functions as Alice's encoding and Bob's decoding in a one-way public-coin protocol. Consequently every one-way lower bound is a context-compaction lower bound, and every one-way protocol is a context-compaction scheme. The paper further proves that selection algorithms correspond to protocols whose messages identify a subset, and exhibits a set of $n$ items and one query where selection needs $n \\log_2 n$ bits but generation needs only $n$ bits.","pith_inferences":["Because the theorem's proof identifies GEN randomness with public coins, agents whose summarizer and interpreter LLM draw independent randomness face the private-coin one-way complexity, which can be strictly larger; equality queries are the standard example.","The equivalence is information-theoretic, so achieving an optimal budget may require the interpreter to decode a sketch-like representation; whether an LLM can reliably do that decoding is an open question, and practical gaps may persist even where lower bounds match.","Repeated compaction should compound losses: since each invocation runs on the output of an earlier one, the single-shot bound is the most favorable case, and a multi-shot model would likely require error that grows with the number of compactions.","An adaptive adversary who sees the summary before choosing the query falls outside Theorem 1; a two-round or adaptive communication model would be the natural replacement, and measuring the gap between oblivious and adaptive compactors could guide real deployments."],"forward_implications":["Known one-way communication lower bounds become unconditional context-compaction lower bounds; for example, set disjointness forces $\\Omega(Nm)$ bits for dependency-list queries, no better than storing the dependencies.","Approximate answers do not escape the lower bound: a Bloom-filter strategy for set disjointness still needs $\\Omega(N \\log(|T|/\\delta))$ bits, which becomes $\\Omega(Nm)$ when the query may name any package in the universe.","The minimum budget for generation is computable from communication complexity, giving agent designers a precise target before choosing a compaction method.","Selection and generation are separated: for the query in Theorem 3, selection needs $n \\log_2 n$ bits while generation needs only $n$ bits, so summary-based compaction can outperform subset-based compaction by a logarithmic factor.","The equivalence provides a measurement tool: any deployed summarizer's error can be compared against the optimal budget for the same workload, as demonstrated on set membership queries."],"supporting_citations":[{"why":"Defines one-way randomized communication complexity and the equality problem, the model that Theorem 1 identifies with the Context Generation Game.","marker":"[26]"},{"why":"Supplies the set-disjointness lower bound that the paper imports to show dependency queries need $\\Omega(Nm)$ bits of compacted context.","marker":"[37]"},{"why":"Gives the exact and approximate membership tester lower bound used for the optimal set-membership budget and the Bloom-filter comparison.","marker":"[14]"},{"why":"Extends the approximate-membership lower bound to the case where the set size is not known in advance, cited alongside [14].","marker":"[35]"},{"why":"Introduces the Bloom filter, the near-optimal membership structure used as the baseline in the set-disjointness and case-study comparisons.","marker":"[12]"},{"why":"Supplies the factor-of-$\\log_2 e$ overhead of Bloom filters over the information-theoretic lower bound.","marker":"[13]"}],"fun_headline_variants":["Context budget equals one-way communication complexity","AI context limits = communication complexity","Why context compaction is a communication problem","Selection vs generation: the exact budget gap"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The equivalence assumes that the summarizer and the interpreter share the same random source; if they draw independent randomness instead, the required context size can be larger, and the paper does not flag this distinction.","fun_headline_variants_meta":{"raw":{"variants":["Context budget equals one-way communication complexity","AI context limits = communication complexity","Why context compaction is a communication problem","Selection vs generation: the exact budget gap"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000391,"raw_usage":{"total_tokens":2089,"prompt_tokens":1010,"completion_tokens":1079,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":1028}},"tokens_in":626,"tokens_out":1079,"duration_ms":8067,"temperature":1.0,"reasoning_tokens":1028,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:09:20.389577+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the equality-query game twice, once with the summarizer and interpreter sharing random coins and once with independent coins; if the independent-coins budget provably exceeds the shared-coins budget, the paper's public-coin identification fails, because equality has constant public-coin one-way complexity but logarithmic private-coin complexity.","supporting_citations":[{"cited_title":"Communication complexity (for algorithm designers).Foundations and Trends in Theoretical Computer Science, 11(3-4):217–404, 2016","cited_arxiv_id":null,"evidence_quote":"Supplies the set-disjointness lower bound that the paper imports to show dependency queries need $\\Omega(Nm)$ bits of compacted context."},{"cited_title":"Exact and approximate membership testers","cited_arxiv_id":null,"evidence_quote":"Gives the exact and approximate membership tester lower bound used for the optimal set-membership budget and the Bloom-filter comparison."},{"cited_title":"How to approximate a set without knowing its size in advance","cited_arxiv_id":null,"evidence_quote":"Extends the approximate-membership lower bound to the case where the set size is not known in advance, cited alongside [14]."},{"cited_title":"Network applications of Bloom filters: A survey","cited_arxiv_id":null,"evidence_quote":"Supplies the factor-of-$\\log_2 e$ overhead of Bloom filters over the information-theoretic lower bound."}],"review_version":2}