acceptodds
Under review as a conference paper at ICLR 2027

Transformers Provably Learn to Internalize Chain-of-Thought

Abstract

Explicit chain-of-thought (CoT) reasoning improves language models' performance, but generating intermediate tokens increases inference cost. Implicit CoT (ICoT) progressively removes those tokens during training, aiming to internalize reasoning without explicitly generating the intermediate steps at inference. We ask whether a transformer can still learn efficiently as intermediate reasoning steps are progressively removed during training. We introduce Log-ICoT, which uses a given hierarchical decomposition of the task into simpler subproblems. The curriculum removes intermediate steps in geometric chunks aligned with the levels of this hierarchy. We establish sufficient conditions under which a simplified -layer transformer trained with Log-ICoT learns -parity, where , using a number of samples polynomial in the input length and training stages. The resulting model predicts in one forward pass rather than generating a linear number of reasoning tokens sequentially. Experiments illustrate layer-wise internalization on parity and demonstrate the curriculum on balanced ListOps and four-digit multiplication with pretrained GPT-2. Log-ICoT attains high answer accuracy with fewer training updates than vanilla ICoT and lower inference latency than explicit CoT.

Primary area:
learning theory
Keywords:
Chain-of-Thought, Implicit Reasoning, Theory of LLMs

Reviews

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

This paper Log-ICoT and shows that a L-layer transformer can provabley internalize the CoT of a 2^L parity tree. The experiment on balanced ListOps and four-digit multiplication with pretrained GPT-2 shows that Log-ICoT attains high answer accuracy with fewer training updates than vanilla ICoT and lower inference latency than explicit CoT.

Critical strengths

Provably shows that a simplified L-layer transformer trained with Log-ICoT learns k-parity, where k = 2^L, using a number of samples polynomial in the input length n and L = log2 k training stages. The experiment on n balanced ListOps and four-digit multiplication further support such claim.

Critical weaknesses

Generalization remains a limit. Experiment only limit to toy dataset rather than general dataset. Also,the method requires the balanced tree, making it hard to generalize to CoT with other structure

Questions for authors
  1. The idea of the Log-ICoT is interesting, but the method is strictly limit to CoT with a balanced tree. I suggest the authors to try the method with other fixed but unbalanced tree.
  2. Could authors futher compare the method on 7 × 7 mult. and 9 × 9 mult., or a deeper tree?
3 comments
AuthorsOpenReview ↗

Response to Reviewer gvvC — Part 1/1

Thank you for suggesting broader task structures and larger-scale experiments.

W1. Limited datasets and balanced-tree restriction

We have expanded the experiments to unbalanced trees and graph-based logical reasoning. On a fixed unbalanced ListOps tree with 16 leaves and depth 6, Log-ICoT achieves 98.0% test accuracy in 48,250 updates, compared with 97.9% in 66,250 updates for token-wise ICoT. This shows that the curriculum can work beyond balanced trees; our response to Q1 describes the setup and how the benefit depends on the amount of parallel computation. Experiments on deeper balanced trees and larger multiplication are still running, as discussed in Q2.

We also added ProsQA, a synthetic logical reasoning benchmark in which natural-language statements describe a directed acyclic graph and the model must find a valid reasoning path through distracting branches (Hao et al., 2024). We provide breadth-first search traces listing all newly reachable nodes at each step and progressively internalize these steps. After full internalization, Log-ICoT achieves 96.2% test accuracy in 22,750 updates, close to explicit CoT's 96.6%. The consolidated table in our shared response reports the results. These experiments broaden the structures considered, while still using synthetic tasks and supplied decompositions. Learning the decomposition and evaluating on broader natural-language reasoning tasks remain future work.

Q1. Fixed unbalanced trees

Following the suggestion, we evaluated a fixed unbalanced ListOps tree with 16 leaves, depth 6, and level widths 6,4,2,1,1,16,4,2,1,1,1. We group computations by node height so that independent nodes can be internalized together. Both methods use GPT-2 Small, 10,000 explicit-CoT updates, a learning rate of 10−410^{-4}, and the same validation-based stopping rule.

From the consolidated table in our shared response, Log-ICoT uses about 27% fewer updates. Its smaller advantage than on balanced D=5 ListOps is consistent with the reduced parallelism: several levels contain only one node, leaving fewer computations to internalize together. In the limiting case of a chain, Log-ICoT removes one reasoning step at a time, matching the token-wise removal order when each step is one token. Greater parallelism allows Log-ICoT to internalize more computations together and reduce the number of curriculum stages.

Q2. Larger multiplication or deeper trees

We have extended Log-ICoT to an unbalanced ListOps tree with depth 6, deeper than the original balanced tree settings, and to ProsQA, a more complex graph-based logical reasoning task expressed in natural language.

Experiments on 8×8 multiplication and balanced ListOps D=6 are still running. We will update the consolidated table with their final test accuracies and training costs once available.

