[2509.21091] Best-of-$\infty$ -- Asymptotic Performance of Test-Time Compute

Statistics > Machine Learning arXiv:2509.21091 (stat) [Submitted on 25 Sep 2025 (v1), last revised 3 Mar 2026 (this version, v2)] Title:Best-of-$\infty$ -- Asymptotic Performance of Test-Time Compute Authors:Junpei Komiyama, Daisuke Oba, Masafumi Oyamada View a PDF of the paper titled Best-of-$\infty$ -- Asymptotic Performance of Test-Time Compute, by Junpei Komiyama and Daisuke Oba and Masafumi Oyamada View PDF HTML (experimental) Abstract:We study best-of-$N$ for large language models (LLMs) where the selection is based on majority voting. In particular, we analyze the limit $N \to \infty$, which we denote as \boinflower. While this approach achieves impressive performance in the limit, it requires an infinite test-time budget. To address this, we propose an adaptive generation scheme that selects $N$ based on answer agreement, thereby efficiently allocating inference-time computation. Beyond adaptivity, we extend the framework to weighted ensembles of multiple LLMs, showing that such mixtures can outperform any individual model. The optimal ensemble weighting is formulated and efficiently computed as a mixed-integer linear program. Extensive experiments demonstrate the effectiveness of our approach. Comments: Subjects: Machine Learning (stat.ML); Artificial Intelligence (cs.AI); Machine Learning (cs.LG) Cite as: arXiv:2509.21091 [stat.ML]   (or arXiv:2509.21091v2 [stat.ML] for this version)   https://doi.org/10.48550/arXiv.2509.21091 Focus to learn more arXiv-issued DOI...