CoBa: Cost-Effective Test-Time Scaling via Compute-Balanced Routing

arXiv:2608.07424 · cs.AI · Submitted 2026-08-10 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Paper Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "CoBa: Cost-Effective Test-Time Scaling via Compute-Balanced Routing".

Jane: The paper was written by Yan Zhou, Yue Ouyang, Kaiyang Zheng and Suncheng Xiang from Changsha University of Science and Technology and Shanghai Jiao Tong University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Paper summary: Tom: We finally get to sit down with this one, and honestly the framing grabbed me on the first read. Most test-time scaling work treats sampling more, thinking longer, and evaluating harder as separate knobs, and this paper says they all draw from the same fixed inference budget, so they compete.

Jane: Then the move is to treat that competition as an allocation problem. The system has to decide whether the next unit of compute goes to generating another candidate, checking a candidate with a cheap judge, running a strong verifier, or stopping altogether. That last action — stopping — is the one most test-time scaling papers forget to include.

Lu: They formalize it nicely, too. There's a state made of the candidates collected, the verifier scores, the remaining budget, and the history, and an action space spanning sampling, verification at different strengths, and stopping. Everything the policy knows is right there in the state vector.

Meng: And the cost metric they lean on is parameter-weighted tokens — each model's token count multiplied by its size in billions. A token from a 14B model is simply more expensive than one from an 8B model, and accuracy-only tables never show that.

Lalam: The headline result follows from that. Their strongest variant hits 85 point 13 percent macro accuracy, statistically matching a self-evaluation weighted-voting proxy at 85 point 20 percent, but using 49 point 1 percent fewer parameter-weighted tokens. Against best-of-16 majority voting it lands within 0 point 01 accuracy points while using 58 point 9 percent fewer.

Tom: Those numbers come from 3,129 example-generator evaluations across MATH-500, eyeME 2024 and 2025, AMC 2023, and the hard Reasoning Gym subset. Three local generators — Qwen3-14B, Phi-4-reasoning, and Qwen3-8B — all replayed over shared candidate pools.

Jane: So the claim is that you can reach the accuracy of heavy sampling or broad self-evaluation just by being selective about which candidates deserve the expensive verification. Cheap evidence first, strong verification only where it can change the decision. That's the whole method in one sentence.

Meng: But the paper doesn't oversell, and I respect that. Best-of-16 keeps a small paired edge of about 0 point 70 points, and it pays for that edge with 2 point 43 times the parameter-weighted cost. So the result is a Pareto improvement over moderate baselines and a cost cut at the high-accuracy end.

Lu: Then there's the oracle gap to keep in mind. The pool oracle sits at 91 point 36 percent, so plenty of headroom remains. Sometimes the correct answer sits in the pool and routing misses it; sometimes the pool simply contains no right answer.

Lalam: And that distinction ends up being the most productive part of the paper. If the answer exists but goes unselected, the next unit of compute should sharpen verification. If it doesn't exist, the next unit should expand generation. The oracle gap becomes a design signal instead of just a score.

Tom: Good place to start digging in, then. The first page sets up the central hypothesis that accuracy gains and cost savings have to be evaluated together, not as separate virtues.

Page 1 of the paper: Jane: Page one opens with exactly that hypothesis, and the supporting argument is simple. A system that always samples sixteen candidates or always runs a strong evaluator can be accurate, but it spends the same expensive actions on problems that were already settled.

Tom: "Settled and ambiguous examples" — that phrase carries the paper. Once sampled answers agree and the cheap judge is confident, extra compute is just going through the motions. Routing exists to eliminate that waste.

Lu: Page one also establishes the control-loop picture. The figure shows a state vector, a budget tracker, cheap evidence signals, and an action router all connected. It's a controller wrapped around the language model, deciding what happens next.

Meng: And the contributions listed there — formalizing test-time reasoning as allocation, introducing a reproducible routing policy with light and strong verification tiers, and running controlled replay experiments — the replay piece is the one that earns trust.

Lalam: The replay protocol means every method sees the same sixteen generated candidates per problem. Routing can change which candidates get inspected and selected, but it can't invent new generations. That keeps the comparison honest.

Tom: The abstract also gives the clearest statement of the method anywhere in the paper. Get a small candidate set, apply cheap verification broadly, then route uncertain or high-value candidates to stronger verification. Cheap broadly, strong narrowly.

