RoBoN: Routed Online Best-of-n for Test-Time Scaling with Multiple LLMs

AI summary

Overview

Research area: Test-time scaling for large language model (LLM) inference; specifically best-of-n sampling and inference-time model routing/ensembling.

Technical level: Intermediate. The paper assumes familiarity with LLM sampling, reward models, and the standard best-of-n pipeline, but the core idea is described without heavy mathematics.

Scope: The paper proposes and empirically evaluates RoBoN, a training-free sequential routing method that spreads a fixed budget of n generations across four LLMs to beat single-model best-of-n on reasoning benchmarks.

What This Paper Is About

Standard best-of-n (BoN) generates n responses from one model and picks the highest-scoring one with a reward model. But different LLMs have complementary strengths, and single-model BoN leaves that diversity unused. The authors ask whether they can route a fixed budget of n generations across a portfolio of models, one generation at a time, to get better test-time scaling without any additional training and without spending more compute than standard BoN.

Key Contributions

1. RoBoN (Routed Online Best-of-n): a sequential, multi-LLM alternative to single-model BoN. Given a suite of M models and a per-prompt budget n, it routes generations one-by-one across models rather than generating in parallel from one model.
2. A training-free online scoring rule: at each step each model's "head" candidate is scored with a combination of a plug-in reward model and an agreement signal over the extracted, normalized answers. The best candidate is committed, and unchosen heads are recycled to the next step.
3. Compute parity: exactly n responses are generated in total, matching the FLOPs of single-model BoN (memory grows linearly with the number of models M).
4. Empirical evaluation on five reasoning benchmarks with four models, comparing against single-model BoN for each constituent model, an average across models, and a uniform multi-model portfolio baseline.

Main Findings

• RoBoN wins for larger n, on average: In Table 1 (average accuracy across datasets), RoBoN reaches 0.548 ± 0.008 at n=16, 0.576 ± 0.010 at n=64, and 0.581 ± 0.012 at n=256. Individual single-model BoN baselines sit at roughly 0.548 at n=16, 0.560 at n=64, and 0.562–0.564 at n=256.
• Gains reported as up to 3.4% absolute in the abstract (the introduction states gains up to 5% absolute accuracy); the paper says RoBoN lags at n=1 and n=4, is on par at n=16, and is significantly better at n=64 and n=256.
• Beats the uniform portfolio baseline: the "equal" baseline (n/M = n/4 samples per model) scores 0.532 ± 0.012 at n=16, 0.552 ± 0.009 at n=64, and 0.560 ± 0.012 at n=256, below RoBoN at every reported n.
• Per-dataset pattern: RoBoN is best-marked on MATH500 (0.845 ± 0.007 at n=64; 0.838 ± 0.012 at n=256), OlympiadBench (0.409 ± 0.012 at n=64; 0.411 ± 0.012 at n=256), MinervaMath (0.331 ± 0.011 at n=64; 0.323 ± 0.012 at n=256), GSM8K (0.961 ± 0.005, 0.966 ± 0.003, 0.968 ± 0.001 at n=16, 64, 256), and MMLU (0.256 ± 0.011, 0.331 ± 0.019, 0.364 ± 0.021 at n=16, 64, 256).
• Reward hacking hurts the baselines more: baseline performance degrades on MATH500 and MinervaMath as n grows, attributed to reward hacking; RoBoN also suffers this effect but "significantly diminished."
• RoBoN reaches accuracies no single model reaches at any n: the authors state that in the regime where RoBoN wins, no runtime budget lets single-model BoN catch up, which is why they did not include an explicit runtime comparison.
• Reward normalization is required: rewards are normalized per model by their empirical CDF onto [0,1]; without this, RoBoN degrades to the average of the individual BoN baselines.
• Robustness to α: the ablation over α ∈ {0.0, 0.2, 0.4, 0.6, 0.8, 1.0} averaged over MATH500, OlympiadBench, and MinervaMath shows most values perform similarly, with α = 0.4 having a slight edge and α = 1 (rewards only) significantly worse.
• Routing is uneven: deepseek-coder-6.7b is selected 50–75% of the time for larger n, yet RoBoN still outperforms BoN on that model alone. On GSM8K deepseek-coder-6.7b is selected less often; on MMLU-STEM qwen-coder-7b is never selected; on OlympiadBench qwen-math-7b is never selected.

Methodology in Plain English

