CoBa: Cost-Effective Test-Time Scaling via Compute-...

CoBa: Cost-Effective Test-Time Scaling via Compute-... | AI Research

Key Takeaways

CoBa (Compute-Balanced routing) addresses the inefficiency of test-time scaling in large language models by treating reasoning as a dynamic compute-allocatio...
Test-time scaling is often implemented by spending more compute along one axis: sampling more solutions, extending a chain of thought, or applying a stronger evaluator.
Under a fixed inference budget, these choices compete.
This paper formulates test-time reasoning as a compute-allocation problem in which a system must decide whether the next unit of compute should be spent on generation, verification, or stopping.
We introduce CoBa, a compute-balanced routing policy that first obtains a small set of candidates, applies cheap verification broadly, and routes uncertain or high-value candidates to stronger verification.

Paper AbstractExpand

Test-time scaling is often implemented by spending more compute along one axis: sampling more solutions, extending a chain of thought, or applying a stronger evaluator. Under a fixed inference budget, these choices compete. This paper formulates test-time reasoning as a compute-allocation problem in which a system must decide whether the next unit of compute should be spent on generation, verification, or stopping. We introduce CoBa, a compute-balanced routing policy that first obtains a small set of candidates, applies cheap verification broadly, and routes uncertain or high-value candidates to stronger verification. On 3,129 example-generator evaluations spanning MATH-500, AIME 2024/2025, AMC 2023, and procedural symbolic reasoning, CoBa-Routed-Strong reaches 85.13% macro accuracy, statistically matching a self-evaluation weighted-voting proxy at 85.20% while using 49.1% fewer parameter-weighted tokens. It also matches best-of-16 majority voting within 0.01 macro-accuracy points while using 58.9% fewer parameter-weighted tokens; paired tests retain a small best-of-16 edge at substantially higher cost. Paired bootstrap tests show significant gains over single-sample decoding, while the remaining gap to the pool oracle exposes headroom for sharper routing. For local reasoning systems, test-time scaling becomes a question of where the next computation is most valuable.

CoBa (Compute-Balanced routing) addresses the inefficiency of test-time scaling in large language models by treating reasoning as a dynamic compute-allocation problem. Instead of applying a uniform amount of compute to every problem—such as always sampling a fixed number of solutions or using a heavy verifier—CoBa routes compute based on the specific needs of each task. It decides whether to generate more candidates, apply lightweight verification, invoke a stronger verifier, or stop, aiming to maximize accuracy while minimizing the total cost of parameter-weighted tokens.

How CoBa Works

The system follows a staged routing procedure that separates candidate generation from verification. First, it generates a small, initial set of candidates. It then uses a lightweight judge to evaluate all candidates and checks for answer agreement. If the system is confident in the top answer, it stops. If the result is uncertain, it continues to sample more candidates or routes the most promising ones to a stronger, more expensive verifier. This approach ensures that expensive computational resources are reserved for ambiguous or high-value candidates rather than being spent equally on every problem.

Performance and Efficiency

In experiments across 3,129 evaluations—including MATH-500, AIME, and AMC datasets—the CoBa-Routed-Strong variant achieved 85.13% macro accuracy. This performance is statistically comparable to a self-evaluation weighted-voting proxy (85.20%) and best-of-16 majority voting (85.12%). However, CoBa-Routed-Strong achieved these results with significantly lower resource consumption: it used 49.1% fewer parameter-weighted tokens than the self-evaluation proxy and 58.9% fewer than best-of-16 majority voting.

Strategic Allocation

The research suggests that test-time scaling is most effective when compute is treated as a limited budget. By comparing CoBa against various baselines, the authors show that uniform strategies often over-allocate resources to simple problems while under-allocating to difficult ones. CoBa’s routing policy allows the system to scale its effort based on the difficulty of the input, effectively concentrating the budget where it is most likely to change the final outcome.

Limitations and Future Directions

The gap between CoBa’s performance and the "pool oracle"—the theoretical upper bound if the best candidate were always selected—indicates room for improvement. On datasets like AIME 2025, this gap suggests that while better routing helps, some failures are due to the quality of the initial candidate pool rather than the verification process. The authors note that future improvements will require pairing more selective routing with better candidate generation, as deeper verification cannot recover a correct answer if one is not present in the generated set.