BOSS: Token-Budgeted Online Sampling and Selection for LLM Reasoning

Yupeng Chang; Yahan Li; Chenlu Guo; Diana Inkpen; Yuan Wu; Yi Chang

cs.AIOct 19, 2026

BOSS: Token-Budgeted Online Sampling and Selection for LLM Reasoning

Authors: Yupeng Chang, Yahan Li, Chenlu Guo, Diana Inkpen, Yuan Wu, Yi Chang

Organizations: School of Artificial Intelligence, Jilin University · Xingchen AGI Lab, China Telecom Artificial Intelligence (Beijing) Co., Ltd., China · Bilibili Inc., China · School of Electrical Engineering and Computer Science, University of Ottawa, Canada ·

Abstract

Test-time scaling can improve LLM reasoning, but existing approaches typically adapt generation or apply answer selection after a predetermined generation schedule. We study within-instance allocation: under a hard per-instance prompt-plus-completion token cap, when should inference stop, generate another candidate, or spend residual tokens adjudicating candidates already observed? BOSS is a training-free policy for this three-way decision, with worst-case budget checks before every generation and judge call. Its key contribution is online generation-adjudication allocation under one shared token ledger. Across two Llama-3.1 models and four reasoning benchmarks, BOSS attains the highest accuracy in 22 of 24 model-task-budget cells under the common hard cap. At Llama-3.1-8B and B=4k, it reaches 60.5 macro-average accuracy versus 58.6 for Adaptive-Consistency, 59.1 for TALE-EP, and 58.9 for fixed-schedule League. On identical Stage-I candidate pools, randomized A/B judging with repeated voting improves plurality from 58.4 to 60.3, with the full BOSS selector reaching 60.5. Approximately matched-cost controls further characterize how the benefit of adjudication changes with available inference budget. Together, these results establish generation-adjudication allocation as a distinct design axis for reasoning under strict per-instance caps.

Figures & tables

Figure 1: Overview of BOSS. Under the same hard cap $B$ , BOSS allocates residual tokens online among Return , Generate , and Adjudicate .

	GSM8K (EM)			MATH (EM)			GPQA-D (Acc)			MMLU-Pro (Acc)
Method	$2\mathrm{k}$	$4\mathrm{k}$	$8\mathrm{k}$	$2\mathrm{k}$	$4\mathrm{k}$	$8\mathrm{k}$	$2\mathrm{k}$	$4\mathrm{k}$	$8\mathrm{k}$	$2\mathrm{k}$	$4\mathrm{k}$	$8\mathrm{k}$
Base model: Llama-3.1-8B-Instruct
CoT@1 (Greedy)	84.5			51.9			30.4			48.3
SC (budgeted)	85.8	87.3	88.1	54.7	56.6	58.0	33.1	35.7	37.0	49.9	51.2	52.2
ESC ( Li et al., 2024 )	86.2	87.6	88.3	55.3	56.8	58.4	33.5	36.1	37.2	50.3	51.6	52.5
FFS ( Agarwal et al., 2025 )	86.9	87.2	87.5	54.5	55.7	56.0	32.2	33.3	33.8	49.5	50.1	50.8

Table 1: Accuracy (%) under fixed per-instance token budgets

B

. The budget counts all prompt and completion tokens consumed by each inference policy. Values are averaged over 5 random seeds. CoT@1 (Greedy) is budget-invariant because one deterministic generation uses far fewer tokens than the smallest budget (

2\mathrm{k}

); identical values across budgets are shown in merged cells. GPQA-D denotes GPQA-Diamond. Bold indicates the best result within each model block and column.

Method / control	Macro (%)
Adaptive-Consistency ( Aggarwal et al., 2023 )	58.6
TALE-EP ( Han et al., 2025 )	59.1
League (fixed schedule)	58.9
BOSS	60.5
No novelty transition	59.0
Fixed generation–selection split	59.3

Table 2: Targeted controls at Llama-3.1-8B-Instruct and

B=4\mathrm{k}

. “Macro” averages all four benchmarks. Same-pool rows reuse exactly the same Stage-I candidates and change only the selector.

Method	Mean tokens	Macro (%)
BOSS	$\approx$ 2,500	58.4
Adaptive-Consistency	2,508	58.6
BOSS	$\approx$ 3,100	59.4
TALE-EP	3,074	59.1
BOSS	$\approx$ 3,850	60.3
League	3,853	58.9

Table 3: Approximately cost-matched operating points for Llama-3.1-8B.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Hyperparameter	Value
Generation cap $L^{\mathrm{gen}}$	1024
Judge cap $L^{\mathrm{judge}}$	4
Judge replicates $R$	3
Consensus threshold $\tau_{\mathrm{cons}}$	0.70
Consensus gap $m_{\mathrm{gap}}$	2
Novelty window $W$	4

Appendix

