Pith. sign in

REVIEW 4 major objections 4 minor 1 cited by

Sample Complexity and Representation Ability of Test-time Scaling Paradigms

T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper proves that self-correction with verifier feedback lets a single Transformer architecture solve multiple tasks without knowing which task is asked, and that best-of-n is quadratically more sample-efficient than self-consistency.

desk verdict The sample complexity separation is solid, but Theorem 4.7's routing construction doesn't actually generate actions with f0, so the main expressiveness claim doesn't follow from the written proof. read the letter →

arxiv 2506.05295 v2 pith:MWOIJRFX submitted 2025-06-05 cs.LG cs.AIstat.ML

Baihe Huang , Shanda Li , Tianhao Wu , Yiming Yang , Ameet Talwalkar , Kannan Ramchandran , Michael I. Jordan , Jiantao Jiao This is my paper
classification cs.LGcs.AIstat.ML MSC 68T0768Q32
keywords test-timescalingself-consistencybest-of-nself-correctionTransformerexpressivenesssamplecomplexitygeneral-purposeverifierfeedback
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper is trying to establish two theoretical results about test-time scaling. First, it gives matching sample-complexity bounds showing that self-consistency needs Θ(1/Δ²) independent samples from a model to output the correct answer, while best-of-n needs only Θ(1/Δ), where Δ is the gap between the probability of the correct answer and the second most likely answer. Second, it shows that a Transformer with verifier feedback can simulate online learning over a pool of expert Transformers at test time, so a single 'general-purpose' architecture can provably solve K different tasks without being told which task a query belongs to. The paper also runs a small synthetic experiment indicating that self-correction with verifier signals improves accuracy, especially for larger models. If the results hold, they change how we compare test-time strategies: best-of-n is the more sample-efficient repeated-sampling method, and self-correction is not just a heuristic but a mechanism with a provable expressiveness advantage.

What carries the argument

The load-bearing mechanism is a generalized position encoder (Definition 2.2) that encodes, for each token position, the set-membership of every preceding token relative to expert vocabularies, plus an attention-sink positional-encoding scheme (Lemmas A.2 and A.3). These allow the unified Transformer to stack the attention blocks of all experts, layer by layer, and to route each token through exactly one expert's computation: when generating an action, only the regret-minimizing Transformer f0 is active, and when generating a response, only the selected expert is active; all other experts' attention 'sinks' to a dummy token. The final guarantee then follows directly from the simple-regret bound of the bandit algorithm implemented by f0.

What would settle it

For the sample-complexity claim, construct a model where the correct answer has probability gap Δ and check whether self-consistency succeeds with n = 1/Δ samples (far below the claimed 1/Δ² requirement); if it does, the lower bound is false. For the expressiveness claim, take any instantiable regret-minimizing f0 from the cited constructions, run the self-correction protocol on a concrete K-expert instance, and measure whether the empirical expected reward gap stays within λ + reg(T); a violation at lengths allowed by Nmax would refute the construction.

Watch

Extended reading notes

Core claim

The central discovery is a construction theorem: for any collection of K expert Transformers and any reward function, there exists a unified Transformer φ of width O(K)·d and depth L+O(1) that, when run under a self-correction protocol with verifier feedback and a regret-minimizing Transformer f0, produces a final response whose expected reward is within λ+reg(T) of the optimal reward, where λ is the best expert's suboptimality and reg(T) is the simple regret of f0 after T rounds. Alongside it, the paper proves a sample-complexity separation: self-consistency requires Θ(1/Δ²) samples while best-of-n requires Θ(1/Δ). The pieces fit together because repeated sampling produces i.i.d. attempts, while self-correction provably updates the next attempt based on reward feedback.

Load-bearing premise

The expressiveness theorem assumes that a Transformer f0 already exists that implements a bandit algorithm with the claimed simple regret over the expert pool—the paper outsources this existence to universal approximation and prior work—and it assumes a generalized position encoder that depends on set membership of past tokens, not the standard positional encoding of deployed models.

Editorial extensions

If this is right

  • Best-of-n should be preferred over self-consistency when a reliable reward signal is available, because it achieves the same correctness guarantee with a factor of roughly 1/Δ fewer samples.
  • A single Transformer can be built once for a set of experts and then solve any query those experts can solve, without task detection at inference time.
  • Adding a new expert to the general-purpose architecture costs O(K) width and only O(1) extra depth, so the unified architecture scales linearly in the number of experts.
  • Self-correction with verifier feedback has a provable advantage over i.i.d. repeated sampling: later attempts are correlated through the learned reward signal, and the regret shrinks as the number of correction rounds T grows.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • This suggests a new reading of mixture-of-experts: rather than learning a static router, the router can be a test-time online-learning process that uses verifier feedback, so the same architecture could adapt to a changing distribution of queries.
  • The sample-complexity separation is stated for the model's own output distribution; for deployed systems where the reward model is imperfect, the best-of-n guarantee should be read as holding for the reward proxy, not necessarily for ground-truth correctness.
  • One testable extension is to replace the assumed regret-minimization Transformer f0 with a trained policy and measure whether the final-response reward gap shrinks at the rate reg(T) predicted by the bandit algorithm; a mismatch would indicate that the f0 assumption is the practical bottleneck.
  • Because the proof relies on a set-membership positional encoder rather than standard positional encodings, adapting the construction to deployed positional encodings is a concrete open engineering question.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. This paper studies two test-time scaling paradigms. In the first part, it analyzes the sample complexity of self-consistency and best-of-n sampling, proving that self-consistency needs Θ(1/Δ²) samples to identify the most likely (correct) answer while best-of-n needs only Θ(1/Δ), where Δ is the probability gap between the correct and second-most-likely answers. In the second part, it introduces a notion of "general-purpose Transformer" and claims that, with verifier feedback and a regret-minimizing Transformer, a single Transformer architecture can route among multiple expert Transformers at test time and achieve expected reward within λ + reg(T) of optimal. The paper also reports synthetic 3-SAT experiments in which self-correction improves test accuracy.