References

Hao, S., Sukhbaatar, S., Su, D., Li, X., Hu, Z., Weston, J., and Tian, Y. (2024; COLM 2025). Training Large Language Models to Reason in a Continuous Latent Space. arXiv:2412.06769.

Thank you for your response. The experiment on unbalanced trees partially addresses my concern. This is an interesting work interesting and I will maintain my original score.

Thank you for your constructive feedback and positive assessment of our work. Our general response presents additional evidence on ListOps with depth 66 and discusses the remaining difficulty with full internalization on 8×8 multiplication. We will continue experimenting to investigate this difficulty. We appreciate your suggestions, which helped us strengthen the experimental evaluation.

Reviewer_Svb2OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies whether a transformer can keep learning efficiently as chain-of-thought tokens are progressively removed during training (implicit CoT). It proposes Log-ICoT, which removes the reasoning trace one level per stage in a hierarchy and replaces removed tokens with zero padding. For k-parity, it proves that a simplified L-layer transformer learns the task with polynomially many samples (Theorem 1). Experiments show layer-wise internalization on parity with the toy model, and on GPT-2 small for balanced ListOps and 4-digit multiplication, where Log-ICoT reaches accuracy close to token-wise ICoT with fewer training updates.

Critical strengths
  • The question (sample-efficient internalization of CoT in multi-layer models) is natural, and the result extends prior one-layer explicit-CoT parity results to the implicit setting
  • The two technical issues, representation collapse from uniform attention and disturbing earlier layers, are clearly explained, and the ablations in Table 2 are informative.
Critical weaknesses
  • The theoretical model is hand-designed around the parity tree. The ablation shows that the gating mechanism central to the analysis is unnecessary once the fixed link is replaced by a learned MLP, which suggests the key difficulty analyzed is an artifact of the fixed link rather than of internalization.
  • The method requires a given hierarchical decomposition and intermediate traces, which limits applicability to the practical ICoT tasks
  • Presentation: the main text is dense and a little hard to follow
Questions for authors
  • How would a decomposition be obtained for tasks without a known tree structure?
4 comments
AuthorsOpenReview ↗

Response to Reviewer Svb2 — Part 1/2

Thank you for the questions about the architectural assumptions, supplied hierarchy, and clarity of the analysis.

W1. Hand-designed architecture and the fixed-link obstacle

We agree that the particular representation-collapse behavior arises from our fixed-link setup. Near-uniform attention averages input signs close to zero, which the link maps close to a constant. Repeated application can then destroy information needed by later layers, and the gate preserves that information. The learned-MLP ablation (Table 4 in the revision) shows that a learned MLP can support internalization without the prescribed gate, so this collapse is not an inherent obstacle for every internalization architecture.

The main technical difficulty is learning attention after intermediate CoT tokens are removed: each new layer must learn from approximate internal representations, while later updates must preserve earlier computations. Our contribution is to establish the gradient signal, error bounds, and stability guarantees that make this stage-by-stage learning possible (Lemmas 8–10). We fix the local parity operation to isolate and analyze these attention dynamics. The tradeoff is that the fixed link makes the gradients tractable to control but introduces the rigidity responsible for the collapse above, requiring the prescribed gates. A learned MLP can adapt its local computation and avoid this particular collapse.

The learned-MLP ablation shows that Log-ICoT can succeed beyond this analytical setup. A trainable MLP can adapt its local computation, but extending the theorem requires tracking its changing outputs and derivatives together with attention. Wen et al. (2024) provide relevant progress on joint attention and MLP learning for a simplified one-layer explicit-CoT model. Extending such analysis to multi-layer internalization is future work, as discussed in our response to M9kd, Q2.

W2. Supplied decomposition and intermediate traces

We agree that requiring a supplied hierarchical decomposition limits the current method's applicability. Intermediate reasoning traces are already used in standard ICoT training, where they are progressively removed. Log-ICoT additionally uses their dependency structure to group computations into curriculum stages. Our new unbalanced ListOps and ProsQA experiments broaden the structures considered. We now state the decomposition requirement explicitly in the introduction and discuss it in Appendix A.2. Please see 6dtd, W1, for the experimental evidence and the shared response, “General reasoning without a known structure,” for broader training directions. Automatically obtaining suitable decompositions remains an open problem.

AuthorsOpenReview ↗

Response to Reviewer Svb2 — Part 2/2

W3. Dense presentation

We have added the following component summary in Appendix B.1, referenced from Section 2.2, and a short proof roadmap immediately after Theorem 1 in Section 3.3.

ComponentLearned or fixed?Role
Positional attention matrices W(1),…,W(L)W^{(1)},\ldots,W^{(L)}LearnedSelect the input bits and intermediate representations to combine.
Positional encodingsFixedIdentify sequence positions.
Value matricesFixedPass the selected representations to the local computation.
Link functionFixedCompute local parity.
GatesFixedControl where each layer writes new computations and preserves existing information.
Block-shift output mapsFixedStore each layer's results in the next residual block.
ReadoutsFixedExtract predictions from the designated residual block.

