Data Shifts Hurt CoT: A Theoretical Study

Debangshu Banerjee; Gagandeep Singh; Lang Yin

REVIEW 2 major objections 4 minor 25 references

Data Shifts Hurt CoT: A Theoretical Study

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2506.10647 v2 pith:EMD27EOQ submitted 2025-06-12 cs.LG cs.AI

Lang Yin , Debangshu Banerjee , Gagandeep Singh This is my paper

classification cs.LGcs.AI MSC 68T0768Q32

keywords chain-of-thoughtk-paritydistributionshiftdatapoisoningtransformerteacherforcingsoftmaxattentiongradientdescent

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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))$.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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$.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

Smaller 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).

What 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.

Who 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.

Referee Report

2 major / 4 minor

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.

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 (2)

[Appendix B.5, Eqs. (156)-(160)] 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.
[Appendix B.5, Eq. (161)] 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).

minor comments (4)

[Theorem 4.2 statement] 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.
[Corollary 4.3 proof] 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.
[Corollary 4.4 title] 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.
[Appendix B.5, Eq. (153)] 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.

Circularity Check

1 steps flagged · score 2.0 of 10

Local circular step in the necessity proof of Theorem 4.2: Eq. (158) replaces the erroneous CoT node output by ground truth, cancelling the Omega(1) error it must propagate.

other [Appendix B.5, Eqs. (157)-(160) (proof of the 'only if' direction of Theorem 4.2)]
"Ex∼Uniform({±1}d)|xp[m] −ˆxp[m]|=E|x mxm′ −ˆxm ˆxm′|(157) d→∞ =E|x mxm′ −x m ˆxm′|(158)"

Eq. (158) is introduced to prove the key propagation lemma of the 'only if' direction: an Omega(1) error at intermediate node m must make the root prediction have Omega(1) error. The equality replaces the generated value xhat_m by the ground truth x_m 'in the limit d→∞'. But Eq. (156), two lines earlier, proved E|x_m − xhat_m| ≥ 1/3 under the same failed-condition scenario, so xhat_m does not converge to x_m; the substitution is valid only if the child error vanishes, the opposite of the premise. The parent-error bound is therefore obtained by erasing the error that is supposed to propagate and reassigning the damage to the sibling xhat_{m′}, whose Omega(1) error was never established.

full rationale

The core of the paper is a direct gradient computation: the quantities G_{h[m]=1}, G_{h[m]>1}, and S in Eqs. (4)-(6) are derived from the explicit loss (3), and the sufficiency direction of Theorem 4.2 builds a recurrence for the per-step error epsilon_m from the attention-score separation implied by the B_m bounds. The poisoning threshold 1/(2(k-1)) and Corollary 4.4 are algebraic consequences of substituting rho=1 and q_{m,c1,c2}=1/2 into these computed expressions, not fitted values. The rho=0 corollary also follows from the computed gradient differences, which make B_m=0 via Eq. (121). No load-bearing self-citation appears; the CoT decomposition is taken from Kim and Suzuki (2025), an external prior result used as problem setup. The only circularity-shaped step is in the necessity proof, where the parent-error propagation replaces the erroneous node output by the ground truth in the d→∞ limit, thereby cancelling the Omega(1) error just established; this is a local question-begging step affecting the 'only if' direction, but it does not reduce the main prediction to its inputs by construction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claim rests on a specific training protocol (teacher forcing, all-zero initialization, one gradient update), a specific CoT tree with k a power of two, a no-input-poisoning model, and a uniform test input for the failure lower bound. These are stated assumptions, not fitted parameters. No invented entities appear.

free parameters (2)

epsilon = >0 arbitrary
Controls the sample complexity n = Omega(d^(2+epsilon)) and the probability bound 1 - exp(d^(epsilon/2)). It is chosen freely in the theorem, not fitted to data.
mu = > -2 - epsilon/4
Threshold exponent in Theorem 4.2 that also selects the learning rate eta = Theta(d^(-mu)) and appears in the error bound. A free parameter of the analysis, not fitted to data.

