acceptodds
Under review as a conference paper at ICLR 2027

Transformers Provably Solve Parity by Internalizing Chain-of-Thought

Abstract

Chain-of-thought (CoT) improves the performance of transformers on complex reasoning tasks. However, generating explicit reasoning traces incurs substantial inference overhead. Implicit CoT (ICoT) aims to internalize these reasoning steps by gradually removing intermediate CoT tokens during training, yet the learning dynamics of this process remain poorly understood. We provide a theoretical analysis of ICoT for parity learning in a one-layer transformer with multi-head softmax attention. We prove that removing one intermediate token at a time enables ordinary gradient descent (GD) to solve parity with polynomially many samples and updates under suitable initialization. Our analysis characterizes a race among attention heads in which each newly missing parity bit recruits a new head while previously learned assignments are preserved. In contrast, we show that direct training from final-answer supervision alone leaves GD with high prediction error. Numerical experiments support our theoretical findings. Together, these results provide a mechanistic explanation for how a curriculum with intermediate supervision can enable efficient learning without explicit CoT at inference time.

Primary area:
learning theory
Keywords:
Transformer, Chain-of-Thought, Parity Learning, Learning Dynamics

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_oTCcOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the gradient descent dynamics of implicit chain-of-thought (iCoT) learning in a one-layer multi-head transformer on the parity task. The analysis shows how one head picks up each new relevant input bit while earlier heads keep their learned choices. Under the stated conditions, direct training on final answers fails. They also provide numerical results to support the theoretical findings.

Critical strengths
  1. The analysis of multi-head learning dynamics which illustrates the competition among attention heads during training is very interesting and technically novel. Most of previous theoretical work has paid relatively little attention to interactions between different heads while they studied the multi-head setup. This paper helps explain how multiple heads learn together and how their assignments evolve during training.

  2. I appreciate the clear comparison with closely related work e.g., Huang et al. (2026) and Tsilivis et al. (2026). The authors directly explain how their results differ from previous studies, which helps clarify the technical contribution of this paper.

Critical weaknesses

The main weakness is that, based on how the paper frames its contribution, the advance over prior ICoT results like Huang et al. (2026) seems somewhat limited. The paper extends the analysis to multi-head softmax attention and removes assumptions such as parameter rounding, but introduces other conditions on the initialization of attention heads and the stopping rule between stages. While the multi-head analysis provides useful insights into the learning dynamics, it is unclear how much broader understanding of ICoT these results provide beyond the setting studied in this paper.

Questions for authors
  1. The paper removes parameter rounding but introduces new conditions on the bos initialization and stage transitions. Could the author clarify what additional understanding of ICoT does this provide compared with earlier work? (see the weakness)

  2. The multi-head analysis requires one new head to be recruited at each stage while earlier heads keep their assignments. I found in Section G.5, it shows some different learning patterns in experiments, where heads forms cancelling pairs and changes their assignments. Can the theory be extended to explain these behaviors?

  3. Can the approach be extended to handle longer inputs or more relevant bits without retraining from scratch?

2 comments

We thank the reviewer for the thoughtful and constructive assessment. We appreciate their recognition of the technical novelty of our multi-head learning dynamics analysis and the clarity of our comparison with prior work. We clarify the additional insights our results provide and address the reviewer’s questions below.

W1 & Q1: Additional understanding beyond earlier ICoT results.

Our central contribution is explaining how ordinary GD acquires new computations while preserving earlier ones under coupled, nonconvex dynamics. Huang et al. (2026) use rounding to keep previously trained layers unchanged, while Tsilivis et al.’s (2026) within-stage analysis reduces to linear regression. In our setting, each deletion exposes a missing bit with an order-one normalized-gradient advantage (Lemma 3). Competition among idle heads recruits one head and suppresses redundant recruitment (Lemma 9), while previously recruited heads retain their assignments despite continuing to train. Establishing acquisition and retention jointly is the key technical challenge.

The initialization and stopping conditions specify the starting state and when the supervised target changes. The initialization is independent of the secret and permits independently sampled BOS scales (Corollary 1). The stopping rule determines stage transition timing without rounding, resetting, or freezing learned parameters. Theorem 1 proves that these updates reach the stopping conditions in polynomial time.