Significance. The sample-complexity separation between self-consistency and best-of-n is clean, explicitly stated, and directly relevant to current LLM decoding practice; if fully established, it would be a useful theoretical result. The multi-task expressiveness framework is also conceptually interesting: embedding expert Transformers into one wider Transformer and using attention-sink positional encodings to route among them is a novel construction. The paper is honest about the generalized position encoder and attention-only restriction. However, the central expressiveness theorem has a proof gap that is load-bearing, and the lower-bound proofs in Section 3 contain fixable but real technical errors. The paper's headline claim that a single Transformer can "provably" solve multiple tasks is currently conditional on an unconstructed regret-minimizing Transformer and on a routing construction that does not appear to implement Algorithm 1.

major comments (4)
  1. [§4.2, Theorem 4.7 and Appendix A.5]
  2. [Appendix A.1, lower bound of Theorem 3.1]
  3. [Appendix A.2, lower bound of Theorem 3.2]
  4. [§4.2, Definition 4.6 and Theorem 4.7]
minor comments (4)
  1. [§4.2 and Remark 4.3]
  2. [Appendix A.7, Claim A.5]
  3. [Appendix A.4, proof of Proposition 4.4]
  4. [Throughout]

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the main expressiveness claim is a transparent reduction whose regret term is an explicitly assumed input, not a hidden derivation.

full rationale

The sample-complexity theorems (3.1 and 3.2) are derived from first principles using concentration inequalities, Berry-Esseen, and explicit hard instances, so they are self-contained. The routing results (Propositions 4.2 and 4.4) construct attention-sink positional encodings from explicit matrices and prove the required attention identities, so they do not define their conclusions into their inputs. Theorem 4.7 is a reduction: it assumes a Regret-Minimization Transformer f0 with simple regret reg(T) (Definition 4.6), and its conclusion is the same reg(T) plus the λ-suboptimality of the best expert. The proof in Appendix A.5 states the regret bound directly from the assumption and then uses the routing propositions to transfer it to responses, so the bound is inherited rather than fitted or derived from a self-citation. The existence of f0 is explicitly outsourced to external universal-approximation and bandit constructions, notably reference [55], which is not a self-citation. The only overlapping-author citation is [50] in the Figure 1 caption, which is illustrative and not load-bearing. The acknowledged limitation in Section 7 concerns attention-only Transformers and the generalized position encoder, both stated openly. There is no fitted parameter later renamed as a prediction and no self-citation chain that forces the central claim, so no circular step is present.

Assumptions & free parameters 0 free parameters · 6 assumptions · 1 invented entities

No numerical parameters are fitted to data in the theoretical results. The central constructions rely on standard concentration and embedding tools plus domain assumptions about the model class (attention-only, finite precision, generalized position encoding) and the test-time protocol (exact verifier rewards). The main unproven input is the regret-minimizing Transformer f0, which is borrowed from universal approximation and prior bandit-Transformer results.

assumptions (6)
  • standard math Berry-Esseen theorem and multinomial concentration bound (Claim A.5)
    Used in Theorem 3.1 upper and lower bounds to control the difference between empirical and true answer probabilities.
  • standard math Johnson-Lindenstrauss lemma (Claim A.4)
    Used in Lemmas A.2 and A.3 to build near-orthogonal positional vectors with dimension O(log Nmax).
  • domain assumption Existence of a regret-minimizing Transformer f0 with simple regret reg(T) over the expert action space
    Assumed in Definition 4.6 and Theorem 4.7; the paper cites universal approximation and [55] but gives no explicit construction with the required simple-regret guarantee.
  • domain assumption Generalized position encoder depending on set membership of all previous tokens (Definition 2.2)
    The attention-sink routing construction requires the position encoder to know which vocabulary subset each previous token belongs to; this is not the standard positional encoding of deployed Transformers.
  • domain assumption Attention-only Transformer with softmax precision epsilon (Definition 2.1)
    The constructions assume that attention scores below a threshold are zeroed, a finite-precision model that differs from exact softmax.
  • domain assumption Verifier provides exact reward r(q,u) for every generated response at test time
    Algorithm 1 and Theorem 4.7 assume access to a reward oracle; noisy or missing verification is not addressed.
invented entities (1)
  • Regret-Minimization Transformer f0
    purpose: Acts as an online-learning router that selects which expert to use at each self-correction round in Theorem 4.7.
    The paper postulates f0 with simple regret reg(T) but does not construct it or provide a falsifiable handle; the theorem is conditional on its existence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sample Complexity and Representation Ability of Test-time Scaling Paradigms." pith.science (2026). https://pith.science/paper/MWOIJRFX

@misc{pith2026250605295,
  author       = {Pith},
  title        = {Pith review of: Sample Complexity and Representation Ability of Test-time Scaling Paradigms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MWOIJRFX}},
  note         = {Machine review of arXiv:2506.05295}
}
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.

Figures

Figures reproduced from arXiv: 2506.05295 by the authors.