The fixed components are shared across all secret subsets SS. They specify the computation structure but do not reveal the relevant input indices or set the correct attention weights.

Proof roadmap. The proof proceeds by induction over curriculum stages, maintaining that trained layers attend to the correct children and compute accurate intermediate parities.

  1. Learn the first layer. With intermediate supervision, the gradient distinguishes each node's two children from irrelevant positions. One update followed by quantization trains the first layer (Lemma 7).
  2. Learn from internal representations. At the next stage, removed tokens are replaced by approximate values computed by earlier layers. Lemma 8 characterizes these representations, and Lemma 9 shows that the remaining gradient signal trains the next layer while keeping computation errors small.
  3. Preserve earlier computations. Gradients in previously trained layers are small enough that quantization leaves their weights unchanged (Lemma 10). This allows the induction to continue through all LL stages and yields an accurate final answer without an explicit CoT trace.

Please let us know if any part of the paper remains unclear. We would be happy to clarify it further.

Q1. Obtaining a decomposition without a known tree

Our current method assumes a supplied decomposition, and discovering one for general reasoning tasks remains an open problem. Please see the shared response, “General reasoning without a known structure,” for connections to self-distillation and trace adaptation, and 6dtd, W1 for the scope of the new experiments.

References

Wen, K., Zhang, H., Lin, H., and Zhang, J. (2024; ICLR 2025). From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency. arXiv:2410.05459.

Thanks for the clear explanation which helps me better understand the paper now. I have also checked other review and would like to vote for a weak acceptance. Nice work

Thank you for the positive reassessment. We are glad that our explanations clarified the paper’s contributions and addressed your concerns. We appreciate your careful review and constructive feedback.

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

Unlike explicit CoT, implicit CoT gradually removes intermediate tokens during training to internalize reasoning. Although this framework has achieved empirical success, it remains theoretically unclear whether transformers can make efficient predictions with internalized reasoning. It is also unclear whether more efficient approaches exist than current methods that gradually remove reasoning tokens at a fixed rate.

This work proposes log-ICoT. For tasks that can be solved efficiently using a tree structure, log-ICoT accelerates training by removing intermediate tokens at an exponentially faster rate than vanilla ICoT. The authors theoretically prove that simplified L-layer transformers trained using this approach can learn k-parity with k = 2^L. Experimental results further show that log-ICoT maintains comparable accuracy while requiring lower inference latency than explicit CoT and fewer training updates than vanilla ICoT.

Critical strengths

Log-ICoT provides an efficient approach to ICoT for certain tasks through a simple yet effective method. Specifically, whereas vanilla ICoT removes intermediate tokens at a linear rate, log-ICoT removes them at an exponential rate while achieving nearly the same accuracy. The authors also provide a theoretical guarantee that log-ICoT can learn parity tasks using a polynomial number of training samples. This is a theoretically significant result, even considering the practical limitations discussed below.

Critical weaknesses
  1. The range of tasks for which log-ICoT is effective is limited. First, log-ICoT assumes that the task can be solved efficiently using a balanced tree structure. Such tasks are not always common in practice. Even when a task admits an efficient tree-structured solution, training additionally requires the intermediate results of that solution to be provided as supervision for the transformer. Thus, log-ICoT is effective only for tasks that can be solved efficiently using a balanced tree structure and for which the intermediate results can be obtained easily.
    In this regard, the title also somewhat overstates the scope of the contribution. The authors should make this limitation explicit in the title, as Kim & Suzuki (2024) do. For example: "Transformers Provably Learn Parity with Internalized Chain-of-Thought" or "Transformers Provably Learn Parity by Internalizing Chain-of-Thought."

  2. log-ICoT has a higher inference cost than vanilla ICoT because it retains padding to store intermediate computational results. Indeed, in the 4 × 4 multiplication experiment, the computational cost in GFLOPs is five times that of vanilla ICoT. Although this has little effect on inference speed for the short sequences considered here, it may cause a more pronounced slowdown for longer sequences. Table 3 also includes an experiment without padding, but this slightly increases the number of training updates, diminishing the log-ICoT’s advantage.

Questions for authors

As discussed in the Weaknesses section, this method targets tasks with a specific structure. There are likely relatively few practical settings in which it would work efficiently. Nevertheless, for tasks that can be solved efficiently using balanced binary trees, it provides an exponential improvement in training efficiency over the existing approach. Its theoretical learning guarantee is also a significant contribution. Taking these points into account, I lean slightly toward acceptance. I would like the authors to clarify the issues raised in the Weaknesses section, particularly the general applicability of the proposed method.

Minor