Jane: And they're explicit that they are not proposing a new generator or a new verifier. The models are the same ones the baselines use. CoBa only changes when those models get called — that's the entire intervention.

Lu: That's the cleanest experimental design you could ask for. If accuracy holds while cost drops, the gain has to come from the allocation policy, not from a cleverer model. The ablation structure on later pages confirms that.

Meng: The evaluation scope is visible on this page as well — three locally served generators on competition math and procedural symbolic reasoning. No closed APIs, no unavailable checkpoints anywhere in the stack.

Lalam: So the whole paper runs on hardware a decent local setup can reproduce. That's increasingly rare in this corner of the literature, and it makes the numbers worth taking seriously.

Tom: Then page two positions the work against the field — the sampling line, the verification line, the adaptive compute line — and shows what's missing from each of them.

Page 2 of the paper: Jane: Page two runs through that landscape with a clear pattern in mind. Self-consistency buys diversity, chain-of-thought buys reasoning depth, verifiers buy selection — each family treated as its own recipe, its own scaling knob.

Tom: The gap the paper identifies is that nobody treats those as competing draws on one budget. Under a fixed inference budget, spending the next token on sampling means not spending it on verification. That's the hole the routing framework fills.

Lu: There's also a current and practical discussion of verifier cost becoming a first-order variable. With generative process reward models and evaluation-time scaling using reasoning models as judges, strong verification is no longer cheap. Deciding who gets verified is a real economic decision.

Meng: The adaptive allocation line — FrugalGPT, RouteLLM, early-stopping monitors like interwhen — shares the intuition that inputs deserve different amounts of compute. CoBa applies that intuition inside a reasoning workflow, routing among sampling, verification, and stopping rather than between whole models.

Lalam: The positioning is pointed without being dismissive. The section concedes that each method family does something real — diversity, selection, waste avoidance — and then says the contribution is treating those as complementary actions under one controller.

Tom: The surveys of test-time scaling get cited here too, organizing the field by what, how, and where compute gets scaled. CoBa's answer is essentially "at the action level, guided by cheap evidence."

Jane: The end of page two starts the formal setup, and that's where the definitions land. State, action space, and the two cost metrics — total tokens and parameter-weighted tokens — all appear there.

Meng: Right, and that parameter-weighted metric is the one most papers ignore. A 14B token is not the same cost as an 8B token, and any allocation policy that treats them identically is blind to the thing it's supposed to optimize.

Lu: The objective function on that page has a sensitivity parameter lambda that trades accuracy against budget. The experiments use fixed replay policies, but the framework itself has a tuning dial.

Lalam: So by the end of page two, the machinery is in place. Page three then makes everything concrete — the routing algorithm, the stop criterion, the scoring rule, and the three variants that trace the cost-accuracy curve.

Page 3 of the paper: Tom: Page three delivers Algorithm 1, and the structure is almost elegant in its simplicity. Warm up with two candidates, score all of them with the cheap frequency check and the lightweight judge, then enter the decision loop.

Jane: The loop is where the adaptivity lives. The policy computes answer agreement, score gap, and uncertainty. If the top answer holds at least 60 percent agreement and the lightweight judge scores it at least 0 point 7, the system stops; otherwise it generates one more candidate and scores it cheaply.

Lu: That stop criterion is fully transparent, and that matters. It's not a learned function hidden inside a network; it's literally "the answers agree and the cheap judge is confident, so we're done." Anyone can audit it against the logs.

Meng: The final ranking score is explicit as well. Answer frequency carries weight 0 point 20, the 8B judge score carries 0 point 30, the optional process-verifier score carries 0 point 15 when it parses, and the strong 14B deep verifier carries 0 point 45.

Lalam: The weight distribution tells the story. The strongest verifier has the biggest weight, but it only touches the top-K routed candidates. Cheap evidence decides who gets routed; strong evidence decides among the routed few.

Jane: One detail that matters here is the renormalization when process-verifier scores are missing. Unrouted candidates don't get an artificial penalty just because they skipped the strong verifier. The weights renormalize, so absent evidence is never misread as a negative signal.

Tom: The routing variants trace a clean curve from that base. Light runs just the two-candidate warm-up with no extra sampling. Balanced expands to four candidates and routes two to the strong verifier. Strong expands to eight and routes four.

Lu: And the table on that page locks those values in before final aggregation, which is a real commitment. Test labels stay reserved for evaluation, so the thresholds can't be accused of being cherry-picked.

