# Test-Time Scaling via Budgeted Multi-Attribute Verification

arXiv: https://arxiv.org/abs/2609.34322 · HTML: https://mlsanity.com/paper/2609.34322/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 29 of its 33 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 29 of 29)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Universal Self-Consistency for Large Language Model Generation](https://mlsanity.com/paper/2311.17311/) (2023)
- [Let's Sample Step by Step: Adaptive-Consistency for Efficient Reasoning and Coding with LLMs](https://mlsanity.com/paper/2305.11860/) (2023)
- [Learning How Hard to Think: Input-Adaptive Allocation of LM Computation](https://mlsanity.com/paper/2410.04707/) (2024)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Sampling-Efficient Test-Time Scaling: Self-Estimating the Best-of-N Sampling in Early Decoding](https://mlsanity.com/paper/2503.01422/) (2025)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Multi-Agent Verification: Scaling Test-Time Compute with Multiple Verifiers](https://mlsanity.com/paper/2502.20379/) (2025)
- [When To Solve, When To Verify: Compute-Optimal Problem Solving and Generative Verification for LLM Reasoning](https://mlsanity.com/paper/2504.01005/) (2025)
- [Good Arm Identification via Bandit Feedback](https://mlsanity.com/paper/1710.06360/) (2017)
- [LLM-as-a-Verifier: A General-Purpose Verification Framework](https://mlsanity.com/paper/2607.05391/) (2026)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Solve-Detect-Verify: Inference-Time Scaling with Flexible Generative Verifier](https://mlsanity.com/paper/2505.11966/) (2025)
- [Strategic Scaling of Test-Time Compute: A Bandit Learning Approach](https://mlsanity.com/paper/2506.12721/) (2025)
- [DynScaling: Efficient Verifier-free Inference Scaling via Dynamic and Integrated Sampling](https://mlsanity.com/paper/2506.16043/) (2025)
- [Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Bandits](https://mlsanity.com/paper/2410.15564/) (2024)
- [Best Arm Identification with Resource Constraints](https://mlsanity.com/paper/2402.19090/) (2024)
- [Constrained Best Arm Identification in Grouped Bandits](https://mlsanity.com/paper/2412.08031/) (2024)
- [Multi-thresholding Good Arm Identification with Bandit Feedback](https://mlsanity.com/paper/2503.10386/) (2025)
- [Constrained Best Arm Identification with Tests for Feasibility](https://mlsanity.com/paper/2511.09808/) (2025)
- [Fixed-Budget Constrained Best Arm Identification in Grouped Bandits](https://mlsanity.com/paper/2603.04007/) (2026)

## Abstract (arXiv)

Verifying LLM-generated answers under a shared computational budget requires jointly deciding which candidates to inspect and which verification attributes to evaluate. We formulate this problem as multi-attribute good-arm identification under a global budget: each candidate is an arm evaluated along several costly attributes, and the goal is to certify as many candidates as possible whose mean scores exceed the prescribed thresholds on all attributes. We propose textscBMA-GAI, an algorithm that combines cost-aware arm selection with adaptive sampling of attributes. Every observation serves both to guide adaptive allocation and to support anytime-valid certification, which removes the need for a separate confirmation stage. We establish an asymptotic coverage guarantee for textscBMA-GAI and derive a matching information-theoretic converse that characterizes the intrinsic complexity of the problem, thereby proving that textscBMA-GAI is first-order optimal away from critical budget levels. Experiments on synthetic benchmarks and an LLM answer-verification task show that textscBMA-GAI allocates the verification budget more efficiently and certifies more high-quality candidates than competing methods.