Probabilistic Optimality for Inference-time Scaling
Youkang Wang, Jian Wang, Rubing Chen, Xiao-Yong Wei, Qing Li · 2025
Read Probabilistic Optimality for Inference-time Scaling by Youkang Wang, Jian Wang, Rubing Chen, Xiao-Yong Wei, Qing Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-22376.txt.
Introduction
Youkang Wang and co-authors put inference-time scaling of language models on a probability footing. Their twenty twenty-five paper, OptScale, asks how many parallel answers a model should draw before picking the best. Heuristic habits rule this choice today, wasting compute or starving hard questions.
Assuming samples are independent draws, the authors derive a floor on the count needed for a target success level. Their algorithm then sets the sample number on the fly per question. Easy prompts stop early; hard ones earn more tries. A principled dial for test-time compute helps labs spend GPU hours where they buy real accuracy.
Catalog record
| CREATOR | Youkang Wang, Jian Wang, Rubing Chen, Xiao-Yong Wei, Qing Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-22376
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Probabilistic Optimality for Inference-time Scaling Youkang Wang, Jian Wang, Rubing Chen, Xiao-Yong Wei, Qing Li Abstract Inference-time scaling has emerged as a powerful technique for enhancing the reasoning performance of Large Language Models (LLMs). However, existing approaches often rely on heuristic strategies for parallel sampling, lacking a principled foundation. To address this gap, we propose a probabilistic framework that formalizes the optimality of inference-time scaling under the assumption that parallel samples are independently and identically distributed (i.i.d.), and where the Best-of-N selection strategy follows a probability distribution that can be estimated. Within this framework, we derive a theoretical lower bound on the required number of samples to achieve a target performance level, providing the first principled guidance for compute-efficient scaling. Leveraging this insight, we develop OptScale , a practical algorithm that dynamically determines the optimal number of sampled responses. OptScale employs a language model-based predictor to estimate probabilistic prior parameters, enabling the decision of the minimal number of samples needed that satisfy predefined performance thresholds and confidence levels. Extensive experiments on mathematical reasoning benchmarks (including MATH-500, GSM8K, AIME, and AMC) demonstrate that OptScale significantly reduces sampling overhead while remaining better or on par with state-of-the-art reasoning performance. Our work offers both a theoretical foundation and a practical solution for principled inference-time scaling, addressing a critical gap in the efficient deployment of LLMs for complex reasoning. The source code will be open upon acceptance at https://open_upon_acceptance . 1 1 footnotetext: Corresponding author. 1 Introduction The reasoning capabilities of large language models (LLMs) have become a pivotal research area, given their ability to tackle complex cognitive tasks spanning mathematical reasoning, decision-making, and problem-solving zhang2025and ; yang2025towards . Recent advances demonstrate that inference-time scaling can substantially enhance reasoning performance by enabling the model to generate diverse candidate solutions, creating a richer space for comprehensive inference through answer aggregation chen2025seal ; ding2025dynamic ; wan2024dynamic . This approach is particularly valuable for proprietary LLMs, as it can operate purely at inference time without requiring model modifications. Although effective, these techniques face a fundamental efficiency challenge: the linear relationship between candidate solutions and computational costs leads to prohibitive token consumption. This has created an urgent need for optimized scaling strategies that navigate the Pareto frontier between reasoning performance and computational efficiency, maximizing accuracy while minimizing redundant computation universityOptimizingLLMTestTime2025 . Parallel inference-time scaling, a dominant paradigm in this space, operates by generating N candidate responses in parallel and selecting the optimal output via learned rules (e.g., verifiers) prmlessons or consensus (e.g., majority voting) wang2023self . Current approaches fall into three categories: verifier-based approaches that train auxiliary models to rerank candidates yang2025towards ; data-driven methods that fine-tune LLMs on high-quality reasoning traces to improve solution quality qu2025optimizing ; and inference-time techniques that dynamically adjust the number of candidates per input chen2025seal . While these methods demonstrate practical effectiveness, they suffer from significant theoretical limitations. Current strategies rely heavily on empirical heuristics and implicit priors (such as learned verifier preferences or empirical token budgets) without proper mathematical formulation. Crucially, the field lacks systematic derivation of these priors from first principles or rigorous quantification of the fundamental efficiency-accuracy trade-offs inherent in parallel scaling. This paper presents a foundational study that bridges this critical gap through three key contributions: First, we formulate a probabilistic framework that formally establishes the optimality conditions for parallel inference-time scaling under i.i.d. assumptions, where the Best-of-N selection process follows an estimable probability distribution. This theoretical formulation provides a principled understanding of scaling behavior in probabilistic terms. Second, we derive a theoretical lower bound on the number of samples required to achieve any target performance level. This result offers mathematically grounded guidance for compute-efficient scaling, representing a significant advance beyond current heuristic approaches. Third, we develop OptScale , an efficient algorithm that implements these theoretical insights in practice. OptScale dynamically determines the optimal sample size by employing an LM-based predictor to estimate prior parameters, ensuring minimal computational cost while satisfying predefined performance thresholds and confidence levels. Our experiments demonstrate OptScale ’s computational efficiency: it automatically terminates sampling for simple questions while preventing excessive computation on intractable ones. To our knowledge, this work presents the first comprehensive treatment of parallel inference-time scaling that: 1) establishes a rigorous probabilistic model of the scaling process, 2) derives fundamental limits on scaling efficiency, and 3) provides a practical algorithmic implementation that approaches these theoretical optima. 2 Related Work 2.1 LLM Reasoning The ability of LLMs to perform complex reasoning tasks has garnered significant attention and seen rapid advancements yu2024natural ; xu2025towards . Early successes with prompting strategies like Chain-of-Thought (CoT) wei2022chain demonstrated that LLMs could produce step-by-step reasoning traces, significantly improving performance on tasks requiring logical deduction, mathematical problem-solving, and multi-step planning ahn2024large ; snell2024scaling ; liang2024improving . This foundational work has spurred the development of more sophisticated prompting techniques, including Self-Consistency wan2024dynamic , which generates multiple reasoning paths and selects the most consistent answer, and Tree-of-Thought (ToT) reasoning, which allows models to explore diverse reasoning trajectories in parallel yao2023tree ; long2023large . 2.2 Parallel Inference-time Scaling Despite these advances, efficiently scaling LLMs at inference time remains a challenge. Parallel inference-time scaling has emerged as a key strategy to enhance LLM performance by enlarging computational resources during inference. This approach involves generating N candidate solutions in parallel and selecting the best one using various methods snell2024scaling . Existing techniques can be categorized into the following three groups: Verifier-based Scaling Methods. To improve inference-time performance, many studies use auxiliary models, known as verifiers or Process Reward Models (PRMs), to assess the quality of candidate solutions generated by a primary LLM setlur2024rewarding ; qu2025optimizing . These verifiers predict the correctness of a solution or assign it a quality score, guiding the selection of the final answer by re-ranking the N outputs. For example, some methods train verifiers using human feedback or generated labels bai2022training . Recent work examines how the interaction between generators, PRMs, and problem difficulty affects optimal test-time scaling prmlessons . However, relying on additional models increases computational overhead, and the strategies for determining N often lack a theoretical foundation. Model-tuning Based Methods with High-quality Data. Some approaches aim to improve the output quality by enhancing the generator LLM itself. This is often done by fine-tuning the base LLM on datasets rich in high-quality reasoning traces or problem-solution pairs qu2025optimizing ; chen2025rethinking . Research efforts focus on creating specialized datasets for mathematical or coding reasoning to embed these capabilities directly into the model xu2025phi . Techniques like Reinforcement Learning from Human Feedback (RLHF) or process supervision, where models are rewarded for correct reasoning steps instead of just final answers, also fall into this category ke2025survey . While these methods enhance the generator’s initial quality, they do not address computational efficiency during inference, which is a critical aspect of scaling. Dynamic Inference-based Scaling Methods. Recognizing the limitations of fixed N , several methods explore dynamic approaches to adjust computation at inference time. These techniques adapt the number of generated candidates or computational resources based on the input query or the ongoing generation process ding2025dynamic ; wan2024dynamic . For example, some methods allocate more computation to complex problems or where initial candidate solutions show high uncertainty or disagreement chen2025seal . Approaches like dynamic