Sample Complexity and Representation Ability of Test-time Scaling Paradigms
Authors: Baihe Huang
Shanda Li
Tianhao Wu
Yiming Yang
Ameet Talwalkar
Kannan Ramchandran
Michael I. Jordan
Jiantao Jiao
Venue: ICLR 2026 Poster (2026)
Keywords: Large Language Models
Test-time Scaling
Sample Complexity
Representation Theory
Primary area: learning theory

Abstract: Test-time scaling paradigms have significantly advanced the capabilities of large language models (LLMs) on complex tasks. Despite their empirical success, theoretical understanding of the sample efficiency of various test-time strategies---such as self-consistency, best-of-$n$, and self-correction---remains limited. 
In this work, we first establish a separation result between two repeated sampling strategies: self-consistency requires $\Theta(1/\Delta^2)$ samples to produce the correct answer, while best-of-$n$ only needs $\Theta(1/\Delta)$, where $\Delta < 1$ denotes the probability gap between the correct and second most likely answers. 
Next, we present an expressiveness result for the self-correction approach with verifier feedback: it enables Transformers to simulate online learning over a pool of experts at test time. Therefore, a single Transformer architecture can provably solve multiple tasks without prior knowledge of the specific task associated with a user query, extending the representation theory of Transformers from single-task to multi-task settings. 
Finally, we empirically validate our theoretical results, demonstrating the practical effectiveness of self-correction methods.