The header “Under review as a conference paper at ICLR 2027,” which should appear at the top of the paper, is missing.

3 comments
AuthorsOpenReview ↗

Response to Reviewer 6dtd

Thank you for recognizing the training-efficiency benefits of Log-ICoT on structured tasks and the significance of its theoretical learning guarantee.

W1. Applicability, intermediate supervision, and title

We have revised the title to "Transformers Provably Learn Parity with Internalized Chain-of-Thought" to state the scope of the theoretical result. The theorem studies a balanced computation tree with intermediate supervision, and our current curriculum requires a supplied decomposition and reasoning trace.

Our new experiments extend the empirical evaluation beyond balanced trees. On unbalanced ListOps, Log-ICoT achieves 98.0% test accuracy in 48,250 updates, compared with 97.9% in 66,250 updates for token-wise ICoT. We also added ProsQA (Hao et al., 2024), a synthetic logical reasoning task involving graphs described in natural language. Using breadth-first search traces that list newly reachable nodes at each step, Log-ICoT reaches 96.2% accuracy after full internalization, compared with 96.6% for explicit CoT. The consolidated table in our shared response reports these results, and gvvC, Q1 discusses how the benefit depends on the amount of parallel computation. These tasks still provide the structure and intermediate supervision needed for training.

For implications for general reasoning tasks without a known structure, please see the shared response, “General reasoning without a known structure.”

W2. Padding overhead and inference cost

The reviewer is right that padding adds inference cost relative to token-wise ICoT. Our existing benchmark of the prescribed 8×8 multiplication inference formats, using GPT-2 Small, demonstrates this as batch size increases: Log-ICoT's latency rises from approximately equal to token-wise ICoT at batch size 1 to 2.85× at batch size 32. Similar batch-1 latency therefore does not imply negligible padding overhead. We have highlighted this result in Section 4.3.

Batch sizeLog-ICoT / token-wise ICoT latencyExplicit CoT / Log-ICoT latency
11.00×26.8×
81.16×22.8×
322.85×10.1×

Log-ICoT retains its latency advantage over explicit CoT in these measurements, including a 10.1× speedup at batch size 32. It processes retained positions together during prefill and avoids sequentially generating the reasoning trace. Our main benefit over token-wise ICoT is fewer training updates, rather than faster inference.

The no-padding variant is a potential empirical direction for retaining level-wise internalization with lower inference cost. It has the same prompt and answer format as token-wise ICoT, matching its inference workload. Our ablation achieves high accuracy without padding but requires more training updates than padded Log-ICoT under the tested schedules. This exposes a useful tradeoff: padding can ease training at the cost of additional inference work. Improving the no-padding curriculum could reduce that training cost. We now note this direction alongside the no-padding discussion in Section 4.3.

Q1. General applicability

Please refer to our response in W1.

Minor comment: ICLR header

Thank you for pointing this out. We have restored the ICLR under-review header in the revised manuscript.

References

Hao, S., Sukhbaatar, S., Su, D., Li, X., Hu, Z., Weston, J., and Tian, Y. (2024; COLM 2025). Training Large Language Models to Reason in a Continuous Latent Space. arXiv:2412.06769.

I thank the authors for their response. In particular, the additional experiments on datasets with unbalanced tree structures and the discussion of the method’s limitations and possible directions for future work address my concerns. Unless the ongoing experiments yield results that substantially contradict the findings reported so far, I intend to maintain my current score.

Thank you for the follow-up. We are glad that the unbalanced-tree experiments and the discussion of limitations and future directions address your concerns. We have provided the latest experimental updates in our general response, including the successful deeper-ListOps results and the remaining difficulty with full internalization on 8×8 multiplication. We will continue experimenting to investigate this difficulty and determine whether changes to the training setup can enable successful internalization.

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

Chain-of-thought lets a model write out intermediate steps (e.g. partial products in multiplication) before combining them, but every step costs tokens. This paper asks whether a Transformer can learn those steps and then internalize them into its weights, so that at inference it answers in one pass. The proposed curriculum, Log-ICoT, views the reasoning process as a binary tree: the model first learns the bottom-level pairwise operations with full CoT, then those tokens are removed and the next level is learned, and so on, for L = log_2 k stages.

The theory studies k-parity with k = 2^L. Theorem 1 gives sufficient conditions (a simplified L-layer attention model with position-only attention, fixed link and gates, an approximate gradient oracle, specified learning rates, and B = Ω(n^{2+ε}) samples per stage) under which one quantized gradient step per stage yields root-prediction error exp(-Ω(n^{ε/16})), with total sample complexity O(n^{2+ε} log n). The proof extends Kim & Suzuki (2024); the key new ingredient is Lemma 10, showing that gradients with respect to already-trained layers are exponentially small, so later stages do not disturb earlier ones. Experiments cover parity (4-layer model), and balanced ListOps and 4x4 multiplication on pretrained GPT-2, comparing explicit CoT, token-wise ICoT, and Log-ICoT in accuracy, number of updates, and latency.