The analysis also explains why initialization and curriculum design matter. Exact head symmetry prevents specialization (Proposition 2), and specified diffuse random initializations lead to exponentially slow learning when H=Ω(d)H=\Omega(d) (Proposition 3). For dense parity, Corollary 2 isolates the curriculum’s benefit through a comparison with direct population GD under the same architecture and initialization. Corollary 3 establishes an obstruction for the specified right-to-left schedule. Appendix G.4 further illustrates how premature deletion can cause failure that longer training resolves. These results identify concrete mechanisms behind initialization and schedule sensitivity. The quantitative conditions in Theorem 1 are sufficient rather than necessary.

Q2: Cancelling pairs and changing assignments.

Our current analysis explains part of this behavior. At sharp attention assignments, two heads selecting the same key contribute xj2=1x_j^2=1, so a correct prefix prediction can include heads attending to irrelevant keys. Lemma 5 (Appendix B.2) allows precisely this possibility: its assignment condition requires that the keys selected an odd number of times match the target support. It therefore establishes local stability and sharpening near correct configurations containing cancelling pairs.

The remaining challenge is to explain how GD forms and reorganizes these pairs across stages. Theorem 1 tracks previously idle heads moving from BOS to newly required bits while previously recruited heads retain their assignments. Cancelling-pair trajectories can instead involve several heads changing assignments together. Moreover, Figures 6–7 show that the model can underfit one stage and recover later, so it may need to learn multiple missing bits in the next stage. Extending the proof would therefore require tracking the parity represented collectively by groups of heads and analyzing transitions between these configurations. A full convergence guarantee for these dynamics remains open, and we will discuss it in the limitations section of the revision.

Q3: Longer inputs or more relevant bits without retraining from scratch.

For more relevant bits within the existing input dimension, the curriculum already provides a way to continue training without reinitialization. To extend a learned kk-bit prefix to k′>kk'>k, with H≥k′H\geq k', we can continue through k′−kk'-k additional stages using the corresponding prefix labels. Previously recruited heads retain their assignments, while unused heads learn the additional bits. Theorem 1 guarantees this continuation from checkpoints satisfying the nonfinal stopping conditions: these ensure that earlier assignments are sufficiently stable and unused heads remain ready to learn. Thus, the guarantee concerns continuation from suitable curriculum checkpoints, rather than adaptation from any completed model.

For longer inputs, new positions require additional attention parameters. Reusing the learned logits and initializing only the new ones is a natural extension, but adding keys also changes softmax normalization and may disrupt the conditions needed for further recruitment. Our current theorem assumes a fixed input dimension, and a guarantee for this length extension is left to future work.

Thank you for the detailed response. It helped clarify the paper's contributions relative to prior work. While I sitll feel the broader insights somewhat limited, I believe the paper makes a sufficiently distinct contribution. I therefore maintain my recommendation for acceptance.

Reviewer_mkxFOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how a transformer learns parity while gradually removing intermediate CoT tokens during training. The model the theory studies consists of one attention layer with multiple softmax heads, followed by a fixed function that multiplies their outputs. The curriculum progressively asks the model to predict the parity of more relevant input bits, until it predicts the final answer without intermediate tokens. Under a pre-specified initialization and training curriculum, the authors prove that gradient descent learns the target with polynomially many samples and updates. Their analysis explains how each stage recruits one previously unused head while preserving the assignments learned by other heads. They also prove that direct final-answer training has high squared error under population GD, their initialization assumptions, and dense parity.

Synthetic experiments are done and provide evidence for the predicted mechanism: unused heads learn the newly introduced bits while earlier assignments are retained. Internalization achieves the same accuracy as explicit CoT, whereas direct training remains near chance. Further experiments examine how initialization, training duration, and the number of heads affect this process. Interestingly, under the more relaxed initialization for BOS and the rest of the logits, learning can also succeed when some earlier head assignments change, suggesting that the mechanisms analyzed in the theory is one of several possible paths to learn parity (under the curriculum).

Critical strengths