assumptions (5)

domain assumption Input bits are never poisoned; only CoT ground-truth labels are flipped.
Used throughout Section B, for example in Equation (97), where q_m = q_{m,c1,c2} relies on inputs having no poisoning. If input bits were poisoned, the cancellation structure would change.
domain assumption All-zero initialization and a single gradient update with softmax attention define the trained predictor.
The entire gradient analysis in Section B computes only the first gradient step. Guarantees are for this restricted training protocol, not general training.
domain assumption k = Theta(d) and k = 2^v for some integer v.
The CoT tree decomposition requires k to be a power of two (Section 3.2), and several asymptotic simplifications, for example in Appendix A, use k = Theta(d).
standard math Hoeffding's inequality and union bound concentration as formalized in Lemma A.1.
Used to bound perturbation terms in the gradient computations throughout Appendices A and B.
domain assumption The test input distribution for the failure lower bound is uniform over {+/-1}^d.
Appendix B.5 computes E_{x ~ Uniform} |y - y_hat| to prove failure, while training may be imbalanced. The success criterion is worst-case over inputs, so uniform test inputs are a witness.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Data Shifts Hurt CoT: A Theoretical Study." pith.science (2026). https://pith.science/paper/EMD27EOQ

@misc{pith2026250610647,
  author       = {Pith},
  title        = {Pith review of: Data Shifts Hurt CoT: A Theoretical Study},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EMD27EOQ}},
  note         = {Machine review of arXiv:2506.10647}
}

abstract

Chain of Thought (CoT) has been applied to various large language models (LLMs) and proven to be effective in improving the quality of outputs. In recent studies, transformers are proven to have absolute upper bounds in terms of expressive power, and consequently, they cannot solve many computationally difficult problems. However, empowered by CoT, transformers are proven to be able to solve some difficult problems effectively, such as the $k$-parity problem. Nevertheless, those works rely on two imperative assumptions: (1) identical training and testing distribution, and (2) corruption-free training data with correct reasoning steps. However, in the real world, these assumptions do not always hold. Although the risks of data shifts have caught attention, our work is the first to rigorously study the exact harm caused by such shifts to the best of our knowledge. Focusing on the $k$-parity problem, in this work we investigate the joint impact of two types of data shifts: the distribution shifts and data poisoning, on the quality of trained models obtained by a well-established CoT decomposition. In addition to revealing a surprising phenomenon that CoT leads to worse performance on learning parity than directly generating the prediction, our technical results also give a rigorous and comprehensive explanation of the mechanistic reasons of such impact.

Figures

Figures reproduced from arXiv: 2506.10647 by the authors.