Meng: Then the offline replay protocol makes every method comparable. Sixteen candidates per example, same pools for everyone. CoBa chooses prefixes, subsets, and routed verification calls, but nothing beyond what the baselines could also see.

Lalam: That's what makes the later cost comparisons meaningful. When the paper reports a 49 percent token reduction at matching accuracy, both methods drew from the same generated evidence, so the difference is allocation.

Tom: With that foundation set, page four fills in the experimental machinery — datasets, models, baseline taxonomy, metrics — all the choices that give those numbers their credibility.

Page 4 of the paper: Jane: Page four introduces the benchmark suite in full. Five test sets — MATH-500, eyeME 2024, eyeME 2025, AMC 2023, and the hard Reasoning Gym subset — giving 1,043 unique examples and 3,129 example-generator evaluations across fifteen pairs of datasets and generators.

Tom: The hardware story is relatable, too. Local RTX 3090 GPUs, FP16 or quantized serving, vLLM for OpenAI-compatible serving. That's a modest setup, and it means the results reflect what many practitioners actually run.

Lu: The model lineup is fixed across the whole study. Qwen3-14B and Qwen3-8B generate, Phi-4-reasoning generates as well, the 8B model acts as the lightweight judge, and the 14B model acts as the strong outcome verifier. Phi-4-reasoning also supplies auxiliary process-verifier scores.

Meng: And the paper is upfront that those process-verifier scores were sparse in the final run, so the main comparison centers on outcome verification. It's an honest note — they don't lean on a score stream that never fully materialized.

Jane: The baseline taxonomy on this page is one of the most valuable parts. Direct baselines like best-of-N and self-consistency run literally over the shared pool. Local proxies preserve the inference pattern of recent methods but get labeled as proxies. The pool oracle stands apart as an upper bound that can see correctness.

Tom: That taxonomy matters because a lot of recent test-time scaling results depend on private checkpoints or closed evaluator APIs. Anchoring the comparison to locally reproducible methods is what makes the frontier movement credible.

Lu: The metrics list includes measured latency in seconds alongside accuracy, total tokens, model calls, and parameter-weighted tokens. The cost picture has several independent dimensions rather than one convenient proxy.

Meng: Answer extraction also gets a rigorous treatment — boxed answers, final-answer statements, normalization of fractions, tuples, and π. Because routing changes which candidates survive to the end, extraction has to be identical across methods or the accuracy comparison breaks.

Lalam: By the end of page four, every methodological choice is on the table. Page five then delivers the results, and the headline numbers genuinely deliver on the abstract's promises.

Page 5 of the paper: Tom: Page five carries the main results table, and the numbers land exactly where the abstract said they would. CoBa-Routed-Strong reaches 85 point 13 percent macro accuracy at roughly 58,000 total tokens and 630,000 parameter-weighted tokens per item.

Jane: The comparison pairs are the ones to focus on. The routed system is statistically indistinguishable from the self-evaluation weighted-voting proxy at 85 point 20 percent, with 49 point 1 percent fewer parameter-weighted tokens. It also lands within 0 point 01 accuracy points of best-of-16 majority voting, with 58 point 9 percent fewer.

Lu: Figure two shows the same result as a frontier. The routed variants occupy the upper-middle region — light is inexpensive, balanced beats best-of-4 at similar cost, and strong reaches the accuracy zone of best-of-16 and self-evaluation while spending far less.

Meng: But the per-dataset table is where the nuance jumps out. eyeME 2024 goes from 65 point 6 percent greedy to 82 point 2 percent routed — a massive allocation gain. eyeME 2025 only reaches 71 point 1 percent against an oracle at 83 point 3 percent.

Jane: That contrast between the two eyeME years is the most instructive thing in the results. On eyeME 2024, extra candidates and routed verification often recover from a weak first sample. On eyeME 2025, the correct answer often isn't in the pool at all, or the verification signals can't surface it.

Tom: The paper splits those into two failure modes — allocation errors, where better routing could pick an existing correct answer, and generation errors, where the next useful unit of compute should create better candidates before scoring deeper. Deeper evaluation on a wrong pool mostly audits bad candidates more carefully.

Lu: Reasoning Gym tells a similar story from the other direction. CoBa reaches 92 point 3 percent against an oracle of 99 point 8 percent. The pool is rich with correct answers, and the policy still can't always identify the right one.

