Pith. sign in

REVIEW 3 major objections 5 minor 2 cited by

A one-layer transformer provably learns k-sparse Boolean functions — parity, AND, and OR — through either RL or SFT, with RL acquiring the entire chain of thought in a single gradient update while SFT learns it step by step.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-03 20:51 UTC pith:37I6P3OY

load-bearing objection Worth a serious referee; the RL half is proved for an immediate-reward surrogate, not the stated policy gradient, so the RL-vs-SFT contrast needs re-scoping. the 3 major comments →

arxiv 2511.17852 v2 pith:37I6P3OY submitted 2025-11-22 cs.LG stat.ML

Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently

Bochen Lyu , Yiyang Jia , Xiaohao Cai , Zhanxing Zhu This is my paper
classification cs.LG stat.ML MSC 68T0768Q32
keywords chain-of-thoughtRL fine-tuningSFT without teacher forcingk-sparse Boolean functionsparitypolicy gradientprovable learningtransformer attention dynamics
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper tries to establish that a one-layer transformer, fine-tuned either by reinforcement learning with per-step process rewards or by supervised fine-tuning without teacher forcing, provably learns k-sparse Boolean functions — parity, AND, and OR — when the task is decomposed into a chain of 2-input reasoning steps. Both guarantees rest on a single sufficient condition: the separation of the critical gradient component, meaning that at initialization the gradient is strictly larger at the two child positions each reasoning token should attend to than at every other position. Under that condition, RL reaches epsilon-accurate attention weights after one sign-policy-gradient update, so the whole chain of thought is learned at once, while SFT needs one update per chain level because later ground-truth labels are usable only after earlier generated steps are correct. If true, this converts an empirical contrast between RL and SFT into a sharp statement about learning dynamics, and it isolates the reward design and the absence of teacher forcing as the deciding factors.

Core claim

On the paper's own terms: fine-tuning a one-layer transformer on the intermediate steps of a recursively decomposed sparse Boolean function succeeds under one sufficient condition, the separation of the critical gradient component. Theorems 3.1 and 3.2 show that when this condition holds, sign-policy-gradient RL reaches ∥softmax(W(1))−softmax(W*)∥₁ ≤ ε after a single update, and sign-gradient SFT reaches the same error after T updates, where T is the length of the reasoning chain. The paper verifies the separation condition for k-PARITY, k-AND, and k-OR with specially chosen activation functions, and proves a hardness result: RL with only a final reward fails for sparse parity because the po

What carries the argument

The critical gradient component, γ^p_{l(t)}(y^{(t−1)}) = (2/(k−1)) ψ′(ξ_{l(t)}) φ₂(y_{i₁}, y_{i₂}) y_p, is the building block of both the policy gradient and the SFT gradient: each gradient entry factors as (γ_p − Σ_i γ_i σ_i) σ_p, so at the all-ones initialization its sign is determined by whether p is one of the two child nodes the current reasoning token must attend to. The 'separation' of this component — strictly larger at child positions than at all other positions — is the sufficient condition driving both theorems. Supporting machinery consists of causal plus 'pretrained' masks on the attention matrix W, which force step-t tokens to attend only to step-(t−1) tokens, and activation fu

Load-bearing premise

The RL theorem is proven for a truncated gradient (Eq. 9) that keeps only the immediate reward at each step, and the paper asserts, without derivation, that this equals optimizing RL with immediate reward; if that assertion fails, the one-update result applies to a greedy per-step objective rather than to the stated reward R(W).

What would settle it