Critical strengths
  1. The question is well chosen and the paper goes beyond "CoT speeds up training": it tries to explain why level-by-level internalization is learnable by gradient descent, with a clean multi-stage guarantee. The mathematical content is substantial. I checked the main induction and the supporting lemmas; the argument is consistent, and Lemma 10 (later stages leave trained layers untouched after rounding) is the genuinely new technical step over Kim & Suzuki (2024).

  2. The curriculum is natural and the empirical section shows it works on tasks beyond parity, including a pretrained GPT-2 on ListOps and multiplication, with attention maps that match the predicted tree structure.

Critical weaknesses
  1. The hard part of the problem is not what gets internalized. Attention depends only on position, not content. From level 3 upward, the children of every internal node sit at fixed positions that do not depend on the secret S; only stage 1 has to discover S, and that stage is exactly the Kim–Suzuki setting. Later stages learn S-independent positional patterns, and the gates and block-shift maps (Eq. 4) hard-wire where each level is written. So the claim that "polynomial sample complexity is preserved under internalization" holds largely by construction, and the theoretical contribution reads as a reworking of prior results inside a fixed scaffold. I am not fully convinced this says much about internalization in general; the paper should state this limitation plainly in Sections 1 and 3.

  2. Distance between theory and practice. (a) The architecture is far from a real Transformer: fixed link function, fixed gates aligned to the known tree, fixed W_V, W_O and readouts, no content attention, one quantized step per stage. The title "Transformers Provably Learn ..." should be more modest. (b) The parity experiment itself departs from the theorem (a different quartic link, 500 Adam steps per stage, no quantization, joint layer updates), so it illustrates the mechanism rather than testing the stated result. (c) The GPT-2 experiments lack a direct-answer (no-CoT) baseline and latent-CoT baselines, and the update-count comparison pairs validation-based early stopping for Log-ICoT against a fixed removal schedule for token-wise ICoT. ListOps and 4x4 multiplication are also too narrow to support claims about complex language reasoning.

Questions for authors
  1. Please state explicitly which parts of the computation are learned from data and which are fixed by the architecture (gates, block shifts, readouts). In particular, do stages 2..L learn anything that depends on S? (Clarification; this affects how I weigh the theoretical contribution.)
  2. Can the guarantee be extended, even partially, to content-dependent attention or to a learned link, given that Table 2 shows a learned MLP link removes the "representation collapse" obstacle?
  3. Could you run the parity experiment under the theorem's actual conditions (degree-8 link, one quantized step per stage) to confirm the mechanism, even at small n?
  4. Please add a no-CoT direct-answer baseline for ListOps and multiplication, and give token-wise ICoT the same early-stopping rule as Log-ICoT, so the update-count comparison is like-for-like.
  5. The proof requires K_n = ⌈n^{ε/16}⌉ ≥ 15, which for ε = 1 needs n on the order of 10^19. Please comment on the regime in which the bound is meaningful.
5 comments
AuthorsOpenReview ↗

Response to Reviewer M9kd — Part 1/3

Thank you for the detailed questions about what the model learns, the theoretical contribution, and the experimental comparisons.

W1. Learned computation versus a fixed scaffold

We agree that stage 1 identifies the relevant input indices and that later stages learn target attention patterns independent of SS. Stage 1 directly uses the learning argument of Kim & Suzuki (2024). However, the analysis for the remaining stages remain non-trivial. Our new analysis asks whether learning remains sample-efficient after intermediate values are removed from the input. This requires analyzing a multi-step curriculum in a multi-layer model. Below we illustrate the challenging part of the analysis in a concrete 44-bit parity example:

Consider four relevant bits among the nn inputs, with S={s1,s2,s3,s4}S=\{s_1,s_2,s_3,s_4\} and

u1=xs1xs2,u2=xs3xs4,y=u1u2.u_1=x_{s_1}x_{s_2},\qquad u_2=x_{s_3}x_{s_4},\qquad y=u_1u_2.

  • Explicit CoT (Kim & Suzuki, 2024). During training, the model receives the correct intermediate tokens u1,u2u_1,u_2 when learning to predict yy. Each prediction requires learning to select and combine two supplied values. At inference, the model generates the intermediate tokens explicitly.

  • The internalization obstacle (Li et al., 2026). Li et al. study CoT compression for parity in a simplified one-layer transformer. They show that removing intermediate steps requires higher-order interactions, whose useful gradient signal weakens relative to finite-sample noise. In the four-bit example, predicting yy directly after removing u1,u2u_1,u_2 requires learning the four-way interaction xs1xs2xs3xs4x_{s_1}x_{s_2}x_{s_3}x_{s_4}.

  • Our analysis. Stage 1 trains the first layer to reconstruct u1,u2u_1,u_2. After these tokens are removed, stage 2 learns to select their approximate internal representations u^1,u^2\hat u_1,\hat u_2 and combine them through the fixed link. Even though the target positions are independent of SS, learning must succeed using approximate representations computed by earlier layers.