Nontrivial learning dynamics theory. The learning process is quite intriguing and complex. From my understanding, the main insight is that when a new parity bit is introduced in training, several unused heads can receive a learning signal for that bit. Successful learning requires one head to select it, the remaining heads to stay available, and previously learned assignments to survive further updates. The authors show how these conditions are maintained across the curriculum, obtaining prediction guarantee that holds uniformly over all inputs. This is the main technical contribution from my understanding.

Experimental analysis of the theory’s regime of “validity”. The experiments help explain which aspects of the theoretical mechanism extend beyond the analyzed setting. The predicted head-assignment behavior persists with Adam (theory works with GD), trainable BOS logits (theory keeps it frozen), Gaussian initialization (theory initialize all non-BOS logits to zero), and so on, providing evidence that the relatively strict assumptions in the theory can be relaxed in practical settings. More interestingly, certain successful runs learn cancelling head pairs and later reorganize them. This suggests that the role of BOS (keeping heads that are not yet needed from altering the current prediction in the theory, if I understand right) can also be achieved through certain (learned) coordination between heads. I do not really view this as a weakness of the theory: I think the more monotone, progressive head assignment dynamics for forming latent CoT paths in the model is already quite interesting, and the experiments pave the way for further principled understanding of how latent CoT abilities can develop in transformers in non-monotone and interestingly coordinated ways -- considering how difficult learning theory of transformers (and neural networks in general) is, I think the experiments in this paper are quite nice in spelling out what the simplified setting cannot capture and suggesting future directions.

Critical weaknesses

I think the main weakness of the theory is that it captures a restricted model of CoT internalization. Each prediction position has separate attention parameters, so the predictor used at inference evolves independently of the losses at other CoT positions (Lemma 2, also pointed out in the main text). Its training is therefore equivalent to learning successive prefix-parity targets. This gives a useful explanation of how previously learned computations are preserved and extended as intermediate tokens are removed, but it leaves open how this process works when parameters are shared across positions and their learning objectives interact, which real transformers do (and the experiments show that there indeed are more subtle coordinations between the heads during learning).

Questions for authors

There are a few experimental specifications that are missing in the paper which can influence how solid the experiments are. Are the final-answer accuracies for explicit CoT in Tables 2 and 4 measured using model-generated intermediate predictions or ground-truth prefixes? If model-generated predictions are used, are the continuous outputs passed directly to subsequent positions or converted into Boolean tokens? Also, could the authors provide hyperparameters for their training (the training dataset size, optimizer hyperparameters, and the definition of the “all-input sign certificate”)? I could not find these details in the paper.

1 comment

We thank the reviewer for the thoughtful and constructive assessment. We appreciate their recognition of our analysis of coupled multi-head learning dynamics and the value of our experiments. We address the concern about position-dependent attention and clarify the experimental specifications below.

(W) Position-dependent attention.

We agree that our model parameterizes attention separately at each position, and acknowledge that it does not capture the setting where parameters are shared across positions and their learning objectives interact, as in real transformers. This parameterization follows the positional-attention abstraction of Kim & Suzuki (2025, §2.2), also adopted by Huang et al. (2026, §2.2) and Tsilivis et al. (2026, §4). These models learn positional attention while fixing the feedforward computation. Tsilivis et al. likewise analyze the first output row through successive prefix-parity targets. Within this abstraction, our main contribution is the characterization of coupled multi-head softmax dynamics: how ordinary GD recruits new heads while preserving previously learned assignments.

(Q1) Explicit-CoT evaluation.

The final-answer accuracies for Explicit CoT in Tables 2 and 4 are measured using model-generated intermediate predictions, not ground-truth prefixes. We take the sign of each intermediate prediction as the intermediate CoT token before passing it to subsequent positions; the continuous outputs are not passed directly. Ground-truth prefixes are used only during training. We will state this explicitly in Appendix G.

(Q2) Training specifications.