Meng: The deployment read is that the savings spread across the benchmark. Easy examples stop after cheap agreement; hard contest problems consume extra samples and strong-verifier calls. Uniform best-of-N pays the hard-example budget on every single problem.

Lalam: That's the whole routing thesis in one sentence — concentrate the budget where the decision can still change, rather than spending everywhere identically. Page five backs that thesis with hard numbers.

Tom: Then page six goes one layer deeper, showing the actual action mix across datasets and running the significance tests that separate real gains from noise.

Page 6 of the paper: Jane: Page six opens with the behavioral evidence for adaptive allocation. The action mix per dataset is genuinely different — MATH-500 stops early after lightweight judging, while the contest sets trigger more sampling and more strong-verifier calls.

Tom: That's the policy's fingerprint. The system isn't applying a uniform compute cap; it's shifting the composition of compute based on what the cheap evidence says about each problem.

Lu: The routing-strength ablation shows the expected progression. Light gets 78 point 88 percent, balanced gets 82 point 92 percent, strong gets 85 point 13 percent. And the jump from light to balanced is the biggest, which tells you the first routed candidates carry the most value.

Meng: The paired bootstrap tests then do the statistical work. CoBa-Routed-Strong beats greedy by 3 point 74 points with a 95 percent confidence interval from about 2 point 97 to 4 point 54. Against the self-evaluation proxy, the difference is minus 0 point 16 points and the interval includes zero — statistically indistinguishable.

Jane: And the best-of-16 comparison stays honest. Best-of-16 holds a 0 point 70 point edge, with a confidence interval from minus 1 point 25 to minus 0 point 16, but it pays 2 point 43 times the parameter-weighted cost. That's a real advantage, and a very expensive one.

Tom: There's also a result most papers would quietly drop — the learned MLP controller degenerated to a near-greedy policy in the leave-one-dataset-out setting. They present it as a negative result and say learning a robust controller from offline trajectories remains open.

Lalam: Publishing that failure is a genuine scientific strength. It keeps the claims honest: the routing gains come from the transparent hand-designed policy, not from a trained black box that might be overfitting the benchmark.

Lu: The cost table at the end of the page frames the high-accuracy regime cleanly. The three high-accuracy methods all sit around 85 percent, but their relative parameter-weighted costs are 1 point 0, 1 point 96, and 2 point 43 times.

Meng: So the savings decompose into two mechanisms. The policy avoids repeating expensive actions when the decision is already settled, and it concentrates strong verification on the few candidates that could actually flip the final answer.

Jane: Those two mechanisms attack different kinds of waste. Best-of-N over-generates, self-evaluation over-verifies, and this method does a limited amount of each, guided by cheap evidence.

Tom: Page seven then pulls the discussion together — where the savings come from, what the residual gap means, and what the field should report in future work.

Page 7 of the paper: Tom: Page seven sharpens the cost-savings story into something almost surgical. Best-of-16 spends on diversity — sixteen full generations even when answers already agree. Self-evaluation spends on evaluation — judging nearly every candidate regardless of whether it matters.

Jane: The method sits between those extremes. It buys a modest amount of diversity first, then uses cheap evidence to decide whether the next unit of compute should be another sample or a stronger verifier call. That's the allocation view made operational.

Lu: The residual gap gets a precise diagnosis, too. On eyeME 2025 and some symbolic tasks, the oracle finds correct candidates that routing misses. Those cases call for sharper uncertainty or process signals, because extra always-on verification just rescores the same ambiguous pool.

Meng: The paper then proposes a reporting norm for the whole field — action mix, cost-accuracy frontier, and oracle gap together. That makes routing claims falsifiable, because you have to show both where compute was removed and where it was concentrated.

Lalam: That norm would change how the community reads papers. Accuracy alone can hide whether a method bought better candidates, spent more verifier effort, or simply stopped earlier. The allocation trace exposes the mechanism.

Jane: The future directions are concrete as well. Natural science and code generation bring longer horizons, tool use, and public checks like unit tests. Latency could become a routed objective rather than just an audited statistic.

Tom: And the learned controller gets another chance as process signals get denser. The paper doesn't close that door, but it's clear the transparent policy wins on today's evidence.

Lu: The two failure modes from the results section come back as design guidance. Correct answer in the pool but unselected — improve uncertainty estimation or verification. No correct answer in the pool — expand generation. The oracle gap becomes a roadmap.