Table 4: BOSS hyperparameters. Values are fixed after development tuning and are not selected using reported test instances.

	League (Fixed)					BOSS (Adaptive)
$B$	Gen.	Judge	Total	Util.%	Judge%	Gen.	Judge	Total	Util.%	Judge%
$1\mathrm{k}$	523	414	937	93.7	44.2	958	0	958	95.8	0.0
$2\mathrm{k}$	812	1103	1915	95.8	57.6	1445	492	1937	96.9	25.4
$4\mathrm{k}$	1634	2219	3853	96.3	57.6	1903	2044	3947	98.7	51.8
$8\mathrm{k}$	2542	5237	7779	97.2	67.3	1987	5924	7911	98.9	74.9

Appendix

Table 7: Mean realized token utilization over 5 random seeds. All prompt and completion tokens are counted.

Selector	Recovery (%)	Harm (%)
Randomized A/B + repeated	22.8	2.0
Full BOSS selector	25.1	2.2

Appendix

Table 9: Error-correction behavior on identical Stage-I candidate pools. Recovery is measured when plurality is wrong but the correct hypothesis is present; harm is measured when plurality is initially correct.

Variant	MATH	GPQA-D	Avg
BOSS (Full)	59.4	39.5	60.5
No early stop	58.0	38.7	59.6
No novelty transition	58.1	37.6	59.0
Fixed gen.–sel. split	58.5	38.1	59.3
Fixed-order single-vote judge	56.8	35.0	57.7
Round-robin scheduling	57.4	37.1	58.8

Appendix

Table 10: Component ablation at

B=4\mathrm{k}

with Llama-3.1-8B-Instruct. Selected columns are shown; “Avg” averages all four benchmarks.

$B$	Gen.	Judge	Entry (%)	Fallback (%)
$2\mathrm{k}$	1445	492	31.8	65.6
$4\mathrm{k}$	1903	2044	84.1	12.4
$8\mathrm{k}$	1987	5924	94.1	1.2

Appendix

Table 11: Observed BOSS allocation by hard budget. Gen./Judge are mean realized tokens; Entry/Fallback are trajectory rates.

Efficient Language Model Reasoning

Efficient language model reasoning studies how to improve problem-solving accuracy while reducing inference, memory, latency, and training costs.

See all 371 papers

Uncertainty-Aware Budget Allocation for Adaptive Test-Time Reasoning
May 26, 2026Manh Nguyen, Sunil Gupta, Hung LeEfficient Language Model Reasoning Adaptive Sampling
Applied Artificial Intelligence Initiative Deakin University, Australia
Avoiding Overthinking and Underthinking: Curriculum-Aware Budget Scheduling for LLMs
Mar 29, 2026Amirul Rahman, Aisha Karim, Kenji Nakamura +1Efficient Language Model Reasoning Inference-Time Compute Allocation
University of Malaya
ROI-Reasoning: Rational Optimization for Inference via Pre-Computation Meta-Cognition
Jan 7, 2026Muyang Zhao, Chunhao Tian, Qi Qi +1Cost-Aware Inference Metacognition in Language Models
Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China

May 26, 2026J/K move · Enter open · S save

Uncertainty-Aware Budget Allocation for Adaptive Test-Time Reasoning

Manh Nguyen, Sunil Gupta, Hung Le

Applied Artificial Intelligence Initiative Deakin University, Australia

Efficient Language Model Reasoning Adaptive Sampling Uncertainty Sampling Inference-Time Compute Allocation LLM Reasoning

Open paper AskPDF arXiv

Sampling multiple responses improves language model reasoning, but uniform compute allocation is inefficient because easy questions are over-sampled while hard questions remain under-explored. We propose Uncertainty-Aware Budget Allocation (UAB), a concave integer optimization framework that reallocates a fixed sampling budget using uncertainty estimated from the initial samples themselves. In Phase-1, every question receives a small fixed number of generations. Their answer disagreement, measured by vote entropy, provides a difficulty signal while these generations contribute to the final vote. In Phase-2, the remaining budget is allocated by a marginal-greedy algorithm that optimally solves a concave coverage-maximization surrogate, concentrating samples on questions whose initial answers disagree. Across five open-weight models (1.5B--27B parameters) and five reasoning benchmarks of varying difficulty, UAB improves average accuracy by

+2.3\%

over uniform allocation, and achieves gains of up to

+5.5\%

on individual benchmarks, with the largest gains in low-resource settings. Moreover, UAB meets the target budget exactly and requires no auxiliary model or additional LLM calls. Code is publicly available at https://github.com/manhitv/UAB.

Abstract

Efficient Language Model Reasoning

Explore similar work

Uncertainty-Aware Budget Allocation for Adaptive Test-Time Reasoning

Avoiding Overthinking and Underthinking: Curriculum-Aware Budget Scheduling for LLMs

ROI-Reasoning: Rational Optimization for Inference via Pre-Computation Meta-Cognition