On a small parity instance (say d=8, k=4), compute at initialization W=1 the full policy gradient of Eq. (8) including the future-reward terms, and compare the sign pattern of its attention entries with the sign pattern of the immediate-reward gradient in Eq. (9). If any child position loses its strictly positive sign relative to every non-child position, the one-update guarantee does not extend to the stated objective R(W), and the 'entire chain at once' conclusion holds only for the immediate-reward surrogate.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • If the separation condition holds, RL with per-step process rewards makes the transformer reach ε-accurate attention weights after a single sign-policy-gradient update, meaning the entire chain of thought is absorbed at once (Thm. 3.1).
  • SFT without teacher forcing needs exactly T sign-gradient updates, one per chain level, and this stepwise behavior is intrinsic to the objective rather than imposed by a curriculum (Thm. 3.2).
  • For sparse parity, RL with only a final reward is hard in this framework: the policy-gradient variance over the exponentially many candidate parity functions drowns out the target's signal (Prop. 3.1).
  • Both guarantees are powered by the same separation condition, so whenever SFT succeeds the corresponding RL variant also succeeds; the shared bottleneck is whether the initial gradient distinguishes child positions from non-child positions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The paper's RL result is proven for the update in Eq. (9), which drops the future-reward terms of the full policy gradient in Eq. (8); the text asserts without derivation that this is 'equivalent to optimizing RL with immediate reward.' If that equivalence fails, the one-update claim describes a greedy per-step reward algorithm, and the RL-versus-SFT contrast becomes a comparison between two diffe
  • A testable prediction follows for real reasoning models: with process-reward RL, per-step accuracy across the chain should improve simultaneously, whereas with SFT it should improve sequentially from the first step to the last — measurable by logging per-step accuracies during fine-tuning.
  • The separation condition is verified only for the three chosen activations ψ; for other k-sparse decomposable functions it may fail, so the paper delineates a class of CoT-friendly reasoning problems rather than establishing universal learnability.
  • The proofs are population-level statements; the authors list finite-sample analysis as future work, and sampling noise is the most immediate threat to the clean sign separation on which the one-update and T-update guarantees rely.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies a one-layer transformer with positional encoding, softmax self-attention, and a feedforward layer, fine-tuned by either RL (sign policy gradient) or SFT without teacher forcing, to learn k-sparse Boolean functions that are recursively decomposable into fixed 2-sparse Boolean functions. A hard mask is imposed on the attention weights, called a 'pretrained mask', to encode the recursive decomposition. The authors define a process reward, derive its policy gradient, and then state that optimizing with a truncated immediate-reward version is equivalent; under a separation condition on a 'critical gradient component', they prove that RL learns the entire chain in one update (Theorem 3.1), while SFT learns one step per update (Theorem 3.2). They verify the separation condition for k-PARITY, k-AND, and k-OR, and give exact attention dynamics for parity (Theorem 4.1). They also prove a hardness result for RL with only a final reward (Proposition 3.1). Numerical experiments on k-PARITY illustrate the claimed sign patterns.

Significance. If the results are correct, this is a valuable contribution: it provides one of the first theoretical analyses comparing RL and SFT for chain-of-thought fine-tuning in a tractable transformer model, with explicit separation conditions, closed-form dynamics for parity, and a negative result for final-reward RL. The paper is honest about its limitations (population gradient, hard-mask pretraining, one-layer model), and the parity analysis in Section 4.1 is concrete and checkable. The main conceptual claim — that RL learns the whole reasoning chain simultaneously while SFT learns it step by step — is interesting and empirically supported by the sign-pattern plots in Appendix D. However, the central derivation of the RL update is currently not rigorous, and the AND/OR verification is incomplete, so the significance of the main comparison is not yet fully established.