Meng: The conclusion ties it to what a practical system should expose: the answer, the computation path, and the marginal action that changed the decision. That connects model capability, verifier evidence, latency, and user value into one trace.

Lalam: For local deployments, where moderate sampling is feasible and deep evaluation of every candidate is not, that trace is the difference between an expensive black box and an auditable reasoning system. That's the operational payoff of the whole paper.

Tom: And that is exactly the place to close the discussion. The concluding section lands on the design implications for future test-time systems.

Conclusion: Tom: So wrapping it up — the paper reframes test-time scaling as a compute-allocation problem. The question isn't just how many samples or how long a chain of thought; it's which action deserves the next unit of compute across generation, verification, and stopping.

Jane: The evidence holds across three local generators and five reasoning benchmarks. The strongest routed variant matches the accuracy of best-of-16 majority voting and the self-evaluation weighted proxy while cutting parameter-weighted compute by 49 to 59 percent. And it does that on shared candidate pools, so the gain is genuinely allocation.

Lu: The oracle gap keeps things honest. At 91 point 36 percent pooled oracle versus 85 point 13 percent for the routed system, real headroom remains, and the paper maps that headroom into concrete next steps — sharper uncertainty, denser process signals, better candidate generation.

Meng: The allocation trace is probably the most durable contribution. When a system can say which action changed the final decision, failures become actionable instead of just scores on a leaderboard.

Lalam: The broader message is that generation and verification should be treated as one shared budget. The field gains a vocabulary — action mix, cost-accuracy frontier, oracle gap — that should make the next round of test-time scaling papers comparable in a way they haven't been.

Jane: I also want to carry the negative result on the learned controller forward. Publishing it keeps the story honest and marks a clear open problem for anyone who wants to learn a routing policy from offline trajectories.

Tom: Right, and the hand-designed policy being fully transparent means its thresholds can be audited and replayed, which is more than many approaches offer. It's a solid, reproducible contribution.

Lu: And the practical message for anyone serving reasoning models locally is simple. Don't spend the hard budget on every example; score cheaply first, then escalate only where it can change the answer.

Meng: That's a strong closing point. This paper gave us a good discussion, and we'll leave the computation path behind with it.

Jane: Looking forward to the next one. Thanks for the conversation, everyone.

Yan Zhou, Yue Ouyang, Kaiyang Zheng, Suncheng Xiang

Changsha University of Science and Technology · Shanghai Jiao Tong University

cs.AI

Submitted: 2026-08-10

Updated: 2026-08-11

Comments: 11 pages, 7 figures; includes supplementary material. Preprint

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 79/100

The gist: The paper addresses test-time scaling in large language models, which is "often implemented by spending more compute along one axis: sampling more solutions, extending a chain of thought, or applying

Key concepts

Parameter-weighted tokens: A cost metric that multiplies each token count by the model's size in billions, so a token from a 14B model costs more than one from an 8B model. This captures the true computational expense of different models, unlike raw token counts.
Compute-balanced routing: A policy that decides, at each step, whether to generate a new candidate, verify a candidate with a cheap or strong judge, or stop. It allocates compute based on cheap evidence, sending only uncertain or high-value candidates to expensive verification.
Replay protocol: An experimental setup where all methods see the same pre-generated candidate pools (16 per problem). Routing can only select which candidates to inspect or verify, not create new ones, ensuring fair comparisons and isolating the effect of allocation policy.

Terminology

Accuracy — 64× in this paper · explained in 1 episode
Verifier — 63× in this paper · explained in 2 episodes
Verification — 61× in this paper · explained in 2 episodes
Test-time Scaling — 21× in this paper · explained in 2 episodes
Benchmark — 13× in this paper · explained in 2 episodes
Consistency — 9× in this paper · explained in 3 episodes
Self-consistency — 9× in this paper · explained in 2 episodes
Trace — 7× in this paper · explained in 2 episodes
Ablation — 5× in this paper · explained in 1 episode
Chain-of-Thought Prompting — 2× in this paper · explained in 2 episodes
Core — 2× in this paper · explained in 2 episodes
Failure Modes — 2× in this paper · explained in 3 episodes
Reinforcement Learning — 2× in this paper · explained in 4 episodes
Action Space — 1× in this paper · explained in 1 episode
Adaptive Compute Allocation — 1× in this paper · explained in 1 episode
Adaptive Sampling — 1× in this paper · explained in 1 episode
Aggregation — 1× in this paper · explained in 1 episode
Distribution Shift — 1× in this paper · explained in 6 episodes
Iterative Refinement — 1× in this paper · explained in 3 episodes
Reasoning Traces — 1× in this paper · explained in 3 episodes
Robustness — 1× in this paper · explained in 5 episodes
Steering — 1× in this paper · explained in 2 episodes