Figure 1
Figure 1. An example from [50] of test-time online learning, where the Transformer progressively learns that finite-element method solves the partial differential equation with higher accuracy. Proposition 1.2 (Informal statement of Theorem 4.7). There exists a generic way to construct a wider transformer f from any Transformer-based expert models f1, . . . , fE such that, when provided with reward-based feedback, f can gener… view at source ↗
Figure 2
Figure 2. As a result, the action sequence achieves [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 2
Figure 2. Illustration of the attention sink behavior in the self-correcting Transformer. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figures from the paper (3 more)
Figure 3
Figure 3. Figure 3: Illustration of the general-purpose Transformer that combines Transformers over different [PITH_FULL_IMAGE:figures/full_fig_p006_3.png]
Figure 4
Figure 4. Figure 4: Illustration of the general-purpose Transformer that combines Transformers over the same [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Accuracy comparisons of different models with/without self-correction at test time. In our experiment, we construct datasets using 3-SAT problems with 4 variables and 20 clauses. The lengths of the data strings are set to 5. We gen￾erate 10000 instances for training an…

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Optimal Bayesian Stopping for Efficient Inference of Consistent LLM Answers

    stat.ML 2026-02 conditional novelty 6.0 of 10

    Tracking only the counts of the two most frequent LLM answers is asymptotically as sample-efficient as the full Bayesian posterior in an adaptive self-consistency procedure, cutting LLM calls by up to half.

Reference graph

Works this paper leans on

126 extracted references · 40 canonical work pages · cited by 1 Pith paper

  1. [1]

    Aggarwal and S

    P. Aggarwal and S. Welleck. L1: Controlling how long a reasoning model thinks with reinforcement learning. In arXiv, 2025

    2025

  2. [2]

    Agrawal and R

    S. Agrawal and R. Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in neural information processing systems, 30, 2017

    2017

  3. [3]

    Akyürek, D

    E. Akyürek, D. Schuurmans, J. Andreas, T. Ma, and D. Zhou. What learning algorithm is in-context learning? investigations with linear models. arXiv preprint arXiv:2211.15661, 2022

    arXiv 2022

  4. [4]

    Alberti, N

    S. Alberti, N. Dern, L. Thesing, and G. Kutyniok. Sumformer: Universal approximation for efficient transformers. In T. Doster, T. Emerson, H. Kvinge, N. Miolane, M. Papillon, B. Rieck, and S. Sanborn, editors, Proceedings of 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML), volume 221 of Proceedings of Machine Learning R...

    2023

  5. [5]

    C. Anil, Y . Wu, A. Andreassen, A. Lewkowycz, V . Misra, V . Ramasesh, A. Slone, G. Gur-Ari, E. Dyer, and B. Neyshabur. Exploring length generalization in large language models. arXiv preprint arXiv:2207.04901, 2022

    arXiv 2022

  6. [6]

    Y . Bai, F. Chen, H. Wang, C. Xiong, and S. Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection. arXiv preprint arXiv:2306.04637, 2023

    arXiv 2023

  7. [7]

    Barak, B

    B. Barak, B. Edelman, S. Goel, S. Kakade, E. Malach, and C. Zhang. Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 35:21750–21764, 2022

    2022

  8. [8]

    Bhattamishra, K

    S. Bhattamishra, K. Ahuja, and N. 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), pages 7096–7116, 2020

    2020