For Tables 2 and 4, each seed uses a fixed pool of 100,000100{,}000 independent uniform Boolean inputs, reused across stages. Minibatches contain 1,0241{,}024 examples sampled with replacement. We use Adam with constant learning rate 0.010.01, (β1,β2)=(0.9,0.999)(\beta_1,\beta_2)=(0.9,0.999), ϵ=10−8\epsilon=10^{-8}, zero weight decay, and AMSGrad disabled. The training objective averages squared error over examples and sums over active prediction rows.

Each setting uses ten seeds and kk blocks of 740740 updates per method, giving 740k740k updates in total; internalization removes one token between consecutive blocks. Methods share their corresponding initial parameters and exactly matched minibatch sequences. Learned weights are carried forward, while Adam’s moment buffers and step counter are reset at each block for all three methods. Longer-budget runs use 1,4801{,}480 updates per block. We will explicitly state these settings in Appendix G.

(Q3) All-input sign certificate.

This is a sufficient check on the learned attention weights that guarantees correct prediction signs for every Boolean input. It uses the total attention error defined in Appendix A and the uniform prediction-error argument already presented in Appendix D (proof of Theorem 1).

Writing ph,ip_{h,i} for head hh’s attention weights, we select its highest-attention key aha_h and require

\qquad E=\sum_{h=1}^{H}(1-p_{h,a_h})<\frac{1}{2}.$$ We additionally require that the raw coordinates selected an odd number of times are exactly the current target support. BOS has value $1$ and is excluded from this count. This makes the product of the values at the selected keys equal to the target parity, even when the assignment includes cancelling pairs of heads. The Appendix D argument then gives $|\widehat y(x)-y(x)|\le 2E<1$ for every input, ensuring the correct sign without exhaustive evaluation. We will state this explicitly alongside the results reported in Appendix G.
Reviewer_r7NBOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the theoretical learning dynamics of implicit chain-of-thought (ICoT) on the parity problem. The authors consider a simplified one-layer, multi-head softmax-attention model with a fixed multiplicative readout and a curriculum that progressively removes intermediate parity tokens.

The main theoretical result shows that, under carefully designed initialization and stage-wise stopping conditions, full-batch gradient descent can learn parity with polynomial sample and iteration complexity. The analysis characterizes a sequential head-recruitment mechanism, where each newly required parity bit is assigned to an unused attention head while previously learned assignments are preserved. The authors also establish a negative result for direct final-answer training under population gradient descent and symmetric initialization.

Synthetic experiments on parity tasks with input dimensions 32 and 64 are used to illustrate the theoretical predictions and compare direct training, explicit CoT, and ICoT.

Critical strengths

The main technical strength is the analysis of multi-head softmax attention under ordinary gradient descent, without the parameter rounding or freezing mechanisms required by some previous theoretical studies. The characterization of head competition and assignment preservation is also mathematically interesting.

However, I view these primarily as technical refinements of an already established theoretical framework, rather than substantive new conceptual contributions. They do not outweigh my concerns about novelty, relevance, and significance.

Critical weaknesses

1. Limited novelty and substantial overlap with existing literature.

My primary concern is that the paper revisits a problem for which much of the central conceptual understanding has already been established.

Kim and Suzuki (ICLR 2025) studied parity learning in one-layer transformers and established the importance of intermediate CoT supervision. More importantly, Huang et al. (2026), Transformers Provably Learn to Internalize Chain-of-Thought, and Tsilivis et al. (2026), Learning through Internalization, have already provided theoretical analyses of learning parity through progressive CoT internalization, including efficient learning without explicit intermediate tokens at inference.

The present paper differs in its use of multi-head softmax attention, ordinary gradient descent, and the absence of rounding or parameter freezing. I acknowledge these differences. Nevertheless, the central qualitative conclusions—efficient parity learning through progressive internalization and the importance of intermediate supervision—are already known.

I am not convinced that replacing the optimization and architectural assumptions in previous stylized models constitutes a sufficiently significant advance, particularly when the resulting theoretical setting remains highly specialized. The paper does not clearly establish a genuinely new learning principle beyond those identified in prior work.

2. Strong structural assumptions and limited practical relevance substantially weaken the significance of the theoretical and empirical results.