The method keeps a running set S of already-selected (response, reward) pairs. At each iteration, every model in the portfolio offers a "head" candidate — a freshly generated response if that model was selected last round, otherwise the previously drawn response, which is reused rather than regenerated. Each candidate is scored by tentatively adding it to S and computing an agreement-weighted soft score: rewards are turned into weights with a temperature-scaled softmax (β = 1e5 in the experiments), and each candidate's contribution mixes its reward with how often its extracted, normalized answer already appears among the candidates in S (α = 0.4, so rewards get 40% of the weight and agreement 60%). The candidate with the highest marginal score is committed to S, and that model's counter advances. The loop runs n − M + 1 times, so the final set S contains n − M + 1 responses even though exactly n generations were drawn (in the last iteration, M − 1 candidates are discarded). A final best-of-n selection over S produces the answer. With M = 1 and α = 1 the method reduces to standard soft BoN; with α = 0 it becomes majority-style voting; with large β and moderate α it approximates hard BoN with an agreement-modified reward.

Experimental setup: four models (Qwen2.5-Math-7B-Instruct, DeepSeek-Coder-6.7B-Instruct, Llama-3.1-8B-Instruct, Qwen2.5-Coder-7B-Instruct), no search over the model suite, reward model Skywork/Skywork-Reward-V2-Llama-3.1-8B, implemented with vLLM on a single H100 GPU, temperature 1.0 and top_p 0.95, evaluated on MATH500, the OE_TO_maths_en_COMP split of OlympiadBench, MinervaMath, GSM8K, and MMLU-STEM, with 1-sigma confidence intervals reported. Code and a dataset of all generated responses, rewards, and normalized rewards are released.

Why This Matters

Impact on research. The paper opens a direction largely unexplored: cross-model BoN. Prior work shows LLMs have complementary strengths and that ensembling can beat any constituent model, but BoN is conventionally run with a single model. RoBoN shows diversification across models can be exploited at inference with no router training, no fine-tuning, and no extra samples, and that it also beats a naive uniform portfolio. It also connects BoN to majority voting through the α knob and documents a mitigation for reward hacking.

Real-world applications (bullets):

• Serving systems that already host several open-weight models and want better answer quality per prompt without training a router.
• Math and STEM tutoring or homework-checking assistants, where answers can be compared exactly and a verifier or reward model is available.
• Cost-constrained deployments that cannot afford a much larger model but can afford a portfolio of comparable-size ones.
• Inference pipelines where a pre-computed response/reward corpus exists and per-model reward normalization can be estimated offline.

Industry relevance. The requirement of compute parity with single-model BoN matters for serving budgets, and the method is stated to be compatible with common acceleration stacks such as vLLM. The main trade-off is runtime: RoBoN generates sequentially and can cost an extra factor of n versus parallel BoN, though the authors argue that in the regime where RoBoN wins, no runtime budget lets BoN match it, so a like-for-like runtime comparison is not possible.

Future Directions

1. Extending beyond verifiable answers. The agreement term currently needs exact string comparison of extracted answers, so RoBoN in its present form only applies where two answers can be immediately checked for identity; the authors suggest replacing it with embedding similarities for open-ended tasks.
2. New domains and suites. Applying RoBoN to coding and verifying its benefits on different suites of models.
3. Theoretical guarantees. The authors note that guarantees on expected accuracy would require further assumptions on the reward model, and that the nature of the RoBoN scoring algorithm makes reliable practical guarantees hard to derive.
4. Semi-parallel variants. Computing part of the responses in parallel, routing the remainder based on already-computed responses, then parallelizing again, as a way to improve runtime complexity.

Related open questions the paper raises include explaining why routing behavior differs so sharply by dataset (with some models never selected on particular benchmarks).

Target Audience

Researchers and engineers working on LLM inference, test-time scaling, and inference-time routing or ensembling; practitioners who run multi-model serving stacks and want better selection without training a router; and readers interested in reward-model-based selection and reward hacking mitigation on reasoning benchmarks. Readers without exposure to best-of-n, reward models, or the standard sampling notation may need background reading first.

Authors’ abstract

Best-of-$n$ is a widely used test-time scaling approach for LLM inference. Yet despite evidence that LLMs exhibit complementary strengths across tasks, traditionally best-of-$n$ relies on a single model to generate responses. We propose RoBoN (Routed Online Best-of-$n$), a sequential multi-LLM alternative to the prevailing single-model best-of-$n$. Given a suite of models $\{m_i\}_{i=1}^M$, RoBoN sequentially routes generations one-by-one across models, based on scores computed using a reward model and an agreement signal on the predicted responses. This online routing requires no additional training, keeps compute parity, and works with any plug-in reward model. Across reasoning benchmarks (MATH500, OlympiadBench, MinervaMath, GSM8K, MMLU), RoBoN consistently outperforms standard best-of-$n$ applied to each individual model for larger $n$, with gains of up to 3.4\% in absolute accuracy, and also improves over a uniform multi-model portfolio baseline. Our results indicate that diversity across models can be exploited at inference to improve best-of-$n$ performance over any constituent model alone, providing a simple, training-free path to test-time scaling with multiple LLMs.