**Figure 2.** and 3 for visualizations. We will denote qa,b,c = |Ua,b,c| for the size of this set [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 4.** Heatmap of testing loss with respect to both distribution shift and poisoning structure. Each [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗

Figures from the paper (2 more)

**Figure 5.** Figure 5: The same parity function where P = {2, 3, 5, 7, 9, 11, 14, 16} as one represented by [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]

**Figure 6.** Figure 6: Mean and variance of the test losses after repetitions [PITH_FULL_IMAGE:figures/full_fig_p027_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 12 canonical work pages

[1]

Understanding in-context learning in transformers and llms by learning to learn discrete functions

Satwik Bhattamishra, Arkil Patel, Phil Blunsom, and Varun Kanade. Understanding in-context learning in transformers and llms by learning to learn discrete functions. In The Twelfth International Conference on Learning Representations, 2024

work page 2024
[2]

Learning parities with neural networks

Amit Daniely and Eran Malach. Learning parities with neural networks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546

work page 2020
[3]

Chain-of-verification reduces hallucination in large language models

Shehzaad Dhuliawala, Mojtaba Komeili, Jing Xu, Roberta Raileanu, Xian Li, Asli Celikyilmaz, and Jason Weston. Chain-of-verification reduces hallucination in large language models. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Findings of the Association for Computational Linguistics: ACL 2024, pages 3563--3578, Bangkok, Thailand, August 2024....

doi:10.18653/v1/2024.findings-acl.212 2024
[4]

Position: LLM s can’t plan, but can help planning in LLM -modulo frameworks

Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil B Murthy. Position: LLM s can’t plan, but can help planning in LLM -modulo frameworks. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings...

work page 2024
[5]

Transformers provably solve parity efficiently with chain of thought

Juno Kim and Taiji Suzuki. Transformers provably solve parity efficiently with chain of thought. In The Thirteenth International Conference on Learning Representations, 2025

work page 2025
[6]

Metastable dynamics of chain-of-thought reasoning: Provable benefits of search, rl and distillation

Juno Kim, Denny Wu, Jason Lee, and Taiji Suzuki. Metastable dynamics of chain-of-thought reasoning: Provable benefits of search, rl and distillation. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 2025

work page 2025
[7]

How do nonlinear transformers acquire generalization-guaranteed cot ability? In High-dimensional Learning Dynamics 2024: The Emergence of Structure and Reasoning

Hongkang Li, Meng Wang, Songtao Lu, Xiaodong Cui, and Pin-Yu Chen. How do nonlinear transformers acquire generalization-guaranteed cot ability? In High-dimensional Learning Dynamics 2024: The Emergence of Structure and Reasoning

work page 2024
[8]

Dissecting chain-of-thought: compositionality through in-context filtering and learning

Yingcong Li, Kartik Sreenivasan, Angeliki Giannou, Dimitris Papailiopoulos, and Samet Oymak. Dissecting chain-of-thought: compositionality through in-context filtering and learning. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc

work page 2023

Show all 25 references

[9]

Chain of thought empowers transformers to solve inherently serial problems

Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. In The Twelfth International Conference on Learning Representations, 2024

2024
[10]

Let's verify step by step

Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2024

2024
[11]

Mind your step (by step): Chain-of-thought can reduce performance on tasks where thinking makes humans worse

Ryan Liu, Jiayi Geng, Addison J Wu, Ilia Sucholutsky, Tania Lombrozo, and Thomas L Griffiths. Mind your step (by step): Chain-of-thought can reduce performance on tasks where thinking makes humans worse. arXiv preprint arXiv:2410.21333, 2024

arXiv
[12]

The parallelism tradeoff: Limitations of log-precision transformers

William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11: 0 531--545, 2023. doi:10.1162/tacl_a_00562. URL https://aclanthology.org/2023.tacl-1.31/

2023 doi
[13]

The expressive power of transformers with chain of thought

William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations, 2024

2024
[14]

William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10: 0 843--856, 2022. doi:10.1162/tacl_a_00493. URL https://aclanthology.org/2022.tacl-1.49/

2022 doi
[15]

Show your work: Scratchpads for intermediate computation with language models, 2021

Maxwell Nye, Anders Andreassen, Guy Gur-Ari, Henryk Witold Michalewski, Jacob Austin, David Bieber, David Martin Dohan, Aitor Lewkowycz, Maarten Paul Bosma, David Luan, Charles Sutton, and Augustus Odena. Show your work: Scratchpads for intermediate computation with language m...

2021 arXiv
[16]

Jacob Pfau, William Merrill, and Samuel R. Bowman. Let s think dot by dot: Hidden computation in transformer language models. In First Conference on Language Modeling, 2024. URL https://openreview.net/forum?id=NikbrdtYvG

2024
[17]

Memory injections: Correcting multi-hop reasoning failures during inference in transformer-based language models

Mansi Sakarvadia, Aswathy Ajith, Arham Khan, Daniel Grzenda, Nathaniel Hudson, Andr \'e Bauer, Kyle Chard, and Ian Foster. Memory injections: Correcting multi-hop reasoning failures during inference in transformer-based language models. In Yonatan Belinkov, Sophie Hao, Jaap Ju...

2023
[18]

On second thought, let`s not think step by step! bias and toxicity in zero-shot reasoning

Omar Shaikh, Hongxin Zhang, William Held, Michael Bernstein, and Diyi Yang. On second thought, let`s not think step by step! bias and toxicity in zero-shot reasoning. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the...

2023 doi
[19]

Failures of gradient-based deep learning

Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3067--3...

2017
[20]

Distribution-specific hardness of learning neural networks

Ohad Shamir. Distribution-specific hardness of learning neural networks. J. Mach. Learn. Res., 19 0 (1): 0 1135–1163, January 2018. ISSN 1532-4435

2018
[21]

To cot or not to cot? chain-of-thought helps mainly on math and symbolic reasoning

Zayne Sprague, Fangcong Yin, Juan Diego Rodriguez, Dongwei Jiang, Manya Wadhwa, Prasann Singhal, Xinyu Zhao, Xi Ye, Kyle Mahowald, and Greg Durrett. To cot or not to cot? chain-of-thought helps mainly on math and symbolic reasoning. In The Thirteenth International Conference o...

2025
[22]

Gomez, ukasz Kaiser, and Illia Polosukhin

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17, page 6000–6010, Red Ho...

2017
[23]

Chi, Quoc V

Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Proceedings of the 36th International Conference on Neural Information Processing Sys...

2022
[24]

Sub-task decomposition enables learning in sequence to sequence tasks

Noam Wies, Yoav Levine, and Amnon Shashua. Sub-task decomposition enables learning in sequence to sequence tasks. In The Eleventh International Conference on Learning Representations, 2023

2023
[25]

Star: Bootstrapping reasoning with reasoning

Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 15476--15488. Curran Associate...

2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Understanding in-context learning in transformers and llms by learning to learn discrete functions

Satwik Bhattamishra, Arkil Patel, Phil Blunsom, and Varun Kanade. Understanding in-context learning in transformers and llms by learning to learn discrete functions. In The Twelfth International Conference on Learning Representations, 2024

work page 2024

[2] [2]

Learning parities with neural networks

Amit Daniely and Eran Malach. Learning parities with neural networks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546

work page 2020

[3] [3]

Chain-of-verification reduces hallucination in large language models

Shehzaad Dhuliawala, Mojtaba Komeili, Jing Xu, Roberta Raileanu, Xian Li, Asli Celikyilmaz, and Jason Weston. Chain-of-verification reduces hallucination in large language models. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Findings of the Association for Computational Linguistics: ACL 2024, pages 3563--3578, Bangkok, Thailand, August 2024....

doi:10.18653/v1/2024.findings-acl.212 2024

[4] [4]

Position: LLM s can’t plan, but can help planning in LLM -modulo frameworks

Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil B Murthy. Position: LLM s can’t plan, but can help planning in LLM -modulo frameworks. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings...

work page 2024

[5] [5]

Transformers provably solve parity efficiently with chain of thought

Juno Kim and Taiji Suzuki. Transformers provably solve parity efficiently with chain of thought. In The Thirteenth International Conference on Learning Representations, 2025

work page 2025

[6] [6]

Metastable dynamics of chain-of-thought reasoning: Provable benefits of search, rl and distillation

Juno Kim, Denny Wu, Jason Lee, and Taiji Suzuki. Metastable dynamics of chain-of-thought reasoning: Provable benefits of search, rl and distillation. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 2025

work page 2025

[7] [7]

How do nonlinear transformers acquire generalization-guaranteed cot ability? In High-dimensional Learning Dynamics 2024: The Emergence of Structure and Reasoning

Hongkang Li, Meng Wang, Songtao Lu, Xiaodong Cui, and Pin-Yu Chen. How do nonlinear transformers acquire generalization-guaranteed cot ability? In High-dimensional Learning Dynamics 2024: The Emergence of Structure and Reasoning

work page 2024

[8] [8]

Dissecting chain-of-thought: compositionality through in-context filtering and learning

Yingcong Li, Kartik Sreenivasan, Angeliki Giannou, Dimitris Papailiopoulos, and Samet Oymak. Dissecting chain-of-thought: compositionality through in-context filtering and learning. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc

work page 2023