The new analysis tracks the approximate hidden states (Lemma 8) and establishes enough gradient signal to learn the next layer's attention pattern while keeping computation errors small (Lemma 9). It also bounds gradients in previously trained layers so that later updates preserve their computations after quantization (Lemma 10). Identifying SS in stage 1 does not establish these properties.

AuthorsOpenReview ↗

Response to Reviewer M9kd — Part 2/3

W2. Theory/practice gap, title, and experimental comparisons

(a) Architecture and scope. We have revised the title to explicitly mention parity. The introduction identifies the theoretical model as a simplified transformer, and Appendix A.1 discusses its architectural and training assumptions. Our experiments with learned components explore settings beyond the current guarantee.

(b) Relation between the parity experiments and the theorem. We agree that the original parity experiments illustrate internalization under practical training settings. We have now added experiments using the theorem's degree-eight link and update procedure: one empirical-gradient step followed by integer rounding at each stage, with all layers updated. Here, nn is the total number of input bits, of which k=16k=16 determine the target parity. The table reports mean test accuracy over three seeds with no CoT at inference. Appendix B.3.1 gives the setup and results; Figure 2 retains the original quartic-link AdamW experiment.

KKn=30n=30646412812825625651251210241024
Kn=⌈n1/16⌉=2K_n=\lceil n^{1/16}\rceil=250.6%50.2%50.1%50.0%49.4%49.6%
151549.8%49.7%100%100%100%100%
6060100%100%100%100%100%100%

The parameter KK controls the update magnitude through the learning rate ηt=Knt2/(2c)\eta_t=Kn_t^2/(2c). The theorem sets Kn=⌈nϵ/16⌉K_n=\lceil n^{\epsilon/16}\rceil and guarantees learning for sufficiently large nn. With ϵ=1\epsilon=1, this gives Kn=2K_n=2 at every tested input size. In these runs, the first update identifies the correct children, but attention remains too diffuse for accurate computation. We therefore also evaluate larger values of KK. Empirically, K=15K=15 achieves 100% test accuracy at the tested sizes n≥128n\ge128, and K=60K=60 achieves 100% at every tested size. These results demonstrate finite-size learning with a larger update scale.

(c) Matched stopping rules, baselines, and task coverage. The consolidated table in our shared response summarizes the results.

  • Matched training. We reran token-wise ICoT and Log-ICoT on ListOps with the same learning rate (10−410^{-4}) and validation-based stopping rule.
  • Additional baselines. We completed no-CoT and Coconut baselines on ListOps D=4/D=5 and 4×4 multiplication, as well as both baselines on unbalanced ListOps.
  • Broader tasks. We added unbalanced ListOps and ProsQA (Hao et al., 2024), a synthetic logical reasoning benchmark that requires finding a valid path through a graph described in natural language. Experiments on 8×8 multiplication and ListOps D=6 are still running. These tasks remain synthetic and use a supplied dependency structure; Appendix A.2 now states this limitation. Please see the shared response, “General reasoning without a known structure,” for further discussion.

Q1. Learned versus fixed components and dependence on S

The trainable parameters are the positional attention matrices W(1),…,W(L)W^{(1)},\ldots,W^{(L)}. The positional encoding, value matrices, link function, gates, block-shift output maps, and readouts are fixed. We fix these components to focus on the central learning difficulty in our setting: learning which inputs and intermediate representations attention should select. The fixed components supply the local parity operation and computation structure, but they are identical for every SS and do not reveal its indices or set the correct attention weights. We have also added a table in Appendix B.1 summarizing each model component, whether it is learned or fixed, and its role, with a pointer from Section 2.2.

Stage 1 learns the relevant input indices and therefore depends on SS. The target attention patterns in stages 2,…,L2,\ldots,L are independent of SS, but must still be learned from approximate representations computed by earlier layers. Please see W1 (Part 1) for the new technical contribution and the four-bit comparison with explicit CoT and Li et al. (2026).

AuthorsOpenReview ↗

Response to Reviewer M9kd — Part 3/3

Q2. Content-dependent attention and learned links

We fix the link to isolate attention learning as intermediate CoT tokens are removed. Positional attention is sufficient for our parity task, but each layer must still select both children using approximate representations, control accumulated errors, and preserve earlier computations. W1 (Part 1) explains how our analysis addresses these challenges.

The learned-MLP ablation (Table 2 in the submission; Table 4 in the revision) highlights a tradeoff: the fixed link simplifies the theoretical analysis but introduces a particular collapse behavior that a learned MLP can avoid. Please see Svb2, W1, for a detailed discussion; Appendix A.1 now summarizes this tradeoff. Extending the guarantee to learned MLPs would require controlling the joint attention–MLP dynamics across internalization stages. Wen et al. (2024) jointly train attention and MLP input weights in a simplified one-layer explicit-CoT model. Extending this approach to multi-layer internalization, and analyzing content-dependent attention for broader reasoning tasks, remain future work.

