Search papers, labs, and topics across Lattice.
This paper introduces Uncertainty-Aware Budget Allocation (UAB), a method for adaptively allocating sampling budget in LLM reasoning by estimating per-question uncertainty using average negative log-likelihood (ANLL) from initial generations. A marginal-greedy algorithm then solves a concave coverage-maximization surrogate to allocate the remaining budget, prioritizing uncertain questions. Experiments across six models and five reasoning benchmarks demonstrate that UAB improves average accuracy by up to 3% and up to 5% on individual benchmarks, particularly in low-resource settings, without requiring auxiliary models or additional LLM calls.
LLMs can reason more accurately without extra compute: just intelligently reallocate your sampling budget based on a simple uncertainty estimate.
Sampling multiple responses improves language model reasoning, but uniform compute allocation is inefficient: 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 based on per-question uncertainty estimated at no additional inference cost. In Phase 1, every question receives one generation; its average negative log-likelihood (ANLL), extracted directly from output log-probabilities, serves as a difficulty signal while the generation contributes to the final vote. In Phase 2, the remaining budget is allocated by a marginal-greedy algorithm that solves a concave coverage-maximization surrogate exactly: uncertain questions receive more sampling budget while confident questions receive fewer additional samples. Evaluated on six open-weight and black-box models spanning 1.5B to 27B parameters and five reasoning benchmarks covering math, logic, and preference tasks, UAB outperforms baselines by up to +3% in average accuracy and up to +5% on individual benchmarks, with the largest gains in low-resource settings, requiring no auxiliary model or additional LLM call. Code is publicly available at https://github.com/manhitv/UAB.
