Self-Verifying Reflection Helps Transformers with CoT Reasoning
Authors: Zhongwei Yu
Wannian Xia
Xue Yan
Bo XU
Haifeng Zhang
Yali Du
Jun Wang
Venue: NeurIPS 2025 poster ()
Keywords: chain-of-thought
reasoning
reflection
verification
transformer
Primary area: deep_learning
TL;DR: Transformers can learn self-verifying reflection without language, and reinforcement learning enhances performance through shallow statistical patterns.

Abstract: Advanced large language models (LLMs) frequently reflect in reasoning chain-of-thoughts (CoTs), where they self-verify the correctness of current solutions and explore alternatives. However, given recent findings that LLMs detect limited errors in CoTs, how reflection contributes to empirical improvements remains unclear. To analyze this issue, in this paper, we present a minimalistic reasoning framework to support basic self-verifying reflection for small transformers without natural language, which ensures analytic clarity and reduces the cost of comprehensive experiments. Theoretically, we prove that self-verifying reflection guarantees improvements if verification errors are properly bounded. Experimentally, we show that tiny transformers, with only a few million parameters, benefit from self-verification in both training and reflective execution, reaching remarkable LLM-level performance in integer multiplication and Sudoku. Similar to LLM results, we find that reinforcement learning (RL) improves in-distribution performance and incentivizes frequent reflection for tiny transformers, yet RL mainly optimizes shallow statistical patterns without faithfully reducing verification errors. In conclusion, integrating generative transformers with discriminative verification inherently facilitates CoT reasoning, regardless of scaling and natural language.

Self- Reflection Helps Transformers with CoT Reasoning
Zhongwei Yu Wannian Xia?, Xue Yan', Bo Xu², Haifeng Zhang?, Yali Du , Jun Wang'
The Hong Kong University of Science and Technology (Guangzhou) Institute of Automation, Chinese Academy of Sciences King's College London University College London zyu9508connect.. hkust-gz. edu. cn.
(xiawannian2020 yanxue2021, xubo, haifeng wanng.zhngg@@ia. att.g//iaaac...... acaaaaccoo cn.cn, yali pali.cu0kcl.. ac. uk, jun. wangdcs ucl ac uk
Abstract
Advanced large language models (LLMs) frequently reflect in reasoning chain- of-thoughts (Co'ss), where they self-verify the correctness of current solutions and explore alternatives. However, given recent findings that LLMs detect limited errors in CoTs, how reflection contributes to empirical improvements remains unclear. To analyze this issue, in this paper, we present minimalistic reason- ing framework to support basic self-verifyngg reflection for small transformers without natural language, which ensures analytic clarity and reduces the cost comprehensive experiments. Theoretically, we prove that self-verifying reflection guarantees improvements if verification errors are properly bounded. Experimen- tally, show that tiny transformers, with only few million parameters, benefit from self-verification in both training and reflective execution, reaching remarkable LLM-level performance in integer multiplication and Sudoku. Similar LLM results, we find that reinforcement learning (RL) improves in-distribution perfor- mance and incentivizes frequent reflection for tiny transformers. yet RL mainly optimizes shallow statistical patterns without faithfully reducing verification errors. In conclusion, integrating generative transformers with discriminative verification inherently facilitates CoT reasoning, regardless of scaling and natural language.
Introduction
Numerous studies have explored the ability of large language models (LLMs) reason through chain thought (CoT)) an intermediate sequence leading to the final answer. While simple prompts [13). subsequent works have further enhanced CoT quality through reflective
elicit CoT reasoning
thinking [10] and the use of verifiers 4 Recently, reinforcement lcarning (RL) 33 has achieved notable success in advanced reasoning models, such OpenAl-ol (20) and Deepscek-RI (5), which show frequent reflective behaviors that self-verify the correctness of current solutions and explore alternatives, integrating generative processes with discriminative inference. However, researchers also report that the ability of these LLMs to detect errors is rather limited, and large portion of reflection fails to bring correct solutions (IT). Given the weak verification ability, the experimental benefits of reflection and the emergence of high reflection frequency in RL require further explanation.
To address this challenge, seek to analyze main questions in this paper: what role self- verifying reflection plays in training and execution of reasoning models, and 2) how reflective reasoning evolves in RL with verifiable outcome rewards [15). However, the complexity of natural language and the prohibitive training cost of LLMs make it difficult to draw clear conclusions from theoretical abstraction and comprehensive experiments across settings. Inspired by Zeyuan al.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

2]. we observe that task-specific reasoning and self-verifying reflection do not necessitate complex language. This allows us investigate reflective reasoning through tiny transformer models (36). which provide efficient tools to understand self-verifying reflccion through massive experiments.
To enable tiny transformers to produce long reflective CoTss and ensure analytic simplicity, introduce minimalistic reasoning framework, which supports essential reasoning behaviors that are operable without natural language. In our study, the model self-verifies the correctness of each thought step; then, it may resample incorrect steps or trace back to previous steps. Based on this framework, we theoretically prove that self-verifying reflection improves reasoning aceuracy verification errors are properly bounded, which does not necessitate strong verifier. Additionally, a rrace-back mechanism that allows revisiting previous solutions conditionally improves performance if the problem requires sufficiently large number of steps.
Our experiments evaluate 1M, 4M, and 16M transformers in solving integer multiplication 7 and Sudoku puzzles ( which have simple definitions (thus, operable by transformers without language) yet still challenging for even LLM solvers. To maintain relevance broader LLM research, the tiny transformers are trained from scratch through pipeline similar to that of training LLM reasoners. Our main findings are listed as follows: 1) Learning to self-verify greatly facilitates the learning of forward reasoning. 2) Reflection improves reasoning accuracy if true correct steps are not excessively verified incorrect. 3) Resembling the results of DeepSeek- R1 [5], RL can incentivize reflection if the reasoner can effectively explore potential solutions. 4) However, RL fine-ture tne-tuning increases performance mainly statistically, with limited improvements in generalizable
sooollem-soviigggg skills.
Overall, this paper contributes to the fundamental understanding of reflection in reasoning models by clarifying its effectiveness and synergy with RL. Our findings based minimal reasoners imply general benefit of reflection for more advanced models, which operate on a super-set of our simplified reasoning behaviors. In addition, our implementation also provides insights into the development of computationally efficient reasoning models.
2
Related works
CoT reasoning Pretrained LLMs emerge the ability produce CoTs from simple prompts 13
38). which can be explained via the local dependencies (25) and probabilistic distribution [35 of
natural- reasoning. Many recent studies develop models targeted at reasoning, e.g., scaling
test-time inference with external verifiers 4 17 18 32] and distilling large general models to smaller
specialized models (34] 9. In this paper, we train tiny transformers from scratch not only generate Co'Ts but also self-verify, y, i.e., detect errors in their own thoughts without external models.
recently emerges as key method for CoT reasoning 31 40). It optimizes the transformer model by favoring CoTs that yield high cumulated rewards, where PPO [29] and its variant GRPO (3T] are two representative approaches. Central to RL fine- tuning are reward models that guide policy optimization: the 1) outcome reward models (ORM) assessing final answers, and the 2) process reward models (PRM) (17) evaluating intermediate
RL fine-tuning for CoT reasoning RL 33
reasoning steps. Recent advances in RI. with verifiable rewards (RLVR) [5 41 demonstrate that
simple ORM based solely on answer correctness can induce sophisticated reasoning behaviors.
Reflection in LLM reasoning LLM reflection provides feedback to the generated solutions 19 and may accordingly refine the solutions [10). Research shows that supervised learning from verbal reflection improves performance, even though the reflective feedback is omitted during execution [42]. Compared to the generative verbal reflection, self- velf-veriiication uses discriminative labels to indicate the correctness of reasoning steps, which supports reflective execution and is operable without linguistic knowledge. Recently, RL widely used to develop strong reflective abilities [14] 20) In particular, DeepSeek-R -R1 1 (5) shows that RLVR elicits frequent reflection, and such a result is reproduced in smaller LLMs [24]. In this paper, we further investigate how reflection evolves during RLVR by examining the change of verification errors.
Understanding LLMs through small transformers Small transformers are helpful tools to understand LLMMs, for their architectural consistency with LLMs and low development cost to support massive experiments. For example, transformers smaller than IB provide insights into how data They also contribute to foundational
mixture and data diversity influence LLM training 39 2]

---