Published as a conference paper at ICLR 2026
SAMPLE COMPLEXITY AND REPRESENTATION ABIL- ITY OF TEST-TIME SCALING PARADIGMS
Baihe Huang', Shanda Li,, Tianhao Wu', Yiming Yang², Ameet Talwalkar Kannan Ramchandran', Michael I. Jordan', Jiantao J.
Deept. of Electrical Engincering and Computer Sciences, University of California, Berkeley School of Computer Science, Camegie Mellon University Datadog
"Nvidia
Correspondence to: baihe_ haine_huang@berree.ee edu, shandal@ca. cmu. edu.
ABSTRACT
Test-time scaling paradigms have significantly advanced the capabilities of large language models (LLMMs) complex tasks. Despite their empirical success, the- oretical understanding of the sample efficiency of various test-time strategies- such as self-consistency, best-of-n,, and self-corrrcioon-remaee work, we first establish separation result between two repeated sampling strate- gies: self-connistency requires ((1/A²) samples to produce the correct answer, while best-of-n only needs ((1AA), where Á < 1 denotes the probability gap between the correct and second most likely answers. Next, we present an expres- siveness result for the self-correction approach with verifier feedback: it enables Transformers to simulate online learning over a pool of experts at test time. There- fore, single Transformer architecture can provably solve multiple tasks without prior knowledge of the specific task associated with a user query, extending the representation theory of Transformers from single-task multi-task settings. Fi- nally, we empirically validate our theoretical results, demonstrating the practical effectiveness of self-correction methods.
limited. In this
INTRODUCTION
Over the past several years, Large Language Models (LLMs) have witnessed remarkable advances, achieving unprecedented performance across a broad spectrum of applications (Brown el all 2020, Bubeck etall 2023: Chowdhery at 2022). Driven by the paradigm of chain-of-thought (CoT) rea- soning (Weret 20224). the outputs of LLMs have not only grown in length but also in structural complexity. In particular, recent studies have demonstrated that scaling up computational resources during test time significantly enhances the groblem-solving capabilities of LLMs phenomenon known as test-time scaling (Brown al], 2024; Wu all 2024; DeepSeek-AA, 2025; OpenAl 2025)).
Various methods have been proposed to effectively utilize additional test-time compute, including self-consistency (Wang et al, 2022% Brown et all 2024; Nguyen et all 2024, Chen al ((228)
best-of-n sampling (Irvine al M123 Song al, 0124a: Munkhhaf et all 2025 Quu al,, [02
Sessa et all 2024), Monte Carlo Tree Search (MCTS) (Taan et all 2024; Zhang et al, 202241 Gan
et all 2022:
Wan all 2024: Chen et all 2024a: Lin et all 2025. and self correction (Madaan
et all
202% Welleck el all 2023: Chen el all 20240: Gou et all 2022, Zhang et all 20240 Kuman
all
2022).. Powered by test-time scaling paradigms, several reasoning models, such OpenAl-
ol
(OpenAl, 2024) and Deepseek-R1 (DeepSeek-Al, 2025), have achieved remarkable success in
many complex tasks (Cobhe
Н02 Hendrycks et al. 202T: Shi
Huang all
20246 Zhang et all 20248).
Despite these empirical advancements, the theoretical foundations of test-time scaling remain under- developed. While recent progress has been made in understanding the expressiveness and learnabil- ity of chain-of thothht reasoning (Feng all, 2023; Memill Sabharwal (023: loshi et all, 20255,, two fundamental challenges remain unresolved:
2024h:
Many test-time scaling approaches rely on repeated sampling from the same LLM to select final answer (Wang et al] 2023: Brown al. 2024; Iryine stall, 2023: Song all, 20)2

---

Published as a conference paper at ICLR 2026
J6: Spectral method
fg:
Finite-Element method
Solve the PDE...
def s..ver.._ 0.5
def FE, solver(.... 1
User Query
Action 1 =
Response
Reward
Action
Response
Reward
Figure 1: An illustration test-time online learning (figure adapted from all 2025)), where the Transformer progressively learns that finite-clement method solves the partial differential equation with higher accuracy.
Nguyen al. M024: hen et al 20246:
et al.
21255
Kimi 2023:
Munkhbat ef all
2025: Quu ct all 2024: Sessa ei all 2022)). Two dominant paradigms are: self-consistency,
which marginalizes reasoning paths and selects the most frequent answer; and best-of-n, which chooses the answer with the highest reward score. However, a rigorous understand- ing of their sample complexities is lacking. This raises the first question:
What the sample complexity of repeated sampling methods, particularly self-consistency and best-of-n?
2. Theoretical analyses of Transformers' expressiveness have largely focused on their ability to represent individual tasks (Dehghani al, 2018 Yun all, 2020), while their ability to express multiple tasks at the same time is under-studied. In contrast, practical LLMs have shown remarkable success in adapting to new, diverse tasks test time via self- correction (Madaan et all, 2023; Welleck et all 20233 Chen all 20244) Giu et all 2224 Zhang all 20244: Kumar et all 2024 Guo
2025) or In-Context Reinforcement Learning (Monea et all, 4(24) Toollende 2025: Song all 2025, Novikov et al, 2025).
This gap underscores need to understand how Transformers express multiple task-solving capabilities inherently and learn adapt their behavior the right task via test-time inter-
action. Therefore, we are motivated to pose the second central question:
How can we characterize the expressiveness under test-time scaling methods, especially in multi-task settings?
Our Contributions. This work addresses the challenges outlined above through two key con- tributions. First, we analyze the sample complexity of two prominent decoding strategies: self- consistency and best-of-n, in terms of the probability gap between the most likely (correct) and the second most likely model outputs. Our results reveal a fundamental separation in sample efficiency that highlights the advantage of the best-of-n approach.
Proposition 1.1 (Informal statement of Theorem 3.1 and Theorem (.2). Let A E (0, denote the difference between the Transformer's probability of producing the correct answer and the probability of the second most likely answer. Then, self-consistency requires ((1/A²) samples to reliably produce the correct answer, whereas best-of-n achieves the same with only ((1/A) samples.
Second, we investigate Transformer's capacity for self- ceff-correction. We demonstrate that Trans- former equipped with verifier feedback test time can implement online learning algorithms over pool of expert models, enabling it to adaptively identify the most suitable expert and ultimately generate a response that maximizes the reward. This process is illustrated Figure given the
user query (e.g. solve the PDE the Transformer f autoregressively generates sequence of actions (e.g., selecting the sixth expert) and responses (e.g.. constructing and applying spectral method solver), conditioned on the history of previous action-response pairs and their corresponding rewards (e.g.. solution error). Notably, this process relies solely on the Transformer f- whose architecture encapsulates the capabilities of all experts inperts-and the reward function. distinguishing it from traditional routing algorithms that explicitly query experts. As such, this mechanism allows single Transformer architecture to solve multiple tasks without prior knowledge of the specific task associated with user query.
B बह Au = in Ω x (0, with some boundary conditions),
2

---

Published as a conference paper at ICLR 2026
There exists generic way construct wider transformer f from any Transformer-bont based expert models fi...., fE such that, when provided with award-based feedback. f can generate sequence of responses where the t-th response has regret o(1).
Proposition 1.2 (Informal statement of Theorem A M.
Proposition has two key implications. First, it demonstrates that a Transformer can express multiple tasks within single architecture, extending beyond prior theoretical results that focus on single-task expressiveness. Importantly the construction is task-agnostic and independent of the specific expert Transformers used, making both the result and the underlying techniques of inde- pendent theoretical interest. Second, Proposition I.2 reveals fundamental distinction between self-correction and repeated-sampling paradigms. While repeated-sampling methods generate iden- tically distributed responses across attempts, self-correction provably allows the model to update its attempts based on verifier feedback, thereby increasing the probability of producing the correct answer inference progresses. We further validate these results through controlled experiments.
2 PRELIMINARIES
Transformers. In this work, consider attention-only Transformers defined as follows. Definition 2.1 (Transformer). We define Transformer model over vocabulary V tuple (0, (K(), Q, V )e{[H))ee()) 0,
where 0 : V > Rd is the tokenizer, pe : IRd x Vou + Rd a position encoder, K Q v Rddd are the key, query, value matrices over layers and H heads each layer, and is the output feature. The computation of a Transformer rolls out as follows:
h
1. For each == 1,... x pe(0(us): (1,
2. For each = I,..., L. compute each x((+1) for = I,..., n by
8 (1) (X,, X,)
H
exp
x x((+1)
v x-()
(1)
h=13=1
where (-) ) is the attention score defined by 8% t
(0)) x ((") =
T(K x
and
0 ー exp
()) (X.,,)) is the normalizing constant.
3. The output probability is given by P vx) = (oftmax("(y)
V.
In particular, we assume the softmax attention layer has precision if two attention scores 81,82 satisfy e <0 then e is treated as zero in the attention computation Eq. (II).
While classical positional encoders are solely dependent on the index of the current token (i.c. we may write pe(O(u,); .i..... v1) pe(O(u:); i)), recent advances (He all 2024; Zhang all 2024E, Golovveva et 20224) have extended this notion to incorporate set membership information of preceding tokens. This generalization proves crucial for enhancing the long-context capability required for effective self-correction. Motivated by this insight, we introduce the following notion of generalized position encoder.
Definition 2.2 (Generalized Position Encoder). We say that pc Rd x Do + Rd is a generalized position encoder w.r.t. a partition Vi,..., Vx of V if it maps an input feature in Rd and token sequence (of arbitrary length) "., . to a vector in Rd. so that only depends on the input feature and the membership of each in the sets VI..... VK. i..
pe(O(r:))e ..... v.) = pe (0(e:); (1 E vk)) (
Test-time scaling. In this work, study the following three strategies for test-time scaling.
3

---

Published as a conference paper at ICLR 2026
1. Self-consistency samples i..d. responses from the language model and chooses the most consistent answer, while marginalizing over the reasoning paths.
2. Best-of-n samples i.i.d. responses from the language model and chooses the answer with the highest score given by the reward model.
3. In the Self-Correctio paradigm, the Transformer autonomously generates a sequence of n responses, each conditioned the previous responses and their respective reward scores.
3 SEPARATION BETWEEN SELF-CONSISTENCE AND BEST-OF-N
In this section, study the sample complexity of self-consistency and best-of-n. Let denote the user query (e.g. a math problem) and denote the answer space; then for each answer o E O we define p(o) as the marginalized probability of generating o over all possible reasoning paths
p(o) = Σ
preasonngng path, olg)
reasoning path
where Py denotes the probability distribution of Transformer f.
To understand the sample complexity, we focus on the dependence on the following probability gap:
A p(o")
p(o)
oEO.oş0'
where o" denotes the correct answer If < O, then self-consistency fails to find the correct answer with high probability and the separation becomes trivial. Therefore, we focus on the setting where A > (i.e., the most likely answer is correct), which is also considered in prior theoretical work (Huang et all ()ZEF). Under this setting, we may assume without loss of generality that the reward function is maximized (only) at the correct answer, because p itself is such reward function satisfying this condition. Note that since p(o) is marginalized over reasoning paths, A does not imply that the correct answer be derived easily from greedy decoding.
Theorem 3.1 (Sample Complexity of Self-Consistency).. When 2 2log(1/6),
A A² self-consistency with
i..dd samples is able produce the correct answer with probability at least 1 8; When S S. there exists hard instance where self-consistency with n ii.d samples fails to produce the correct answer with constant probability.
Theorem 3.2 (Sample Complexity of Best-of-n).. When n 2 2log(1/6) best-of-n with n i.i.d. sam- ples is able to produce the correct answer with probability least 1- When S I there exists hard instance where best-of-n with n i.i.d. samples fails to produce the correct answer with constant probability.
By providing matching (up to logarithmic factors) upper and lower bounds the number of sam- ples, the above results establish the separation hetween self-consistency and best-of-n. While self- consistency requires ( 2) samples to produce the correct answer, best-of-n shows advantage by only requiring ( A) samples. Therefore, this theory corroborates the empirical findings that best-of-n generally leads better problem solving accuracy on reasoning tasks compared with self- consistency (Sum et all 2024; Wu et all, ((225))
EXPRESSIVENESS UNDER COLE-CORRECTION
key distinction between self-correction and the repeated sampling strategies discussed in the pre- vious section lies in the dependence structure of the generated responses: unlike repeated sampling, the outputs produced by self-correction are not i.idd.. Consequently, to analyze the sample efficiency of self-correction, we must first address fundamental question: can large language model (LLM), through self-correction. increase the likelihood of generating the correct answer? At its core, this question one of expressiveness whether is sufficient to support such improvement.
whether the Transformer architecture's 's representation capacity
If there multiple correct answers, we can let o² denote the set, and our results continue to hold in this setting.
4

---

Published as a conference paper at ICLR 2026
In this section, take first step toward analyzing the expressiveness of Transformers under the self-correction paradigm. Unlike prior work that focuses on expressiveness in the context a single task, study what call general purposs expressiveness: the ability to solve broad range of tasks. To this end, we introduce the concept of a General-Purpose Transformer-a construction that maps any collection of task-specific Transformers (experts) into single unified Transformer.
Purrpsse Transformer). We say that & is a General-Purpon Transformer of type (4,, (2) if it maps any set of Transformers with hidden size d and depth L. into another 'unified' Transformer with hidden size 1 d + l2 and depth I. + O(1).
Definition 4.1
A general-purpose Transformer provides a principled framework for constructing more powerful Transformer architectures by composing simpler, task-specific components. This meta-architecture enables single model to solve multiple tasks at inference time, representing significant advance- ment in our theoretical understanding of the expressive power of modern machine learning systems. Our goal is to investigate the general-purpose expressiveness of self-correction paradigms through the lens of general-purpon Transformers: specifically, how a Transformer can adaptively solve dif- ferent tasks during inference without prior knowledge of the task identity.
4.1 GENERAL-PURPOSE EXPRESSIVENESS
In this section, we present two auxiliary results that serve as building blocks for constructing general- purpose Transformers capable of solving multiple tasks. These results may also be of independent interest beyond expressiveness of self-correction.
fi: arithmetic
fi common sense
fj: chemistry (1)
fi history
The + 5 capital France is
Paris:
Columbus (3) Primary gas discovered
America
f
capital France is
Primary gas (4) Columbur (1)
nitrogen
(a)
Figure 2: (a): Illustration of Proposition A.21 In the first query, fa is called to solve the common sense problem by attending to only blue tokens. In the second query. Ji is called to solve the arithmetic problem by attending only red tokens. (b): Illustration of Proposition 4.4 In the first query, f2 called to solve the history problem by attending to only blue tokens. In the second query, fi is called solve the chemistry problem by attending to only red tokens. Importantly, these function calls occur implicitly within the internal computation of the unified Transformer architecture.
The first result addresses the setting in which multiple Transformers operate over distinct vocabular- ies, with each vocabulary corresponding to specific task. The objective is to construct a unified Transformer that uses the final token in the input sequence infer which task perform, and sub- sequently solves the task by attending only to the task-relevant tokens.
Proposition 4.2 (General-pure pprrpsse Expressiveness over Different Token Spaces). For any H. L, K, Nmax E Σ., V. n V/ = 0 (Vi * j jE {0} U [K]), there exists general- purpose Transformer & of type (O(K), Olog Nmax)) such that for any Transformers fx. (0, (e,pe, (K!!) kihe kije ki keh))e(w 9, Va) for K E [K]. the Transformer f = =f(f1... Φ(f1...., ffx sat- isfies the following property: for any token sequence U = ... Un such that n S. Nuax and there
(1)
exists one Us, Vo. we have
p7(-10) ((((1u)
where is the lask indicated by the last token: i.e., Un Vn. and u Vi ...i. where (ia im {i: U. E Vx3. is the sequence of tokens relevant to task K. Remark 4.3. The existence of Vig which does belong to any (Vihee serves the technical purpose of inducing atlention sink of all irrelevant experts to Vig- It may be achieved by assuming the user query always ends with the special token <eas>.
The following result considers a more challenging scenario which multiple Transformers operate across different tasks but share common vocabulary space. set of indicator tokens, denoted by
5

---

Published as a conference paper at ICLR 2026
Ω, is used to specify the intended task. The objective is to determine which task to execute based on the most recent indicator token. It then proceeds to solve the task by attending exclusively to the task-relevant tokens appearing before the first indicator token and after the last indicator token in the input sequence.
Proposition 4.4 (Multi-Tase Representation over the Same Token Space). For any H, L, K, Nmax E Z+,, token spaces n V Transformer Φ of type (O(K), O(lo), Nmax)) such that for any Transformers Sk
there exists a general-purpose
(0, pe, Riho Qkch
vloh krh) 0, V), E [K] over V. the Transformer j (fI,...,, satisfies the following property: for any token sequence U1 ... Un such that
(5I ... < {m) = (i: E 22 5m < n S Nmax
then we have
pÿ(-1o)= Ps, (-lu)
(2)
where ... -1mm Un is the token sequence obtained by omitting tokens from position E1 to Ems and is is the task indicated by token Vgm.
Remark 4.5. We observe that in both results above, reducing the type parameters is generally not feasible. The dependence on arises from the need to compute features for all K experts cor- responding to the user query. Since the model lacks prior knowledge of the task, it must encode all task-relevant information to preserve the ability to invoke any expert at inference time. The log(NNao (mNax)) scaling stems from the positional encoding: in order construct Nmax nearly orthogo- nal vectors, the positional embedding must have dimension at least log( Oog(Naan Nmax).
4.2 GENERAL-PURPOSE EXPRESSIVENESS OF TRANSFORMERS WITH CELF-CORRECTIO
In this section we state the main result that establishes general purpose expressiveness of Transform- ers with self- corretonret. We rely on the following notion of regret- segeet-miiiiization Transformer, which expresses the single task of finding the most rewardable action.
Definition 4.6 (Regret-Minimization Transformer). We say that a Transformer f achieves sim- ple regret reg(-) over reward function and action space A, if for any T E Z+, we have max EA r(a("))) E[r(ar)) & rog(T) where a1,.... or are generated in the following way:
a₂ py(-|a1, Fl, (1-1) 1), W 1.....?,
Y: = r(t),, 11 1..... T.
Essentially, the goal of regret- sinnett-inimzzztionn Transformer is to learn from a reward oracle and ulti- mately recommend an action that near-optimal, which related to concept commonly referred to as simple regret in the bandit literature (Even-Dar et all 2006 Carpentier & Valko, 2015 [amieson atal 24).4). To achieve this, the Transformer may implement strategies such mirror descent, upper confidence bounds, search-based algorithms, depending on the problem structure. As these procedures rely only on basic arithmetic operations, such Transformers can be constructed by apply- ing the universal approximation capabilities of Transformers etal 2026, Luo all 2022: Feng ct aLa 2023: Li ct 20246): For example, Lm et all (2023) provide constructions to approximate
upper confidence bounds and Thompson sampling algorithms with regret O(VT). Consequently, their construction is not the primary focus of this work.
The following theorem establishes the existence of a general- purpose Transformer that can simulate the behavior of set of expert Transformers (not necessarily over the same token space) through self-correction. Specifically, shows that such a unified Transformer can, at inference time, identify and invoke the appropriate expert to solve any task that the original experts can solve. The self- correction protocol is described in Algorithm M. wherein the unified Transformer autorogressively generates actions and responses, after which the verifier is queried obtain reward signals. Through this process of trial and error, the model effectively "learns" at inference time, using the verifier to minimize regret and adaptively select the correct expert.
Theorem 4.7 (Regret Minimization via Self- Ceff-Correcton). For any H, L, K, Nmax E Z4. token spaces Vo, Vi,..., VK. A (IA) K) such that Vo. V = (UK Vk), and A are disjoint, and reward -eneral-purpose purpose Transformer ó of rype (O(K), Olog N Nmax)) such that given any of Transformers denoted as follows,
function r, there exists a general

---

Published as a conference paper at ICLR 2026
Algorithm 1 Self-correction with verifier
1: procedure GENERATION(4)
... denotes the user query.
2: prompt +
3: fort I,..., T do
4: (0 P prompt)
b a designates which expert to use in f-th iteration Update the prompt autoregressively. represents token concatenation.
5: prompt < prompt/a!
6: for i 1.... do
7:
p7( prompt)
b Generate 1-th response autoregressively Update the prompt autoregressively
prompt + promptlu
u EOS then
10:
Break
11:
,()) <- r(g, ( prompt prompt/r())
b Query verifier to obtain reward of f-th response
12: Return
expert Transformers: fa (0,pe, pe, (K such that one of the expert [u- achieves X-suboptimal reward:
kch Qiah vi )netm, Vx) for & E [K].
Eu-ss-(--e u)] max r(g, u²) - =VV
Dnggret-Minmiizatiinn Transformer: fo (0, pe, K!! Q Von
0th hell 0, U A)
that implements bandit algorithm over the reward function to and action space A with simple regret reg(t), where ro(a) = Euwsfalllglrr u)] denotes the average reward of responses generated by the a-th expert,
then the Transformer f fi...., satisfies the following property: for any prompt
01 up. the response sequence (12) (.)) generated by the protocol in Algorithm W has total length & Nmax then we have
max r(g, u²) E[r(g, u x EV
Remark 4.8. While the general-purpont Transformer i can applied construct the brute-force Transformer f that simply tries every expert, we note that the generality of Definition H. allows construct more powerful Transformers beyond brute-force search. Leveraging the structures in the problem and the expert pool, it is entirely possible to identify the correct expert using & K Toster eLal 2022))
trials (Russo & Van Roy, 2018
As consequence of Theorem 1.7, we obtain Transformer architecture that provably produce a final answer that nearly maximizes the reward. This means that the unified transformer can solve K distinct tasks at inference time, without requiring prior knowledge of which task the user query pertains to. Notably, the construction of such an architecture is rmmeral-purpose in that it is indepen- dent of the specific tasks, reward functions, or expert policies. To our knowledge, this constitutes the first theoretical study of Transformers' expressiveness under this setting of self-correction. Further- more, our theory aligns with the empirical finding that LLMs can progressively optimize outcome rewards during test-time (Qu et all 2025 Song et all 2025: Tooliense 2025; Monea ()24)).
EXPERIMENTS
In this section, we conduct synthetic experiments to show that Transformers can self-correct with verifier feedback.
5.1 EXPRESSIVENESS OF DELF-CORRECTIO
Data generation. We aim to construct a test problem with complex prompts such that correctly solving the problem in the single-term generation is challenging. In this case, self-correction can
Code:
7

---

Published as a conference paper at ICLR 2026
play critical role if Transformers have such capacities. Specifically, in synthetic problem, the prompt is the concatenation of the following two components:
Instruction: 3-SAT problem, e.g.
(~ V xi 22) (~ xIV 2g V22) (~ 24 02V 13) A...
Data: string composed of characters from the set (a, b).
The ground truth target defined as follows: the 3-SAT problem in the instruction is satisfiable, the model should copy the string in the data part in the output; otherwise, the model should reverse the string in the output. In our experiment, we construct datasets using 3-SAT problems with variables and 20 clauses. The lengths of the data strings set to 5. We generate 10000 instances for training and 512 instances for evaluation. In the training set, we control the ratio of satisfiable and unsatisfiable 3-SAT instructions to 9:1, while the test the ratio is imbalance encourages that models fail to answer the question correctly in the first attempt and thus elicit the self-correction behavior.
1:1. This label
Models and training configuration. We train a class of Transformer models of various sizes: [GPT-nano, GPT-micro, GPT-mini, Gopher-44M} with the Adam optimizer (Kingma Ba, 2015) for 5 epochs. More implementation details can be found in Appendix
Results. Test set accuracy across different inference settings shown in Figure We note that model performance plateaus at 63. 19% when there is no self- correction test time, with no improvement from in- creased model size. By contrast, when models are equipped with verifier signals to enable self-correction, test accuracy improves substantially, demonstrating the efficacy this mechanism. Crucially, larger mod- els such as GPT-mini and Gopher-44M achieve near-perfect accuracy under self-correction, suggest- ing that sufficiently expressive Transformers capa- ble of implementing effective self-correction strategies. This empirical result supports theoretical findings.
Test accuracy comparison
100
03.00
99.15
Accuracy (9)
63.19
63.19
6319
40
W/o self-correction
1,33255 2.5
W/ self-correctiin
GPT-micro GPT-mini Gopher-44M
Figure 3: Accuracy comparisons differ- models with/without self-correction test time.
5.2 EVALUATION OF SAMPLE COMPLEXITY
Dataset. We conduct experiments on the AIME 2024 & 2025 datasets (Mathematical Association
of America, 2025),, which serve as real-world benchmark evaluating mathematical reasoning tasks. These datasets allow to measure not only the raw accuracy of different large language models (LLMs), but also the impact of verification- based strategies on sample efficiency.
Model configuration. We consider recent LLMs, including Qwen 1 7B, Qwen3 4B (Yang ctall 2025), and Llama-3, -.naa-3.2200 - ruct (Dubey et all, 2024), as candidate models. In ad- dition, Owen3-32B is employed an LLM verifier. This setup enables us to compare standard de- coding strategies (self-consie celf-consistency) with verification- based methods (best-of-n and self correctort...
Results. We compare the accuracy of self-consistency, best-of-n, and self-correction under differ- ent sample sizes. Notably, as summarized in Table II. best-of-n with only 4 samples consistently
Self-consistency (64 samples)
Best-of-n (4 samples)
Self-correction samples)
Model \ Method
Qwen3-1.7B
58.33%
59.68%
79.29%
Qwen3-4B
78.33%
80.58%
81.19%
Haaaa-3.2-B---
1.67%
4.84%
24.52%
Table Accuracy comparison of self-consistency, best-of-n, and self-correction methods on AIME
24 & 25 datasets.
8

---

Published as a conference paper at ICLR 2026
outperforms self-consistency with 64 samples, confirming the predicted gap in sample complexity. Furthermore, self-correction with verifiers achieves strong performance, highlighting the ability of LLMs to leverage verifier feedback effectively. These results show notable sample complexity gap between Self-consistency and Best-of-n and confirm that modern Transformer models are suf- ficiently expressive to implement self-correction mechanisms when combined with verifiers, thus validating our theoretical results in Section G and g.
6 RELATED WORKS
Theories of Transformers and Large Language Models. The success of Transformers and LLMs has motivated the study on their expressiveness. Existing research has shown that Transform- ers can implement simple functions such as sparse linear functions, two-layer neural networks, and decision trees (Garg all (022), gradient descent (Akyürek et all 2122; Bai all 2023; Von Os all 2023), automata (Liu at 2022; Zhao al 2023), Dyck languages (Bhattamishra et ell 2020a; Yao all 2021), Turing machines (Dehghani al. 2018; BhattamiShra all, 20206; Za:
heer 202E Perez et al 212T; Weteial 2022a), variational inference (Mer & Wil 2023). and
bandit algorithms all MIPX) Yun (2112)); atll (20222; Alhert at (2122)) Perrow
c all (2024l) establish universal approximation results under various settings. Edelman et all (2022);
Elhage et al. (2021); Ll (2021); Likhosherstov et all (20221) study representational capabilities
and properties of self-attention, the core component in Transformers. Feng et all (202)); al
(2024h) study the expressiveness of auto-regressive Transformers with chain-of-thought, Eddelmn all (2(022); Li all (20248); Botta et all (2025) study the sample complexity of Transformers. Re- cently, growing body of work has begun to explore the theoretical foundations of self-improvement large language models (LLMs). Song ct al. (20246) introduce the inneraation-erificcut gap as a key quantity governing scaling behavior. Huang et al. (2024t) propose a progressive sharpening framework in which the policy gradually shifts toward more confident responses. SSellur all (2025) draw on reinforcement learning theory to formally establish the advantages of verifier-based meth- ods. In contrast to these works, our results provide explicit sample complexity rates and tangible representation architectures, enabling more concrete understanding of the fundamental capabilities and limitations of test-time scaling paradigms.
Test-time scaling. Recent research has established the test-time scaling law of LLMs, illuminating a new scaling axis beyond training-time scaling laws (Kaplan et all 2021 Hotiman et all, 2022).. Existing approaches of scaling up test-time compute of LLMs can be broadly classified into two categories: (1) applying test-time time algorithms (aka inference-time algorithms) during LLM decoding (Brown all 2024; Wi all 20255 Snell et all, 2025); and (2) explicitly training LLMs to output long chain-of-thougle traces (DeepSek-AA, 2025; Kimi, 2025; OpenA], 2025: Yang et al, (0225). Many recent works focus on understanding and improving the effectiveness of test-time scaling empirically: Chen et all (21220) Aggarwal & Welleck (20225); Cuadron all (2025); Wang et al. (2025) study under-thinking, over-thinking, and length control in LLM reasoning. Chen ctal (202)) proposes to integrate self-verification and self-correction into sampling. Qu et all (2025) analyze optimizing test-time compute by introducing a meta reinforcement learning formulation. Seilm etall (2025) demonstrate that verification/RL. is important for optimal test-time scaling. Zhang all (2025) provide an extensive review of the test-time scaling landscape. In contrast, our work focuses on theoretical analyses of test-time scaling. In addition, our work provides theoretical explanation of In-Context Reinforcement I Learning (Song et all 2025. Toolense 2025% Monea et all (124)).
7 DISCUSSIONS
Our investigation reveals fundamental separation in sample complexity between self-consistency and best-of-n, providing theoretical support for the empirically observed superiority of the latter method. Furthermore, by introducing the framework of general-purpose expressiveness, we con- struet generic Transformer architectures capable of emulating online learning algorithms test time. This capability enables a single model to provably solve multiple tasks without task -ask-specffic adap- tation, thus extending our understanding of expressiveness to multi-task settings. Our experiments validate the theoretical separation and confirm that it requires additional model capacities for Trans- former to implement celf-correctio.

---

Published as a conference paper at ICLR 2026
REFERENCES
Pranjal Aggarwal and Sean Welleck. L1: Controlling how long a reasoning model thinks with reinforcement learning. In arxiv, 2025, URL httpt:://t/rtttttt www./orrg/ooooo abs/ 2005//5/0..0 04697.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst- case regret bounds. Advances in neural information processing systems, 30, 2017.
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou, What learning algo- rithm is in-context learning? investigations with linear models. arXiv preprint arXiv:2211. 156611 2022.
Silas Alberti, Niclas Dern, Laura Thesing, and Gitta Kutyniok. Sumformer: Universal approx- imation for efficient transformers. In Timothy Doster, Tegan Emerson, Henry Kvinge, Nina Miolane, Mathilde Papillon, Bastian Rieck, and Sophia Sanborn (eds.). Proceedings of 2nd An- nual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML), volume 221 of Proceedings of Machine Learning Research, pp. 72-86. PMLR, 28 Jul 2023. URL
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers statisticians: Prov- able in-context learning with in-context algorithm selection. arXiv preprint urXiv22306.06377 2023.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7096-7116, 2020a.
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of transformers and its implications in sequence modeling. In Proceedings of the 24th Conference on Computa- tional Natural Language Learning, pp. 455-475, 2020b.
Edoardo Botta, Yuchen Li, Aashay Mehta, Jordan T Ash, Cyril Zhang, and Andrej Risteski. On the query complexity of verifier-assister language generation. arXiv preprint Xii::2502.12123, 2025.
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXi::240..21787, 2024.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Ma- teusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Asso- ciates, Inc., 2020. hww.:t::://eeeeeeesssccco
files/paper/
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint 2333v:2303..2712. 2023.
Alexandra Carpentier and Michal Valko. Simple regret for infinitely many armed bandits. Inter- national Conference on Machine Learning, pp. 1133-1141. PMLR, 2015.
Guoxin Chen, Minpeng Liao, Chengxi Li, and Kai Fan. Alphamath almost zero: Process supervi- sion without process. In The eiihty- Annual Conference on Neural Information Processing Systems, 2024a. URL https:/ hetpp://////eeeeee///eeeee
wwt. forum 1d=Vaxxxx330KXX
Jiefeng Chen, Jie Ren, Xinyun Chen, Chengrun Yang, Ruoxi Sun, and Sercan Ô Ank. Sets: Leveraging velfiiciiinntoio and self-correction for improved test-time scaling. arXiv preprint arXiv:2501. 19306, 2025.
10

---

Published as a conference paper at ICLR 2026
Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, lon Stoica, Matei Zaharia, and James Zou. Are more LLM calls all you need? towards the scaling properties of com- pound AI systems. In Conference on Neural Information Processing Systems, 2024b. URL
ht.ts:://peenees ew. net Forum? d= C6RRLqx
Xingyu Chen, Jiahao Xu, Tian Liang, Zhiwei He, Jianhui Pang, Dian Yu, Linfeng Song, Qiuzhi Liu, Mengfei Zhou, Zhuosheng Zhang, al. Do not think that much for 2+ 3=? the overthinking of ol-like lims. arXiv preprint arXiv:2412.2118/ 2024c.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. International Conference on Learning Representations, 2024d. URL https:
/openrevee net foo.mmmidekufLx..0
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311 2022.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reicchrr Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv: 14168, 2021.
Alejandro Cuadron, Dacheng Li, Wenjie Ma, Xingyao Wang. Yichuan Wang, Siyuan Zhuang, Shu Liu, Luis Gaspar Schroeder, Tian Xia, Huanzhi Mao, et al. The danger of overthinking: Examin- ing the reasoning-action dilemma in agentic tasks. arXiv preprint arXiv:2502.08225,, 2025.
DeepSeek-AL. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning. In arXiv, 2025.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.0388 2018
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv e-prints, pp. arXiv preprint 2407.21783, 2024.
Benjamin I. Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In International Conference Machine Learning, pp. 5793-5831, PMLR, 2022.
Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai. Anna Chen, Tom Conerly, et al. A mathematical framework for transformer circuits. Transformer Circuits Thread, 1:1, 2021.
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. Advances in Neural Information Processing Systems, 36:70757-70798, 2023.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487 2021.
Zitian Gao, Boye Niu, Xuzheng He, Haotian Xu, Hongzhang Liu, Aiwei Liu, Xuming Hu, and Lijie Wen. Interpretable contrastive monte carlo tree search reasoning. In arXiv, 2024. URL
Shivam Garg, Dimitris Tsipras, Percy S Liang and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583-30598, 2022.
Olga Golovneva, Tianlu Wang. Jason Weston, and Sainbayar Sukhbaatar, Contextual position en- coding: Learning to count what's important. arXiv preprint arXiv:2405.188 18719, 2024.
11

---

Published as a conference paper at ICLR 2026
Zhibin Gou, Zhihong Shao, Yeyun Gong, yelong shen, Yujiu Yang, Nan Duan, and Weizhu Chen. CRITIC: Large language models can self-correct with tool-interactive critiquing. In International Conference Learning Representations, 2024. URL
id==x0038xxiek
Bradley Guo, Jingwen Gu, Jin Peng Zhou, and Wen Sun. Learning to self-correct through chain-of- thought verification. In Second Workshop on Test-Time Adaptation: Putting Updates to the Test! at ICML 2025, 2025.
Zhenyu He, Guhao Feng, Shengjie Luo, Kai Yang, Liwei Wang, Jingjing Xu, Zhi Zhang, Hongxia Yang, and Di He. Two stones hit one bird: Bilevel positional encoding for better length extrapola- tion. arXiv preprint arXiv:2401.1642/ 2024.
Dan Hendrycks. Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
URL httpps://openee 1
net.
2mOsCe.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hen- nigan, Eric Noland, Katherine Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Oriol Vinyals, Jack William Rae, and Laurent Sifre. An empirical analysis of compute-optimal large language model training, In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances Neu- ral Information Processing Systems, 2022. URL https: /OtEpss://penrevvi.. ew net/ did=
1 OAPR.
Audrey Huang, Adam Block, Dylan Foster, Dhruv Rohatgi, Cyril Zhang, Max Simchowitz, Jor- dan T Ash, and Akshay Krishnamurthy, Self-improvement in language models: The sharpening mechanism. arXiv preprint arXivv2412.0199) 2024a.
Zhen Huang, Zengzhi Wang, Shijie Xia, Xuefeng Li, Haoyang Zou, Ruijie Xu, Run-Ze Fan, Lyumanshan Ye, Ethan Chern, Yixin Ye, Yikai Zhang, Yuqing Yang, Ting Wu, Binjie Wang, Shichao Sun, Yang Xiao, Yiyuan Li, Fan Zhou, Steffi Chern, Yiwei Qin, Yan Ma, Jiadi Su, Yixiu Liu, Yuxiang Zheng, Shaoting Zhang, Dahua Lin, Yu Qiao, and Pengfei Liu. Olympi- carena: Benchmarking multi-disciplin cognitive reasoning for superintelligent AI. In Confer- ence on Neural Information Processing Systems Datasets and Benchmarks Track, 2024b. URL /ettps:/coperreee ew net. wtw.rr/wwwwee.eee//oouummmmm Fttp//ooommm1ayyamm/e
Robert Irvine, Douglas Boubert, Vyas Raina, Adian Liusie, Ziyi Zhu, Vineet Mudupalli, Aliaksei Korshuk, Zongyi Liu, Fritz Cremer, Valentin Assassi, Ptristie-Carol Beauchamp, Xiaoding Lu, Thomas Rialan, and William Beauchamp. Rewarding chatbots for real-world engagement with millions of users. In arXiv, 2023. URL httts:://aaxtt www.vorrgaaaa. abs /20/a/2333.m 06135.
Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lilucb: An optimal ex- ploration algorithm for multi-armed bandits. In Conference on Learning Theory, pp. 423 439. PMLR, 2014.
Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro. A theory of learning with autoregressive chain of thought. arXiv preprint arXiv:2503.0795 079322 2025.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08300 2020.
Kimi. Kimi kl.5: Scaling reinforcement learning with 1lms. In arXiv, 2025. URL AttDs://
arxiv. wttpoor///.....11/2222
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
12

---

Published as a conference paper at ICLR 2026
Aviral Kumar, Vincent Zhuang, Rishabh Agarwal, Yi Su, John D Co-Reyes, Avi Singh, Kate Baumli, Shariq lqbal, Colton Bishop, Rebecca Roelofs, et al. Training language models to self-correct via reinforcement learning. arXiv preprint arXiv:2409. 12917, 2024.
Shanda Li, Xiangning Chen, Di He, and Cho-Jui Hsich. Can vision transformers perform convolu- tion? arXiv preprint arXiv:2111.01353. 2021.
Shanda Li, Tanya Marwah, Junhong Shen, Weiwei Sun, Andrej Risteski, Yiming Yang, and Ameet Talwalkar. Codepde: An inference framework for llm-driven pde solver generation. arXiv preprini 2rXiv:2505.08783, 2025.
Yuchen Li, Alexandre Kirchmeyer, Aashay Mehta, Yilong Qin, Boris Dadachev, Kishore Papineni, Sanjiv Kumar, and Andrej Risteski. Promises and pitfalls of generative masked language model- ing: theoretical framework and practical guidelines. arXiv preprint arXiv:2407.2 1046, 2024a.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. In The Twelfth International Conference on Learning Represen- tations, 2024b. URL nttps: / wttp://wwww.eetoomneeeeee. http://oooouu///3/33W.M. 3MM
Valerii Likhosherstov, Krzysztof Choromanski, and Adrian Weller. On the expressive power of self-attention matrices. arXiv preprint arXiv:2106.03764, 2021.
Licong Lin, Yu Bai, and Song Mei. Transformers as decision makers: Provable in-context reinforce- ment learning via supervised pretraining, arXiv preprint arXiv:2310.08500 2023.
Qingwen Lin, Boyan Xu, Zijian Li, Zhifeng Hao, Keli Zhang, and Ruichu Cai. Leveraging con- strained monte carlo tree search to generate reliable long chain-of-thought for mathematical rea- soning, arXiv, 2025. URL https::/azzi..rrre
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts automata. arXiv preprint arXiv:2210. 10749, 2022.
Shengjie Luo, Shanda Li, Shuxin Zheng, Tic- Liu, Liwei Wang, and Di He. Your transformer may not be as powerful as you expect. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL nttps: //openreview. net. wttp:/eeee.ooomme/nnnneoee......
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback. Thirty-seventh Conference on Neural Information Pro- cessing Systems, 2023. URL
Mathematical Association of America. American invitational mathematics examination.
ittps:
7/maa. org. http://aaennttttttttaaaaaa-oooo-
2025.
Song Mei and Yuchen Wu. Deep networks as denoising algorithms: Sample-efficient learning of diffusion models in high-dimensional graphical models. arXiv preprint arXiv:2309.11420, 2023.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. arXiv preprint arXhv:2310.079233 2023.
Giovanni Monea, Antoine Bosselut, Kianté Brantley, and Yoav Artzi Lims are in-context bandit reinforcement learners. arXiv preprint arXiv:2410.05362, 2024.
Tergel Munkhbat, Namgyu Ho, Seo Hyun Kim, Yongjin Yang, Yujin Kim, and Se- Young Yun. Self- training elicits concise reasoning in large language models. In arXiv, 2025. URL nEEDs:/7
Ltxiv.org/abs//5500
Alex Nguyen, Dheeraj Mekala, Chengyu Dong, and Jingbo Shang. When is the consistent prediction likely to be a correct prediction? In arXiv, 2024. URL https: /wtp/vaa.vv./..a////////a.//a../ otq/abs//41)
05778
13

---

Published as a conference paper at ICLR 2026
Alexander Novikov, Ngån Vü, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco JR Ruiz, Abbas Mehrabian, et al. Alphaevolve: A coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506. 13131, 2025.
OpenAl. Openai ol system card. In arXiv, 2024. URL https:/ /atpi//arxvv... www.xvvorr//b//24200
16..
OpenAl. Openai 03-mini, 2025. Bttpattss//ooeaa..coo//eeeeeeeee
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complent Journal of Ma- chine Learning Research, 22(75):1-35, 2021.
Aleksandar Petrov, Philip HS Torr, and Adel Bibi. Prompting a pretrained transformer can be a uni- versal approximator. In Proceedings of the 41st International Conference Machine Learning, pp. 40523 40550, 2024.
Jiahao Qiu, Yifu Lu, Yifan Zeng, Jiacheng Guo, Jiayi Geng, Huazheng Wang, Kaixuan Huang, Yue Wu, and Mengdi Wang. Treebon: Enhancing inference-timg timeenece-imeeeeeee alignment with speculative tree- search and best-of-n sampling. arXiv preprint arXiv:2410. 16033, 2024.
Yuxiao Qu, Matthew YR Yang, Amrith Setlur, Lewis Tunstall, Edward Emanuel Beeching, Ruslan Salakhutdinov, and Aviral Kumar. Optimizing test-time compute via meta reinforcement fine- tuning. arXiv preprint arXlv:2503.07572, 2025.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. Operations Research, 66(1):230-25) 2018.
Pier Giuseppe Sessa, Robert Dadashi, Léonard Hussenot, Johan Ferret, Nino Vieillard, Alexan- dre Ramé, Bobak Shariari, Sarah Perrin, Abe Friesen, Geoffrey Cideron, Sertan Girgin, Piotr Stanczyk, Andrea Michi, Danila Sinopalnikov. Sabela Ramos, Amélie Héliou, Aliaksei Severyn, Matt Hoffman, Nikola Momchev, and Olivier Bachem. Bond: Aligning ilms with best-of-n distil- lation. In arXiv, 2024. URL https:
wwt.abs/ 2407 14622.
Amrith Setlur, Nived Rajaraman, Sergey Levine, and Aviral Kumar. Scaling test-time compute without verification or rl is suboptimal. arXiv preprint arXiv:2502.12118, 2025.
Ben Shi, Michael Tang, Karthik R Narasimhan, and Shunyu Yao. Can language models solve olympiad programming? In Conference on Language Modeling, 2024. URL https:/7
obenreview net /oor/////u// www.ooowwnmmmonaae.ee 1d==Gaa4MMEP91
Charlie Victor Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM test-time compute optimally can be more effective than scaling parameters for reasoning. The Thirteenth Interna- tional Conference Learning Representations, 2025. URL /tttss:/openzeview. net/
Forum21d=44FAw2tt..
Kefan Song, Amir Moeini, Peng Wang, Lei Gong, Rohan Chandra, Yanjun Qi, and Shang- tong Zhang. Reward enough: Lims are in-context reinforcement learners. arXiv preprint 0000::25006006333. 2025.
Yifan Song, Guoyin Wang, Sujian Li, and Bill Yuchen Lin. The good, the bad, and the greedy: Evaluation of Ilms should not ignore denedetermnism. In arXiv, 2024a. htRLs:tp:: //arxiv..
/407 10457.
Yuda Song, Hanlin Zhang, Carson Eisenach, Sham Kakade, Dean Foster, and Udaya Ghai. Mind the gap: Examining the selfoimmpoveeeet capabilities of large language models. arXiv preprint 2.X2:2411.002674 2024b.
14

---

Published as a conference paper at ICLR 2026
Zhiqing Sun, Longhui Yu, Yikang Shen, Weiyang Liu, Yiming Yang, Sean Welleck, and Chuang Gan. Easy-to-han hard generalization: Scalable alignment beyond human supervision. In The Thirty- eighth Annual Conference Neural Information Processing Systems, 2024. URL nEEDs:// openreviese Beenreview.net//e www..eee/oorutt... 20w.oruuummwgqww22FFT
Ye Tian, Baolin Peng, Linfeng Song, Lifeng Jin, Dian Yu, Lei Han, Haitao Mi, and Dong Yu. To- ward self-improvement of LLMs via imagination, searching, and criticizing. In Conference Neural Information Processing Systems, 2024. URL https:: wtt.w//wwwwweeeormmmmmo
1d=tPaJZqHKOB
Tooliense. Crux: 2025. URL https://Eool com/ cruxl html IC-RL Implementation with Self- Evolve Mechanism.
through hierarchical multi-agent orchestration,
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordy- intsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference Machine Learning, pp. 35151-35174, PMLR, 2023.
Ziyu Wan, Xidong Feng, Muning Wen, Stephen Marcus McAleer, Ying Wen, Weinan Zhang, and Jun Wang- Alphazzeoolike tree-search can guide large language model decoding and training. In Forty-first International Conference on Machine Learning, 2024. URL nttps:
//openreview net. http://wwwwe.eeefooooo//ooooooa // oftt:
Xuezhi Wang, Jason Wei, Dale Schuurmans. Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self Self-coosistency improves chain of thought reasoning in language models. The Eleventh International Conference on Learning Representations, 2023. URI. https: oewnrevvevveeeeeeeeeeeeeeeeeeeve
net www.ee/ww.ntttttttttettem
Yue Wang, Qiuzhi Liu, Jiahao Xu, Tian Liang, Xingyu Chen, Zhiwei He, Linfeng Song, Dian Yu, Juntao Li, Zhuosheng Zhang, et al. Thoughts are all over the place: On the underthinking of ol-like llms. arXiv preprint 2rXiv 18585, 2025.
Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: a case study on approximating turing machines with transformers. Advances in Neural Information Processing Systems, 35:12071-12088 2022a.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large lan- guage models. Advances in neural information processing systems, 35:24824-24837, 2022b. URL Bttps://proceeeeeee www.:eee.enuuu..o.mo.. cc/paprr files/paper/2022/ h227:/0000051522eee1111100000110
atwp://sssaaaaaaa--aaataaaaaaaaa www.erreoooteeeeeeeee .tm
Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning self-correct. In The Eleventh International Confer- ence on Learning Representations, 2023. URL
hH33JeQZDaQ
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Scaling inference compu- tation: Compute-optimal inference for problem-solving with language models. In Workshop on Mathematical Reasoning and Al at NeurlPS'24 24, 2024. URL bttps::/ openrevi ew. net.
Eorum?io 2
7DZWSc8qu
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical analysis of compute-optinet inference for LLM problem-solving. In The Thirteenth International Conference on Learning Representations, 2025a. URL /ttpss:/openrevi.ee
net//oorum2ideNNokp..oo
Yuyang Wu, Yifei Wang, Tianqi Du, Stefanie Jegelka, and Yisen Wang. When more is less: Under- standing chain-of -f-tuuughtt length 1lms. arXiv, 2025b. URL Attps: http:///axvvvc.om www.vvorgggaao abs/ 2502.07255 072268
15

---

Published as a conference paper at ICLR 2026
An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang. Jiaxi Yang. Jing Zhou, Jingren Zhou, Junyang Lin, Kai Dang, Keqin Bao, Kexin Yang, Le Yu, Lianghao Deng, Mei Li, Mingfeng Xue, Mingze Li, Pei Zhang, Peng Wang. Qin Zhu, Rui Men, Ruize Gao, Shixuan Liu, Shuang Luo, Tianhao Li, Tianyi Tang. Wenbiao Yin. Xingzhang Ren, Xinyu Wang, Xinyu Zhang, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yinger Zhang, Yu Wan, Yugiong Liu, Zekun Wang, Zeyu Cui, Zhenru Zhang, Zhipeng Zhou, and Zihan Qiu. Qwen3 technical report. arXiv preprint arXiv:2505.099 093888 2025. URL https://arxis
arg/aba/ 2505. 09388.
Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. Self-attention net- works can process bounded hierarchical languages. arXiv preprint arXiv:2105. 11115, 2021.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? In International Con- ference on Learning Representations, 2020. URL
net/ forum?
ByxRMNNNNE
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. Advances in neural information processing systems, 13:17283-17297, 2020.
Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. ReST-MCTS*:
LLM self-training via process reward guided tree search. In The Thirty-eighth Annual Confer- ence on Neural Information Processing Systems, 2024a. URL
Forum?id=8rcF
Kechi Zhang, Ge Li, Huangzhao Zhang, and Zhi Jin. Hirope: Length extrapolation for code models using hierarchical position. arXiv preprint arXiv:2403. /9115 2024b.
Qiyuan Zhang, Fuyuan Lyu, Zexu Sun, Lei Wang, Weixu Zhang, Zhihan Guo, Yufei Wang, Irwin King, Xue Liu, and Chen Ma. What, how, where, and how well? a survey on test-time scaling in large language models. arXiv preprint arXiv:2503.24235, 2025.
Yunxiang Zhang, Muhammad Khalifa, Lajanugen Logeswaran, Jackyeom Kim, Moontae Lee, Honglak Lee, and Lu Wang. Small language models need strong verifiers to self-correct reasoning. In ACL (Findings), 2024c. URL htt.://a..//.aaaat..ooooo....... findings
9247
Yuxiang Zhang. Shangxi Wu, Yuqi Yang. Jiangming Shu, Jinlin Xiao, Chao Kong, and Jitao Sang. ol-coder: an replication for coding. In arXiv, 2024d. URL Fttps://arxiv..rrd
2412.00151
Haoyu Zhao, Abhishek Panigrahi. Rong Ge, and Sanjeev Arora. Do transformers parse while pre- dicting the masked word? In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Laggugge Processing, pp. 16513-16542, Singapore, December 2023. Association for Computational Linguistics. doi: 10. 10.18653/v1/0023. emnlp-main 1029. URL https: BEDs://Allaathooooy.ooor
emn wenn_p-main..i.mmmmmmmm www..ainnn......... 10297
16

---

Published as a conference paper at ICLR 2026
A PROOFS
A.1 PROOF OF THEOREM
Proof. Write = {1..... 0} (O E Σ+) where is the i-th most likely answer and let n, denote
the number of occurrences of i. Then we have
i [1 no) ~ Muuttioomial(n.p),
where = :()))....pP))
Upper bound.
When 2 21/8(1
we apply Claim to obtain that with probability at least
1 6,
2l101/))
|1 pll S
A.
n
Under this event, have that for any
(fi - pi)
(pi p; || pll1)
20 0
and hence the correct answer is the most consistent answer. It follows that self-consistency can produce the correct answer with probability at least 1 - 8.
Lower bound. When n < L we construct the hard instance where P1 = (1 + A)/2, = AZ. (1- 2 and A < 0.00001. If n S Á then by the proof of Theorem B.21 with constant probability correct answer is not generated at all and hence self-consistency fails to produce the correct answer. Otherwise n variables divided by Vn:
10000. We may write X 21-m--1 as sum of i.i.d random vn
n i= Y X
where IE()) = 0, = =E(Y? 2 1/2, | 3) < 1. By Claim A.G. we have that
P(n1 < 12) P(X < <11)
8p
> ((-1) /3 /n
2 0.01.
Thus in both cases, self-consistency fails produce the correct answer with constant probability.
A.2 PROOF OF THEOREM
Proof. Write f1..... 0} where is the i-th most likely answer and let n, denote the number of occurrences of Then we have
p(1) 2 +
Note that for best-of-n, correctness is achieved if the correct answer appears at least once among independent samples.
Upper bound.
When 2log(1/6) have
PPBesttoff- outputs correct answer)
(1 - p(1))"
1 (1 A) 1/4
> 1 5.
This confirms that best-of-n achieves the correct answer with 8 probability.
17

---

Published as a conference paper at ICLR 2026
Lower bound. When v A construct the hard instance where p(1) = -+(1-A))0, p(2)
p(O)= = (1 A and A 0.0000001. Since the correct answer occurs with probability at least A, we have:
P P(Best-of-n outputs correct answer) = 1 (1 - -(1))
-1 2A)
< 0.99.
This confirms that best-of-n fails to produce the correct answer with constant probability.
A.3 PROOF OF PROPOSITION
We first introduce the following result that extends any Transformer larger vocabulary, that it only attends to tokens its original vocabulary.
Proposition A.1 (Extended Representation to Multiple Token Spaces). For any H. L,, Ninax E Zet, V1 n Vo there exists a general-purposs Transformer Φ of type (O(1), Oflog Nmax)) such that for any Transformers J = (0, pe, (K) Q v )eetH,, 0, Vi) over vocabulary Vi, the pe,pe, Transformer f = f(f)) satisfies the following property: for any token sequence v = U1 ... Un such that n Nuax denote {ir < 2m) {a: E V1}, then have
- p7((1))-pp((u))
where u = 04g Ukm"
Proof. Set constants Bu, Byks Bg such that for any layer and head h, it holds that
[ ) lg < Bok.
I Bu, and [[(x))l2 s Bg holds for all v E V. Let Ba, C 4B² + log(1/e), Co = 4C. By Lemma A. there exists
v/ 2
B (HB,)* (H
a1..... Naaee Bo, B1 E pdd and Ao, AI,A E do for do Ollog Nmax) such that
1. For any 2 Js:
(a; + B1) Ao(a + Bii = [aa;+ + T Ao(as, + +11 2 (a; + 3:) Aolar, + + Co
(or + (.)) Ao(a; + B0) 2 (a; + Bo) T Ao(a;, + 31) + Co.
(3)
2. For any i> j
(a: + TT)TT(a
A(a, + B1) 2 (a, T1) A(aj + B1) Co 2 (as + 31) A(a, + Bo) 2Co.
(4)
3. For any 2 j.J1
(as + (1) T A₁ (ay + Bb) = + (A:+ Aı(a, + +1) + C.
(a, (1) A1 (1) 2 max{(a; 81) A1 + B1), (at + TT) A1(ag, +B0)} Co.
(5)
We define á as follows: for any Transformers f (0,pe, pe, (K() Q V )e(mm) Vi), the Transformer f o(f) is given by
(0. pe, (K 0h V )eeee 3, Vi U Vo),
where the tokenizer is given by
(0(w)) B1
0(0) = 1le Vi)
+ 1(0 Vo) (%))
the positional encoder is given by
pe (z; u) aj
pe
81,
18

---

Published as a conference paper at ICLR 2026
where 041
Um and
R for I = 1...., the key, query, value matrices given by
(0% (1)
,).
K
(1)
21
Ao
V (1)
V
h
1). 1))
v H+1 = 0 (
K (1)
(1) 1H+1
H+1
A
H+1
The output feature is given by F(y) ((y)
Since .,, im only depends on whether vy's belong to the set V/1 the generalized position encoding pe is well-defined. It can be verified that indeed canerre-purpose Transformer of type (0(1), Ollog Nmax)).
We show that for any / 1,...... L.
x
X
Vi = i1,...,, km
(6)
where X, is the I-th layer of Transformer f at position i (attending only to positions ii...., im)
such that
|xx, < Ba(HB,)),
and
X = 0
Vi $ fmm....,
(8)
0g)
where ā a; + 1(VE Vo) Bo 1(v vi)) 31.
We prove these results by induction. The case I = folows directly from the definitions of the tokenizer.
Prove Eq. (8). We have
Suppose Eq. (6) and Eq. (8) hold for 1,.... I - 1-th layer, and consider l-the layer.
H exp (0
X
( x
(1++1
x
70) h
A
k=1
term 1
(0 [Q X (
H- (KK) x())
exp
5.0 ((1)
2
tem
Eq. (G) ensures that for any i, E fi.....,mm].. & (i.,..., km):
x(") x = (Q (K< x() + (a; + T.)TAAA An + +
2 (Q) x(")))]) x(²) + (aa + TT) Ao(a; + + C
= x(")) x(0) + +C,
and if E (i,,...,mm)
x2xxx11 x(") (K (1) ((!)) (6 (,(0) T (K()) x())
(1) ( (as B1) AT(ao, + Bi) =QQ 1 ( (K) (1) x (1) (a: 81) Ao(a + +111) - -00 x(")) T(<!
(1)
-Q,f0 x(") (K x(!)) -QQ x((1) T T(K!!
(1) x(1))
(Q x (1) ( x/(")/ Since the transformers
where we use the fact that Co 2 C + 2 maxi.1.s
(Q) x (K) x) + log(1/e), it follows that the
have precision and C 2 2 maxx.iii
h
19

---

Published as a conference paper at ICLR 2026
attention weights of head (A 1)H + h is identical to the attention weights of expert le i... exp (Q)) ( ) (K) 1 x
exp (10) x (K% x
1(j- (ii,...,,mm)
%/
Therefore
exp (Q x(()) T(K), (xx))
(x) xx((t)
term Σ
Furthermore, by Eq. (EI) have for any j <
( T (K H+1 = 0, Adi;
{11
2 a Aā₁ +C
= ( (1) x
#+1 T x + +C,
and hence the attention weights concentrate on itself. Thus
0
term 2
7
oi
Combining, derive (q.(0) for (1 + 1)-th layer.
Prove Eq. (0).
From above,
exp 12 x
X (K( x
H
|| (++1
v x
2/
h=lj=! j=1
S HBB.
max || l12
55$
< BB
This confirms Eq. (24)) for 1.
Prove Eq.
(.) Notice that Eq. ensures that for any j.j' {i u;; Vi and i i {i Vi)
Q h
(1)
x T
(K x(() + (az + (b) Aolay + Bo) x(() = x(
2 (Q) 12
(ay +b) Ao(as + (1) +
= x x
follows that the attention weights is concentrated on the complement of {i: Us E Vi} itself, and therefore Eq. (8) follows by simple induction argument.
Finally, at the output layer
P7(y|e1..... .....,, wx) = Softmax Softmax(0(v)) x(())
Softmax(0(u) x(())
Pf. (ylu).
This establishes the desired statement.
Now we return to the proof of Proposition 2.
Proof. By Proposition suffices to construct general-purposs Transformer e such that p7( (n) = Py. (:lu),
where u = ... Vio +1 ... Un. because then the t given by
fK) o...(f)).....e((ff))
satisfies the requirement, where o, is the formers the larger vocabulary : uk Vi. given by Proposition A.
Transformer that extends the K Trans-
20

---

Published as a conference paper at ICLR 2026
Set constants Bu, Bobs Bg such that for any layer and head h, it holds that |(0) (1 T T (1)
S
Bgb: |/(
1 B,, and []0(e)]l2 & Bg holds for all E V. Let B (KHB,) Bet Bo C
4B + log (1/e), Co 4C. By Lemma A.3 there exists al...., AN, BI,....... 3x E R and
A1,... K E dddo for do S O(K + log Nmax) such that
1. For any 12 J2, and k, #0:
(a; + {x)) An + (r) (a; + 5x) T
Ao(ajz + (w²)) 2 (a; + Bx) Ao(a,, + (b) + Co
(a; + 86) Ao(a; + +0)) 2 (a; 9n) Ao(aj, + (x)) Co.
(9)
2. For any > j and Ao + k 0
(a: + 3x) T A(a: + 3x) 2 (a; + [x) A(aAA(a + 3x) + Co
2 (a, [ + (0) + 2Co.
(10)
3. For any 2 j.J1 and & * K
(as [&) (ag -B) (a: Baa) A (aj + Bkn) Co
(as; + Bx) Ag(a; + (x) 2 max{(a; + 3x) Ax + Bwr), (as, + Ba) Aw + +190] + Co= (11)
define e as follows:
for any Transformers
fa (0k. pek, (K() (1) v
kihh lihh 1e hejmmeet OR. Va),
over VR, & E [K], the Transformer = offi...., fxk is given by
(0, pe, (K 2h
(1) (1) (i()) )e([ 3, V),
where the tokenizer is given by
(v)
((0) = 1(v $ Vo)
0k(u)
BE(T))
where E(v) iff Vs. Let the positional encoder be given by
pe₁ (z; u)
pe
U1
03
y
pex (a; u)
O₁ +
where E Idd and is the sub-sequence of that omits via (if any); for / 1, L the key, query, value matrices are given by
0
K
(0)
K
( kch
( Qk
ik
1)H
Ao
I
(
(1
(k-1)
21

---

Published as a conference paper at ICLR 2026
0
K
Q
V
KB+1
KK++1
KH+1
A
1
where the submatrices K
(1)
(1)
V
Je are located in the k-th diagonal block, and for the final
())
kihh
layer
K (1+1)
Q
(1++1)
v (1++1_
0
O
Ag
where the identity sub-matrix in (L++)) is located in the k-th block. The output feature is given by
01 (1(1)
((v)
Since u (ki's only depend on set membership information o; us's, the general-
1 (v)
ized position encoding pe is well-defined. We can easily verify that e is indeed a general-purpose Transformer of type (O(K), Ollog N Nmax)).
show that for any / I,...,I. L.
1
x
Vi # io
(12)
Ka
a
where kgl is the 1-th layer of Transformer is position i (attending all positions but ig) such that
|| s Bg (o
(13)
and
X
(14)
10
Clia
where ā; a4 + SE(m))
We prove these results by induction. The case / folows directly from the definitions of the tokenizer.
Prove Eq. layer. We have
(22
Suppose Eq. 122 and Eq.
444 hold for 1,...,/ / 1=th layer, and consider (-the
K
exp 1 (1)
1)
x
( X
7
(1-1)
(10 x (1
K x()))
exp
50
KH41
70)
*K
22

---

Published as a conference paper at ICLR 2026
Eq. (9) ensures that for any S i such that to & f2):
X (1 = (Q 1 x
(K Rihh
X kJj + (a; + (E(A)) (1 "Ao(a,, + RE(H))
R 1)
(k-
(Q
(1)
+ (a; + +B()) Ao(as, + (e(ia) + C
kjji
1| +
and
+1-1) x - (Q x10)T T (K 1k-1)) fz
x()
(o kit
T (!)
x
(1)
+ (a: + )e(()) " -B(i))
-Q T
(1) x
kidz -a; + BE(S) TT Ao(ajo (E(z)) kih
kit
-Q x
T
(1) kch
x
Jijh (Q X x(2
follows from the precision of the transformers that the attention weights of head (k 1)H is identical to the attention weights of expert k, i.e.
ExP (Q0 (R- x
(K- 1)- x
exp (10))
(K
(1) kid
xx1)
kij
7 (k-1)H+b
Therefore
X (1)
TIK kihh (1)))))
exp
v U
term 1
2(0)
kz
x Ki
Furthermore, by Eq. (III we have for any j <i
(õ (0)) (1) x(0)
(K (1)
x(0) ā, Aã;
KH+1
2 ã Aā; +
@20 [KH+1** x(0) (K ( +
and hence the attention weighs concentrates on itself. Thus
term 2
0
Ki
Combining these two terms, we confirm that (I. holds for (1 + 1)-th layer.
Prove Eq. (I3)
From above,
K
H
exp (Q)
11 x 5 (((()
(k 16-1)1 1) x
X
(1+1) ki
1|2
(k-H+)
x (1)
(0)
11/Ht
< KHB, max
|X
lle
kig
< Bo
This confirms Eq. (13) for +
23

---

Published as a conference paper at ICLR 2026
Prove Eq. (14).
Notice that Eq. (D) ensures that for any io:
(Q ( 2
(Q
x
(K
(1)
x!1
(aso + (E(ta) Ao(ass + Bg()))
+) 10
(1-1))Hh
i0
k
k;h
kio
2 Aith k
(1) (
+ (ar + ) T Ao(ay + Be()) + k:h koj
x!1)
= (Q (1)
(k- (|= +
(k- +) 10
follows that the attention weights of head (k 1)H + h concentrated in itself, therefore
term 1 =
V
0
0.
Ag
k= 1=1
By the same argument, for i = in we have
0
0
term 2 =
=
1
Olio
Combining these confirms Eq. (EE)
Next, we show that the last layer satisfies
((++1)
1(++1)
(15)
where I(L+1) is the k-th block. To this, notice that Eq. (III implies the followings (the proofs are identical to the above):
1. Attention sink to dummy token Us for mismatch expert: for any k'' * and j S we have (L) (
@0 ((==1)+++*
(L) X(1))T
= (an + BE()) T Aw (ax + RE(S)
I (an + BE(m)) T A (aso + (8E(1))) - C
(044) (L)
1)H - ((11)) T (K (L)
( 1)H 1 {(L))
C. (16)
2. Attention to oneself for matching expert: for any j * in we have
(6 (0 ( (x-1))+ (()) = (an + BB(r)) T Ax(aş + BEG))
2 (a, + BE(m)) T Ax(ai, + (E(()) +C
(Q {((1)T (L)
(x-1))+hh x/10 ) (17)
+C,
and
(Q (L) X
1)-1)) (K X( (a. + BB(w)) Ax + BE(N))
2 (a. + BB(m)) T Ax(a; + BB()) + +C
= ( {(11) ((K(L))
(x-1)Hthh* x
((L)
+
(x-1)H+
(18)
24

---

Published as a conference paper at ICLR 2026
Combining Eq. (TG)) Eq. 7),
and Eq. (18), we have
T(K (T)
(K (k-1)
exp +1
1000
k k k
(1)
8
k K
follows that
x(++1)
(L)
Σ
v
(
(k-1))Hth
kz
x
1:a
X X
X (L)
K3
0/
Og
Therefore we establish Eq. (LS). Finally, at the output layer
p7(U|ur,.... vn) = Softmax (0()) T [x(++))))))
Softmax (D)) Ty(
Ps. (y/u).
This establishes the desired statement.
A.4 PROOF OF PROPOSITION
Proof. Set constants Bu, Boks Bg such that for any layer and head h, it holds that Bu, and [10(v)ll2 Bo holds for all (Eo -1, BB, 2B2 + log(1/e), Co = 4C. Define i(i) = u iff c. S i < Eu+1 Do by default). Let E(.) denote the task id indicated by the special to- ken. By Lemma AZ there exists a1...., a., S1...., 3x E Rdo and A Ax E dooxdo for
(Q (1) )
11, Byk. v
V. Let
B = (KHB,)
du S O(K log Mmaxx such that for any n S N we have
1. For any l + W::
a Akan
a Aa + Bw) 2 Co +
a Anaj
s KK (19)
a As(ay Bkd)
2. For any [K]:
n Ak(Uin + +kk
a Agan, = a A400 2 Co +
a Asaz ax Ac(as + Ber)
44 <j < <k. (20)
3. For any h W, K' [K]
(an + Bxr) T As(an + (x) 2 Co (an BBr) Asaj, 4A S S
(21)
4. For any < j < nt
an Ace 2 0₂
T A(an + 3x3 + Co
2 Co + max fa Aay, a A(az + Be)}, 4k, k² E [K].
(22)
We define & as follows: for any Transformers
(1 ft (0%, pek. (K) kih Qkik V 1e Oz. V), e [K]
25

---

Published as a conference paper at ICLR 2026
over V. the Transformer f @ff1...... fx) is given by
pe. (K) 0 v
Me(KH=Heeu 0, VUN),
where the tokenizer is given by
(1(w)
0
((v)=
. V, 0(w)
:
w 22
(x(
0 (E(w))
the positional encoder is given by
pe₁ (z;
Ugg -,, Um +1, Un)
② (0)
pe
U1
U/
y
pex (æ; U1
UEl 11 u +1, +1 Un)
(1) +
where E Rdd for = 1, ..... L the key, query, value matrices are given by
K +
K
kih
(k-11) 1)
A
V
v
Acch
K
(1)
(
KH+1
RH++
KH+1
0
0
0
where the submatrices
((()
Rish kgh are located in the k-th diagonal block. The output feature
v
kihh
(3)
01
is given by Ö(y)= = :
Since E1, &m only depends on whether v, 's belong to the set Ω the
(x) 0
generalized position encoding pe is well-defined. We can easily verify that & is indeed general- purpose Transformer type (O(K), Olog Nmax)))
Let X (1) represent the 1-th hidden layer. Our goal is to show that for any 1,..., L.
x,() can be written as:
X
(
x
==
1,...,,,
(23)
(1)
Ki
Ol
where ã; a.(1) (((()) i) -e(()) and x!!) Rd such that
| S (oH....)
(24)
26

---

Published as a conference paper at ICLR 2026
In partieular, for i 1,..., we have
x0
kiC: 0, vk =l.... K,
(25)
and for j = -,....,5i we have
x kij Rij Ak = I,...,
(!)
(26)
and for j = =;....., E1 5m + 1, ..... we have
x Kzj
(1)
5m 1+ 2ky 0, wk' + ni
(27)
where yr) is the 1-th hidden layer of (attending only positions 1, ,i 1, Em 1....,n).
Thus apply induction on l. The case = 1 holds trivially from the definition of 0 and pe. Suppose the above relationship holds for all layers 1,....,A ,L, consider layer + 1. We have
" exp @ā (1 ) (K (K (K-1)H++ x
k
x(+11
V.
(K-1)++
X0
2:01 11-1))+
term
( (1)
(QKH+1X)) x(") KK (1)
KHH+ x
exp
70
*HH+1
temn 2
where
200 (k-
Σ
exp (1 x(
11)
(K
1)--11H x(01)=
1)
(k-
1=1
By induction hypothesis,
1:2
x:10
Ka
O2
and x-(1) = - for i = 1,..., .1 1, +1, 1,... where ((i) =
i,
i< E1
kg
(())
1 ii- Em -1 1 E1,
i> mm
Notice that for j é:
(2 (1) 1)
(1) [K (1)
(k-1) x(011 (Q [K() x(() (KO
lihh X aj Akāz
(2
(xx++1xx1) (K(
((K))
KH+1 x(11 ā. Aōj-
Prove Eq (2.)
By properties of 3, A, for any j2 < Eu < <i< Eo notice that:
( X {(1)
(0 @ x((0)((()) kH++
=() C
> (
K (0) (K! K# ((1) 2C.
T(
Due to e-precision of transformers, this implies that
exp (@@#41 (((0) x
10pEaa 8-80
Ea <i< < Ea+1
(
i En
#K#41
27

---

Published as a conference paper at ICLR 2026
and hence for Eu < i
Eu+1
K H
exp (Q
1k-1) H)H (
(K (k-1))+ x301)
x(+1)=
v +)
x
k=
h=
1k-1))
i - Eu
(L(()))
X
(1+1)
la
x
11+1)
Ki
04
and for i = Ex
0
x((+1)
K H
exp
(0 1
+)
X(1)TT
(K
1) + x00)
x
200
(k-1)
+
1k-1)
(r((1) + Be(va)
(1+1)
la
x
((++))
Kzi
ai
where
H
exp (0
(k- 11-1k))) 1) + x11) T(K]TT(()))
(k- (1-1) x(
x (1+1)
v-()
kid x(() kis
(28)
(1)
R=1 1==1
(R- 1)
This confirms Eq.
(2
for + 1.
Prove Eq.
From above,
K
H
exp (Ô 1
11H T(K))(((()
(x- x."))
||
l
( x(()
kgs
7,00
kih kz
k= b=
(k-1))H44
KHB, max I
351 < (oHBB (+1
This confirms Eq.
(24) for + 1.
Prove Eq.
We first show x x(() = 0. Indeed, by the properties of as, 8k. for any j s E
@tth (QR-
T
((1)
(k-1)
x
(x K:S 1ch
((0)))
x
(ao + ) I Ax (as + Be(ve,))
kih
kili
(xx)) @hch
((Q))))
!I)
+ (ao + Be(ve, 1) AgCi +
kihh
(()
( x(1) +
= 111H++++++
1)H
28

---

Published as a conference paper at ICLR 2026
It follows from Eq. (28) that
K
H
(1-1) KEE1
kibh
RiE1
0.
k=1k=1
For &a (i > 1), we apply the same argument again to obtain that for any j S & such that j $ {5i < } and any i' < i,
F0
1)H + Ee
2 2 1) &
(k- 1)Hf x +
This implies that the attention weights supported on {51 <...<.. { and therefore
i exp (7 (1)
()- x(1))
[K (1)
1)HH x(())
X x(+))
ΣΣΣ
(1) kih k:gy
200
+)
where we apply the induction hypothesis k; x! the proof of Eq. (25).
0 for all j = 1,...., - 1. This thus completes
Prove Eq. (ZG)
When j1 < Si < &1, have
(1-IM T T (0)
(R-1) x - (2 (( T(T)
(K 1)-1)++ x!0
= =(x{) TOO (
x(1)
+ +00 Apdo T
l:h kihh
- T(
(OEN))
(
(1) (1)
-ag T ARoo T
kih k:22
= (Q T(K)
lih kise
(1) (0)
(0 NiF
(1) (
T(K T
(K k122)
It follows that
70) +1
Σ exp (Q
(1)
(K (1)
kii
Rihh
and
exp (Q)
(1) yr())
(K (K(()) x(())
K
H
(++1)_
ki
kih
k=
(k-1)H+h
y- (1+1)
This confirms Eq. (26).
Prove Eq. When
Em. we rely on the following properties:
1. Attention sink to fg... for mismatch expert: for any k * k. and j S we have
(Q X x ( (0() (1)
(K
(1 X (2) [K (!)
((1) C.
1)H1
(29)
2. Attention to task-relevant tokens for matching expert: for j E {l..... E1 1, 1m 5m+ to, and E j' < Em we have
(1) (2
(1-1)#+h* x(") 2 (1-1))44 x(1)) [K (1-11)H+h {((1) + C.
(30)
and for ji < < E (1,..... - - 1m + 1, ...
Q 11x-1)HHh x-(1) T (K (1)
(1)
(x-1)HHh [1))
(2 (x 1)H +h x(11)
(1)
[ (1)
(1)
(x--))HH
jz
= =(0 with Rij Em -145 ( T (K((
(1) y!)
Nil <(i)))
(1) (1)
(Q.
y!))
i-Em 1+8
Nih )
(1)
(31)
29

---

Published as a conference paper at ICLR 2026
To see Eq. (29). notice that
Q0l (k-+)) x
(K
(2-1) x
(Q
(1)
((1)
+ T Aw (((())) + Bo(w,) 1(()) - j))
With kJ
S Wa)
T(Q
(1)
+ a (am + BE(v)m)) -C
(1)
11H++ x C,
where we use Eq. (19) with k' + k.
To see Eq. (EO0, we notice that
(õ (9)
(0 (x-1)H+A x (Q 11
(1)
kith Eg am An.o
2 Nogh
An(a,))) + BE(ry)) +
m
= - + x(1))
1jHH x +C,
and
(1)
x
T(()
(N-1)H-H) x00)
(Q kii
!1
an A,00
(K-1)
k:j
2 (Q
ki
x(()
kzj')
+ a am Anaun)
1)Hth x +C,
= k- 1)8
where we use Eq. (M and Eq. (22)).
When fm < < j2, Eq. follows directly from
x
( 4)
T( (N-1) x
1)th
=
!1)
X kihh Tn
Apam
x kis)
(K
(1) X k:dz + am Anam
kihh
(Q (()) -
- -1+8 )T (K
with 11- -m--a-
(1) (1)
(Q
with i-Em 11-14 ) TK(1)
(1) y!
with Nid2- Em 148.)
M y-())
The other cases follow similarly due to Eq. (22))
We have hence confirmed Eq. (24). Eq. (30). Eq.
(1 and therefore
k K, j &
exp ( y
Kit- -140 ((k
(2 v(,)))
(10 (K (k- (K(
exp
20
(1) H)
0, exp
k K, a S j S &m
(Q
(0 ytu
mis- Em -145 )
(K(() (0
Nihh 6m 14811)
k == K, j > Em
118 13
and
70)
Σ
1 y(U) exp (10
Mis &m - T (((()) wich x,11))
(k-1)H+
j=1.... 11 +h...
follows that
exp (10
p())
ASI Sm -111 TTE (K(() (())) (00)
x (1+1)
vil1) y-11)
701
j=1
(k-1)H+h
exp (Q
wigh -si- em- -145))
(1) (1)
(K!!) (1)
with j- - -14,))
V (1) kih -
71)
j=Em+1
(1-1))
(1+1)
K: --1-5m -1+6
x(+11
x())
kig... = 0, Ak' + k.
Therefore we establish Eq. (27). This completes the induction.
30

---

Published as a conference paper at ICLR 2026
At the output layer, we have
pi(ylu1 v.)) Softmax(((()) (((
Softmax (Oy) X(L) n n- 1+4
= Ps. (y/uu,,... Un Um -1+8
This establishes the desired Eq. (2))
A.5 PROOF OF THEOREM !
Proof. Let tha Om: &e denote the general-purpose Transformers in Proposition 4.4 (with K experts), 422 (with K = token spaces), and [ (extending to V) respectively. We construct a dummy
Transformer fa that oulputs BOS immediately after token in A. Then we claim that the general- purpose Transformer & defined by
St.......... = Φm ( (alll.....,.kkk)kl (c(Jk)), Sa. Jo)
achieves the desired property.
Indeed, let 9I = 2.
by Proposition 4. we have
Expert following: At 1-th iteration,
Psn ((prompt) ~ PS,00 (1alu)2-))
where qlu[2-1 is the token sequence obtained by concatenating the user query g and prior generated part in response t: u "1
2. Regret minimization:
max ro(a") E[ro(a!")) $ reg(T).
a E.A
Therefore by Proposition
we have
a ~ Pf.m (11llufi-))
It follows that
r(g,u" B/r(g, u [T]) < X + E Su u)]
-Earr BuTT Lan u u(
< X + max ro(a") ((ro(a(T))] a*Ed
< + rrg((T)
Finally, @ has type o of type (O(K), Ollog( Nmax))) because dh has type (O(K), O(log (N (N and Φm, &e has type (O(1), (log( Nmax)) ))). This completes the proof.
A.6 ATTENTION SINK POSITIONAL ENCODING
In this section, we introduce positional encoding mechanisms that induce attention sink behaviors used by Theorem 7.7.
Lemma A.2 (Attention Sink Positional Encoding, Type 1), For any C R., K, Z,, there exist vectors a1,..., ONN, ,1, .a....,,, B& E Bd and matrices A, A1,..., Ak E Bddd for S O(K log N) such that for any [N] the followings hold
For any + k:
a Again a Akaz
0 A + +Bx) 2++
C+
VO so K.
As(ag + -pr)
31

---

Published as a conference paper at ICLR 2026
2. For any is [K]:
0g Am + Bi)
0g Akaa = Apau0 2C+
On Azaz
[00K < <n *k
On Ax(az + +Bx
3. For any k , E [K]:
(an + )xr) T AR + Bk)) 2 C+ (an + BE)) AROS 64 = S n.
4. For any 0 j n
T a Aan a A(an + Bk) +C
2 C + max Aay, a, A(ay + Br]}, kk, e [K].
Proof. Notice that the following relations are sufficient to guarantee the desired properties
Og AAa, = 0, Ag00:
on AxBr = =, T a Apap 2 an Agaz + az Ar + C.
0, AnBr -C,
0n A3g = C,
3g 3x = 9C.
By Lemma A.4. we find : NN E Rd such that d O(log N), 75 73 S 1/2 for any [M, and 7f 7u 2 1 for any i E [M]. Define
i +
B₁ e T/k Ek.
where .1...., ek form the standard basis of R We thus let
am
bl E
fTK
ai =
cl
B6
e
Og
gl
h
1/K
A
=
0
where b = f= VC,e VC/22.a = V3C.g 9 2VC.h 3VC. The dimension can be = 0(K Nog.
bounded by d =
Lemma A.3 (Attention Sink Positional Encoding, Type 2). For any C R_, K.N Z+. there exist vectors on,-..,, O,N 90, .ao.....,... BK E Rdd and matrices A, Ai,..., Ak E &Rdxd for S O(K + log N) such that for any [N] the followings hold
1. For any 2 fn. Jz and k. k', k. 0:
(as 3xx) Ao + Bxr) (a; + B4) Ao(a + (wr) 2 (as + Ba) Ao(a,, Bo) + C
(a; + 36) T Ao(a; + +B0) 2 (a:+ 36) Ao + 3x) +C.
2. For any i > and 1: + K' + 0
(as + 3x) T A(a; + 3x) 2 (a; + B&) T A(a; + Be) + C
(a; + B&) T A(ay + (0) 2C.
32

---

Published as a conference paper at ICLR 2026
3. For any i 2 j.J1 and k + K
(ax; + 3x) (a 86) 2 (a: + Ba) Aajaj + BKx) + C
(os B&) As(a; (x)) max{(a; Bx) As BBBr)) (ass Be) Ar + + C.
Proof. Following the notations in Lemma A. A.2. let
7
8k
7
30
Ck
and
ee.I
a
0
A
AA
A =
0
C.
exck
where a = c= 6 C, 3.5C, C, = 4C. The dimension can bounded by d d + K +
O(K + log.N.
A.7 TECHNICAL CLAIMS
Claim A.4 (Johnson-Lindenstraass Lemma). Given < 6 < 1, a set X of N points in IR",, and an
integer & > 80nN) there is linear map f R= + R such that
(1- (1- w/I? < (1f(m) f(o)]l s (1 + +e)llu e||
holds for all u, v E X.
Claim A.5 (Concentration of Multinomial Distributions, adapted from Agrawal Jia (2017)). Let p E A and Multinomial((n.22 p). Then, for any E [0, 1]:
2 (l100
11 -ū--10 pll 2
S 8.
n
are i.idd random variables with E(X,) B(X?) o² > 0, and (() p < we define
Claim A.6 (Berry-Esseen theorem). X1, X2...
Y, X, X X,,
as the sample mean, with F2 the cumulative distribution function of Yuv/ and & the cumulative distribution function of the standard normal distribution, then for all and n,
Sp
Fx 4(x) s σ vn
33

---

Published as a conference paper at ICLR 2026
B EXPERIMENT DETAILS
B. IMPLEMENTATION DETAILS OF SELF-CORRECTION EXPERIMENTS
The model configurations are detailed in Table
2 Our code is implemented based PyTorch Paszke et all (2019) and mi DGPT All the models trained one NVIDIA GeForce RTX 2080 Ti GPU with 11GB memory.
Model
Depth
Heads
Width
GPT-nano
3
48
GPT-micro
128
GPT-mini
6
6
192
Following common practice, the learning rate goes through the warm-up stage in the first 5% of training iterations, and then decays linearly 0 until training finishes. We set the peak learning rate to 10 and find that all the models are stably trained under this learning rate schedule. We not apply drop out or weight decay during training. We repeat the experiments for 3 times under different random seeds and report the average accuracy with error bars.
Gopher-44M
16
512
Table 2: Model configuration hyperparameters.
B.2 PROMPTS FOR SELF-CORRECTION
Initial Problem Solving Prompt
Solve the following math problem efficiently and clearly. The last line of your response should be of the following format: "Therefore, the final answer is: $ Aaboxed ANSWER] $. I hope correct' (without quotes) where ANSWER is just the final number or expression that solves the problem. Think step by step before answering. [Question]
Correction Prompt
Your answer is incorrect. Please analyze your solution and identify where you made an error. Then provide corrected solution that leads the right answer. The last line of your response should be of the following format: 'Therefore, the final answer is: Aboxed (NSWER) $.
C BEST-OF-n WITH IMPERFECT VERIFICATION
We additionally perform experiments to test robustness of best-of-n under imperfect verification. Using Qwen3-32B as an LLM verifier, we evaluated best-of-n on the AIME 24/25 datasets with 3 recent models. As shown in Table E. best-of-n with LLM verifier closely matches the per- formance using an oracle verifier. This evidence supports the practical validity of our theoretical assumptions in Section 5
Model
Best-of-n (64, oracle)
Best-of-n (64, LLM verifier)
Qwen3- 1.7B
80.00
76.56
Qwen3-4B
91.67
85.20
1.aama33.233B-Instt
23.33
21.45
Table Comparison of best-of-64 performance using an oracle verifier vs. Qwen3-32B LLM verifier on AIME 24/25. Results are similar across all evaluated models, indicating robustness to imperfect verification.
https://qithub. http://ahh....coaacaaaaaata/a//m (MIT license).
34

---

Published as a conference paper at ICLR 2026
D LIMITATIONS
Despite these contributions, our work comes with limitations: our construction Theorem A. only applies attention-only Transformers and relies slightly generalized position encoding method. Relaxing these constraints constitutes interesting problems for future research.
LARGE LANGUAGE MODELS USAGE DISCLOSURE
LLMs were used only to polish writing.
35


Reviews:
[{"review_id": "A5bdZqszNJ", "reviewer": "Reviewer_zTQW", "summary": "This work aims to provide a theoretical foundation for several popular test-time scaling paradigms. The paper's contributions are twofold:\n\nSeparation of Sample Complexity: The paper provides the first rigorous theoretical separation between two repeated sampling strategies: self-consistency and best-of-n (BofN). The authors prove that to achieve the same success probability, self-consistency requires a sample complexity of $\\Theta(1/\\Delta^2)$, whereas BofN only requires $\\Theta(1/\\Delta)$. Here, $\\Delta$ represents the probability gap between the correct answer and the second-most-likely answer. This result theoretically explains why BofN (when equipped with a good verifier) is generally more sample-efficient than self-consistency.\n\nRepresentation Ability of Self-Correction: The paper then analyzes the representation ability of self-correction with verifier feedback. The authors introduce the concept of a \"General-Purpose Transformer\" and prove that a Transformer architecture can be constructed to simulate an online learning algorithm over a pool of \"experts\" at test-time. Specifically, this Transformer can leverage reward feedback from a verifier to adaptively select experts and minimize regret, enabling it to solve multi-task problems without prior knowledge. This extends the known representation theory of Transformers from single-task to multi-task settings.", "questions": "The experiments in Section 5.1 show that larger models (GPT-mini, Gopher-44M) achieve near-perfect accuracy with self-correction feedback. Does this imply that these models are truly simulating the \"online learning over an expert pool\" described in Theorem 4.7? Or is it more likely that they are simply learning a much stronger, but simpler, heuristic (e.g., \"if the answer is 'no', flip the string\")? How do the authors view the gap between this complex theoretical construction and the observed empirical result?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work provides a solid theoretical basis for two widely-used but poorly-understood practical heuristics (BofN vs. Self-consistency). The $\\Theta(1/\\Delta)$ vs. $\\Theta(1/\\Delta^2)$ separation result is clear, important, and appears fundamental.\n\n- The framework of a \"General-Purpose Transformer\" and \"test-time online learning\" is a novel perspective. The proof that a Transformer architecture can (by construction) implement regret-minimizing online learning is a significant extension of Transformer representation theory, moving beyond standard \"universal approximator\" or \"Turing complete\" claims.\n\n- The synthetic experiments (on the 3-SAT task) are cleverly designed and successfully demonstrate both (1) the theoretical sample complexity separation and (2) the representation ability of the model to improve its performance via self-correction, validating the paper's core theoretical", "weaknesses": "- The theoretical construction of the \"General-Purpose Transformer\" (Propositions 4.2, 4.4) appears highly complex and relies on a specific \"Generalized Position Encoder\" (Definition 2.2) and attention sink techniques. This feels more like an existence proof (i.e., \"we can construct a Transformer that does this\") rather than an explanation of how existing LLMs might learn this behavior through standard pre-training.\n\n- The proof of self-correction's representation ability relies on a non-standard, more powerful \"Generalized Position Encoder\" that has access to set membership information of preceding tokens. This limits the applicability of this theoretical proof to specific (and perhaps not yet existing) architectures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3ncxEtUd2M", "reviewer": "Reviewer_9kos", "summary": "This paper analyzes the test‑time scaling of LLMs along two directions. First, it proves a sample‑complexity separation between repeated‑sampling strategies. Self‑consistency needs $\\Theta(1/\\Delta^2)$ samples while best‑of‑n needs $\\Theta(1/\\Delta)$, where $\\Delta$ is the probability gap between the most likely correct answer and the next alternative. Second, it develops a general‑purpose expressiveness framework, showing that a single wider Transformer equipped with verifier feedback can implement online learning over a pool of expert Transformers at inference time, yielding simple‑regret $\\mathrm{reg}(T)$ and final reward within $\\lambda+\\mathrm{reg}(T)$ of optimal. Experiments also illustrate that self‑correction can boost accuracy on a synthetic task and that best‑of‑n with a verifier can outperform self‑consistency on AIME’24/’25 even with far fewer samples.", "questions": "- It's not clearly specified what kind of verification feedback is obtained from Qwen3-32B model and how many steps of verification are performed on AIME benchmarks.\n- The expressiveness results depend on an attention‑precision assumption, could you justify why this is necessary?\n- The expressiveness proof depends on $\\epsilon-$thresholded attention assumption, which causes sparsity. Could you justify the necessity of this assumption?\n- I also want to bring to authors' attention that there's a previous work analyzing 3-SAT problems for self-correction, \"Learning to Self-Correct through Chain-of-Thought Verification\", as the relation to that work is not discussed.\n\nI don't have any more questions, please see weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper connects strands across CoT scaling and verification and makes a clear theoretical contribution on sampling and self‑correction.\n- The paper has good technical depth and the mathematical statements/proofs are rigorous with matching upper/lower bounds, together with complementary experiments.\n- It's also interesting to have that general‑purpose Transformer constructions manage to route to the correct expert in far less than $K$ trials, which is equivalent to brute‑force trials.", "weaknesses": "- The separation results assume a perfect reward for best‑of‑n, the theory does not capture the settings with noisy/imperfect verification.\n- The unified construction of transformer using experts is already engineered to convey the claim that transformer does online learning over a pool of experts with verification, so the conclusion feels built‑in. If it was the other way around (i.e., inductive bias of trained transformer on forming experts), the story would be more convincing.\n- It would be good to have confidence intervals on AIME accuracies with only 4 samples. \n- A full section is devoted to Section 3, yet the technical novelty here is limited as the separation bounds follow directly from known approximation results (w.r.t $\\ell_1, \\ell_2$, etc.) for multinomial distribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QMkvGltQDB", "reviewer": "Reviewer_jvdL", "summary": "This paper theoretically investigates the sample complexity and representation ability of test-time scaling paradigms for Large Language Models (LLMs), such as self-consistency, best-of-n, and self-correction.\n\nThis paper should be rejected because (1) The paper employs complex and abstract theoretical concepts that are either disconnected from the subsequent proposed method, (2) The paper's structure is fundamentally fragmented, (3) The central Self-Correction method's theoretical framework relies on the existence of an accruate verifier with feedback, which is unrealistic and severe limitation in standard Test-Time Scaling (TTS) paradigms. Seed detailed comments below.", "questions": "- What is the relation between the sample complexity proof and the proposed method?\n- How can one obtain a oracle verifier with feedback in practice?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.  The paper provides a novel theoretical framework to analyze the sample complexity of Test-Time Scaling (TTS) methods, establishing a clear separation result between self-consistency ($\\Theta(1/\\Delta^2)$) and best-of-n ($\\Theta(1/\\Delta)$).\n    \n2.  It offers a new perspective on self-correction, proving its representational power to enable a single Transformer to simulate online learning over a pool of experts (Bandit problem) at test time, thus extending the theory of Transformers from single-task to multi-task settings.", "weaknesses": "1.  The paper lacks a unified motivation, splitting into two seemingly disconnected parts: the sample complexity analysis of repeated sampling methods (self-consistency and best-of-n) and the theoretical analysis of Self-Correction with Verifier Feedback. The connection between the two main results is not clearly established.\n    \n2.  The analysis of Self-Correction with Verifier Feedback relies on the existence of an _accurate_ verifier, which is generally not a realistic assumption for a test-time scaling paradigm. Specifically, the modeling of the LLM inference process as a Bandit problem, where a General-Purpose Transformer (conceptually similar to MoE) learns to select an expert based on verifier feedback, is novel but appears disconnected from practical Test-Time Scaling (TTS) scenarios.\n    \n3.  The paper's structure is confusing. The Introduction elaborates on the implementation details of the \"General-Purpose Transformer,\" while the dedicated Method section provides minimal subsequent discussion. This makes the Introduction overly dense and difficult to follow. The authors should prioritize an intuitive understanding and the main \"takeaway\" conclusions of the General-Purpose Transformer concept in the Introduction, moving the implementation specifics to the Method section or an Appendix.\n    \n4.  The reasoning in the claim \"We illustrated this mechanism in Figure 2. As a result, the action sequence achieves $o(1)$ regret and the response sequence is generated from the corresponding expert selected by the latest action. Therefore, the response sequence also achieves regret $o(1)$\" is unclear. It is not immediately obvious how merely illustrating a mechanism in Figure 2 leads to the conclusion of $o(1)$ regret for the action sequence.\n    \n5.  The Generalized Position Encoder introduced in the Preliminary section appears to be completely irrelevant to the rest of the paper's analysis and discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yyvFQwySSN", "reviewer": "Reviewer_YT7w", "summary": "This paper explores the theoretical foundations of test-time scaling methods for large language models (LLMs), focusing on the sample efficiency and representational power of strategies like self-consistency, best-of-n, and self-correction. The authors first establish that best-of-n sampling is significantly more sample-efficient than self-consistency for arriving at a correct answer. Secondly, they demonstrate that a Transformer model, when provided with verifier feedback, can simulate online learning over a pool of \"expert\" models during test time. This allows a single Transformer architecture to solve a variety of tasks without needing to know the specific task in advance, thereby extending the theory of Transformer expressiveness to multi-task scenarios. The paper's theoretical claims are then validated through empirical experiments.", "questions": "- Is it possible to establish a sample complexity result of the self-correct method for a comparison with boN and SC to match the result in Table 1?\n- While I appreciate the multitask construction run general purpose transformer, it seems an independent result which is used to construct an online learning transformer. This result seems does not directly connect to self correctness but instead in-context RL [1][2], which is widely studied in literature. Could authors clarify more on this?\n\n\n[1] Lin, Licong, Yu Bai, and Song Mei. \"Transformers as decision makers: Provable in-context reinforcement learning via supervised pretraining.\" arXiv preprint arXiv:2310.08566 (2023).\n[2] Lee, Jonathan, et al. \"Supervised pretraining can learn in-context reinforcement learning.\" Advances in Neural Information Processing Systems 36 (2023): 43057-43083.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* This paper provides a novel conceptual framework for how a single Transformer can achieve multi-task representation.\n* Framing self-correction as an online learning problem (i.e., selecting an optimal \"expert\" ) is an interesting approach.", "weaknesses": "* The comparison between best-of-n and self-consistency is unfair. BoN is granted access to a \"perfect verifier\" while SC is not, making its superior efficiency an expected outcome of having an external signal based not he standard concentration results\n* The theoretical model relies on non-standard components, e.g., generalized position encoders. It is unclear if this specific construction applies to the mechanisms of standard Transformers given information beyond positions provided.\n* The experiment in 5.1 demonstrates the capacity for self-correction, but it does not validate that this occurs via the specific \"expert-selection\" mechanism proposed in the theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)