Summary

The paper addresses test-time scaling in large language models, which is often implemented by spending more compute along one axis: sampling more solutions, extending a chain of thought, or applying a stronger evaluator. The authors note that under a fixed inference budget, these choices compete. Spending the next unit of compute on one operation prevents spending it elsewhere. The 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. The central hypothesis is that "accuracy gains and cost savings should be evaluated together. A system that always samples many candidates or always invokes a strong evaluator may be accurate, yet it spends the same expensive actions on settled and ambiguous examples."

CoBa (Compute-Balanced test-time scaling) is 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.

Algorithm structure (Algorithm 1): The policy first spends a small, fixed warm-up budget to obtain candidate diversity (warm-up count k=2). It then applies lightweight verification to every candidate and uses the resulting answer agreement and judge scores to decide whether to stop, sample more candidates, or route selected candidates to a strong verifier. Ground-truth answers are never used in the policy.

Fixed routing specification (Table 1):

Warm-up k = 2 candidates
Nmax: 2 for CoBa-Routed-Light, 4 for CoBa-Routed, 8 for CoBa-Routed-Strong
Strong routes K: 0/2/4 respectively
Stable answer stop criterion: answer share ≥ 0.6 and cheap judge score s1 ≥ 0.7
Cheap verifier: Qwen3-8B (yes/no judge applied to all candidates)
Strong verifier: Qwen3-14B (deep outcome verifier, routed to top-K candidates)
Fusion weights: 0.20 (answer frequency f) / 0.30 (cheap judge s1) / 0.15 (process verifier s2) / 0.45 (strong verifier s3)
Missing scores are renormalized so unrouted candidates receive neither artificial penalties nor artificial support from absent verifier evidence

The final ranking score is: R(c) = 0.20 f(c) + 0.30 s1(c) + 0.15 s2(c) + 0.45 s3(c), where f(c) is normalized answer frequency, s1(c) is the Qwen3-8B judge score, s2(c) is the optional sparse process-verifier score, and s3(c) is the Qwen3-14B deep-verifier score.

Three routing variants trace a cost-accuracy curve: CoBa-Routed-Light (two-candidate warm-up + lightweight verification only), CoBa-Routed (at most four candidates, two routed to strong verification), and CoBa-Routed-Strong (at most eight candidates, four routed to strong verification).

Two cost metrics are used: total-token cost (sum of input and output tokens across all models) and parameter-weighted token cost, Cptok = Σ Pm(T in m + T out m), where Pm is model parameters in billions, approximat[ing] the fact that a token processed by a 14B model is more expensive than a token processed by an 8B model. The formal allocation objective maximizes expected utility: max E[1 ŷπ(x)=y] − λ Cπ(x)/B, with λ controlling cost sensitivity.

Datasets: MATH-500, AIME 2024, AIME 2025, AMC 2023, and a hard Reasoning Gym subset — 1,043 unique examples and 3,129 example–generator evaluations across 15 dataset–generator pairs.
Models: Qwen3-14B, Phi-4-reasoning, and Qwen3-8B as generators; Qwen3-8B as cheap judge; Qwen3-14B as strong verifier; Phi-4-reasoning provides auxiliary sparse process-verifier scores.
Offline replay protocol: All methods operate over the same shared pool of N=16 candidates per example (temperature 0.6, top-p 0.95, max 16,384 output tokens). Replay methods can choose prefixes, subsets, or routed verification actions from this pool. Candidate correctness is reserved for the explicitly labeled oracle upper bound.
Baselines: greedy single-sample, fixed-long reasoning, s1 budget-matched replay, best-of-N majority voting, self-consistency, k-stable and overthinking-aware early stopping, difficulty-adaptive allocation, uncertainty/bandit allocation proxies, always-on evaluator proxies, self-evaluation weighted voting, and a pool oracle (which selects a correct candidate whenever one appears in the generated pool). Baselines are separated into direct baselines, local proxies (labeled when exact public artifacts are unavailable), and upper bounds.
Statistics: paired bootstrap tests with 2,000 resamples; significance when the 95% CI of the paired accuracy difference excludes zero.