major comments (3)
  1. [Sec. 3.1, Eq. (8) vs Eq. (9)] The gradient used in Theorem 3.1 is not the policy gradient of the stated objective R(W). Lemma 1 correctly gives Eq. (8) with cumulative future rewards Σ_{τ≥t} r_τ. The text then asserts without proof that Eq. (9), which multiplies by only r_t, 'is equivalent to optimizing RL with immediate reward.' This equivalence is not generally true: r_{t+1} depends on y(t), so E[∇ log p(y(t)|y(t−1)) r_{t+1}] is generically nonzero. Because Theorem 3.1 and Theorem 4.1 analyze Eq. (9), the results establish learnability for a truncated immediate-reward estimator, not for vanilla policy gradient on the process-reward objective R(W) claimed in the introduction. This undermines the headline claim that 'RL learns the whole CoT chain in one update' as a statement about standard policy gradient. The authors must either prove that the omitted future-reward terms vanish at the relevant iterates (which is un
  2. [Thm 3.1 proof, around Eq. (45)] The proof of Theorem 3.1 asserts that 'W⋆ = arg max_W R(W) has the formulation' with attention scores 1/2 on relevant positions and 0 on irrelevant positions. This is not proven. The objective R(W) may have multiple global optima, and even if the ideal attention pattern is one of them, the error bound ∥softmax(W(1))−softmax(W⋆)∥₁ is only meaningful if W⋆ is that particular pattern. Please either characterize all global optimizers of R(W) and prove the ideal pattern is a global optimizer, or define W⋆ explicitly as the ideal attention matrix and prove the corresponding bound. As written, the theorem's conclusion is not justified.
  3. [Claim 4.2 and App. C.3.1, Eq. (127)] The verification that k-AND (and k-OR) satisfy the separation condition reduces to ∆ ∝ 8b > 0 (or ¯∆ ∝ 8c > 0), where b and c are sums over case-split regions D_{-1} and D_{+1}. The proof simply states that b > 0 (c > 0) without proving that these terms are strictly positive. With ψ(z) = max(z,0) for AND, p_+ = ψ(ξ) can be zero when ξ ≤ 0, and the sets D_{-1}/D_{+1} can be empty under the current policy. Therefore the separation condition is not rigorously established for all relevant cases. A complete case analysis, or additional assumptions on the initialization and the distribution of ξ, is needed before Claim 4.2 can be accepted.
minor comments (5)
  1. [Abstract / Definition 2.1] The abstract says 'k-sparse Boolean functions that can be recursively decomposed into fixed 2-sparse Boolean functions,' but the paper assumes k = 2^T. Please state this explicitly in the abstract or in Definition 2.1, as it restricts the class.
  2. [Sec. 2.2, Eq. (4)] The notation in the mask definition is hard to parse: t is used both for the index of the reasoning step and for a loop variable in the same sentence ('givent∈[T]' and 'ift= 1'). Please clarify the indexing, perhaps by using different symbols for the step index and the row index.
  3. [App. A.2, around Eq. (27)] In the proof of Lemma 2, the factorization p(y(t:)|x) = p(y(t:)|y(t−1)) is used; this relies on the pretrained mask making y(t) depend only on y(t−1). The independence of tokens within y(t) is also used implicitly. A short justification of these factorizations would improve readability.
  4. [Sec. 4.1, Eq. (16)] The notation 'dt−1−2' is ambiguous: it should be d_t − 1 − 2 or d_{t-1} − 2? Please disambiguate with parentheses or typeset clearly. Similar notation appears in several equations in the appendix.
  5. [App. D] The numerical experiment uses 50,000 samples but reports no confidence intervals or multiple seeds. Since the plots are meant to support the theoretical sign-pattern claims, a few independent runs or an explicit statement that the sign pattern is deterministic under the analytic gradient would strengthen the evidence.

Circularity Check

0 steps flagged

No significant circularity: the theorems are conditional on an explicit separation condition, verified by direct calculation for the worked examples.

full rationale

The paper's central derivations are self-contained conditional statements rather than fitted predictions. Theorem 3.1 assumes the separation of the critical gradient component (Eqs. 10-11) and derives, via Lemma 2, that sign policy-gradient updates on the explicitly stated estimator Eq. (9) increase relevant attention weights and decrease irrelevant ones; the proof is algebraic and does not reuse the conclusion. Theorem 3.2 is analogous. The applications in Section 4 do not assume learnability: for k-PARITY (Theorem 4.1), k-AND, and k-OR (Claim 4.2), the separation inequalities are checked by explicit expectations, and the activation functions are stated as designed choices (Table 1) rather than fitted to the target result. There is no parameter fitting to data and no renamed empirical pattern being presented as prediction; the numerical section is illustrative. The only in-scope issue I flag is one of internal consistency, not circularity: after Eq. (8), the text says 'we consider optimizing max_W R(W) with the policy gradient below, which is equivalent to optimizing RL with immediate reward,' and Eq. (9) drops the future-reward terms from the REINFORCE gradient. That equivalence is asserted without proof and is not evidently true as stated. However, Theorem 3.1 is explicitly stated and proved for the sign of the Eq. (9) estimator, so the paper does not secretly substitute the conclusion of the theorem. The one self-citation (Lyu et al. 2025) appears only among several references for an architectural tractability choice and is not load-bearing. The hand-designed masks and activations are disclosed as structural priors/designed expressibility choices, not as independently fitted inputs, so they do not make the derivation circular. No circular step can be exhibited from the paper's own equations.

Axiom & Free-Parameter Ledger

0 free parameters · 8 axioms · 1 invented entities

The central results rest on a heavily specified toy model: fixed tree recursion, hard-coded level masks, per-function activations, population sign-gradient updates, and exact intermediate supervision. The paper contributes the separation-condition proof technique and verifies it on three examples, but these structural choices are assumed rather than derived.

axioms (8)
  • domain assumption Input x is uniform over {±1}^d, coordinates are independent, and the support B is fixed.
    Used throughout Def. 2.1 and all expectation computations, e.g., E_x[x_i]=0 and independence of coordinates in Lemma 5 and Appendix C.
  • domain assumption The target k-sparse function has k=2^T and decomposes into a complete binary tree of fixed 2-sparse Boolean functions.
    The whole CoT construction, the number of SFT updates T, and the mask structure depend on this exact recursion.
  • ad hoc to paper The model is the specific one-layer transformer of Sec. 2.2: merged key-query matrix, value matrix preserving only x, no residual, and causal mask plus Eq. (5).
    The proofs are tied to this exact architecture; it is not justified as an approximation to standard transformers.
  • ad hoc to paper The hard mask in Eq. (4) encodes which level of the tree each token belongs to and is called 'pretraining'.
    The mask gives the model the recursive level structure for free; the paper admits this is a heuristic structural prior, not learned pretraining.
  • ad hoc to paper The activation function ψ is chosen per target function (Table 1) so that the expressibility condition Eq. (73) holds.
    Learnability for AND and OR depends on these specific ReLU/min variants; the model is not generic across activations.
  • ad hoc to paper Optimization is population sign-gradient descent with W(0)=1 and η=Ω(ln(d/ϵ)).
    All theorems are for this specific optimizer; no finite-sample or stochastic-gradient analysis is provided.
  • ad hoc to paper The RL update uses the immediate-reward policy gradient in Eq. (9), dropping future-reward terms from Eq. (8).
    Sec. 3.1 asserts this is equivalent to immediate-reward RL without a derivation; the theorem proves learnability for this modified update.
  • domain assumption The separation of the critical gradient component holds for the functions considered.
    For parity this is proven as Theorem 4.1; for AND and OR it is argued in Claim 4.2 and the appendix. For general k-sparse functions it remains a sufficient condition.
invented entities (1)
  • Hard 'pretrained' mask (Eq. 4) no independent evidence
    purpose: Inject the recursive-decomposition level structure into the attention pattern so that each CoT step attends only to the previous level.
    No learning or pretraining produces this mask; it is a hand-designed prior and would not transfer to unseen decompositions.

pith-pipeline@v1.3.0-alltime-deepseek · 70460 in / 16431 out tokens · 168241 ms · 2026-08-03T20:51:42.366444+00:00 · methodology

0 comments
read the original abstract

Transformers can acquire Chain-of-Thought (CoT) capabilities to solve complex reasoning tasks through fine-tuning. Reinforcement learning (RL) and supervised fine-tuning (SFT) are two primary approaches to this end. In this work, we specifically examine RL with process rewards and SFT for learning $k$-sparse Boolean functions with a one-layer transformer through intermediate reasoning steps akin to CoT. In particular, we consider $k$-sparse Boolean functions that can be recursively decomposed into fixed 2-sparse Boolean functions. We first analyze the learning dynamics of RL fine-tuning with process reward and SFT in a unified way. This allows us to identify sufficient conditions under which the transformer provably learns these sparse Boolean functions. We then verify that these conditions hold for three basic examples, including $k$-PARITY, $k$-AND, and $k$-OR, thus demonstrating their learnability via both RL and SFT. Notably, we reveal that RL and SFT exhibit distinct learning behaviors: RL learns the whole CoT chain simultaneously, whereas SFT naturally learns the CoT chain step by step. Overall, our findings provide insights on the mechanisms underlying RL and SFT and how they differ in triggering the CoT capabilities of transformers, and suggest that the comparison between RL and SFT may need to consider the reward design and the use of teacher forcing.

Figures

Figures reproduced from arXiv: 2511.17852 by Bochen Lyu, Xiaohao Cai, Yiyang Jia, Zhanxing Zhu.

Figure 1
Figure 1. Figure 1: (a) Recursive decomposition of learning a k-sparse Boolean function Φk(x) with a random set B ⊆ [d] (shaded boxes in the lowest level) into solving sub-tasks by following a reasoning chain (bottom to top). Each level of the binary tree corresponds to a step of the reasoning chain, where each node in a level computes a 2-sparse Boolean function ϕ2(·, ·) over its two child nodes. (b) The self-attention weigh… view at source ↗
Figure 2
Figure 2. Figure 2: The pretrained transformer iteratively uses its output to solve [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (a) The ground truth (σ ⋆ ) Nt−2+p Nt−1+l (t) . Each white box is 0.5 and each gray box is 0. (b) sign(∇W L(W)) at W(0) = 1. Each white box has value +1 and each black box has value −1. Gray boxes have value 0 coming from causal mask and pretrained mask. 41 [PITH_FULL_IMAGE:figures/full_fig_p041_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: sign(−∇W L(W)) computed by W(s) for different updating step s. Each white box has value +1, each black box has value −1, and grey boxes are 0. 42 [PITH_FULL_IMAGE:figures/full_fig_p042_4.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On the Emergence of Implicit Curriculum in RLVR Learning Dynamics

    cs.LG 2026-02 conditional novelty 8.0

    For a stylized transformer, outcome-only RL learns short compositions, and mixed-difficulty training produces an implicit easy-to-hard curriculum: smooth difficulty spectra relay progress, abrupt spectra grok.

  2. On the Emergence of Implicit Curriculum in RLVR Learning Dynamics

    cs.LG 2026-02 unverdicted novelty 6.0

    RLVR training on transformers for compositional tasks follows an implicit curriculum from easy to hard problems, with difficulty spectrum smoothness determining steady relay progress or grokking phase transitions.

Reference graph

Works this paper leans on

35 extracted references · 27 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Lower bounds for chain-of-thought reasoning in hard-attention transformers, 2025

    Alireza Amiri, Xinting Huang, Mark Rofin, and Michael Hahn. Lower bounds for chain-of-thought reasoning in hard-attention transformers, 2025. URL https://arxiv.org/abs/2502.02393

    Pith/arXiv arXiv 2025

  2. [2]

    Training a helpful and harmless assistant with reinforcement learning from human feedback, 2022

    Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, Nicholas Joseph, Saurav Kadavath, Jackson Kernion, Tom Conerly, Sheer El-Showk, Nelson Elhage, Zac Hatfield-Dodds, Danny Hernandez, Tristan Hume, Scott Johnston, Shauna Kravec, Liane Lovitt, Neel Nanda, Catherine Olsson, ...

    Pith/arXiv arXiv 2022

  3. [3]

    Ehrenfeucht-haussler rank and chain of thought, 2025

    Pablo Barceló, Alexander Kozachinskiy, and Tomasz Steifer. Ehrenfeucht-haussler rank and chain of thought, 2025. URL https://arxiv.org/abs/2501.12997

    Pith/arXiv arXiv 2025

  4. [4]

    Simplicity bias in transformers and their ability to learn sparse B oolean functions

    Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom. Simplicity bias in transformers and their ability to learn sparse B oolean functions. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5767--5791, Toronto, ...

    doi:10.18653/v1/2023.acl-long.317 2023

  5. [5]

    Theoretical limitations of multi-layer transformer, 2024 a

    Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical limitations of multi-layer transformer, 2024 a . URL https://arxiv.org/abs/2412.02975

    Pith/arXiv arXiv 2024

  6. [6]

    Training dynamics of multi-head softmax attention for in-context learning: Emergence, convergence, and optimality, 2024 b

    Siyu Chen, Heejune Sheen, Tianhao Wang, and Zhuoran Yang. Training dynamics of multi-head softmax attention for in-context learning: Emergence, convergence, and optimality, 2024 b . URL https://arxiv.org/abs/2402.19442

    Pith/arXiv arXiv 2024

  7. [7]

    Brown, Miljan Martic, Shane Legg, and Dario Amodei

    Paul Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences, 2023. URL https://arxiv.org/abs/1706.03741

    Pith/arXiv arXiv 2023

  8. [8]

    SFT memorizes, RL generalizes: A comparative study of foundation model post-training

    Tianzhe Chu, Yuexiang Zhai, Jihan Yang, Shengbang Tong, Saining Xie, Dale Schuurmans, Quoc V Le, Sergey Levine, and Yi Ma. SFT memorizes, RL generalizes: A comparative study of foundation model post-training. In Forty-second International Conference on Machine Learning, 2025. URL https://openreview.net/forum?id=dYur3yabMj

    2025

  9. [9]

    DeepSeek-AI, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang, Bochao Wu, Bei Feng, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai D...

    Pith/arXiv arXiv 2025

  10. [10]

    Why are sensitive functions hard for transformers?, 2024

    Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers?, 2024. URL https://arxiv.org/abs/2402.09963

    Pith/arXiv arXiv 2024

  11. [11]

    Minimalist softmax attention provably learns constrained boolean functions, 2025

    Jerry Yao-Chieh Hu, Xiwen Zhang, Maojiang Su, Zhao Song, and Han Liu. Minimalist softmax attention provably learns constrained boolean functions, 2025. URL https://arxiv.org/abs/2505.19531

    Pith/arXiv arXiv 2025

  12. [12]

    Unveiling the statistical foundations of chain-of-thought prompting methods, 2024

    Xinyang Hu, Fengzhuo Zhang, Siyu Chen, and Zhuoran Yang. Unveiling the statistical foundations of chain-of-thought prompting methods, 2024. URL https://arxiv.org/abs/2408.14511

    Pith/arXiv arXiv 2024

  13. [13]

    How transformers learn regular language recognition: A theoretical study on training dynamics and implicit bias, 2025

    Ruiquan Huang, Yingbin Liang, and Jing Yang. How transformers learn regular language recognition: A theoretical study on training dynamics and implicit bias, 2025. URL https://arxiv.org/abs/2505.00926

    Pith/arXiv arXiv 2025

  14. [14]

    In-context convergence of transformers, 2023

    Yu Huang, Yuan Cheng, and Yingbin Liang. In-context convergence of transformers, 2023. URL https://arxiv.org/abs/2310.05249

    Pith/arXiv arXiv 2023

  15. [15]

    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. URL https://openreview.net/forum?id=n2NidsYDop

    2025

  16. [16]

    Kingma and Jimmy Ba

    Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017. URL https://arxiv.org/abs/1412.6980

    Pith/arXiv arXiv 2017

  17. [17]

    Training language models to self-correct via reinforcement learning, 2024

    Aviral Kumar, Vincent Zhuang, Rishabh Agarwal, Yi Su, John D Co-Reyes, Avi Singh, Kate Baumli, Shariq Iqbal, Colton Bishop, Rebecca Roelofs, Lei M Zhang, Kay McKinney, Disha Shrivastava, Cosmin Paduraru, George Tucker, Doina Precup, Feryal Behbahani, and Aleksandra Faust. Training language models to self-correct via reinforcement learning, 2024. URL https...

    Pith/arXiv arXiv 2024

  18. [18]

    Chain of thought empowers transformers to solve inherently serial problems, 2024

    Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems, 2024. URL https://arxiv.org/abs/2402.12875

    Pith/arXiv arXiv 2024

  19. [19]

    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. URL https://openreview.net/forum?id=v8L0pN6EOi

    2024

  20. [20]

    A solvable attention for neural scaling laws

    Bochen Lyu, Di Wang, and Zhanxing Zhu. A solvable attention for neural scaling laws. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=wYxOMEzpkl

    2025

  21. [21]

    The expressive power of transformers with chain of thought, 2024

    William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought, 2024. URL https://arxiv.org/abs/2310.07923

    Pith/arXiv arXiv 2024

  22. [22]

    Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu

    Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning, 2016. URL https://arxiv.org/abs/1602.01783

    Pith/arXiv arXiv 2016

  23. [23]

    Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback,...

    Pith/arXiv arXiv 2022

  24. [24]

    Proximal policy optimization algorithms, 2017

    John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms, 2017. URL https://arxiv.org/abs/1707.06347

    Pith/arXiv arXiv 2017

  25. [25]

    Failures of gradient-based deep learning, 2017

    Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning, 2017. URL https://arxiv.org/abs/1703.07950

    Pith/arXiv arXiv 2017

  26. [26]

    Distribution-specific hardness of learning neural networks, 2017

    Ohad Shamir. Distribution-specific hardness of learning neural networks, 2017. URL https://arxiv.org/abs/1609.01037

    Pith/arXiv arXiv 2017

  27. [27]

    Transformers learn low sensitivity functions: Investigations and implications, 2025

    Bhavya Vasudeva, Deqing Fu, Tianyi Zhou, Elliott Kau, Youqi Huang, and Vatsal Sharan. Transformers learn low sensitivity functions: Investigations and implications, 2025. URL https://arxiv.org/abs/2403.06925

    Pith/arXiv arXiv 2025

  28. [28]

    Transformers learn in-context by gradient descent, 2023

    Johannes von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent, 2023. URL https://arxiv.org/abs/2212.07677

    Pith/arXiv arXiv 2023

  29. [29]

    Lee, and Denny Wu

    Zixuan Wang, Eshaan Nichani, Alberto Bietti, Alex Damian, Daniel Hsu, Jason D. Lee, and Denny Wu. Learning compositional functions with transformers from easy-to-hard data, 2025. URL https://arxiv.org/abs/2505.23683

    Pith/arXiv arXiv 2025

  30. [30]

    Chi, Quoc V Le, and Denny Zhou

    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 Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?i...

    2022

  31. [31]

    Sub-task decomposition enables learning in sequence to sequence tasks, 2023

    Noam Wies, Yoav Levine, and Amnon Shashua. Sub-task decomposition enables learning in sequence to sequence tasks, 2023. URL https://arxiv.org/abs/2204.02892

    Pith/arXiv arXiv 2023

  32. [32]

    In-context learning with representations: Contextual generalization of trained transformers, 2024

    Tong Yang, Yu Huang, Yingbin Liang, and Yuejie Chi. In-context learning with representations: Contextual generalization of trained transformers, 2024. URL https://arxiv.org/abs/2408.10147

    Pith/arXiv arXiv 2024

  33. [33]

    Multi-head transformers provably learn symbolic multi-step reasoning via gradient descent, 2025

    Tong Yang, Yu Huang, Yingbin Liang, and Yuejie Chi. Multi-head transformers provably learn symbolic multi-step reasoning via gradient descent, 2025. URL https://arxiv.org/abs/2508.08222

    arXiv 2025

  34. [34]

    ST ar: Bootstrapping reasoning with reasoning

    Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. ST ar: Bootstrapping reasoning with reasoning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=_3ELRdg2sgI

    2022

  35. [35]

    Bartlett

    Ruiqi Zhang, Spencer Frei, and Peter L. Bartlett. Trained transformers learn linear models in-context, 2023. URL https://arxiv.org/abs/2306.09927

    Pith/arXiv arXiv 2023