Show all 126 references
  1. [9]

    Bhattamishra, A

    S. Bhattamishra, A. Patel, and N. Goyal. On the computational power of transformers and its implications in sequence modeling. In Proceedings of the 24th Conference on Computational Natural Language Learning, pages 455–475, 2020

    2020

  2. [10]

    Botta, Y

    E. Botta, Y . Li, A. Mehta, J. T. Ash, C. Zhang, and A. Risteski. On the query complexity of verifier-assisted language generation. arXiv preprint arXiv:2502.12123, 2025

    2025 arXiv

  3. [11]

    Brown, J

    B. Brown, J. Juravsky, R. Ehrlich, R. Clark, Q. V . Le, C. Ré, and A. Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024

    2024 arXiv

  4. [12]

    Brown, B

    T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-V oss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Ch...

    1901

  5. [13]

    Bubeck, V

    S. Bubeck, V . Chandrasekaran, R. Eldan, J. Gehrke, E. Horvitz, E. Kamar, P. Lee, Y . T. Lee, Y . Li, S. Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.12712, 2023

    2023 arXiv

  6. [14]

    Carpentier and M

    A. Carpentier and M. Valko. Simple regret for infinitely many armed bandits. In International Conference on Machine Learning, pages 1133–1141. PMLR, 2015

    2015

  7. [15]

    G. Chen, M. Liao, C. Li, and K. Fan. Alphamath almost zero: Process supervision without process. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  8. [16]

    J. Chen, J. Ren, X. Chen, C. Yang, R. Sun, and S. Ö. Arık. Sets: Leveraging self-verification and self-correction for improved test-time scaling. arXiv preprint arXiv:2501.19306, 2025

    2025

  9. [17]

    L. Chen, J. Q. Davis, B. Hanin, P. Bailis, I. Stoica, M. Zaharia, and J. Zou. Are more LLM calls all you need? towards the scaling properties of compound AI systems. In Conference on Neural Information Processing Systems, 2024

    2024

  10. [18]

    X. Chen, M. Lin, N. Schärli, and D. Zhou. Teaching large language models to self-debug. In International Conference on Learning Representations, 2024

    2024

  11. [19]

    X. Chen, J. Xu, T. Liang, Z. He, J. Pang, D. Yu, L. Song, Q. Liu, M. Zhou, Z. Zhang, et al. Do not think that much for 2+ 3=? on the overthinking of o1-like llms. arXiv preprint arXiv:2412.21187, 2024

    2024 arXiv

  12. [20]

    Chowdhery, S

    A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. W. Chung, C. Sutton, S. Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022

    2022 arXiv

  13. [21]

    Cobbe, V

    K. Cobbe, V . Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021

    2021 arXiv

  14. [22]

    Codeforces, 2025

    codeforce. Codeforces, 2025

    2025

  15. [23]

    Cuadron, D

    A. Cuadron, D. Li, W. Ma, X. Wang, Y . Wang, S. Zhuang, S. Liu, L. G. Schroeder, T. Xia, H. Mao, et al. The danger of overthinking: Examining the reasoning-action dilemma in agentic tasks. arXiv preprint arXiv:2502.08235, 2025

    2025 arXiv

  16. [24]

    Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning

    DeepSeek-AI. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. In arXiv, 2025

    2025

  17. [25]

    Dehghani, S

    M. Dehghani, S. Gouws, O. Vinyals, J. Uszkoreit, and Ł. Kaiser. Universal transformers.arXiv preprint arXiv:1807.03819, 2018

    2018 arXiv

  18. [26]

    B. L. Edelman, S. Goel, S. Kakade, and C. Zhang. Inductive biases and variable creation in self- attention mechanisms. In International Conference on Machine Learning, pages 5793–5831. PMLR, 2022

    2022

  19. [27]

    Elhage, N

    N. Elhage, N. Nanda, C. Olsson, T. Henighan, N. Joseph, B. Mann, A. Askell, Y . Bai, A. Chen, T. Conerly, et al. A mathematical framework for transformer circuits. Transformer Circuits Thread, 1:1, 2021. 14

    2021

  20. [28]

    Even-Dar, S

    E. Even-Dar, S. Mannor, Y . Mansour, and S. Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems.Journal of machine learning research, 7(6), 2006

    2006

  21. [29]

    G. Feng, B. Zhang, Y . Gu, H. Ye, D. He, and L. Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems, 36:70757–70798, 2023

    2023

  22. [30]

    D. J. Foster, S. M. Kakade, J. Qian, and A. Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021

    2021 arXiv

  23. [31]

    Z. Gao, B. Niu, X. He, H. Xu, H. Liu, A. Liu, X. Hu, and L. Wen. Interpretable contrastive monte carlo tree search reasoning. In arXiv, 2024

    2024

  24. [32]

    S. Garg, D. Tsipras, P. S. Liang, and G. Valiant. What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583–30598, 2022

    2022

  25. [33]

    Golovneva, T

    O. Golovneva, T. Wang, J. Weston, and S. Sukhbaatar. Contextual position encoding: Learning to count what’s important. arXiv preprint arXiv:2405.18719, 2024

    2024 arXiv

  26. [34]

    Aime problems and solutions, 2025

    Google. Aime problems and solutions, 2025

    2025

  27. [35]

    Z. Gou, Z. Shao, Y . Gong, yelong shen, Y . Yang, N. Duan, and W. Chen. CRITIC: Large language models can self-correct with tool-interactive critiquing. In International Conference on Learning Representations, 2024

    2024

  28. [36]

    D. Guo, D. Yang, H. Zhang, J. Song, R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi, et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025

    2025 arXiv

  29. [37]

    Z. He, G. Feng, S. Luo, K. Yang, L. Wang, J. Xu, Z. Zhang, H. Yang, and D. He. Two stones hit one bird: Bilevel positional encoding for better length extrapolation. arXiv preprint arXiv:2401.16421, 2024

    2024 arXiv

  30. [38]

    Hendrycks, C

    D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021

    2021

  31. [39]

    Hoffmann, S

    J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. de las Casas, L. A. Hendricks, J. Welbl, A. Clark, T. Hennigan, E. Noland, K. Millican, G. van den Driessche, B. Damoc, A. Guy, S. Osindero, K. Simonyan, E. Elsen, O. Vinyals, J. W. Rae, and L. Sifr...

    2022

  32. [40]

    Huang, A

    A. Huang, A. Block, D. J. Foster, D. Rohatgi, C. Zhang, M. Simchowitz, J. T. Ash, and A. Krishnamurthy. Self-improvement in language models: The sharpening mechanism. arXiv preprint arXiv:2412.01951, 2024

    2024 arXiv

  33. [41]

    Huang, Z

    Z. Huang, Z. Wang, S. Xia, X. Li, H. Zou, R. Xu, R.-Z. Fan, L. Ye, E. Chern, Y . Ye, Y . Zhang, Y . Yang, T. Wu, B. Wang, S. Sun, Y . Xiao, Y . Li, F. Zhou, S. Chern, Y . Qin, Y . Ma, J. Su, Y . Liu, Y . Zheng, S. Zhang, D. Lin, Y . Qiao, and P. Liu. Olympicarena: Benchmarking...

    2024

  34. [42]

    Irvine, D

    R. Irvine, D. Boubert, V . Raina, A. Liusie, Z. Zhu, V . Mudupalli, A. Korshuk, Z. Liu, F. Cremer, V . Assassi, C.-C. Beauchamp, X. Lu, T. Rialan, and W. Beauchamp. Rewarding chatbots for real-world engagement with millions of users. In arXiv, 2023

    2023

  35. [43]

    Jamieson, M

    K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. lil’ucb: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423–439. PMLR, 2014

    2014

  36. [44]

    Joshi, G

    N. Joshi, G. Vardi, A. Block, S. Goel, Z. Li, T. Misiakiewicz, and N. Srebro. A theory of learning with autoregressive chain of thought. arXiv preprint arXiv:2503.07932, 2025

    2025 arXiv

  37. [45]

    Kaplan, S

    J. Kaplan, S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Rad- ford, J. Wu, and D. Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020

    2001 arXiv

  38. [46]

    Kimi k1.5: Scaling reinforcement learning with llms

    Kimi. Kimi k1.5: Scaling reinforcement learning with llms. In arXiv, 2025

    2025

  39. [47]

    D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015

    2015

  40. [48]

    Kumar, V

    A. Kumar, V . Zhuang, R. Agarwal, Y . Su, J. D. Co-Reyes, A. Singh, K. Baumli, S. Iqbal, C. Bishop, R. Roelofs, et al. Training language models to self-correct via reinforcement learning. arXiv preprint arXiv:2409.12917, 2024

    2024 arXiv

  41. [49]

    S. Li, X. Chen, D. He, and C.-J. Hsieh. Can vision transformers perform convolution? arXiv preprint arXiv:2111.01353, 2021

    2021 arXiv

  42. [50]

    S. Li, T. Marwah, J. Shen, W. Sun, A. Risteski, Y . Yang, and A. Talwalkar. Codepde: An inference framework for llm-driven pde solver generation. arXiv preprint arXiv:2505.08783, 2025

    2025

  43. [51]

    S. Li, Z. Song, Y . Xia, T. Yu, and T. Zhou. The closeness of in-context learning and weight shifting for softmax regression. arXiv preprint arXiv:2304.13276, 2023

    2023 arXiv

  44. [52]

    Y . Li, A. Kirchmeyer, A. Mehta, Y . Qin, B. Dadachev, K. Papineni, S. Kumar, and A. Risteski. Promises and pitfalls of generative masked language modeling: theoretical framework and practical guidelines. arXiv preprint arXiv:2407.21046, 2024

    2024 arXiv

  45. [53]

    Z. Li, H. Liu, D. Zhou, and T. Ma. Chain of thought empowers transformers to solve inherently serial problems. In The Twelfth International Conference on Learning Representations, 2024

    2024

  46. [54]

    Likhosherstov, K

    V . Likhosherstov, K. Choromanski, and A. Weller. On the expressive power of self-attention matrices. arXiv preprint arXiv:2106.03764, 2021

    2021 arXiv

  47. [55]

    L. Lin, Y . Bai, and S. Mei. Transformers as decision makers: Provable in-context reinforcement learning via supervised pretraining. arXiv preprint arXiv:2310.08566, 2023

    2023 arXiv

  48. [56]

    Q. Lin, B. Xu, Z. Li, Z. Hao, K. Zhang, and R. Cai. Leveraging constrained monte carlo tree search to generate reliable long chain-of-thought for mathematical reasoning. In arXiv, 2025

    2025

  49. [57]

    B. Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and C. Zhang. Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.10749, 2022. 16

    2022 arXiv

  50. [58]

    S. Luo, S. Li, S. Zheng, T.-Y . Liu, L. Wang, and D. He. Your transformer may not be as powerful as you expect. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022

    2022

  51. [59]

    Madaan, N

    A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri, S. Prabhumoye, Y . Yang, S. Gupta, B. P. Majumder, K. Hermann, S. Welleck, A. Yazdanbakhsh, and P. Clark. Self-refine: Iterative refinement with self-feedback. In Thirty-seventh Conference on...

    2023

  52. [60]

    Mei and Y

    S. Mei and Y . Wu. Deep networks as denoising algorithms: Sample-efficient learning of diffusion models in high-dimensional graphical models. arXiv preprint arXiv:2309.11420, 2023

    2023 arXiv

  53. [61]

    Merrill and A

    W. Merrill and A. Sabharwal. The expressive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923, 2023

    2023 arXiv

  54. [62]

    Munkhbat, N

    T. Munkhbat, N. Ho, S. H. Kim, Y . Yang, Y . Kim, and S.-Y . Yun. Self-training elicits concise reasoning in large language models. In arXiv, 2025

    2025

  55. [63]

    Nguyen, D

    A. Nguyen, D. Mekala, C. Dong, and J. Shang. When is the consistent prediction likely to be a correct prediction? In arXiv, 2024

    2024

  56. [64]

    Olsson, N

    C. Olsson, N. Elhage, N. Nanda, N. Joseph, N. DasSarma, T. Henighan, B. Mann, A. Askell, Y . Bai, A. Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209.11895, 2022

    2022 arXiv

  57. [65]

    Openai o1 system card

    OpenAI. Openai o1 system card. In arXiv, 2024

    2024

  58. [66]

    Openai o3-mini, 2024

    OpenAI. Openai o3-mini, 2024

    2024

  59. [67]

    Paszke, S

    A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32:8026–8037, 2019

    2019

  60. [68]

    Pérez, P

    J. Pérez, P. Barceló, and J. Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75):1–35, 2021

    2021

  61. [69]

    Petrov, P

    A. Petrov, P. H. Torr, and A. Bibi. Prompting a pretrained transformer can be a universal approximator. In Proceedings of the 41st International Conference on Machine Learning , pages 40523–40550, 2024

    2024

  62. [70]

    J. Qiu, Y . Lu, Y . Zeng, J. Guo, J. Geng, H. Wang, K. Huang, Y . Wu, and M. Wang. Treebon: Enhancing inference-time alignment with speculative tree-search and best-of-n sampling. arXiv preprint arXiv:2410.16033, 2024

    2024 arXiv

  63. [71]

    Y . Qu, M. Y . Yang, A. Setlur, L. Tunstall, E. E. Beeching, R. Salakhutdinov, and A. Ku- mar. Optimizing test-time compute via meta reinforcement fine-tuning. arXiv preprint arXiv:2503.07572, 2025

    2025 arXiv

  64. [72]

    Russo and B

    D. Russo and B. Van Roy. Learning to optimize via information-directed sampling.Operations Research, 66(1):230–252, 2018. 17

    2018

  65. [73]

    P. G. Sessa, R. Dadashi, L. Hussenot, J. Ferret, N. Vieillard, A. Ramé, B. Shariari, S. Perrin, A. Friesen, G. Cideron, S. Girgin, P. Stanczyk, A. Michi, D. Sinopalnikov, S. Ramos, A. Héliou, A. Severyn, M. Hoffman, N. Momchev, and O. Bachem. Bond: Aligning llms with best-of-n...

    2024

  66. [74]

    Setlur, N

    A. Setlur, N. Rajaraman, S. Levine, and A. Kumar. Scaling test-time compute without verification or rl is suboptimal. arXiv preprint arXiv:2502.12118, 2025

    2025 arXiv

  67. [75]

    B. Shi, M. Tang, K. R. Narasimhan, and S. Yao. Can language models solve olympiad programming? In Conference on Language Modeling, 2024

    2024

  68. [76]

    C. V . Snell, J. Lee, K. Xu, and A. Kumar. Scaling LLM test-time compute optimally can be more effective than scaling parameters for reasoning. In The Thirteenth International Conference on Learning Representations, 2025

    2025

  69. [77]

    Y . Song, G. Wang, S. Li, and B. Y . Lin. The good, the bad, and the greedy: Evaluation of llms should not ignore non-determinism. In arXiv, 2024

    2024

  70. [78]

    Y . Song, H. Zhang, C. Eisenach, S. Kakade, D. Foster, and U. Ghai. Mind the gap: Examining the self-improvement capabilities of large language models. arXiv preprint arXiv:2412.02674, 2024

    2024 arXiv

  71. [79]

    Z. Sun, L. Yu, Y . Shen, W. Liu, Y . Yang, S. Welleck, and C. Gan. Easy-to-hard generalization: Scalable alignment beyond human supervision. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  72. [80]

    Y . Tian, B. Peng, L. Song, L. Jin, D. Yu, L. Han, H. Mi, and D. Yu. Toward self-improvement of LLMs via imagination, searching, and criticizing. In Conference on Neural Information Processing Systems, 2024

    2024

  73. [81]

    V on Oswald, E

    J. V on Oswald, E. Niklasson, E. Randazzo, J. Sacramento, A. Mordvintsev, A. Zhmoginov, and M. Vladymyrov. Transformers learn in-context by gradient descent. arXiv preprint arXiv:2212.07677, 2022

    2022 arXiv

  74. [82]

    V on Oswald, E

    J. V on Oswald, E. Niklasson, E. Randazzo, J. Sacramento, A. Mordvintsev, A. Zhmoginov, and M. Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, pages 35151–35174. PMLR, 2023

    2023

  75. [83]

    Z. Wan, X. Feng, M. Wen, S. M. McAleer, Y . Wen, W. Zhang, and J. Wang. Alphazero-like tree-search can guide large language model decoding and training. In Forty-first International Conference on Machine Learning, 2024

    2024

  76. [84]

    X. Wang, J. Wei, D. Schuurmans, Q. V . Le, E. H. Chi, S. Narang, A. Chowdhery, and D. Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023

    2023

  77. [85]

    Y . Wang, Q. Liu, J. Xu, T. Liang, X. Chen, Z. He, L. Song, D. Yu, J. Li, Z. Zhang, et al. Thoughts are all over the place: On the underthinking of o1-like llms. arXiv preprint arXiv:2501.18585, 2025

    2025 arXiv

  78. [86]

    C. Wei, Y . Chen, and T. Ma. Statistically meaningful approximation: a case study on ap- proximating turing machines with transformers. Advances in Neural Information Processing Systems, 35:12071–12083, 2022. 18

    2022

  79. [87]

    J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V . Le, D. Zhou, et al. Chain-of- thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837, 2022

    2022

  80. [88]

    Welleck, X

    S. Welleck, X. Lu, P. West, F. Brahman, T. Shen, D. Khashabi, and Y . Choi. Generating sequences by learning to self-correct. In The Eleventh International Conference on Learning Representations, 2023

    2023

  81. [89]

    Y . Wu, Z. Sun, S. Li, S. Welleck, and Y . Yang. Scaling inference computation: Compute- optimal inference for problem-solving with language models. In Workshop on Mathematical Reasoning and AI at NeurIPS’24, 2024

    2024

  82. [90]

    Y . Wu, Z. Sun, S. Li, S. Welleck, and Y . Yang. Inference scaling laws: An empirical analysis of compute-optimal inference for LLM problem-solving. In The Thirteenth International Conference on Learning Representations, 2025

    2025

  83. [91]

    Y . Wu, Y . Wang, T. Du, S. Jegelka, and Y . Wang. When more is less: Understanding chain-of- thought length in llms. In arXiv, 2025

    2025

  84. [92]

    G. Xiao, Y . Tian, B. Chen, S. Han, and M. Lewis. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2309.17453, 2023

    2023 arXiv

  85. [93]

    A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, C. Zheng, D. Liu, F. Zhou, F. Huang, F. Hu, H. Ge, H. Wei, H. Lin, J. Tang, J. Yang, J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Zhou, J. Lin, K. Dang, K. Bao, K. Yang, L. Yu, L. Deng, M. L...

    2025 arXiv

  86. [94]

    S. Yao, B. Peng, C. Papadimitriou, and K. Narasimhan. Self-attention networks can process bounded hierarchical languages. arXiv preprint arXiv:2105.11115, 2021

    2021 arXiv

  87. [95]

    C. Yun, S. Bhojanapalli, A. S. Rawat, S. Reddi, and S. Kumar. Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations, 2020

    2020

  88. [96]

    Zaheer, G

    M. Zaheer, G. Guruganesh, K. A. Dubey, J. Ainslie, C. Alberti, S. Ontanon, P. Pham, A. Ravula, Q. Wang, L. Yang, et al. Big bird: Transformers for longer sequences. Advances in neural information processing systems, 33:17283–17297, 2020

    2020

  89. [97]

    Zhang, S

    D. Zhang, S. Zhoubian, Z. Hu, Y . Yue, Y . Dong, and J. Tang. ReST-MCTS*: LLM self-training via process reward guided tree search. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  90. [98]

    Zhang, G

    K. Zhang, G. Li, H. Zhang, and Z. Jin. Hirope: Length extrapolation for code models using hierarchical position. arXiv preprint arXiv:2403.19115, 2024

    2024 arXiv

  91. [99]

    Zhang, F

    Q. Zhang, F. Lyu, Z. Sun, L. Wang, W. Zhang, Z. Guo, Y . Wang, I. King, X. Liu, and C. Ma. What, how, where, and how well? a survey on test-time scaling in large language models. arXiv preprint arXiv:2503.24235, 2025. 19

    2025 arXiv

  92. [100]

    Zhang, M

    Y . Zhang, M. Khalifa, L. Logeswaran, J. Kim, M. Lee, H. Lee, and L. Wang. Small language models need strong verifiers to self-correct reasoning. In ACL (Findings), 2024

    2024

  93. [101]

    Zhang, S

    Y . Zhang, S. Wu, Y . Yang, J. Shu, J. Xiao, C. Kong, and J. Sang. o1-coder: an o1 replication for coding. In arXiv, 2024

    2024

  94. [102]

    H. Zhao, A. Panigrahi, R. Ge, and S. Arora. Do transformers parse while predicting the masked word? In H. Bouamor, J. Pino, and K. Bali, editors, Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 16513–16542, Singapore, Dec

    2023

  95. [104]

    For any i ≥ j1, j2, j3: (αi + β1)⊤A0(αj1 + β1) = (αi + β1)⊤A0(αj2 + β1) ≥ (αi + β1)⊤A0(αj1 + β0) + C0 (αi + β0)⊤A0(αi + β0) ≥ (αi + β0)⊤A0(αj1 + β1) + C0, (3)

  96. [105]

    For any i > j (αi + β1)⊤A(αi + β1) ≥ (αi + β1)⊤A(αj + β1) + C0 ≥ (αi + β1)⊤A(αj + β0) + 2C0, (4)

  97. [106]

    For any i ≥ j, j1 (αi + β1)⊤A1(αj + β0) = (αi + β1)⊤A1(αj1 + β1) + C0 (αi + β1)⊤A1(αi + β1) ≥ max{(αi + β1)⊤A1(αj1 + β1), (αi + β1)⊤A1(αj1 + β0)} + C0. (5) 22 We define ϕ as follows: for any Transformers f = (θ, pe, (K(l) h , Q(l) h , V(l) h )h∈[H],l∈[L], ϑ,V1), the Transforme...

  98. [107]

    For any i ≥ j1, j2, j3 and k, k′, k′′ ̸= 0: (αi + βk)⊤A0(αj1 + βk′) = (αi + βk)⊤A0(αj2 + βk′′ ) ≥ (αi + βk)⊤A0(αj1 + β0) + C0 (αi + β0)⊤A0(αi + β0) ≥ (αi + β0)⊤A0(αj1 + βk) + C0, (9)

  99. [108]

    For any i > jand k ̸= k′ ̸= 0 (αi + βk)⊤A(αi + βk) ≥ (αi + βk)⊤A(αj + βk′) + C0 ≥ (αi + βk)⊤A(αj + β0) + 2C0, (10) 25

  100. [109]

    , fK) is given by (eθ, fpe, ( eK(l) h , eQ(l) h , eV(l) h )h∈[KH +1],l∈[L+1], eϑ, V), where the tokenizer is given by eθ(v) = 1 (v /∈ V0) ·   θ1(v)

    For any i ≥ j, j1 and k ̸= k′, k′′ (αi + βk)⊤Ak′(αj + β0) = (αi + βk)⊤Ak′(αj1 + βk′′) + C0 (αi + βk)⊤Ak(αi + βk) ≥ max{(αi + βk)⊤Ak(αj1 + βk′′ ), (αi + βk)⊤Ak′(αj1 + β0)} + C0, (11) We define ϕ as follows: for any Transformers fk = (θk, pek, (K(l) k;h, Q(l) k;h, V(l) k;h)h∈[H]...

  101. [110]

    Attention sink to dummny token vi0 for mismatch expert: for any k′ ̸= κ and j ≤ n we have ( eQ(L) (k′−1)H+h eX (L) n )⊤( eK(L) (k′−1)H+h eX (L) j ) = (αn + βE(n))⊤Ak′(αj + βE(j)) ≤ (αn + βE(n))⊤Ak′(αi0 + βE(i0)) − C = ( eQ(L) (k′−1)H+h eX (L) n )⊤( eK(L) (k′−1)H+h eX (L) i0 ) ...

  102. [111]

    (18) Combining Eq

    Attention to oneself for matching expert: for any j ̸= i0 we have ( eQ(L) (κ−1)H+h eX (L) n )⊤( eK(L) (κ−1)H+h eX (L) j ) = (αn + βE(n))⊤Aκ(αj + βE(j)) ≥ (αn + βE(n))⊤Aκ(αi0 + βE(i0)) + C = ( eQ(L) (κ−1)H+h eX (L) n )⊤( eK(L) (κ−1)H+h eX (L) i0 ) + C, (17) and ( eQ(L) (κ−1)H+h...

  103. [112]

    For any k ̸= k′: α⊤ n Ak(αn + βk′) ≥ C0 +    α⊤ n Akαn α⊤ n Akαj α⊤ n Ak(αj + βk′′ ) , ∀0 ≤ j ≤ n, 1 ≤ k′′ ≤ K. (19)

  104. [113]

    For any k ∈ [K]: α⊤ n Akαn = α⊤ n Akα0 ≥ C0 +    α⊤ n Ak(αn + βk) α⊤ n Akαj α⊤ n Ak(αj + βk′) , ∀0 < j < n, k′ ̸= k. (20)

  105. [114]

    For any k, k′, k′′ ∈ [K]: (αn + βk′)⊤Ak(αn + βk′) ≥ C0 + (αn + βk′)⊤Akαj, ∀0 ≤ j ≤ n. (21)

  106. [115]

    (22) We define ϕ as follows: for any Transformers fk = (θk, pek, (K(l) k;h, Q(l) k;h, V(l) k;h)h∈[H],l∈[L], ϑk, V), k∈ [K] over V, the Transformer ef = ϕ(f1,

    For any 0 < j < n: α⊤ n Aαn ≥ α⊤ n A(αn + βk) + C0 ≥ C0 + max{α⊤ n Aαj, α⊤ n A(αj + βk′)}, ∀k, k′′ ∈ [K]. (22) We define ϕ as follows: for any Transformers fk = (θk, pek, (K(l) k;h, Q(l) k;h, V(l) k;h)h∈[H],l∈[L], ϑk, V), k∈ [K] over V, the Transformer ef = ϕ(f1, . . . , fK) i...

  107. [116]

    Attention sink to vξm for mismatch expert: for any k′ ̸= κ and j ≤ i we have ( eQ(l) (k′−1)H+h eX (l) i )⊤( eK(l) (k′−1)H+h eX (l) j ) ≤ ( eQ(l) (k′−1)H+h eX (l) i )⊤( eK(l) (k′−1)H+h eX (l) ξm ) − C. (29)

  108. [117]

    , ξ1 − 1, ξm + 1,

    Attention to task-relevant tokens for matching expert: for j ∈ {1, . . . , ξ1 − 1, ξm + 1, . . . , n}, and ξ1 ≤ j′ ≤ ξm we have ( eQ(l) (κ−1)H+h eX (l) i )⊤( eK(l) (κ−1)H+h eX (l) j ) ≥ ( eQ(l) (κ−1)H+h eX (l) i )⊤( eK(l) (κ−1)H+h eX (l) j′ ) + C. (30) and for j1 < j2 ∈ {1, . ...

  109. [118]

    Expert following: At t-th iteration, pg1 · prompt ∼ pfa(t) · q|u(t) 1:i−1 , where q|u(t) 1:i−1 is the token sequence obtained by concatenating the user query q and prior generated part in response t: u(t) 1:i−1. 37

  110. [119]

    Therefore by Proposition 4.2, we have u(t) i ∼ pfa(t) · q|u(t) 1:i−1

    Regret minimization: max a∗∈A r0(a∗) − E[r0(a(T ))] ≤ reg(T ). Therefore by Proposition 4.2, we have u(t) i ∼ pfa(t) · q|u(t) 1:i−1 . It follows that max u∗∈V ω r(q, u∗) − E[r(q, u(T ))] ≤ λ + Eu∼fk∗ (·|p)[r(q, u)] − Ea(T ) h Eu(T )∼fa(t) (·|q)[r(q, u(T ))] i ≤ λ + max a∗∈A r0...

  111. [120]

    For any k ̸= k′: α⊤ n Ak(αn + βk′) ≥ C +    α⊤ n Akαn α⊤ n Akαj α⊤ n Ak(αj + βk′′ ) , ∀0 ≤ j ≤ n, 1 ≤ k′′ ≤ K

  112. [121]

    For any k ∈ [K]: α⊤ n Akαn = α⊤ n Akα0 ≥ C +    α⊤ n Ak(αn + βk) α⊤ n Akαj α⊤ n Ak(αj + βk′) , ∀0 < j < n, k′ ̸= k

  113. [122]

    For any k, k′, k′′ ∈ [K]: (αn + βk′)⊤Ak(αn + βk′) ≥ C + (αn + βk′)⊤Akαj, ∀0 ≤ j ≤ n

  114. [123]

    38 Proof

    For any 0 < j < n: α⊤ n Aαn ≥ α⊤ n A(αn + βk) + C ≥ C + max{α⊤ n Aαj, α⊤ n A(αj + βk′)}, ∀k, k′′ ∈ [K]. 38 Proof. Notice that the following relations are sufficient to guarantee the desired properties α⊤ n Akαn = α⊤ n Akα0, α⊤ n Akβk′ = C, α⊤ n Akαn ≥ α⊤ n Akαj + α⊤ n Akβk′ + ...

  115. [124]

    For any i ≥ j1, j2, j3 and k, k′, k′′ ̸= 0: (αi + βk)⊤A0(αj1 + βk′) = (αi + βk)⊤A0(αj2 + βk′′) ≥ (αi + βk)⊤A0(αj1 + β0) + C (αi + β0)⊤A0(αi + β0) ≥ (αi + β0)⊤A0(αj1 + βk) + C

  116. [125]

    For any i > jand k ̸= k′ ̸= 0 (αi + βk)⊤A(αi + βk) ≥ (αi + βk)⊤A(αj + βk′) + C ≥ (αi + βk)⊤A(αj + β0) + 2C

  117. [126]

    39 Proof

    For any i ≥ j, j1 and k ̸= k′, k′′ (αi + βk)⊤Ak′(αj + β0) ≥ (αi + βk)⊤Ak′(αj1 + βk′′) + C (αi + βk)⊤Ak(αi + βk) ≥ max{(αi + βk)⊤Ak(αj1 + βk′′ ), (αi + βk)⊤Ak′(αj1 + β0)} + C. 39 Proof. Following the notations in Lemma A.2, let αi =   γi 0 0 0   , βk =   0 γ ek 1  ...

  118. [2023]

    20 A Proofs A.1 Proof of Theorem 3.1 Proof

    Association for Computational Linguistics. 20 A Proofs A.1 Proof of Theorem 3.1 Proof. Write O = {1, . . . , O} (O ∈ Z+) where i is the i-th most likely answer and let ni denote the number of occurrences of i. Then we have ˆp = 1 n (n1, . . . , nO) ∼ 1 n Multinomial(n, p), whe...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.