Overall accuracy-cost results (Table 2), macro-averaged over 15 dataset–generator pairs:

CoBa-Routed-Strong achieves 85.13% macro accuracy with 5.80×104 total tokens and 6.30×105 parameter-weighted tokens per item, at 7.91 model calls and 1013.3 seconds latency.
This is statistically comparable to the self-evaluation weighted-voting proxy, which obtains 85.20%, but CoBa-Routed-Strong uses 49.1% fewer parameter-weighted tokens.
It also matches best-of-16 majority voting within 0.01 macro-accuracy points while reducing parameter-weighted tokens by 58.9% (85.12% accuracy for best-of-16 at 1.533×106 parameter-weighted tokens).
The pool oracle obtains 91.36%, serving as an evaluator-side diagnostic upper bound.

Per-dataset results (Table 3), averaged over three generators:

MATH-500: CoBa-Routed-Strong 87.6% vs. greedy 86.4%, best-of-16 88.3%, oracle 90.3%
AIME 2024: CoBa-Routed-Strong 82.2% vs. greedy 65.6%, best-of-16 80.0%, oracle 87.8% (CoBa-Routed-Strong improves from 65.6% greedy accuracy to 82.2%)
AIME 2025: CoBa-Routed-Strong 71.1% vs. greedy 53.3%, best-of-16 72.2%, oracle 83.3% (the large oracle gap points to candidate generation as the dominant remaining source of improvement)
AMC 2023: CoBa-Routed-Strong 92.4%, matching self-eval 92.4%, oracle 95.6%
Reasoning Gym: CoBa-Routed-Strong 92.3% vs. greedy 88.2%, best-of-16 93.5%, oracle 99.8%

The authors note: On AIME 2024, additional candidate diversity and routed verification are often enough to recover from an initially weak sample. On AIME 2025, the oracle gap remains large, separating two failure modes: "allocation errors, where better routing could select an existing correct candidate, and generation errors, where the next useful unit of compute should create better candidates before scoring the current pool more deeply."

Figure 3 shows that routing uses stronger verification and additional sampling unevenly across datasets, producing an action mix that differs from a uniform compute cap. The authors state: "easy or stable examples terminate after agreement and lightweight judging, moderately ambiguous examples receive a few extra candidates, and the most decision-relevant candidates are escalated to strong verification. That action distribution is the behavioral evidence behind the frontier improvement: expensive actions are reallocated away from already-settled cases and toward decisions that can still change."

Paired bootstrap tests support three conclusions:

CoBa-Routed-Strong significantly improves over greedy decoding: the paired accuracy difference is +3.74 points with a 95% confidence interval of [+2.97, +4.54] points (p <.001).
CoBa-Routed-Strong is statistically indistinguishable from the self-evaluation weighted-voting proxy: the observed difference is −0.16 points and the confidence interval includes zero.
Best-of-16 remains slightly more accurate than CoBa-Routed-Strong under the paired test, but the difference is only 0.70 points (95% CI [−1.25, −0.16], p =.004) and comes at 2.43× the parameter-weighted cost.

Routing-strength ablation (Table 4): CoBa-Routed-Light achieves 78.88% at 252.9k P-Tok; CoBa-Routed achieves 82.92% at 392.4k P-Tok; CoBa-Routed-Strong achieves 85.13% at 629.9k P-Tok. Moving from CoBa-Routed-Light to CoBa-Routed adds a small number of strong-verifier calls and yields a large accuracy gain, indicating that the first routed candidates are high value. The pattern shows a diminishing-return pattern... exactly what a compute-allocation view predicts.

Negative result: "The learned MLP controller was also evaluated and degenerated to a near-greedy policy in the final leave-one-dataset-out setting. This negative result is useful: the current evidence supports transparent routed allocation, while learning a robust controller from the available offline trajectories remains open."

The paper identifies where the cost is saved: "First, CoBa avoids repeating expensive actions on settled examples: when sampled answers agree and the lightweight judge is confident, routing stops early before a fixed evaluator stack would be invoked. Second, it concentrates strong verification on the few candidates most likely to change the final decision."

At comparable accuracy (Table 5): CoBa-Routed-Strong costs 1.00× relative parameter-weighted cost, self-evaluation costs 1.96×, and best-of-16 costs 2.43×. The authors summarize: "Best-of-N spends on diversity by generating sixteen full candidates, even when answers already agree. Self-evaluation weighted voting spends on evaluation by judging many candidates, including candidates whose answers can be decided from cheap agreement. CoBa-Routed-Strong sits between these extremes: it first buys modest diversity, then uses cheap evidence to decide which candidates deserve stronger verification."