Q3. Parity experiment under the theorem conditions

Please see W2(b) (Part 2) for the results.

Q4. Direct-answer baselines and matched early stopping

Please see W2(c) (Part 2) for the results.

Q5. Meaningful regime of the theoretical bound

We agree that the theorem's sufficient conditions require extremely large input sizes. Its contribution is an asymptotic polynomial sample-complexity guarantee for internalization, rather than a practical estimate of the input or sample size needed for learning. The large threshold comes from conservative bounds used to control attention concentration and quantized updates. It does not establish that such input sizes are necessary. Kim & Suzuki (2024, Theorems 5 and 7) likewise require a sufficiently large input dimension, denoted nn here. Their analysis uses the same nϵ/16n^{\epsilon/16} scaling to control attention concentration and rounding errors. Our choice of KnK_n provides a more detailed treatment of rounding errors, including possible one-unit differences between child logits, whereas Kim & Suzuki (2024) consider only equal rounded child logits. Sharper finite-size guarantees remain future work.

The experiments in W2(b) (Part 2) show that, for k=16k=16, K=15K=15 achieves 100% test accuracy at the tested sizes n≥128n\ge128, and K=60K=60 achieves 100% at all tested sizes. Although the prescribed Kn=2K_n=2 fails in this range, increasing the update scale enables learning at much smaller input sizes than required by the theoretical bound.

References

Hao, S., Sukhbaatar, S., Su, D., Li, X., Hu, Z., Weston, J., and Tian, Y. (2024; COLM 2025). Training Large Language Models to Reason in a Continuous Latent Space. arXiv:2412.06769.

Kim, J., and Suzuki, T. (2024). Transformers Provably Solve Parity Efficiently with Chain of Thought. arXiv:2410.08633.

Li, J., Li, R., Zhou, Y., Ma, B., and Pan, J. Z. (2026). Chain Of Thought Compression: A Theoretical Analysis. arXiv:2601.21576.

Wen, K., Zhang, H., Lin, H., and Zhang, J. (2024; ICLR 2025). From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency. arXiv:2410.05459.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General response

We thank the reviewers for their careful reading and constructive feedback. Below, we present additional experimental results and discuss the method’s task-structure assumptions and limitations.

We appreciate the reviewers’ recognition of the paper’s main contributions. First, we prove a polynomial sample-complexity guarantee for learning parity with internalized CoT in a simplified multi-layer transformer (M9kd, 6dtd, Svb2, gvvC). Second, the level-wise curriculum needs only logarithmically many stages (6dtd, gvvC). Third, experiments with pretrained GPT-2 support the approach beyond parity (M9kd, 6dtd, gvvC).

1. Consolidated experiment results

Following the reviewers' suggestions, we have:

  • Expanded the tasks. We added unbalanced ListOps to evaluate a tree structure beyond balanced trees (gvvC, Q1), and ProsQA to evaluate graph-based logical reasoning expressed in natural language (M9kd, W2; gvvC, W1). Experiments on balanced ListOps D=6 and 8×8 multiplication are still running and we will update the table once results are available (gvvC, Q2).
  • Added baselines. We added Coconut (Hao et al., 2024), a continuous-CoT method, and filled in missing no-CoT comparisons (M9kd, W2/Q4). Coconut still performs sequential latent reasoning steps at inference. The three methods to the right of the separator predict the answer without generating intermediate reasoning steps.
  • Matched the ListOps training comparisons. We reran token-wise ICoT and Log-ICoT with the same learning rate (10−410^{-4}) and validation-based stopping rule (M9kd, W2/Q4).

Each completed cell reports test accuracy (%) / training updates (×103\times 10^3). Our runs use GPT-2 Small and a single seed, except where noted. Running indicates that completed results are pending.

We will incorporate these additional GPT-2 experiments into the revised manuscript after completing multi-seed runs and the corresponding inference-efficiency measurements.

TaskExplicit CoTCoconut│No-CoTToken-wise ICoTLog-ICoT
ListOps D=499.0% / 3.596.9% / 42│95.6% / 51.2596.4% / 2096.0% / 21
ListOps D=5100.0% / 3.596.0% / 52│98.3% / 157.597.9% / 13496.7% / 33
ListOps D=699.7% / 1098.4% / 38│25.8% / 98Failed97.8% / 43.5
Unbalanced ListOps D=6100.0% / 1097.5% / 57│97.8% / 100.597.9% / 66.2598.0% / 48.25
4×4 multiplication99.9% / 1096.1% / 85│2.0% / 17599.2% / 17598.9% / 55
ProsQA96.6% / 5 [1]97.0 ± 0.3% / — [2]│80% / 45Failed96.2% / 22.75

