{"id":"e1ba5323-068d-4104-a58f-c9e2bf60c2fa","arxiv_id":"2506.10647","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The authors derive a joint condition on distribution skew and poisoned reasoning labels that decides whether chain-of-thought training on k-parity succeeds, and they claim a paradox where maximal information leakage makes chain of thought worse than direct prediction.","lead":"Chain-of-thought training on the k-parity problem is shown to be fragile: a small fraction of poisoned intermediate steps can break learning, and a skewed input distribution that leaks the answer can make chain of thought fail entirely. The paper proves a necessary and sufficient condition for success under both kinds of data shift, though one direction of the proof has a gap.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Necessity proof of Theorem 4.2 rests on an invalid limit in Appendix B.5: Eq. (158) replaces the erroneous output xhat_m by the true x_m even though Eq. (156) just proved they differ by Omega(1).","rationale":"Agree with the reader's weakest-assumption identification. The necessity proof's propagation step is the load-bearing bridge from 'one CoT step is wrong' to 'final prediction is wrong'; without it, the iff claim is only a sufficiency result plus a partial necessity argument. The invalid limit in Eq. (158) is not a cosmetic typo because it appears in the only place where the paper argues that local failure propagates to the root. I am not claiming the theorem is false; the propagation lemma may be true, and a direct induction would likely repair it. But as written, the central characterization is unproven. I also note the paper's CoT-versus-direct comparison is overstated in the abstract: Theorem 4.1 applies only to rho<1, while Theorem 4.2 shows CoT failure mainly in high-leakage regimes; at rho=1 CoT is still better than direct learning under known hardness. This substantiates the reader's reject posture without moving the verdict further, so the verdict remains unchanged.","tokens_in":26862,"tokens_out":10652,"duration_ms":122855,"concrete_test":"Independently prove or disprove the propagation lemma used in B.5: for the failure mode xhat_m = -1/3 + o(1), with sibling output xhat_{m'} = x_{m'} + o(1) and x_m, x_{m'} independent uniform bits, compute directly E|x_m x_{m'} - xhat_m xhat_{m'}| instead of passing through Eq. (158). If this expectation is Omega(1), the lemma is true and the necessity proof can be repaired by rewriting B.5; if it can be made o(1) for an admissible failure configuration, the 'only if' direction collapses. A small symbolic or exhaustive check with d=8 and one corrupted intermediate node would also reveal whether the claimed propagation holds in the base cases.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is the iff characterization in Theorem 4.2. The sufficiency half is a gradient computation, but the necessity half needs a propagation lemma: a constant error at any intermediate CoT node must produce a constant error at the root. Appendix B.5 does not prove this. After a violated condition at node m, it shows (Eq. 156) that E|x_m - xhat_m| >= 1/3: with probability 1/2, x_m = -1 while xhat_m is approximately -1/3. Immediately afterward, Eqs. (157)-(160) propagate the parent error by writing E|x_m x_{m'} - xhat_m xhat_{m'}| = E|x_m x_{m'} - x_m xhat_{m'}|, i.e. replacing xhat_m by x_m 'in the limit d -> infinity'. But Eq. (156) just established that xhat_m does not converge to x_m; the step assumes exactly the non-vanishing-error propagation that is supposed to be proved. The extension to multiple failing nodes (Eq. 161) also applies Hoeffding to a sum of intermediate parity nodes whose supports overlap, so their independence is not automatic. Because Corollaries 4.3-4.4 and the claimed 1/(2(k-1)) poisoning tolerance inherit the necessity half, those conclusions are not established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the k-parity problem under a fixed CoT decomposition into binary parity steps, with two types of data shift: distribution shift controlled by a parameter rho and structured data poisoning of CoT labels. Theorem 4.1 states that the imbalanced parity problem can be solved by a one-layer transformer in one gradient step without CoT. Theorem 4.2 claims a necessary and sufficient condition for successful one-step training with the CoT decomposition, expressed as upper bounds on gradient gaps B_m between correct and incorrect attention targets; the sufficiency direction is a detailed gradient computation, while the necessity direction is argued by contrapositive and by an error-propagation argument. Corollaries state that rho = 0 always causes failure, that distribution shift always hurts, and that the poisoning tolerance is 1/(2(k-1)). Experiments on d = 128, k = 64 show qualitative agreement with the predicted degradation.","tokens_in":27115,"tokens_out":4831,"duration_ms":57968,"significance":"If Theorem 4.2 were correct, the paper would provide the first rigorous theoretical account of how distribution shifts and label poisoning jointly degrade CoT training on a concrete task, with a quantitatively checkable condition and a surprising 'distribution leak hurts' phenomenon. The sufficiency half is a nontrivial gradient computation and the experimental section adds supporting evidence. However, the central iff claim rests on the necessity half, and the necessity proof contains an invalid limiting step in the error-propagation argument. Since the corollaries and the claimed poisoning tolerance inherit the necessity half, the main contribution is not established as written.","major_comments":[{"comment":"The error-propagation step is invalid. Equation (156) establishes that, under the failure condition at node m, E|\\hat x_m - x_m| >= 1/3, with \\hat x_m approximately -1/3 on the event where x_m = -1. Equations (157)-(160) then pass to the limit and replace \\hat x_m by x_m, writing E|x_m x_{m'} - \\hat x_m \\hat x_{m'}| -> E|x_m x_{m'} - x_m \\hat x_{m'}|. But \\hat x_m does not converge to x_m along the very failure event just analyzed: the two differ by Omega(1). The step therefore assumes the conclusion that is supposed to be proved, namely that a non-vanishing error at an intermediate node propagates to the root. The 'only if' direction of Theorem 4.2 is not established unless a genuine propagation lemma for non-vanishing errors is proven.","section":"Appendix B.5, Eqs. (156)-(160)"},{"comment":"The extension to multiple failing nodes applies Hoeffding's inequality to the sum \\sum_{f in F} x_f/(f-1), where the x_f are intermediate CoT parity nodes. These variables are not independent in general because their defining subsets of input bits overlap through the decomposition tree; no argument is supplied to justify concentration under dependence. This is a further gap in the necessity argument, separate from the invalid replacement in Eqs. (157)-(160).","section":"Appendix B.5, Eq. (161)"}],"minor_comments":[{"comment":"The theorem says the transformer 'can solve the uniform parity problem', but the setting is the generalized problem with arbitrary rho in [0,1]; this should be corrected. Also, the set in Eq. (8) is written as {d+k/2+1, ..., m-1}, which is self-referential; the intended upper endpoint is d+k-1.","section":"Theorem 4.2 statement"},{"comment":"The proof asserts 'B_m = 0' when rho = 0, but only the first argument in the max in Eqs. (7)-(8) is visibly zero; the second argument is not shown to be zero. The conclusion that training fails does follow from B_m >= 0, but the stated equality is not established.","section":"Corollary 4.3 proof"},{"comment":"The title says 'without distribution shift', but the statement concerns the case rho = 1, i.e., identical training and testing distributions, which is precise; consider rewording to avoid ambiguity.","section":"Corollary 4.4 title"},{"comment":"The notation 'delta <= -2 - epsilon/4' followed by 'O(d^delta) + O(d^{-2-epsilon/4}) = O(d^{-2-epsilon/4})' is confusing; the exponent arithmetic should be stated explicitly.","section":"Appendix B.5, Eq. (153)"}],"recommendation":"reject","confidential_remarks":"The central 'only if' direction of the main theorem is not valid as written; the flaw is in the propagation lemma, which is load-bearing for the iff claim and for the corollaries. A revision would need to supply a correct propagation argument, not merely patch a local calculation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about arXiv:2506.10647. First, it is a genuine extension of Kim and Suzuki, not a recycled version: the joint condition on rho and q is new, the rho=0 failure corollary is a real observation, and the sufficiency half of Theorem 4.2 is a detailed, mostly careful gradient computation. Second, the necessity half has a load-bearing hole that the authors do not seem to notice.\n\nThe problem is in Appendix B.5. After showing in Eq. (156) that a failed condition gives E|x_m - xhat_m| >= 1/3, the proof immediately replaces xhat_m by x_m \"as d goes to infinity\" in Eq. (158). Those two statements are incompatible: if the node error is Omega(1), taking d large does not make the erroneous output converge to the ground truth. The propagation lemma is exactly what needs proving, and the proof assumes it. The extension to multiple failing nodes in Eq. (161) is also shaky, applying Hoeffding to a sum of intermediate parity nodes whose supports overlap. Corollaries 4.3 and 4.4 and the 1/(2(k-1)) poisoning tolerance all inherit the necessity half, so they are not established as written.\n\nSmaller issues: the abstract overstates the CoT-versus-direct comparison. Theorem 4.1 assumes rho = Theta(1), while the failure corollary is at rho = 0, so the \"surprising phenomenon\" is not a head-to-head comparison in a common regime. There are also typos in Theorem 4.2 (the second range should end at d+k-1, not m-1).\n\nWhat the paper does well: the gradient computations are thorough, the definitions of the poisoning sets are careful, and the authors are honest about the astronomical d needed for the theory to bind. No code is provided, and the experiments are at best suggestive, but that is not where the paper lives or dies.\n\nWho should read it: people working on provable CoT and on learning parity with transformers. It deserves a serious referee: the idea is good and the sufficiency half is likely fixable, but the necessity half needs a correct error-propagation argument. I would send it to peer review with a request for major revision focused on Appendix B.5.","headline":"A serious CoT theory paper with a real gap in the only-if direction: the sufficiency analysis is careful and the rho=0 observation is interesting, but the central iff theorem is not established as written.","tokens_in":27668,"tokens_out":5833,"would_cite":false,"duration_ms":64206,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"For the k-parity problem, a fixed chain-of-thought decomposition trains a transformer to vanishing error in one gradient step only when every intermediate node's gradient gap between correct and incorrect attention targets stays below an…","keywords":["chain-of-thought","k-parity","distribution shift","data poisoning","transformer","teacher forcing","softmax attention","gradient descent"],"falsifier":"Numerically simulate the $\\rho=0$ case for $d=128$, $k=64$: after one gradient step with the paper's loss, record the attention scores at each intermediate node and the final prediction error. The theorem predicts failure (average error bounded away from zero and attention spread across the failing node), so if the final error vanishes while an intermediate node has constant error, the propagation lemma is false. As an even sharper check, compute the parent's error under the exact constant $-1/3$ prediction at the failed node and see whether the error cancels.","tokens_in":26644,"feed_emoji":"🧪","tokens_out":6744,"duration_ms":76041,"temperature":0.7,"pith_summary":"This paper studies whether chain-of-thought (CoT) training still works when the training data are not clean and not identically distributed to the test data, using the k-parity problem as a testbed. It claims that for one particular, previously successful CoT decomposition of k-parity, a one-layer transformer trained with a single gradient step succeeds if and only if every intermediate reasoning node has a sufficiently negative gradient gap between correct and incorrect attention targets, and it writes that threshold as an explicit inequality in the distribution-shift parameter $\\rho$ and the poisoning counts $q$. The upshot is that the reasoning chain is fragile: poisoning just $0.5n$ of the $(k-1)n$ CoT labels at one node breaks training, and the more the input distribution leaks the locations of relevant bits (smaller $\\rho$), the worse training becomes, with $\\rho=0$ an outright failure. The authors also show that without CoT the imbalanced problem is easy, so under distribution shift CoT can be worse than predicting the answer directly.","feed_headline":"CoT training on k-parity breaks under data shifts","feed_subtitle":"One theorem ties distribution shift and poisoned reasoning steps to a gradient limit that decides success or failure.","key_machinery":"The fixed CoT decomposition is a complete binary tree of height $v=\\log_2 k$ over the $k$ relevant input bits, whose $k-1$ internal nodes each compute a 2-parity through the non-linearity $\\phi$ of Equation (1), which satisfies $\\phi((a+b)/2)=ab$; teacher forcing trains all internal nodes with the loss $L(W)=\\frac{1}{2n}\\sum_m\\|\\phi(\\hat{z}_m)-x_m\\|^2$. The argument is carried by explicit formulas for gradient updates: $G_{h[m]=1}$, $G_{h[m]>1}$, and $S(m,j)$ (Equations 4–6), assembled into $B_m=\\max\\{ -2\\rho(1-2q_m)/(m-1)^2,\\, G_{h[m]=1}(m,j,\\rho)+(1-\\rho)S(m,j)\\}$ or its height-one analog, which measures how much more strongly the correct children are updated than any incorrect node. Sufficiency follows when $B_m$ is below $-O(d^{\\mu})$, because softmax attention then concentrates on the two children of each node; necessity is meant to follow from a propagation lemma claiming that a non-vanishing error at any node forces a non-vanishing error at the root.","core_discovery":"In their main result (Theorem 4.2), the authors characterize one-step gradient training on the teacher-forced CoT tree for generalized k-parity. Let $B_m$ be the maximum, over incorrect attention targets $j$, of the two gradient differences between the correct children of node $m$ and $j$, one difference for nodes of height one and another for higher nodes. The theorem asserts that training succeeds with error converging to zero as $d\\to\\infty$ if and only if $B_m<-O(d^{\\mu})$ for every intermediate node $m$, with $\\mu>-2-\\epsilon/4$, and that if any inequality fails the expected final error is $\\Omega(1)$. Corollaries follow: with no distribution shift ($\\rho=1$) success is equivalent to $q_{m,c_1[m],c_2[m]}\\le 0.5-O(d^{\\mu})$ at every node; with maximum leakage ($\\rho=0$) training always fails; and the poisoning tolerance is only $1/(2(k-1))$.","pith_inferences":["The gradient-gap mechanism is not specific to parity: any teacher-forced decomposition whose internal steps are verified by a fixed non-linearity will likely show the same failure mode when attention cannot tell correct and incorrect parents apart; this could be tested on a Boolean function with a different tree shape and the same one-step update.","The $\\rho=0$ paradox is a property of this gradient-following algorithm, not of the statistical problem: a method that first identifies relevant positions (feature selection) should succeed where one-step softmax attention fails, and comparing such methods on $\\rho=0$ would isolate the mechanism.","The unproven propagation lemma is the fragile hinge: if error cancellation is possible in the tree (a failed node's wrong output could cancel in the parent's product), the only-if direction may fail in its current form, and a repaired proof would need a quantitative statement about how errors compound without assuming $\\hat{z}_m\\to x_m$."],"forward_implications":["A single poisoning attack needs only $0.5n$ flipped labels at one intermediate node to push $q_{m,c_1[m],c_2[m]}\\ge 0.5$ and violate the threshold, so the tolerance is $1/(2(k-1))$, shrinking to zero as $k$ grows.","Even without poisoning, any distribution shift with $\\rho<1$ slows convergence, and $\\rho=0$ (maximally exposed relevant bit locations) makes training fail outright, contradicting the intuition that leakage helps.","Under identical train and test distributions ($\\rho=1$), success is equivalent to $q_{m,c_1[m],c_2[m]}\\le 0.5-O(d^{\\mu})$ at every node, so the criterion becomes purely a bound on poisoned samples in each 2-parity step.","For $\\rho<1$ the same k-parity can be learned by a one-layer transformer without CoT, so under shifts CoT is not just unhelpful but strictly worse than direct prediction."],"supporting_citations":[{"why":"Supplies the chain-of-thought decomposition of k-parity into 2-parity steps that the paper analyzes and whose teacher-forced training loss is adopted.","marker":"[Kim and Suzuki, 2025]"},{"why":"Introduces the sub-task decomposition of k-parity and the teacher-forcing training protocol for reasoning steps.","marker":"[Wies et al., 2023]"},{"why":"Establishes that imbalanced parity with $\\rho<1$ is learnable by one-layer networks, the baseline the paper contrasts with CoT.","marker":"[Daniely and Malach, 2020]"},{"why":"Shows standard gradient-based learning fails on uniform parity, motivating the difficulty that CoT is supposed to overcome.","marker":"[Shalev-Shwartz et al., 2017]"},{"why":"Provides distribution-specific hardness results for learning parities that justify the uniform-case difficulty assumption.","marker":"[Shamir, 2018]"},{"why":"Defines chain-of-thought prompting, the method whose efficacy under data shifts is being examined.","marker":"[Wei et al., 2022]"}],"fun_headline_variants":["CoT fails on parity under data shifts, theory shows","Data shifts break CoT's advantage on k-parity","Gradient limit decides CoT success under shift","CoT worse than direct on shifted parity, rigorous"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole only-if direction rests on an unproven assumption that a non-vanishing error at any intermediate CoT node must propagate to a non-vanishing error at the final prediction; in the proof (Appendix B.5, around Equations 157–160) the failed node's output is replaced by the true value even though the failure condition makes it a constant $-1/3$ instead of $\\pm1$, so this propagation is not established.","fun_headline_variants_meta":{"raw":{"variants":["CoT fails on parity under data shifts, theory shows","Data shifts break CoT's advantage on k-parity","Gradient limit decides CoT success under shift","CoT worse than direct on shifted parity, rigorous"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000329,"raw_usage":{"total_tokens":1852,"prompt_tokens":978,"completion_tokens":874,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":594,"completion_tokens_details":{"reasoning_tokens":810}},"tokens_in":594,"tokens_out":874,"duration_ms":8584,"temperature":1.0,"reasoning_tokens":810,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:21:54.926374+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Numerically simulate the $\\rho=0$ case for $d=128$, $k=64$: after one gradient step with the paper's loss, record the attention scores at each intermediate node and the final prediction error. The theorem predicts failure (average error bounded away from zero and attention spread across the failing node), so if the final error vanishes while an intermediate node has constant error, the propagation lemma is false. As an even sharper check, compute the parent's error under the exact constant $-1/3$ prediction at the failed node and see whether the error cancels.","supporting_citations":[{"cited_title":"Sub-task decomposition enables learning in sequence to sequence tasks","cited_arxiv_id":null,"evidence_quote":"Introduces the sub-task decomposition of k-parity and the teacher-forcing training protocol for reasoning steps."},{"cited_title":"Learning parities with neural networks","cited_arxiv_id":null,"evidence_quote":"Establishes that imbalanced parity with $\\rho<1$ is learnable by one-layer networks, the baseline the paper contrasts with CoT."},{"cited_title":"Failures of gradient-based deep learning","cited_arxiv_id":null,"evidence_quote":"Shows standard gradient-based learning fails on uniform parity, motivating the difficulty that CoT is supposed to overcome."},{"cited_title":"Distribution-specific hardness of learning neural networks","cited_arxiv_id":null,"evidence_quote":"Provides distribution-specific hardness results for learning parities that justify the uniform-case difficulty assumption."}],"review_version":1}