The paper's conclusions include:

"CoBa asks which action deserves the next unit of compute across generation, verification, and stopping. Across three local generators and five reasoning benchmarks, routed generation–verification allocation matches much more expensive sampling and self-evaluation baselines while using substantially fewer parameter-weighted tokens."
"The remaining oracle gap turns allocation into a productive axis for practical reasoning systems: better candidate creation, sharper uncertainty, and richer process signals can all be expressed as decisions about the next computation."
"The allocation trace also makes failures actionable. When a correct candidate appears in the pool but routing misses it, the next computation should improve uncertainty estimation or verification. When the pool lacks a correct candidate, the next computation should expand generation."
The authors suggest a reporting norm for test-time scaling systems: "Accuracy alone can hide whether a method buys better candidates, spends more verifier effort, or simply stops earlier. Reporting the action mix, the cost–accuracy frontier, and the oracle gap together makes the allocation mechanism falsifiable."

The paper notes the deployment implication that "the savings are distributed across the benchmark. Easier examples often stop after cheap agreement and lightweight judging, whereas harder contest problems consume additional samples and strong-verifier calls. Uniform best-of-N or always-on evaluation pays the hard-example budget on every example; routing concentrates that budget where the decision can still change. Future directions include natural science and code benchmarks, measured latency as a routed objective, and learned controllers as process signals become denser."

Improvements for AI systems

Based on CoBa, here are concrete improvements you can build into AI reasoning systems:

Replace “always sample N solutions” or “always run a strong verifier” with a policy that decides, after each unit of compute, whether to stop, generate more candidates, or route candidates to strong verification.
Use a fixed warm-up of 2 candidate generations, followed by cheap verification on all candidates, and only escalate ambiguous/high-value candidates to a stronger verifier.
Stop when answer agreement is high (e.g., answer share ≥ 0.6) and the cheap judge is confident (score ≥ 0.7).

What the improved system can do:

Under a fixed inference budget, it can match best-of-16 majority voting within 0.01 macro-accuracy points while using 58.9% fewer parameter-weighted tokens. On AIME 2024, it can improve greedy accuracy from 65.6% to 82.2%.

Run a small, cheap judge (e.g., Qwen3-8B) on every candidate to get broad coverage.
Route only the top-K uncertain/valuable candidates to a strong verifier (e.g., Qwen3-14B).
Fuse all evidence with weights that reflect reliability, e.g.:
0.20 answer frequency
0.30 cheap judge score
0.15 process verifier score (when available)
0.45 strong verifier score
Renormalize missing scores so unrouted candidates are not artificially penalized or boosted.
Provide configurable variants: light routing (2 candidates, no strong verifier), routed (4 candidates, 2 strong routes), and routed-strong (8 candidates, 4 strong routes).
Let the deployment choose where to operate based on its latency/cost constraints.
Use an oracle gap analysis: compare current accuracy against a pool-oracle upper bound that selects a correct candidate whenever one exists.
If the oracle gap is large, the bottleneck is candidate generation — allocate the next unit of compute to sampling more/diverse candidates.
If a correct candidate already exists but routing misses it, allocate the next compute to sharper uncertainty estimation or stronger verification.
Track and report: number of cheap judge calls, strong verifier calls, generation steps, early stops, and parameter-weighted token cost.
Report accuracy alone is misleading — always pair it with cost and with the oracle gap.
Before invoking expensive evaluators, check whether sampled answers already agree.
If they agree and the lightweight judge is confident, stop and return the majority/fused answer.
Only spend extra compute when answers disagree or the judge is uncertain.
The paper’s learned MLP controller degenerated to a near-greedy policy in leave-one-dataset-out evaluation.
Prefer transparent, rule-based routing for now; revisit learned controllers only when richer process verifier signals become available.
Optimize: expected accuracy minus a cost penalty: max E[accuracy] − λ · cost / budget.
Use the cost coefficient λ to tune how aggressively the system saves compute on easy items and spends it on hard items.

Overall, the improved AI system built from CoBa can achieve near-best-of-N accuracy at a fraction of the cost, adaptively allocate computation across generation, verification, and stopping, and provide clear diagnostics for where to invest future compute.

Abstract

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.