[1] Explicit CoT achieves 96.6% accuracy in our experiments, compared with 77.5% reported by Hao et al. (2024). This improvement may come from our use of breadth-first search traces listing all newly reachable nodes at each step, instead of single-path traces.

[2] Coconut's ProsQA entry is the paper-reported multi-seed result from Hao et al. (2024, Table 1), with its reported uncertainty. The update count is not reported in the paper.

2. General reasoning without a known structure

Log-ICoT requires intermediate traces, as in standard ICoT, together with a hierarchy whose levels define curriculum stages. In our parity setting, these stages follow the computation tree's levels and respect their dependencies. While in our theoretical model we assume the CoT traces are organized as a balanced tree, the hierarchy need not to be a balanced tree in practice. Our new experiments organize computations by node height on unbalanced ListOps and by breadth-first level on ProsQA graphs. Extending this principle to general reasoning requires both identifying suitable levels and maintaining effective supervision as they are internalized; both remain open. We now state this limitation in the introduction and discuss possible extensions in Appendix A.2.

Identifying candidate levels. Wang et al. (2024) extract nested proof levels using Isabelle, a proof assistant that checks formal proofs and records their structure. Another direction is to infer dependencies from a reference trace: Cabral et al. (2025) construct dependency graphs for proof formalization, and Biju et al. (2025) infer dependencies to organize reasoning steps for parallel execution. These structures could provide candidate levels for an internalization curriculum.

Turning levels into training stages. A structural hierarchy does not by itself determine how much reasoning the model can internalize in one stage. A practical curriculum may therefore need to split a candidate level across several stages, allocate different training budgets, and advance only when validation accuracy recovers.

In this setting, Zhao et al. (2026) use a teacher conditioned on the full reference solution to provide feedback on student-generated responses; such feedback could maintain a learning signal after steps are hidden. Karan et al. (2026) adapt expert traces toward the model's distribution before fine-tuning, which could make the remaining supervision easier to learn during difficult transitions. These approaches could complement an adaptive removal schedule, whose granularity would be determined by the model's progress rather than the candidate structure alone. Developing and evaluating such a curriculum remains future work. We have added this discussion to Appendix A.2.

References

Biju, E., Talaei, S., Huang, Z., Pourreza, M., Mirhoseini, A., and Saberi, A. (2025; NeurIPS 2025). SPRINT: Enabling Interleaved Planning and Parallelized Execution in Reasoning Models. arXiv:2506.05745.

Cabral, R., Do, T. M., Yu, X., Tai, W. M., Feng, Z., and Shen, X. (2025). ProofFlow: A Dependency Graph Approach to Faithful Proof Autoformalization. arXiv:2510.15981.

Hao, S., Sukhbaatar, S., Su, D., Li, X., Hu, Z., Weston, J., and Tian, Y. (2024; COLM 2025). Training Large Language Models to Reason in a Continuous Latent Space. arXiv:2412.06769.

Wang, H., Xin, H., Liu, Z., Li, W., Huang, Y., Lu, J., Yang, Z., Tang, J., Yin, J., Li, Z., and Liang, X. (2024; NeurIPS 2024). Proving Theorems Recursively. arXiv:2405.14414.

Zhao, S., Xie, Z., Liu, M., Huang, J., Pang, G., Chen, F., and Grover, A. (2026). Self-Distilled Reasoner: On-Policy Self-Distillation for Large Language Models. arXiv:2601.18734.

Karan, A., Chen, S., and Du, Y. (2026). Finetuning with Sampling: SFT Learns Better Than You Think. arXiv:2610.02140.

AuthorsOpenReview ↗

Update on the experiment results

We thank the reviewers for their positive feedback on the additional experiments. We are pleased that our responses have addressed many of their concerns. Below, we provide an update on the latest experimental results.

On ListOps with depth 66, Log-ICoT completes all five internalization stages and achieves 97.8% test accuracy in 43,500 training updates. In contrast, token-wise ICoT stops before completing internalization, remaining below the validation threshold after 92,000 total updates. Similarly, on ProsQA, token-wise ICoT completes only 11 of 28 removals before stopping after 129,000 updates, whereas Log-ICoT completes internalization in 22,750 updates with 96.2% test accuracy. These results provide further evidence for Log-ICoT's training efficiency on deeper trees and graph-based reasoning.

On 8×8 multiplication, neither Log-ICoT nor token-wise ICoT has achieved reliable full internalization in our current runs. A possible explanation is that the levels of our recursive arithmetic decomposition differ substantially in learning difficulty: higher levels involve wider intermediate values and carry dependencies. This suggests that a valid hierarchy alone may not provide manageable internalization stages. Finer subdivisions or additional training signals may help, as discussed in Section 2, General reasoning without a known structure.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.