Despite the title's broad reference to transformers, the analyzed architecture is an attention-table model followed by a fixed product readout. This readout explicitly implements the algebraic operation required by parity and is not learned. Moreover, successful convergence requires at least as many attention heads as relevant parity bits, carefully separated head-specific initialization scales, strong initial attention to a fixed BOS sink, and a specialized stage-wise stopping rule based on attention assignments.

These conditions are not minor technical details. They directly enable the sequential head-specialization mechanism underlying the main theorem. Consequently, the result does not establish that conventional transformers can generally internalize reasoning through ordinary gradient descent.

The negative result for direct training is also restricted to population gradient descent with permutation-invariant initialization, making the claimed separation narrower than the broad motivation suggests.

The experiments do little to address these limitations. They use only small synthetic parity problems with the same fixed multiplicative readout. Under initialization without an explicit BOS preference, performance becomes substantially less reliable, with complete failure in some higher-dimensional settings. The experiments therefore largely confirm behavior within the hand-designed model rather than demonstrate a broadly applicable phenomenon.

Overall, I find the incremental theoretical contribution insufficient relative to the restrictive assumptions and the substantial existing literature.

Questions for authors

1. What is the fundamental conceptual contribution beyond existing theoretical results on ICoT?

Huang et al. (2026) and Tsilivis et al. (2026) already establish provable parity internalization through progressive removal of intermediate reasoning tokens. Beyond replacing linear or modified attention with multi-head softmax attention and eliminating rounding, what new learning principle does the present analysis establish? Can the authors identify a concrete qualitative prediction or theoretical phenomenon that cannot be explained by the previous analyses?

2. How essential are the fixed product readout and carefully constructed initialization?

The model is equipped with the exact multiplicative structure needed to represent parity, while the initialization biases unused heads toward a multiplicative identity and imposes substantial separation between head scales. Can the authors provide theoretical or convincing empirical evidence that the claimed learning mechanism persists when the product readout is learned rather than fixed and when the initialization is not deliberately engineered to facilitate head specialization?

This question is particularly important given the initialization sensitivity reported in Table 4.

3. How should the claimed advantage over direct training be interpreted beyond the symmetric population-gradient setting?

Theorem 2 relies on permutation-invariant initialization and exact population gradient descent, whereas the positive theorem uses a carefully structured curriculum and specialized initialization. Can the authors establish a comparable separation under generic asymmetric initialization and practical finite-sample optimization?

Without such evidence, it is unclear whether the negative result reveals an intrinsic difficulty of direct training or primarily reflects the symmetry of the chosen theoretical setting.

3 comments
AuthorsOpenReview ↗

Author Response (Part 1/2)

We thank the reviewer for the careful assessments and constructive feedback. We appreciate the recognition of our analysis of multi-head interactions, particularly competition among heads and preservation of earlier assignments under ordinary gradient descent. We highlight three contributions and clarifications that address the main concerns raised in the review.

1. Novelty and significance (W1 & Q1).

Our main contribution is a theoretical characterization of the learning dynamics through which a deletion curriculum coordinates specialization across attention heads. Each newly required bit creates a gradient advantage that recruits exactly one idle head. Once that head assigns more than 1/21/2 of its attention to the bit, competitors’ drift reverses toward BOS, while earlier assignments remain stable under continued training (§5). To our knowledge, this is the first theoretical analysis showing how racing dynamics among attention heads enable sequential recruitment and retention under the internalization curriculum.

In the concurrent work of Tsilivis et al. (2026), the within-stage dynamics reduce to convex linear regression within an affine region of the fixed activation, and integer rounding restores an exact prefix representation between stages (Lemma 4). Our proof instead establishes efficient learning by controlling interactions among competing heads and approximate assignments that continue to evolve across stages. In contrast to Tsilivis et al. (2026), our optimization problem is truly non-convex. Despite that, we show that it can be solved in polynomial time. We also show that unfavorable initialization results in failure in learning, as may be expected for a non-convex problem.

Huang et al. (2026) use log k layers, zero padding, prescribed gates and rounding that fixes previously trained layers. We instead analyze fixed depth transformer using literal token deletion, following Deng et al. (2024), and sequential head recruitment within a single attention layer.

