Vector Policy Optimization: Training for Diversity Improves Test-Time Search

# Training for Diversity Improves Test-Time Search
Source: [https://arxiv.org/html/2605.22817](https://arxiv.org/html/2605.22817)
## Vector Policy Optimization: Training for Diversity Improves Test\-Time Search

Ryan Bahlous\-Boldi1,2Isha Puri1Idan Shenfeld1,2Akarsh Kumar1Mehul Damani1 Sebastian Risi4Omar Khattab1Zhang\-Wei Hong1,2,3Pulkit Agrawal1,2 1MIT2Improbable AI Lab3MIT\-IBM Computing Research Lab4Sakana AI

###### Abstract

Language models must now generalize out of the box to novel environments and work inside inference\-scaling search procedures, such as AlphaEvolve, that select rollouts with a variety of task\-specific reward functions\. Unfortunately, the standard paradigm of LLM post\-training optimizes a pre\-specified scalar reward, often leading current LLMs to produce low\-entropy response distributions and thus to struggle at displaying the diversity that inference\-time search will require\. We proposeVector Policy Optimization \(VPO\), an RL algorithm that explicitly trains policies to anticipate diverse downstream reward functions and to produce diverse solutions\. VPO exploits that rewards are often vector\-valued in practice, like per\-test\-case correctness in code generation or, say, multiple different user personas or reward models\. VPO is essentially a drop\-in replacement for the GRPO advantage estimator, but it trains the LLM to output asetof solutions where individual solutions specialize to different trade\-offs in the vector reward space\. Across four tasks, VPO matches or beats the strongest scalar RL baselines on test\-time search \(e\.g\. pass@kkand best@kk\), with the gap widening as the search budget grows\. For evolutionary search, VPO models unlock problems that GRPO models cannot solve at all\. As test\-time search becomes more standardized, optimizing for diversity may need to become the default post\-training objective\.

![Refer to caption](https://arxiv.org/html/2605.22817v1/x1.png)Figure 1:Vector Policy Optimization \(VPO\)\.When maximizing a scalar, GRPO sends all solutions to the same, potentially sub\-optimal, solution\. VPO simultaneously optimizes across different reward weightings, increasing the chance of finding a superior target solution\. As a result, on LiveCodeBench, for example, VPO results in better test\-time search performance, whether using pass@kkor even complex evolutionary test\-time search like AlphaEvolve\.## 1Introduction

Exploration is a core principle in reinforcement learning \(RL\)\. For learning to keep progressing, an agent must maintain diverse behavior, trying different strategies rather than committing to one prematurely\. Balancing exploration and exploitation\[Ladoszet al\.,[2022](https://arxiv.org/html/2605.22817#bib.bib82)\]is well studied in both classical RL\[Sutton and Barto,[1998](https://arxiv.org/html/2605.22817#bib.bib72), Bellemareet al\.,[2016](https://arxiv.org/html/2605.22817#bib.bib77), Pathaket al\.,[2017](https://arxiv.org/html/2605.22817#bib.bib107)\]and in the context of modern foundation models\[Chenet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib27), Setluret al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib81), Quet al\.,[2026](https://arxiv.org/html/2605.22817#bib.bib78), Honget al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib108)\]\. This trade\-off remains a largely unsolved problem particularly for foundation models\.

In many AI systems, the network is only one component of a larger pipeline\. Especially for hard problems, language models are typically wrapped in some form of search, ranging from simple rejection sampling with a verifier\[Cobbeet al\.,[2021](https://arxiv.org/html/2605.22817#bib.bib11), Brownet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib83)\]to complex evolutionary methods like AlphaEvolve\[Novikovet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib75), Langeet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib110)\]\. In these settings, test\-time search handles exploitation, hinting that training should focus on providing the search with arich and diverse pool of solutionsto select from\. However, existing RL post\-training methods are poorly suited for this kind of diversity preservation\. Policy gradient methods like GRPO\[Shaoet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib12)\]drive the policy toward a narrow set of high\-probability responses\[Wu and Choi,[2025](https://arxiv.org/html/2605.22817#bib.bib20), Yueet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib40)\]\. After training, the diversity required for effective test\-time search disappears, as additional samples become near\-duplicates\[GX\-Chenet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib7), Kirket al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib57), Karouzoset al\.,[2026](https://arxiv.org/html/2605.22817#bib.bib16)\]\.

In this work, we propose a shift in perspective\. Rather than asking a single training algorithm to handle both exploration and exploitation, we separate the two responsibilities entirely by assuming a future test\-time exploitation stage\.In this setting, the role of RL post\-training should not be to converge on a single best response, but to maximize the diversity of a set of competent solutions\.Later, during test\-time, the search method will select among them\.

To train a policy that produces diverse yet competent solutions, we exploit the fact that, in many realistic tasks, rewards can be naturally decomposed into a vector of components: per\-test\-case correctness for code generation, per\-criterion ratings for RLHF, or per\-sub\-question success in multi\-hop reasoning\. This decomposition provides a natural axis for diversity\. Rather than collapsing these components into a single scalar and optimizing toward one peak, we can encourage the model to produce solutions that excel along different reward dimensions, covering the Pareto frontier rather than converging to a single point on it\[Roijerset al\.,[2013](https://arxiv.org/html/2605.22817#bib.bib98)\]\. We term this optimization schemeVector Policy Optimization \(VPO\)\.

Concretely, VPO combines multi\-answer generation\[Puriet al\.,[2026](https://arxiv.org/html/2605.22817#bib.bib4)\]with stochastic reward scalarizations, training the model to produce sets of candidates that span the Pareto frontier rather than collapsing onto a single point\. Together, these mechanisms maintain a richer candidate distribution so that test\-time search can extract increasingly better solutions as the sample budget grows\.

We evaluate VPO across four diverse settings spanning multi\-hop question answering, logic reasoning, navigation, tool use and coding\. Empirically, VPO matches or beats the strongest scalar baselines on test\-time best@kkacross our four benchmarks, with the gap widening as the candidate budget grows\. The advantage holds at scale: on LiveCodeBench, a VPO\-trained Qwen2\.5\-Coder\-7B\-Instruct improves both pass@kkand best@kkover a matched\-compute GRPO checkpoint, and inside the OpenEvolve search loop unlocks problems that GRPO cannot solve at any candidate budget \(Fig\.[1](https://arxiv.org/html/2605.22817#S0.F1)\)\. Our main contributions are:

- •We argue that in AI systems where test\-time search is available, RL post\-training should focus exclusively on producing diverse, competent solutions, leaving exploitation to search\.
- •We show that the vector\-valued structure of rewards in many practical settings provides a natural mechanism for achieving this diversity, by training the model to cover the Pareto frontier of the different objectives\.
- •We propose Vector Policy Optimization \(VPO\), a concrete instantiation of this idea that combines randomized reward scalarizations with the in\-context capabilities of language models to generate diverse candidate sets within a single rollout\.

## 2What kind of diversity are we after?

#### Motivation

A downstream search procedure only benefits from diversity if the candidates differ along specific axes the search requires\. Surface\-level variation, semantic diversity, or noisy sampling are not enough\. Search needs a pool of candidates that realizes different high\-quality trade\-offs between the objectives underlying the task\. This becomes important once language models are deployed inside search\-augmented systems\. At inference time, the model is no longer evaluated one response at a time\. Instead, the system generates many candidate solutions and selects among them\. In this regime, committing the entire policy to a single trade\-off is unnecessarily restrictive\. The goal is no longer to produce one response that is optimal under a single fixed objective, but to produce a*set*of responses that spans multiple plausible trade\-offs, so downstream search can choose among them\.

We call this property*reward diversity*\. A reward\-diverse candidate pool contains solutions that are each optimal under different weightings of the underlying reward components\. Intuitively, the policy remains deliberately non\-committal: instead of collapsing onto a single mode, it preserves multiple strategies that perform well under different preferences\.

#### Setting\.

Letxxdenote a prompt andyya response sampled from policyπθ\(⋅∣x\)\\pi\_\{\\theta\}\(\\cdot\\mid x\)\. In many practical tasks, the reward signal decomposes naturally intoddcomponents,r​\(x,y\)=\[r1​\(x,y\),…,rd​\(x,y\)\]∈ℝdr\(x,y\)=\[r\_\{1\}\(x,y\),\\dots,r\_\{d\}\(x,y\)\]\\in\\mathbb\{R\}^\{d\}, where eachrir\_\{i\}captures a distinct aspect of response quality\. For example,rir\_\{i\}may be per\-test\-case correctness in code generation\[Chenet al\.,[2021](https://arxiv.org/html/2605.22817#bib.bib86)\], per\-criterion preference scores in RLHF\[Wanget al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib100)\], per\-hop correctness in multi\-hop reasoning\[Trivediet al\.,[2022](https://arxiv.org/html/2605.22817#bib.bib9)\], or per\-tool\-call structural and content scores in agentic tasks\[Qianet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib73)\]\. Any weightingw∈Δd−1w\\in\\Delta^\{d\-1\}over the simplex induces a scalar objectivew⊤​r​\(x,y\)w^\{\\top\}r\(x,y\); standard post\-training fixes a singlew∗w^\{\*\}and trains the policy to maximize𝔼y∼πθ\(⋅∣x\)​\[w∗⊤​r​\(x,y\)\]\\mathbb\{E\}\_\{y\\sim\\pi\_\{\\theta\}\(\\cdot\\mid x\)\}\\bigl\[w^\{\*\\top\}r\(x,y\)\\bigr\]\.

Under the standard single\-response framing, this is sensible: if the policy emits only one answer, and evaluation uses a known weightingw∗w^\{\*\}, then directly optimizingw∗w^\{\*\}is the correct objective\. The situation changes once inference\-time search is introduced\. Search benefits precisely from candidates that realize different trade\-offs\. A policy trained only underw∗w^\{\*\}has no incentive to preserve such alternatives, and policy\-gradient training instead concentrates probability mass onto whichever strategy currently maximizes the scalarized reward\. Additional samples then become increasingly redundant\.

Crucially, preserving these alternatives is useful even when the deployment objectivew∗w^\{\*\}is known in advance\. The reason is that search operates over*sets*of candidates rather than individual responses\. A candidate pool that spans multiple reward trade\-offs gives the search procedure more opportunities to discover high\-performing solutions underw∗w^\{\*\}itself\.

Under scalar training, optimization commits aggressively toward whichever responses currently score highest underw∗w^\{\*\}\. Alternative strategies that sacrifice one component in exchange for another are suppressed early, even if they would eventually lead to stronger solutions under the same final objective\. As training progresses, the candidate distribution collapses, and additional samples become increasingly redundant\. Reward diversity counteracts this collapse by preserving solutions that are optimal under different regions of the reward simplex\. Many of these solutions may appear locally suboptimal underw∗w^\{\*\}, yet still contain partial reasoning patterns, decompositions, or strategies that ultimately yield higher\-scoring outcomes underw∗w^\{\*\}itself\. In this sense, reward diversity functions as a structured form of exploration: instead of committing prematurely to a single trade\-off, the policy maintains a population of competent alternatives long enough for search to exploit them\.

This perspective connects naturally to work in multi\-objective RL\[Roijerset al\.,[2013](https://arxiv.org/html/2605.22817#bib.bib98), Hayeset al\.,[2022](https://arxiv.org/html/2605.22817#bib.bib106)\]and to lexicase selection in evolutionary computation\[Spector,[2012](https://arxiv.org/html/2605.22817#bib.bib104), Spectoret al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib101), La Cavaet al\.,[2019](https://arxiv.org/html/2605.22817#bib.bib102), Niet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib105)\]\. Both preserve solutions that are optimal under different subsets or weightings of objectives rather than collapsing all criteria into a single aggregate score\. Importantly, however, our goal is different from classical multi\-objective optimization\. We do not seek a policy conditioned on user\-specified preferences, nor do we assume the deployment objective is unknown\. Our goal remains performance under a fixed weightingw∗w^\{\*\}\. The key difference is that in a search\-augmented regime, the best way to optimizew∗w^\{\*\}may be to train a policy that maintains reward\-diverse candidate sets rather than immediately collapsing onto a single optimum\.

## 3Method: Vector Policy Optimization

In Section[2](https://arxiv.org/html/2605.22817#S2), we argued that the right RL target is reward\-diverse sets, or collections of candidates that are each optimal under some weighting of the reward components\. This section describes our proposed algorithm,Vector Policy Optimization \(VPO\), which trains a policy to produce such sets\. VPO has two key components\. First, we train a model to generate multiple candidate completions per prompt within a single autoregressive rollout\. Second, we replace a fixed reward weighting with a distribution over weights, so the model is incentivized to span its candidates across different trade\-offs between the sub\-objectives\.

![Refer to caption](https://arxiv.org/html/2605.22817v1/x2.png)Figure 2:Outline of Vector Policy Optimization\. Given a promptxx, a modelπθ\\pi\_\{\\theta\}outputsmmanswers in a single autoregressive chain\. Each answeryiy\_\{i\}is evaluated on multiple objectives and receives a score vector\[r1,r2,…,rn\]\\left\[r\_\{1\},r\_\{2\},\\dots,r\_\{n\}\\right\]\. We repeatedly sample weighting vectorswi∼Dir​\(𝟏\)w\_\{i\}\\sim\\mathrm\{Dir\}\(\\mathbf\{1\}\), and evaluate the mean best\-of\-mmunder each weightingwwin the set of answers\. This set level reward is treated as the reward for the entire completionπθ​\(x\)\\pi\_\{\\theta\}\(x\)\.Together, these components define a set\-level objective that rewards the model for producing diverse, high\-quality solutions\. We describe each component in detail below\.

### 3\.1Multi\-Answer Chains as In\-Context Exploration

FollowingPuriet al\.\[[2026](https://arxiv.org/html/2605.22817#bib.bib4)\], we train a language model to produce a set ofmmcandidate completionsS=\{y1,…,ym\}S=\\\{y\_\{1\},\\dots,y\_\{m\}\\\}within a single rollout\. The completions are emitted sequentially, separated by a delimiter token, so when generatingyiy\_\{i\}, the prefix already containsy1,…,yi−1y\_\{1\},\\dots,y\_\{i\-1\}\.

This fundamentally changes the nature of exploration\. Under standard independent sampling, diversity arises only from stochastic decoding applied to a fixed conditional distribution, producing small variations around whichever mode the policy has concentrated on\. In multi\-answer rollouts, each new candidate can attend to the ones already emitted, giving the model the capacity to recognize which regions of the solution space are covered and steer subsequent candidates towards different ones\. Diversity becomes an explicit, in\-context mechanism rather than a byproduct of sampling noise\.

Importantly, this mechanism provides the*capacity*for diversity, but not a strong*incentive*111In practice,Puriet al\.\[[2026](https://arxiv.org/html/2605.22817#bib.bib4)\]de\-duplicate their responses before reward calculation, which adds an incentive against direct duplicates, but the underlying objective still doesn’t reward genuine specialization\. Without an appropriate training signal, the model will still collapse to producing near\-identical answers\. We confirm this empirically in Section[5](https://arxiv.org/html/2605.22817#S5): Multi\-RLVR, which combines multi\-answer rollouts with a fixed scalar reward, produced sets whose reward\-diversity collapses early in training\. The objective defined in the next section supplies this missing incentive by rewarding sets whose elements specialize to different reward trade\-offs\.

### 3\.2Set\-Level Optimization via Stochastic Scalarization

To train a policy to output diverse sets, we replace the fixed scalarization prevalent in RL post training with a distribution over scalarizations\. For each rollout, we sample weightsw∼Dir​\(α\)w\\sim\\mathrm\{Dir\}\(\\alpha\), whereα∈ℝ\>0d\\alpha\\in\\mathbb\{R\}^\{d\}\_\{\>0\}defines a distribution over the simplexΔd−1\\Delta^\{d\-1\}\. We useα=1\\alpha=1throughout, which results in uniform distribution over the simplex \(i\.e\. the set ofdd\-dimensional vectors that sum to 1\)\. We evaluate a setS=\{y1,…,ym\}S=\\\{y\_\{1\},\\dots,y\_\{m\}\\\}under each sampled scalarization by selecting the best\-performing element:

R​\(S\)=𝔼w∼Dir​\(α\)​\[maxy∈S⁡w⊤​r​\(x,y\)\]R\(S\)=\\mathbb\{E\}\_\{w\\sim\\mathrm\{Dir\}\(\\alpha\)\}\\left\[\\max\_\{y\\in S\}w^\{\\top\}r\(x,y\)\\right\]\(1\)This objective directly rewards coverage of the reward space: different elements inSSare optimal under different samples ofww\. A set that collapses to identical responses performs well under a narrow region of the simplex, while a set that spans multiple trade\-offs performs well across many scalarizations\. This objective can be seen as directly optimizing expected best\-of\-NNover sampledww\.

The two components of VPO are complementary: multi\-answer generation alone does not incentivize diversity, while varying scalarizations for a single output can create instability\. Together, they form a stable set\-level objective that directly rewards diversity\. Intuitively, VPO turns policy optimization into a coverage problem over the Pareto front\.

#### Reward estimation

As it only specifies a reward calculation, VPO can be combined with any policy\-gradient method\. In our experiments, we use GRPO\[Shaoet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib12)\]\. For each promptxx, we sampleGGrollouts, each producing a setS\(g\)=\{y1\(g\),…,ym\(g\)\}S^\{\(g\)\}=\\\{y\_\{1\}^\{\(g\)\},\\dots,y\_\{m\}^\{\(g\)\}\\\}ofmmcompletions, along withKKscalarization weightsw\(1\),…,w\(K\)∼iidDir​\(𝟏\)w^\{\(1\)\},\\dots,w^\{\(K\)\}\\stackrel\{\{\\scriptstyle\\mathrm\{iid\}\}\}\{\{\\sim\}\}\\mathrm\{Dir\}\(\\mathbf\{1\}\)used in common across the group\. The per\-rollout Monte\-Carlo reward is

R^​\(S\(g\)\)=1K​∑k=1Kmaxs∈S\(g\)⁡w\(k\)⊤​r​\(x,s\),\\hat\{R\}\(S^\{\(g\)\}\)\\;=\\;\\frac\{1\}\{K\}\\sum\_\{k=1\}^\{K\}\\max\_\{s\\in S^\{\(g\)\}\}w^\{\(k\)\\top\}r\(x,s\),which estimatesR​\(S\)R\(S\)from the previous section\. The GRPO advantage is then calculated and applied uniformly to every token in the rolloutgg\. TheKKscalarization weights are shared across theGGrollouts in the group, so allGGsets are evaluated under the same draws ofwwand are therefore comparable\.

## 4Experimental Setup

### 4\.1Evaluations Tasks

We evaluate on four domains chosen to span distinct shapes of multi\-objective structure: \(i\) binary vs\. continuous reward components, and \(ii\) hand\-crafted vs\. metric\-based reward shapes\. In all our experiments, we usedm=3m\{=\}3candidates per multi\-answer chain across all domains\. Full reward and prompt details are in App\.[A](https://arxiv.org/html/2605.22817#A1)\.

#### Maze\.

A synthetic9×99\{\\times\}9navigation task in which the model emits, in text, a sequence of moves from a start cornerSSto a goal cornerEE, collecting gold and diamond items and avoiding lava along the way\. We construct the mazes so that item types are forced to trade off against each other and against reaching the exit: the geometry guarantees that no single route can satisfy every reward component\. The rewardr∈ℝ4r\\in\\mathbb\{R\}^\{4\}has one binary completion component and three clipped item/safety terms \(gold, diamond, lava\-avoidance\); the GRPO scalar is the uniform mean\. The maze is our controlled testbed: unlike the other three domains, the trade\-off is engineered rather than naturally occurring, which lets us isolate the counter\-intuitive question of whether training VPO and evaluating under the*same*uniform mean GRPO was directly optimized for still beats GRPO\. We train Qwen3\-4B and evaluate on 100 held\-out mazes\.

#### MuSiQue\.

A 2–4 hop reading\-comprehension benchmark\[Trivediet al\.,[2022](https://arxiv.org/html/2605.22817#bib.bib9)\]in which the model selects supporting paragraphs from 20 candidates and emits a final answer\. The rewardr∈ℝ5r\\in\\mathbb\{R\}^\{5\}has four binary citation indicators \(one per gold hop\) plus a continuous answer\-F1 term; the GRPO scalarization weights the answer3×3\\timesto reflect its priority\. We train Qwen3\-1\.7B and evaluate on a 300\-question hop\-stratified split\.

#### EUREQA\.

A 5\-hop chain\-reasoning benchmark\[Liet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib74)\]where the model back\-chains through five relations to identify five masked entities\. The rewardr∈\{0,1\}5r\\in\\\{0,1\\\}^\{5\}is binary per\-entity and the GRPO scalar is a uniform mean\. Unlike MuSiQue’s loosely coupled hops, the chain is causally ordered, so the per\-hop training signal is informative about which step failed\. We train Qwen3\-8B and evaluate on a held\-out hard split\. Due to the limited size of the eval dataset, we averaged over 4 evaluation seeds

#### ToolRL\.

A function\-calling benchmark\[Qianet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib73)\]of 3,920 train and 80 test prompts\. The rewardr∈ℝ4r\\in\\mathbb\{R\}^\{4\}has one binary structural\-format component and three continuous F1 dimensions \(tool\-name, arg\-key, arg\-value\), graded from trivially solvable to schema\-precise; the GRPO scalar is a uniform mean\. We train Qwen3\-1\.7B and evaluate on the 80\-prompt test split\. Due to the limited size of the eval dataset, we averaged over 4 evaluation seeds\.

We build on veRLShenget al\.\[[2024](https://arxiv.org/html/2605.22817#bib.bib79)\]with standard outcome\-reward GRPO\[Shaoet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib12)\]\. The full training details are documented in App\.[B](https://arxiv.org/html/2605.22817#A2)\.

### 4\.2Baselines

Our baselines are designed to isolate which ingredient of VPO is responsible for improved test\-time search\. VPO combines two mechanisms: multi\-answer generation within a single autoregressive rollout, and stochastic scalarization over a vector\-valued reward\. We compare against methods that test whether either ingredient, or existing search\-aware RL objectives, are sufficient on their own\.

- •GRPO\[Shaoet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib12)\]\(single\-answer, scalar reward\)\. This is the standard RL post\-training baseline\. Rewards are collapsed into a fixed scalar objective, and the model emits one completion per prompt\. This tests whether ordinary scalar RL already produces candidate pools that are useful for test\-time search\.
- •Multi\-RLVR\[Puriet al\.,[2026](https://arxiv.org/html/2605.22817#bib.bib4)\]\(multi\-answer, scalar reward\)\. This baseline trains the model to emit multiple answers in one rollout, but evaluates the set using the same fixed scalar reward\. It tests whether multi\-answer generation alone is sufficient, or whether a diversity\-preserving reward signal is also needed\.
- •Random\-Weighting GRPO\(single\-answer, stochastic scalarization\)\. Here the model still emits one answer per rollout, but the scalarization weights are resampled during training,w∼Dir​\(α\)w\\sim\\mathrm\{Dir\}\(\\alpha\)\. This tests whether randomizing the reward objective alone is enough without set\-level optimization\.
- •Max\-at\-kkTraining\[Bagirovet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib71)\]\. This baseline directly optimizes an inference\-aware best@kk/max@kkobjective\. It tests whether explicitly training for best\-of\-kkperformance is sufficient without requiring reward\-diverse candidate sets\.
- •MaxRL\. MaxRL\[Tajwaret al\.,[2026](https://arxiv.org/html/2605.22817#bib.bib111)\]is another search\-aware RL objective that uses additional sampling compute during training to better approximate maximum\-likelihood\-style learning from successful rollouts\. It tests whether stronger scalar search\-aware training objectives can recover the gains of VPO\.
- •Goal\-Conditioned GRPO\. This baseline conditions the policy on a target scalarizationwwand trains it to maximizew⊤​r​\(x,y\)w^\{\\top\}r\(x,y\)\. It tests the natural multi\-objective RL alternative: whether diversity is better obtained by asking for different trade\-offs explicitly, rather than by producing a reward\-diverse set within one rollout\.

### 4\.3Evaluation Metrics

#### Best@kk\.

Our central metric is the maximum scalarized reward over a pool ofkkcandidates,

best​@​k​\(x\)=maxs∈Sk​\(x\)⁡w⋆⊤​r​\(x,s\),\\mathrm\{best\}@k\(x\)\\;=\\;\\max\_\{s\\in S\_\{k\}\(x\)\}\\,w^\{\\star\\top\}\\,r\(x,s\),wherew⋆w^\{\\star\}is the per\-domain GRPO training scalar \(Table[7](https://arxiv.org/html/2605.22817#A2.T7)\) andSk​\(x\)S\_\{k\}\(x\)is a pool ofkkcompletions sampled from the trained policy on promptxx\. Multi\-answer methods draw⌈k/m⌉\\lceil k/m\\rceilindependent multi\-answer chains, each yieldingmmcandidates, and concatenate them in draw order;SkS\_\{k\}is the firstkkentries of this list, soSkS\_\{k\}fork≤mk\\leq mcomes from a single chain\. Single\-answer methods drawkki\.i\.d\. completions\.

#### Reward\-space diversity\.

Alongside best@kk, we report the average pairwiseL1L\_\{1\}distance between the*reward vectors*of the completions in the pool, which measures spread in the reward spaceℝd\\mathbb\{R\}^\{d\}: high diversity means the candidates realize different reward trade\-offs\. A model whose pool collapses to a single mode hasdiv→0\\mathrm\{div\}\\to 0even when the surface text varies\.

## 5Results

![Refer to caption](https://arxiv.org/html/2605.22817v1/x3.png)Figure 3:Test\-time scaling on MuSiQue and EUREQA\.Best@kkon the GRPO training scalar as a function ofkk\. Scalar GRPO plateaus quickly, reflecting collapse of the candidate pool to near\-duplicates, while VPO continues to extract value from additional samples\.#### VPO Improves Gains from Test\-Time Search

A central goal of VPO is to improve the effectiveness of test\-time search by producing more diverse and useful candidate solutions\. We evaluate this through best@kk, a simple search procedure that chooses the maximum scalarized reward over a pool ofkkcandidates\.

Across all four domains, Maze \(Table[2](https://arxiv.org/html/2605.22817#S5.T2)\), MuSiQue \(Table[1](https://arxiv.org/html/2605.22817#S5.T1)\), EUREQA \(Table[3](https://arxiv.org/html/2605.22817#S5.T3)\), and ToolRL \(Table[4](https://arxiv.org/html/2605.22817#S5.T4)\), VPO consistently improves best@kkrelative to scalar baselines\. While scalar GRPO quickly saturates askkincreases, indicating collapsing candidate diversity, VPO continues improving with additional samples and plateaus at a substantially higher level\. Figure[3](https://arxiv.org/html/2605.22817#S5.F3)shows this effect on MuSiQue and EUREQA \(the companion plot for Maze and ToolRL is in App\.[D](https://arxiv.org/html/2605.22817#A4)\)\.

Table 1:Best@kkon MuSiQue\(held\-out 300\-question hop\-stratified split\)\. Bold marks the best entry per column, underline the second\-best\. VPO continues improving askkgrows while scalar baselines plateau\.Table 2:Best@kkon Maze\(100 held\-out mazes\)\. VPO outperforms scalar baselines under the same uniform\-mean GRPO scalar even though it was trained on Dirichlet\-sampled scalarizations\.Table 3:Best@kkon EUREQA\(held\-out half ofhard\_5, averaged over 4 evaluation seeds\)\.Table 4:Best@kkon ToolRL\(80\-prompt held\-out split, averaged over 4 evaluation seeds\)\.
#### Is the gain due to multi\-answer prompting alone?

We want to understand if generating multiple answers within a shared autoregressive context, as explored in\[Puriet al\.,[2026](https://arxiv.org/html/2605.22817#bib.bib4)\]is enough for diversity\. It does not\. VPO outperformed Multi\-RLVR on best@kkacross all four domains, and the gap widened withkk, mirroring the pattern against scalar GRPO\. The mechanism is visible in App\.[D](https://arxiv.org/html/2605.22817#A4), Fig\.[6](https://arxiv.org/html/2605.22817#A4.F6), which plots the pairwiseL1L\_\{1\}distance between the per\-rollout*reward vectors*in each candidate pool—a measure of how much the pool spreads in reward space, not in token space\. Throughout training, Multi\-RLVR’s reward\-space diversity collapses on Maze, MuSiQue, and ToolRL\. Interestingly, the domain on which Multi\-RLVR performs best relative to the other baselines \(EUREQA\) is also the only one on which its training\-time reward\-space diversity tracks VPO’s, supporting the hypothesis that VPO’s training\-time diversity is instrumental in improving test\-time performance\. We conclude that multi\-answer prompting supplies the capacity to produce distinct candidates, but under a fixed scalarization, the gradient still pushes every position in the chain toward the same scalar optimum, so the candidates collapse to similar reward vectors\. The stochastic scalarization in VPO gives different positions an incentive to specialize\.

#### Is the gain due to more evaluator signal during training or normalization issues?

Table 5:MuSiQue\. Even when GRPO/GDPO receive 3×\\timesthe rollouts \(n=24n\{=\}24, also 3×\\timesthe LM compute\), they don’t match VPO atn=8n\{=\}8\.Two natural questions arise\. First, VPO may benefit simply from receiving 3x more evaluator signal per rollout\. Second, GRPO is known to be sensitive to reward components with very different variances, where a single high\-variance dimension can dominate the baseline\-subtracted advantage\. GDPO\[Liuet al\.,[2026](https://arxiv.org/html/2605.22817#bib.bib6)\]addresses this by normalizing the advantage per reward dimension before aggregating\. If VPO’s gains came from better gradient conditioning across components rather than from set\-level diversity, per\-dimension normalization should close the gap\.

We test both at once on the MuSiQue domain by giving GRPO and GDPO 3x the rollouts \(n=24n=24\) to equalize evaluator calls with VPO atn=8n=8\. Note that this also gives the baselines 3x the LM compute, since their reasoning chains are independent per answer rather than shared, so the comparison is conservative against VPO\. Table[5](https://arxiv.org/html/2605.22817#S5.T5)shows that neither effect explains the gap\. At matchedn=8n=8, GDPO closely tracks GRPO, indicating the per\-component normalization is not a binding constraint\. At 3x the compute, both GRPO and GDPO improve modestly but remain below VPO atn=8n=8, and adding randomwwscalarization atn=24n=24also fails to close the gap\. Extra evaluator signal during training and better normalization help marginally, but scalarized objectives still remove the incentive to maintain a diverse candidate set\.

#### Why not just condition onww?

Table 6:Goal\-conditioned GRPO on Mazeunder fixedw∗w^\{\*\}and randomw∼Dir​\(𝟏\)w\\sim\\mathrm\{Dir\}\(\\mathbf\{1\}\)\. Neither matches VPO on either the gold scalar or the Dirichlet\-averaged metric\.To optimize the model to output responses on the Pareto front, VPO uses in\-context exploration\. Prior work instead trains goal\-conditioned policies\[Yanget al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib95), Mahankaliet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib96)\]that take a target scalarizationwwas input and optimizew⊤​rw^\{\\top\}rdirectly\. \(These approaches create diversity by varyingwwat inference time\)\. To compare, we train a goal\-conditioned GRPO policy and evaluate it under two settings \(Table[6](https://arxiv.org/html/2605.22817#S5.T6)\):*\(i\)*conditioning on the canonical scalarizationw∗w^\{\*\}and*\(ii\)*conditioning on randomw∼Dir​\(𝟏\)w\\sim\\mathrm\{Dir\}\(\{\\mathbf\{1\}\}\)\. Neither matches VPO on the maze domain under either gold scalar expected value under a random weight distributions\. Interestingly, the goal conditioned policy had mode collapsed \(hence identical best@3 and best@6\), and also began to ignore the conditioning\. Despite explicit access toww, the model struggles to reliably translate text\-encoded preferences into effective behavior\.

#### How does VPO scale to harder problems and more sophisticated search?

Two questions remain after the main results: does VPO’s benefit survive on substantially harder problems, and does it survive under search procedures more sophisticated than best@kk? We answer both in a single\-checkpoint case study comparing VPO to scalar GRPO on LiveCodeBench \(LCB\)\[Jainet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib112)\], a competitive\-programming benchmark with a strict temporal held\-out cut \(App\.[A\.5](https://arxiv.org/html/2605.22817#A1.SS5)\)\. Both runs train on the same DeepCoder corpus from the same Qwen2\.5\-Coder\-7B\-Instruct checkpoint for one epoch; the only difference is the advantage estimator\. On single\-shot pass@11\(Fig\.[4](https://arxiv.org/html/2605.22817#S5.F4)A\), the regime with no downstream search to amortize over, GRPO is better; the scalar baseline correctly wins when only one shot is allowed\. The moment the model is given a candidate chain ofm=3m\{=\}3and is evaluated under best@kk\(Fig\.[4](https://arxiv.org/html/2605.22817#S5.F4)B\), the picture inverts: VPO sits above GRPO at everykkand the gap widens withkk, mirroring the main benchmark results\. Replacing best@kkwith a more capable search procedure makes the case sharper still\. We plug both checkpoints into OpenEvolve\[Sharma,[2025](https://arxiv.org/html/2605.22817#bib.bib1)\], an evolutionary test\-time search loop that iteratively rewrites candidates against test feedback, and run it on the3232hardest held\-out problems \(those on which neither method passes any test case at best@3030\)\. Over200200search iterations VPO continues to discover new solutions and cracks problems that neither arm could touch under the standard regime, while GRPO plateaus early \(Fig\.[4](https://arxiv.org/html/2605.22817#S5.F4)C,D\)\. The case study points the same direction as the main results: diversity matters most when downstream search is non\-trivial, and the benefit sharpens both as the problems get harder and as the search procedure gets more capable\.

![Refer to caption](https://arxiv.org/html/2605.22817v1/x4.png)Figure 4:LiveCodeBench case study: VPO vs\. scalar GRPO\.\(A\) Pass@kkon the full279279\-problem held\-out split: atk=1k\{=\}1GRPO is better, but VPO catches up and overtakes askkgrows\. \(B\) Best@kkon the same split: VPO sits above GRPO at everykkand the gap widens withkk, mirroring the main benchmark results\. \(C, D\) Pass@kkand best@kkover OpenEvolve search iterations on the3232hardest held\-out problems \(those on which both methods score0at best@3030in the standard regime\)\. VPO continues to discover new solutions over200200iterations and cracks problems neither arm could touch under best@kk, while GRPO plateaus early\.
#### When would VPO not help?

VPO’s central premise is that the reward decomposes into components whose individually optimal responses occupy distinct regions of the simplex, and its empirical gain is largest precisely when this premise holds\. On Maze, MuSiQue, EUREQA, and ToolRL the on\-policy reward components are not collinear under the trained model \(see App\.[F](https://arxiv.org/html/2605.22817#A6)\), the Pareto front is wide, and VPO produces sets that span it\. The benefit shrinks as the reward becomes effectively scalar\. On a separate experiment using the UltraFeedback\[Cuiet al\.,[2023](https://arxiv.org/html/2605.22817#bib.bib99)\]under ArmoRM\-5 reward model\[Wanget al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib100)\]the five nominally distinct components are near\-collinear, and so the simplex collapses to a near\-line, and VPO converges below scalar baselines on absolute best@kkwhile still retaining the largest per\-KKheadroom of any method\.

## 6Related Work

#### Inference\-time search over LLM outputs

A line of work treats the LLM as a generator inside a search loop\. Best\-of\-NNsampling\[Beiramiet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib45)\], self\-consistency\[Wanget al\.,[2022](https://arxiv.org/html/2605.22817#bib.bib87)\], particle filtering\[Puriet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib47)\], and Tree\-of\-Thoughts\[Yaoet al\.,[2023](https://arxiv.org/html/2605.22817#bib.bib85)\]draw or expand many candidates and select among them\. AlphaEvolve\[Novikovet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib75)\]and FunSearch\[Romera\-Paredeset al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib84)\]wrap static LLMs in evolutionary outer loops\. The effectiveness of these approaches depends on generating candidate sets with sufficient diversity and quality for selection to improve outcomes\. VPO instead trains the policy to directly produce candidate sets that better support inference\-time selection\. Another line of work integrate training into the search procedure\[Yuksekgonulet al\.,[2026](https://arxiv.org/html/2605.22817#bib.bib90), Wanget al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib92)\]\. These methods deliberately sacrifice generalization, as the policy is overfit to one instance for the duration of the search which is out of the scope of our setting\.

#### Training for best@kk

A growing line of work modifies the training objective to anticipate inference\-time selection\. BOND\[Sessaet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib88)\]and BoNBoN\[Guiet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib89)\]distill the Best\-of\-N distribution into a single policy\. InfAlign\[Balashankaret al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib91)\]derives reward transformations that make standard RLHF inference\-aware for procedures like BoN\. Closer to our setting, BoN\-aware fine\-tuning\[Chowet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib2)\], PKPO\[Walder and Karkhanis,[2025](https://arxiv.org/html/2605.22817#bib.bib54)\], Pass@kktraining\[Chenet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib27)\], and max@kkoptimization\[Bagirovet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib71)\]derive objectives that directly optimize max@kk\(or pass@kkfor binary rewards\)\. These methods treat thekksamples as independent draws from the policy, whereas VPO emits themmcandidates as a single autoregressive chain\. We additionally compare to Multi\-RLVR\[Puriet al\.,[2026](https://arxiv.org/html/2605.22817#bib.bib4)\], which jointly generates a set ofkkoutputs but optimizes a fixed scalar objective, whereas VPO optimizes across sampled reward weightings\. Our experiments show that VPO outperforms these methods, including max@kktraining\[Bagirovet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib71)\]\.

#### Multi\-objective RL and reward randomization

Vector rewards and Pareto\-optimal policy sets are classical tools in learning\[Roijerset al\.,[2013](https://arxiv.org/html/2605.22817#bib.bib98), Hayeset al\.,[2022](https://arxiv.org/html/2605.22817#bib.bib106)\]\. Goal\-conditioned methods recover the Pareto front by training a single network conditioned on a sampled weight vector\[Yanget al\.,[2019](https://arxiv.org/html/2605.22817#bib.bib13), Kanazawa and Gupta,[2023](https://arxiv.org/html/2605.22817#bib.bib14)\]\. Reward randomization has also been used to escape local optima\[Mahankaliet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib96)\]\.Tanget al\.\[[2021](https://arxiv.org/html/2605.22817#bib.bib94)\]sample reward perturbations during training to discover diverse multi\-agent strategies\. VPO builds on these ideas and proposes an RL algorithm to optimize a multi\-objective reward that fits and leverages the capabilities of LLMs\.

#### Diversity collapse from RL post\-training

RL post\-training sharpens the output distribution and erodes pass@kkat largekk\[Kirket al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib57), Yueet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib40), Karouzoset al\.,[2026](https://arxiv.org/html/2605.22817#bib.bib16)\]\.GX\-Chenet al\.\[[2025](https://arxiv.org/html/2605.22817#bib.bib7)\]argue this is structural\. VPO instead changes the objective, so coverage of the reward simplex is the equilibrium rather than something a regularizer fights for\.

## 7Discussion and Conclusion

We argued that when language models are deployed inside pipelines with test\-time search, the responsibilities of exploration and exploitation should be separated: training should produce a diverse pool of competent candidates, and the search procedure at test time should handle exploitation\. VPO instantiates this by sampling scalarizations uniformly over the simplex and training the policy to emit sets that span the Pareto front of the underlying reward components\. The change is a drop\-in replacement for the GRPO advantage estimator\. Across MuSiQue, EUREQA, Maze, and ToolRL, VPO improves best@kkover scalar baselines, with the gap widening as the test\-time budget grows\.

#### Why does VPO work?

We see two complementary explanations\. First, policies that are optimized to maximize the set\-level rewardR​\(S\)R\(S\)may produce reward\-diverse sets that cover the Pareto front \(or its budget\-constrained subset\)\. The second possible explanation is about training dynamics\. A candidate that scores poorly underw∗w^\{\*\}but well under some otherwwstill receives a positive gradient on the rollouts wherewwis sampled, while a fixed\-w∗w^\{\*\}run would push it away\. VPO, therefore, could keep a broader set of reasoning strategies alive long enough to be refined, including strategies aw∗w^\{\*\}\-trained policy would never visit\. Although hard to measure, this could be a part of why VPO outperforms aw∗w^\{\*\}\-trained policy even when both are evaluated underw∗w^\{\*\}\.

#### Limitations

VPO comes with three limitations\. First, precisely equalizing training compute across methods is non\-trivial, since each method produces outputs of different lengths and VPO generatesmmcompletions per rollout rather than one \(though this is partly amortized because the reasoning prefix is shared across themmsolutions\)\. To address this, we show in Section[5](https://arxiv.org/html/2605.22817#S5)that VPO continues to outperform GRPO on MuSiQue even when GRPO is given 3x the compute, indicating that the gains are not merely a function of compute mismatch\. Second, VPO benefits from a vector\-valued reward; when reward is scalar only, it reduces to more standard RL\. Finally, it sacrifices pass@11for pass@kkby training the policy to explore rather than to exploit\. VPO is for the regime where test\-time search is part of the system\.

## Acknowledgments and Disclosure of Funding

The authors express gratitude to Jyo Pari, Nitish Dashora, Andre Ye, Itamar Pres, Navodita Sharma, John Marangola, Nolan Fey, Oliver Sieberling, Linlu Qiu, Luca Grillotti, Benjamin Eysenbach, Yoon Kim, Jacob Andreas, and members of the Improbable AI lab at MIT for discussions that helped shape this work\. This work was supported by National Science Foundation graduate research fellowships to RB, IP, and AK, the MIT\-IBM Computing Research Lab, the MIT\-Google Program for Computing Innovation and Hyundai Motor Company\. This research was sponsored by the Army Research Office and was accomplished under Grant Numbers W911NF2110328 and W911NF\-23\-1\-0277\. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U\.S\. Government\. The U\.S\. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein\.

## References

- The best of n worlds: aligning reinforcement learning with best\-of\-n sampling via max@ k optimisation\.arXiv preprint arXiv:2510\.23393\.Cited by:[4th item](https://arxiv.org/html/2605.22817#S4.I1.i4.p1.4),[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px2.p1.8)\.
- A\. Balashankar, Z\. Sun, J\. Berant, J\. Eisenstein, M\. Collins, A\. Hutter, J\. Lee, C\. Nagpal, F\. Prost, A\. Sinha,et al\.\(2024\)Infalign: inference\-aware language model alignment\.arXiv preprint arXiv:2412\.19792\.Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px2.p1.8)\.
- A\. Beirami, A\. Agarwal, J\. Berant, A\. N\. D’Amour, J\. Eisenstein, C\. Nagpal, and A\. T\. Suresh \(2025\)Theoretical guarantees on the best\-of\-n alignment policy\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=u3U8qzFV7w)Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px1.p1.1)\.
- M\. Bellemare, S\. Srinivasan, G\. Ostrovski, T\. Schaul, D\. Saxton, and R\. Munos \(2016\)Unifying count\-based exploration and intrinsic motivation\.Advances in neural information processing systems29\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p1.1)\.
- B\. Brown, J\. Juravsky, R\. Ehrlich, R\. Clark, Q\. V\. Le, C\. Ré, and A\. Mirhoseini \(2024\)Large language monkeys: scaling inference compute with repeated sampling\.arXiv preprint arXiv:2407\.21787\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p2.1)\.
- M\. Chen, J\. Tworek, H\. Jun, Q\. Yuan, H\. P\. D\. O\. Pinto, J\. Kaplan, H\. Edwards, Y\. Burda, N\. Joseph, G\. Brockman,et al\.\(2021\)Evaluating large language models trained on code\.arXiv preprint arXiv:2107\.03374\.Cited by:[§2](https://arxiv.org/html/2605.22817#S2.SS0.SSS0.Px2.p1.11)\.
- Z\. Chen, X\. Qin, Y\. Wu, Y\. Ling, Q\. Ye, W\. X\. Zhao, and G\. Shi \(2025\)Pass@ k training for adaptively balancing exploration and exploitation of large reasoning models\.arXiv preprint arXiv:2508\.10751\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p1.1),[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px2.p1.8)\.
- Y\. Chow, G\. Tennenholtz, I\. Gur, V\. Zhuang, B\. Dai, S\. Thiagarajan, C\. Boutilier, R\. Agarwal, A\. Kumar, and A\. Faust \(2025\)Inference\-Aware Fine\-Tuning for Best\-of\-N Sampling in Large Language Models\.arXiv\.Note:arXiv:2412\.15287 \[cs\]External Links:[Link](http://arxiv.org/abs/2412.15287),[Document](https://dx.doi.org/10.48550/arXiv.2412.15287)Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px2.p1.8)\.
- K\. Cobbe, V\. Kosaraju, M\. Bavarian, M\. Chen, H\. Jun, L\. Kaiser, M\. Plappert, J\. Tworek, J\. Hilton, R\. Nakano,et al\.\(2021\)Training verifiers to solve math word problems\.arXiv preprint arXiv:2110\.14168\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p2.1)\.
- G\. Cui, L\. Yuan, N\. Ding, G\. Yao, B\. He, W\. Zhu, Y\. Ni, G\. Xie, R\. Xie, Y\. Lin,et al\.\(2023\)Ultrafeedback: boosting language models with scaled ai feedback\.arXiv preprint arXiv:2310\.01377\.Cited by:[§5](https://arxiv.org/html/2605.22817#S5.SS0.SSS0.Px6.p1.2)\.
- L\. Gui, C\. Gârbacea, and V\. Veitch \(2024\)Bonbon alignment for large language models and the sweetness of best\-of\-n sampling\.Advances in Neural Information Processing Systems37,pp\. 2851–2885\.Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px2.p1.8)\.
- A\. GX\-Chen, J\. Prakash, J\. Guo, R\. Fergus, and R\. Ranganath \(2025\)KL\-regularized reinforcement learning is designed to mode collapse\.arXiv preprint arXiv:2510\.20817\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p2.1),[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px4.p1.2)\.
- C\. F\. Hayes, R\. Rădulescu, E\. Bargiacchi, J\. Källström, M\. Macfarlane, M\. Reymond, T\. Verstraeten, L\. M\. Zintgraf, R\. Dazeley, F\. Heintz, E\. Howley, A\. A\. Irissappane, P\. Mannion, A\. Nowé, G\. Ramos, M\. Restelli, P\. Vamplew, and D\. M\. Roijers \(2022\)A practical guide to multi\-objective reinforcement learning and planning\.Autonomous Agents and Multi\-Agent Systems36\(1\)\.External Links:ISSN 1573\-7454,[Link](http://dx.doi.org/10.1007/s10458-022-09552-y),[Document](https://dx.doi.org/10.1007/s10458-022-09552-y)Cited by:[§2](https://arxiv.org/html/2605.22817#S2.SS0.SSS0.Px2.p5.2),[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px3.p1.1)\.
- Z\. Hong, I\. Shenfeld, J\. Wang, Y\. Chuang, A\. Pareja, J\. R\. Glass, A\. Srivastava, and P\. Agrawal \(2024\)Curiosity\-driven red\-teaming for large language models\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 19935–19961\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p1.1)\.
- N\. Jain, K\. Han, A\. Gu, W\. Li, F\. Yan, T\. Zhang, S\. Wang, A\. Solar\-Lezama, K\. Sen, and I\. Stoica \(2025\)LiveCodeBench: holistic and contamination free evaluation of large language models for code\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=chfJJYC3iL)Cited by:[§A\.5](https://arxiv.org/html/2605.22817#A1.SS5.p1.33),[§5](https://arxiv.org/html/2605.22817#S5.SS0.SSS0.Px5.p1.10)\.
- T\. Kanazawa and C\. Gupta \(2023\)Latent\-conditioned policy gradient for multi\-objective deep reinforcement learning\.InInternational Conference on Artificial Neural Networks,pp\. 63–76\.Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px3.p1.1)\.
- C\. Karouzos, X\. Tan, and N\. Aletras \(2026\)Where does output diversity collapse in post\-training?\.arXiv preprint arXiv:2604\.16027\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p2.1),[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px4.p1.2)\.
- R\. Kirk, I\. Mediratta, C\. Nalmpantis, J\. Luketina, E\. Hambro, E\. Grefenstette, and R\. Raileanu \(2024\)Understanding the effects of RLHF on LLM generalisation and diversity\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=PXD3FAVHJT)Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p2.1),[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px4.p1.2)\.
- W\. La Cava, T\. Helmuth, L\. Spector, and J\. H\. Moore \(2019\)A Probabilistic and Multi\-Objective Analysis of Lexicase Selection andϵ\\epsilon\-Lexicase Selection\.Evolutionary Computation27\(3\),pp\. 377–402\(eng\)\.External Links:ISSN 1530\-9304,[Document](https://dx.doi.org/10.1162/evco%5Fa%5F00224)Cited by:[§2](https://arxiv.org/html/2605.22817#S2.SS0.SSS0.Px2.p5.2)\.
- P\. Ladosz, L\. Weng, M\. Kim, and H\. Oh \(2022\)Exploration in deep reinforcement learning: a survey\.Information Fusion85,pp\. 1–22\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p1.1)\.
- R\. T\. Lange, Y\. Imajuku, and E\. Cetin \(2025\)Shinkaevolve: towards open\-ended and sample\-efficient program evolution\.arXiv preprint arXiv:2509\.19349\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p2.1)\.
- B\. Li, B\. Zhou, F\. Wang, X\. Fu, D\. Roth, and M\. Chen \(2024\)Deceptive semantic shortcuts on reasoning chains: how far can models go without hallucination?\.InProceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 1: Long Papers\),pp\. 7675–7688\.Cited by:[§A\.3](https://arxiv.org/html/2605.22817#A1.SS3.p1.10),[§4\.1](https://arxiv.org/html/2605.22817#S4.SS1.SSS0.Px3.p1.1)\.
- S\. Liu, X\. Dong, X\. Lu, S\. Diao, P\. Belcak, M\. Liu, M\. Chen, H\. Yin, Y\. F\. Wang, K\. Cheng, Y\. Choi, J\. Kautz, and P\. Molchanov \(2026\)GDPO: Group reward\-Decoupled Normalization Policy Optimization for Multi\-reward RL Optimization\.arXiv\.Note:arXiv:2601\.05242 \[cs\]Comment: NVIDIA\-Tech ReportExternal Links:[Link](http://arxiv.org/abs/2601.05242),[Document](https://dx.doi.org/10.48550/arXiv.2601.05242)Cited by:[§5](https://arxiv.org/html/2605.22817#S5.SS0.SSS0.Px3.p1.1)\.
- S\. Mahankali, Z\. Hong, A\. Sekhari, A\. Rakhlin, and P\. Agrawal \(2024\)Random latent exploration for deep reinforcement learning\.arXiv preprint arXiv:2407\.13755\.Cited by:[§5](https://arxiv.org/html/2605.22817#S5.SS0.SSS0.Px4.p1.6),[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px3.p1.1)\.
- A\. Ni, L\. Ding, and L\. Spector \(2024\)Dalex: lexicase\-like selection via diverse aggregation\.InEuropean Conference on Genetic Programming \(Part of EvoStar\),pp\. 90–107\.Cited by:[§2](https://arxiv.org/html/2605.22817#S2.SS0.SSS0.Px2.p5.2)\.
- A\. Novikov, N\. Vũ, M\. Eisenberger, E\. Dupont, P\. Huang, A\. Z\. Wagner, S\. Shirobokov, B\. Kozlovskii, F\. J\. Ruiz, A\. Mehrabian,et al\.\(2025\)Alphaevolve: a coding agent for scientific and algorithmic discovery\.arXiv preprint arXiv:2506\.13131\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p2.1),[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px1.p1.1)\.
- D\. Pathak, P\. Agrawal, A\. A\. Efros, and T\. Darrell \(2017\)Curiosity\-driven Exploration by Self\-supervised Prediction\.arXiv\(en\)\.Note:arXiv:1705\.05363 \[cs, stat\]External Links:[Link](http://arxiv.org/abs/1705.05363)Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p1.1)\.
- I\. Puri, M\. Damani, I\. Shenfeld, M\. Ghassemi, J\. Andreas, and Y\. Kim \(2026\)Reaching Beyond the Mode: RL for Distributional Reasoning in Language Models\.arXiv\.Note:arXiv:2603\.24844 \[cs\]External Links:[Link](http://arxiv.org/abs/2603.24844),[Document](https://dx.doi.org/10.48550/arXiv.2603.24844)Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p5.1),[§3\.1](https://arxiv.org/html/2605.22817#S3.SS1.p1.4),[2nd item](https://arxiv.org/html/2605.22817#S4.I1.i2.p1.1),[§5](https://arxiv.org/html/2605.22817#S5.SS0.SSS0.Px2.p1.3),[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px2.p1.8),[footnote 1](https://arxiv.org/html/2605.22817#footnote1)\.
- I\. Puri, S\. Sudalairaj, G\. Xu, K\. Xu, and A\. Srivastava \(2025\)Rollout roulette: a probabilistic inference approach to inference\-time scaling of llms using particle\-based monte carlo methods\.External Links:2502\.01618,[Link](https://arxiv.org/abs/2502.01618)Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px1.p1.1)\.
- C\. Qian, E\. C\. Acikgoz, Q\. He, H\. Wang, X\. Chen, D\. Hakkani\-Tür, G\. Tur, and H\. Ji \(2025\)Toolrl: reward is all tool learning needs\.arXiv preprint arXiv:2504\.13958\.Cited by:[§A\.4](https://arxiv.org/html/2605.22817#A1.SS4.p1.10),[§2](https://arxiv.org/html/2605.22817#S2.SS0.SSS0.Px2.p1.11),[§4\.1](https://arxiv.org/html/2605.22817#S4.SS1.SSS0.Px4.p1.1)\.
- Y\. Qu, A\. Setlur, V\. Smith, R\. Salakhutdinov, and A\. Kumar \(2026\)POPE: learning to reason on hard problems via privileged on\-policy exploration\.arXiv preprint arXiv:2601\.18779\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p1.1)\.
- D\. M\. Roijers, P\. Vamplew, S\. Whiteson, and R\. Dazeley \(2013\)A survey of multi\-objective sequential decision\-making\.Journal of Artificial Intelligence Research48,pp\. 67–113\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p4.1),[§2](https://arxiv.org/html/2605.22817#S2.SS0.SSS0.Px2.p5.2),[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px3.p1.1)\.
- B\. Romera\-Paredes, M\. Barekatain, A\. Novikov, M\. Balog, M\. P\. Kumar, E\. Dupont, F\. J\. Ruiz, J\. S\. Ellenberg, P\. Wang, O\. Fawzi,et al\.\(2024\)Mathematical discoveries from program search with large language models\.Nature625\(7995\),pp\. 468–475\.Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px1.p1.1)\.
- P\. G\. Sessa, R\. Dadashi\-Tazehozi, L\. Hussenot, J\. Ferret, N\. Vieillard, A\. Ramé, B\. Shahriari, S\. Perrin, A\. L\. Friesen, G\. Cideron,et al\.\(2025\)Bond: aligning llms with best\-of\-n distillation\.InThe Thirteenth International Conference on Learning Representations,Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px2.p1.8)\.
- A\. Setlur, M\. Y\. Yang, C\. Snell, J\. Greer, I\. Wu, V\. Smith, M\. Simchowitz, and A\. Kumar \(2025\)E3: learning to explore enables extrapolation of test\-time compute for llms\.arXiv preprint arXiv:2506\.09026\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p1.1)\.
- Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, X\. Bi, H\. Zhang, M\. Zhang, Y\. Li, Y\. Wu,et al\.\(2024\)Deepseekmath: pushing the limits of mathematical reasoning in open language models\.arXiv preprint arXiv:2402\.03300\.Cited by:[Appendix B](https://arxiv.org/html/2605.22817#A2.p1.1),[§1](https://arxiv.org/html/2605.22817#S1.p2.1),[§3\.2](https://arxiv.org/html/2605.22817#S3.SS2.SSS0.Px1.p1.6),[1st item](https://arxiv.org/html/2605.22817#S4.I1.i1.p1.1),[§4\.1](https://arxiv.org/html/2605.22817#S4.SS1.SSS0.Px4.p2.1)\.
- A\. Sharma \(2025\)OpenEvolve: an open\-source evolutionary coding agentExternal Links:[Link](https://github.com/algorithmicsuperintelligence/openevolve)Cited by:[§5](https://arxiv.org/html/2605.22817#S5.SS0.SSS0.Px5.p1.10)\.
- G\. Sheng, C\. Zhang, Z\. Ye, X\. Wu, W\. Zhang, R\. Zhang, Y\. Peng, H\. Lin, and C\. Wu \(2024\)HybridFlow: a flexible and efficient rlhf framework\.arXiv preprint arXiv: 2409\.19256\.Cited by:[Appendix B](https://arxiv.org/html/2605.22817#A2.p1.1),[§4\.1](https://arxiv.org/html/2605.22817#S4.SS1.SSS0.Px4.p2.1)\.
- L\. Spector, L\. Ding, and R\. Boldi \(2024\)Particularity\.InGenetic Programming Theory and Practice XX,pp\. 159–176\.Cited by:[§2](https://arxiv.org/html/2605.22817#S2.SS0.SSS0.Px2.p5.2)\.
- L\. Spector \(2012\)Assessment of Problem Modality by Differential Performance of Lexicase Selection in Genetic Programming: A Preliminary Report\.\(en\)\.Cited by:[§2](https://arxiv.org/html/2605.22817#S2.SS0.SSS0.Px2.p5.2)\.
- R\. S\. Sutton and A\. G\. Barto \(1998\)Reinforcement learning: an introduction\.Vol\.1,MIT press Cambridge\.Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p1.1)\.
- F\. Tajwar, G\. Zeng, Y\. Zhou, Y\. Song, D\. Arora, Y\. Jiang, J\. Schneider, R\. Salakhutdinov, H\. Feng, and A\. Zanette \(2026\)Maximum likelihood reinforcement learning\.arXiv preprint arXiv:2602\.02710\.Cited by:[5th item](https://arxiv.org/html/2605.22817#S4.I1.i5.p1.1)\.
- Z\. Tang, C\. Yu, B\. Chen, H\. Xu, X\. Wang, F\. Fang, S\. Du, Y\. Wang, and Y\. Wu \(2021\)Discovering diverse multi\-agent strategic behavior via reward randomization\.arXiv preprint arXiv:2103\.04564\.Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px3.p1.1)\.
- H\. Trivedi, N\. Balasubramanian, T\. Khot, and A\. Sabharwal \(2022\)MuSiQue: multihop questions via single\-hop question composition\.Transactions of the Association for Computational Linguistics10,pp\. 539–554\.Cited by:[§A\.2](https://arxiv.org/html/2605.22817#A1.SS2.p1.6),[§2](https://arxiv.org/html/2605.22817#S2.SS0.SSS0.Px2.p1.11),[§4\.1](https://arxiv.org/html/2605.22817#S4.SS1.SSS0.Px2.p1.2)\.
- C\. Walder and D\. Karkhanis \(2025\)Pass@ k policy optimization: solving harder reinforcement learning problems\.arXiv preprint arXiv:2505\.15201\.Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px2.p1.8)\.
- H\. Wang, W\. Xiong, T\. Xie, H\. Zhao, and T\. Zhang \(2024\)Interpretable preferences via multi\-objective reward modeling and mixture\-of\-experts\.InFindings of the Association for Computational Linguistics: EMNLP 2024,pp\. 10582–10592\.Cited by:[§2](https://arxiv.org/html/2605.22817#S2.SS0.SSS0.Px2.p1.11),[§5](https://arxiv.org/html/2605.22817#S5.SS0.SSS0.Px6.p1.2)\.
- X\. Wang, J\. Wei, D\. Schuurmans, Q\. Le, E\. Chi, S\. Narang, A\. Chowdhery, and D\. Zhou \(2022\)Self\-consistency improves chain of thought reasoning in language models\.arXiv preprint arXiv:2203\.11171\.Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px1.p1.1)\.
- Y\. Wang, S\. Su, Z\. Zeng, E\. Xu, L\. Ren, X\. Yang, Z\. Huang, X\. He, L\. Ma, B\. Peng, H\. Cheng, P\. He, W\. Chen, S\. Wang, S\. S\. Du, and Y\. Shen \(2025\)ThetaEvolve: Test\-time Learning on Open Problems\.arXiv\.Note:arXiv:2511\.23473 \[cs\]External Links:[Link](http://arxiv.org/abs/2511.23473),[Document](https://dx.doi.org/10.48550/arXiv.2511.23473)Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px1.p1.1)\.
- F\. Wu and Y\. Choi \(2025\)The invisible leash: why rlvr may not escape its origin\.In2nd AI for Math Workshop@ ICML 2025,Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p2.1)\.
- R\. Yang, X\. Pan, F\. Luo, S\. Qiu, H\. Zhong, D\. Yu, and J\. Chen \(2024\)Rewards\-in\-context: multi\-objective alignment of foundation models with dynamic preference adjustment\.arXiv preprint arXiv:2402\.10207\.Cited by:[§5](https://arxiv.org/html/2605.22817#S5.SS0.SSS0.Px4.p1.6)\.
- R\. Yang, X\. Sun, and K\. Narasimhan \(2019\)A generalized algorithm for multi\-objective reinforcement learning and policy adaptation\.Advances in neural information processing systems32\.Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px3.p1.1)\.
- S\. Yao, D\. Yu, J\. Zhao, I\. Shafran, T\. Griffiths, Y\. Cao, and K\. Narasimhan \(2023\)Tree of thoughts: deliberate problem solving with large language models\.Advances in neural information processing systems36,pp\. 11809–11822\.Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px1.p1.1)\.
- Y\. Yue, Z\. Chen, R\. Lu, A\. Zhao, Z\. Wang, Y\. Yue, S\. Song, and G\. Huang \(2025\)Does reinforcement learning really incentivize reasoning capacity in llms beyond the base model?\.External Links:2504\.13837,[Link](https://arxiv.org/abs/2504.13837)Cited by:[§1](https://arxiv.org/html/2605.22817#S1.p2.1),[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px4.p1.2)\.
- M\. Yuksekgonul, D\. Koceja, X\. Li, F\. Bianchi, J\. McCaleb, X\. Wang, J\. Kautz, Y\. Choi, J\. Zou, C\. Guestrin,et al\.\(2026\)Learning to discover at test time\.arXiv preprint arXiv:2601\.16175\.Cited by:[§6](https://arxiv.org/html/2605.22817#S6.SS0.SSS0.Px1.p1.1)\.

## Appendix AEnvironment Details

### A\.1Maze

#### Generation\.

Each maze is a9×99\{\\times\}9grid built in two stages\. We first carve a spanning tree using Prim’s algorithm: starting from an all\-walls grid and a uniformly random seed cell, we repeatedly pop a uniform random frontier cell and carve it to empty if it has exactly one empty neighbor \(the standard wall\-carving rule\)\. We then injectncycles∼Unif​\{18,…,28\}n\_\{\\text\{cycles\}\}\\sim\\mathrm\{Unif\}\\\{18,\\dots,28\\\}additional openings by converting wall cells with≥2\\geq 2empty neighbors to empty; this is essential, since it turns the spanning tree into a multi\-route graph so VPO’s candidate pool has distinct paths to find\. Endpoints are placed as one of\{\(0,0\)→\(8,8\),\(0,8\)→\(8,0\)\}\\\{\(0,0\)\{\\to\}\(8,8\),\(0,8\)\{\\to\}\(8,0\)\\\}with equal probability; the remaining two corners are randomly designated the*gold corner*and*diamond corner*; the center cell\(4,4\)\(4,4\)is a*bonus tile*that is rendered in the grid \(asB\) and advertised in the prompt as a score multiplier, but is in fact a distractor: visiting it has no effect on the reward\. We then compute via\-BFS detour lengthsvia​\_​gold=d​\(S,gold\)\+d​\(gold,E\)\\mathrm\{via\\\_gold\}=d\(S,\\mathrm\{gold\}\)\+d\(\\mathrm\{gold\},E\),via​\_​diam=d​\(S,diam\)\+d​\(diam,E\)\\mathrm\{via\\\_diam\}=d\(S,\\mathrm\{diam\}\)\+d\(\\mathrm\{diam\},E\), andvia​\_​both=d​\(S,gold\)\+d​\(gold,diam\)\+d​\(diam,E\)\\mathrm\{via\\\_both\}=d\(S,\\mathrm\{gold\}\)\+d\(\\mathrm\{gold\},\\mathrm\{diam\}\)\+d\(\\mathrm\{diam\},E\), and define the step budgetbudget=max⁡\(via​\_​gold,via​\_​diam\)\+7\\text\{budget\}=\\max\(\\mathrm\{via\\\_gold\},\\mathrm\{via\\\_diam\}\)\+7\. We*reject*the maze unlessvia​\_​both\>budget\\mathrm\{via\\\_both\}\>\\text\{budget\}– this is the design lever that guarantees the budget fits one corner detour but not both, so no single route can hit both the gold and diamond corners and still reachEE\. We then placengold∼Unif​\{3,…,5\}n\_\{\\text\{gold\}\}\\sim\\mathrm\{Unif\}\\\{3,\\dots,5\\\}gold cells in the Manhattan\-radius\-2 ball around the gold corner, the same for diamonds, andnlava∼Unif​\{3,…,5\}n\_\{\\text\{lava\}\}\\sim\\mathrm\{Unif\}\\\{3,\\dots,5\\\}lava cells in the strict interior\{\(r,c\):2≤r,c≤6\}\\\{\(r,c\):2\\leq r,c\\leq 6\\\}\. A final BFS check verifies that a lava\-avoiding pathS→ES\\to Eexists within budget; otherwise the maze is rejected\. The first 1000 mazes that survive \(seeds from 42\) form the train split; the next 100 \(seeds from 4242\) form the test split\.

#### Reward\.

The model’s text output is parsed into a move list and simulated: walls and borders block, the trajectory ends as soon asEEis stepped on, lava is walkable but counted, and items only count if collected before reachingEE\. IfEEis never reached, the reward vector is\(0,0,0,0\)\(0,0,0,0\)on all four dimensions\. Otherwise, define the per\-item collection rates

g=\|distinct gold visited\|ngold,d=\|distinct diamond visited\|ndiam,ℓ=1−\|distinct lava stepped\|nlava\.g\\;=\\;\\frac\{\|\\text\{distinct gold visited\}\|\}\{n\_\{\\text\{gold\}\}\},\\qquad d\\;=\\;\\frac\{\|\\text\{distinct diamond visited\}\|\}\{n\_\{\\text\{diam\}\}\},\\qquad\\ell\\;=\\;1\-\\frac\{\|\\text\{distinct lava stepped\}\|\}\{n\_\{\\text\{lava\}\}\}\.The 4\-D reward is

r​\(x,y\)=\(1,g,d,ℓ\)∈\[0,1\]4,r\(x,y\)\\;=\\;\\bigl\(\\,1,\\;\\,g,\\;\\,d,\\;\\,\\ell\\,\\bigr\)\\in\[0,1\]^\{4\},i\.e\., binary completion together with the three linear item\-collection and lava\-avoidance fractions\. The gold scalar used by GRPO, MaxRL, GoalCond\(w⋆w^\{\\star\}\) training, and by best@kkevaluation is the uniform mean

r¯=14​\(r1\+r2\+r3\+r4\)\.\\bar\{r\}\\;=\\;\\tfrac\{1\}\{4\}\\bigl\(r\_\{1\}\+r\_\{2\}\+r\_\{3\}\+r\_\{4\}\\bigr\)\.

### A\.2MuSiQue

MuSiQue\[Trivediet al\.,[2022](https://arxiv.org/html/2605.22817#bib.bib9)\]is a multi\-hop QA benchmark in which each 2–4 hop question decomposes into a chain of sub\-questions whose answers must be composed; we use the MuSiQue\-Ans split \(19,938 train / 2,417 test\)\. Each prompt embeds the question alongside 20 paragraphs, 2–4 of which carry gold supporting evidence and the rest sampled as distractors from MuSiQue’s own paragraph pool \(no external retrieval\)\. The model emits a<support\>block \(paragraph indices, capped at four distinct entries\) and an<answer\>block\. The reward vectorr​\(x,s\)∈ℝ5r\(x,s\)\\in\\mathbb\{R\}^\{5\}contains four binary citation indicators, one per gold hop \(hop1,…,hop4\\mathrm\{hop\}\_\{1\},\\dots,\\mathrm\{hop\}\_\{4\}\), each\{0,1\}\\\{0,1\\\}for whether<support\>cites that paragraph, plus a continuousanswer​\_​f1\\mathrm\{answer\\\_f1\}against gold \(best over aliases, with MuSiQue\-style normalization: lowercase, drop articles, drop punctuation\)\. The GRPO scalar is\(∑ihopi\+3​answer​\_​f1\)/7\\big\(\\sum\_\{i\}\\mathrm\{hop\}\_\{i\}\+3\\,\\mathrm\{answer\\\_f1\}\\big\)/7, weighting the answer3×3\\timesto reflect that a correct answer is worth more than any single citation\. The two reward components are causally linked but not redundant: a model can answer correctly while citing distractors, or cite correctly and fail to compose, so the domain probes pipeline coupling between evidence and answer\. The asymmetric scalar weighting gives GRPO an explicit single\-objective bias toward the answer, while vector\-reward methods see all five dimensions at parity\. We train Qwen3\-1\.7B from a shared base for one epoch across all methods and evaluate on a hop\-stratified split of 300 held\-out questions\.

### A\.3EUREQA

EUREQA\[Liet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib74)\]is a 5\-hop chain\-reasoning benchmark released with two difficulty levels of the same underlying questions:questions\_normal\_5\(1,109 examples, baseline phrasing\) andquestions\_hard\_5\(682 examples, harder rephrasings\)\. We use a 50/50 random split ofhard\_5\(seed 0\) as the held\-out test set, and train on the remaining half ofhard\_5together with all of the easiernormal\_5rephrasings\. The test set is therefore in\-distribution with the harder half of training data, while thenormal\_5rephrasings provide a small additional easy\-data exposure\. Each prompt is a narrative containing six masked entitiesA,B,C,D,E,FA,B,C,D,E,Fconnected by a 5\-relation chain, with the anchor entityFFshown verbatim; the model must back\-chain through the relations to identifyAAthroughEEby their canonical Wikipedia names \(e\.g\.,Robert\_Rodriguez\), emitting five numbered tags\. The reward vectorr​\(x,y\)∈\{0,1\}5r\(x,y\)\\in\\\{0,1\\\}^\{5\}is binary, with one exact\-match indicator per entity after Wikipedia\-style normalization\. The GRPO scalar is a uniform mean of the five dimensions\. Unlike MuSiQue’s loosely coupled hops, the EUREQA chain is causally chained: identifyingEErequires composing a relation step fromFF,DDrequiresEE, and so on\. Scalar reward provides no signal about which hop in the chain failed, while vector\-reward methods see per\-hop correctness, so this domain probes whether per\-dim training signal yields more robust chain\-following on the harder rephrasings\. We train Qwen3\-8B and report best@kkaveraged over 4 evaluation seeds on the held\-outhard\_5test split\.

### A\.4ToolRL

ToolRL\[Qianet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib73)\]is a function\-calling benchmark assembled from ToolACE, Hammer, and xLAM, comprising 3,920 train and 80 test prompts\. The reward vectorr​\(x,y\)∈ℝ4r\(x,y\)\\in\\mathbb\{R\}^\{4\}contains one binary and three continuous F1 dimensions:format∈\{0,1\}\\mathrm\{format\}\\in\\\{0,1\\\}\(structural well\-formedness; all four format checks collapse to a single binary pass\),tool​\_​name∈\[0,1\]\\mathrm\{tool\\\_name\}\\in\[0,1\]\(multiset F1 between predicted and gold tool\-call names\),arg​\_​key∈\[0,1\]\\mathrm\{arg\\\_key\}\\in\[0,1\]\(mean set\-F1 over parameter keys across aligned tool calls, with greedy alignment by name then by key overlap\), andarg​\_​value∈\[0,1\]\\mathrm\{arg\\\_value\}\\in\[0,1\]\(token\-level F1 between predicted and gold values on aligned keys\)\. The GRPO scalar is a uniform mean of the four dimensions\. The dimensions are graded by difficulty:format\\mathrm\{format\}is trivially solvable,tool​\_​name\\mathrm\{tool\\\_name\}requires retrieval,arg​\_​key\\mathrm\{arg\\\_key\}requires schema knowledge, andarg​\_​value\\mathrm\{arg\\\_value\}requires precise content generation\. We train Qwen3\-1\.7B and report best@kkaveraged over 4 evaluation seeds on the 80\-prompt test split\.

### A\.5LiveCodeBench \(case study\)

LiveCodeBench \(LCB\)\[Jainet al\.,[2025](https://arxiv.org/html/2605.22817#bib.bib112)\]is a competitive\-programming benchmark with a strict temporal held\-out cut: each problem has a contest date and the held\-out slice \(Aug 2024 – Feb 2025\) postdates every training\-time problem, ruling out contamination by construction\. We use LCB as a two\-arm scaling case study \(VPO and scalar GRPO only\) rather than as one of the four main benchmark domains\. Training data is the DeepCoder corpus,24,26924\{,\}269problems concatenated from three sources:16,23816\{,\}238from PrimeIntellect SYNTHETIC\-1 \(stdin, easiest\),7,4327\{,\}432from TACO \(Topics in Algorithmic Code Generation; verified competitive\-programming slice, middle difficulty\), and599599from LCB\-v5 train \(May – Jul 2024, hardest\)\. Each row carries a structured array of test cases withinputs/outputs\(and anfn\_namefield for functional\-I/O problems\); per\-problem test counts are variable, capped at3232by the preprocessor\. The held\-out evaluation split is LCB\-v5 Aug 2024 – Feb 2025,279279problems, strictly later than every training\-time LCB problem\. The reward vector is a per\-test\-case binary pass indicator,r​\(x,y\)∈\{0,1\}dr\(x,y\)\\in\\\{0,1\\\}^\{d\}, whereddis the problem\-specific test count; VPO samples a Dirichlet of dimensionddper prompt with no zero\-padding for advantage computation\. The gold scalar is the uniform mean over the actually\-present dimensions, which equals the problem’s pass rate\. Training uses Qwen2\.5\-Coder\-7B\-Instruct, FSDP across8×8\\timesH100 80 GB, GRPO inner loop with PPO\-clipε=0\.2\\varepsilon\{=\}0\.2, AdamWlr=10−6\\mathrm\{lr\}\{=\}10^\{\-6\}\(constant, no warmup\), weight decay0\.010\.01, gradient clip1\.01\.0, KL coefficient10−310^\{\-3\}, no entropy bonus; train batch6464, mini\-batch3232,n=8n\{=\}8rollouts per prompt, generation temperature0\.80\.8, max context4096\+40964096\+4096\. One epoch is≈379\\approx 379steps; we evaluate atglobal\_step\_378for both methods\. The configuration is identical across VPO and GRPO except for the advantage estimator\. For pass@kkand best@kkwe sample3030candidates per problem at temperature0\.80\.8over the full279279\-problem held\-out split\. For OpenEvolve we restrict to the3232hardest problems \(those on which both VPO and GRPO score0at best@3030in the standard regime\) and run200200iterations withm=3m\{=\}3candidates per iteration \(≈600\\approx 600candidates per problem\); the test feedback from each iteration is exposed to the model as the search\-loop input\. The restricted subset isolates the regime where the standard best@kkpool is exhausted, so any further progress must come from the search procedure itself rather than from drawing more samples\.

## Appendix BTraining Setup

All methods share a common GRPO\[Shaoet al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib12)\]backbone implemented on top of veRL\[Shenget al\.,[2024](https://arxiv.org/html/2605.22817#bib.bib79)\]; only the advantage estimator changes per method\. The recipe below applies to GRPO and to all VPO variants unless stated otherwise\.

#### Advantage estimation\.

For each prompt we sample a group ofn=8n\{=\}8rollouts, compute a per\-rollout scalar score \(per\-domain formula in Table[7](https://arxiv.org/html/2605.22817#A2.T7)\), and form the advantage as the within\-groupzz\-scoreA^i=\(scorei−μg\)/\(σg\+ϵ\)\\hat\{A\}\_\{i\}=\(\\mathrm\{score\}\_\{i\}\-\\mu\_\{g\}\)/\(\\sigma\_\{g\}\+\\epsilon\)withϵ=10−6\\epsilon\{=\}10^\{\-6\}and population standard deviation\. The advantage is broadcast across all response tokens via the response mask\. There is no value/critic network and no GAE\.

#### Objective\.

Standard PPO\-clip withϵ=0\.2\\epsilon\{=\}0\.2\(symmetric, dual\-clipc=3\.0c\{=\}3\.0\),ppo​\_​epochs=1\\mathrm\{ppo\\\_epochs\}\{=\}1, token\-mean loss aggregation, and no entropy bonus\. KL is applied as a loss\-side regularizer only \(no in\-reward penalty\): low\-variancek3k\_\{3\}estimator against a frozen reference equal to the SFT initialization, with coefficientβKL=10−3\\beta\_\{\\mathrm\{KL\}\}=10^\{\-3\}\.

#### Optimizer\.

AdamW with learning rate10−610^\{\-6\},\(β1,β2\)=\(0\.9,0\.999\)\(\\beta\_\{1\},\\beta\_\{2\}\)\{=\}\(0\.9,0\.999\), weight decay0\.010\.01, gradient clipping at1\.01\.0, no warmup, constant learning\-rate schedule\.

#### Engine and rollout sampling\.

FSDP1 with bf16 mixed precision \(parameter dtype fp32\)\. The reference policy is a frozen copy of the actor’s initialization with parameters CPU\-offloaded between forward passes\. Training rollouts use vLLM at temperature1\.01\.0, top\-pp1\.01\.0, top\-kk−1\-1\. In\-training validation uses greedy decoding \(do\_sample=False\) on all four domains as a low\-noise progress signal\.

#### Final\-evaluation sampling\.

The numbers reported in the main paper come from a separate post\-training evaluation pass with stochastic decoding, so that best@kkhas a non\-degenerate candidate pool to draw from\. We usetop​\_​k=−1\\mathrm\{top\\\_k\}=\-1everywhere and the following per\-domain settings, applied uniformly across every method evaluated on that domain: Maze and MuSiQue at temperature0\.70\.7, top\-pp1\.01\.0; EUREQA and ToolRL at temperature0\.70\.7, top\-pp0\.950\.95\.

#### Per\-domain batch sizes\.

Batch sizes vary with model scale\. For Qwen≤\\leq4B \(Maze, MuSiQue, ToolRL\): train batch128128, mini\-batch6464, micro\-batch88,n=8n\{=\}8rollouts per prompt\. For Qwen 7B/8B \(EUREQA\): train batch6464, mini\-batch3232, micro\-batch22,n=8n\{=\}8\. We honor veRL’s divisibility constraints \(train×n\\times ndivisible by GPU count; train divisible by mini\-batch; mini\-batch divisible by micro\-batch×\\timesGPU count\), so each PPO update consumes the full train\-batch generation, with train//mini gradient steps per generation\.

#### Per\-domain GRPO scalar\.

Table[7](https://arxiv.org/html/2605.22817#A2.T7)lists the per\-domain scalar reward formulasw⋆⊤​r​\(x,y\)w^\{\\star\\top\}r\(x,y\)used as the GRPO score\. Empty or unparseable responses receivescore=0\\mathrm\{score\}=0in every domain\.

Table 7:Per\-domain GRPO scalar reward formulas\.ddis the dimensionality of the underlying vector rewardrr\.

## Appendix CCompute Resources

All experiments ran on NVIDIA H100 GPUs \(80 GB SXM\)\. Each training run used a single node with4×4\\timesH100, with a typical wall\-clock duration of approximately 12 hours per run \(∼\\sim48 GPU\-hours per run\)\. The reported best@kknumbers come from training one run per \(method, domain\) cell across the four domains \(Maze, MuSiQue, EUREQA, ToolRL\) and the five core methods \(GRPO, Random\-ww, Max\-at\-KK, Multi\-RLVR, VPO\), plus the goal\-conditioned baseline on Maze and the3×3\{\\times\}\-rollout ablation on MuSiQue, totaling roughly 20–25 reported training runs \(∼\\sim1,000 GPU\-hours\)\. Including preliminary, failed, and hyperparameter\-search runs, the full project consumed approximately2×2\\timesthe reported budget \(∼\\sim2,000 GPU\-hours total\)\. Inference\-time evaluation \(best@kkpool generation and theρ¯\\bar\{\\rho\}collinearity diagnostics in App\.[F](https://arxiv.org/html/2605.22817#A6)\) was orders of magnitude cheaper and is not separately accounted for\.

## Appendix DAdditional Figures

![Refer to caption](https://arxiv.org/html/2605.22817v1/x5.png)Figure 5:Test\-time scaling on Maze and ToolRL\.Best@kkon the GRPO training scalar as a function ofkk, pooled acrossccmulti\-answer chains per prompt\. VPO matches or exceeds scalar baselines at everykkon Maze; on ToolRL all methods saturate near the reward ceiling and converge\. Companion to Fig\.[3](https://arxiv.org/html/2605.22817#S5.F3)\.![Refer to caption](https://arxiv.org/html/2605.22817v1/x6.png)Figure 6:Reward\-space diversity over training\.PairwiseL1L\_\{1\}distance between the per\-rollout reward vectorsr​\(x,y\)∈ℝdr\(x,y\)\\in\\mathbb\{R\}^\{d\}in each candidate pool, averaged across prompts, plotted over training steps\. This measures the spread of the pool in reward space \(not in token space\): a large value means the rollouts realize different reward trade\-offs\. VPO sustains substantially higher reward\-space diversity than Multi\-RLVR throughout training; the only domain on which Multi\-RLVR’s diversity tracks VPO’s is EUREQA, which is also the only domain on which Multi\-RLVR comes close to VPO on best@kk\.
## Appendix EDomain Prompts

For each domain, we list the prompt template as it appears in the training corpus \(single\-solution form\) followed by the rewriting applied for multi\-solution methods \(Multi\-RLVR, VPO\)\. We usem=3m\{=\}3candidates per multi\-answer chain on all domains\. Curly\-braced names \(\{question\},\{m\}, etc\.\) are placeholders filled in per example\. The goal\-conditioning suffix \(§[E\.5](https://arxiv.org/html/2605.22817#A5.SS5)\) is appended only for the goal\-conditioned baseline\.

### E\.1MuSiQue

`MuSiQue: single\-solution prompt \{paragraphs\_text\} is "\[\{idx\}\] \(Title: \{title\}\) \{paragraph\_text\}" joined over 20 paragraphs \(2–4 gold, the rest distractors\)\.`

`Multi\-solution rewrite\. The block from “First reason…” through “<answer\>your answer</answer\>” is replaced with: MuSiQue: multi\-solution rewrite The header, paragraphs, and question are unchanged\. E\.2 EUREQA EUREQA: single\-solution prompt \{mask\_list\} is the five masks bulleted with “ \- ”\. Multi\-solution rewrite\. The block from “Replace each ‘\.\.\.‘ below…” through “…in <entity\_A\>” is replaced with: EUREQA: multi\-solution rewrite E\.3 Maze The example below shows the prompt for one specific maze \(the per\-maze grid, item counts, and step budget are filled in per example\)\. Maze: single\-solution prompt \(GRPO, MaxRL, GDPO, MaxAtK, RandomW\) Multi\-solution rewrite\. The multi\-solution prompt \(used by VPO and Multi\-RLVR with m=3m\{=\}3\) reuses the preamble, grid, and bullet list verbatim, except that “You have 27 steps\.” becomes “You have 27 steps per route\.”\. The closing two lines \(the tile\-count line and the “Output moves …” instruction\) are replaced by the block below\. Maze: multi\-solution rewrite \(m=3m=3\) For general mm, the tag list extends to <route\_1\>…</route\_1\>, …, <route\_m\>…</route\_m\>\. E\.4 ToolRL ToolRL prompts come directly from the upstream qiancheng0/ToolRL rlla\_4k corpus: the system message specifies the output format and the user message contains the dialogue task\. We do not override the system prompt\. ToolRL: system message The user message is the task itself, e\.g\.: ToolRL: example user message Multi\-solution rewrite\. The system message is unchanged\. The block below is appended to the user message\. ToolRL: multi\-solution rewrite E\.5 Goal\-Conditioning Suffix \(Goal\-Conditioned GRPO baseline only\) For the goal\-conditioned GRPO baseline \(any domain\), the following block is appended to whichever variant is in use \(single or multi\)\. Per training example, weights are resampled from Dir​\(1,…,1\)\\mathrm\{Dir\}\(1,\\ldots,1\)\. Goal\-conditioning suffix The per\-domain \{desc\_i\} strings are domain\-specific component names; for MuSiQue, e\.g\., “Finding evidence for reasoning step 1”, …, “Finding evidence for reasoning step 4”, “Answer word\-level accuracy”\. Appendix F Reward Collinearity Predicts When VPO Helps In §5 we argued that VPO’s gain over scalar baselines depends on whether the reward components are genuinely competing or effectively redundant\. To make this prediction quantitative, we run a single cross\-domain diagnostic: for each \(domain, method\) pair we measure \(i\) the on\-policy collinearity of the reward vector under the trained model and \(ii\) the realized best@1616 under the GRPO training scalar\. The prediction is that VPO outperforms scalar GRPO precisely when on\-policy reward dimensions are not collinear; UltraFeedback should be the only domain in which the prediction inverts\. Table 9 confirms this\. Across Maze, MuSiQue, EUREQA, and ToolRL, on\-policy ρ¯\\bar\{\\rho\} stays well below 1 and VPO wins best@1616\. On UltraFeedback the on\-policy distribution is near\-collinear \(ρ¯VPO=0\.95\\bar\{\\rho\}\_\{\\text\{VPO\}\}=0\.95, ρ¯GRPO=0\.82\\bar\{\\rho\}\_\{\\text\{GRPO\}\}=0\.82\): the simplex collapses to a near\-line, there is essentially one Pareto\-optimal candidate per prompt, and VPO roughly matches GRPO\. This is a sanity check on the regime claim in §5: when the reward is effectively scalar, VPO does not \(and should not\) outperform scalar GRPO\. Table 8: Best@kk on UltraFeedback under the ArmoRM\-5 reward model\. The on\-policy reward simplex is near\-collinear, so VPO loses to scalar GRPO on absolute best@kk while still retaining the largest per\-kk headroom of any method\. Method best@1 best@5 best@10 best@20 best@50 Δ\\Delta Qwen3\-4B \(single\-answer prompt\) 0\.700 0\.724 0\.730 0\.735 0\.741 \+0\.041 ↪\\hookrightarrow GRPO 0\.741 0\.762 0\.768 0\.773 0\.779 \+0\.038 ↪\\hookrightarrow GDPO 0\.737 0\.759 0\.765 0\.770 0\.776 \+0\.039 ↪\\hookrightarrow Goal\-cond 0\.727 0\.750 0\.756 0\.762 0\.767 \+0\.040 Qwen3\-4B \(multi\-answer prompt\) 0\.700 0\.724 0\.730 0\.735 0\.741 \+0\.041 ↪\\hookrightarrow Multi\-RLVR 0\.730 0\.763 0\.770 0\.775 0\.780 \+0\.050 ↪\\hookrightarrow VPO \(ours\) 0\.700 0\.755 0\.763 0\.769 0\.776 \+0\.076 Table 9: On\-policy reward collinearity ρ¯\\bar\{\\rho\} vs\. realized best@1616 across all five domains\. VPO’s advantage over scalar GRPO disappears exactly on UltraFeedback, the only domain where the on\-policy components are near\-collinear\. on\-policy ρ¯\\bar\{\\rho\} best@16 Domain reward dims VPO GRPO VPO GRPO Δ\\Delta Maze 4 reward feats \(D=4D\{=\}4\) 0\.39 0\.37 0\.593 0\.432 \+0\.161 MuSiQue 4 hop \+ 1 F1 \(D=5D\{=\}5\) 0\.12 0\.11 0\.864 0\.841 \+0\.023 EUREQA 5 entity\-EM \(D=5D\{=\}5\) 0\.05 0\.03 0\.204 0\.182 \+0\.022 ToolRL 4 sub\-metrics \(D=4D\{=\}4\) 0\.86 0\.62 0\.953 0\.924 \+0\.028 UltraFeedback 5 ArmoRM dims \(D=5D\{=\}5\) 0\.95 0\.82 0\.767 0\.772 \-0\.004 Methodology\. For each \(domain, method\) pair we proceed as follows\. 1\. On\-policy rollout pool\. Sample the trained checkpoint for that method on every prompt in the held\-out evaluation set, drawing NN samples per prompt under the domain’s final\-evaluation sampler \(App\. B\)\. Per\-domain pool shapes \(prompts ×\\times samples ×\\times reward dims\) are: Maze 500×30×4500\\times 30\\times 4 \(\[completion, gold, diamond, avoid\_lava\]\); MuSiQue 300×30×5300\\times 30\\times 5 \(4 hop indicators \+ answer\-F1\); EUREQA 682×50×5682\\times 50\\times 5 \(entity\-EM\); ToolRL 80×N×480\\times N\\times 4; and UltraFeedback \(epoch 2\) 200×50×5200\\times 50\\times 5 \(ArmoRM dims\)\. 2\. ρ¯\\bar\{\\rho\} \(on\-policy off\-diagonal Pearson correlation\)\. Flatten the rollout tensor to \(Nresponses,D\)\(N\_\{\\text\{responses\}\},D\), drop zero\-variance dimensions, compute the D×DD\{\\times\}D Pearson correlation matrix \(np\.corrcoef\), and average the D​\(D−1\)D\(D\{\-\}1\) off\-diagonal entries\. We report ρ¯VPO\\bar\{\\rho\}\_\{\\text\{VPO\}\} and ρ¯GRPO\\bar\{\\rho\}\_\{\\text\{GRPO\}\} on the same prompt set under each domain’s final\-evaluation sampler\. 3\. Best@1616\. Scalarize each response with the GRPO training scalar for that domain \(per\-domain formulas in Table 7; the ArmoRM “overall” dim for UltraFeedback\)\. For each prompt, evaluate the unbiased order\-statistic estimator of 𝔼​\[maxk∈S⁡rk\]\\mathbb\{E\}\[\\max\_\{k\\in S\}r\_\{k\}\] over a uniform 16\-element subset SS of the per\-prompt sample pool, then average over prompts\.`