{"id":"d34afe29-8781-429b-93e6-f6e2d1c18d7d","arxiv_id":"2502.02393","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In the unique-hard-attention transformer model, chain-of-thought length must grow linearly with input size for parity, multiplication, median, and reachability.","lead":"This paper proves that transformers using unique hard attention need at least a linear number of chain-of-thought steps to solve parity, multiplication, median, and graph reachability. It provides a general lower-bound technique and shows the bounds are tight up to logarithmic factors.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central result rests on Lemma B.3's strengthened depth-reduction lemma, whose proof is omitted; if the strengthening fails, Theorem 3.3 and all four application theorems collapse, so a self-contained proof is required.","rationale":"The reader identified Lemma B.3 as the weakest assumption, and my reading agrees. The paper's central contribution is the generic CoT lower bound Theorem 3.3, and that theorem is proved by applying the depth-reduction lemma iteratively. If Lemma B.3 only preserves the final output rather than all intermediate activations, then the single restriction required by Lemma 3.4 is not guaranteed to exist. In that case the inductive construction in Theorem B.6, which fixes CoT tokens one by one by controlling attention heads, cannot be started, and the lower bounds for PARITY, MULTIPLICATION, MEDIAN, and REACHABILITY all lose their justification. I checked the subsequent attention-fixing induction in Theorem B.6 and did not find an independent gap there: if the leftmost tie-breaking rule is used, then choosing the leftmost position among those with maximal possible score and forcing that position to attain the maximum does force the head to attend to it, because any competing position with the same actual score would also have the same maximal possible score and would lie to the right. The remaining unexamined step is therefore exactly the strengthening asserted in Lemma B.3. The application-specific 'cannot be fixed' claims are also terse, especially for M_N in Appendix C.2.1, but they are secondary to the generic theorem and are more plausibly repairable with a detailed case analysis. The experiments, while supportive, use softmax attention rather than UHAT and thus do not test Lemma B.3. Because the omitted proof is likely to be repairable but is essential to every main theorem, the appropriate verdict is conditional on that proof being supplied, which matches the reader's CONDITIONAL verdict; hence no verdict change is warranted.","tokens_in":34958,"tokens_out":8744,"duration_ms":95465,"concrete_test":"Reconstruct the proof of Hahn (2020) Lemma 4 and write out the construction of T' explicitly, then verify formally that for every position i and every layer l in {1,...,L}, y_i^{(l)} computed by T equals y_i^{(l-1)} computed by T' on all inputs in the restricted subcube. The critical step is the first one, where old layer-1 activations become new layer-0 activations: the random-restriction argument must bound the dependence of all y_i^{(1)} simultaneously, not just the activation used to produce the final output y_N^{(L)}. A useful computational check is to implement a small UHAT transformer (e.g. 2 layers, 2 heads, binary alphabet, N=8), apply the depth-reduction algorithm from Hahn (2020), and test whether all intermediate activations, not just the output, are preserved on the restricted subcube.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The single most load-bearing point is Lemma B.3, the strengthened version of Hahn (2020) Lemma 4. The original lemma only guarantees that the final output y_N^{(L)} is preserved when one layer is removed; Lemma B.3 asserts that every intermediate activation y_i^{(l)} in the original transformer equals y_i^{(l-1)} in the reduced transformer on the restricted input set. The paper does not prove this. It says only that 'by the way T' is obtained in that proof, the stronger statement for all activations follows.' This matters because Lemma 3.4 is proved by iterating Lemma B.3 L times, and Theorem 3.3 is proved by applying Lemma 3.4 and then inductively fixing CoT tokens. If the strengthened simultaneous preservation of all activations is false, the single restriction needed to make every layer's activations depend on at most c input positions need not exist. Without Lemma 3.4, the inductive step in Theorem B.6 cannot start, and the generic o(N)-CoT lower bound, as well as the derived lower bounds for PARITY, middle-digit multiplication, MEDIAN, and DAG reachability (Theorems 4.2, 4.5, 4.8, 4.10), do not follow. The proof of Theorem B.6 also uses Lemma 3.4 directly to bound the dependence of key activations y_j^{(l-1)}; if that guarantee holds only for the final output, the step that fixes each CoT token by forcing an attention head to a unique position cannot be justified. This is a correctness risk, not merely a presentation issue, because the lemma is load-bearing for every main theorem. The application-specific 'cannot be fixed' claims, e.g. for M_N in Appendix C.2.1, are also compressed, but they are secondary: the generic bound is the foundation, and Lemma B.3 is its weakest point.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies lower bounds on the length of chain-of-thought (CoT) sequences required by unique-hard-attention transformers (UHAT). The main technical result is Theorem 3.3, a generic CoT lower bound: if a function f has a UHAT-expressible CoT of length o(n), then for any C < 1 there is a restriction leaving at least Cn input positions free on which f is constant. From this the authors derive Omega(n) lower bounds for PARITY (Theorem 4.2), for the middle digit of N-bit multiplication (Theorem 4.5), for the last bit of MEDIAN (Theorem 4.8), and an Omega(|E| log |V|) bound for reachability in a specific DAG family (Theorem 4.10), with matching upper bounds up to logarithmic factors. The paper also shows that dot-by-dot CoTs for PARITY must have superpolynomial length and provides experimental evidence on trained transformers and LLMs. The central proof relies on Lemma B.3, a stated strengthening of a random-restriction depth reduction lemma from Hahn (2020), whose proof is not reproduced in the manuscript.","tokens_in":35347,"tokens_out":3142,"duration_ms":33354,"significance":"If Theorem 3.3 and its applications are correct, the paper makes a substantial contribution: it gives the first systematic, unconditional lower bounds on CoT length for a range of algorithmic problems in the UHAT model, and the bounds are tight up to polylogarithmic factors. The matching upper bounds, including the O(N log N) multiplication scratchpad via the number-theoretic transform and the BFS-based reachability scratchpad, are valuable and non-obvious. The experiments complement the theory by showing that the proposed scratchpads are learnable and that models without scratchpads fail on these tasks. However, the central claim currently rests on an unproven strengthening of a prior lemma, and several application proofs assert rather than demonstrate the required restriction-robustness of the target functions. For these reasons, the paper cannot be accepted in its present form, but the issues appear fixable by supplying the missing proof details.","major_comments":[{"comment":"The strengthened depth reduction lemma is load-bearing for the entire paper, yet its proof is not given. The text asserts: 'by the way T' is obtained in that proof, the stronger statement for all activations follows.' This is not sufficient for a journal proof, especially because Lemma 3.4 is proved by iterating Lemma B.3 L times, and Theorem 3.3 relies on that iteration. If the strengthening fails, the single restriction needed to make every layer's activations depend on at most c input positions need not exist, and the generic CoT bound and all four application theorems collapse. The authors should include a complete, self-contained proof of Lemma B.3, or at least a detailed derivation of the strengthened statement from the construction in Hahn (2020), showing explicitly why simultaneous preservation of all intermediate activations holds.","section":"Appendix B.1, Lemma B.3"},{"comment":"The proof of the multiplication lower bound is a single sentence: 'Now if one fixes CN input bits, for C small, the result cannot be fixed.' This is precisely the kind of claim that needs proof: one must show that for every restriction with a constant fraction of free positions, the middle digit M_N is not constant on the remaining strings. The intuitive argument based on high-degree parity is complicated by carries, and the one-sentence argument does not rule out the possibility that a cleverly chosen restriction fixes the digit. A rigorous argument is required, likely by exhibiting a pair of inputs consistent with the restriction with different M_N, or by a Fourier-analytic sensitivity argument.","section":"Appendix C.2.1, Theorem 4.5"},{"comment":"The MEDIAN proof similarly asserts: 'fixing, say, 1/10 N digits cannot fix the median.' This is not evident and in fact depends delicately on the relationship between the number of bits B and N, as the paper itself acknowledges in the regime discussion. A proof must show that for every restriction with a constant fraction of free positions, the last bit of the median is not constant on the restricted subcube. The current proof does not provide this, so the application of Theorem 3.3 is not justified as written.","section":"Appendix C.3, Theorem 4.8"},{"comment":"In the reachability proof, the statement 'fixing a small constant fraction of edges, while staying within G, cannot fix the reachability' is asserted without proof. Since the graph family G is designed to encode PARITY, a careful argument is needed to show that any restriction fixing fewer than a constant fraction of edges leaves at least one pair of vertices whose reachability remains variable. The current proof is too brief to be checked, and this step is necessary to apply Theorem 3.3 to the reachability lower bound.","section":"Appendix C.4.1, Theorem 4.10"}],"minor_comments":[{"comment":"There is a typo: 'a a family' should be 'a family'.","section":"Definition 3.2"},{"comment":"The word 'precisioin' appears in the sentence 'not fixed-precisioin transformers'; it should be 'precision'.","section":"Section 4.2"},{"comment":"The word 'superceeding' should be 'superseding'.","section":"Appendix B.2"},{"comment":"The theorem states that there is a scratchpad of length O(N log N) for multiplication, but the construction in Appendix C.2.3 relies on an unbounded CoT alphabet and modular arithmetic encoded in the MLP; this is fine for the lower-bound model, but the text should clarify that the upper bound is in the same UHAT model with unbounded alphabets and not in a fixed-precision setting.","section":"Theorem 4.6"},{"comment":"The caption says 'Left: CoTs consisting of prefix sum parities' but the figure appears to show two panels; the description of the right panel ('Dot-by-dot scratchpads help much less') would benefit from a clearer explanation of the axes and the dotted diagonal line.","section":"Figure 2"}],"recommendation":"major_revision","confidential_remarks":"The central issue is the unproven strengthening of Hahn (2020), Lemma B.3. Since one co-author is the author of the prior work, the authors are in a good position to supply the missing proof, but it must be included in the revision. I also recommend that the application proofs (Theorems 4.5, 4.8, 4.10) be expanded with formal arguments for the 'cannot be fixed by a constant fraction of bits' claims. These are not mere presentation issues; they are essential steps in applying the generic bound. The paper is otherwise well-written and the results are plausible, so I view major revision as appropriate rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The genuinely new thing is the generic random-restriction theorem (Thm 3.3): a sublinear UHAT CoT forces the function to be fixable by a constant-fraction restriction. That is a real tool, and the applications to PARITY, middle-bit multiplication, MEDIAN, and DAG reachability are natural and tight up to logs. The paper is honest about what is new and cites prior work cleanly.\n\nNow the soft spots. The load-bearing Lemma B.3 is a strengthening of Hahn's Lemma 4, asserted without proof. The text says 'by the way T' is obtained, the stronger statement follows.' That is not enough for a result whose every theorem depends on it. The stress-test note is right: if the simultaneous preservation of intermediate activations fails, Theorem 3.3 and all four applications collapse. I don't think the lemma is false—the proof sketch is plausible and Hahn's technique likely extends—but this is exactly the kind of step that needs to be written out or at least accompanied by a detailed appendix. As submitted, a referee cannot verify the main theorem from the paper alone.\n\nThe application-specific 'cannot be fixed' claims are also compressed. For multiplication, the proof is a single sentence plus a remark; for median and reachability similar. These are probably right, but they need the same care as the main proof. This is not a fatal flaw, but it moves the paper from 'ready to accept' to 'needs a serious revision.'\n\nWhat the paper does well beyond the main result: the upper-bound constructions matter, especially the O(N log N) NTT scratchpad for multiplication, and the experiments support the claim that these CoTs are learnable. The experiments use softmax, not UHAT, which the paper acknowledges; that's fine as sanity-check rather than evidence for the lower bound.\n\nVerdict: this deserves a serious referee. The central idea is good, the conclusions are likely correct, and the tightness is valuable. But the omitted proof of Lemma B.3 is a correctness risk, not a stylistic issue. I'd send it to review and ask for a self-contained proof of the depth-reduction lemma and fuller treatment of the 'cannot be fixed' steps before publication.","headline":"A genuinely new generic CoT lower bound for UHAT, but the load-bearing depth-reduction lemma is asserted without proof and needs to be written out before the results can be trusted.","tokens_in":35899,"tokens_out":1677,"would_cite":true,"duration_ms":17808,"reading_group":"yes","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 any chain-of-thought for PARITY, the middle digit of multiplication, MEDIAN, or DAG reachability in a hard-attention transformer must have at least linear length, with matching constructive upper bounds up to…","keywords":["chain-of-thought","unique hard attention","lower bounds","random restrictions","average sensitivity","PARITY","scratchpads","transformers"],"falsifier":"A counterexample would be a UHAT transformer family with constant layers and heads together with a chain-of-thought of length $o(|x|)$ that computes PARITY on all inputs under the paper's Definition 2.2; finding one would refute Theorem 4.2. More directly, build a two-layer UHAT transformer and a constant $C$ such that every restriction leaving at least $CN$ positions free leaves some intermediate activation at layer 2 dependent on more than a bounded number of input positions—that would disprove Lemma 3.4, the strengthened depth-reduction lemma on which the main theorem rests.","tokens_in":34715,"feed_emoji":"🧠","tokens_out":15083,"duration_ms":128422,"temperature":0.7,"pith_summary":"This paper proves that several basic algorithmic problems cannot be solved by hard-attention transformers with a short chain-of-thought: the number of intermediate reasoning tokens must grow at least linearly with the input size. The central theorem says that if a function has a sublinear-length chain-of-thought in the unique-hard-attention (UHAT) model, then fixing a constant fraction of the input positions already fixes the output; PARITY, the middle bit of multiplication, MEDIAN, and DAG reachability all stay unfixed under any such restriction, so they force linear (or larger) scratchpad length. The bounds are tight up to logarithmic factors, with explicit constructions: prefix parities, a Fourier-transform multiplication scratchpad of length $O(N \\log N)$, enumeration of the lower half for MEDIAN, and a breadth-first-search scratchpad for reachability. These results put a provable limit on the inference-time compute that can be saved by compressing or jumping over chain-of-thought steps in transformers.","feed_headline":"Provably no sublinear chain-of-thought for parity and three more tasks","feed_subtitle":"Hard-attention transformers provably need at least linear chain-of-thought length on all four tasks.","key_machinery":"The load-bearing object is the random restriction and its depth-reduction lemma (Lemma 3.4), a transformer analogue of the switching lemma for $\\mathrm{AC}^0$ circuits: for any constant $C$, one restriction can fix a constant fraction of input positions so that every intermediate activation $y_i^{(l)}$ in a bounded-layer UHAT transformer depends on at most $c$ input positions. This strengthens the earlier depth-reduction lemma, which only preserved the final output, and the proof iterates it $L$ times to get a single restriction valid for all layers. Theorem 3.3 then appends the chain-of-thought to the restriction: because each autoregressive step's activation depends on the previously fixed CoT tokens and only $O(1)$ input positions, fixing $O(|g|)$ extra input bits pins down the whole CoT. When $|g| = o(N)$, the restriction still leaves a constant fraction of the input free while the output is fixed, and that is exactly the structure that high-sensitivity functions forbid.","core_discovery":"On the paper's own terms, the central discovery is Theorem 3.3: if $f$ has a UHAT-expressible chain-of-thought $g(x)$ of length $|g(x)| = o(|x|)$, then for every $C \\in (0,1)$ there is a restriction $\\rho$ leaving at least $CN$ positions free such that $f$ is constant on the remaining strings. The proof obtains a random restriction that makes every intermediate activation depend on a bounded number of input positions (Lemma 3.4), then fixes $O(|g(x)|)$ further positions to pin down all chain-of-thought tokens one by one; if $|g(x)| = o(N)$, a constant fraction of the input stays free while the answer is already decided. Since PARITY, the middle digit $M_N$ of $N$-bit multiplication, MEDIAN, and DAG reachability cannot be made constant by fixing any constant fraction of positions, their chain-of-thought length must be $\\Omega(N)$ (and $\\Omega(|E|\\log|V|)$ for reachability). These lower bounds are tight up to logarithmic factors via explicit UHAT scratchpads, and a further theorem shows that 'dot-by-dot' pause-token scratchpads for PARITY require superpolynomial length $\\omega(|x|^k)$ for every $k$, while an exponential-length one exists.","pith_inferences":["An editorial extension of the restriction criterion: any Boolean function that cannot be made constant by fixing a constant fraction of its input bits automatically inherits a linear UHAT chain-of-thought lower bound, so the generic theorem is a reusable test for other high-sensitivity tasks such as counting modulo $m$ or evaluating a formula whose value depends on all variables.","The paper proves the UHAT lower bounds and notes that UHAT upper-bounds fixed-precision softmax transformers; I infer the practical lesson for LLMs is that attempts to distill or skip chain-of-thought steps on these tasks will hit an architectural floor, unless the model can use extra depth, tools, or a non-hard attention mechanism.","The dot-by-dot superpolynomial bound suggests a precise, testable difference between explicit and implicit reasoning: a pause-token-only model should fail to length-generalize on PARITY, whereas a model emitting explicit per-position parity tokens should succeed; the paper's LLM trace experiments are consistent with this, but the causal claim is an inference beyond its theorems."],"forward_implications":["PARITY requires a UHAT chain-of-thought of length $\\Omega(N)$, and the prefix-parity scratchpad attains $\\Theta(N)$, making the bound tight up to constants.","The middle output bit of $N$-bit binary multiplication requires UHAT chain-of-thought length $\\Omega(N)$, while a number-theoretic transform scratchpad computes the full product in $O(N\\log N)$ steps.","MEDIAN on $N$ numbers requires UHAT scratchpad length $\\Omega(N)$, attained by a chain-of-thought enumerating the lower $\\lfloor N/2\\rfloor$ sorted elements.","DAG reachability requires UHAT chain-of-thought length $\\Omega(|E|\\log|V|)$, attained by a breadth-first-search scratchpad, and this lower bound holds unconditionally without assuming $\\mathrm{TC}^0 \\neq \\mathrm{NC}^1$.","Dot-by-dot scratchpads—sequences of pause tokens followed by the answer—cannot solve PARITY in polynomial length: their length must be $\\omega(|x|^k)$ for every $k$, a superpolynomial separation from ordinary chain-of-thought."],"supporting_citations":[{"why":"Supplies the depth-reduction lemma for UHAT transformers that the paper strengthens to preserve all intermediate activations.","marker":"Hahn (2020)"},{"why":"Provides the classical switching lemma and random-restriction framework the proof adapts to transformers.","marker":"Hastad et al., 1994"},{"why":"Origin of random-restriction lower bounds for PARITY, the template for the paper's restriction argument.","marker":"Furst et al., 1984"},{"why":"Establishes the sensitivity-based account of why transformers struggle with high-sensitivity functions, motivating the four target problems.","marker":"Hahn & Rofin (2024)"},{"why":"Shows UHAT is contained in AC0, used to rule out polynomial dot-by-dot scratchpads for PARITY.","marker":"Hao et al. (2022)"},{"why":"Bounds the average sensitivity of AC0 circuits, used in the dot-by-dot impossibility proof.","marker":"Boppana (1997)"},{"why":"Characterizes regular languages outside AC0 via non-quasi-aperiodic syntactic monoids, used in the dichotomy corollary.","marker":"Barrington et al. (1992)"},{"why":"Shows UHAT expresses exactly the star-free (AC0) regular languages, completing the dichotomy.","marker":"Yang et al. (2024)"}],"fun_headline_variants":["Linear chain-of-thought mandatory for parity, median, and more","No sublinear chain-of-thought for parity, median, and more","Four tasks demand linear chain-of-thought in hard attention","Chain-of-thought must be linear for parity and three tasks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the strengthened depth-reduction lemma (Lemma B.3): a single random restriction can make every intermediate activation of a bounded-layer UHAT transformer depend on only a constant number of input positions, whereas the previously published version of the lemma only made this guarantee for the final output; the paper states the stronger claim follows from the earlier proof but does not reproduce that proof, so if the strengthening fails, the generic CoT bound and all four applications collapse.","fun_headline_variants_meta":{"raw":{"variants":["Linear chain-of-thought mandatory for parity, median, and more","No sublinear chain-of-thought for parity, median, and more","Four tasks demand linear chain-of-thought in hard attention","Chain-of-thought must be linear for parity and three tasks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000761,"raw_usage":{"total_tokens":3391,"prompt_tokens":971,"completion_tokens":2420,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":587,"completion_tokens_details":{"reasoning_tokens":2359}},"tokens_in":587,"tokens_out":2420,"duration_ms":16650,"temperature":1.0,"reasoning_tokens":2359,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T12:18:18.650294+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A counterexample would be a UHAT transformer family with constant layers and heads together with a chain-of-thought of length $o(|x|)$ that computes PARITY on all inputs under the paper's Definition 2.2; finding one would refute Theorem 4.2. More directly, build a two-layer UHAT transformer and a constant $C$ such that every restriction leaving at least $CN$ positions free leaves some intermediate activation at layer 2 dependent on more than a bounded number of input positions—that would disprove Lemma 3.4, the strengthened depth-reduction lemma on which the main theorem rests.","supporting_citations":[],"review_version":1}