{"id":"29c139f8-6c74-48c4-9ba3-84364adc6e18","arxiv_id":"2602.02909","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under the BAPO abstraction of LLMs, majority, triplet matching, and graph reachability each require Ω(n) chain-of-thought tokens, with matching upper bounds in a self-consistent variant.","lead":"The paper proves that, in a communication-limited model of LLMs, three simple tasks—majority, triplet-sum matching, and graph reachability—each need chain-of-thought tokens that grow at least linearly with input size. It also reports that frontier reasoning models use roughly linear reasoning tokens on these tasks, matching the bound.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"BAPO's hard-attention abstraction is contradicted by softmax attention's ability to compute MAJORITY in one step","rationale":"The reader's weakest assumption is exactly the BAPO constant-bandwidth abstraction's faithfulness. I agree: the central claim that these lower bounds are 'fundamental bottlenecks' for LLM inference-time compute depends on the BAPO model being an accurate model of a single transformer token-generation step. The BAPO attention model is a hard-selection mechanism (top-b tokens), while real softmax attention computes a weighted combination of all prefix tokens. MAJORITY is a canonical example where softmax attention trivially computes the required aggregate statistic in one step, so the Ω(n) lower bound for constant-bandwidth BAPO-CoT does not transfer. The paper's own experiments show LLMs do not use this shortcut, but that is an empirical property of specific models, not an architectural impossibility. The theoretical results are valid within the BAPO model, but the 'fundamental bottleneck' framing is overreach unless the abstraction is validated. The reader already conditions acceptance on stronger evidence for the abstraction, so the verdict stays CONDITIONAL (UNCHANGED).","tokens_in":30791,"tokens_out":9218,"duration_ms":98260,"concrete_test":"Hand-construct or train a one-layer, one-head transformer with embedding dimension 2 (keys/query = 0, values = [bit;1], linear readout) and evaluate on all binary strings up to length 101; if it attains 100% accuracy in a single forward pass with no CoT, it falsifies the transfer of Theorem 4.1 to actual transformers and demonstrates the BAPO abstraction is not faithful.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorems 4.1–4.3 are proved for the BAPO model, whose attention function (Definition 2.1) returns a set of at most b attended tokens; the suffix oracle h sees only those token symbols and indices. This hard-selection model omits the defining property of softmax attention: the output is a weighted sum over all prefix tokens. Consequently, the model does not capture the information that can cross a prefix/suffix cut in one transformer step. Concrete failure: for MAJORITY, a single attention head with uniform weights over the prefix yields the average bit value in one vector; a linear readout then decides majority. This is a one-step, no-CoT solution with O(1) layers, heads, and embedding dimension. Thus Theorem 4.1's Ω(n) lower bound does not apply to standard transformers, and the paper's conclusion that these are 'fundamental bottlenecks' for LLM reasoning is unsupported. The transfer relies on the undocumented assumption that attention is equivalent to selecting O(1) tokens, which is false for softmax attention.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper extends the bounded attention prefix oracle (BAPO) model, introduced in prior work, to multi-step chain-of-thought (CoT) generation and defines a formal notion of BAPO token complexity. Its main theoretical results are lower bounds of Ω(n) on the number of CoT tokens required by any constant-bandwidth BAPO-CoT for three problems: binary MAJORITY, MATCH3_n, and graph REACHABILITY (Theorems 4.1–4.3). The paper complements these with explicit cBAPO-CoT upper bounds (O(n log n) for MAJORITY, O(n) for MATCH3_n, O(n^2) for REACHABILITY), a general Turing-machine-simulation upper bound, and experiments with GPT-5.2 and Gemini 2.5 Pro showing roughly linear reasoning-token usage and accuracy loss under tight reasoning budgets. A new self-consistent restriction, cBAPO, is introduced to close the input-doubling loophole that otherwise lets any problem be solved in n+1 tokens.","tokens_in":31097,"tokens_out":16948,"duration_ms":187975,"significance":"If one accepts BAPO as a faithful abstraction of per-token information flow in transformers, the paper contributes a clean and non-trivial extension of prior BAPO-hardness results: it shows not only that certain problems require CoT, but that they require linearly many CoT tokens even under constant bandwidth. The lower-bound constructions are detailed, self-contained, and appear internally sound; the upper bounds are explicit algorithms, and the proofs are presented with care. However, the broader significance for real LLMs is conditional on the hard-attention abstraction in Definitions 2.1–2.2. That abstraction is in direct tension with standard softmax attention, which can compute aggregate statistics such as MAJORITY in one step by averaging over all prefix tokens. The paper does not address this tension, and its abstract and discussion claim 'fundamental bottlenecks' for LLM reasoning. The theoretical results are valuable within the BAPO model, but the transfer to actual transformer-based LLMs is a load-bearing assumption that is neither proved nor adequately discussed.","major_comments":[{"comment":"The lower bounds are theorems about BAPO, whose attention function returns a set of at most b attended token symbols and indices; the suffix oracle never receives a weighted combination of prefix tokens. Standard softmax attention is not of this form: a single attention head with uniform weights over the prefix produces the average bit value, and a linear readout decides MAJORITY in one step. Thus Theorem 4.1 does not apply to a vanilla transformer with softmax attention, and the paper's claim that these are 'fundamental bottlenecks' for LLM reasoning is unsupported. The paper should either justify why a hard-selection bandwidth captures the relevant information bottleneck (including aggregate statistics), or explicitly restrict all abstract/conclusion-level claims to the BAPO model. This is not an internal inconsistency in the proofs, but it is the load-bearing premise for the paper's s","section":"Definitions 2.1–2.2; Theorems 4.1–4.3; Section 8"},{"comment":"The experiments are presented as being 'consistent with our theoretical lower bounds,' but linear token usage by GPT-5.2 cannot distinguish the claim 'fewer tokens are information-theoretically impossible' from the claim 'the model happens to use a linear algorithm.' Accuracy degradation under word limits is observational and could be caused by instruction-following, model biases, or training choices, not by a communication bottleneck. Given the BAPO-to-transformer transfer problem in Definitions 2.1–2.2, the empirical section cannot carry the burden of validating the lower bounds for actual LLMs. At minimum, the authors should weaken the interpretation and, ideally, test a softmax-attention model on MAJORITY to see whether the predicted linear bottleneck actually appears.","section":"Section 6, Figures 2–3"},{"comment":"The statement that constant-bandwidth BAPOs 'cannot in general be simulated by Turing machines' is true but essentially trivial: with an unbounded token alphabet Σ=N and an arbitrary suffix oracle h, a (0,0)-BAPO can decide an undecidable language by looking at the final token. The surrounding prose ('It was previously unknown whether constant-bandwidth BAPOs could be simulated by Turing machines at all. We resolve this question in the negative') overstates the conceptual content. The result depends on non-computable h and unbounded alphabets, which are not features of real transformers. Please rephrase so readers understand this is an artifact of the model's freedom, not a new barrier.","section":"Section 4.2, Proposition 4.4"}],"minor_comments":[{"comment":"Typo in the opening sentence: 'defintion' should be 'definition.'","section":"Appendix B"},{"comment":"The sentence 'cBAPO and BAPO models share the same lower bounds' is correct but initially confusing because the BAPO row in Table 1 shows n+1 upper bounds for all problems via the input-doubling loophole. Clarify that the lower bounds apply to both, while the upper bounds differ because the loophole is excluded in cBAPO.","section":"Section 3.1 / Table 1"},{"comment":"The figures report means but no variance, error bars, or number of seeds. Since token counts on frontier API models can be highly variable, please add at least a variance measure or state the number of independent runs.","section":"Section 6 / Figures 2–4"},{"comment":"The theorem states the construction uses Θ(n log n) CoT tokens and concludes an O(n log n) upper bound; the relationship to the Ω(n) lower bound is clear, but the paragraph after the theorem says 'this leaves a small gap'—consider stating explicitly that the gap is between Ω(n) and O(n log n), and that it is conjectured to be an artifact of a binary CoT alphabet.","section":"Theorem 5.6"}],"recommendation":"major_revision","confidential_remarks":"The core lower-bound proofs appear careful and the internal BAPO contribution is publishable in principle. My main concern is scope: the paper's framing promises conclusions about LLM reasoning, but the BAPO model's hard-attention assumption is contradicted by softmax attention on one of its own canonical examples (MAJORITY). This is fixable by a major revision that either justifies the abstraction or repositions the claims as model-relative, but it is load-bearing and should not be treated as a minor caveat. I would also encourage the editor to seek an independent check of the lower-bound proofs, since the BAPO hardness classification and proof templates come from the same authors' prior work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. This is a real extension of the authors' prior BAPO work: they define a token-complexity measure for chain-of-thought, introduce the cBAPO restriction to close an input-doubling loophole, and prove linear lower bounds on CoT length for MAJORITY, MATCH3, and REACHABILITY, with matching or near-matching upper bounds. The lower-bound proofs are intricate adversarial constructions, and I didn't find a gap in them. The upper-bound constructions are also explicit and checkable.\n\nThe second thing: the paper overclaims what the lower bounds say about real LLMs. The BAPO attention function selects up to b tokens; the suffix oracle sees only those tokens, not any aggregate. Softmax attention, by contrast, returns a weighted sum over all prefix tokens. That difference is not cosmetic. For MAJORITY, a single attention head with uniform weights gives the average of the prefix in one vector, and a linear readout decides. That is a one-step solution with constant bandwidth in the sense that matters for transformers, so Theorem 4.1's Ω(n) bound doesn't transfer to standard transformers. The paper's 'fundamental bottlenecks in inference-time compute' framing is therefore not supported unless you accept the hard-attention abstraction as a literal model of LLMs. The abstraction is defensible as a communication-complexity model, but the paper doesn't confront the softmax counterexample at all.\n\nThe experiments are secondary: they show rough linear token scaling for GPT-5.2 and heavy token use for Gemini, but the results are noisy, limited, and the MAJORITY refusal behavior is a side issue. They don't validate the lower bounds; they say 'consistent with' at most.\n\nWho benefits? Researchers working on reasoning compression or CoT theory will want to engage with the BAPO-CoT formalism and the cBAPO construction. The paper deserves a serious referee, but the referee should ask the authors to (i) state clearly what the BAPO attention model captures, (ii) discuss the softmax-aggregation gap, and (iii) soften the claims about real LLMs unless they can justify hard attention as a faithful abstraction. If those fixes are made, the formal results stand as a useful contribution to a specific model class.","headline":"Solid formal results within the BAPO model, but the hard-attention abstraction doesn't support the 'fundamental bottlenecks' claim for real transformers.","tokens_in":31547,"tokens_out":4530,"would_cite":true,"duration_ms":52693,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that binary majority, triplet matching, and graph reachability each require Ω(n) chain-of-thought tokens in a constant-bandwidth model of transformer token generation, with matching upper bounds and empirical scaling consis","keywords":["chain-of-thought","BAPO","token complexity","lower bounds","binary majority","triplet matching","graph reachability","reasoning compression"],"falsifier":"Exhibit a constant-bandwidth BAPO-CoT that solves any one of the three tasks on all length-n inputs with o(n) tokens—such an object would break the masking/pigeonhole argument. Alternatively, demonstrate in a real model a single token-generation step that reliably transmits ω(1) bits about a prefix of length n across a cut (for instance, an attention pattern whose output encodes the number of ones in the prefix), which would falsify the modeling assumption rather than the theorem.","tokens_in":30728,"feed_emoji":"🧠","tokens_out":6500,"duration_ms":60310,"temperature":0.7,"pith_summary":"The paper asks how many reasoning tokens an LLM fundamentally needs as input size grows, and answers it in a formal model. For three tasks known to resist single-step transformers—binary majority, triplet matching, and graph reachability—any chain-of-thought that respects constant per-step communication must produce at least a linear number of tokens. The lower bounds are proved by extending a communication-based abstraction of transformer steps, and they are matched or nearly matched by explicit constructions. The paper also exposes an input-doubling loophole in the original model and introduces a self-consistent variant that closes it. Experiments on frontier reasoning models show token counts scaling roughly linearly on these tasks and accuracy collapsing when reasoning budgets are capped, exactly the pattern the theory predicts.","feed_headline":"Three LLM tasks need at least linear reasoning tokens","feed_subtitle":"Proof in the BAPO model; frontier models' token use grows at the same rate.","key_machinery":"The central object is the BAPO-CoT step: each autoregressive token is produced by a BAPO in which a prefix oracle f summarizes everything before a split into a bits, an attention function g selects at most b attended tokens, and a suffix oracle h combines both with the suffix. With a and b constant, only O(1) bits of global information can cross any cut per token, so the reasoning chain is the only channel for accumulating global information. The lower-bound technique plants masking tokens to force the same attended set on different inputs, uses pigeonhole over the finite set of prefix summaries to force an f-collision, and arranges suffixes so the two indistinguishable instances demand oppo","core_discovery":"Under the bounded attention prefix oracle (BAPO) abstraction—where each generated token can carry only O(1) bits of prefix summary and attend to only O(1) tokens across any prefix/suffix split—the paper proves three impossibility results: MAJORITY on n bits has token complexity Ω(n), MATCH3_n over Z_{n^2} has token complexity Ω(n), and REACHABILITY on m-edge graphs has token complexity Ω(m). These mean no constant-bandwidth BAPO-CoT can solve all instances of these problems with sublinear reasoning tokens. Upper bounds complement the results: an O(n log n) cBAPO-CoT for MAJORITY, an O(n) cBAPO-CoT for MATCH3_n, an O(n^2) cBAPO-CoT for REACHABILITY, and a general Turing-machine-simulation bou","pith_inferences":["If BAPO's constant-bandwidth assumption accurately captures real transformer generation, the proof recipe suggests a general strategy for showing that other high-communication problems—connectivity, median, set intersection, or counting problems—also demand linear or worse token complexity; this is testable by applying the same masking-plus-collision construction.","The input-doubling loophole shows the original BAPO model is too permissive; the self-consistent cBAPO restriction is a modeling fix. An editorial extension: architectural changes that add external memory, retrieval, or tool calls violate the per-step constant-bandwidth assumption, so those are the natural places to look for breaking the linear barrier.","The experiments suggest models may already be performing BAPO-like decompositions internally. A testable extension is to measure whether explicit step-by-step prompting changes only the constant factor in token scaling, not the linear slope, and whether models can ever be trained to solve these tasks with sublinear chains.","The lower bounds are worst-case; an open and useful refinement would be average-case or instance-dependent token complexity, distinguishing easy instances (short paths, early matches) from hard ones."],"forward_implications":["For MAJORITY, MATCH3_n, and REACHABILITY, any input-size-agnostic reasoning budget will eventually fail: a fixed cap on CoT tokens cannot solve large instances.","Because inference cost grows superlinearly in token count, these linear lower bounds translate into at least quadratic compute and latency scaling in input length for these tasks under the model.","Chain compression or brevity prompting can hope only for constant-factor savings on these problems; asymptotic linear reasoning is information-theoretically necessary.","The upper bounds show the lower bounds are tight or near-tight: MATCH3_n needs Θ(n) tokens, dense-graph REACHABILITY needs Θ(n^2), and MAJORITY sits between Ω(n) and O(n log n).","Empirically, frontier models exhibit approximately linear native reasoning token scaling on these tasks, and accuracy degrades sharply when the reasoning budget is too small—consistent with the proved lower bounds."],"fun_headline_variants":["LLM reasoning tokens: three tasks proven linear","Proof: majority, matching, reachability need Ω(n) CoT tokens","Three tasks force linear CoT tokens—BAPO proof","BAPO model: three problems need at least linear CoT tokens","Linear reasoning tokens proven necessary for 3 LLM tasks"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that a single transformer token-generation step can be modeled as a BAPO with constant prefix bandwidth and constant attention bandwidth; if real attention can communicate more than O(1) bits across an arbitrary prefix/suffix split, the linear lower bounds need not transfer to actual LLMs.","fun_headline_variants_meta":{"raw":{"variants":["LLM reasoning tokens: three tasks proven linear","Proof: majority, matching, reachability need Ω(n) CoT tokens","Three tasks force linear CoT tokens—BAPO proof","BAPO model: three problems need at least linear CoT tokens","Linear reasoning tokens proven necessary for 3 LLM tasks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000747,"raw_usage":{"total_tokens":3174,"prompt_tokens":758,"completion_tokens":2416,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":502,"completion_tokens_details":{"reasoning_tokens":2339}},"tokens_in":502,"tokens_out":2416,"duration_ms":16834,"temperature":1.0,"reasoning_tokens":2339,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T05:11:44.753463+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a constant-bandwidth BAPO-CoT that solves any one of the three tasks on all length-n inputs with o(n) tokens—such an object would break the masking/pigeonhole argument. Alternatively, demonstrate in a real model a single token-generation step that reliably transmits ω(1) bits about a prefix of length n across a cut (for instance, an attention pattern whose output encodes the number of ones in the prefix), which would falsify the modeling assumption rather than the theorem.","supporting_citations":[],"review_version":1}