Model
R, (Su)
nt. 15,)
A x(: 15y-1)
Ressoning Steps
R1
R2
R
State Transition
Sp
- ((So.R.)
S2
R3)
...
Sy
22
Sy =
(S
Figure I: The illustration MTP, where the transformer model n reasons the answer query Q through T intermediate steps.
St
Se+1
Rr+1
St
R R++1
S
Collaz +
3
2
3
145
340 300
T
145
Cellyu <-
T
9
x310
145 x 580
x300
47
250
290 5800 6090
6090
86
816
9
9
3
8
(a) Multiplication
(b) Sudoku
Figure Example reasoning steps for multiplication and Sudoku, where the core planning is presented in the reasoning step R++1.
understanding of CoT reasoning, such as length generalization 112] and how CoT's inherently extend the problem-solving ability [8] In this paper, further tiny transformers to better understand reflection in CoT reasoning.
internalization of thoughts [6],
Reflective reasoning for transformers
In this section, we develop transformers to perform simple reflective reasoning in long CoTs. Focusing on analytic clarity and broader implications, the design our framework follows the minimalistic principle, providing only essential reasoning behavior operable without linguistic knowledge. More advanced reasoning frameworks optimized for small-scale models are certainly our next move in future work. In the following, based on this formulation, we introduce our simple reasoning framework for self-verifying reflection; afterwards, describe how transformers trained to reason through this framework.
first introduce the basic formulation of CoT reasoning; then,
3.1 Reasoning formulation
CoT Reasoning as Markov decision process
general form of CoT reasoning is given
tuple (Q, {R}, A), where Q is the input query, {R} (Ri..... RT-1) -1) is the sequence of T
intermediate steps, and is the final answer. Following Wang [37], we formulate the CoT reasoning
as Markov thought process (MTP). As shown in Figure [ an MTP follows that [37]
Re+1 ~ ( St). S T(S., Re+1),
where S, is the (-th reasoning state, is the planning policy (the transformer model), and T is the (usually deterministic) transition function. The initial state So == Q given by the input query. In each reasoning step Re+1, the policy plans the next reasoning action that determines the state transition, which then executed by T to obtain the next state. The process terminates when the step presents the answer, i.e., A = Rr. For clarity, table of notations is presented in Appendix A
An MTP implemented by specifying the state representations and transition function T. Since use tiny transformers that are weak in inferring long contexts, we suggest reducing the length of state representations, that each state S, carries only necessary information for subsequent reasoning. Here, we present two examples to better illustrate how MTPs are designed for tiny transformers.
Example (An MTP for integer multiplication). As shown in Figure 2(a) to reason the product of two integers z, 2 0, each state is expression S; == [ay X 21] mathematically equal to
initialized as 5n = [ar x 0]. On each step, æ plans //++1 1 by eliminate a non-zero digit in y to 0, and Tx(1: 1.+ Consequently, T updates S.+1 as [ x y++1 + z++1]
it then computes 1 with F = It. Similarly, æ may also eliminate non-zero digits in 2; in a symmetric manner. Finally, yields A as the answer if either z; or yt becomes 0.

---

R1X
R
R2x
R4
5. -5
54
Ry.K
Ra.
Ra,
5.5
4-9
10% Rg)
R2
Rgi
A.V
Re. v
Rs,
A.v
- (2),
% (,700%
Xa-16s.A)
(a) Reflective MTP
(b) Reflective trace-back search (width m 2)
Figure 3: Reflective reasoning based on MTP. "V" and "x" are self-verification labels for positive and negative steps, respectively. The steps that are instantly verified negative are highlighted in red. In RTBS, the dashed-line arrows back pack-propagate the negative labels, causing parental steps to be recursively rejected (orange). The green shows the steps that successfully lead to the answer.
Example (An MTP for Sudoku (3)) As shown in Figure 2(b) each Sudoku state a x game board. On each step, the model x fills some blank cells to produce new board, which is exactly the next state. The answer a board with no blank cells.
3.2 The framework of self- self-verifying reflection
Conceptually, reflection provides feedback for the proposed steps and may alter the subsequent reasoning accordingly. Reflection takes flexible forms in natural language (e.g., justifications and comprehensive evaluations), making it extremely costly to analyze. this work, we propose to equip transformers with the simplest discriminative form of reflection, where the model self-verifies the correctness of each step and is allowed to retry those incorrect attempts. We currently do not consider find learning such
the high-level revisory behavior that maps incorrect steps to correct ones, mapping is challenging for tiny models and leads to no significant gain in practice. Specifically, we the reflective MTP and the reflective
analyze two basic variants of reflective reasoning this paper: trace-back search, as described below (see pseudo-code in Appendix D.I
verifier V to produce a verification sequence after each reasoning step, denoted as V V(-)R,). Such V includes verification label(s): The positive "V" and negative "x" signifying correct and incorrect reasoning of Rú, respectively. Given the verified step Re+1 (Re+1, V4+1) that contains verification, define T as the reflective transition function that rejects incorrect steps:
Reflective MTP (RMTP) Given any MTP with policy and transition T,
Se: S T(,, Re+1) T(e,, (Re+1, Vz-1)) T(S Re+1), otherwise.
"x" V++1;
(2)
In other words, if V detects any error (i.e. "x") in Re+1, the state remains unchanged so that may re-sample another attempt. Focusing on self-verification, we use single model called the self-verifying policy == { V} serve simultaneously the plamning policy and the verifier V. By operating tokens, स outputs the verified step RG for each input state S.. In this way, T and constitute new MTP called the RMTP, with illustration in Figure 3(a)
Reflective trace-back search (RTBS) Though RMTP allows instant rejections of incorrect steps, sometimes the quality of a step can be better determined by actually trying it. For example, a Sudoku solver occasionally makes tentative guesses and traces back if the subsequent reasoning fails. Inspired by ol-journey [26). a trace-back search allowing the reasoner to revisit previous states may be applied explore solution paths
MTP. We implement simple RTBS by simulating the depth-first search in the trajectory space. Let m denote the RTBS width, i.c., the maximal number of attempts on each step. As illustrated in Figure (bb) proposed steps are rejected on state S,, the negative label "x" will be propagated back to recursively reject the previous step RG, As result, the state traces back the closest ancestral state that has remaining attempt opportunities.
3.3 Training
As shown in Figure we train the tiny transformers from scratch through consistent techniques of LLM counterparts, such pretraining, supervised fine-tuning (SFT), and RL fine-tuning, First,

---

Col examples
Rg
Fg
MIP
OUT excemples (chite mixtune)
Trsining Ddla
R
R
contect windows
trandomly drawa)
(1 Pretraining
Rg
RMIP
y
sampling Cal's through MTP
π
S = 5 (S B. Mp.Kk
Expest Verfler
stegs
Reward Model
Policy Optimization
:
(S
(IT) Non-reflective
startes & strps
ground truth verification
SFT
(IV) RL fine-tuning
(III) ReflectiveSFT
Figure The training workflow for transformers to perform CoT reasoning.
use conventional pipelines to train a baseline model æ with only the planning ability in MTPs. During (I) pretraining, these CoT examples are treated textual corpus, where sequences are randomly drawn to minimize cross-entropy loss of next-token prediction. Then, in (II) non-reflective SFT, the model learns to map each state S, to the corresponding step Re+1 by imitating examples.
Next, we employ (III) reflective SFT to integrate the planning policy æ with the knowledge of sample non-reflective CoTs,
self-verification. To produce ground-truth verification labels, we in which the sampled steps are then labeled by an expert verifier (e.g., a rule-based process reward model). Reflective SFT learns predict these labels from the states and the proposed steps, i.e., (St, Rv+1) V4+1- To prevent disastrous forgetting, we also mix the same CoT examples as in non-reflective SFT. This converts π to a self-verifying policy के that can self-verify reasoning steps.
Thus far, we have obtained the planning policy π and the self-veri policy म,, which can be further strengthened through (IV) RL fine-tuning. As illustrated in Figure 4 RI fine-tuning involves iteratively executing æ (#) to collect experience Co'Ts through an MTP (RMTP), evaluating these CoT's with reward model, and updating the policy favor higher-reward solutions. Following the RLVR paradigm [15.. we use binary outcome rewards (i.e., for correct answers and 0 otherwise) computed by rule-based answer checker ORM(Q, A). When training the self-verifying policy म. the RMTP treats verification Vi as part of the augmented step Rg, simulating R1-like training
[5] where reflection and solution planning are jointly optimized. We mainly use GRPO 31 as the algorithms to optimize policies. Details RI. fine-tuning are elaborated in Appendix B
Theoretical results
This section establishes theoretical conditions under which self-verifyin reflection (RMTP or RTBS
Section 3.22 enhances reasoning accuracy (the probability of deriving correct answers). The general relationship between the verification ability and reasoning accuracy (discussed in Appendix [C.1) for any MTP intractable as the states and transitions can be arbitrarily specified. Therefore, to derive interpretable insights, we discuss simplified prototype of reasoning that epitomizes the representative principle CoT's - incrementally express complex relations by chaining the local relation in each step [25) Specifically, Given query Q as the initial state, we view a CoT as the step-by-step process that reduces the complexity within states:
We define S, as the set of states with complexity scale of n. For simplicity, we assume that each step, if not rejected by reflection, reduces the complexity scale by 1. Therefore, the scale is the number of effective steps required to derive an answer.
An answer A is state with scale of 0, ie. A E Sg. Given an input query Q, the answers So divided into positive (correct) answers S and negative (wrong) answers S
States S, (n > 0) are divided into 1) positive states S that potentially lead to correct answers and negative states S, leading to only incorrect answers through forward transitions.
Consider self-verifying policy म {T,, V) to solve this simplified task. We describe fundamental abilities using the following probabilities (whose meanings will be explained afterwards):
5

---

1
1n-1
5 1++1
Sn
S 1ー11
(1 (1-pee
Sn
S+
5n+
8
MCI
After attempts RTBS
pic. (1 --0(1-e) e.)
(a) Non-reflective reasoning
(b) Reflective reasoning through an RMTP or RTBS
Figure 5: The diagram of state transitions starting from scale n the simplified reasoning, where probabilities are attached to solid lines. In (b) reflective reasoning, the dashed-line arrow presents the trace-back move after m attempts in RTBS.
# == (T), E S 1
(3)
e+ V ((S, Sū-1, "x" S Stt,,
(4)
e_ = PR.V RT) St-1;"" "x" VISE S
(5)
p== E SES,
(6)
To elaborate, a measures the planning ability, defined as the probability that plans step that leads to positive next state, given that the current state is positive. For verification abilities, we measure the rates of two types of errors: e++ (false positive rate) is the probability of accepting step that leads to a negative state, and e. (false negative rate) is the probability of rejecting step that leads to a positive state. Additionally, f is the probability of rejecting any step on negative states, providing the chance of tracing back to previous states, Given these factors, Figure 5 illustrates the state transitions in non-reflective (vanilla MTP) and reflective (RMTB and RTBS) reasoning.
For input problems with scale nt, we use p(n), p(n), and (m) to respectively denote the reasoning accuracy using reflection, RMTP, and RTBS (with width m). Obviously, we have p(n) = n². In contrast, the mathematical forms of p(n) and imm (n) are more complicated and therefore left to Appendix C.2, Our main result provides simple conditions for the above factors (H, e,, 64, f) to ensure an improved accuracy when reasoning through an RMTP or RTBS.
Theorem 1. In the above simplified problem, consider a self-verifying policy where p., e., and e.- e4) denote the rejection probability
non-trivial (i.e. neither 0 nor 1). Let == μe- (11 on positive states. Given an infinite computation budget, for n > we have;
p(n) 2 p(n) if and only e__ + e. S L, where equalities hold simultaneously; furthermore, reducing either e. or e. strictly increases p(n).
Pm (n) > p(n) for sufficiently large if and only if and m > - furthermore, such gap of pm (n) over p(n) increases strictly with f-
Does reflection require strong verifier? Theorem shows that RMTP improves performance over vanilla MTP if the verification errors e+ and e are properly bounded, which does not necessitate a strong verifier. In simplified setting, this only requires the verifier V be better than random guessing (which ensures e + e+ = 1). This also indicates a trivial guarantee of RTBS, as an infinitely large width (m + +oo) substantially converts RTBS to RMTB.
When does trace-back search facilitate reflection? Theorem i provides the conditions for RTBS to outperform RMTP for sufficiently large n: 1) The width is large enough to ensure effective exploration. 2) f > a indicates that negative states are inherently discriminated from positive ones, negative states than on positive states (see Figure 5b)). In
leading to higher rejection probability other words, provided f > a, RTBS is ensured to be more effective on complicated queries using a finite However, this also implies a risk of over-thought simple queries that have small n.
The derivation and additional details of Theorem [ are provided in Appendix also derive how many steps it costs to find correct solution in RMTP. The following Proposition [ (see proof in Appendix C.4b shows that a higher e.. causes more steps to necessarily rejected and increases the solution cost. In contrast, although a higher e4. reduces accuracy, it forces successful solutions to rely less on reflection, leading to fewer expected steps. Therefore, high false negative rate e_ is worse than high e given the limited computational budget in practice.
In addition, we

---

Easy
ID Hard
OOD Hard
100
Venfication
Azcuracy (%)
75
Type
None
Binary
50-
Detailed
25-
1M
4M
16M
1M
4M
16M
LM
4M
16M
Model
Size
Figure 6: The accuracy of non-reflective execution of models in Mult. In each group, compare training with various types of verification ("None" for no reflective SFT).
Proposition (RMTP Reasoning Length), For a simplified reasoning problem with scale n, the expected number of steps T for मे to find a correct answer is T -1- (2-w)e=t((-ee_)" Especially, correct answer will never be found if the denominator is
Appendix C.5 further extends our analysis to more realistic reasoning, where rejected attempts lead posterior drop of ys (or rise of e-), indicating that the model may not well generalize the current state. In this case, the bound of e_ to ensure improvements becomes stricter than that in Theorem
5 Experiments
We conduct comprehensive experiments to examine the reasoning performance of tiny transformers under various settings. We trained simple -uttntnnt transformers (36) (implemented LitGPT
1 with IM, 4M, and 16M parameters, through the pipelines described in Section 3.3 Details of training data, model architectures, tokenization, and hyperparameters included in Appendix D The source code is available at uttttps://ggithue com/ httpa////////aaa///e/eee///////e wlseell
We test tiny transformers in two reasoning tasks: The integer multiplication task (Mult for short) computes the product of two integers x and y, the Sudoku task fills numbers into blank positions of 9 x 9 matrix, such that each row, column, or 3 x 3 block is permutation of f1.....9 .9). For both tasks, we divide queries into levels of difficulties: The in-distribution (ID) Easy, ID Hard, and out-of-distribution (OOD) Hard. The models while tested additionally on OOD-Hard cases. We define the difficulty of a Mult query by the number d of digits of the greater multiplicand, and that of Sudoku puzzle is determined by the number b of blanks to be filled. Specifically, we have S d & 5 or 9 < < 36 for ID Easy, s d < 8 or 36 < Our full results are presented in Appendix Shown in Appendix E. these seemingly simple tasks pose challenges even for some well-known LLMs. Remarkably, through simple self-verifyin reflection, our best 4M Sudoku model is as good as OpenAl 03-mini [2I), and our best 16M Mult model outperforms DeepSeck-RI [5] in ID difficulties.
trained ID-Easy and ID HD-Hard problems,
54 for ID Hard, and
10 or 54
63 for OOD Hard.
5.1 Results of supervised fine-tuning
First, we conduct (I) pretraining, (II) non-reflective SFT, and (III) reflective SFT as described in Section 3.3 In reflective SFT, consider learning two types of self-verification: 1) The binary verification includes a single binary label indicating the overall correctness of a planned step; 2) the detailed verification includes series of binary labels checking the correctness of each meaningful element in the step. The implementation of verification labels is elaborated in Appendix [.2.3] We present our full SFT results in Appendix E.2 which includes training 30 models and executing 54 tests. In the following, we discuss our main findings through visualizing representative results.
Does learning self-verification facilitate learning the planning policy? We compare our models under the non-reflective execution, where self verificaion is not actively used in time. As shown in Figure 6 reflective SFT with binary verification brings remarkable improvements for 1M and 4M ID-Easy and ID-Hard Mult problems, greatly reducing the gap among model sizes. Although detailed verification does not benefit as much binary verification in ID problems, it significantly benefits the 16M model in solving OOD-Hard problems. Therefore, learning to self-verify benefits the learning of forward planning, increasing performance even test-time reflection is not enabled.
7

---

Mult ID-H
Mult ID-Hard Detailed Verification
Sudoku ID-Hard Binary Verification
Sudoku ID-H
Binary Verification
Detailed Verification
40
Reflecive
Exceution
60
Nonr
Accurccy
RMTF
40
Ector Metries
40-
DOO
RTBS e-
4M
16M
1M
4M
16M
4M
16M
IM
4M
16M
Model Size
Model Size
Model Size
Model Size
Figure 7: Performance of reflective execution methods across different model sizes, including the accuracy (top) and the self-verification errors (bottom).
Since reflective SFT mixes the same CoT examples as used in non-reflective SFT, an explanation for this phenomenon is that learning to self-verify serves regularizer the planning policy. This substantially improves the quality of hidden embeddings in transformers, which facilitates the learning of CoT examples. Binary verification is inherently harder target learn, which produces stronger regularizing effects than detailed verification. However, the complexity (length) of the verification should match the capacity of the model; otherwise, could severely compromise the benefits of learning self-verification. For instance, learning binary verification and detailed verification fails to improve the 16M model and the IM model, respectively.
When do reflective executions improve reasoning accuracy? Figure the non-reflective, RMTP, and RTBS executions for models in solving ID-Hard problems. Apart from the accuracy, the rates of verification error (i.e., the false positive rate e and false negative rate e defined in Section 4 measured using oracle verifier. In these results, RMTP reasoning raises the performance over non-reflective reasoning except for the IM models (which fail in ID-hard Sudoku). Smaller error rates (especially e-) generally lead to higher improvements, whereas high e in binary verification severely compromises the performance of the IM Mult Model. Overall, reflection improves reasoning the chance of rejecting correct steps (e_) is sufficiently small.
In what task is the trace-back search helpful? As seen in Figure 7 though RTBS shows no advantage against RMTP in Mult, it outperforms RMTP in Sudoku, especially the 4M model with detailed verification. This aligns with T The state of Sudoku (the 9 x matrix) is required to comply with explicit verifiable rules, making incorrect states easily discriminated from correct states. However, errors Mult states can only be checked by recalculating all historical steps. Therefore, we more likely to have f > in Sudoku, which grants higher chance of solving harder problems. This suggests that RTBS can be more helpful than RMTP if incorrect states in the task carry verifiable errors, which validates our theoretical results.
5.2 Results of reinforcement learning
As introduced in Section 3.3 further apply GRPO to fine-tune the models after SFT. Especially, GRPO based on RMTP allows solution planning and verification to be jointly optimized for self- verifying policies. The full GRPO results are presented in Appendix [E.3] and the main findings are presented below. Overall, RL does enable most models to better solve ID problems, yet such improvements arise from superficial shift in the distribution of known reasoning skills.
How does RL improve reasoning accuracy? Figure & presents the performance of 4M and 16M models in Mult after GRPO, where the differences from SET results visualized. GRPO effectively enhances accuracy in solving ID-Hare problems, yet the change in OOD performance is marginal. Therefore, RL can optimize ID performance, while failing to generalize 0OD cases.
Does RL truly enhance verification? From the change of verification errors Figure X we find that the false negative rate decreases along with increase in the false positive rate e4. This suggests

---

Mult ID-Hard (4M)
Mult OOD-Hard (4M)
Mult ID-Ilard (16M)
Mult OOD-Hard (16M)
50
Reflextive
Accunsyy (50
Nonr
RNTT KITRS
40
(%6
75
Error Metrics IMIE
50-
IMTT e.
RTBS e
F
Binory Detailed
Binory
Detailed
Binary
Detailed
Binary
Detailed
Verification Type
Verification Type
Verificution Type
Verification Type
Figure 8: Performance of the 4M and 16M models in Mult after GRPO, including accuracy and the verification error rates. As an ablation, we also include non-reflective models. The vertical arrows start from the baseline accuracy after SFT, presenting the relative change caused by GRPO.
that models learn optimistic bias, which avoids rejecting correct steps through a high false positive rate that bypasses verification. In other words, instead of truly improving the verifier (where e.. and e. both decrease). RL mainly induces an error-type trade-off. shifting from false negatives (e4) to false positives (e-).
To explain this, note that a high raises the computational cost (Proposition D and thus causes a significant performance loss under the limited budget of RL sampling, making reducing e more rewarding than maintaining low e+. Mcanwhile, shifting the error type is easy to learn, achievable by adjusting only a few parameters in the output layer of the transformer.
Inspired by DeepSeek-RI R1 [5], we additionally examine how RL influences the frequency of reflective behavior. To simulate the natural distribution of human reasoning, we train models to perform optional detailed verification by adding examples of emply verification (in the same amount as the full verification) into reflective SFT. This allows the policy to optionally omit self-verification, usually with higher probability than producing full verification, since empty verification is easier to learn. Consequently, we can measure the reflection frequency by counting the proportion of steps that include non-empty verification. Since models can implicitly omit binary verification by producing false positive labels, we do not explicitly examine the optional binary verification.
When does RL incentivize frequent reflection? Figure 9 shows reflection frequency in Mult before and after GRPO, comparing exploratory (1.25) and exploitative (1) temperatures when sampling experience CoTSs With a temperature 1.25, GRPO elicits frequent reflection, especially on hard queries. However, reflection frequency remains low if using temperature 1. Additional results for other model sizes and Sudoku appear in Appendix E.3.3 In conclusion, RL can adapt reflection frequency to align with the exploratory ability of the planning policy म, encouraging more reflection if the policy can potentially explore rewards. This helps explain why RL promotes frequent reflection LLMs [5. as the flexibility of language naturally fosters exploratory reasoning.
6 Conclusion and Discussion
In this paper, we provide a foundational analysis of self-verifyngg reflection in multi-step CoTs using small transformers. Through minimalistic prototypes of reflective reasoning (the RMTP and RTBS), we demonstrate that self-verificatio benefits both training and execution. Compared to natural-language reasoning based on LLMs, the proposed minimalistic framework performs effective reasoning and reflection using limited computational resources. We also show that RL fine-tuning can enhance the performance in solving in-distribution problems and incentivize reflective thinking for exploratory reasoners. However, the improvements from RI. rely on shallow patterns and lack generalizable new skills. Overall, we suggest that self-verifying reflection is inherently beneficial for CoT reasoning, yet its synergy with RL fine-tuning is limited in superficial statisties.

---

After GR
After GRPO
Before GRPO
Temperature: 1.25
Temperature: 1.0
14
20
51
49
48
52 47
14
13
6
16
2
4
0
210
of
13
515
5/3
number of
21
2
m1s
rb
12
400
10
79
20
number of x's digits
number of x's digits
number of X'S digits
Figure 9: The hot-maps of reflection frequencies of the 4M transformer in multiplication before and after GRPO using temperatures 1 and 1.25, tested with RMTP execution. The i-th row and j-th column shows the frequency (%) for problems r x y where x has j digits and y has digits.
Limitations and future work Although the current training pipeline enables tiny transformers to reason properly through reflective CoT's, the generulization ability is still low and not improved in RL. Therefore, future work will extend reflection frameworks and explore novel training approaches. Observing the positive effect of learning self-verification, closer connection between generative and discriminative reasoning may be the key to addressing this challenge. Additionally, how our findings transfer from small transformers to natural- nnsturallanguggee LLMs needs to be further examined. However, the diversity of natural language and high computational cost pose significant challenges to comprehensive evaluation, and our proposed framework does not sufficiently exploit the emergent linguistic ability LLMs. To this end, we expect to investigate more flexible self-verification framework with an efficient evaluator of natural-language reflection in future work.
Acknowledgments and Disclosure of Funding
We gratefully acknowledge Dr. Linyi Yang for providing partial computational resources.
References
2023, [2] Zeyuan Allen-Zhu and Yuanzhi Li. Physics of Language Models: Part 3.1, Knowledge Storage
[1] Lightning AI. LisGPT.
and Extraction. July 2024. DOI: 10. 48550/ arx.vv/rrxvvv.. 2309. 14316 arXiv: 2309. 14316 [cs]
[3] Eric C. Chi and Kenneth Lange. Techniques for Solving Sudoku Puzzles. May 2013. DOI:
10.
aatvv./iiii... 1203. 2295 arXiv: 1203. 2295 [math]
[4] Karl Cobbe et al. Training Verifiers Solve Math Word Problems. Nov. 2021. arv: 2110
14168
[cs]
[5]
DeepSeek-AI et al. DeepSeek-RI: Incentivizing Reasoning Capability in LLMs via Rein- forcement Learning. Jan. 2025. DO1: 10. 48550/arXii 2501 12948
arXiv: 2501 12948
[cs]
[6] Yuntian Deng, Yejin Choi, and Stuart Shieber. From Explicit CoT to Implicit CoT: Learning to Internalize CoT Step by Step. May 2024. DOI: 10. 48550/ arxivv 2405 14838 arXiv:
2405. 14838 [cs]
[7]
Nouha Dziri al. Faith and Fate; Limits of Transformers on Compositionality. Oct. 2023.
DO1: 48550/8550a00 arXiv. 2305. 18654] arXiv: 2305 18654 [cs]
[8] Guhao Feng et al. Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective. Dec. 2023. DOT: 10. 48550/ arXiv 2305. 15408, arXiv: 2305. 15408 [cs]]
[9] Yao Fu et al. "Specializing Smaller Language Models towards Multi-Step Reasoning". In: Proceedings of the 40th International Conference on Machine Learning. PMLR, July 2023, pp. 10421-10430.
[10] Alex Havrilla et al. GLoRe: When, Where, and How to Improve LLM Reasoning via Global and
Local Refinements. June 2024. DOI: 10. 48554/550//00 arxiv 2402. 10963, arxiv: 2402 10963
[cs]
[11] Yancheng He et al. Can Large Language Models Detect Errors in Long Chain-of-Thought Reasoning? Mar. 2025, DO1: 10. 48550/ wwwia.252............... 2502..9361 arXiv: 2502, 19361 [cs]
10

---

[12] Kaiying Hou et al. Universal Length Generalization with Turing Programs. July 2024. DOI:
10. 488500/axxiv 2407.00310 arXiv: 2407 03310 [cs]
[13] Takeshi Kojima et al. Large Language Models Are Zero-Shot Reasoners. Jan. 2023. DOI:
10. .48850/arXiv 2205 11966 arXiv: 2205 11916 [cs]
[14] Aviral Kumar et al. Training Language Models Self-Correct via Reinforcement Learning.
Sept. 2024, arXiv: 2409. 12917 [cs]
[15] Nathan Lambert et al. Tulu 3: Pushing Frontiers in Open Language Model Post-Training Apr.
2025. DOI: 10. 088555//axiiv 2411 15124 arXiv: 2411 15124 [cs]
[16] Zhiyuan Li et al. Chain of Thought Empowers Transformers to Solve Inherently Serial Problems.
Sept. 2024. DOT: 10. 48550/ /00000//riv..... 2402. 12 12875, Xiv: 2402. 12875 [cs, stat]
[17] Hunter Lightman et al. Let's Verify Step by Step. May 2023. arXiv: 2305 20050 [cs]
[18) Liangchen Luo et al. Improve Mathematical Reasoning in Language Models by Automated
Process Supervision. June 2024. arXiv: 2406. 2406.06592 [cs]
[19]
Aman Madaan et al. Self-Refine: Iterative Refinement with Self-Feedback. May 2023. DOI:
10. 48550/arXiv 2303. 17651 arXiv: 2303. 17651 [cs]
[20]
OpenAl. Learning to Reason with L.LMs. http:///wgggggn.ooooooo/o///aane
llms/.
[21]
OpenAL. OpenAl O3-Mini System Card. http://ogeniiicommmnnoddddmmmmmp arXiv:
[22]
OpenAl al. GPT-4o System Card. Oct. 2024. DOt: 10.
2410. 21276 [cs]
[23] Long Ouyang et al. "Training Language Models to Follow Instructions with Human Feedback". In: Advances Neural Information Processing Systems 35 (NeurIPS 2022). Mar. 2022, arXiv:
2203. 02155 [cs]
[24]
Jiayi Pan et al. TinyZero. http://ggtbbbbccom/jjaaPaaaa/iit
Accessed: 2025-01-24. 2025. Ben Prystawski. Michael Y. Li, and Noah D. Goodman. Why Think Step by Step? Reasoning
[25]
Emerges from the Locality of Experience. Nov. 2023. arXiv: 2304. 03843 [cs]
[26] Yiwei Qin et al. 01 Replication Journey: A Strategic Progress Report - Part 1. Oct. 2024. DOI:
10. 4.450/ arvi 2410 18982 arXiv: 2410 18982 [cs]
[27] Yuxiao Qu al. Recursive Introspection: Teaching Language Model Agents How to Self- Improve. July 2024. DO1: 10. 48550/ Seexxi..4000 18219, arXiv: 2407 18219 [cs]]
[28] John Schulman et al. Hlihh-iiennn Diig--Dimesiioall Continuous Control Using Generalized Advantage Estimation. Oct. 2018. arXiv: 1506.02438 [cs]
[29] John Schulman et al. Proximal Policy Optimization Algorithms. Aug. 2017. arXiv: 1707
06347
[cs]]
[30] Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural Machine Translation of Rare Words with Subword Units. June 2016. DOI: 10. 48550/ arXiv. 1508 .09909 arXiv: 1508
07909 [cs]
[31] Zhihong Shao et al. DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models. Apr. 2024. arviv: 2402. 03300 [cs]
[32] Charlie Snell et al. Scaling LLM Time Compute Optimally Can Be More Effective than Scaling Model Parameters. Aug. 2024. arXiv: 2408 24002033184 [cs]
[33] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. 2nd ed. Cambridge, Massachusetts: The MIT Press, 2018 ISBN: 978-0-262-36401-
[34] Yijun Tian et al. TInyLLM: Learning a Small Student from Multiple Large Language Models.
Mar. 2024. DO1: 2.0.48550/A5 arXiv.2402. 20....442226666
arXiv: 2402.046166 04616 [cs]]
[35] Rasul Tutunov et al. Why Can Large Language Models Generate Correct Chuin-of-Thoughuss
June 2024. DOI: 10. 485504855KK33 www......11....... 13571 arXiv: 2310. 13571 [ca]
[36] Ashish Vaswani et al. "Attention Is All You Need". In: Proceedings of the 31st International Conference on Neural Information Processing Systems. Long Beach, CA, USA, 2017.
[37] Jun Wang. A Tutorial on LLM Reasoning: Relevant Methods behind CharGPT 01. Feb. 2025. DOT: 10. 00..48550/arat http//arvvvvv..
10867] Xivi:: 2502. 10867 [cs]]
[38] Jason Wei et al. Chain-of Thoughh Prompting Elicits Reasoning in Large Language Models.
Jan. 2023. DOI: 10. 48550/ arXiv. 11903 arXiv: 2201. 11903 [cs]
[39] Sang Michael Xie et al. DoReMi: Optimizing Data Mixtures Speeds Up Language Model Pretraining, Nov. 2023, DOL: 10. 48550/arXiv.. 2305. 10429. arXiv: 2305. 10429 [cs]
11

---

[40] An Yang et al. Qwen2.5-Math Technical Report: Toward Mathematical Expert Model via Self-Impe leproonproee Sept. 2024. arXiv: 2409. 12122 [cs]
[41] Yang Yue et al. Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model? Apr. 2025. DOL: 10 48550/ arxiv 2504. 13837 arXiv:
2504. 13837 [cs]
[42] Zhihan Zhang et al. Learn Beyond The Answer: Training Language Models with Reflection
for Mathematical Reasoning. Oct. 2024, DO1: 10. 48550 / aaxiiv.. 2406 12050
arXiv:
2406. 12050 [cs]
12

---

Contents
Introduction
Related works
3
Reflective reasoning for transformers
3.1
Reasoning formulation
3.2
The framework of self- self-verifying reflection
3.3
Training
Theoretical results
5
Experiments
5.1
Results of supervised fine-tuning
5.2
Results of reinforcement learning
Conclusion and Discussion
Notations
14
Details of reinforcement learning
14
B.
I
Proximal policy optimization
15
B.2
Group-reward policy optimization
15
B.3
Technical Implementation
16
Theory
16
A general formulation of reasoning performance
16
C.1.1 Bellman equations in RMTP
16
C.1.2
Bellman equations in RTBS
17
Accuracy derivation the simplified reasoning task
17
Derivation of Theorem
19
C.3.1 Proof of Proposition
19
C,3
Proof of Proposition
20
C.4 Derivation of RMTP reasoning cosl
23
C.5
Considering posterior risks of rejected attempts
24
D
Implementation details
25
D.I
Algorithmic descriptions of reflective reasoning
25
D.2
Example CoT data
25
D.2.1
Multiplication CoT
25
D.2.2 Sudoku CoT
27
D.2.3 Verification of reasoning steps
27
13

---

D.3
Model architectures and tokenization
28
D.4
Hyperparameters
28
D.5
Computational resources
29
Supplementary results of experiments
30
Evaluation of LLMs
30
E.2
Results of supervised fine tuning
30
Results of GRPO
................................
32
The verification errors after GRPO
32
E.3.2
The planning correctness rate after GRPO
34
E.3.3
Reflection frequency of optional detailed verification
................................
34
E,4
Reflection frequency under controlled verification error rates
Results of PPO
35
Notations
The notations used in the main paper are summarized in Table Notations only appear in the appendix are not included.
Table 1: Notations in the main paper.
Symbol
Meaning
The query of CoT reasoning
[R]
The sequence of intermediate reasoning steps
R.
The t-th intermediate step in CoT reasoning
A
The answer of CoT reasoning.
T
The number of steps (including the final answer) in an CoT The planning policy in MTP reasoning
π
St
The t-th state in CoT reasoning
T
The transition function an MTP
The special token as the positive label of verification. The special token as the negative label verification
"X"
V
The verification sequence for the proposed step R.-
A
The verifier such that V4+1 V..(S,, R(+1)
R
The verified reasoning step, i.e. (Re, Vi)
7
The reflective transition function in an RMTP
The self-verifying policy, i.e. { V}
m
The RTBS width, i.e. maximal number of attempts on each state
The probability of proposing correct step positive states
e_
The probability of instantly rejecting a correct step on positive states
6
The probability of accepting an incorrect step on positive states
f
The probability of instantly rejecting any step on negative states
a
The shorthand of μе_ + (1 (1)1164)
p(n)
The accuracy of non-reflective MTP reasoning
p(n)
The accuracy RMTP reasoning for queries with scale
(m(
The accuracy of RTBS reasoning with width m for queries with scale n
B Details of reinforcement learning
This section introduces PPO and GRPO algorithms used in RI. fine-tuning, We introduce PPO and GRPO under the context of MTP, which is described in Section 3.1 This also applies to RMTP
14

---

reasoning in Section 3.2 as RMTP is a special MTP given the self-verifying policy क and the reflective transition function T.
For any sequence X of tokens, additionally define the following notations: X denotes the i-th token, X (XlSi) denotes the former - 1 (i) tokens, and X denotes the length (i.e., the number of tokens).
Both PPO and GRPO iteratively update the reasoning policy through online experience. Let to denote a reasoning policy parameterized by 0. On each iteration, PPO and GRPO use similar process to update 0:
1. Randomly draw queries from the task or taring set, and apply the old policy Mesia to sample experience CoT's.
2. Use reward models to assign rewards to the experience CoTs. Let ORM and PRM be the outcome reward model and process reward model, respectively. For each CoT A). we obtain outcome rewards r. = ORM(Q, A) and the process rewards Ft = (S, 1 for 0, 1....... T (where Ry A). In our case, we only use the outcome reward model and thus all process rewards are O.
(Q,R1..
"i1....,,T 1. R2.......
3. Then, is updated by maximizing an objective function based on the experience CoTs with above rewards. Especially, PPO additionally needs update value approximator.
B.1 Proximal policy optimization
PPO (29 a classic RL algorithm widely used in various applications. includes value model to approximate the value function, namely the expected cumulated rewards:
oSS, R((()))
Ex
To
+
Tk
12 (1) No (n! Joatd [ s/
Let (t,( be the reference model (e.g., the policy before RL-tuning). Then, the PPO algorithm maximizes
be the relative likelihood of the i-th token in the t-th step, and Tref
T
R
JPPo(O) -EQ-P())AR)
1
ΣΣ
E1=
Rs
min qt (0)A.) clip (0), - e, + Acs] Au.] KL [roll }
(8) Here, A, is the advantage of the i-th token step f, computed using the value model v. For example, A., vS,,, R|| R( v(S,, (!(=)) is simple way estimate advantage. In practice, advantages can be estimated using the general advantage estimation (GAE) (28).
The value model is implemented using the same architecture the reasoner except for the output layer, which is replaced by linear function that outputs a scalar value. The value model is initialized using the same parameters the reasoner, apart from the output layer. Assuming that is parameterized by w, we learn v by minimizing the temporal-difffreenee error:
T Rel
[u(w)= = -BQ Rowdesld
ΣΣ
(Se, R( Uwsna (Se+1))
Although PPO proves effective in training LLMS 23 we deprecate using it in training tiny trans- formers due the difficulty of learning the value function. Since the value model is also tiny transformer, its weakness in model capacity severely compromise the precision of value approxima- tion, leading unreliable advantage estimation.
B.2 Group-reward policy optimization
PPO requires learning an additional value model, which can expensive and unstable. Alternatively, GRPO 31 directly computes the advantages using the relative rewards from group of G solutions.
15

---

For each query Q, it samples group of G solutions:
{Ry) (Rg.1,
~ Tonis for 1, I.....G. G.
(10)
In this group, each solution {Ry} contains Tg steps, where the answer Ag is considered as the final step TT Using the reward models, we obtain process rewards rр := ((Tg.1..... g. 1g== and outcome rewards To == Pgg.og=11 Then, GPRO computes the normalized rewards, given by:
i g. gg. mean Tp
Tg.o mean ro
(11)
std F'
r.
Afterwards, the advantage step in the g-th solution of the group is Ag,t = 7,o + Ekee aa Let (0) = To / ( (1=4))
be the relative likelihood of the i-th token in the i-th step from the
Toord (1 Sa.. 1))
g-th solution. Then, the GRPO objective is to maximize the following:
1 ΣΣ Σ
T. 1R
1 Σ
(aRPo(0) -BQ-
G
[T(1]
g
{ min (0) clip (0), - E, +) An. - BD (oollres (12)
B.3 Technical Implementation
We made technical modifications that make RL more suitable in our case, described in the following.
First, in RMTP, we mask off the advantage of rejected steps, while the advantage of self seff-verification labels is reserved. This prevents the algorithm from increasing the likelihood rejected steps, allowing the planning policy to be properly optimized. In practice, find this modification facilitates the training models that perform mandatory detailed verification. Otherwise, RL could make the reasoner excessively rely reflection, leading to CoT' that unnecessarily long.
Second, we employ an early-truncating strategy when sampling trajectories in training. If the model has already made clear error at some step (detected using oracle process reward model), we truncate the trajectory as it is impossible to find a correct answer. This avoids unnecessarily punishing later steps due to previous deviations, own context. Empirically, we find this modification reduces the training time required reach the same performance, while the difference in final performance is marginal.
some later steps may be locally correct in their
C
Theory
C.1 general formulation of reasoning performance
Let S denote the state space and A denote the answer space. We use Aq C A to denote the set of correct answers for some input query Q. Given any thought state S, the accuracy, namely the probability of finding correct answer, is denoted as
PQ (S) = P(Re+1 R ANn (A E Ag S =
(13)
C.1.1 Bellman equations in RMTP
By considering the reasoning correctness the binary outcome reward, we may use Bellman equations [33] to provide a general formulation of the reasoning performance for arbitrary MTPs (RMTP). For simplicity, we use S, Rt and S" to respectively denote the state, step, and next state in transition.
Initially, in the absence of a trace-back mechanism, the accuracy PQ (s) can be interpreted as the value function when considering the MTP coal-directed decision process. For simplicity, we denote the transition probability drawn from the reasoning dynamics T as p(S" |S, R).. In non-reflective reasoning, the state transition probability p(S' (S) can be expressed as:
p(S' (S
Σ P(S'S (R.S)
(14)
16

---

When using RMTP execution, assuming that E(S, R) = Pv-P("X" E V S. represents the probability of rejecting the step R. we have:
Σ R (1))) - [(S, R)), E - (R)S) ((1 ())(()))))))) +ES, R)),
if $
(15)
if =
Consequently, the Bellman equation follows:
if AQ if A AQ if A
PQ(S)
0,
(16)
Es PQ (S')p(( |S),
C.1.2 Bellman equations RTBS
Let m denote the number of attempts at each state, and let (SS) represent the failure probability (i.e., the probability of tracing back after rejected steps) at state S. The probability of needing to retry proposed step due to instant rejection or recursive rejection is given by:
c(S) Σ T(RSS E(S, R) + -( - (1E5 (S) It
(17)
8'
The failure probability is then given by o(S) = E (S). When there are l attempts remaining at the current state S, denote the accuracy as (S, k)), given by:
k k> 0 (S k) = e pz))s, - +)+ En (2 (1 - E(S, RJ) Es (S)()) 10
k k= 0
(18)
It follows that Ps (S) Pe (S, m). This leads recursive formulation that ultimately results in the following equations for each s S:
e(S) = Σ (R|S)
E(S,R)+ + Ea -00-E(S,nn)) (S),
(19)
R
S
Po(S) 1- (S)"(S)
Σ (R]))) ((S, 1- E(S) E(S)
(20)
C.2 Accuracy derivation in the simplified reasoning task
In the following, derive the accuracy of reflective reasoning with and without the trace-back search, given the simplified reasoning task in Section 4 For each proposed step on a correct state, we define several probabilities to simplify notations:
= pe_ + (1 μ1 e4) is the probability of being instantly rejected; 3 = 1u(1 - -e) (--)it is the probability of being correct and accepted; y (1 p)e+ is the probability of being incorrect but accepted. Note that 3 here no longer refers to the Ki-deieeeeece factor in Appendix [
Proposition 2. The RTMP accuracy p(n) for problems with scale of n. is
p(n) = 1-
(21)
Let be the width of RTBS. Let 8m (n) and (n. be the probability of a proposed step being rejected (either instantly or recursively) on a correct state and incorrect state of scale n, respectively. We have am (0) em (0) 0 and the following recursive equations for 0:
8m (n) a + (6 1))" 7 11
(22)
(n) = (1 (Em 1))
(23)
Then, the RTBS accuracy pm (n. for problems with scale of is given by
(m) II om (t), where o. (t) = 33 m2-1
> (om) = (8m (1) 1=0
B.
(24)
8m (t)
In addition, (m), (n) and om (n) all motonously increase and converge in relation to
17

---

Proof. We first consider reasoning through RTBS. Let (n) and thn (n) denote the probabilities of failure (reaching the maximum number of attempts) in correct and incorrect states, respectively. Let Patm(()) indicate the accuracy after the i attempts at the current sub-problem of scale n. Therefore, we have Pm Palm (n) and Pmmm (n) = 0.
At correct state, have the following possible cases:
A correct step is proposed and instantly accepted with probability 3 = pul - e-). In this case, the next state has a scale of n 1. which is correctly solved with probability Pojm (n - 1) and fails (i.c., is recursively rejected) with probability om (n - 1).
A correct step is proposed and instantly rejected with probability pe-.
An incorrect step is proposed and instantly accepted with probability ? (1 e.) In this scenario, the next state has scale of n 1, which fails with probability 2 (n - 1).
An incorrect step is proposed and instantly rejected with probability / = (1 11) E+).
Thus, we have probability of a pe_ + (1 11 e+) instantly reject the step, and probability of 36m (n - 1) + 7m (n 1) to recursively reject the step. Therefore, the overall probability of rejecting attempt on correct states is:
(m)n) = a + 36m (n - 1) + m/ 1).
(25)
Since failure occurs after m rejections, we have:
(n) (1))
(26)
At an incorrect state, we have probability f instantly reject a step. Otherwise, we accept the step. and the next state fails with probability 4 1). Therefore, the overall probability of rejecting an attempt for incorrect states is:
Em (n) = ff +1(11
(27)
Similarly, we obtain:
mm (cm (n))
(28)
By substituting Equations (26) and (28 into Equations 225 and 27 obtain Equations (2) and (33.. If an attempt is rejected (either instantly or recursively), we initiate another attempt which solves the problem with probability of P(+1(m Therefore, we have the recursive form of the accuracy, given by:
7a 370mm (n + 8(n, p
(29)
Thus, we can expand im (n) as: pm (n)
Pojm (12)
Bpm (n 1) + 8m (1)
(B 5m (n)3 + 57h, (n))3 .... 6 (1) (r..)
(30)
= =m (m))) (n- -
(31)
Note that indicates that the state is exactly the outcome, which means Pmm (0) 1. Then, Equation (4 is evident given the recursive form Equation (3T).
For reflective reasoning without trace-back, we can simply replace 8, (n) with a in omm (n), as only instant rejections are allowed. We then set m - co, leading to Equation (2T).
Monotonicity We first prove the monotonic increase of 6m (n). Equation 23 gives 6m 6m(n) =
(em(nn 1))mM and em (n 1n+1)= f (fm (n)) for each 1. Therefore, if 6m (n) 2 Cm (n 1).
we have:
(n + 1) = f (n)) 2 (Em (n 1))" (n).
(32)
Additionally, it is clear that cm (1) - / 0= cm (0). Using mathematical induction, we conclude
that em (n + 1) > 6m (n)) for all n 2 0. The monotonicity of 6m) can be proven similarly, and the
monotonicity of om (m) is evident from that of d, (n). Since 8m (n) and em (n) are probabilities, they are bounded in [0, and thus converge monotonically.
L
18

---

reasoning accuracy (p)
1.0
RTBS
RTBS m=2
RTBS m=3
RTBS m=4
RTBS m=5
RTBS m- 6
0.4
RMTP
reflection
0.
10
20
problem scale (m)
Figure 10: The accuracy curves of non-reflective MTP p(n), RMTP p(n), and RTBS Pm (n), using
0.8, e_ = 0.3, e+ = 0.2, and f = 0.8.
Illustration of accuracy curves Using the recursive formulae Proposition 2 we are able to implement program to compute the reasoning accuracy in the simplified reasoning problem in Section 4 and thereby visualize the accuracy curves of various reasoning algorithms. For example, Figure 10 presents the reasoning curves given μ 0.8, e_ 0.3, et 0.2, and f = 0.8, which lead to a 0.4 < f. For this example, we may observe the following patterns: 1) An overly small width m in RTBS leads to poor performance; and 2) by choosing m properly, (n) remains stable when n > po. These observations are formally described and proved in Appendix
Furthermore, in Figure 10 we see that small m stabilizes the drop of (m) when n is large, yet it also makes pm.(") (n) drop sharply in the area where is small. This indicates the potential of using an adaptive width in RTBS, where is set small when the current subproblem (state) requires large number n steps to solve, and m increases when n is reduced by previous reasoning steps. Since this paper currently focuses on the minimalistic reflection framework, we expect to explore such an extension in future work.
C.3 Derivation of Theorem
Theorem [ obtained by merging the following Proposition and Proposition which also provide supplementary details on the non-trivial assumptions of factors μe, e-, and e+. Additionally, Proposition 4 also shows that there exists an ideal range of RTBS width such that stabilizes the drop of Pm (n) when -> co.
Proposition (RMTP Validity conditions). For all n. 2 O, we have p(n) 2 p(n) = e- +e+ < Additionally, μ > 0 and e. < 1, then for all n 2 1 we have that p(n) = p(n) = c. + and p(n) decreases strictly with either
64-
Proposition 4 (RTBS Validity Condition). Assuming 0 < p < 1, e_ < 1, and e+ > 0, then
lim (m(n) p(n)
m
and
(33)
n n-+00
a
Furthermore, we have
limm-sco (m) Pm (n]1 m [ 1-11
*m((n) increases strictly with f for all n 2
The proof of propositions 3 3addd given in Appendix C.3.1 and Appendix C.3.2 which based
on the previous derivation in Appendix C.2
C.3.1 Proof of Proposition! 3
In any case, we have 7(0) = ((0) = 1.
If 0 1, clearly have p(n) p(n) 0 for 2 1.
19

---

0 > and e_ < 1, we can transform p(n) (given in Proposition as:
Ø(n) (1+ +
1
11l -e-) 11l ct - e-) +c+
(34)
1 1-c. (p-1
This shows that p(n) strictly decreases with both e, and e.,, and p(n) = 1p" - c te_ =1 Therefore, also have p(n) > n² + ex + < 1.
The Proposition is proved by combining all the above cases.
C.3.2 Proof of Proposition 4
The assumptions 0 < μ < e- < 1, and 6+ > 0 ensure that 8 > 0 and > 0. Proposition
suggests the monotonous convergence of (n), (m(n), and om (n). For simplicity, we denote
6 lima-+co 5m (n), == 1im Em (n). and lom om (n). From Equations (22 and
23
we have:
36 7C
(35)
6 c= f (1-f)e f)
(36)
Note that 5 gives the trivial solution of the above equations. However, there may exist another solution (if any) such that ó < 1 or < under certain circumstances. Since em (0) = 0 and 5m (0) O, the limits and å take the smaller solution within [0, 1]. In the following, we first discuss when another non-trivia trivill solution exists.
Lemma For any m 2 1, if 0 S p < m=11 then x - + (1 -))=" has a unique solution
J. E [p. 1), which strictly increases with p. Otherwise, if m-1 S p S 1, the only solution in [0, 1] is T. 1.
Proof. Define F(x) = p + (1 p) - x. We find:
F((x) = m(1 - p)=
It is observed that (x(x) increases monotonically with æ. Additionally, have F*(0) --1 << (1) = -m(1 - p) 1. and F(1) = 0. We only consider the scenario where p > 0, since
= - [0, obviously the unique solution.
m This implies F'(1) > 0. Combining F'(0) < 0, there exists E (0, such that F'(E) = 0. As a result, F(z) strictly decreases in [0, E] and increases in [g. 1). Therefore, we have F(E) < F(1) 0. Since F(p) = (1 - p)p" > O, we know that there exists
IfO SpSpp m-1 we have p 1
unique x. E) such that F(x.) = 0.
If m-1 SP 1, we have 1 - p 1 and (1) < 0. In this case, F'(x) < On (0,1) due to the
monotonicity of F'(x). Thus, F(x) F(1) = 0 for all x E [0, 1). Therefore, v. = 1 is the only solution within [0, 1].
Now, we prove the monotonic increase of x. when S < m-1 We have:
dx. dp 1 1 1-1mh
dr.
+ m(1 - p)x: --
x
(37)
dp
dr,
x
(38)
dp 1-m(1 p)r 1n-
F(.x.)
F
The previous discussion shows that with F((z) increases monotonically, we have Fxxx,) < 0 and thus dæ.
[p. {) for some & such that F* 0. Given that
dp 0.
Lemma Assume p 0, q 0, and p + S 1. Then, the equation x = p + qur" has a unique solution v. E [0, 1), which increases monotonically with E [0, q).
Proof. Define F(x) : p + qrr" - x. Since F(O) > and F(1) 0, there exists a solution r. E 1). Since F is convex, we know there is at most one other solution. Clearly, the other solution appears (1, (00), since F(+20) > O. Therefore, F(x) = must have a unique solution r, in [0, 1). Additionally, must appear the left of the minimum of F, which yields F* fz(x.) 0.
20

---

Using the Implicit Function Theorem, we write:
dr 1
Fx > 0
(39)
dp mgqa*
Thus, we conclude that x. increases monotonically with p.
Applying Lemmas and 2 to Equation (6), we find that e == if and only f 2 m-1; otherwise, c strictly increases with p. Therefore, f m=1 indicates that 1, leading (a + 7c) + y Using Lemma 2 again in Equation (35 we have f < m=1
m
< 1. Conversely, f 2 m-11
yields = 1. and thus f
m--
8 = 1.
First, we consider the special case where 5 = 1, which occurs if both S, a + m-1 namely
m S min( }3. In this case, we write o (1 + 5 + ... + + = m33 Therefore, we have:
lim p(n) n-+00 p(n)
B
> + 1 1-6
B
mB >
1
m >
1-a
This leads to the validity condition that 1-a < m < min
1
1
Next, we consider the case where 8 < 1, which occurs when
m=1
7 <
m-1
This leads
m
m
3 2 m
and we can write:
8
(5 ")
(40)
B
8m
(1 8Th) )
0
1
(1 a) (38Th + m
(41)
Then, we can derive:
((n)
lim
<1
0
1 00000
p(n)
1-a a
1 - 8m
1
(1 a) (38m + m
1-a a
(1 8t [[ a) > (1 a) -m38Th + 7
7E" > 8th (1 a - 3)
7 7mth
E>
Since have assumed 8 < 1, we have = 1> 8 f m=1, otherwise if M-1 then e = leads to = being a solution of Equation (35). Additionally, from Lemmas D and 2 that a higher would increase (a + ye), which eventually raises ó above conversely, lower causes to drop below e. To summarize, we have the following conditions when 1:
we know
126>8 + 4
a aa+<<
m-1 -
<I)
or a <
m
(42)
m
m S
or
a < f and m
(43)
8
1 1-
1-
21

---

Combining the conditions when 5 = 1, we have:
((n)
lim
> 1
11000 p(n))
1
1 1- f f/z) ( or (3 < (3<m=
1
1- :
(a< and m >
1 m S min
1-
(44)
and f > a
(45)
1 a
Thus far, we have obtained Equation 33 Proposition 4
Now, we start proving the two additional statements in
First, we prove that 3/ 5 m - y ensures that o = 1. First, if 0 = we have m S 3 1 In
this case, m33 and thus 1 when We can express that:
3. Alternatively, if have >> min 33 1-7)
1 8m
3 - (6 ycm
1-e o1-
(46)
1
Using Lemma 2 we know that increases with a + ye, which increases with Therefore, we have dé > 0. Then, obtain
m
B d6
do/dc= Σ
10
0,
(47)
de
8m
8 - (6 7e
a a 3
(1 e 8 1-8
1-8
8 7(1 1-1)
(48)
1 6
Therefore, increases with and reaches its maximum value of 1 when 1. As a re-
sult, we conclude that 3 I m I --f ensures that a = 1. Combining 3 = 1(1 e_)
(m) and a = limn (n) = lim,-+00 (mn(--)) we have proved that lim,-+00 (n-1) m E [ ): 1-
(n)
if
Next, we prove the monotonicity of pm (n) with respect to f. To prove this, we first prove the monotonicity of em (t) for all with respect to f.
Lemma 3. For n >> em (t) as defined in Equation 23 increases strictly with
Proof. We regard
(0; 10;f)=0. = 0,
(1-))(emm(mmt 1)
(49)
function of ff [0. 1]. When t = 1 have
Gn (1; = (1 f)m = f.
(50)
80 Bem (lif) that
1 > 0. Thus cm [) is strictly increasing with f. Further, assume for some k: 2 1
@mm(k; f) 0 vf e 10,
0 6m (k; f)= < and
(51)
0S
Differentiate the recursion for t = h + 1:
'm (k: + 1; 1; =
[] (k: [k:]]]] f)!m
(52)
dem (k + 1: = 1 - Fem (k:; f)] + (1 - f) mm (k; m-1 dem (k: f)
(53)
05
01
22

---

By the inductive hypothesis, cm (k; f) < 1 implies [em (k; f)]
< 1. Therefore, we have
1 - [Im (k:; [)] > 0.
(54)
Since 1 - f 2 O, m 2 1, [<m(k: f)] m=1 2 0, and Hence
Or., (k:f) of
> 0, the second term is also positive.
dem (k 1:f)
>0,
(55)
Of
showing that 6m f) strictly increasing. This completes the induction.
Given Lemma 3 we can also prove the monotonicity of 5m using mathematical induction: It is easy to write that 8m (2) = a + Ba +>f"", showing that 8m (2) increases strictly with f. Then, for
t > 2, assuming that 6m (f 1) increases strictly with f and using Given Lemma 3 we know that 8m (t) increases strictly with f from Equation (22).
Therefore, we have (1) = a and that (t) strictly increases with f for n 2 2. According to Equation 24), from the above monotonicity of 5m (f), it is obvious that o (!) increases with respect to f for all f. This gives the corollary that (n)(n) increases with f for all n.
C.4 Derivation of RMTP reasoning cost
In this section, we derive how many steps it costs to find a correct solution in RMTP and thereby prove Proposition T
Proposition / The probability of accepting the correct step after the i-th attempt is given by a'-1 Assuming maximum number of attempts m, the number of attempts consumed at each step satisfies:
3
aa
Pr(i attempts
correct)
(56)
3 + aB +
+ am
am
Therefore, the average number of attempts required for a correct reasoning step is given by
(1 ata
1 1 C
Am
ia 4-1
(57)
1 m
a 1=1
To simplify the summation expression telescoping series. Let == Em= ia!-1
E i-1 (where 0 < a < 1), we can use the method of
We calculate aS:
as = ia
(58)
i=1
Thus,
m
S Σ ia 1-1
Σ
ia
(59)
i=
This gives (1-a)S=1+a+dl a- ma
1- t
ma" m
(60)
1 C
Rearranging, we have
m
1- a (1 )m
ia
(61)
(1 - a)
Thus, the average number of attempts can be further expressed
1 1 - ah (1 a a)ma"
A
(62)
a.
(1 a)²
a
(1 mm
(63)
a)( (1 m
a" m
1
(64)
m
(65)
23

---

Considering the limit as m - oc, it can be shown using limit properties that limm- m I-a 0. If the correct solution is obtained (i.e., correct steps are accepted at each step), the average number of steps taken given by
T = ==nAx
n
n
(66)
pe- p1(1 e+) (1 ple- 101 e-)
C,5
Considering posterior risks of rejected attempts
Our previous analysis is based on a coarse binary partition of states (correct and incorrect) for each scale, which enhances clarity yet does not apply to real-world complexity. Therefore, we can introduce stronger constraints by taking into account the posterior distribution of states in S after multiple attempts. For example, if the state has produced several incorrect attempts on state S (or rejected several correct attempls), is more likely that the current state has not been well generalized by the model. Consequently, the chances of making subsequent errors increase. In this case, is likely to decrease with the number of attempts, while e.. increases with the number of attempts. Thus, the probability of accepting the correct action will decrease as the number of attempts increases.
Therefore, we consider the scenario where the probabilities of error increase while the correctness rate μ drops after each attempt. We define Cs+. Ci-, M4, etc., to represent the probabilities related to the i-th attempt, corresponding to the calculations of o;;; 8r, Tia etc. We have that 9 = 14:1 - e;-) is monotonically decreasing, and = /1/) /ss)et+ is monotonically increasing with the index of the attempt. In this case, the derivation similar that of Proposition 2 Therefore, we skip all unnecessary details and present the results directly.
Proposition 5. Given the above posterior risks, the RTMP accuracy p(n) for problems with scale of n is
p(n)
31
Osi
(67)
j=1
Let be the width of RTBS. Let 81mm(()) (n) denote the probability of a proposed step being rejected (either instantly recursively) the i-th attempt correct state, and c. (n) follows the same definition as in Proposition 2 for n > 0:
We have dam (0) = Em (0) = and the following recursive equations
M
0m (n) 0; 8i 6 (n 1) + (e -(
1, ,
(68)
j=1
em (n) = f (1- f) (Em (m 1))
(69)
Then, the RTBS accuracy Pm (n) problems of scale n is given by:
(m((1) (n) III (t), where o. (t) = B
Σ 3 II (t,
(70)
In addition, 6mpm (n), em (n., and (n) all monotonically increase and converge with respect n.
The theoretical result in this new setting becomes much more challenging to derive exact validity condition that remains clear and understandable. However, it is still useful to derive a bound that sufficiently guarantees the effectiveness of reflection. In the following, show that sufficient condition becomes much stricter than that in Proposition 3
Proposition 6. Assume PI < and inf; 8.t1 the lower bound of the decay rate of the probability of accepting the correct step multiple attempts. Then, a sufficient condition for p(n) > p(n) is:
61
+supe es
(71)
k(1 m1)
24

---

Proof. Considering 14c1- + (1 - 1s)(1 - max; cit), let = - -11((1 - sup; Cit) be its
lower bound. It can be seen that
m 1
1 - (ak)
B1 a1 a10283 + + 3m
II
a Σ (ak) m- 91 31
(72)
As m - oc, the sufficient condition for reflection validity is:
B1 1 ak
(73)
1 61-
(74)
1 k(1 111(1 - sup; cit)
e
- (1 11) - supeit) k
(75)
61
sup u (1 m1) <
(76)
k
61
+ sup ei+ < 1
(77)
k(1 kn)
D Implementation details
This section describes the details of the training datasets, model architectures, and hyper-paramette used in experiments. Our implementation derives the models architectures, pretraining, and SFT from LitGPT (version 0.4. 12) under Apache License 2.0.
D.1 Algorithmic descriptions of reflective reasoning
Algorithms | and 2 presents the pseudo-code of reasoning execution through RMTP and RTBS, respectively. In practice, we introduce reflection budget M to avoid infinite iteration. If reflective reasoning fails to find a solution within M steps, the algorithm retrogrades to non-reflective reasoning.
To implement RTBS. maintain a stack to store the reversed list of parental states, allowing them to be restored if needed. Different from our theoretical analysis, our practical implementation does not limit the number of attempts the input query Q (as long the total budget M is not used up) as Q has no parent (i.e. the stack empty).
D.2 Example CoT data
We implement predefined programs to generate examples of CoTs and self-verification. Figure II presents the example reasoning steps (correct) for non-reflective training and the example detailed verification for reflective training. In our practical implementations, the reasoning steps include additional tokens, such as preprocessing and formatting, assist planning and transition. To simplify transition function T, the example steps also include exactly how the states are supposed to be updated, which removes the task spec-fpec prior in T.
D.2.1 Multiplication CoT
Each state is an expression F; x St tr, where v, and y are the remaining values two multiplicands, and r, is the cumulative result. For an input query x y, the expert reasoner assigns 2ı 2, y/1 and r1 = 0.
For each step, the reasoner plans a number u E (1...., computes = w. x yt or (6 u X²). Next, it finds the digits in x, (or yr) that are equal to u and set them to 0 in 1 (or 1)+1). For each digit set to 0, the reasoner cumulates å x 10s to rt, where i is the position of the digit (starting from for the unit digit). An example of reasoning step is shown in Figure [I(a) Such steps are repeated until either Øт yr becomes 0, then the answer is rT.
.,,...,9).... 9} to eliminate in (or y.). Specifically, it
25

---

Algorithm Reflective reasoning through RMTP
Require: the query Q, the augmented policy म {T, VJ. transition function T, and reflective reasoning budget
1: 0,
Q
2: repeat
3:
Infer R&+1 x(.-1 St)
4: Reject +- False
5: ift S M then
6:
Infer Ve+1 ~ VC- | St, R(+1)
7:
Reject t- True if "x" E V41
8:
Reject = True then S St
9:
10:
else
S T(S,, if R is the answer then
12:
+ 1, Ret1
14:
else
t ++t+1
16:
until The answer A is produced return
17:
Algorithm 2 Reflective trace-back search
Require: the query Q, the augmented policy ă = { V}, transition function T, search width m, and reflective reasoning budget M
I: + 0, S2 f Q
2: e 0 ('The index of attempts)
3: Initialize an empty stack
4: repeat
5:
Infer R&+1 ~ x(-1 St)
6: Z+it)
7:
Reject + False
8:
ift S. M then
9:
Infer V4+1 ~ V(. St, R(41)
Reject +- True if "x" E V44
11:
if Reject = True then
if < m then S +- St
13:
else
15:
(Find parent state that has remaining number of attempts.) repeat
16:
17:
Pop (sRij) from L
18:
S4+1 +- Sk. + until < or L is empty
19:
20:
else
21:
Push (S) into L S +- T(St, Re+1), +- 0 if R441 is the answer then
22:
23:
24:
++ t- R
25:
else
26:
t 1+14 1+11
27:
until the answer A is produced
28:
return A
26

---

step Re+1
verification V/+1 (detailed)
state St
planning
update
Context window
<state>
145586093
left 8::
649*
<artion>
+11701500
</state>
-32 07244-0 4-44--30
</state>>
cumulate d:
-8+3
------4----
</action>
cumulate 0000000:
<state>
+0 0
-0+0=0
</reflect>
-1+0=1
-1+6=7
get 111011000.
</actton>>
(a) Mult
step R
verification V (detailed)
state St
precrocessing
planning & update
rows
12456789
<state>
3578204 4 1
124578 123456769 145789
3.58 6 464499 19
1234589
12345789
669 40 72
cols 123589 13456789 12345789
86 150352
0
13456789 12456789 124578
682 575573
513966 8
124579 123478 1243689
513968
97 0
blockes 135677 89 1245789 124679
97 4 68
J V
124578
04 6 02
1234589 12345678 1234589
74568922
</state>>
</state>
</reflect>
(b) Sudoku
Figure 11: Example reasoning steps with detailed verfication for integer multiplication and Sudoku.
D.2.2 Sudoku CoT
Each state is a 9 x 9 matrix representing the partial solution, where blank numbers are represented by On each step, the reasoner preprocesses the state by listing the determined numbers of each row, columns, and blocks. Given these information, the model reduces the blank positions that has only one valid candidate, If blank can be reduced, the model randomly guess a blank position that has the fewest candidates. Such process continues until there exist no blanks (i.e., zeros) in the matrix.
An example of reasoning step is shown in the right of Figure 11(b) The planned updates (i.e., which positions are filled with which numbers) is intrinsically included in a new puzzle, which is directly taken the next state by the transition function T.
D.2.3 Verification of reasoning steps
Binary Verification The Binary verification labels are generated using rule-based checker of each reasoning step. In Multiplication, it simply checks whether the next state 3++1 Vt++1 + F+++ is equal the current state x, y/ + rt- In Sudoku, checks whether existing numbers in the old matrix are modified and whether the new matrix has duplicated numbers in any row, column, and block.
Detailed Verification In Multiplication, output label for each elemental computation addition or unit-pair product - is computed correctly. Sudoku, we output label for each position in the new matrix, signifying whether the number violates the rule of Sudoku (i.c. confficts with other
27

---

numbers in the same row, column, or block) or is inconsistent with the previous matrix. These labels are organized using a consistent format as the CoT data. Examples of detailed reflection for correct steps is in Figure [1(b) If the step contains errors, we replace the corresponding "V" with "x"
D.3
Model architectures and tokenization
Table 2: The model architectures of models for the transitional implementation.
Task
Mult
Sudoku
Model size
1M
4M
16M
1M
4M
16M
Vocabulary size
128
Embedding size
128
256
512
128
256
512
Number of layers
5
Number of attention Heads
4
8
8
4
8
Our models architectures uses multi multi-head causal attention with LayerNorm (36] with implementation provided by LitGPT (T). Sable([speciffie the architecture settings of transformer models with 1M, 4M, 16M parameters.
Tokenizers We employ the byte-pair encoding algorithm 330 examples for tiny transformers. Special tokens for reflection and reasoning structure (e.g., identifiers for the beginning and ending positions of states and reasoning steps) are manually added to the vocabulary. Since the vocabulary size is small (128 in our experiments), the learned vocabulary is limited elemental characters and the high-frequency words for formatting.
train tokenizers reasoning CoT
D.4 Hyperparameters
Table 3 presents the hyper-parameter used in training and testing the tiny-transformer models. In the following sections, we describe how these parameters are involved in our implementation.
Non-reflective training The pretraining and SFT utilize a dataset No.r of CoT examples generated by an expert reasoning program. Pretraining treats these CoT examples as plain text and minimizes the cross-entropy loss for next-token prediction, using the batch size Bpre and the learning rate Myre. The pretraining process terminates after predicting a total of Npre_tok tokens. The non-reflective SFT uses the same dataset as that used in pretraining. It maximizes the likelihood of predicting example outputs (reasoning steps) from prompts (reasoning states), using the batch size BSFt and the learning rate TTS The total number of non-reflective SFT epochs is ESET.
To perform non-reflective SFT, use the model after non-reflective training to sample trajectories for each input query in the training set. The reflective sampling involves two decoding temperatures: the lower solving temperature Trefl:s used walk through the solution path, while higher proposing temperature frp is used to generate diverse steps, which are fed into the reflective dataset. Then, the verification examples, which include binary or detailed labels, are generated by an expert verifier program. The reflective SFT includes EnSTT epochs, using the same batch size and learning rate as the non-reflective SFT.
Reflective SFT
Reinforcement learning We use online RL algorithms as described in Appendix B including PPO and GRPO. These algorithms include experience replay buffer store Norouu and NGRPO:buf example trajectories, respectively. After every ERL:ine epochs trained on the buffer, the buffer updated by sampling new trajectories, using the temperature TRL: for planning steps and the temperature TAL:# for reflective feedback. According to Equations S and [2] the hyper-parameters both the PPO and GRPO objectives include the clipping factor and the KL--Divergence factor 3. Additionally, GRPO defines G as the number of trajectories in group. We run RL algorithms F.I. epochs, using the learning rate m). PPO involves Epro:wermap warm-up epochs the beginning of training, during which only the value model is optimized.
28

---

Table 3: The main used in this work.
Task
Mult
Sudoku
Model size
1M
4M
16M
IM
4M
16M
Training CoT examples: NCoT
32K
36K
Total pretraining tokens: Npre tok
IB
Pretraining batch size: Bpre
128
Pretraining learning rate: Opre
0.001 + 0.00006
SFT batch size: BSrt
128
SFT learning rate: VSFT
0.001 + 0.00006
Non-reflective SFT epochs: ESFT
Reflective sampling temperature: Solving Treft:s
0.75
Reflective sampling temperature: Proposing Treflip
1.25
1.5
1.25
1.5
Reflective SFT epochs: ERSFT
PPO replay buffer size: NppO:buf
512
GRPO replay buffer size: NGRPOSS
1024
RL sampling interval: ERL:int
4
RL sampling temperature: Planning TRL:s
1.25
1.25
1.25
RL sampling temperature: Feedback TRE.F
RL clipping factor:
0.1
RL KL-divergence factor: 3
0.1
GRPO group size: G
8
RL total epochs: EXL
512
RL learning rate: 7RL
0.00005 -> 0.00001
PPO warm-up epochs: EprO-warmup
64
Testing first-attempt temperature: Tr:first
0
Testing revision temperature: Tarrev
Testing verification temperature: Tay
0
Testing ron-eefleet steps T:
32
Testing reflective steps T:
64
RTBS width: m
Testing During testing, we execute the reasoner using three decoding temperatures: Trafirst for the first planning attempt, Tr:rev for the revised planning attempt after being rejected, and Tay for self-verification. We use low temperatures to improve accuracy for more deterministic decisions, such self-verifying feedback and the first attempt Mult. We higher temperatures for exploratory decisions, such as planning in Sudoku and revised attempts in Mult. We set the non-reflective reasoning budget to steps and the reflective reasoning budget to steps. If the reflective budget is exhausted, the reasoner reverts to non-reflective reasoning. We set the search width of RTBS
D.5
Computational resources
Since our models are very small, it entirely feasible to reproduce all our results on any PC (even laptops) that has standard NVIDIA GPU. Using our syper-parameters, the maximum GPU memory used for training the MM, 4M, and 16M models is approximately 4GB, 12GB, and 16GB, respectively, which can be easily reduced by using smaller batch sizes. To run multiple experiments simultancously, we utilize cloud servers with a total of 5 GPUs (one NVIDIA RTX-3090 GPU and four NVIDIA A10 GPUs).
For each model size and task, a complete pipeline (non-reflective training, reflective training, and RL) takes about two days single GPU. This includes 1-2 hours for non-reflective training, 8-12 hours for data collection for reflective training, 1-2 hours for reflective SFT, 6-12 hours for RI., and 6- 12 hours for testing.
29

---

Table 4: The accuracy (%) of GRT-4o, DeepSeek-RI, and OpenAI o3-mini in integer multiplication and Sudoku, compared with the best performance of our 1M (IM*). 4M (4M*), and 16M (16M*) transformers. The "OOD-Hard" for LLMs only refers to the same difficulty as used in testing our tiny transformers, as OOD-Hard questions may have been seen the training of LLMs.
Model
GPT-4o
03-mini
DeepSeck-FR R1
IM
4M
16M
ID-Easy
73.2
100
96.8
96.2
98.7
99.7
Mult
ID-Hard
32.6
97.2
77.0
52.7
77.0
81.1
OOD-Hard
18.6
96.4
61.4
3.7
5.8
9.4
ID-Easy
40.7
99.6
90.4
33.9
97.2
99.8
Sudoku
ID-Hard
2.8
52.8
4.4
0.4
58.1
72.2
OOD-Hard
0.0
0.0
0.0
0.0
6.9
14.4
E
Supplementary results of experiments
In this section, present supplementary results from experiments: 1) assess the reasoning accuracy of various large language models on integer multiplication and Sudoku tasks; 2) we report the accuracy outcomes of models after implementing different supervised fine-tuning strategies; 3) we provide full results reasoning accuracy after GRPO; 4) we additionally provide the results of PPO, which is weaker than GRPO in reflective reasoning.
E.1 Evaluation of LLMs
In this section, we provide the reasoning accuracy of LLMs on Mult and Sudoku, including GPT-4o [22]. OpenAI 03-mini [21), and DeepSeek-RI (5). Since GPT-4o is not a CoT-spccialized model, we use the magic prompt "let's think step-by-step" [33] to elicit CoT reasoning. For 03-mini and DeepSeek-R1, only prompt with the natural description of the queries. As shown in Table 4 among these LLMs, OpenAl o3-mini produces the highest accuracy in both tasks.
To illustrate how well tiny transformers can do in these tasks, we also present the best performance (results selected from Tables 5 and 7 of our 1M, 4M, and 16M models for each difficulty level, respectively, showing performance close to or even better than some of the LLM reasoners. For example, according to our GRPO results (see Table 7 our best 4M Sudoku reasoner performs (RTBS through optional detailed verification) equally well to OpenAl o3-mini, and our best 16M Mult reasoner (through binary verification) outperforms DeepSeck-RR R1 in ID difficulties. Note that this paper mainly focuses fundamental analysis and does not intend to compete with the general- purpose LLM reasoners, which can certainly gain better accuracy if specially trained on our tasks. Such comparison is inherently unfair due to the massive gap resource costs and data scale. The purpose these results is to show how challenging these tasks can be, providing a conceptual notion of how well tiny model can perform.
E.2 Results of supervised fine tuning
our complete results of reasoning accuracy after non-reflective and reflective SFT. As discussed in Section 3.1 implementation uses Reduced states that maintain only useful information for tiny translormers. To justify this, we also test the vanilla Complete implementation. where each state S. = (Q., R1... ..... R2-1) includes the full history of past reasoning steps. As baseline, the Direct thought without intermediate steps is also presented.
Reducing the redundancy of states in long CoTs benefits tiny transformers. The left three columns compare the above thought implementations for non-reflective models. We see that both direct and complete thoughts fail to provide an acceptable performance even in ID-Fasy difficulty. This proves the importance of avoiding long-context inference by reducing redundancy in representing states. Considering the huge performance gap, we exclude the complete and direct implementations from our main discussion.
Estimated errors of self-verification For RMTP and RTBS executions, we employ the oracle verifiers to maintain test-time statisties of the average e and e+ (see definition in Section 4 of reasoning states. The results are shown in Table 6 where also present the difference in how much
30

---

Table 5: The reasoning accuracy (%) for IM, 4M, and 16M transformers after SFT.
Thought Implementation
Direct
Complete
Reduced
Verification Type
None None
None None
None None
Binary RMTP
Detailed RMTP
Reflective Execution
None
RTBS
None
RTBS
Easy
21.8
10.6
95.8
94.5
93.4
22.0
33.4
24.2
Mult
ID Hard
3.0
1.4
2.0
52.7
44.6
35.5
2.2
4.8
2.8
OOD Hard
1.4
0.3
IM
ID Easy
2.8
0
1.4
33.0
32.4
2,4
17.4
18.7
19.4
Sudoku
Hard
0.3
0.1
0.1
OOD Hard
0
0
Easy
15.6
17.2
92.0
97.7
97.6
97.3
94.5
93.8
93.3
Mult
ID Hard
1.7
1.9
37.3
56.9
62.2
53.0
43.4
47.6
42.4
OOD Hard
1.2
1.0
2.2
2.9
1.8
1.1
3.7
3.3
2.7
4M
ID Easy
13.0
3.9
52.2
92.1
96.8
96.0
54.4
81.9
88.5
Sudoku
ID Hard
0.1
0
3.3
40.9
46,3
53.3
5.2
16.9
45.7
OOD Hard
0
0.4
4.0
6.7
0.0
2.0
ID Easy
15.1
59.2
99.2
98.8
98,9
98.8
99.2
99.5
98.5
Mult
ID Hard
1.6
9.6
65.9
65.2
76.7
74.9
65.9
76.4
73.5
OOD Hard
1.2
1.0
2.5
1.1
1,3
1.3
9.2
9.4
7.2
16M
Easy
35.8
15.9
95.7
97.9
92.5
93.0
99.0
99.7
Sudoku
ID Hard
0.4
0
48.8
50.1
53.1
54,8
46.9
57.9
70.7
OOD Hard
0.9
8.2
14.4
reflective reasoning raises the performance over non-reflective reasoning. We only count the errors in the first attempts reasoning states avoid positive bias, the reasoner may be trapped in some state and repeat the same error for many steps.
Table 6: The percentage (%) of test-time verification errors (i.e., and 64) after reflective SFT. Additionally, we compute as the difference of how much reflective reasoning raises the performance over non-reflective reasoning, i.e. RMTP (RTBS) accuracy minus non-reflective accuracy.
Verification Type
Binary
Detailed
Reflective Exccution
RMTP
RTBS
RMTP
RTBS
Measurement
e-
A
c+
e-
64
e-
A
c+
A
ID Easy
19.3
4.4
1.3
14.9
4.9
224
10.2
18.3
+11.4
24.4
19.4
+222
Mult
ID Hard
3.8
37.6
-81
3.6
33.0
-17.2
0.9
6.9
+2.6
14.5
7.4
+0.6
OOD Hard
16.4
32.9
-1.5
6.0
22.5
-2.5
13.6
2.2
-0.2
13.2
2.4
-0.6
ID Fasy
9.9
35.2
-0.6
31.1
43.9
30.6
87.1
0.1
+1.3
85.1
0.1
Sudoku
ID Hard
21.1
31.0
-0.2
33.1
28.6
-0.3
82.8
0
0.1
79.4
0
-0.1
OOD Hard
60.3
7.5
60.2
13.4
87.9
84.5
ID Easy
25.1
5.9
-0.1
58.1
8.9
-0.4
30.4
3.7
00.7
28.7
7.5
-12
Mult
Hard
2.4
23.6
+5.3
26.0
339
3.3
25.1
+4.2
10.0
29.3
-1.0
OOD Hard
7.5
42.9
-1.1
18.0
61.7
-1.8
5.9
28.1
-0.4
10.9
28.2
-1.0
Easy
39.5
9.5
+4.7
40.4
11.5
+3.9
23.8
0.1
+27.5
46.7
0.3
+34.1
Sudoku
ID Hard
41.3
1.9
+5.4
56.0
6.7
+12.4
17.3
0.2
+11.7
22.1
0.3
+0.5
OOD Hard
78.5
0.8
+3.6
70.6
+6.3
31.5
0.1
+1.1
35.9
0.1
+2
ID Easy
11.3
8.6
+0.1
6.1
9.4
+0.0
15.7
2.1
+0.3
3.8
2.9
00.7
Mult
Hard
1.4
13.9
+11.5
16.9
+9.7
2.5
7.0
+10.5
4.4
7.2
+7.6
OOD Hard
1.3
86.4
+0.2
1.5
88.2
+0.2
8.5
18.3
+0.2
11.7
19.7
-2
16M
ID Easy
40.1
3.3
+0.8
10.1
4.7
-4.6
6.6
1.7
+6
9.1
6.4
+6.7
Sudoku
ID Hard
50.5
4.3
+3
37.2
9.4
+4.7
15.4
0.1
+11.0
10.6
0.6
+23.8
OOD Hard
75.2
4.2
+3.5
65.0
3.1
+5.1
28.3
0.1
+7.5
24.8
0.0
+13.7
Our full results provide more evidence for the findings discussed in Section 5.1
31

---

Learning to self-verify enhances non non-reflective execution for 9 out of 12 models (2 verification types, model sizes, and 2 tasks), such that accuracy does not decrease in any difficulty and increases in at least one difficulty.
RMTP improves performance over non-reflective exccution for all 4M and 16M models. However, RMTP based on binary verification fails benefit the 1M models, which suffer from a high e...
4M and 16M Sudoku models greatly benefit from RTBS, especially using detailed verification.
E.3
Results of GRPO
The complete results models after GRPO are given in Table To have a convenient comparison, (ahleepreeentt the difference of accuracy across Table 5 and Table showing that the difference of accuracy is caused by GRPO.
Table 7: The accuracy (%) of the 1M, 4M, and 16M transformers after GRPO.
Verification Type
None None
Binary
Detailed
Optional Detailed
Reflective Execution
None
RMTP
RTBS
None
RMTP
RTBS
None
RMTP
RTBS
ID Easy
52.6
96,2
95.9
95.7
53.0
49.5
45.1
48.6
47.7
48.8
Mult
Hard
11.6
50.0
44.0
42.0
11.4
9.7
8.1
12.2
12.7
12.6
OOD Hard
1.1
2.5
1.9
1.6
1.0
0.9
0,4
1.2
1.3
1.2
Easy
1.3
33.9
29.2
17.6
20.7
18.7
23.0
23.0
22.6
Sudoku
ID Hard
0
0.4
0.2
0
0.1
0
0.1
0.1
0
OOD Hard
0
ID Easy
98.0
98.6
98.7
98.8 8
98.2
98.0
98.4
98.2
98.4
98.6
Mult
Hard
73.6
77.0
76.7
63.0
64.3
63.2
63.9
66.8
66.1
OOD Hard
2.3
2.7
2.7
2.3
5.8
5.3
5.3
3.3
3.2
3.3
4M
Easy
58.7
93.8
97.2
96.7
57.8
85.3
92.2
77.0
94
98.2
Sudoku
ID Hard
3.2
43.9
53.8
58.1
5.6
24.7
47.7
21.4
37.7
61.3
OOD Hard
0.4
4.9
6.9
0
0.4
2.0
0
1.8
4.2
ID Easy
99.8
99.2
99.2
99.1
99.7
99.6
99.4
99.2
99.4
99.3
Mult
Hard
77.2
75.2
81.1
79.6
76.3
77.8
77.6
75.9
78.4
77.7
OOD Hard
1.8
1.3
1.8
1.8
8.4
8.2
7.4
6.0
5.5
5.6
16M
ID Easy
96.3
97.6
98.8
94.6
93.3
98.8
99.8
88.7
97.6
99.0
Sudoku
ID Hard
51.3
51.7
58.0
62.3
46.7
60.4
72.2
42.2
57.3
70.9
OOD Hard
0.7
0.7
6.0
7.8
0.2
6.7
12.0
0.2
6.7
11.1
Reflection usually extends the limit of RI. For reflective models, GRPO samples experience Co'Ts through RMTP, where self-verification V and the forward policy form of a self-verifying policy Ā. By comparing the RMTP results (columns 3, 6, and 9) with the non-reflective model (the first column) in Table 7 find that GRPO usually converges to higher accuracy solving ID-Hard problems in RMTP. This shows that having reflection in long CoTs extends the limit of RL, compared to only exploiting a planning policy.
jointly optimized in the
Interestingly, optional detailed verification generally demonstrates higher performance after GRPO than mandatory verification. A probable explanation is that mandatory verification may cause the reasoner to overly rely on reflection, which stagnates the learning of the planning policy.
Overall, our full results provide more evidence to better support our findings discussed in Section 5.2
RL enhances 24 out of 42 ID-Harr results in Table by no less than 3% (measured in absolute difference). However, only 8 out of 42 OOD-Hard results are improved by no less than 1%
In 9 an increase of e is observed in 20 out of 25 cases where e decreases by more than 5% (measured in absolute difference).
E.3.1 The verification errors after GRPO
Furthermore, we also present the estimated errors of verification after GRPO in Table 9 in order to investigate how self- verification evolves during RL. Our main observation is that if model has
32

---

Table 8: The difference of accuracy (%) of the 1M, 4M, and 16M transformers after GRPO. Positive
values mean that GRPO raises the accuracy of the models above SFT.
Reflective Training
None None
Binary
Detailed
Reflective Execution
None
RMTP
RTBS
None
RMTP
RTBS
TD Easy
29.0
+0.4
+1.4
+2.33
+31.0
+16.1
+20.9
Mult
ID Hard
+9.6
-2.
-0.6
+6,5
+9.2
+4.9
+5.3
OOD Hard
+0.1
-1.2
-0.3
+0.4
0.0
+0.1
0.0
IM
ID Easy
0.1
+0.99
-3.2
42.1
+00.2
+2.0
-0.
Sudoku
Hard
40.11
-0.1
+0.2
-0.1
+0.1
OOD Hard
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Easy
+6.0
+0.9
+1.1
+1.5
4-3.7
44.2
45.1
Mult
ID Hard
28.3
+16.7
+14.8
423.7
+9.6
+16.7
+0.8
OOD Hard
0.1
-02
+0.9
+1.2
+2.1
+2.0
+2.6
4M
ID Easy
+6.5
+1.7
+0.4
+0.7
+3.4
+3.4
+3.7
Sudoku
Hard
+3.0
+7.5
+4.8
+0.4
+7.8
+2.0
OOD Hard
0.0
+0.4
+4.9
+6.9
-0.7
0
Easy
+0.6
+0.4
+0.3
+0.3
+0.5
+0.1
+0.9
Mult
ID Hard
11.3
+10.0
+4.4
+4.7
+10.4
+14
+4.1
OOD Hard
0.7
+0.2
+0.5
+0.5
-0.8
-12
+0.2
16M
ID Easy
+0.6
+0.5
+0.9
+2.1
+0.3
-02
+0.1
Sudoku
ID) Hard
+2.5
+1.6
+4.9
+7.5
0.2
+2.5
+1.5
OOD Hard
+0.3
0.2
+1.6
+1.8
0.5
115
-24
high c. before GPRO, then GRPO tends to reduce e and also increases e+. This change in verification errors a rather superficial (lazy) way to obtain improvements. If the model faithfully improves verification through RL, both types of errors should simultaneously decrease such case occurs only in the ID-Easy difficulty or when e already after SFT. This highlights a potential retrograde of verffverification ability after RL.
Table 9; The percentage (%) of test-time verification errors (i.e., e. and e4) after GRPO. The arrows HLtH (increase) and "L" (decrease) present the change compared to the results in SFT (Table
Verification Type
Binary
Detailed
Reflective Exccution
RMTP
RTBS
RMTP
RTBS
Error Type
e+
e
e+
e_
c+
e_
e+
ID Easy
6x,12.5
3311.1
so.9.9
3.41.4
124422.6
17.11.11
35;27.9
176, 1.8
Mult
Hard
16.;20..3
17.420.0
10.10.6
187,19.33
546455.5
4612.3
42.116.66
1.,
OOD Hard
412157.6
16131.3
#0246.2
1.524..0
539167.5
164118.6
57.1
19.1
IM
Easy
12;11.1
17136.9
13.118.0
4.014..9
0.187.22
0010.0
00187.1
0440.5
Sudoku
ID Hard
29124.0
09130.1
5.127.6
0.429.00
0.1833.7
0o,0.0
a.,80.3
00,0.0
OOD Hard
3.163.4
0.18.33
4.555.77
19.3
03188.4
0o.0.00
a6185.1
0..0.0
ID Easy
25122.6
48.1.1
302127.9
7.11.8
21.1.9.3
3o.0.7
50123.7
63.0.7
Mult
ID Hard
53.555.55
21811.8
s06156.6
28.12.3
20.2
20.15.0
22.032.00
24x
OOD Hard
60.67..5
28.618.66
s2s170.5
42.5
15.111.66
20917.2
33.464.3
229,5.3
4M
ID Easy
79131.6
3216.3
28,43.2
7713.8
11,112.3
1371.4
27.1
19r2.2
Sudoku
Hard
78.770.0
0s11.4 .4
22158.2
4712.0
45/12.8
16
92112.9
0.10.2
OOD Hard
69185.4
0.10..1
11.0181.6
0210.4
2.129.44
0,0.1
59,30.0
0.r0.22
Easy
4217.1
7a11.4
0415.7
7..
81_7.6
1910.2
7.6
27,0.2
Mult
ID Hard
7999.3
12811_1
67:8.5
1.611.3
22.225.2
3913.1
186723.0
43,2.9
OOD Hard
80.1
s7.139.3
#92190.7
16.141.8
$60154.5
12515.8
464158.1
14.45.00
16M
ID Easy
245164.6
6219.5
25.615..7
1.1
21-8.7
0611.1
33,5.88
54,1.0
Sudoku
Hard
25.3775.8
o0]4.3
164153.6
2017.4
0s,15.9
ao10.1
24r13.0
0.4
OOD Hard
79183.1
3s10.7
127177.7
21.1.0
78136.1
0o.0.11
68:31.6
0.n0.1
33

---

E.3.2
The planning correctness rate after GRPO
Table 10:
The planning correctness rate (p) before and after GRPO. Each result is reported by
USFT
PGRPO-
Task
Verification Type
Model Size
ID Easy
ID Hard
OOD Hard
IM
70.2 - 81.7
54.4 + 59.5
42.9 41.9
Detailed
4M
98.3 + 99.5
68.4
79.1
35.0 + 38.0
16M
99.7 7 99.99
80.0 4 85.9
47.9 - 43.4
Mult
IM
98.8 99.1
81.2
80.3
42.7
38.6
Binary
4M
99.3 7 99.7
77.6 7 89.9
57.1 + 48.1
16M
99.4 99.8
79.6 + 85.1
75.2 + 44.8
IM
34.1 7 33.0
13.2
12.4
9.0 7 8.6
Detailed
4M
85.0 + 86.8
65.2 + 72.0
70.1 + 70.3
16M
98.6 + 98.1
92.5
94.0
84.9 7 83.9
Sudoku
IM
59. + 60.3
36.6
+ 36.1
19.5 7 19.9
Binary
4M
97.3 7 97.8
80.2
81.4
74.5 - 70.9
16M
99.0 7 99.2
88.5
+ 85.1
68.4
64.6
We also report how GRPO influences the step-wise planning ability, measured by μ (defined in Section 4. across various tasks, verification types, and model sizes. Shown in Table TO GRPO increases the planning correctness rate j in most ID cases, except for the Sudoku models with binary verification. This indicates that the proposed steps are more likely to be correct and further reduces the overall penalties of false positive verification, making optimistic verification bias (a high e.+ exchange for a low e_) even more rewarding. In particular, the planning ability shows almost no improvement in OOD problems.
E.3.3 Reflection frequency of optional detailed verification
To show how GRPO adapts the reflection frequency for optional detailed verification, Figure 12 shows the reflection frequency of 1M and 16M transformers before and after GRPO, and the reflection frequency of the 4M model previously shown in Section 5.2 Similarly, Figure 13 shows the reflection frequency for IM, 4M, and 16M models in Sudoku.
According results in Table 3 reflective execution does not improve performance for the 1M model, implying its weakness exploring correct solutions. Therefore, GRPO does not much incentivize reflection for the IM model. Contrarily, it greatly encourages reflection for 4M and 16M models, for they explore more effectively than the 1M model. These results align with the discussion in Section 5.2 that RL adapts the reflection frequency based how well the proposing policy can explore higher rewards.
E,4 Reflection frequency under controlled verification error rates
To investigate how verification error rates (e... and influence the reflection frequency in GRPO, we ran a controlled experiment in which the error rates were fixed by intervening with expert verifications. After each time the transformer generated a non-empty verification, we replaced the verification sequence with the expert verification, where randomized noise is injected achieve the prescribed false-negative rate and false-positive rate
We used the 4M Mult model and GRPO (sampling temperature 1.25) for 25 epochs in the in-distribution setting. We measured the fraction of steps at which the model invoked non-empty reflection ('reflection frequency")) after 25 epochs. Especially, we are interested in how reflection frequency changes, given a low e = 0.1 or high e = 0.4. In both cases, we set e 0.1. The results are follows:
Using a low e = 0.1, the reflection frequency increases to 59.8% after 25 GRPO epochs.
Using a high e 0.4, the reflection frequency drops to 0.0% after 25 GRPO epochs. That is, the model learns completely disuse reflection.
Discussion. When the verifier rejects many correct steps (high e-), the model learns to avoid invoking reflection, driving the observed reflection frequency to nearly 0%. Conversely, when is
34

---

Before GRPO
After GRPO
38
A6
28
22
22
28
23
24
36
32
42
39
32
2
33
28
23
17
20
23
2
28
25
32
10
44
number of y digits
3
27
20
22
19
14
15
17
17
16
27
34
20
14
13
26
33
38
38
42
5
30
32
25
22
21
16
15
20
19
22
24
26
32
36
39
42
37
34
28
21
20
14
19
19
17
30
36
34
38
44
A9
38
36
number
7
8
32
22
18
23
18
14
13112
12
8
26
30
40
40
31
10
24
23
20
17
14
14
10
29
30
34
38
30
10
10
9
10
2
5
10
number x's digits
number x's digits
(a)
1M
Before GRPO
After GRPO
15
19
15
5
5
3
311
72
72
71
70
68
70
70
number of y's digits
78
5
4
415
80
79
78
79
81
82
88
8
3
74
80
80
83
85
88
92
93
7
4
6
numbe
7 98
81
84
86
90
94
95
96
96
S
10
87
94
96
96
10
10
96
97
10
6 9
10
10
9
7
6
10
77
86
90
93
96
97
97
96
95
2 3 5
8
10
3
6
8
9
10
number of x's digits
number of x's digits
(b)
16M
Figure 12: The hot-maps of reflection frequency (%) of 1 1M and 16M multiplication models before and after GRPO, which uses sampling temperature of 1.25. All models are tested using RMTP execution.
low (with the same e4), reflection becomes beneficial and the model increases reflection usage (here to 60%). Intuitively, reducing excessive false negatives shortens CoT lengths and makes reflection more rewarding; when is large, the model can trade off reflection for no-reflection policy (which corresponds the extreme e 0, e = 1), thereby avoiding costly rejections. This experiment demonstrates that the model learns to reduce by strategically bypassing verification.
E.5 Results of PPO
discussed in Appendix B.I we prefer GRPO over PPO for tiny transformers, as the value model in PPO increases computational cost and introduces additional approximation bias in computing advantages.
Table presents the reasoning accuracy after PPO, and Table gives the difference compared to the SFT results in Table Our results show that PPO is much weaker than GRPO. Although PPO effectively improves the non-reflective models, the performance of reflective reasoning deteriorates after PPO. To explain this, self-verification reasoming steps causes higher complexity of the value function, which may obfuscate tiny transformers. Overall, we suggest that GRPO is more suitable algorithm to optimize reflective reasoning for tiny transformers.
35

---

Before GRPO
After GRPO
1.0
reflection frequency (56
(%)
0.6
0.6
0.4
reflection
0.4
0.2
0.2
0.0
0.0
number of blanks
number of blanks
IM
Before GRPO
After GRPO
1.0
1.0
reflection frequency (%6
reflection frequency (%)
0.8
0.8
0.6
0.6
0.4
0.4
0.2
27
45
54
18
27
45
number blanks
number of blanks
(b)
Before GRPO
After GRPO
1.0
1.0
reflection frequency (%)
reflection quequency (%)
0.8
0.6
0.2
0.2
0.0
0.0
18
27
36
45
54
9
18
27
36
45
54
number of blanks
number of blanks
(c) 16M
Figure 13: The histograms of reflection frequency of 1M, 4M, and 16M Sudoku models before and after GRPO, which sampling temperature of 1.25. All models are tested using RMTP execution.
36

---

Table 11: The accuracy (%) of the 1M, 4M, and 16M transformers after PPO.
Verification Type
None
Binary
Detailed
Optional Detailed
Reflective Execution
None
None
RMTP
RTBS
None
RMTP
RTBS
None
RMTP
RTBS
ID Easy
39.6
96.5
94.1
90.6
28.3
30.1
27.2
37,9
49.0
44.4
Mult
ID Hard
7.8
49.6
43.7
32.2
2.4
3.1
2.4
5.9
9.6
7.3
OOD Hard
1.1
2.6
1.8
1.2
0.7
0.8
0.7
1.0
1.0
0.8
IM
ID Easy
1.7
36.1
33.7
5.6
17.3
20.6
20.1
23.8
21.9
20.1
Sudoku
Hard
0.4
1.0
0
0.1
0
0
OOD Hard
0
0
0
0
0
Easy
97.7
95.5
98.6
93.8
96.6
95.7
94,9
97.2
96.9
94.6
Mult
ID Hard
63.0
52.8
68.6
54.7
54.0
54,6
45.5
58.7
61.7
56.8
OOD Hard
2.2
2.9
1.6
5.3
3.9
2.2
4.4
3.3
3.7
4M
ID Easy
56.4
88.4
97.3
97.6
49.3
82.1
80.6
76.2
94.1
97.3
Sudoku
Hard
28.6
47.4
15.1
35.9
35.3
55.6
OOD Hard
0.2
1.6
3.3
3.1
0.4
0.9
0
1.1
2.7
Easy
99.0
99.0
98.2
98.5
98.7
97.8
99.0
99.5
99.2
Mult
ID Hard
64.8
62.9
75.7
71.9
63.2
68.6
65.6
65.1
77.1
74.6
OOD Hard
1.9
1.0
5.4
5.6
16M
ID Easy
96.5
91.8
97.3
96.7
87.6
98.1
98.9
94.5
96.7
97.1
Sudoku
ID Hard
49.0
41.0
51.4
52.7
34.7
55.7
66.3
47.8
53.8
53.0
OOD Hard
0.6
2.4
4.0
0
1.1
2.0
0
3.8
2.9
Table 12: The difference of accuracy (%) of the 1M, 4M, and 16M transformers after PPO. Positive values mean that PPO raises the accuracy of the models above SFT.
Reflective Training
None None
Binary RMTP
Detailed RMTP
Reflective Execution
None
RTBS
None
RTBS
ID Easy
+16.0
+0.7
-0.4
-2.8
+6.3
-3.3
+3.0
Mult
ID Hard
+5.8
3.1
-0.9
-3.3
+0.2
-1.7
-0.4
OOD Hard
+0.1
-1.1
-0.4
+0.0
-0.3
+0.0
+0.3
1M
ID Easy
+0.3
+3.1
+1.3
+3.2
-0.1
+1.9
+0.7
Sudoku
ID Hard
+0.0
+0.1
+0.9
+0.0
-0.1
+0.1
+0.0
OOD Hard
+0.0
+0.0
+0.0
+0.0
+0.0
+0.0
+0.0
ID Easy
+5.7
2.2
+1.0
-3.5
+2.1
+1.9
+1.6
Mult
Hard
+25.7
+6.4
+1.7
+10.6
+7.0
+3.1
OOD Hard
+0.0
+0.2
+1.1
+0.5
+1.6
+0.6
-0.5
4M
ID Easy
+4.2
3.7
+0.5
+1.6
-5.1
+0.2
-79
Sudoku
ID Hard
-33
12.3
+1.1
55.6
5.2
-1.8
99.8
OOD Hard
+0.0
+0.2
+1.6
+3.3
+2.7
3.6
5.8
ID Easy
+0.1
+0.2
+0.1
-0.6
-0.7
-0.8
-0.7
Mult
ID Hard
-1.1
2.3
-1.
3.0
27
-7.8
-7.9
OOD Hard
0.6
0.1
0.1
0.2
0.1
-1.3
+0.3
16M
ID Easy
+0.8
5.3
0.6
4.2
-54
0.9
00.8
Sudoku
ID Hard
+0.2
-9.1
-1.7
-2.1
12.2
-22
-4.4
OOD Hard
+0.2
-0.
-20
-20
0.7
-7.1
-12.4
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our title, abstract, and introduction clearly state our main claim that trans- formers can benefit from self-verilying reflection. Our theoretical and experimental results support this claim.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We mention limitations the conclusion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
38

---

Answer: [Yes]
Justification: The main paper describes the assumptions of our theoretical results. The proof is provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in the appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We include necessary information to reproduce our results in the appendix, such as hyper-parametert model architecture, data examples, and detailed implementation.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
39

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Full code is in the supplementary materials. No data is provided as it is generated by the code. "README.md" introduces the commands to perform the complete pipeline and reproduce our results. We will open-source our code once it is formally accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips.c... cttpppccccccccccccccccccccccclct guwdes/ www.ooouaaiiiiinnoooiiioieeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Most relevant hyper-parameter parameters and experiment details are in the appendix. Full settings are clearly defined our code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report emror bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification:
is too expensive to run multiple instances our experiments, which include training 78 models under various settings (sizes, tasks, verification types, etc). Each model is tested using at most 3 different executions. Given our limited resources. it would take several months to compute error bars. Since our paper focuses on analysis instead of best performance or accurate evaluation, it acceptable not to include error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
40

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We roughly describe the computational resource used in the appendix. Since our models are very small, this paper can be easily reproduced by a single NVIDIA GPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics sttiics/ttts:///t
Answer: [Yes]
Justification: As far as we may perceive, this research does not involve human subjects or negative societal impacts.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
41

---

Justification:
This paper focuses on the fundamental analysis of reasoning instead and is tied to no practical applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-us should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Assets used in this paper are cited in the paper. The appendix mentions the version of the asset and the license.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
42

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssi thoode com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release assets besides our code.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing research with human subjects.
Guidelines:
43

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question:
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Although this research related LLM reasoning, we focus on tiny trans- formers. The appendix includes the evaluation of LLMs, yet these results do not impact our core methodology and originality.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy (https://neure) http:////...a.eeeeee//e2000550 for what should or should be described.
44


Reviews:
[{"review_id": "YWdbTEA28i", "reviewer": "Reviewer_bmmN", "summary": "This paper investigates how small transformer models, without relying on natural language, can perform self-verifying reflection to improve multi-step reasoning. The authors introduce a minimal reasoning framework and provide theoretical guarantees that reflective execution improves accuracy when verification errors are bounded. Empirical results on multiplication and Sudoku tasks demonstrate that tiny transformers (1M–16M parameters) can achieve near-LLM performance using this reflective mechanism. The work also reveals that while reinforcement learning encourages reflective behavior and improves in-distribution performance, it largely exploits statistical patterns without enhancing verification capabilities.", "questions": "**Questions for the Authors**\n\n1. How does your self-verifying reflection framework perform when integrated into a pre-trained transformer model, rather than training from scratch?\n2. Have you considered comparing your method to natural language-based self-reflection approaches in terms of both accuracy and inference cost?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper is well written and clearly organized. The figures and wording are effective, making the technical content easy to follow.\n2. The authors conduct a thorough analysis of the proposed method, combining theoretical guarantees with strong experimental validation.\n3. The topic is timely and important. The work provides insightful observations on self-verifying reflection, which could have significant implications for improving reasoning in large language models.\n\n**Weaknesses**\n\n1. It remains unclear how the proposed method performs when applied to an already pre-trained model. This is a relevant concern for practical adoption, as many real-world models are not trained from scratch under controlled settings, but are instead adapted from general-purpose, pre-trained LLMs.\n2. It is unclear how this method compares to other variants of CoT reasoning. How does this minimalistic reflection framework compare to natural language-based self-reflection COT in terms of (1) accuracy and (2) inference efficiency? Such comparisons would help contextualize the advantages of the proposed approach.", "was_revised": true, "final_justification": "I appreciate author's effort in addressing all my concerns. I would love to see this paper in the final proceedings.", "rebuttal": "Dear Reviewer,\n\nThank you very much for your thoughtful and constructive feedback. We appreciate your recognition of the strengths of our work and the opportunity to address your concerns.\n\n## Regarding Weakness 1 and Question 1: Integration with Pre-trained Models\nFirst, we aim to highlight that our analytical framework naturally extends to general reasoning tasks. For general LLM reasoning, a state is defined as the sequence of all prior reasoning steps:  \n\n$$\nS_t = (R_1, R_2, \\ldots, R_t)\n$$  \n\nAn LLM may not explicitly verify every step; if a step lacks explicit verification, we can default to viewing it as positively verified (accepted). Thus, our framework constitutes a minimal abstraction of natural LLM reflection. That said, a key characteristic of general LLMs is their ability to implicitly segment steps using linguistic markers (e.g., sentences or paragraphs), enabling the entire chain-of-thought (CoT) to be generated via token-wise processing. As a result, the CoT structure remains rather implicit in LLM outputs, which complicates comprehensive assessment. This motivates us to explicate the reasoning patterns in small transformers and conduct an in-depth analysis.  \n\nWe acknowledge the important gap between our current experiments and practical applications involving general-purpose, pre-trained LLMs. We are actively pursuing follow-up work to apply insights from this study to larger models with billions of parameters, which is ongoing. An intriguing preliminary finding is that natural language does not necessarily improve verification accuracy in  reasoning tasks; its flexibility can introduce noise when representing identical states or reasoning steps. We plan to carefully investigate these implications for general LLM applications in future work and will expand the discussion of these limitations and future directions in the revised manuscript.\n\nWe would also like to clarify why we have not applied our method directly to pre-trained models at this stage. As discussed in the paper, evaluating reasoning methods on pre-trained LLMs presents significant challenges:\n\n1. While we have extensively tested various scenarios with small transformers, the computational cost of training and evaluating large LLMs restricts us to limited settings, which may not reveal comprehensive patterns.\n2. Pre-trained LLMs’ ability to understand and generate natural language complicates precise performance evaluation, especially for verification errors. Our tiny models are trained on controlled data with strict output formats, enabling straightforward rule-based evaluation. In contrast, LLMs often produce correct but format-divergent outputs, making detailed assessment difficult.\n\nGiven these challenges, we chose to focus on fundamental aspects of small transformers under constrained training to map out key phenomena. This foundational understanding will guide future research on applying these insights to large pre-trained models. While some findings may not directly transfer, identifying what to investigate is a crucial first step.\n\n## Regarding Weakness 2 and Question 2: Comparison to Natural Language-Based Reasoning\n\nWe appreciate your interest in how our minimalistic reflection framework compares to natural language-based self-reflection methods in terms of accuracy and inference efficiency. For task-specific applications, we believe our approach offers competitive accuracy without sacrificing computational efficiency:\n\n- **Accuracy:** Our experiments demonstrate that tiny transformers achieve strong performance relative to natural language-based reasoners. For example, our 4M-parameter model outperforms the o3-mini model, which uses natural language reflection, on Sudoku tasks (see Appendix E.1 for LLM results). This suggests that natural language may sometimes introduce redundancy or noise that does not enhance accuracy in specific reasoning domains. We will revise the manuscript to have a direct comparison between  these natural-language reasoners and our best-performing tiny transformers in the same table.\n- **Inference Cost:** Our minimalistic framework enables efficient inference on extremely small models that do not understand natural language. For instance, batched inference of 256 queries with a 4M-parameter model can run on a laptop with only 4GB VRAM, facilitating extensive experimentation. In contrast, natural language reasoning typically requires much larger models and greater computational resources.\n\nThat said, natural language approaches also have their own advantages:\n\n- They offer greater flexibility, supporting multi-task scenarios and more casual query expressions.\n- Theoretically, natural language provides a superset of reflective behaviors, potentially enabling higher performance bounds.\n- Natural language simplifies engineering by leveraging pre-trained domain priors to decompose chain-of-thought reasoning into logical steps and states via token-by-token prediction.\n- It supports revision-based reflection by explicitly expressing verification errors, although recent work [^1] suggests that LLMs may not revise effectively in practice.\n\nWe will make sure to add discussion about this comparison in the revised manuscript. However, we also emphasize that our goal is not to compete directly with natural language reasoning paradigms but to provide a minimalistic framework that captures their core reflective mechanisms in a clearer, more analyzable form. The strong empirical performance of our approach is a welcome surprise rather than the primary objective. For applications demanding higher accuracy, our framework can be extended with more sophisticated reflection mechanisms, such as a formal reasoning language, in future work.\n\n---\n\nWe sincerely appreciate your valuable comments once again. Should you have any further questions, please feel free to raise them in our subsequent discussions.\n\n[^1]: He, Y. _et al._ (2025) ‘Can Large Language Models Detect Errors in Long Chain-of-Thought Reasoning?’ arXiv. Available at: https://doi.org/10.48550/arXiv.2502.19361"}, {"review_id": "jNbmIlKdfV", "reviewer": "Reviewer_xGjd", "summary": "This paper investigates how LLMs use reflection and self verify the reasoning chain-of-thoughts (CoTs) which leads to empirical improvements. To analytically understand self verifying reflection process, they use a reasoning framework with small transformer models. They found that their small transformers with self-verification archives performance of LLMs in integer multiplication and Sudoko. They also theoretically show that self-verifying reflection guarantees improvements if verification errors are properly bounded.", "questions": "1) Do the authors have any intuition on why in Figure 6, for OOD hard problem with binary verification smaller model (1M) performs better than larger models (4M and 16M)?\n2) Can the authors fine-tune larger pretrained models such as Llama or Qwen-7B to test whether the RL findings generalize at that scale?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n1) To analytically understand self verification reflection the authors use small transformers which mimics the performance of LLMs. The use of small models reduces the cost of comprehensive experiments.\n\n2) They theoretically show that a self-verifying reflection step improves reasoning as long as the verifier’s errors are properly bounded, so even a lightweight verifier suffices, rather than relying on an expensive one.\n\n3) They also found that a reinforcement-learning (RL) finetuning with reflection can be useful only if the reasoner’s exploration strategy covers a diverse set of candidate solutions; without sufficient exploration, the RL signal can not discover the added value of reflection.\n\nWeaknesses\n1) They did the analysis with tiny models, which shows limited generalisation ability and RL finetuning didn't improve it.\n\n2) No large scale finetuning experiments are done on reasoning benchmarks to show whether their analysis transfer well to LLMs or not.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you very much for your thoughtful and constructive feedback. We greatly appreciate your careful reading and insightful comments.\n\n## Response to Weaknesses\n\n### Weakness 1: Limited Generalization of Small Models and RL Fine-tuning\n\nWe did not claim that small transformers or RL fine-tuning would have strong generalization. Since our models are trained on task-specific data rather than large-scale natural language corpora, limited generalization is expected and does not diminish the core contributions of our work. Moreover, our findings help clarify a common misconception that RL fine-tuning necessarily improves generalization.\n\nThat said, we agree that generalization is an important direction. Our results already indicate that learning self-verification can modestly enhance generalization (e.g., the 16M Mult model with detailed verification). We plan to further explore methods to improve generalization in small models in future work.\n\n### Weakness 2: Lack of Large-Scale Fine-tuning Experiments on Pretrained LLMs\n\nWe acknowledge the gap between our current experiments on small transformers and practical applications involving large, pretrained LLMs. We are actively pursuing follow-up work to extend these insights to billion-parameter models.\n\nPreliminary results suggest that natural language’s flexibility can sometimes introduce noise in verification, which complicates reasoning accuracy. We intend to investigate these effects thoroughly and will expand the discussion of these limitations and future directions in the revised manuscript.\n\nWe also want to clarify why we have not yet applied our methods directly to pretrained LLMs:\n\n1. Training and evaluating large LLMs is computationally expensive, limiting the scope of experiments and making comprehensive analysis challenging.\n2. Pretrained LLMs generate natural language outputs that often deviate from strict formats, complicating precise, rule-based verification. In contrast, our small models are trained on controlled data with strict output formats, enabling straightforward evaluation of verification errors.\n\nGiven these challenges, we focused on small transformers to establish foundational understanding. This groundwork will guide future research on scaling these methods to large pretrained models. While some findings may not transfer directly, identifying key phenomena is a crucial first step.\n\n## Response to Questions\n\n### Question 1: Why Does the Smallest Model (1M) Outperform Larger Models (4M, 16M) on OOD Hard Problems with Binary Verification?\n\nThis is indeed an intriguing and somewhat surprising result. We hypothesize that learning binary verification acts as a strong regularizer, encouraging the model to extract more effective, generalizable features. This effect is more pronounced in smaller models, where many parameters must serve both forward reasoning and verification tasks. In other words, the parameter overlap between reasoning and verification is larger in small models, so improvements in verification directly enhance reasoning generalization.\n\nIn contrast, larger models have more redundant parameters, allowing verification skills to develop in parameter subspaces orthogonal to those used for forward reasoning. As a result, verification learning may not improve the reasoning parameters as effectively, leading to lower OOD performance gains. This issue is the most evident for simple binary verification form, and may be addressed with more sophisticate verifications.\n\nWe will include this discussion in the revised manuscript.\n\n### Question 2: Can Larger Pretrained Models Such as LLaMA or Qwen-7B Be Fine-tuned to Test RL Findings at Scale?\n\nTesting our findings on large pretrained models is exactly our next step. As explained in our response to Weakness 2, resource constraints and evaluation challenges prevented us from including such experiments in this paper. Although it seems straightforward to shift from tiny models to these larger models, the engineering is quite different. More importantly, our current framework focuses on analytic simplicity and may not sufficiently explore the emergent portential of LLMs in solving flexible tasks using reflection, so we suggest that it would be more meaningful to fine-tune them in another study with a more sophisticated framework.\n\nFortunately, we are now equipped to pursue follow-up research on large-scale settings. However, developing effective and efficient evaluation methods for LLM-based reasoning and verification remains a significant challenge.\n\nWe apologize for not being able to provide large-scale LLM results within this rebuttal phase but look forward to sharing such results in future work.\n\n---\n\nWe sincerely hope these responses address your concerns and clarify the scope and contributions of our work. Thank you again for your valuable feedback. Should you have any further questions, please feel free to raise them in our subsequent discussions."}, {"review_id": "EFiN4IDB1I", "reviewer": "Reviewer_oXtR", "summary": "This paper investigates how self-verifying reflection enhances chain-of-thought (CoT) reasoning in small-scale transformer models. The authors demonstrate theoretically and experimentally that even tiny transformers can achieve LLM-level performance on tasks like integer multiplication and Sudoku. The study also shows that while reinforcement learning (RL) improves in-distribution performance and encourages reflection, it tends to optimize for shallow statistical patterns rather than genuinely improving the model's ability to detect errors.", "questions": "The main concern, as noted in the weaknesses section, is that conclusions drawn from small-scale models on narrowly defined tasks may not generalize to larger models or more complex, real-world tasks.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- Authors use a minimalistic reasoning framework with tiny transformers to study complex behaviors like reflective CoT, enabling controlled, low-cost analysis.\n- **Comprehensive and Rigorous Evaluation**: Authors combine *formal proofs* with extensive experiments across model scales, tasks, training methods (SFT, RL), and reflection strategies (RMTP, RTBS).\n- The experiments demonstrate interesting findings that self-verification improves planning even without test-time reflection, and that RL promotes reflection by shifting error types rather than enhancing verification.\n\n**Weaknesses**\n- **Limited Generalizability**: Results from small-scale, non-linguistic models may not extend to full-scale LLMs in natural language settings.\n\n- **Narrow Task Scope**: Experiments are confined to structured tasks like integer multiplication and Sudoku, limiting relevance to broader reasoning challenges.", "was_revised": true, "final_justification": "I am largely satisfied with the submission and will maintain my score at 4. However, I would not give a higher score due to my lack of familiarity with other related work.", "rebuttal": "We sincerely thank you for your thoughtful and constructive feedback.\n\n## Reply to Concern 1: Lack of Large-Scale Results\n\nFirst, we aim to highlight that our analytical framework naturally extends to general reasoning tasks. For general LLM reasoning, a state is defined as the sequence of all prior reasoning steps:  \n$$\nS_t = (R_1, R_2, \\ldots, R_t)\n$$  \nAn LLM may not explicitly verify every step; if a step lacks explicit verification, we can default to viewing it as positively verified (accepted). Thus, our framework constitutes a minimal abstraction of natural LLM reflection. That said, a key characteristic of general LLMs is their ability to implicitly segment steps using linguistic markers (e.g., sentences or paragraphs), enabling the entire chain-of-thought (CoT) to be generated via token-wise processing. As a result, the CoT structure remains rather implicit in LLM outputs, which complicates comprehensive assessment. This motivates us to explicate the reasoning patterns in small transformers and conduct an in-depth analysis.  \n\nWe appreciate the reviewer’s recognition of the gap between our analysis on small transformers and practical applications involving large pretrained LLMs. We are actively pursuing follow-up work to extend these insights to billion-parameter models.\n\nPreliminary findings indicate that the flexibility of natural language can introduce noise in verification, complicating reasoning accuracy. We plan to investigate these effects thoroughly and will expand the discussion of these limitations and future directions in the revised manuscript.\n\nWe also wish to clarify why we have not yet applied our methods directly to large LLMs:\n\n1. Training and evaluating large LLMs is computationally expensive, limiting the scope of experiments and making comprehensive analysis challenging.\n2. Pretrained LLMs generate natural language outputs that often deviate from strict formats, complicating precise, rule-based verification. In contrast, our small models are trained on controlled data with strict output formats, enabling straightforward evaluation of verification errors.\n\nGiven these challenges, we focused on small transformers to establish a foundational understanding. This groundwork will guide future research on scaling these methods to large pretrained models. While some findings may not transfer directly, identifying key phenomena worthy of further investigation is a crucial first step.\n\n## Reply to Concern 2: Narrow Task Scope\n\nWe believe that the choice of structured tasks such as integer multiplication and Sudoku is appropriate and does not significantly limit the relevance of our findings. The explicit reasoning structure in these tasks enables efficient and clear analysis, and we expect our insights to generalize to broader applications.\n\n**Our minimalistic framework also applies to general natural-language reasoning.** For general LLM reasoning on unstructured tasks, a state can be defined as the sequence of all previous reasoning steps:\n$$\nS_t = (R_1, R_2, \\ldots, R_t)\n$$\nThese steps may be separated by paragraphs (`\"\\n\\n\"`), splitters (`\"---\"`), sentences, or fixed token counts. Some LLM reasoners explicitly use special tokens to delimit reasoning steps. Therefore, our reflection framework extends naturally to general reasoning tasks without explicit structured states, and the theoretical analysis remains applicable.\n\n**Why focus on explicitly structured tasks?** Structured tasks allow us to identify minimal state representations, so that in the step generation\n$$\nS_t \\xrightarrow{\\pi} R_{t+1}\n$$\nthe model receives a concise prompt. These short prompts are more suitable for small transformers and computationally efficient. Additionally, structured tasks provide straightforward ways to verify the correctness of each step, enabling precise measurement of error types such as false positives and false negatives.\n\nWe emphasize that **structured chain-of-thought reasoning implicitly exists in general LLMs**. When attending to a long prompt containing all previous steps, only a subset of tokens typically receive significant attention weights (assuming a well-trained model), while redundant information is ignored. These influential tokens effectively form a minimal state representation of the reasoning process. Thus, although our analysis uses simple tasks with explicit structures, it offers valuable insights for broader reasoning problems.\n\nIn this paper, we avoid unstructured reasoning tasks because (1) they generally require large models, which are computationally expensive, and (2) verifying the correctness of each reasoning step is challenging.\n\n---\n\nWe sincerely hope these responses address your concerns and clarify the scope and contributions of our work. Should you have any further questions, please feel free to raise them in our subsequent discussions."}, {"review_id": "Mi57YVliiK", "reviewer": "Reviewer_NCEg", "summary": "The paper proposes a framework to study the propensities of R1-style reasoning models to learn certain behaviours like self-reflection during training in easily verifiable environments like Sudoku and integer multiplication.\n\nWithin this framework, the paper theoretically shows that self-verification only helps when the FPR and TNR are below a fixed, bounded value. The authors also explore when does using a search tree for chain of thought becomes beneficial and provide a lower bound on the search depth based on the verifier's performance. \n\nThe authors empirically evaluate their framework and theoretical claims by studying how 1-16 million parameter transformers behave when trained in a similar way to reasoning models. They observe that while reflection boosts the performance of the transformers by default, RL optimisation generally modifies the verifiers to accept many actions, especially in OOD environments.", "questions": "I have listed down specific experiments and questions I had, along with the main strengths and weaknesses for clarity and continuity. The most important parts for me are:\n1. To address why the acceptance rates increase, and provide some information about how the model's policy to suggest next steps changes. \n2. To study when the model chooses to use self-reflection further. Particularly when the rejection rate is high and the planning policy is good.", "limitations": "For most parts, yes. Addressing how likely the claims are to generalise to practical applications is required.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The framework is well-built, and the claims seem theoretically sound. It seems useful to quickly explore new ways for training reasoning models. \n- Very well written and easy to follow\n\n---\n\nWeaknesses:\n- Parts of the experiments done are unlikely to generalise to Deepseek R1-style reasoning models:\n    - Most reasoning models have poor models for verifying their claims effectively (as the authors noted in the paper). This usually results in 'overthinking' and exploring/rejecting many trajectories emerging during training (especially in Deepseek r1). \n        - This seems to be analogous to high error rates for the verifier and a large search depth. Are there any bounds for RTBS with a poor verifier as well?\n        - In contrast, in the paper, I see the verifiers oddly have a much larger acceptance rate (state-action pairs it classifies as being positive/correct) after RL. Is there any reason for this dissimilarity? Is it possible to plot the value of $\\mu$ and the change in error rates?\n        - Can we compare the error rates in this work with those of reasoning models using previous works like [He et al.](https://arxiv.org/pdf/2502.19361)?\n    - In many practical tasks, reflection is not done after every step/regularly. Either due to it being hard (similar to why MCTS didn't work for deepseek r1), or the language model just learns this policy. Therefore, exact recursive backtracing, like in RTBS, might not be what is happening. However, this only affects a part of the motivation, and this could be potentially important for other types of CoT training. \n        - Maybe adding some randomness to which states are reflected on can simulate an imperfect verifier like this.\n        - Another important factor here is studying the propensity to use self-reflection when $\\mu$ and $e_+$/$e_-$ change. Entire RL runs seem expensive, but artificially changing the values/keeping them fixed to see if the frequency changes after a few epochs seems reasonable. \n- Slightly unclear result:\n    - Moving verifiers to classify many states as positive seems like RL is trying to circumvent the verification step. The verification step still looks to be doing something useful. Maybe plotting the number and type of states pruned/rejected from this step before and after RL will make things clearer.\n\n---\n\nOverall: This is a technically sound work, and the framework proposed definitely has good use cases. There could be some more experiments/ablations to simulate more realistic scenarios. However, this paper still provides valuable insights.", "was_revised": true, "final_justification": "I am keeping the same score as the preliminary review. The discussion addressed roughly all of my concerns, but it does not warrant a score improvement, as the scope/impact/usefulness is the same as before.", "rebuttal": "We thank the reviewer for carefully reading our paper and providing valuable comments.\n\n> **Are there any bounds for RTBS with a poor verifier as well?**\n\nA trivial bound indeed exists. First we notice that when $m \\to +\\infty$, RTBS reduces to RMDP (non-traceback), so the RMTP's bounds also hold for RTBS, given **sufficiently large** $m$. Then, for finite $m$, it is naturual that there eixsts a margin $\\varepsilon > 0$ such that $\\text{RMDPBound} - \\varepsilon$ becomes the RTBS bound, depending on how large $m$ is. Despite the existence, the exact RTBS bound can not be written analytically for arbituary $m$ and $n$. It can only be found numerically, using our recurrent expression of accuracy $\\tilde{\\rho}_m(n)$ in Proposition 1 (see Appendix C).\n\nTheorem 1 shows that if $m$ is chosen within a proper range and $f > \\alpha$ (depending on the task’s state representations), RTBS outperforms RMDP for the same false positive ($e_+$) and false negative ($e_-$) rates. In this case, the bounds for RMDP naturally become the bounds for RTBS, provided $n$ is sufficiently large and the task satisfies certain properties.\n\n---\n\n> **In the paper, verifiers have a much larger acceptance rate after RL. Is there a reason for this? Can you plot the value of $\\mu$ and changes in error rates?**\n\nThe increased acceptance rate indicates the verifier becomes more optimistic about step correctness. As discussed in Section 4 (rigorous theory in Appendix C.4 and C.5), false positives are less harmful than false negatives. The bound for $e_-$ becomes much stricter than $e_+$ considering the posterior risks in practice. More importantly, Appendix C.4 shows that a high false negative rate blocks reward paths, *greatly increase the number of total steps to reach the answer*. As a result, a large $e_-$ block rewards of true positives, since only limited computational resrouce is allowed in practical RL.\n\nIn the above case, reducing $e_-$ becomes very rewarding, as it shortens the CoT lengths so the problem can be solved within limited steps. Therefore, the reward of reducing $e_-$ surpasses the penalty of increasing $e_+$. This leads to a simple strategy to significantly increase reward gain: *an optimistic verification prior*. **This optimistic bias of verification is extremely easy to learn** --- By simply tuning a few parameters of the *output linear layer*, the transformer easily gives a high bias to the \"Accept\" token (meanwhile suppress the \"Reject\" token), whenever it needs to predict a verification token. This reduces $e_-$ and increases $e_+$, without learning any substantive new knowledge. \n\nWe note that, in RL, there is no direct supervision to learn verification, and the only signal is the final reward --- If there is a lazy way to increase rewards, RL will not learn the hard way. This explains why RL tends to maximize reward by learning such an optimistic bias.\n\n**Values of $\\mu$.**  We did not save runtime values of $\\mu$ and verification error rates during RL training, so plotting their training curves is currently not possible without rerunning experiments. However, we can provide evaluations of $1 - \\mu$ (planning error rate) before and after GRPO. Due to limited character counts, we here only present results for the multiplication task below, showing that GRPO reduces planning errors (increases $\\mu$) for 4M and 16M models in ID cases:\n\n| Setting | Easy ID | Hard ID | Hard OOD |\n|---------|---------|---------|----------|\n| Mult, Detailed Verification, 4M, **Before** GRPO | 1.68 | 31.60 | 65.03 |\n| Mult, Detailed Verification, 4M, **After** GRPO | 0.46 | 20.95 | 61.99 |\n| Mult, Binary Verification, 4M, **Before** GRPO | 0.67 | 22.40 | 42.93 |\n| Mult, Binary Verification, 4M, **After** GRPO | 0.33 | 10.10 | 51.86 |\n| Mult, Detailed Verification, 16M, **Before** GRPO | 0.27 | 20.00 | 52.06 |\n| Mult, Detailed Verification, 16M, **After** GRPO | 0.13 | 14.09 | 56.62 |\n| Mult, Binary Verification, 16M, **Before** GRPO | 0.60 | 20.44 | 24.85 |\n| Mult, Binary Verification, 16M, **After** GRPO | 0.24 | 14.91 | 55.23 |\n\nThe above indicates an increase in $\\mu$ after GRPO means the model produces more correct steps, which further reduces the overall penalties of false positive verification. This even makes an optimistic verification bias even more rewarding --- If $\\mu$ is low, then $\\tilde\\rho(n)$ quickly drops to nearly $0$ as $n$ increases, where this optimistic verification bias does not translate to a significant advantage. By increasing $\\mu$, the advantage of optimistic verification becomes more evident for large $n$.\n\nWe will add this discussion to the revised manuscript.\n\n---\n\n> **Can error rates in this work be compared with those of reasoning models like in He et al.?**\n\nCurrently, such a comparison is impractical because:\n\n1. He et al. measure \"effective reflection\" differently and do not discuss error rates explicitly.\n2. Estimating error rates with low variance requires many steps, which is expensive for LLM-based reasoners.\n3. LLMs reason in flexible natural language, complicating verification error evaluation. Enforcing strict formats may affect their performance.\n\n---\n\n> **Reflection is not done after every step in many practical tasks.**\n\nWe agree this is important. Our \"optional reflection\" setting simulates irregular reflection with randomness, and we find it often outperforms mandatory reflection after GRPO (see Table 7 in the Appendix). However, due to some exceptions and limited evidence, we did not include this in the main paper.\n\nYour suggestion to study how reflection frequency varies with $e_-$, $e_+$, and $\\mu$ is valuable. While artificially intervening on $\\mu$ is not straightforward, we can fix $e_-$ and $e_+$ by manipulating the verifier using the expert.  After each time the transformer generates a valid (non-empty) verification, we replace the generated verification with the expert verification, injecting noise to control $e_-$ and $e_+$. In this way, we now conduct a supplementary experiment to investigate how the reflection frequency is affected by fixed values of $e_-$ and $e_+$ in GRPO. Although we cannot show figures here, we briefly summarize the results for the 4M Mult model:\n\n- With $e_- = 0.4$ and $e_+ = 0.1$, the find that the reflection frequency drops to almost $0$ on in-distribution problems after 25 GRPO epochs.\n- With $e_- = 0.1$ and $e_+ = 0.1$, the find that the reflection frequency on in-distribution problems rises to 60% after 25 GRPO epochs.\n\nIt demonstrates that RL induces lower reflecton frequency if the verifier rejects many correct steps (a high $e_-$). This is reasonable, as adapting reflection frequence is an approach of trading-off between $e_-$ to $e_+$ (when the model does not reflect, it can be seen as $e_- = 0, e_+ = 1$). By having a low reflection frequency, it avoid rejection rates that are unecessarily high. This shows that reducing excessive rejection ($e_-$) in GRPO may be a crucial condition to incentivize high reflection frequency.\n\nWe will incorporate this discussion into the revised manuscript. Subject to computational resources, we also plan to provide more comprehensive results on this issue in the revision.\n\n---\n\n> **Does RL circumvent verification by classifying many states as positive? Can you plot the number and types of states pruned/rejected before and after RL?**\n\nIt is indeed unclear whether a \"positive\" classification means the verifier ignores computation or genuinely verifies the step.\n\nRegarding rejection rates:\n\n- The rejection rate of positive reasoning is $e_-$ (already presented).\n- The rejection rate of false reasoning is $(1 - e_+)$ (where $e_+$ is already presented).\n- We also recorded overall rejection rates, which decrease after GRPO, as shown below:\n\n| Setting | Easy ID | Hard ID | Hard OOD |\n|---------|---------|---------|----------|\n| Mult, Detailed Verification, 1M, **Before** GRPO | 39.61 | 48.93 | 50.40 |\n| Mult, Detailed Verification, 1M, **After** GRPO | 27.98 | 43.59 | 51.04 |\n| Mult, Binary Verification, 1M, **Before** GRPO | 5.30 | 48.61 | 61.96 |\n| Mult, Binary Verification, 1M, **After** GRPO | 1.48 | 34.88 | 61.00 |\n| Mult, Detailed Verification, 4M, **Before** GRPO | 4.78 | 47.74 | 71.04 |\n| Mult, Detailed Verification, 4M, **After** GRPO | 0.87 | 22.96 | 49.76 |\n| Mult, Binary Verification, 4M, **Before** GRPO | 6.33 | 40.14 | 64.15 |\n| Mult, Binary Verification, 4M, **After** GRPO | 1.16 | 9.41 | 32.04 |\n| Mult, Detailed Verification, 16M, **Before** GRPO | 2.32 | 25.10 | 54.75 |\n| Mult, Detailed Verification, 16M, **After** GRPO | 0.22 | 15.64 | 44.84 |\n| Mult, Binary Verification, 16M, **Before** GRPO | 9.07 | 31.21 | 89.43 |\n| Mult, Binary Verification, 16M, **After** GRPO | 1.41 | 14.82 | 67.70 |\n\nWe would appreciate clarification if the reviewer meant a different type of plot regarding rejected states.\n\n---\n\nWe sincerely hope these responses address your concerns. Should you have any further questions, please feel free to raise them in our subsequent discussions."}, {"review_id": "LZh9vLf9Z1", "reviewer": "Reviewer_NVDB", "summary": "This paper investigates how small-scale Transformers can enhance chain-of-thought (CoT) reasoning through a “Self-Verifying Reflection” mechanism without relying on natural language. The authors propose two fundamental reflective mechanisms: Reflective MTP (RMTP) and Reflective Trace-Back Search (RTBS), which enable the model to detect and reject incorrect steps during the reasoning process. By training models with varying parameter scales on integer multiplication and Sudoku tasks, the authors demonstrate that, under reasonable constraints on verification error, self-verification can improve reasoning accuracy.", "questions": "1.The training pipeline depends on an “expert verifier” to label the correctness of each CoT step. Have you evaluated the accuracy of this verifier? Could its errors introduce systematic bias during training?\n2.The RTBS method requires setting a backtrack width $m$. Have you conducted sensitivity analysis on the choice of $m$? During inference, how does the model determine whether backtracking is needed? Have you considered an adaptive mechanism?\n3.Theoretical analysis assumes each reasoning step can be labeled as a positive or negative state. In real-world scenarios, how would you approximate the partitioning of S⁺ₙ and S⁻ₙ?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\t1.The proposed “Reflective MTP” and “RTBS” frameworks integrate verification mechanisms into the reasoning sequence, allowing small models to perform efficient and minimalistic self-reflection without natural language.\n\t2.The chosen tasks are well-designed, aligning with the capacity boundaries of small models while highlighting the benefits of CoT structure. The experimental validation conditions are clearly defined.\n\t3.The introduction of a trace-back strategy for retrying previous steps significantly improves the success rate in Sudoku tasks, empirically supporting the theoretical claim that complex problems benefit from backtracking.\n\nWeaknesses:\n\t1.During the Reflective SFT phase, the authors rely on an external rule-based expert verifier for supervision but do not provide evidence of the verifier’s accuracy or analyze its impact on training convergence.\n\t2.Although GRPO is used in the reinforcement learning phase, results show that RL primarily improves performance on in-distribution (ID) data, while verification ability degrades (e.g., increased false positive rate e⁺), suggesting that the model may be learning to bypass reflection to avoid penalties rather than improving planning strategies.\n\t3.While the theoretical section is mathematically rigorous, it is built on highly idealized state partitions (e.g., S⁺ₙ and S⁻ₙ), which are not observable in real tasks, limiting the practical applicability of the theorems.", "was_revised": true, "final_justification": "The authors have provided clarifications to several of our earlier concerns in the rebuttal, which helped improve the overall understanding of the paper.", "rebuttal": "We sincerely thank the reviewer for the thoughtful and constructive feedback.\n\n## Weakness 1 and Question 1\n\nWe would like to clarify that the expert verifiers used in our experiments are effectively 100% accurate. Our tasks, such as Sudoku and integer multiplication, have well-defined and structured states. Since the models are trained from scratch on task-specific data with a constrained output format, the expert verifier can reliably parse the output and rigorously check the reasoning states against clearly defined rules.\n\nWhile an imperfect expert verifier would increase error rates ($e_-$ and/or $e_+$) of the learned model, the system remains functional as long as these errors are properly bounded. As discussed in the paper, perfect verification is not required for RMDP or RTBS to improve performance, so learning from an imperfect verifier is not a critical issue.\n\n## Weakness 2\n\nWe acknowledge that the observed limitation of reinforcement learning (RL) is a valid concern. However, this reflects a general challenge with RL rather than a shortcoming of our work specifically. Our intention was to explore the impact of RL on reflective reasoning, not to claim that RL substantially improves planning.\n\nIn fact, reporting that RL may encourage the model to bypass reflection to avoid penalties is an important contribution of our paper, as this could also be the case of DeepSeek-R1 and other LLMs trained with RL. Further, addressing this issue and improving RL to prevent such behavior could be an important direction for future research, especially in the context of general LLM reasoning.\n\n## Question 2\n\nThe traceback is needed on a state if there are $m$ proposed steps rejected on this state. Additional theoretical insights on the choice of backtrack width $m$ are provided in Appendix C.3, Proposition 3. It shows that selecting $m$ such that $\\frac{1}{\\mu(1 - e_-)} < m < \\frac{1}{f}$ ensures that the accuracy drop remains stable as the problem scale $n$ grows large. If $m$ falls outside this range, the success rate $\\tilde{\\rho}_m(n)$ tends to zero as $n$ increases.\n\nUsing the recurrent formula from Proposition 1 (Appendix C.2), we have implemented a simple program to plot success rates based on the parameters $\\mu$, $e_+$, $e_-$, $f$, problem scale $n$, and the RTBS width $m$. Unfortunately, we cannot include image links here, but we plan to release this code upon acceptance and add a related discussion in the revised manuscript. Our key observations are as follows:\n\n- A small $m$ causes $\\tilde{\\rho}_m(n)$ to decline sharply when $n$ is small. In contrast, a higher $m$ lets $\\tilde{\\rho}_m(n)$ drop faster as $n$ grows large.\n- The optimal $m$ to maximize $\\tilde{\\rho}_m(n)$ for large $n$ is the greatest integer within the interval\n\n$$\\left(\\frac{1}{\\mu(1 - e_-)}, \\frac{1}{f}\\right),$$\n\nif such an integer exists.\n\n**Regarding adaptive choice of $m$:** In this work, we focus on a minimalistic design and therefore do not employ an adaptive strategy for selecting $m$. However, based on the observations above, it is possible to extend our approach by adapting $m$ according to the problem scale $n$—for example, using a larger $m$ when $n$ is small. We thank you for providing this valuable comment, and plan to add some discussion about the adaptive $m$ is the revision.\n\n## Weakness 3 and Question 3\n\nWe agree that the binary partition into $S_n^-$ and $S_n^+$ is an idealization that may not hold in all real-world scenarios. The purpose of this partition is to provide a clear and accessible theoretical framework so readers can understand our results intuitively.\n\nA more general formulation of accuracy $\\rho$ using Bellman equations is discussed in Appendix C.1. However, solving for $\\rho$ in this setting requires sophisticated methods such as dynamic programming, making it difficult to derive concise conclusions.\n\nTo better accommodate real-world cases, future work could explore soft labeling schemes (e.g., continuous values) instead of coarse binary partitions (if possible, in the revised manuscript). For example, this soft value can be defined as *the value function under an optimal policy*. The verification ability may be defined as the expected Q function of accepted steps. Intuitively, we expect similar conclusions that bounded verification errors still enable performance gains. However, a rigour analysis would be significantly more complex. Even with our ideal setting, deriving accuracy properties under reflection is already challenging.\n\nTo the best of our knowledge, no other studies have tried to given similar analysis to this self-verifying reflection for LLM reasoning. We believe that establishing a groundwork with a simple, clear model is a critical first step that can inspire further research extending these results to more advanced and realistic settings.\n\n---\n\nWe sincerely hope this clarifies the concerns raised and demonstrates the rigor and potential of our approach. Thank you again for your valuable feedback. Should you have any further questions, please feel free to raise them in our subsequent discussions."}]

Author rebuttal:

Meta-review: The reviewers have reached a consensus on the acceptance of this paper. Although some reviewers did not participate in the discussion, the period was effective in addressing the concerns raised, thanks to the authors’ successful responses. All reviewers acknowledge its significant contribution to the community, mainly through its novelty and a well-organized manuscript with thoughtful insights. While some reviewers noted minor weaknesses related to evaluation, this AC believes the paper’s strengths far outweigh these issues, which can be addressed in a revision. This AC concurs with the reviewers’ positive views and recommends acceptance.
Decision: Accept (poster)