Deletion order provides an additional theoretical separation. Deng et al. (§6.2) empirically observed that left-to-right deletion substantially outperforms right-to-left deletion. In our model, left-to-right deletion exposes row 0 to successive prefix targets. Right-to-left deletion instead leaves row 0 learning only z1z_1 until the final deletion. Together, Corollaries 2–3 establish success versus high squared error for dense parity under the stated matched initialization, population GD, and no parameter copying. Tsilivis et al. provide empirical evidence (App. E), but no theorem separating the two deletion orders; Huang et al. do not analyze this comparison. Our theory therefore identifies a precise mechanism through which deletion order changes the available learning signal.

2. Assumptions (W2 & Q2).

The fixed readout is a structural assumption that allows us to isolate the learning of attention assignments. It specifies how head outputs are combined, but does not specify which input bits are relevant. Learning these assignments and preserving them across stages is the optimization problem addressed by Theorem 1. Corollary 2 shows that the same readout does not make direct training succeed under the matched conditions.

Our formulation follows the abstraction of Kim & Suzuki (2025), Huang et al. (2026), and Tsilivis et al. (2026): attention is learned while the feedforward computation is fixed. Specifically, Kim & Suzuki (§2.2) and Huang et al. (§2.2, Defs. 2–3) fix a two-bit parity link; Tsilivis et al. (Eqs. (7) and (23)) fix a piecewise-linear parity activation.

The head requirement is intrinsic to this architecture: Proposition 1 gives Boolean Fourier degree at most HH, so H<kH<k implies population squared error at least 11.

The initialization neither encodes a target-dependent assignment nor requires a handcrafted scale ladder (Corollary 1). The guarantee uses initial BOS preference and equal initial raw-key logits. Propositions 2–3 show why: identical heads cannot specialize, while diffuse random attention can exponentially suppress gradients even for a one-bit target when H=Ω(d)H=\Omega(d).

Internalization can still succeed without the prescribed initialization, but may require more training. With i.i.d. Gaussian logits and no initial BOS bias, doubling the stage budget at d=32,k=8d=32,k=8 raises success from 8/10 to 10/10 (Table 4; App. G.5). This is consistent with Proposition 3, which shows that diffuse random attention can exponentially suppress gradients and slow learning.

AuthorsOpenReview ↗

Author Response (Part 2/2)

3. Scope (W2 & Q3).

Corollary 2 compares the same architecture and initialization under population GD: the curriculum succeeds in polynomial time, while direct training retains high squared error for dense parity. The positive theorem breaks symmetry between heads through different BOS scales; the negative theorem permits these differences and requires symmetry among raw keys within each head.

We also directly test whether the advantage persists after breaking raw-key symmetry and replacing population gradients with finite-data optimization. With independent Gaussian raw-key logits and an initial BOS bias (App. G.1), internalization achieves 100% final-answer test accuracy in all 60 runs, while Direct remains near chance under matched initialization, minibatches, and update budgets (Table 2). Thus, the observed advantage is not confined to exact raw-key symmetry or population gradients. Corollary 2 establishes the theoretical separation under its stated assumptions, while Table 2 provides empirical evidence beyond those assumptions.

In summary, our contribution addresses a question left open by prior internalization guarantees: how gradient descent coordinates competing heads and preserves earlier learning in a coupled, non-convex optimization problem. We prove polynomial-time learning while approximate assignments continue to evolve across stages, without rounding or freezing. The analysis also turns the previously empirical deletion-order effect into a proof that left-to-right deletion succeeds whereas right-to-left deletion fails under matched conditions. These findings explain how the curriculum changes learnability within the same architecture, and the empirical advantage over direct training persists with asymmetric initialization and finite-data optimization. While our analysis uses a simplified transformer model as in prior work, the results advance understanding of the learning dynamics and conditions that make CoT internalization successful.

Dear Reviewer r7NB,

Thank you again for your review. As today is the last day of the discussion period, we wanted to follow up on our response. If anything remains unclear, we are happy to clarify before the deadline. If our responses have addressed your concerns, we would appreciate it if you would consider raising your score.

Best regards,

Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.