betaFeedback

WorksComputer Science

Policy Optimization With Multiple Verifiers via Pareto Rankings

Abstract

Reinforcement learning with verifiable rewards (RLVR) has become an important approach to improving the reasoning capabilities of large language models. In tasks such as code generation and instruction following, multiple verifiers evaluate whether a response satisfies different requirements. Their outcomes provide detailed feedback about partial success, yet this feedback is commonly aggregated into a scalar reward for policy optimization. Rewarding only complete success discards distinctions among partial solutions, while counts and weighted sums impose comparisons between responses that satisfy different subsets of requirements. We introduce Partial-Order Likelihood Policy Optimization (POLPO), which learns from the comparisons established by verification without first constructing an aggregate reward. Pareto dominance identifies responses that satisfy additional requirements without losing any already satisfied, while leaving responses with conflicting outcomes incomparable. POLPO extends the listwise likelihood underlying Direct Preference Optimization by maximizing the total probability of all complete rankings consistent with these partial orders. This objective provides supervision from verified improvements even before complete solutions are available, without requiring a prescribed ordering of incomparable responses. Experiments on code generation and instruction following demonstrate improved learning efficiency and higher rates of complete requirement satisfaction compared with scalar-reward training. These results support partial-order likelihood as an effective approach to learning from multiple verifiers.

Introduction

Reinforcement learning with verifiable rewards (RLVR) has become an important approach to improving the reasoning capabilities of large language models (LLMs) [12, 7]. By evaluating model-generated responses automatically, RLVR provides training supervision without requiring annotations for every intermediate reasoning step. In many applications, however, verification involves multiple requirements rather than a single correctness check. A generated program must pass tests covering different inputs and behaviors, while an instruction-following response may need to satisfy several content and formatting constraints [9, 28]. The resulting verification outcomes identify both whether a response succeeds completely and which requirements it satisfies along the way. How to use this information during training is therefore a central question for RLVR with multiple verifiers.

A common approach is to aggregate verification outcomes into a scalar reward and optimize the policy using a policy-gradient method, such as Group Relative Policy Optimization (GRPO) [33]. This aggregation determines which distinctions among responses are available to the learning algorithm. An all-pass reward directly expresses the goal of satisfying every requirement, but assigns the same reward to all partially successful responses. A pass-rate reward provides more graded feedback, but ranks responses by how many checks they pass, regardless of which checks they satisfy. Weighted sums allow different priorities, at the cost of specifying how gains on one requirement compensate for losses on another. Although these rewards can share complete success as their optimum, they induce different comparisons among the partial solutions encountered during training. The challenge is to learn from partial progress without having to prescribe trade-offs between requirements.

Partial orders offer a way to express this distinction. Under Pareto dominance, a response improves on another if it passes every check passed by the other and at least one additional check. Consider three programs y1y_1, y2y_2, y3y_3 with outcomes on three tests given by

c1=(1,1,0),c2=(0,0,1),c3=(1,0,0),(1)c_1 = (1, 1, 0), \qquad c_2 = (0, 0, 1), \qquad c_3 = (1, 0, 0), \tag*{(1)}

where 1 denotes a passed test. Program y1y_1 improves on y3y_3, whereas y2y_2 passes a test that neither of the others passes. Verification therefore establishes

y1≻Py3,y1∥Py2,y2∥Py3,(2)y_1 \succ_P y_3, \qquad y_1 \parallel_P y_2, \qquad y_2 \parallel_P y_3, \tag*{(2)}

where ∥P\parallel_P denotes incomparability. An all-pass reward misses the improvement from y3y_3 to y1y_1, while a pass-rate reward additionally favors y1y_1 over y2y_2. Treating both incomparabilities as scalar reward ties would instead force y1y_1 and y3y_3 to tie, erasing the verified improvement. A partial order preserves that improvement while leaving the trade-off involving y2y_2 unresolved.

To turn these partial orders into a training objective, we introduce Partial-Order Likelihood Policy Optimization (POLPO), illustrated in Figure 1. We use the implicit-reward parameterization of Direct Preference Optimization (DPO), originally proposed for aligning language models with human preferences [30]. Policy-to-reference log probability ratios supply scores for a Plackett–Luce model, which assigns probabilities to rankings of the responses. POLPO maximizes the probability that all observed Pareto comparisons hold, obtained by summing the probabilities of the complete rankings consistent with them. For the partial order in Eq. (2), every position for y2y_2 is allowed as long as y1y_1 precedes y3y_3. The objective thus captures the comparisons established by verification while marginalizing over the ordering decisions that verification leaves unspecified. Our contribution is to bring the established partial-order PL likelihood [15] into online policy learning from multiple verifiers, using Pareto comparisons as supervision and DPO-style scores to connect the likelihood to the response policy.

Figure 1. Overview of POLPO. Responses sampled from the current rollout policy are checked against multiple requirements. In the Pareto-order panel, the solid arrow indicates verified dominance, while dashed connections indicate incomparability. For the verification outcomes in Eq. (1), only y1≻y3y_1 \succ y_3 is established, so three complete rankings are compatible. POLPO minimizes the negative log of their total probability under the PL model parameterized by the policy scores in Eq. (6); the prompt and response group are omitted from the displayed objective for brevity.

This formulation makes the partial order itself the supervision for policy optimization. Its likelihood models the specified comparisons jointly, and differentiating its logarithm yields a weighted sum of response log-probability gradients. Consequently, a group containing a Pareto improvement can provide a learning signal even when no response satisfies every requirement. Although POLPO uses scalar scores internally to parameterize ranking probabilities, it does not require a scalar reward that orders every pair of responses or represents incomparability through equal values. The distinction is between assigning scores within a probabilistic model and prescribing a complete ordering as the training target.

We evaluate whether this use of verification feedback improves learning in controlled program synthesis and practical code-generation tasks. The controlled task isolates the difficulty of learning from partial solutions that satisfy different subsets of requirements: POLPO reaches complete success with fewer sampled programs than training with either all-pass or pass-rate rewards. On MBPP and APPS, POLPO improves both complete program correctness and average test satisfaction under matched rollout budgets, compared with scalar-reward and comparison-based baselines. Training on AceCode further demonstrates transfer to external coding benchmarks. We also examine instruction following, where verifiers check heterogeneous requirements, to study how the approach generalizes beyond execution-based feedback. Together, these experiments investigate partial-order supervision as a way to use multiple verifiers directly in language-model training.

Reinforcement Learning with Multiple Verifiers

In tasks with multiple requirements, a response can satisfy some requirements while violating others. We formalize this verification feedback and describe the scalar rewards commonly used to train policies from it.

Task Setup

Let x∼ρx \sim\rho denote a prompt and πθ(y∣x)\pi_\theta(y \mid x) a language-model policy. Each prompt has K=K(x)≥1K = K(x) \ge1 binary verifiers, with ck(x,y)=1c_k(x,y) = 1 when response yy satisfies requirement kk and otherwise. Their outputs form a verification vector c(x,y)=(c1(x,y),…,cK(x,y))∈{0,1}K\mathbf{c}(x,y) = (c_1(x,y),\ldots,c_K(x,y)) \in\{0,1\}^K. In code generation, each verifier can check a program on a test input; in instruction following, it can check a content or formatting constraint [9, 28].

The task goal is to increase the probability of satisfying all requirements. The individual verifier outcomes also describe partial success: they identify which requirements are already satisfied when a response is not yet fully correct. For a group Y=(y1,…,yN)Y = (y_1,\ldots,y_N) of responses to the same prompt, we write ci=c(x,yi)\mathbf{c}_i = \mathbf{c}(x,y_i). The learning question is how to use these vectors to guide the policy toward complete solutions.

Scalar-Reward Aggregation

A common approach maps the verification vector to a scalar reward r(x,y)=g(c(x,y))r(x,y) = g(\mathbf{c}(x,y)) and optimizes its expectation:

Jreward(θ)=Ex∼ρ, y∼πθ(⋅∣x)[r(x,y)].(3)J_{\mathrm{reward}}(\theta) = \mathbb{E}_{x\sim\rho,\,y\sim\pi_\theta(\cdot\mid x)}[r(x,y)]. \tag*{(3)}

For example, an all-pass reward is one only when every check passes, whereas a pass-rate reward averages the individual outcomes:

rall(x,y)=∏k=1Kck(x,y),rrate(x,y)=1K∑k=1Kck(x,y).(4)r_{\mathrm{all}}(x,y) = \prod_{k=1}^{K} c_k(x,y), \qquad r_{\mathrm{rate}}(x,y) = \frac{1}{K}\sum_{k=1}^{K} c_k(x,y). \tag*{(4)}

An all-pass reward directly expresses complete success, but gives every partially successful response the same reward. A pass-rate reward distinguishes partial solutions by the number of checks passed, while assigning equal rewards to responses that pass different subsets of the same size. A weighted sum, rw(x,y)=∑k=1Kwkck(x,y)r_w(x,y) = \sum_{k=1}^{K} w_k c_k(x,y) with wk>0w_k > 0, permits different priorities but specifies how gains on one check compensate for losses on another. These choices can favor the same fully successful responses while assigning different rewards to the partial solutions encountered during training.

The aggregation determines the verification information supplied to the policy optimizer. GRPO is one representative policy-gradient method that uses this scalar feedback [33]. It samples several responses per prompt and normalizes their rewards within the group to obtain advantages for a policy update. If every response receives the same reward, as with all-pass rewards when no response succeeds completely, the reward-derived advantages vanish. See Appendix § 9.§ 2 for the advantage definition and policy surrogate.

These limitations motivate using the improvements established by verification directly as comparison targets, while leaving tradeoffs between conflicting outcomes unspecified.

Partial-Order Likelihood Policy Optimization

Pareto Comparisons from Multiple Verifiers

To use verification feedback without prescribing trade-offs between requirements, we compare responses through Pareto dominance. A response dominates another if it passes every check passed by the other and at least one additional check. Writing ci=(ci1,…,ciK)c_i = (c_{i1}, \ldots, c_{iK}), we define

yi≻Pyj⟺[∀k, cik≥cjk]∧[∃k, cik>cjk].(5)y_i \succ_{\mathrm{P}} y_j \Longleftrightarrow\left[\forall k,\ c_{ik} \ge c_{jk}\right] \land\left[\exists k,\ c_{ik} > c_{jk}\right]. \tag*{(5)}

When each response passes a check that the other fails, neither dominates the other. This leaves the tradeoff between their satisfied requirements unspecified. Responses with identical verification vectors are also left unordered. For the verification outcomes in Eq. (1), verification establishes only y1≻Py3y_1 \succ_{\mathrm{P}} y_3; both pairs involving y2y_2 remain incomparable, as shown in Eq. (2).

The resulting relation on response indices, RV={(i,j):yi≻Pyj}\mathcal{R}_V = \{(i,j) : y_i \succ_{\mathrm{P}} y_j\}, is a strict partial order: it is irreflexive and transitive. With a single binary verifier, every correct response precedes every incorrect response, with no comparisons within either group. More generally, we write RV=A(c1,…,cN)\mathcal{R}_V = \mathcal{A}(c_1,\ldots,c_N) for a task-specific comparison rule, requiring that its output be a strict partial order; Pareto dominance is the rule used for multi-verifier feedback here. An unordered pair supplies no comparison target and does not require equal model scores. The remaining question is how to turn this partial-order supervision into a policy-training objective.

Learning from the Partial-Order Likelihood

To turn these Pareto comparisons into a policy-training objective, we build on the formulation of Direct Preference Optimization (DPO), which was originally proposed for aligning language models with human preferences [30]. DPO uses an implicit reward derived from the policy to model comparison probabilities. We use this parameterization to model the probability that all comparisons in RV\mathcal{R}_V hold jointly. Given a fixed reference policy πref\pi_{\mathrm{ref}}, we define the response score as

sθ(x,y)=βlog⁡πθ(y∣x)πref(y∣x).(6)s_\theta(x,y) = \beta\log\frac{\pi_\theta(y \mid x)}{\pi_{\mathrm{ref}}(y \mid x)}. \tag*{(6)}

Here β>0\beta> 0 sets the score scale, and both log probabilities sum over response tokens (see Appendix § 9.§ 1). The implicit-reward interpretation follows from KL-regularized reward maximization: holding θ\theta fixed, sθs_\theta is a reward for which πθ\pi_\theta is the optimal policy,

πθ(⋅∣x)=arg⁡max⁡q{Ey∼q[sθ(x,y)]−βDKL(q∥πref(⋅∣x))},(7)\pi_\theta(\cdot\mid x) = \underset{q}{\arg\max}\left\{\mathbb{E}_{y \sim q}[s_\theta(x,y)] - \beta D_{\mathrm{KL}}(q \mathbin\Vert\pi_{\mathrm{ref}}(\cdot\mid x))\right\}, \tag*{(7)}

where qq ranges over distributions on complete responses. Adding a prompt-dependent constant C(x)C(x) to the reward preserves this optimizer and cancels from ranking probabilities. See Appendix § 9.§ 3 for a derivation of this correspondence. POLPO learns the implicit reward through the comparison likelihood below: the verification vectors determine which comparisons are observed, while the policy scores determine their probabilities.

We use the Plackett–Luce (PL) model [21, 27] to define a distribution over rankings from these scores. Write si=sθ(x,yi)s_i = s_\theta(x,y_i) and let σ=(σ1,…,σN)\sigma= (\sigma_1,\ldots,\sigma_N) list responses from best to worst. The probability of this ranking is

pθPL(σ∣x,Y)=∏k=1N−1exp⁡(sσk)∑j=kNexp⁡(sσj).(8)p_\theta^{\mathrm{PL}}(\sigma\mid x,Y) = \prod_{k=1}^{N-1} \frac{\exp(s_{\sigma_k})}{\sum_{j=k}^{N}\exp(s_{\sigma_j})}. \tag*{(8)}

At each position, a response is selected with probability proportional to its exponentiated score among the remaining candidates; the final choice has probability one. Higher implicit rewards therefore make a response more likely to appear earlier in the ranking.

To see how this ranking model can learn from partial comparisons, return to the example in Eq. (2). Verification establishes only y1≻Py3y_1 \succ_{\mathrm{P}} y_3, leaving the position of y2y_2 unspecified. There are exactly three complete rankings consistent with this feedback:

y1≻y2≻y3,y1≻y3≻y2,y2≻y1≻y3.y_1 \succ y_2 \succ y_3,\qquad y_1 \succ y_3 \succ y_2,\qquad y_2 \succ y_1 \succ y_3.

Each ranking satisfies the verified comparison, so learning should increase their total probability without selecting a particular position for y2y_2. Since the three rankings are mutually exclusive, their probabilities add up to the probability that y1y_1 precedes y3y_3:

pθ({(1,3)}∣x,Y)=pθPL((1,2,3)∣x,Y)+pθPL((1,3,2)∣x,Y)+pθPL((2,1,3)∣x,Y)=es1+s3es1+s3+es3.(9)p_\theta(\{(1,3)\}\mid x,Y)=p_\theta^{\mathrm{PL}}((1,2,3)\mid x,Y)+p_\theta^{\mathrm{PL}}((1,3,2)\mid x,Y)+p_\theta^{\mathrm{PL}}((2,1,3)\mid x,Y) =\frac{e^{s_1+s_3}}{e^{s_1+s_3}+e^{s_3}}. \tag*{(9)}

The score of y2y_2 cancels because it participates in no verified comparison. The learning signal therefore depends only on the comparison between y1y_1 and y3y_3. Summing over the allowed positions of y2y_2 preserves the unspecified part of the order, without requiring equal scores for incomparable responses.

For a general partial order RVR_V, we adopt the established Plackett–Luce likelihood obtained by summing over its linear extensions (Liu et al. [15]). These are the complete rankings that satisfy every comparison in RVR_V, and we denote their set by LE(RV)LE(R_V). A ranking belongs to this set exactly when yiy_i precedes yjy_j for every (i,j)∈RV(i,j)\in R_V. POLPO uses this likelihood to train the response policy: verification determines RVR_V, the policy-to-reference scores in Eq. (6) parameterize the ranking probabilities, and training minimizes the negative log-likelihood:

ℓPOLPO(θ;x,Y,RV)=−log⁡pθ(RV∣x,Y)=−log⁡∑σ∈LE(RV)pθPL(σ∣x,Y).(10)\ell_{\mathrm{POLPO}}(\theta;x,Y,R_V)=-\log p_\theta(R_V\mid x,Y)=-\log\sum_{\sigma\in LE(R_V)}p_\theta^{\mathrm{PL}}(\sigma\mid x,Y). \tag*{(10)}

This sum marginalizes over the ordering decisions left unspecified by verification. The scalar scores parameterize the ranking probabilities; the partial order supplies the comparison targets. A complete ranking leaves a single PL term, while an empty comparison relation gives likelihood one and zero loss. The objective recovers DPO for a single comparison (see Appendix § 9.§ 4), but generally differs from a sum of pairwise DPO losses when multiple comparisons are observed (see Appendix § 10.§ 3).

We optimize Eq. (10) with gradient-based updates to the policy parameters, differentiating through the scores in Eq. (6). The likelihood is evaluated exactly using a dynamic program over subsets of responses, avoiding explicit enumeration of complete rankings. In our coding experiments, computing this loss instead of GRPO’s objective adds less than 0.1% to the training time (Appendix § 11.§ 4). In instruction-following settings, the corresponding initial-policy loss overhead is 0.03–0.12% of the reported training-update time. See Appendices § 10 and § 11 for the gradient derivations and likelihood computation, and see Algorithm 1 for the training procedure.

Experiments

We study whether comparisons from multiple verifiers help a policy learn to satisfy every requirement. A controlled program-synthesis task isolates learning from partial solutions, coding tests this idea with a language model, and multi-instruction following extends it to heterogeneous requirements. The main comparison is between POLPO and GRPO with an all-pass reward (GRPO–All) or the fraction of passed checks (GRPO–Rate). These scalar rewards are defined in Eq. (4). Complete success is the primary outcome; average check satisfaction is a complementary measure of partial progress. See Appendix § 12 for the task-specific training and evaluation settings.

Controlled Program Synthesis

We first isolate learning from multiple verifier outcomes using the controlled FizzBuzz synthesis task in Figure 2. For divisors (a,b)(a,b), the target returns Fizz, Buzz, or FizzBuzz according to divisibility and otherwise returns the input itself; standard FizzBuzz uses (a,b)=(3,5)(a,b)=(3,5). A categorical policy constructs a fixed three-branch program by choosing three divisor–output pairs (dj,vj)(d_j,v_j), with dj∈{2,…,M}d_j\in\{2,\ldots,M\} and vj∈{Fizz,Buzz,FizzBuzz}v_j\in\{\text{Fizz},\text{Buzz},\text{FizzBuzz}\}. Each input n∈{1,…,60}n\in\{1,\ldots,60\} defines a binary verifier, giving every sampled program a 60-dimensional verification vector. Because the policy is small, we can compute its exact probability of generating a program that passes all verifiers.

Controlled program-synthesis task diagram showing model output choices, a synthesized program, and verifiers

Figure 2. Controlled program-synthesis task. The trainable policy fills only the highlighted branch slots; the program structure, fallback, target outputs, and 60 input-specific verifiers are fixed. For (a,b)=(3,5)(a,b)=(3,5), the two correct assignments are (15,FizzBuzz)(15,\mathrm{FizzBuzz}) followed by (3,Fizz)(3,\mathrm{Fizz}) and (5,Buzz)(5,\mathrm{Buzz}) in either order.

GRPO–All receives no signal from incomplete programs, whereas GRPO–Rate orders them only by the number of passed inputs. POLPO instead preserves componentwise dominance between their verification vectors. We also include two variants with the same likelihood objective: POLPO–Rate ranks programs by mean verifier satisfaction, leaving equal-rate programs unordered, and POLPO–All places completely correct programs above all others, leaving the rest unordered. These comparisons isolate the choice of supervision while keeping the policy, reference, and optimizer fixed. We test whether this distinction reduces the number of sampled programs needed to reach a 0.9 probability of complete success, varying both the divisor search space MM and the target divisors (a,b)(a,b). See Appendix § 12.§ 1 for the complete protocol.

Results. Across all three target pairs in Figure 3, POLPO reaches 0.9 complete-success probability in all five seeds, using approximately 96,000–100,000 programs on average. Within the full budget of 512,000 programs, GRPO–All and POLPO–All never reach the threshold, while GRPO–Rate reaches it in three, three, and one of the five seeds for (3,5)(3,5), (3,7)(3,7), and (3,11)(3,11), respectively. POLPO–Rate requires more samples than POLPO for the first two targets and fails to reach the threshold in two seeds for (3,11)(3,11). POLPO–All obtains no comparison until a completely correct program is sampled; in smaller search spaces, where such programs are sampled, it closely follows GRPO–All and remains slower than POLPO (Appendix § 13.§ 1). Thus, the choice of comparison supervision matters even with the same likelihood objective. For (3,11)(3,11) at 153,600 programs, GRPO–Rate has 98.07% mean verifier satisfaction but only a 0.03% probability of passing the overlap input n=33n=33, compared with 99.28% for POLPO, averaged across seeds. Thus, a high scalar pass rate can conceal a persistently unsatisfied part of the specification; see Appendix § 13.§ 1 for threshold counts and diagnostic curves.

Figure 3. Complete-success probability for target pairs (3,5)(3,5), (3,7)(3,7), and (3,11)(3,11) at M=60M=60, averaged over five training seeds. All settings retain the same 60 input verifiers and initial policy. Shading shows one sample standard deviation across seeds, clipped to [0,1][0,1]. The horizontal dotted line marks 0.9, and markers indicate the first recorded crossings of the mean curves.

Coding Tasks

Code generation provides a direct setting for learning from multiple verifiers, with each test checking a particular program behavior. We study MBPP, APPS Introductory, and transfer from AceCode to external benchmarks. All methods use the same tests and eight fresh responses per prompt, with one optimizer update per rollout batch. We evaluate final checkpoints using greedy decoding. MBPP results report the mean and standard deviation over three training seeds; APPS Introductory and AceCode results use one training seed. For MBPP, All-pass measures the percentage of problems whose response passes every test (pass@1), while Avg. pass averages the fraction of tests passed within each problem, then equally across problems. See Appendix § 12.§ 2 for the full protocols.

Baselines. GRPO–All and GRPO–Rate provide scalar-reward baselines. On MBPP and APPS, we additionally include REINFORCE++–All and REINFORCE++–Rate (Hu et al., [11]), which use the same rewards with batch-wide normalization to test scalar-reward learning beyond GRPO’s group-relative update. GDPO (Liu et al., [19]) instead normalizes each test’s outcomes separately before aggregation, providing a baseline that explicitly uses individual verifier signals. DPO–Pareto applies the DPO objective (Rafailov et al., [30]) to all strict Pareto dominance pairs, while GraphDPO (Liu et al., [18]) learns local rankings over each response and those it dominates. These two baselines use the same Pareto relation as POLPO, allowing us to compare pairwise and local graph objectives with the likelihood of the entire partial order. For MBPP, we also include POLPO–Rate, which uses the same partial-order likelihood objective and hyperparameters as POLPO but constructs comparisons from mean test-pass rates, leaving equal-rate responses unordered. This ablation isolates the effect of Pareto-based supervision while retaining the likelihood objective. POLPO–All from § 4.1 also retains the likelihood objective but compares only responses that pass every test with the others, whereas GRPO–Pareto uses the Pareto relation without the likelihood objective, taking as its advantages in GRPO’s update the coefficients of POLPO’s gradient at equal scores (Appendix § 12.§ 2).

MBPP and APPS Introductory. MBPP contains short Python programming problems with three tests per problem (Austin et al., [1]). We train Qwen3-0.6B and Qwen3-4B with thinking enabled, using the official training and test splits. POLPO achieves the highest All-pass and Avg. pass at both model sizes (Table 1), improving complete program correctness as well as average test satisfaction. Compared with POLPO–Rate, POLPO improves All-pass from 42.00% to 44.73% and Avg. pass from 48.53% to 52.42% for Qwen3-0.6B. For Qwen3-4B, the corresponding improvements are from 67.40% to 67.93% and from 71.93% to 75.49%. These results suggest that Pareto-based comparisons provide more informative supervision than pass-rate rankings when the likelihood objective and hyperparameters are held fixed. POLPO–All and GRPO–Pareto remain below POLPO and do not exceed GRPO–All or GRPO–Rate on either metric for either model, so POLPO’s improvement appears to require both the Pareto relation and the partial-order likelihood.

Qwen3-0.6BQwen3-4B
MethodAll-passAvg. passAll-passAvg. pass
Initial model30.0034.4062.4066.40
GRPO–All41.47 ± 0.9546.96 ± 1.2366.53 ± 0.3171.49 ± 0.89
GRPO–Rate42.47 ± 0.6448.60 ± 0.5066.60 ± 0.5371.18 ± 0.69
GRPO–Pareto40.53 ± 0.4246.11 ± 0.6066.20 ± 0.3571.00 ± 0.27
REINFORCE++–All40.33 ± 1.6746.89 ± 0.2064.80 ± 1.7469.56 ± 2.05
REINFORCE++–Rate38.47 ± 1.1445.02 ± 1.5864.47 ± 1.1768.87 ± 1.03
GDPO36.47 ± 1.4041.76 ± 1.9966.60 ± 0.5370.98 ± 0.15
GraphDPO41.27 ± 1.4247.40 ± 1.0365.87 ± 0.9969.89 ± 1.61
DPO–Pareto39.73 ± 2.3045.84 ± 2.1266.27 ± 0.7671.07 ± 1.01
POLPO–All39.93 ± 1.7045.24 ± 2.2866.40 ± 0.6970.73 ± 0.24
POLPO–Rate42.00 ± 1.9148.53 ± 1.8467.40 ± 2.1171.93 ± 2.03
POLPO44.73 ± 0.6152.42 ± 1.0067.93 ± 0.8375.49 ± 0.56

Table 1. MBPP test results (%) after five training epochs. Both models use thinking during training and evaluation, with one greedy response per problem. Trained-model results are reported as mean ± standard deviation over three training seeds; the initial model is shown without a seed standard deviation. All-pass measures success on every test (pass@1); Avg. pass averages the fraction of tests passed equally across problems.

APPS provides competition-style programming problems with a variable number of tests (Hendrycks et al., [9]). We train and evaluate Qwen2.5-Coder-1.5B-Instruct on its Introductory tier. POLPO leads both metrics across the compared methods (Table 2), extending the improvement to a setting where the number and coverage of verifiers vary across problems.

MethodAll-passAvg. pass
Initial model20.5035.77
GRPO–All23.6039.05
GRPO–Rate23.3038.95
REINFORCE++–All24.3038.75
REINFORCE++–Rate23.2038.36
GDPO23.4039.13
GraphDPO21.8037.38
DPO–Pareto21.7037.57
POLPO25.9042.67

Table 2. APPS Introductory test results (%) after two training epochs.

AceCode and external evaluation. To assess transfer beyond the training problems, we train the same Qwen2.5-Coder model on AceCode’s hard subset (Zeng et al., 2025) and evaluate on HumanEval and the MBPP subset distributed with EvalPlus (Liu et al., [17]). We report pass@1 on both the original and augmented test suites; this MBPP subset differs from the official test split used above. POLPO achieves the highest pass@1 on all four evaluations, tied with GRPO–All on original HumanEval (Table 3).

HumanEval (164)MBPP (378)
MethodOriginal+Original+
Initial model70.1265.2468.5259.52
GRPO–All78.0570.7373.0262.96
GRPO–Rate76.8370.7373.0262.43
GraphDPO75.6168.9071.1662.17
DPO–Pareto75.6168.9071.1661.90
POLPO78.0572.5674.8764.29

Table 3. External pass@1 (%) after one epoch of AceCode training. + denotes augmented tests.

Multi-Instruction Following

We evaluate learning from multiple verifiable constraints on IFM5, the IF-RLVR data released by Pyatkin et al. [28], MulDimIF [38], and MathIF [6]. IFM5 and

MulDimIF use separate models trained on their respective training splits and evaluated on the corresponding test splits. MathIF additionally evaluates mathematical correctness alongside instruction adherence, using models trained on a separate constraint-augmented MATH dataset. For IFM5 and MulDimIF, the initial model is Qwen3-4B-Instruct-2507. On both datasets, we compare the initial model, GRPO–All, GRPO–Rate, GDPO Liu et al. [19], GraphDPO, DPO–Pareto, and POLPO. The primary metric is the percentage of evaluated prompts whose responses satisfy every constraint. Appendix § 12.§ 3 provides the data splits, evaluation protocols, and training configurations.

IFM5 and MulDimIF. IFM5 groups prompts by their number of constraints, K∈{1,…,5}K \in\{1,\ldots,5\}, whereas MulDimIF defines four difficulty levels based on both the number and variety of constraints [38]. Table 4 shows that POLPO has the highest overall mean on IFM5 (61.3%), closely followed by DPO–Pareto (61.0%). POLPO leads at K=2,3,5K = 2, 3, 5, while DPO–Pareto leads at K=1,4K = 1, 4. On MulDimIF (Table 5), POLPO has the highest overall mean (90.1%) and leads at L1–L3; GraphDPO leads at L4. These are comparisons of means across three training seeds.

MethodK=1K = 1K=2K = 2K=3K = 3K=4K = 4K=5K = 5Overall
Initial model56.129.918.57.43.727.1
GRPO–All90.7 ± 0.465.9 ± 0.545.8 ± 1.128.6 ± 1.119.8 ± 2.656.4 ± 0.8
GRPO–Rate90.1 ± 0.666.0 ± 2.748.7 ± 2.328.8 ± 2.420.5 ± 1.157.1 ± 1.7
GDPO89.1 ± 0.665.8 ± 1.048.3 ± 0.729.4 ± 0.320.7 ± 1.356.8 ± 0.3
GraphDPO91.2 ± 0.569.0 ± 2.552.0 ± 3.431.0 ± 3.024.4 ± 2.759.6 ± 2.2
DPO–Pareto92.4 ± 0.269.3 ± 0.453.4 ± 1.734.6 ± 0.925.2 ± 3.061.0 ± 0.6
POLPO92.1 ± 0.669.7 ± 0.254.9 ± 1.433.8 ± 0.026.2 ± 3.561.3 ± 0.2

Table 4. Complete constraint satisfaction (%) on IFM5. KK counts individual constraints. Trained-model results are reported as mean ± SD over three seeds; the initial model is shown without a seed standard deviation. Bold marks column maxima at the reported precision.

MethodL1L2L3L4Overall
Initial model85.363.748.032.357.3
GRPO–All95.3 ± 0.389.7 ± 0.385.3 ± 0.383.0 ± 1.588.3 ± 0.2
GRPO–Rate95.2 ± 0.789.2 ± 0.886.6 ± 1.385.6 ± 2.489.1 ± 1.0
GDPO95.3 ± 1.289.4 ± 0.885.4 ± 0.484.1 ± 1.388.6 ± 0.5
GraphDPO96.4 ± 0.489.8 ± 1.286.4 ± 1.786.2 ± 0.589.7 ± 0.8
DPO–Pareto96.0 ± 1.289.9 ± 0.586.7 ± 2.083.4 ± 1.189.0 ± 0.4
POLPO96.6 ± 1.290.6 ± 0.787.4 ± 2.085.7 ± 2.190.1 ± 0.7

Table 5. Complete constraint satisfaction (%) on MulDimIF. L1–L4 are difficulty levels. Trained-model results are reported as mean ± SD over three seeds; the initial model is shown without a seed standard deviation. Bold marks column maxima at the reported precision.

MathIF. We further evaluate whether responses can satisfy instruction constraints while solving mathematical problems on MathIF [6]. We evaluate Qwen3-0.6B on 420 MathIF examples with thinking disabled and enabled. HAcc measures complete constraint satisfaction, SAcc the mean fraction of constraints satisfied, and Acc mathematical correctness. Joint, the primary metric, requires both mathematical correctness and satisfaction of every instruction constraint. Among the methods shown in Table 6, POLPO achieves the highest Joint score and instruction adherence in both modes. With thinking disabled, GRPO–All has the highest mathematical accuracy (31.4%), while POLPO has the highest Joint score (21.4%). With thinking enabled, POLPO and DPO–Pareto tie for the highest mathematical accuracy (40.2%); POLPO has the highest Joint score (33.8%), followed by DPO–Pareto (31.9%). Appendices § 12.3.5 and § 13.§ 5 provide details and breakdowns. Appendix § 13.§ 4 examines learning-signal availability and Pareto-order structure in instruction-following rollouts.

MethodThinking disabled HAccThinking disabled SAccThinking disabled AccThinking disabled JointThinking enabled HAccThinking enabled SAccThinking enabled AccThinking enabled Joint
Initial model31.255.713.85.725.240.625.06.2
GRPO–All55.774.331.420.241.946.527.122.6
GRPO–Rate76.086.027.119.370.579.338.830.7
GDPO––––58.668.430.523.3
GraphDPO––––56.463.430.024.8
DPO–Pareto––––72.682.740.231.9
POLPO81.489.726.921.478.186.140.233.8

Table 6. MathIF results (%) on 420 examples by thinking mode, with a 16,384-token evaluation response limit. Bold indicates the best result among the methods shown within each mode. Dashes indicate results not reported for that mode.

Related Work

Multi-verifier RLVR and reward design. Multiple verification outcomes provide training supervision in RLVR tasks, such as instruction following and code generation [28] (Zeng et al. 2025). A central design choice is how to turn partial success into a policy-training signal. Pass-rate rewards provide denser feedback than all-pass rewards, but do not consistently improve complete-solution accuracy in code generation [14]. GDPO normalizes reward components separately before aggregation [19], while VeRPO constructs execution-based rewards that account for partial test success, test difficulty, and test density [36]. In multi-instruction following, Scarcity-Aware Rewards counter exploration biased toward easier instructions by assigning rewards according to how rarely each instruction is satisfied (Zhang et al., 2026b). HiR takes a complementary approach: it reuses partially successful responses by rewriting their prompts to retain the instructions they satisfy (Zhang et al., 2026a). POLPO uses verification outcomes to identify supported comparisons between responses and learns their joint likelihood.

Vector-valued feedback also supports learning across competing objectives. Vector Policy Optimization trains diverse sets of responses that specialize in different reward trade-offs, improving their usefulness for test-time search [2]. ParetoPO targets the trade-off between task accuracy and tool-use efficiency through hypervolume-guided reward modulation and Pareto-ranking-based advantages [13]. In our setting, the goal is to produce a response satisfying all verified requirements. Pareto dominance identifies improvements among partially successful responses without specifying how gains on one requirement should compensate for losses on another.

Preference optimization with structured comparisons. DPO parameterizes comparison probabilities through policy-to-reference log-probability ratios [30]. IRPO and DPO-VP apply DPO-based objectives to correct–incorrect response pairs, establishing a connection between verification and preference learning ([24, 35]). PRO and LiPO extend preference optimization to ranked response lists ([34, 20]). Listwise Policy Optimization also learns from response groups in RLVR, using scalar rewards to construct target distributions for policy projection ([29]). GraphDPO represents response comparisons as a directed acyclic graph and aggregates local choice losses, each contrasting a response with the responses it dominates ([18]). It therefore shares POLPO’s use of structured comparisons without requiring a complete ordering. The distinction lies in the objective: GraphDPO aggregates choice probabilities over overlapping neighborhoods, whereas POLPO optimizes the probability that all observed comparisons hold jointly in a single Plackett–Luce ranking. For general partial orders, these local losses do not constitute a factorization of the joint ranking-event likelihood.

Plackett–Luce models have also been used to learn from supervision that leaves some ranking decisions unspecified. Ma et al. [22] study the marginalized likelihood of ordered partitions, where the order between groups is observed but the order within each group is unknown. In recommendation, Mult-DPO considers comparisons between sets of positive and negative items and derives a tractable multinomial surrogate that upper-bounds the corresponding marginalized PL loss ((Zhu et al., 2026)). POLPO builds on this probabilistic treatment of incomplete rankings. It uses verifier-induced Pareto comparisons to define the likelihood of a general partial order and optimizes that likelihood through policy-derived scores. See Appendix § 14 for additional related work.

Conclusion

We studied how multiple verification outcomes can guide policy learning toward satisfying all requirements. POLPO represents verified improvements as Pareto comparisons and maximizes the probability that these comparisons hold jointly, marginalizing over unspecified ordering decisions. This formulation enables learning from partial success without prescribing trade-offs between requirements. In controlled program synthesis, POLPO reaches a high probability of complete success with fewer sampled programs than training with all-pass or pass-rate rewards. Coding and multi-instruction-following experiments further show improvements in complete requirement satisfaction, with coding gains extending to external benchmarks. These findings support partial-order supervision as an effective approach to learning from multiple verifiers.

Limitation. POLPO’s learning signal depends on the comparisons available within each response group. When no response strictly Pareto-dominates another, the group provides no comparison signal, even if some requirements remain unsatisfied. This can limit learning when sampled responses satisfy different, conflicting subsets of requirements. An important direction for future work is to develop sampling strategies that expose verified improvements and provide more informative comparison supervision.

AI USE STATEMENT

In this work, we used generative AI tools (Claude Code and Codex) to clean and reformat datasets, support qualitative and thematic data analysis, assist in the writing of proofs, formulate mathematical claims, provide critical ingredients for proving mathematical claims, implement methods, and assist with translation. We have not used generative AI tools to generate synthetic datasets, propose or refine hypotheses, design or provide feedback on research methodology or experiments, or interpret results, and the development of theoretical models or conceptual frameworks is not applicable to this work. Additionally, we used generative AI tools to support literature reviews, create scientific figures, assist with drafting parts of the research paper, summarize and analyse existing literature, brainstorm ideas, source and search for information, and edit the research paper to improve readability. We have reviewed all AI-assisted work. The author personally reviewed the AI-assisted mathematical claims and proofs, method implementations, data processing and qualitative analyses, literature summaries, translations, figures, and manuscript text. We take responsibility for the final content of this work, including text, claims or artifacts produced with the aid of generative AI.

Ethics Statement

This work studies a training objective for language models using existing benchmark datasets and programmatically constructed tasks. Automatic verifiers assess only specified requirements and may contain errors; satisfying these checks does not guarantee that generated responses are safe, fair, or appropriate for deployment. Improvements in code generation and instruction following may also facilitate harmful applications. Models trained with this objective therefore require safety evaluation and safeguards appropriate to their intended use.

Reproducibility Statement

Section 2 defines the verification outcomes and scalar rewards. Section 3 defines the comparison rules, policy scores, and training objective. See Appendix § 10 for the derivations and proofs for the likelihood and its gradients. See Appendix § 11 for the training algorithm, exact likelihood computation, and the conditions under which response groups are included in training. See Appendix § 12 for the datasets, preprocessing, training configurations, and evaluation procedures.

Policy Optimization Preliminaries

This appendix specifies the sequence-log-probability convention and GRPO surrogate, derives the correspondence between implicit rewards and KL-regularized optimal policies, and shows how the partial-order likelihood recovers DPO for a single comparison.

Sequence Log Probabilities

For a response of length TiT_i, we use the sequence log probability

log⁡πθ(yi∣x)=∑t=1Tilog⁡πθ(yi,t∣x,yi,<t),(11)\log\pi_\theta(y_i \mid x) = \sum_{t=1}^{T_i} \log\pi_\theta(y_{i,t} \mid x, y_{i,<t}), \tag*{(11)}

where yi,<ty_{i,<t} denotes preceding response tokens. All policy scores in this paper use this sum over tokens.

Group Relative Policy Optimization

GRPO samples a response group from a rollout policy πold\pi_{\mathrm{old}}, a snapshot held fixed during the ensuing updates [33]. Given scalar rewards r=(r1,…,rN)\mathbf{r} = (r_1,\ldots,r_N), it computes

rˉ=1N∑j=1Nrj,A^iGRPO=ri−rˉstd⁡(r)+δ,(12)\bar{r} = \frac{1}{N}\sum_{j=1}^{N} r_j,\qquad\widehat{A}_i^{\mathrm{GRPO}} = \frac{r_i-\bar{r}}{\operatorname{std}(\mathbf{r})+\delta}, \tag*{(12)}

where std⁡(r)\operatorname{std}(\mathbf{r}) is the group standard deviation and δ>0\delta> 0 is a stabilizer. Each token in yiy_i receives the same advantage: responses above the group mean have positive advantages, and those below it have negative advantages. GRPO uses these weights in a clipped policy surrogate, with an additional KL penalty in its original formulation. The surrogate and its gradient are given below.

The policy update uses the token probability ratio

qi,t(θ)=πθ(yi,t∣x,yi,<t)πold(yi,t∣x,yi,<t).(13)q_{i,t}(\theta) = \frac{\pi_\theta(y_{i,t} \mid x,y_{i,<t})}{\pi_{\mathrm{old}}(y_{i,t} \mid x,y_{i,<t})}. \tag*{(13)}

For one response group, the clipped policy surrogate is

JGRPOclip(θ;x,Y)=1N∑i=1N1Ti∑t=1Timin⁡{qi,t(θ)A^iGRPO,clip⁡(qi,t(θ),1−ε,1+ε)A^iGRPO}.(14)\mathcal{J}_{\mathrm{GRPO}}^{\mathrm{clip}}(\theta;x,Y) = \frac{1}{N}\sum_{i=1}^{N}\frac{1}{T_i}\sum_{t=1}^{T_i}\min\left\{q_{i,t}(\theta)\widehat{A}_i^{\mathrm{GRPO}},\operatorname{clip}\left(q_{i,t}(\theta),1-\varepsilon,1+\varepsilon\right)\widehat{A}_i^{\mathrm{GRPO}}\right\}. \tag*{(14)}

where ε>0\varepsilon> 0 controls clipping, as in proximal policy optimization [32]. GRPO maximizes this surrogate averaged over prompts and rollout groups, with an additional KL penalty to a reference policy in the original formulation. The comparison with POLPO concerns the clipped policy term alone (see Appendix § 10.§ 2).

Proposition 1. At θ=θold\theta= \theta_{\mathrm{old}}, the gradient of the clipped surrogate Eq. (14) is

∇θJGRPOclip(θ;x,Y)∣θ=θold=1N∑i=1NA^iGRPOTi∇θlog⁡πθ(yi∣x)∣θ=θold.(15)\left.\nabla_\theta\mathcal{J}_{\mathrm{GRPO}}^{\mathrm{clip}}(\theta;x,Y)\right|_{\theta=\theta_{\mathrm{old}}} = \frac{1}{N}\sum_{i=1}^{N}\frac{\widehat{A}_i^{\mathrm{GRPO}}}{T_i}\left.\nabla_\theta\log\pi_\theta(y_i\mid x)\right|_{\theta=\theta_{\mathrm{old}}}. \tag*{(15)}

Proof. The advantages A^iGRPO\widehat{A}_i^{\mathrm{GRPO}} depend only on the rewards and are constants. At θ=θold\theta= \theta_{\mathrm{old}} every ratio equals qi,t(θold)=1q_{i,t}(\theta_{\mathrm{old}}) = 1, which lies strictly inside the clipping interval [1−ε,1+ε][1-\varepsilon,1+\varepsilon]. In a neighborhood of this point the clipping function is the identity, so both arguments of the minimum in Eq. (14) coincide with qi,t(θ)A^iGRPOq_{i,t}(\theta)\widehat{A}_i^{\mathrm{GRPO}}, and the surrogate is differentiable with

∇θ[qi,t(θ)A^iGRPO]=A^iGRPOqi,t(θ)∇θlog⁡πθ(yi,t∣x,yi,<t).\nabla_\theta\left[q_{i,t}(\theta)\widehat{A}_i^{\mathrm{GRPO}}\right] = \widehat{A}_i^{\mathrm{GRPO}}q_{i,t}(\theta)\nabla_\theta\log\pi_\theta(y_{i,t}\mid x,y_{i,<t}).

Evaluating at θold\theta_{\mathrm{old}} sets qi,t=1q_{i,t}=1. Summing over tokens and using the sequence log probability Eq. (11) gives 1N∑i(A^iGRPOTi)∇θlog⁡πθ(yi∣x)\frac{1}{N}\sum_i\left(\frac{\widehat{A}_i^{\mathrm{GRPO}}}{T_i}\right)\nabla_\theta\log\pi_\theta(y_i\mid x) at θold\theta_{\mathrm{old}}, which is Eq. (15).

Implicit Rewards and KL-Regularized Optimal Policies

For a fixed prompt xx and reward function r(x,y)r(x,y), consider the KL-regularized objective

Jr(q∣x)=Ey∼q[r(x,y)]−βDKL(q∥πref(⋅∣x)),(16)\mathcal{J}_{r}(q \mid x) = \mathbb{E}_{y\sim q}[r(x,y)] - \beta D_{\mathrm{KL}}(q \parallel\pi_{\mathrm{ref}}(\cdot\mid x)), \tag*{(16)}

with β>0\beta> 0. The distributions are over complete responses, rather than just the sampled group YY. Assume that the reference and policies under consideration have common positive support, the partition function below is finite, and the displayed expectations and divergences are finite. Define

πr∗(y∣x)=πref(y∣x)exp⁡(r(x,y)/β)Zr(x),Zr(x)=∑yπref(y∣x)exp⁡(r(x,y)/β).(17)\pi_r^*(y \mid x) = \frac{\pi_{\mathrm{ref}}(y \mid x)\exp(r(x,y)/\beta)}{Z_r(x)}, \qquad Z_r(x) = \sum_y \pi_{\mathrm{ref}}(y \mid x)\exp(r(x,y)/\beta). \tag*{(17)}

Substituting this expression into Eq. (16) gives

Jr(q∣x)=βlog⁡Zr(x)−βDKL(q∥πr∗(⋅∣x)).(18)\mathcal{J}_r(q \mid x) = \beta\log Z_r(x) - \beta D_{\mathrm{KL}}(q \parallel\pi_r^*(\cdot\mid x)). \tag*{(18)}

The reward is fixed while optimizing over qq, so Zr(x)Z_r(x) is constant. Nonnegativity of KL divergence shows that the unique maximizing response distribution is q=πr∗(⋅∣x)q = \pi_r^*(\cdot\mid x). Rearranging Eq. (17) yields the inverse reward parameterization used in DPO (Rafailov et al., [30]):

r(x,y)=βlog⁡πr∗(y∣x)πref(y∣x)+βlog⁡Zr(x).(19)r(x,y) = \beta\log\frac{\pi_r^*(y \mid x)}{\pi_{\mathrm{ref}}(y \mid x)} + \beta\log Z_r(x). \tag*{(19)}

The final term depends only on the prompt and cancels from comparison probabilities.

Conversely, fix θ\theta and set rθimp(x,y)=sθ(x,y)+C(x)r_\theta^{\mathrm{imp}}(x,y) = s_\theta(x,y) + C(x), using the score in Eq. (6) and any finite prompt-dependent C(x)C(x). Then Zrθimp(x)=exp⁡(C(x)/β)Z_{r_\theta^{\mathrm{imp}}}(x) = \exp(C(x)/\beta) and πrθimp∗=πθ\pi_{r_\theta^{\mathrm{imp}}}^* = \pi_\theta, since ∑yπθ(y∣x)=1\sum_y \pi_\theta(y \mid x) = 1. Equivalently,

Jrθimp(q∣x)=C(x)−βDKL(q∥πθ(⋅∣x)),(20)\mathcal{J}_{r_\theta^{\mathrm{imp}}}(q \mid x) = C(x) - \beta D_{\mathrm{KL}}(q \parallel\pi_\theta(\cdot\mid x)), \tag*{(20)}

which proves Eq. (7) by taking C(x)=0C(x) = 0. This establishes the policy–reward correspondence for each fixed θ\theta. During POLPO training, θ\theta changes through comparison-likelihood optimization, so the associated implicit reward changes with it; the identity does not assert maximization of a fixed scalar verifier reward. Rescaling the reward and KL coefficient by the same positive factor preserves the optimal policy. Taking C(x)=0C(x) = 0 and dividing both by β\beta gives an equivalent unit-KL interpretation with reward log⁡(πθ/πref)\log(\pi_\theta/\pi_{\mathrm{ref}}); the PL likelihood continues to use the score sθ=βlog⁡(πθ/πref)s_\theta= \beta\log(\pi_\theta/\pi_{\mathrm{ref}}).

Connection to Direct Preference Optimization

For a group containing two responses Y=(yw,yl)Y = (y_w, y_l) and the comparison yw≻yly_w \succ y_l, the partial-order event contains only the ranking that places ywy_w first. Writing sw=sθ(x,yw)s_w = s_\theta(x,y_w) and sl=sθ(x,yl)s_l = s_\theta(x,y_l) using Eq. (6), its PL probability is the Bradley–Terry comparison probability (Bradley & Terry, [3]):

pθpair(yw≻yl∣x)=eswesw+esl=11+exp⁡[−(sw−sl)].(21)p_\theta^{\mathrm{pair}}(y_w \succ y_l \mid x) = \frac{e^{s_w}}{e^{s_w} + e^{s_l}} = \frac{1}{1 + \exp[-(s_w-s_l)]}. \tag*{(21)}

Taking the negative logarithm gives the DPO loss (Rafailov et al., [30]),

ℓDPO(θ;x,yw,yl)=−log⁡pθpair(yw≻yl∣x)=log⁡(1+exp⁡[−(sw−sl)]),(22)\ell_{\mathrm{DPO}}(\theta; x,y_w,y_l) = -\log p_\theta^{\mathrm{pair}}(y_w \succ y_l \mid x) = \log(1 + \exp[-(s_w-s_l)]), \tag*{(22)}

where sw−sl=β[log⁡(πθ(yw∣x)/πref(yw∣x))−log⁡(πθ(yl∣x)/πref(yl∣x))]s_w - s_l = \beta[\log(\pi_\theta(y_w \mid x)/\pi_{\mathrm{ref}}(y_w \mid x)) - \log(\pi_\theta(y_l \mid x)/\pi_{\mathrm{ref}}(y_l \mid x))]. A prompt-dependent additive constant in the implicit reward cancels from this difference and, more generally, from every PL choice probability. Thus the score in Eq. (6) can be used directly in the likelihood.

The same pairwise likelihood results when a larger response group has only one specified comparison, by Lemma 2. If every position is specified, the partial-order likelihood contains a single PL term and recovers the listwise extension of DPO (Rafailov et al., [30], Appendix § 9.§ 3). Verification-derived comparison targets, such as correct–incorrect response pairs used by DPO-based reasoning methods (Pang et al., [24]; Tu et al., [35]), fit within this likelihood formulation.

Derivations and Proofs

This appendix collects the derivations behind § 3. Throughout, Y=(y1,…,yN)Y=(y_1,\ldots,y_N) is a fixed response group, si=sθ(x,yi)s_i=s_\theta(x,y_i) are the policy scores in Eq. (6), wi=esiw_i=e^{s_i}, and RVR_V is a strict partial order on {1,…,N}\{1,\ldots,N\} with linear extensions LE⁡(RV)\operatorname{LE}(R_V). For a complete ranking σ\sigma, Rk(σ)={σk,…,σN}R_k(\sigma)=\{\sigma_k,\ldots,\sigma_N\} denotes the candidates remaining at position kk, and

pi(k)(σ)=wi∑j∈Rk(σ)wjfor i∈Rk(σ)(23)p_i^{(k)}(\sigma)=\frac{w_i}{\sum_{j\in R_k(\sigma)}w_j}\qquad\text{for }i\in R_k(\sigma) \tag*{(23)}

is the probability of choosing yiy_i at position kk given the remaining candidates. Set pi(k)(σ)=0p_i^{(k)}(\sigma)=0 for i∉Rk(σ)i\notin R_k(\sigma).

Gradient of the Plackett–Luce Log-Likelihood

Proposition 2 (Complete-ranking coefficients). For every complete ranking σ\sigma and every i∈{1,…,N}i\in\{1,\ldots,N\},

ai(σ)=∂∂silog⁡pθPL(σ∣x,Y)=∑k=1N−1[1{i=σk}−1{i∈Rk(σ)}pi(k)(σ)],(24)a_i(\sigma)=\frac{\partial}{\partial s_i}\log p_\theta^{\mathrm{PL}}(\sigma\mid x,Y)=\sum_{k=1}^{N-1}\left[1\{i=\sigma_k\}-1\{i\in R_k(\sigma)\}p_i^{(k)}(\sigma)\right], \tag*{(24)}

where 1{⋅}1\{\cdot\} is the indicator function. Moreover, ∑i=1Nai(σ)=0\sum_{i=1}^{N}a_i(\sigma)=0.

Proof. By Eq. (8), log⁡pθPL(σ∣x,Y)=∑k=1N−1[sσk−log⁡∑j∈Rk(σ)esj]\log p_\theta^{\mathrm{PL}}(\sigma\mid x,Y)=\sum_{k=1}^{N-1}\left[s_{\sigma_k}-\log\sum_{j\in R_k(\sigma)}e^{s_j}\right]. The derivative of the kk-th term with respect to sis_i is 1{i=σk}1\{i=\sigma_k\} from the first part and −1{i∈Rk(σ)}esi/∑j∈Rk(σ)esj-1\{i\in R_k(\sigma)\}e^{s_i}/\sum_{j\in R_k(\sigma)}e^{s_j} from the log-partition function, which gives the stated expression. Summing over ii, position kk contributes 1−∑i∈Rk(σ)pi(k)(σ)=01-\sum_{i\in R_k(\sigma)}p_i^{(k)}(\sigma)=0, because the choice probabilities at each position sum to one over the remaining candidates.

Since i=σki=\sigma_k implies i∈Rm(σ)i\in R_m(\sigma) exactly for m≤km\leq k, the coefficient of the response at position kk can also be written as aσk(σ)=1−∑m=1kpσk(m)(σ)a_{\sigma_k}(\sigma)=1-\sum_{m=1}^{k}p_{\sigma_k}^{(m)}(\sigma) for k≤N−1k\leq N-1 and aσN(σ)=−∑m=1N−1pσN(m)(σ)a_{\sigma_N}(\sigma)=-\sum_{m=1}^{N-1}p_{\sigma_N}^{(m)}(\sigma) for the last response. For k<Nk<N, the coefficient is positive exactly when ∑m=1kpσk(m)(σ)<1\sum_{m=1}^{k}p_{\sigma_k}^{(m)}(\sigma)<1, zero when this sum equals one, and negative when it exceeds one. For positive weights and N≥2N\geq2, the final response has a strictly negative coefficient. The sum here combines choice probabilities from different positions; it is not a probability that the response has already been selected.

Gradient of the Partial-Order Likelihood

Proposition 3 (Partial-order coefficients). Let pθ(RV∣x,Y)=∑σ∈LE⁡(RV)pθPL(σ∣x,Y)p_\theta(R_V\mid x,Y)=\sum_{\sigma\in\operatorname{LE}(R_V)}p_\theta^{\mathrm{PL}}(\sigma\mid x,Y) as in Eq. (10). Then

Airank=∂∂silog⁡pθ(RV∣x,Y)=∑σ∈LE⁡(RV)ωθ(σ)ai(σ),ωθ(σ)=pθPL(σ∣x,Y)pθ(RV∣x,Y),(25)A_i^{\mathrm{rank}}=\frac{\partial}{\partial s_i}\log p_\theta(R_V\mid x,Y)=\sum_{\sigma\in\operatorname{LE}(R_V)}\omega_\theta(\sigma)a_i(\sigma),\qquad\omega_\theta(\sigma)=\frac{p_\theta^{\mathrm{PL}}(\sigma\mid x,Y)}{p_\theta(R_V\mid x,Y)}, \tag*{(25)}

where the weights ωθ(σ)\omega_\theta(\sigma) are the conditional probabilities of the compatible rankings given that the comparisons hold and sum to one. Consequently, ∑i=1NAirank=0\sum_{i=1}^{N}A_i^{\mathrm{rank}}=0, and

∇θlog⁡pθ(RV∣x,Y)=β∑i=1NAirank∇θlog⁡πθ(yi∣x).(26)\nabla_\theta\log p_\theta(R_V\mid x,Y)=\beta\sum_{i=1}^{N}A_i^{\mathrm{rank}}\nabla_\theta\log\pi_\theta(y_i\mid x). \tag*{(26)}

Proof. The set LE⁡(RV)\operatorname{LE}(R_V) does not depend on θ\theta, so ∂sipθ(RV∣x,Y)=∑σ∈LE⁡(RV)∂sipθPL(σ∣x,Y)=∑σ∈LE⁡(RV)pθPL(σ∣x,Y)ai(σ)\partial_{s_i}p_\theta(R_V\mid x,Y)=\sum_{\sigma\in\operatorname{LE}(R_V)}\partial_{s_i}p_\theta^{\mathrm{PL}}(\sigma\mid x,Y)=\sum_{\sigma\in\operatorname{LE}(R_V)}p_\theta^{\mathrm{PL}}(\sigma\mid x,Y)a_i(\sigma), using ∂sipθPL=pθPL∂silog⁡pθPL\partial_{s_i}p_\theta^{\mathrm{PL}}=p_\theta^{\mathrm{PL}}\partial_{s_i}\log p_\theta^{\mathrm{PL}}. Dividing by pθ(RV∣x,Y)p_\theta(R_V\mid x,Y) gives the mixture form, and the weights sum to one by definition. The zero-sum property follows from Proposition 2: ∑iAirank=∑σωθ(σ)∑iai(σ)=0\sum_i A_i^{\mathrm{rank}}=\sum_\sigma\omega_\theta(\sigma)\sum_i a_i(\sigma)=0. For the policy gradient, the reference policy is fixed, so ∇θsi=∇θlog⁡πθ(yi∣x)\nabla_\theta s_i=\nabla_\theta\log\pi_\theta(y_i\mid x) by Eq. (6), and the chain rule gives ∇θlog⁡pθ(RV∣x,Y)=∑i(∂silog⁡pθ(RV∣x,Y))∇θsi\nabla_\theta\log p_\theta(R_V\mid x,Y)=\sum_i(\partial_{s_i}\log p_\theta(R_V\mid x,Y))\nabla_\theta s_i.

The likelihood thus supplies a coefficient for each response gradient, depending on both the verified comparisons and the current policy scores. These coefficients are not standardized advantages and need not have unit variance; their scale comes from the likelihood. Their zero-sum property also follows from the invariance of ranking probabilities to a common shift of all scores.

Connection to GRPO updates. Both the POLPO gradient in Eq. (26) and the GRPO surrogate gradient at θ=θold\theta= \theta_{\mathrm{old}} in Eq. (15) weight response gradients using relative information from the group. GRPO derives advantages from scalar rewards; POLPO derives its coefficients from the joint comparison likelihood. This is a connection between update structures, not an equivalence of objectives. GRPO averages token contributions and uses clipping, whereas POLPO uses sequence log probabilities and directly optimizes the likelihood, with no additional explicit KL term in Eq. (10). See Appendix A.2 for the full GRPO surrogate and the conditions for Eq. (15).

Marginalization over Unspecified Positions

Two facts about the Plackett–Luce model explain the marginalization in Eq. (9) and the additional example below. The first is that the probabilities of all orderings of a set of candidates sum to one. The second is that the marginal probability that one candidate precedes another has the Bradley–Terry form.

Lemma 1 (Completions sum to one). For any nonempty R⊂{1,…,N}R \subset\{1,\ldots,N\},

∑τ∏k=1∣R∣−1wτk∑m=k∣R∣wτm=1,\sum_{\tau}\prod_{k=1}^{|R|-1}\frac{w_{\tau_k}}{\sum_{m=k}^{|R|}w_{\tau_m}}=1,

where the sum ranges over all orderings τ=(τ1,…,τ∣R∣)\tau=(\tau_1,\ldots,\tau_{|R|}) of RR.

Proof. By induction on ∣R∣|R|. For ∣R∣=1|R|=1 the product is empty and equals one. For ∣R∣>1|R|>1, group the orderings by their first element i∈Ri\in R: the sum equals ∑i∈R(wi/∑j∈Rwj)S(R∖{i})\sum_{i\in R}(w_i/\sum_{j\in R}w_j)S(R\setminus\{i\}), where S(R∖{i})S(R\setminus\{i\}) denotes the same sum over orderings of R∖{i}R\setminus\{i\} and equals one by the induction hypothesis. The remaining factor is ∑i∈Rwi/∑j∈Rwj=1\sum_{i\in R}w_i/\sum_{j\in R}w_j=1.

Lemma 2 (Pairwise marginal). For distinct ii and jj, the total Plackett–Luce probability of the complete rankings in which yiy_i precedes yjy_j is wi/(wi+wj)w_i/(w_i+w_j).

Proof. We use the standard sampling representation of the Plackett–Luce model. Draw independent exponential random variables E1,…,ENE_1,\ldots,E_N with rates w1,…,wNw_1,\ldots,w_N and rank the candidates by increasing EmE_m. The minimum is attained by candidate mm with probability wm/∑m′wm′w_m/\sum_{m'}w_{m'}. Conditional on the minimum time and its attaining candidate, the memoryless property makes the residual waiting times of the remaining candidates independent exponentials with their original rates. Iterating over positions gives exactly the sequential choice probabilities in Eq. (8), so the induced distribution over rankings is the Plackett–Luce model. Under this representation, yiy_i precedes yjy_j if and only if Ei<EjE_i<E_j, which has probability wi/(wi+wj)w_i/(w_i+w_j).

Corollary 1 (Special cases of the partial-rank likelihood). (i) If verification establishes no comparisons, then LE⁡(RV)\operatorname{LE}(\mathcal{R}_V) contains every ranking, pθ(RV∣x,Y)=1p_\theta(\mathcal{R}_V\mid x,Y)=1, and the loss and its gradient vanish. (ii) If y1y_1 is the only correct response among NN responses and RV={(1,j):j≠1}\mathcal{R}_V=\{(1,j):j\ne1\}, then pθ(RV∣x,Y)=w1/∑j=1Nwjp_\theta(\mathcal{R}_V\mid x,Y)=w_1/\sum_{j=1}^{N}w_j. (iii) If RV={(1,3)}\mathcal{R}_V=\{(1,3)\}, then pθ(RV∣x,Y)=w1/(w1+w3)p_\theta(\mathcal{R}_V\mid x,Y)=w_1/(w_1+w_3), as in Eq. (9), so the loss equals the DPO loss between y1y_1 and y3y_3.

Proof. (i) is Lemma 1 with R={1,…,N}R=\{1,\ldots,N\}. For (ii), every compatible ranking selects y1y_1 first, which has probability w1/∑jwjw_1/\sum_j w_j, and the orderings of the remaining responses that follow sum to one by Lemma 1. (iii) is Lemma 2 with i=1i=1 and j=3j=3.

Learning comparisons jointly. With multiple comparisons, the likelihood accounts for their dependence through shared responses. For example, suppose y1y_1 is correct and y2,y3y_2, y_3 are incorrect, giving RV={(1,2),(1,3)}R_V = \{(1,2),(1,3)\}. The two compatible rankings are (1,2,3)(1,2,3) and (1,3,2)(1,3,2): both place y1y_1 first, while leaving the incorrect responses unordered. Their total probability is

pθ(RV∣x,Y)=es1es1+es2+es3.(27)p_\theta(R_V \mid x,Y) = \frac{e^{s_1}}{e^{s_1}+e^{s_2}+e^{s_3}}. \tag*{(27)}

Once y1y_1 is selected first, the conditional probabilities of the two remaining orderings sum to one. At equal scores, the probability that y1y_1 precedes both other responses is 1/31/3. Each pairwise comparison has probability 1/21/2, so multiplying the two comparison probabilities as if they were independent would instead give 1/41/4. The negative log-likelihood of the joint event therefore differs from the sum of the pairwise comparison losses.

Example policy updates. In Eq. (27), write pi=esi/∑j=13esjp_i = e^{s_i}/\sum_{j=1}^{3} e^{s_j}. The coefficients are (A1rank,A2rank,A3rank)=(1−p1,−p2,−p3)(A_1^{\mathrm{rank}}, A_2^{\mathrm{rank}}, A_3^{\mathrm{rank}}) = (1-p_1, -p_2, -p_3). At equal scores, they are (2/3,−1/3,−1/3)(2/3,-1/3,-1/3), favoring the correct response relative to both incorrect alternatives. As the model assigns greater probability to placing the correct response first, its positive coefficient decreases. Both incorrect responses receive a signal because each is compared with the correct response; no comparison between them is needed. By contrast, y2y_2 in Eq. (9) has zero score derivative because it participates in no comparison. A zero score derivative does not prevent its response probability from changing through shared policy parameters.

Computing the Partial-Order Likelihood

In the binary-correctness example in Eq. (27), we did not need to evaluate both complete rankings separately. Once the correct response was selected first, every order of the remaining responses was acceptable, and their probabilities summed to one. The same principle gives a recurrence for general partial-order likelihoods: many compatible rankings share the same remaining candidates, so their possible continuations can be handled together.

Let R⊆{1,…,N}R \subseteq\{1,\ldots,N\} be the remaining candidate indices, write wi=esiw_i=e^{s_i}, and let H(R)H(R) be the probability of completing the ranking without violating a comparison. A candidate is eligible for the next position when none of its required predecessors remain. Denote these candidates by

Max⁡RV(R)={i∈R: there is no j∈R with (j,i)∈RV}.(28)\operatorname{Max}_{R_V}(R)=\{i\in R:\text{ there is no }j\in R\text{ with }(j,i)\in R_V\}. \tag*{(28)}

The likelihood can be computed recursively by adding the probabilities of the eligible next choices and their valid continuations:

H(∅)=1,H(R)=∑i∈Max⁡RV(R)wi∑j∈RwjH(R∖{i}).(29)H(\varnothing)=1,\qquad H(R)=\sum_{i\in\operatorname{Max}_{R_V}(R)}\frac{w_i}{\sum_{j\in R}w_j}H(R\setminus\{i\}). \tag*{(29)}

The desired probability is pθ(RV∣x,Y)=H({1,…,N})p_\theta(R_V\mid x,Y)=H(\{1,\ldots,N\}). In the binary example, only y1y_1 is eligible initially, and H({2,3})=1H(\{2,3\})=1 after it is selected. The recurrence therefore gives H({1,2,3})=w1/(w1+w2+w3)H(\{1,2,3\})=w_1/(w_1+w_2+w_3), as before. This also explains why the denominator must include all remaining candidates. Normalizing over the eligible set {1}\{1\} alone would always give probability one and remove the learning signal. The PL model can choose an incorrect first response; the likelihood measures the probability that it avoids doing so.

Dynamic programming stores each remaining-set value once, avoiding explicit enumeration of complete rankings. There are at most 2N2^N subset states and at most NN outgoing transitions per state, so the general computation can remain exponential. The number of reachable states depends on the comparison structure. Evaluating the recurrence in log space with log-sum-exp operations also allows differentiation through the policy scores without listing the compatible rankings or their conditional probabilities.

For R⊆{1,…,N}R\subseteq\{1,\ldots,N\}, let LE⁡R(RV)\operatorname{LE}_R(R_V) be the set of orderings of RR that satisfy every comparison (i,j)∈RV(i,j)\in R_V with i,j∈Ri,j\in R, and define

H⋆(R)=∑τ∈LE⁡R(RV)∏k=1∣R∣−1wτk∑m=k∣R∣wτm,H⋆(∅)=1.(30)H^{\star}(R)=\sum_{\tau\in\operatorname{LE}_R(R_V)}\prod_{k=1}^{|R|-1}\frac{w_{\tau_k}}{\sum_{m=k}^{|R|}w_{\tau_m}},\qquad H^{\star}(\varnothing)=1. \tag*{(30)}

By Eq. (10), H⋆({1,…,N})=pθ(RV∣x,Y)H^{\star}(\{1,\ldots,N\})=p_\theta(R_V\mid x,Y).

Proposition 4 (Recurrence). H⋆H^\star satisfies the recurrence Eq. (29). Hence the value H({1,…,N})H(\{1,\ldots,N\}) computed by Eq. (29) equals pθ(RV∣x,Y)p_\theta(\mathcal{R}_V \mid x,Y).

Proof. Fix a nonempty RR. An ordering τ\tau of RR satisfies the comparisons within RR if and only if its first element has no predecessor in RR, that is, τ1∈Max⁡RV(R)\tau_1 \in\operatorname{Max}_{\mathcal{R}_V}(R), and the remaining ordering (τ2,…,τ∣R∣)(\tau_2,\ldots,\tau_{|R|}) satisfies the comparisons within R∖{τ1}R \setminus\{\tau_1\}. Grouping the orderings in Eq. (30) by their first element therefore gives

H⋆(R)=∑i∈Max⁡RV(R)wi∑j∈RwjH⋆(R∖{i}),H^\star(R)=\sum_{i\in\operatorname{Max}_{\mathcal{R}_V}(R)}\frac{w_i}{\sum_{j\in R}w_j}H^\star(R\setminus\{i\}),

which is Eq. (29). Both HH and H⋆H^\star equal one on the empty set and satisfy the same recurrence, so they agree on every subset by induction on ∣R∣|R|.

The subsets reachable from {1,…,N}\{1,\ldots,N\} by repeatedly removing eligible candidates are exactly the subsets RR that are closed under the relation in the following sense: if i∈Ri\in R and (i,j)∈RV(i,j)\in\mathcal{R}_V, then j∈Rj\in R. These subsets are the order ideals under the convention that a preferred candidate is greater, and the eligible candidates of an ideal are its maximal elements. A top-down implementation that memoizes reachable states and expands every nonempty state therefore visits one state per order ideal, including the empty set. This count equals 2N2^N only when RV\mathcal{R}_V is empty, equals N+1N+1 when RV\mathcal{R}_V is a complete ranking, and equals 1+∑g=1M(2∣Gg∣−1)1+\sum_{g=1}^{M}(2^{|G_g|}-1) for an ordered partition G1≻⋯≻GMG_1\succ\cdots\succ G_M. Early termination when no comparisons remain can reduce the number of evaluated states. These are counts of reachable recurrence states. The batched evaluation instead evaluates all subsets within each series component, grouped by cardinality (see Appendix § 11.§ 3).

Ordered Partitions

Let RV=G1≻⋯≻GM\mathcal{R}_V=G_1\succ\cdots\succ G_M be an ordered partition of {1,…,N}\{1,\ldots,N\}: every candidate in an earlier block precedes every candidate in a later block, and no ordering is specified within a block. Binary correctness and graded scalar feedback induce this structure. General Pareto relations need not do so. Write W>g=∑h>g∑j∈GhwjW_{>g}=\sum_{h>g}\sum_{j\in G_h}w_j for the total weight of the blocks below GgG_g, with W>M=0W_{>M}=0. For S⊆GgS\subseteq G_g, define

Fg(S)=∑τ∏k=1∣S∣wτk∑m=k∣S∣wτm+W>g,Fg(∅)=1,(31)F_g(S)=\sum_{\tau}\prod_{k=1}^{|S|}\frac{w_{\tau_k}}{\sum_{m=k}^{|S|}w_{\tau_m}+W_{>g}},\qquad F_g(\varnothing)=1, \tag*{(31)}

where the sum ranges over all orderings τ\tau of SS. Thus Fg(Gg)F_g(G_g) is the probability that the sequential choice process selects every candidate in GgG_g before any candidate in a lower block, given that all higher blocks have already been selected.

Proposition 5 (Block factorization). The likelihood factorizes as

pθ(RV∣x,Y)=∏g=1M−1Fg(Gg).(32)p_\theta(\mathcal{R}_V\mid x,Y)=\prod_{g=1}^{M-1}F_g(G_g). \tag*{(32)}

Each factor satisfies

Fg(S)=∑i∈Swi∑j∈Swj+W>gFg(S∖{i}).(33)F_g(S)=\sum_{i\in S}\frac{w_i}{\sum_{j\in S}w_j+W_{>g}}F_g(S\setminus\{i\}). \tag*{(33)}

Once the block weights W>gW_{>g} are computed, evaluating all factors by this recurrence takes O(∑g=1M−1∣Gg∣2∣Gg∣)O\left(\sum_{g=1}^{M-1}|G_g|2^{|G_g|}\right) arithmetic operations.

Proof. The linear extensions of an ordered partition are the concatenations σ=(τ(1),…,τ(M))\sigma=(\tau^{(1)},\ldots,\tau^{(M)}) of arbitrary orderings τ(g)\tau^{(g)} of the blocks GgG_g. When position kk of σ\sigma lies in block gg, the remaining candidates are the unselected members of GgG_g together with all lower blocks, so the denominator of the choice probability in (8) is the weight of the unselected members of GgG_g plus W>gW_{>g}. The product over positions therefore factorizes over blocks, and summing over the orderings of each block independently gives ∏g=1MFg(Gg)\prod_{g=1}^{M}F_g(G_g). For the final block, W>M=0W_{>M}=0 and FM(GM)=1F_M(G_M)=1 by Lemma 1. The recurrence follows by grouping the orderings of SS by their first element, as in Proposition 4. The cost follows because block gg has 2∣Gg∣2^{|G_g|} subset states with at most ∣Gg∣|G_g| transitions each.

Extension to series components. The same factorization applies when the ordered blocks retain internal comparisons. Form the undirected incomparability graph of RV\mathcal{R}_V, with an edge between distinct candidates ii and jj exactly when neither (i,j)(i,j) nor (j,i)(j,i) belongs to RV\mathcal{R}_V. Its connected components can be ordered as C1≻⋯≻CMC_1 \succ\cdots\succ C_M, meaning that every candidate in CgC_g precedes every candidate in ChC_h whenever g<hg < h. Unlike tie blocks, a component need not be an antichain: candidates linked by a path of incomparable pairs may still be comparable to one another. The original comparisons within each component must therefore be retained. For this decomposition, write W>g=∑h>g∑j∈ChwjW_{>g} = \sum_{h>g} \sum_{j\in C_h} w_j and let RV∣Cg\mathcal{R}_V|_{C_g} be the restriction of RV\mathcal{R}_V to CgC_g.

Proposition 6 (Series-component factorization). For S⊆CgS \subseteq C_g, start with SS and all lower components as the remaining candidates. Let Qg(S)Q_g(S) be the probability of selecting all candidates in SS, in an order satisfying every comparison in RV\mathcal{R}_V whose endpoints both lie in SS, before selecting any candidate in a lower component. Then

Qg(∅)=1,Qg(S)=∑i∈Max⁡RV∣Cg(S)wi∑j∈Swj+W>gQg(S∖{i}),(34)Q_g(\varnothing)=1,\qquad Q_g(S)=\sum_{i\in\operatorname{Max}_{\mathcal{R}_V|_{C_g}}(S)}\frac{w_i}{\sum_{j\in S}w_j+W_{>g}}Q_g(S\setminus\{i\}), \tag*{(34)}

and

pθ(RV∣x,Y)=∏g=1MQg(Cg).(35)p_\theta(\mathcal{R}_V\mid x,Y)=\prod_{g=1}^{M}Q_g(C_g). \tag*{(35)}

For an ordered partition, the components are the tie blocks and Qg=FgQ_g=F_g. The final factor is one if the final component is an antichain. If it contains an internal comparison, its factor must be evaluated even though W>M=0W_{>M}=0.

Proof. Candidates in distinct incomparability components are comparable. Their comparison direction is uniform across the two components: if aa precedes bb and a′a' is incomparable with aa in the same component, then bb cannot precede a′a', since transitivity would imply that aa precedes a′a'. Thus a′a' precedes bb. Propagating along incomparability paths in both components gives the same direction for every cross-component pair. Transitivity then orders the components totally.

Every compatible full ranking is consequently a concatenation of compatible internal rankings of C1,…,CMC_1,\ldots,C_M. Within component gg, the remaining candidates consist of its unselected members and all lower components. Grouping internal rankings by their first candidate gives Eq. (34); its eligible set enforces all internal comparisons. Factoring each full-ranking probability over components and summing separately over their compatible internal rankings gives Eq. (35), without assuming independence of the comparison events. In a final antichain, all internal rankings are allowed and their probabilities sum to one by Lemma 1. If the final component contains a comparison, some internal rankings are forbidden and have positive PL probability because all weights are positive, so its factor is strictly less than one.

Likelihood Computation and Implementation Details

This appendix describes how we evaluate and optimize the POLPO loss in Eq. (10). Scalar verifier scores induce an ordered partition of tied responses, whereas the Pareto rule in Eq. (5) preserves the comparisons supported by individual verification outcomes. Both cases use the same partial-order likelihood.

POLPO Training Algorithm

POLPO alternates between collecting responses and updating the policy (see Algorithm 1). At each rollout iteration, a frozen behavior policy πold\pi_{\mathrm{old}} generates NN responses for each of BrollB_{\mathrm{roll}} prompts. Verification determines the comparison relation within each response group. The collected groups are used for EE training epochs, with the group loss defined in Eq. (10).

The reference policy πref\pi_{\mathrm{ref}} remains fixed throughout training. Sampled responses, verifier outcomes, comparison relations, and reference log probabilities are treated as constants during policy updates. Current-policy scores are recomputed at each update, and gradients flow through these scores and the likelihood calculation. Sampling, verification, and group selection are not differentiated.

Algorithm 1 Partial-Order Likelihood Policy Optimization (POLPO)

Input: Initial policy πθ\pi_\theta, fixed reference πref\pi_{\mathrm{ref}}, prompt distribution ρ\rho, verification function cc, comparison rule A\mathcal{A} (Pareto dominance by default), and score scale β>0\beta> 0; group size N≥2N \ge2, rollout batch size BrollB_{\mathrm{roll}}, training epochs per rollout EE, rollout iterations TT, and an optimizer.

  1. for t=1,…,Tt = 1, \ldots, T do

  2. πold←πθ\pi_{\mathrm{old}} \leftarrow\pi_\theta; hold this rollout policy fixed

  3. Sample prompts x1,…,xBroll∼ρx_1, \ldots, x_{B_{\mathrm{roll}}} \sim\rho

  4. for b=1,…,Brollb = 1, \ldots, B_{\mathrm{roll}} do

  5. &nbsp;&nbsp;Sample Yb=(yb1,…,ybN)Y_b = (y_{b1}, \ldots, y_{bN}) from πold(⋅∣xb)\pi_{\mathrm{old}}(\cdot\mid x_b)

  6. &nbsp;&nbsp;Evaluate cbi←c(xb,ybi)c_{bi} \leftarrow c(x_b, y_{bi}) for i=1,…,Ni = 1, \ldots, N

  7. &nbsp;&nbsp;RV,b←A(cb1,…,cbN)R_{V,b} \leftarrow\mathcal{A}(c_{b1}, \ldots, c_{bN})

  8. end for

  9. Prepare training groups using the inclusion conditions (see Appendix C.3)

  10. for e=1,…,Ee = 1, \ldots, E do

  11. &nbsp;&nbsp;for each training batch D\mathcal{D} of response groups do

  12. &nbsp;&nbsp;&nbsp;&nbsp;Evaluate ℓPOLPO(θ;x,Y,RV)\ell_{\mathrm{POLPO}}(\theta; x, Y, R_V) from Eq. (10) for each (x,Y,RV)∈D(x, Y, R_V) \in\mathcal{D}

  13. &nbsp;&nbsp;&nbsp;&nbsp;Update θ\theta with the optimizer using the gradients of these group losses

  14. &nbsp;&nbsp;end for

  15. end for

  16. end for

  17. return πθ\pi_\theta

Likelihood evaluation. The group loss in Eq. (10) is evaluated using the series-component factorization in Proposition 6, with each required factor computed by a subset recurrence in log space. Policy scores are recomputed from the current parameters according to Eq. (6). At every step of the recurrence, the choice denominator includes all remaining candidates, including candidates that cannot be selected next without violating the relation. The computation is differentiable through the policy scores and does not enumerate complete rankings. An empty comparison relation has log-likelihood zero.

Log-Space Block Recurrence

For ordered partitions G1≻⋯≻GMG_1 \succ\cdots\succ G_M, the evaluator uses the factors in Proposition 5. Equal scalar verifier scores form a tie block; binary correctness yields at most two blocks. To evaluate the factors stably, let sˉ>g=log⁡W>g\bar{s}_{>g} = \log W_{>g} and ϕg(S)=log⁡Fg(S)\phi_g(S) = \log F_g(S). For a non-final block, sˉ>g\bar{s}_{>g} is the log-sum-exp of the scores of all lower candidates. With ϕg(∅)=0\phi_g(\varnothing) = 0, the log-space recurrence is

ϕg(S)=logsumexp⁡i∈S[si−logsumexp⁡((sj)j∈S,sˉ>g)+ϕg(S∖{i})].(36)\phi_g(S) = \operatorname{logsumexp}_{i \in S}\left[s_i - \operatorname{logsumexp}\left((s_j)_{j \in S}, \bar{s}_{>g}\right) + \phi_g(S \setminus\{i\})\right]. \tag*{(36)}

The inner log-sum-exp includes one entry for every remaining candidate and one entry for the aggregate weight of the lower blocks; repeated score values retain their multiplicities. The final tie block contributes a factor of one and is omitted, giving log⁡pθ(RV∣x,Y)=∑g=1M−1ϕg(Gg)\log p_\theta(R_V \mid x, Y) = \sum_{g=1}^{M-1} \phi_g(G_g).

The implementation enumerates all subsets of a processed block as bit masks, groups them by cardinality, and caches score-independent index and membership tables for each block size and device. All subsets of a given cardinality are evaluated together by tensor gathers and log-sum-exp operations. Processing cardinalities in increasing order ensures that the values for S∖{i}S \setminus\{i\} are available when computing the value for SS.

Automatic differentiation through this recurrence and the sequence-summed scores yields the coefficients in Proposition 3. Differentiating the log-likelihood gives AirankA_i^{\mathrm{rank}}; differentiating its negative gives −Airank-A_i^{\mathrm{rank}}. Neither linear extensions nor their conditional probabilities are explicitly constructed. Reference log probabilities are computed for the sampled responses and treated as constants.

General Partial Orders

For binary multi-verifier feedback, Pareto dominance in Eq. (5) is equivalent to strict inclusion between sets of satisfied constraints. These sets are represented as integer bit masks for efficient comparison. Every response used to construct the relation must have recorded verifier outcomes; missing outcomes are not interpreted as failed checks. The evaluator constructs the incomparability graph of the retained candidates and finds its connected components C1,…,CMC_1,\ldots,C_M. As shown in Proposition 6, these components can be ordered so that every candidate in an earlier component dominates every candidate in a later one. Internal comparisons within a component are retained. This decomposition does not impose additional comparisons between incomparable responses.

Each component factor QgQ_g is evaluated using Eq. (34). In log space, the update has the form of Eq. (36), with the outer sum restricted to MaxRV⁡(S)\operatorname{MaxRV}(S) and the denominator unchanged. If there are no lower components, the lower-weight term is omitted from the denominator. A final component is omitted only when it contains no internal comparison; a final component with internal comparisons still requires evaluation. For example, if the only comparison is y1≻y3y_1 \succ y_3 and y2y_2 is incomparable with both, all three candidates belong to one component. Its factor is evaluated and equals w1/(w1+w3)w_1/(w_1+w_3).

Vectorized evaluation and computational cost. The vectorized computation evaluates all 2m2^m subsets of each processed component of size mm, rather than traversing only the reachable order ideals (see Appendix § 10.§ 4). For each subset, candidates with a predecessor still present are excluded from the eligible set. Values for unreachable subsets are computed but do not contribute to the final component likelihood. The denominator retains all candidates in the subset and all lower components.

For a component without internal comparisons, the subset transitions require O(m2m)O(m2^m) arithmetic operations after the lower-component weight is available. For a component with internal comparisons, determining the eligible candidates uses a dense matrix multiplication between subset membership indicators and the dominance matrix; this requires O(m22m)O(m^2 2^m) arithmetic operations. The cached index and membership tables contain O(m2m)O(m2^m) entries. These implementation costs differ from counting only the reachable states of a top-down recurrence. Appendix § 11.§ 4 reports measured times.

Evaluation limits and candidate filtering. Groups with missing or empty responses are excluded before any optional filtering. An optional filter removes responses that reach the generation-length limit; the likelihood is then evaluated on the remaining responses and their induced partial order. Groups with fewer than two responses or no strict comparison contribute zero loss. In the reported training runs, each series component requiring dynamic programming is limited to 16 candidates, and groups exceeding this limit are omitted; the fixed-block cost experiment below varies this limit. A final antichain requires no computation and is exempt. Consequently, the component-size limit cannot exclude a group when N≤16N \le16.

Computational Cost

We measured the cost of the exact likelihood on NVIDIA B300 GPUs in the four coding settings of § 4.2. To isolate the likelihood, we replayed five training updates per setting and timed the forward and backward computation of the loss for the response groups that one GPU processes in an update. The timing starts from given token log probabilities, because the forward and backward passes of the policy are the same for POLPO and GRPO. At the group size N=8N = 8 of these runs, the POLPO loss, including the construction of the Pareto relation and the evaluation of the likelihood, takes 26–203 ms longer per update than GRPO’s clipped objective (Table 7). This overhead amounts to 0.03–0.07% of the time of a training update, and stays below 0.7% even relative to the policy update alone, which takes 8–31 s.

Table 7: Overhead of the POLPO loss over GRPO’s loss in the coding experiments (medians), at the group size of the coding runs (N=8N = 8) and at N=16N = 16. Training update is the time of one training update in the POLPO runs, from the training logs. Loss is the time to compute each loss and its gradient for the response groups that one GPU processes in an update, measured by replaying five training updates at N=8N = 8 and ten at N=16N = 16. Overhead is the difference between the two loss times, in milliseconds and as a percentage of the training-update time.

SettingTraining update (s)Loss (ms) POLPOLoss (ms) GRPOOverhead (ms)Overhead (%)
N=8N = 8
MBPP, Qwen3-0.6B57.564.224.240.00.07
MBPP, Qwen3-4B85.349.924.425.50.03
APPS Introductory155.272.623.948.70.03
AceCode375.1298.395.4202.90.05
N=16N = 16
MBPP, Qwen3-0.6B110.6102.524.278.30.07
MBPP, Qwen3-4B170.893.924.769.20.04
APPS Introductory235.8143.024.7118.30.05
AceCode548.2514.797.8416.90.08

Table 7.

Figure 4 shows how the time per group depends on the group size NN. We use the Pareto relations of training groups that contain at least one comparison. Groups with more than eight responses combine responses to the same problem from different updates, which is possible for MBPP and APPS. The time grows from about 0.8 ms at N=2N = 2 to 2.2–2.6 ms at N=8N = 8 and 4.1–4.7 ms at N=16N = 16, the group size of the IFM5 and MuldimInf runs. To measure the overhead at N=16N = 16 in training, we also ran POLPO with 16 responses per prompt for eleven updates in each coding setting, otherwise as in the runs above, and replayed their second to eleventh updates in the same way. The overhead over GRPO’s loss was then 69–417 ms per update, or 0.04–0.08% of a training update (Table 7).

Figure 4. Time for the likelihood and its gradient per response group on one GPU, as a function of the group size NN. Only training groups with at least one comparison are included. The line shows the median over the four coding settings in Table 7, and the band their range; groups larger than eight are available only for MBPP and APPS. The dotted line marks the group size of the coding runs. Peak additional GPU memory, including cached index tables, is below 0.1 MiB at N=8N = 8 and below 33 MiB at N=16N = 16.

We also report loss-computation costs for initial-policy instruction-following rollouts in Table 8. Relative to GRPO, the POLPO loss takes 24.5 ms longer per update on IFM5, 74.4 ms longer on MulDimIF, and 22.7 ms longer on MathIF with thinking enabled. These differences correspond to 0.05%, 0.12%, and 0.03% of the reported training-update times, respectively. The percentages compare the loss-time differences with the listed update times; they are not direct measurements of differences in total training time.

Table 8: POLPO loss overhead relative to GRPO in instruction-following settings using initial-policy rollouts. Loss times are per update; overhead is the difference between the POLPO and GRPO loss times, in milliseconds and as a percentage of the listed training-update time.

SettingTraining update (s)Loss (ms) POLPOLoss (ms) GRPOOverhead (ms)Overhead (%)
IFM5, Qwen3-4B50.743.619.124.50.05
MulDimIF, Qwen3-4B60.693.919.574.40.12
MathIF thinking, Qwen3-0.6B75.842.219.522.70.03

Table 8.

Update Cost and Block-Size Stress Test

We also measure update time and GPU memory on IFM5 rollouts from a 0.6B model, separately from the isolated loss timings above. The benchmark uses one 96 GB NVIDIA GH200 GPU, 256 sequences per step, and one response group per microbatch for both POLPO and GRPO. Table 9 reports means over steps 2–4. At fixed sequence count, increasing NN decreases the number of groups per step. This 0.6B benchmark has different conditions from the 4B IFM5 experiment in Table 8.

NNUpdate (s)GPU memory (GB)Loss
GRPOPOLPORatioGRPOPOLPO(s/step)
810.8210.791.00×16.819.10.24
165.776.161.07×19.518.30.23

Table 9. Update cost on IFM5 0.6B rollouts, averaged over steps 2–4 on one GH200. Each step contains 256 sequences, with one group per microbatch. Times, memory, and the reported loss time are shown for the measured updates.

At N=16N = 16, POLPO takes 6.16 s per update on these rollouts, compared with 5.77 s for GRPO (1.07×), and uses 18.3 GB of GPU memory compared with 19.5 GB for GRPO.

To test a demanding comparison structure, we replace the relation in every group with two ordered tiers: mm tied responses above the remaining N−mN - m responses. Here mm is the size of the upper component, consistent with the component-size notation in Appendix C.3. Table 10 reports POLPO update time and memory, the ratio to the GRPO update time at the corresponding NN in Table 9, and the loss time per group. Likelihoods are evaluated for every group in these fixed-block runs, with no exclusions or identical-outcome groups. The constructed relation is a controlled stress test rather than a measurement of the natural distribution of orders.

NNmmUpdate (s)GRPO ratioMemory (GB)Loss (ms/group)
8410.961.01×19.59.6
8710.891.01×20.413.5
1646.231.08×19.09.5
1685.931.03×17.814.3
16126.511.13×17.721.0
16156.521.13×18.325.8

Table 10. Fixed-block cost on one GH200: each group has mm tied upper responses and N−mN-m lower responses. The likelihood is evaluated for all groups. Update time, GPU memory, and per-group loss time are averaged over steps 2–4; the ratio uses the GRPO update time at the same NN in Table 9.

In the fixed-block stress test at N=16N = 16 and m=15m = 15, POLPO takes 6.52 s per update (1.13× GRPO) and uses 18.3 GB of GPU memory. Together with the real-rollout result, these measurements suggest modest time and memory costs at N=16N = 16 in the tested settings, including this demanding fixed-block case. The constructed two-tier setting does not cover every possible partial order.

Experimental Details

This appendix describes the datasets, training configurations, and evaluation protocols used in the experiments.

Controlled Program Synthesis

Each program is specified by three independent categorical choices (dj,vj)(d_j, v_j), one for each branch j∈{1,2,3}j \in\{1, 2, 3\}. Each choice has 3(M−1)3(M - 1) possible values, with dj∈{2,…,M}d_j \in\{2, \ldots, M\} and vj∈{Fizz,Buzz,FizzBuzz}v_j \in\{\texttt{Fizz}, \texttt{Buzz}, \texttt{FizzBuzz}\}. The program executes the first satisfied branch:

def f(n):
    if n % d1 == 0:
        return v1
    elif n % d2 == 0:
        return v2
    elif n % d3 == 0:
        return v3
    return str(n)

Branch distributions are initialized uniformly, and duplicate choices are allowed. The log probability of a program is the sum of the log probabilities of its three branch choices. For target divisors (a,b)(a, b), the intended output is FizzBuzz for a multiple of both divisors, Fizz or Buzz for a multiple of only one, and the input string otherwise. For the divisors and search spaces considered here, the two completely correct programs begin with (ab,FizzBuzz)(ab,\texttt{FizzBuzz}) and place (a,Fizz)(a,\texttt{Fizz}) and (b,Buzz)(b,\texttt{Buzz}) in either order afterward. Their initial total probability is 2/[3(M−1)]32/[3(M - 1)]^3.

Each integer input from 1 to 60 defines one verifier. The first sweep uses (a,b)=(3,5)(a, b) = (3, 5) and M∈{15,30,60}M \in\{15, 30, 60\}; the second uses M=60M = 60 and (a,b)∈{(3,5),(3,7),(3,11)}(a, b) \in\{(3, 5), (3, 7), (3, 11)\}. For these three divisor pairs, respectively, 4, 2, and 1 of the 60 inputs are divisible by both divisors. The other input-category counts also change in the second sweep. The experiment therefore varies the specification and does not attribute differences solely to the frequency of overlap inputs.

Each condition uses five training seeds (42, 43, 44, 45, and 46), 1,000 updates, and 64 independent groups of eight programs per update, or 512 new programs per update. Each group contains responses to the same synthesis problem; groups are independent draws from the current policy. Optimization uses Adam with learning rate 0.03, moment coefficients (0.9, 0.999), and ϵ=10−8\epsilon= 10^{-8}. The GRPO analogue uses rewards from Eq. (4), centered and divided by the population standard deviation within each group, with no KL penalty. POLPO uses β=0.1\beta= 0.1, the fixed initial uniform policy as reference, and the group loss in Eq. (10). The verifier relation is built from the complete 60-dimensional outcome vector. POLPO–Rate uses the same policy scores, β\beta, reference, group-loss normalization, and optimizer, but replaces this relation by yi≻yjy_i \succ y_j whenever ∑n=160cn(yi)>∑n=160cn(yj)\sum_{n=1}^{60} c_n(y_i) > \sum_{n=1}^{60} c_n(y_j). Since all programs are evaluated on the same 60 inputs, this is exactly the ranking by mean test pass rate. Programs with equal rates remain unordered, and the likelihood marginalizes over their relative order. POLPO–All instead sets yi≻yjy_i \succ y_j whenever yiy_i passes all 60 inputs and yjy_j does not, leaving all other pairs unordered. Since a completely correct program dominates every other program, these are exactly the comparisons of POLPO in which the preferred program is completely correct.

Complete-success probability is evaluated exactly by summing the probabilities of the two correct programs after every update. The first update at which it reaches 0.9 defines the sample-efficiency statistic, multiplied by 512 to obtain the number of generated programs. No interpolation between recorded updates is needed. Input-specific success probabilities are also computed from the categorical distributions, so evaluation has no response-sampling noise; the training trajectory still depends on the seed. Learning curves report the pointwise mean and sample standard deviation across the five training seeds, without smoothing. Threshold-crossing budgets are computed separately for each seed; when any run fails to reach the threshold within the training budget, we report the number of runs that reach it and do not compute a mean from only the successful runs.

Coding Tasks

Datasets and Prompts

MBPP. We use the full configuration of google-research-datasets/mbpp, with the official 374-problem training split and 500-problem test split [1]. Each problem has three test assertions. The prompt requests a self-contained Python implementation in a Markdown code block and includes the problem description and the first test as an example. All three assertions, including the displayed example, are used to verify the response. The released reference implementations are not used for supervised warmup or added to response groups. The 90-problem validation split is separate from the reported 500-problem test evaluation; results use the prescribed final checkpoint rather than a checkpoint selected by validation or test performance.

APPS Introductory. We use the Introductory tier of codeparrot/apps [9]. Of its 2,639 training problems, 241 have no executable test cases and are excluded, leaving 2,398 training problems. All 1,000 Introductory test problems are retained. There is no further filtering by test count, and every available test is used. Prompts contain the problem statement and supplied starter code when present, together with instructions appropriate for standard-input/output or function-call evaluation. Test cases used by the checker are not appended to the prompt; examples already present in the problem statement are retained. The training and test problem statements have no exact overlap after whitespace normalization; this check does not establish the absence of semantic near-duplicates.

AceCode. We use the hard RL-training subset released with AceCoder (Zeng et al., 2025), distributed as CodeDPO/rlhf_dataset_20250126_openrlhf_format_hard at revision f40aa9de97d882c6d411a8ca5e674ab6b1da2c12. All 21,262 released training rows are used. The hard-subset selection is inherited from the release, rather than recomputed using our initial model. Each problem supplies a prompt and a list of test-code entries. Each entry defines one verifier and can contain setup code as well as assertions; entries execute in their supplied order within the generated program’s namespace. Thus, a verifier corresponds to a supplied test entry, not necessarily a single assertion. The checker records all entries’ outcomes, including those after a failure. We use neither teacher responses nor a supervised warmup stage. Because this release has no official test split, evaluation uses the external benchmarks described below.

Models and Optimization

MBPP initializes either Qwen/Qwen3-0.6B or Qwen/Qwen3-4B, using each model’s native chat template with thinking enabled during both training and evaluation. APPS and AceCode initialize Qwen/Qwen2.5-Coder-1.5B-Instruct, also using its native chat template. The same initial weights are used across methods within each dataset and model size. MBPP trained-model results aggregate three training seeds; APPS Introductory and AceCode use seed 42 across methods. All experiments perform full-parameter fine-tuning. Table 11 summarizes the training hyperparameters.

SettingMBPPAPPS IntroductoryAceCode
Initial modelQwen3-0.6B / Qwen3-4BQwen2.5-Coder-1.5B-InstructQwen2.5-Coder-1.5B-Instruct
OptimizerAdamWAdamWAdamW
Learning rateSee Table 12See Table 12See Table 12
Adam coefficients (β1\beta_1, β2\beta_2)(0.9, 0.999)(0.9, 0.999)(0.9, 0.999)
Weight decay0.010.010.01
Learning-rate scheduleConstantConstantConstant
WarmupNoneNoneNone
Gradient clipping norm1.01.01.0
Prompts per rollout batch3264256
Responses per prompt888
Update mini-batch size3264256
Update epochs per rollout batch111
Training epochs521
Maximum prompt length (tokens)1,02416,38416,384
Maximum response length (tokens)2,0482,0482,048
Sampling temperature1.01.01.0
Top-pp1.01.01.0
Top-kkDisabledDisabledDisabled

Table 11. Training hyperparameters for coding tasks. Rollout and update mini-batch sizes count prompts in a full batch; the final incomplete prompt batch is retained. Learning-rate settings are listed in Table 12. Token limits and sampling settings apply to training rollouts; evaluation context limits are specified in the text.

Each training round samples eight responses per prompt at temperature 1, with top-p and top-k truncation disabled. All sampled responses contribute to a single optimizer update; the optimizer mini-batch equals the full rollout batch. The prompt order is shuffled, and the final incomplete prompt batch in each epoch is retained. Training uses only fresh responses, without replay or demonstrations. Within each MBPP model size, all runs train from the common initial model for all five epochs.

The optimizer is AdamW with a constant learning rate, no warmup, moment coefficients (0.9, 0.999), ϵ=10−8\epsilon= 10^{-8}, weight decay 0.01, and gradient clipping at norm 1. Table 12 lists the learning-rate settings for each dataset, initial model, and method.

MethodMBPP: Qwen3-0.6BMBPP: Qwen3-4BAPPS Introductory: Qwen2.5-Coder-1.5B-InstructAceCode
GRPO–All2×10−62 \times10^{-6}1×10−61 \times10^{-6}2×10−62 \times10^{-6}5×10−75 \times10^{-7}
GRPO–Rate2×10−62 \times10^{-6}1×10−61 \times10^{-6}2×10−62 \times10^{-6}5×10−75 \times10^{-7}
GRPO–Pareto2×10−62 \times10^{-6}1×10−61 \times10^{-6}––
REINFORCE++–All2×10−62 \times10^{-6}2×10−62 \times10^{-6}2×10−62 \times10^{-6}–
REINFORCE++–Rate2×10−62 \times10^{-6}2×10−62 \times10^{-6}2×10−62 \times10^{-6}–
GDPO10−610^{-6}2×10−62 \times10^{-6}2×10−62 \times10^{-6}–
GraphDPO2×10−62 \times10^{-6}5×10−65 \times10^{-6}2×10−62 \times10^{-6}5×10−75 \times10^{-7}
DPO–Pareto2×10−62 \times10^{-6}1×10−61 \times10^{-6}2×10−62 \times10^{-6}5×10−75 \times10^{-7}
POLPO–All2×10−62 \times10^{-6}1×10−61 \times10^{-6}––
POLPO–Rate5×10−65 \times10^{-6}5×10−65 \times10^{-6}––
POLPO5×10−65 \times10^{-6}5×10−65 \times10^{-6}2×10−62 \times10^{-6}2×10−62 \times10^{-6}

Table 12. Learning-rate settings for the coding experiments. A dash indicates that the method is not evaluated in that setting.

The validation-based learning-rate selection protocol specifies a random problem-level split of each eligible training set into 80% training and 20% validation, using seed 42 and rounding the validation count up. This gives training/validation counts of 299/75 for MBPP, 1,918/480 for APPS Introductory, and 17,009/4,253 for AceCode. All tests and responses associated with a problem remain in the same partition, and the partition is shared across methods, model sizes, and learning-rate candidates. The official test sets and external evaluation benchmarks remain separate.

The protocol compares learning rates {5×10−7,1×10−6,2×10−6,5×10−6,10−5}\{5 \times10^{-7}, 1 \times10^{-6}, 2 \times10^{-6}, 5 \times10^{-6}, 10^{-5}\}, training each candidate on the training portion for the dataset-specific number of epochs in Table 11. For each method and initial model, selection uses the highest validation All-pass score at the final checkpoint, with one greedy response per problem. Ties are resolved by higher Avg. pass and then by the smaller learning rate. Training then restarts from the initial model with the selected rate on the full training set, including the validation portion, for the same number of epochs before final-checkpoint evaluation. For the MBPP POLPO–Rate ablation, we reuse the learning rate selected for POLPO for the same initial model. The MBPP POLPO–All and GRPO–Pareto ablations use the learning rate of GRPO–All and GRPO–Rate for the same initial model.

GRPO–All and GRPO–Rate use clipping parameter 0.2, standardize rewards within each response group, and average token contributions within each response before averaging over responses. Neither baseline uses a KL or entropy penalty.

POLPO uses β=10−3\beta= 10^{-3}, the fixed initial model as reference, and sequence-summed token log-probability ratios. Its loss averages over all prompt groups and divides each group’s negative log-likelihood by its eight candidates. Groups without a dominance comparison contribute zero loss and remain in the denominator. This candidate-count normalization does not normalize scores by response length. The verifier outcomes used to construct the Pareto relation are the same outcomes used for the two GRPO rewards. Micro-batches preserve each complete eight-response group.

For MBPP, POLPO–Rate uses the same partial-order likelihood objective, policy scores, fixed initial reference, β\beta, group-loss normalization, optimizer, learning rate, and all other hyperparameters as POLPO. The only difference is the comparison relation: POLPO–Rate uses pass-rate rankings, so a response precedes another if and only if its mean test-pass rate is strictly higher, with equal-rate responses left unordered.

POLPO–All uses the same objective and settings as POLPO except for the learning rate and the comparison relation: a response precedes another if and only if it passes all tests and the other does not, so the responses that pass all tests are tied with one another, as are the remaining responses. GRPO–Pareto uses the update of GRPO–All and GRPO–Rate, including its clipping and token reduction, but replaces their standardized rewards with the coefficients AirankA_i^{\mathrm{rank}} of Proposition 3 evaluated at equal scores s1=⋯=sNs_1=\cdots=s_N. These coefficients depend only on the Pareto relation and sum to zero within each group; they are not standardized, and groups without a dominance comparison receive zero coefficients. GRPO–Pareto uses no reference model.

Additional Baseline Implementations

The following baselines are evaluated on MBPP and APPS; DPO–Pareto and GraphDPO are also evaluated on AceCode. They use the same prompts, tests, rollout budgets, and training horizons as the corresponding GRPO and POLPO runs.

REINFORCE++. We use the original global-normalization variant of REINFORCE++ ([11]), without a within-prompt mean-reward baseline. The All and Rate variants assign the all-pass indicator and the fraction of tests passed, respectively, as terminal rewards. With discount factor 1, the terminal reward propagates to all response tokens; returns are then standardized across valid response tokens in the rollout batch. The policy loss uses the same clipping parameter 0.2 and sequence-mean token-mean reduction as GRPO, without a KL or entropy penalty.

GDPO. We adapt GDPO ([19]) to the problem-specific test sets by treating each binary test outcome as a reward component. Each component is standardized across the eight responses to the same prompt using the sample standard deviation plus 10−610^{-6}. We average the resulting components over that problem’s actual tests, broadcast the aggregate to its response tokens, and standardize across valid response tokens in the batch. A test with a constant outcome within a response group contributes zero. Test identities are aligned only within a prompt; absent tests are not padded into the average. Averaging rather than summing components avoids scaling the aggregate simply by the number of tests. The policy-loss configuration is otherwise the same as for REINFORCE++.

DPO–Pareto and GraphDPO. Both baselines use the same strict Pareto relation, fixed initial reference, sequence-summed log-probability ratios, and β=10−3\beta=10^{-3} as POLPO. DPO–Pareto averages the negative log-sigmoid DPO loss over all strict dominance pairs within each prompt, including transitive pairs. Ties and incomparable responses introduce no preference pairs. For GraphDPO, we apply the local objective of Liu et al. [18] to this Pareto dominance graph. Each response that dominates at least one other response is a positive candidate in a softmax over itself and all responses it dominates, including transitive descendants. We average these negative log-choice probabilities over such responses within the prompt. This applies GraphDPO’s objective to our verifier-derived graph; no reference solutions or ground-truth anchoring are added. For both methods, prompt losses are averaged over all prompts, with comparison-free groups contributing zero and remaining in the denominator. Their within-prompt pair or node averages receive no additional division by the number of candidates, whereas POLPO divides each group’s negative log-likelihood by eight.

Evaluation

All coding evaluations generate one greedy response per problem and score the final checkpoint at the fixed training horizon. The initial-model row uses the same evaluation protocol as the trained models in its table. The response limit is 2,048 tokens for all three coding settings. For both Qwen3 model sizes, this budget includes thinking tokens. Training on MBPP uses a 3,072-token context, while evaluation allows a 4,096-token context to accommodate longer test prompts without reducing the 2,048-token response budget. The APPS and AceCode evaluations use an 8,192-token context, accommodating their evaluation prompts and the 2,048-token response budget.

For MBPP and APPS, let QQ be the number of evaluation problems, let KjK_j be the number of tests for problem jj, and let cjkc_{jk} indicate whether its generated response passes test kk. We report

All-pass=100Q∑j=1Q∏k=1Kjcjk,(37)\mathrm{All\text{-}pass} = \frac{100}{Q}\sum_{j=1}^{Q}\prod_{k=1}^{K_j} c_{jk}, \tag*{(37)}
Avg. pass=100Q∑j=1Q1Kj∑k=1Kjcjk.(38)\mathrm{Avg.\ pass} = \frac{100}{Q}\sum_{j=1}^{Q}\frac{1}{K_j}\sum_{k=1}^{K_j}c_{jk}. \tag*{(38)}

Here Q=500Q = 500 for MBPP and Q=1,000Q = 1{,}000 for APPS Introductory. The second metric is a macro-average over problems, so problems with many tests do not dominate the score. Compilation errors, runtime errors, and timeouts count as failures for the affected checks.

AceCode-trained models are evaluated with EvalPlus version 0.3.1, using HumanEval+ v0.1.10 (164 problems) and MBPP+ v0.2.0 (378 problems) [17]. We use EvalPlus prompt formatting, code sanitization, and execution checking. Each generated response is evaluated against both the original tests and the augmented tests; success requires passing every test in the corresponding suite. Both columns therefore report pass@1, rather than a per-test pass rate. The original-test MBPP score here is computed on the 378 EvalPlus problems and should not be equated with the official 500-problem MBPP test score. Generated programs run in isolated execution environments with time limits.

Multi-Instruction Following

The IFM5 and MulDimIF experiments train separate models using the training data of the corresponding dataset and evaluate on its test data. MulDimIF results do not evaluate transfer of an IFM5-trained checkpoint. For IFM5 and MulDimIF, the initial-model row denotes Qwen3-4B-Instruct-2507 before the additional training in these experiments.1

IFM5 Data and Split

We use allenai/IF_multi_constraints_upto5, released with Pyatkin et al. [28].2 The dataset card identifies this as IF-RLVR training data with up to five constraints per prompt, drawn from 25 IFEval and 29 IFBench-Train constraint templates. We abbreviate this dataset as IFM5. Our test set is a holdout from this released training dataset, not the original IFBench benchmark test set.

All 95,373 rows are uniformly shuffled, the first 2,000 rows are assigned to the test split, and the remaining 93,373 rows to the training split. This is a row-level random split without stratification by the number of constraints. Table 13 gives the test distribution before and after length filtering. The initial distribution is close to the reported approximate training proportions of 24%, 25%, 24%, 19%, and 7% for K=1,…,5K = 1, \ldots, 5, respectively; these training percentages are rounded summaries, not exact counts.

Constraint count KK12345Total
Before filtering4784935003941352,000
Excluded2573017
Retained4764884933911351,983

Table 13. IFM5 test counts before and after excluding prompts longer than 2,048 tokens. The retained counts are the denominators for the reported complete satisfaction rates and the weights for overall aggregation.

Prompts exceeding 2,048 tokens are excluded as entire examples, not shortened. This excludes 17 test prompts, leaving 1,983 for evaluation.

MulDimIF Data and Levels

Models in the MulDimIF experiment are trained on its training split and evaluated on its test split [38]. The paper defines four levels using both the number of constraint categories and the number of individual constraints (Table 14). Thus, Level IV does not mean exactly four individual constraints. The framework also distinguishes example, listing, and incorporation presentation patterns.

LevelConstraint categoriesIndividual constraints
I11–2
II22–4
III33–6
IV44–8

Table 14. MulDimIF difficulty levels, following Ye et al. (2026, Section 3.1.3).

Verification and Evaluation Metrics

For evaluated prompt xjx_j, let KjK_j be its number of constraints and cjk∈{0,1}c_{jk} \in\{0,1\} indicate whether the generated response passes check kk. Complete constraint satisfaction is

uj=∏k=1Kjcjk,CS=1n∑j=1nuj,(39)u_j = \prod_{k=1}^{K_j} c_{jk}, \qquad\mathrm{CS} = \frac{1}{n}\sum_{j=1}^{n} u_j, \tag*{(39)}

where nn is the number of evaluated prompts after applicable exclusions. Tables report 100 CS as a percentage.

For IFM5, let nkn_k count retained prompts with Kj=kK_j = k and let AkA_k be their mean complete satisfaction. The overall rate is the prompt-count-weighted average

CSIFM5=∑k=15nkAk∑k=15nk.(40)\mathrm{CS}_{\mathrm{IFM5}} = \frac{\sum_{k=1}^{5} n_k A_k}{\sum_{k=1}^{5} n_k}. \tag*{(40)}

The weights are the retained counts in Table 13: (n1,…,n5)=(476,488,493,391,135)(n_1, \ldots, n_5) = (476, 488, 493, 391, 135). Overall values are retained from the evaluation summaries rather than recomputed from rounded subgroup rates.

For both IFM5 and MulDimIF, each trained method is reported as the mean and standard deviation across three training seeds. IFM5 test responses use greedy decoding.

Training Configurations

Table 15 summarizes the training hyperparameters for IFM5 and MulDimIF. Both configurations use 64 prompts per rollout batch and 16 sampled responses per prompt, giving 1,024 responses per full rollout batch. The configured training horizon is 400 trainer steps for each dataset.

SettingIFM5MulDimIF
Initial modelQwen3-4B-Instruct-2507Qwen3-4B-Instruct-2507
OptimizerAdamWAdamW
Learning rate10−610^{-6}10−610^{-6}
Adam coefficients (β1,β2\beta_1, \beta_2)(0.9, 0.999)(0.9, 0.999)
Weight decay0.010.01
Learning-rate scheduleConstantConstant
WarmupNoneNone
Gradient clipping norm1.01.0
Prompts per rollout batch6464
Responses per prompt1616
Update mini-batch size1616
Update epochs per rollout batch11
Training horizon (trainer steps)400400
Maximum prompt length (tokens)2,0484,096
Maximum response length (tokens)2,0484,096
Sampling temperature1.01.0
Top-pp1.01.0
Top-kkDisabledDisabled

Table 15. Training hyperparameters for IFM5 and MulDimIF. Rollout batch size counts prompts. The training horizon is measured in trainer steps; the update mini-batch size is reported as configured. Sampling settings apply to training rollouts.

On both IFM5 and MulDimIF, we compare the initial model, GRPO–All, GRPO–Rate, GDPO (Liu et al., [19]), GraphDPO, DPO–Pareto, and POLPO (Table 4 and Table 5). GraphDPO and DPO–Pareto use the Pareto relation, and the reported GraphDPO, DPO–Pareto, and POLPO results use the non-normalized variants. GRPO–All assigns reward one only when every constraint is satisfied, whereas GRPO–Rate uses the fraction of satisfied constraints, as defined in Eq. (4). Both GRPO–All and GRPO–Rate use a KL coefficient of 10−310^{-3}.

POLPO constructs comparisons from the individual pass/fail vectors using Eq. (5) and optimizes the partial-order likelihood in Eq. (10) with score scale β=10−3\beta= 10^{-3}. The GRPO KL coefficient controls the KL penalty, whereas POLPO’s β\beta scales the policy-to-reference scores; their equal numerical values do not imply equal regularization strength.

MathIF: Data, Training, and Evaluation

Benchmark and task. MathIF combines mathematical questions with one, two, or three programmatically verifiable instruction constraints (Fu et al., [6]). We evaluate all 420 examples: GSM8K, MATH-500, Minerva, and OlympiadBench each contribute 30 examples at each constraint count, while AIME 2024/25 contributes 20, giving 140 examples at each count. The benchmark uses 15 constraint types covering lexical, length, format, language, and affix requirements. The prompt contains the mathematical question, a request for step-by-step reasoning and a final answer in \boxed{ }, and the constraint descriptions, in a single user turn without a system prompt.

Training data and overlap filtering. We construct a separate training dataset by adding constraints to problems from the MATH training split (Hendrycks et al., [10]), using DeepLearningGmbH/MATH–lighteval as the source release. Reference answers are extracted from the final boxed expression in each sampled solution. We filter source problems against both the 420 MathIF examples and MATH-500 using normalized exact matching, or a shared word 10-gram together with a difflib similarity ratio of at least 0.9. Problems sharing a template but differing only in numerical values are retained; this filtering therefore does not establish the absence of all semantic overlap. Of the 7,500 source problems, 55 are removed by overlap filtering, two because their question text exceeds 3,000 characters, and two because their solutions contain no boxed answer that can be extracted. These exclusions leave 7,441 source problems, split into 6,941 for training and 500 for validation. Each problem yields one example at each of K=1,2,3K = 1, 2, 3 constraints, producing 20,823 training examples and 1,500 validation examples. An additional validation set contains the 500 MATH-500 problems without added constraints. No difficulty-based or all-pass filtering is applied.

Constraint generation. We use the constraint wording and sample constraint parameters from the MathIF implementation included in our codebase. Training uses 14 of the benchmark’s 15 constraint types, excluding the requirement to answer in a specified language. Each training prompt follows the same format as an evaluation prompt: the mathematical question, a request for step-by-step reasoning, and the sampled constraints.

We check which constraints can be combined before sampling them together. If MathIF lists two constraint types as incompatible in either order, we treat the pair as incompatible in both orders. For the constraint that requires repeating the prompt, we adjust this list to permit the relevant benchmark combinations: its incompatible types are quotation, all-uppercase, all-lowercase, multiple-section, and response-language requirements. We also exclude combinations of all-lowercase text with multiple sections, and combinations of multiple sections with a bullet list. When all-uppercase text and multiple sections are required together, we use SECTION as the section delimiter.

We also check the question and reference answer when their contents could conflict with a constraint. A no-comma constraint is sampled only if the reference answer contains no comma; if the prompt must be repeated, the question must also contain no comma. Before sampling combinations that require repeating the prompt, we check the question for forbidden words and ensure that repeating it would not already exceed the specified word-frequency or word-count limits. Keywords are distinct within each set of constraints.

Verification and training objectives. For a response to a problem with KK instruction constraints, the feedback vector is

v=(a,c1,…,cK)∈{0,1}K+1,rrate=a+∑k=1KckK+1,(41)\mathbf{v} = (a, c_1, \ldots, c_K) \in\{0,1\}^{K+1}, \qquad r_{\mathrm{rate}} = \frac{a + \sum_{k=1}^{K} c_k}{K+1}, \tag*{(41)}

where aa indicates mathematical correctness and ckc_k indicates satisfaction of constraint kk. GRPO–All uses rall=a∏k=1Kckr_{\mathrm{all}} = a \prod_{k=1}^{K} c_k, which is one only when the response is mathematically correct and satisfies every instruction constraint. GRPO–Rate uses rrater_{\mathrm{rate}} as its scalar reward, while POLPO constructs the dominance relation from the full vector, including correctness. The thinking-enabled GraphDPO and DPO–Pareto results use the same Pareto rule and non-normalized variants; the reported POLPO result also uses the non-normalized variant. We use the same verifier implementations during training and evaluation for both mathematical correctness and instruction-constraint satisfaction. Mathematical correctness is evaluated with the mathematical-answer grader distributed with verl and used by MathIF. In the thinking-enabled runs, a response whose thinking segment is not closed receives zero for the mathematical correctness bit and every constraint bit; this rule applies to both training feedback and evaluation. The thinking-enabled results use our verification rules, including LaTeX-aware case checks for instruction constraints, rather than the original MathIF text rules.

Optimization. Table 16 summarizes the MathIF training hyperparameters in the same format as Table 15. The original non-thinking MathIF training runs initialize Qwen/Qwen3-0.6BQ_{\mathrm{wen}}/Q_{\mathrm{wen3\text{-}0.6B}} with thinking disabled. In these non-thinking runs, each rollout batch contains 64 prompts with eight responses per prompt, giving 512 sampled responses. The evaluated trained-model checkpoints correspond to the reported one-epoch runs of 325 trainer steps. Both GRPO–All and GRPO–Rate use a KL coefficient of 10−310^{-3}; POLPO uses score scale β=10−3\beta= 10^{-3} and no additional KL penalty.

SettingThinking disabledThinking enabled
Initial modelQwen3-0.6B
OptimizerAdamW
Learning rate10−610^{-6}
Adam coefficients (β1,β2)(\beta_1,\beta_2)(0.9,0.999)(0.9, 0.999)
Weight decay0.010.01
Learning-rate scheduleConstant
WarmupNone
Gradient clipping norm1.01.0
Prompts per rollout batch6464
Responses per prompt88
Update mini-batch size1616
Update epochs per rollout batch11
Training epochs11
Maximum prompt length (tokens)2,0482{,}048
Maximum response length (tokens)2,0482{,}0488,1928{,}192
Sampling temperature1.01.0
Top-pp1.01.0
Top-kkDisabled

Table 16. MathIF training hyperparameters by thinking mode. Rollout and update mini-batch sizes count prompts; sampling settings apply to training rollouts. Shared values apply to both modes.

Evaluation and metrics. In both thinking modes, evaluation uses one greedy response per MathIF example with a maximum generation length of 16,384 tokens. In thinking-enabled evaluation, this budget includes the thinking segment and the final answer; the training rollout response limit remains 8,192 tokens (Table 16). Benchmark source and constraint count are identified from the dataset filenames because some record identifiers do not match those attributes. For the Q=420Q = 420 evaluated examples, let aja_j be mathematical correctness, KjK_j the number of instruction constraints, and cjkc_{jk} the evaluation checker’s outcome for constraint kk. We report

HAcc=100Q∑j=1Q∏k=1Kjcjk,SAcc=100Q∑j=1Q1Kj∑k=1Kjcjk.(42)\begin{aligned} \mathrm{HAcc} &= \frac{100}{Q}\sum_{j=1}^{Q}\prod_{k=1}^{K_j}c_{jk}, & \mathrm{SAcc} &= \frac{100}{Q}\sum_{j=1}^{Q}\frac{1}{K_j}\sum_{k=1}^{K_j}c_{jk}. \tag*{(42)} \end{aligned}
Acc=100Q∑j=1Qaj,Joint=100Q∑j=1Qaj∏k=1Kjcjk.(43)\begin{aligned} \mathrm{Acc} &= \frac{100}{Q}\sum_{j=1}^{Q}a_j, & \mathrm{Joint} &= \frac{100}{Q}\sum_{j=1}^{Q}a_j\prod_{k=1}^{K_j}c_{jk}. \tag*{(43)} \end{aligned}

HAcc and SAcc measure instruction adherence without requiring mathematical correctness; Joint measures their conjunction with correctness. All displayed percentages retain the precision of the evaluation summaries.

Additional Experiments

Measured Toy Learning Efficiency

Table 17 summarizes the threshold crossings in Figure 3 and Figure 5. The values are computed separately from each of the five saved training trajectories. We report the mean and sample standard deviation of the first recorded crossing budgets only when all five runs reach the threshold. Otherwise, the table gives the number of runs that reach it, so that runs without a crossing are not silently excluded.

Figure 5. Complete-success probability for target (3,5)(3, 5) with search spaces M=15M = 15, 30, and 60 over the full budget of 512,000 programs, averaged over five training seeds. Shading shows one sample standard deviation across seeds, clipped to [0,1][0, 1]. The horizontal dotted line marks 0.9, and markers indicate the first recorded crossings of the mean curves.

Figure 5 shows the first sweep, which varies the search space for target (3,5)(3, 5) over the full budget. POLPO reaches the threshold in all five seeds for every MM, using on average 82.0, 88.7, and 96.5 thousand programs for M=15M = 15, 30, and 60, respectively. GRPO–All and POLPO–All reach it in all five seeds for M=15M = 15, in three seeds for M=30M = 30, and in no seed for M=60M = 60, and their curves nearly coincide. POLPO–Rate reaches it in one, three, and five seeds, and GRPO–Rate in four, five, and three seeds, respectively.

Learning-Signal Availability in Coding Tasks

POLPO compares two responses only when one Pareto-dominates the other, so on the same responses it obtains a learning signal from at most as many groups as a pass-rate reward. This is intended: a pass-rate reward also orders responses with conflicting test outcomes, which prescribes a trade-off between tests that verification does not establish and can steer learning away from complete solutions (§ 4.1). A smaller share of groups with a learning signal is therefore not a drawback in itself. Because a group provides no signal under any of the compared conditions once all eight responses pass every test, we report both the share of training groups that provide a learning signal and the same share among unsolved groups, in which not all eight responses pass every test.

TargetMMGRPO–AllGRPO–RatePOLPO–AllPOLPO–RatePOLPO
(3, 5)15131.0±16.2131.0 \pm16.2— (4/5)132.0±16.3132.0 \pm16.3— (1/5)82.0±3.382.0 \pm3.3
(3, 5)30— (3/5)118.7±8.8118.7 \pm8.8— (3/5)— (3/5)88.7±2.288.7 \pm2.2
(3, 5)60— (0/5)— (3/5)— (0/5)136.5±30.3136.5 \pm30.396.5±0.696.5 \pm0.6
(3, 7)60— (0/5)— (3/5)— (0/5)151.0±13.8151.0 \pm13.899.5±4.699.5 \pm4.6
(3, 11)60— (0/5)— (1/5)— (0/5)— (3/5)99.7±1.999.7 \pm1.9

Table 17. Generated programs needed to reach 0.9 complete-success probability, in thousands (mean ±\pm sample standard deviation over five seeds). The first two rows vary the search space MM for target (3,5)(3, 5); the last three use M=60M = 60, as in Figure 3. A dash with (k/5)(k/5) indicates that only kk runs reached the threshold within 512,000 programs, so a mean crossing budget is not reported. Crossings are taken from every-update records without interpolation.

Figure 7 shows both shares for MBPP in each training epoch. For Qwen3-0.6B, POLPO, POLPO–Rate, and GRPO–Rate obtain a signal from roughly 55–65% of groups, whereas GRPO–All stays below 50%. For Qwen3-4B, the shares are lower for all methods, ranging from about 29% to 41%. In the first epoch, when all runs start from the same initial model, POLPO’s share is within two percentage points of those of POLPO–Rate and GRPO–Rate and above that of GRPO–All for both models. Later in training, POLPO’s share decreases, to about 56–57% in the last two epochs for Qwen3-0.6B and to about 29–32% from the second epoch for Qwen3-4B, but it stays above that of GRPO–All for Qwen3-0.6B and within five percentage points of it for Qwen3-4B. Among unsolved groups, POLPO’s share shows no such decrease: for Qwen3-4B, it stays between about 73% and 77%, close to those of POLPO–Rate and GRPO–Rate, and for Qwen3-0.6B, it is the highest of the four methods in every epoch.

Figure 7. Learning signal on MBPP in each training epoch. Top: share of training groups that provide a learning signal. A group is the eight responses sampled for one problem at one update; it provides a signal when it contains a strict Pareto-dominance pair (POLPO), at least two distinct test-pass rates (POLPO–Rate and GRPO–Rate), or both a response that passes every test and one that does not (GRPO–All), and otherwise contributes no policy gradient. Bottom: the same share among unsolved groups, in which not all eight responses pass every test. Points show the mean over three training seeds of the runs in Table 1, and bars show one sample standard deviation. Within each row, the two panels use the same vertical scale over different ranges.

Figure 8 shows the same shares for APPS Introductory and AceCode, for the training runs in Table 2 and Table 3. POLPO starts at the level of GRPO–Rate, with about 76% of groups for APPS Introductory and 72% for AceCode, and decreases over training to about 54% and 50%, respectively, while GRPO–Rate stays between about 69% and 79% and GRPO–All between about 39% and 48%. Among unsolved groups, POLPO’s share decreases less, from about 84% to 73% for APPS Introductory and from about 74% to 62% for AceCode; it remains well above that of GRPO–All, which is at most about 52%, and falls below that of GRPO–Rate later in training. Thus, restricting comparisons to verified improvements still leaves POLPO with a learning signal from more unsolved groups than GRPO–All in all three datasets, and from a share comparable to that of GRPO–Rate on MBPP and early in training on APPS Introductory and AceCode.

Figure 8. Learning signal on APPS Introductory and AceCode during training. Top: share of training groups that provide a learning signal; bottom: the same share among unsolved groups, as in Figure 7. Each point pools about ten consecutive updates of the training run in Table 2 or Table 3, and the dotted line marks the boundary between the two APPS Introductory epochs. Within each row, the two panels use the same vertical scale over different ranges.

Figure 6. Diagnostic curves for target (3,11)(3, 11), averaged over five training seeds, with shading showing one sample standard deviation clipped to [0,1][0,1]. The left panel averages pass probability over all 60 verifiers, and the right panel shows the overlap input n=33n = 33. The vertical dotted line marks 153,600 generated programs.

Structure of the Pareto Partial Orders

Figure 9 characterizes the partial orders that POLPO receives in the coding tasks, using the same training groups as Figure 7 and Figure 8. It divides all groups into four kinds: the eight responses have identical test outcomes; their outcomes differ but contain no dominance pair; their Pareto order is a ranking with ties; or their Pareto order is genuinely partial, containing two responses with different outcomes neither of which dominates the other. Groups whose outcomes differ without any dominance pair are rare, at most about 1% of groups in every dataset and stage. Genuinely partial orders occur in about 14–23% of all groups for APPS Introductory and AceCode, compared with at most about 7% for Qwen3-0.6B and 2% for Qwen3-4B on MBPP, where each problem has three tests. Over training, the share of groups with identical outcomes increases in every dataset.

Figure 9. Structure of the Pareto partial orders in POLPO’s training groups for the coding tasks, per fifth of training (epochs for MBPP, fifths of the updates for APPS Introductory and AceCode). All groups are divided by whether the eight responses have identical test outcomes, differ without any dominance pair, are ordered as a ranking with ties, or form a genuinely partial order containing two incomparable responses with different outcomes. MBPP pools the three training seeds of the runs in Table 1; APPS Introductory and AceCode show the runs in Tables 2 and 3.

Figure 10 compares POLPO’s objective with GraphDPO’s on the groups with dominance. When every response has at most one immediate dominator, so that the dominance relation forms a rooted forest, the Plackett–Luce events that each dominating response precedes its descendants are independent. POLPO’s group log-likelihood then equals the sum of GraphDPO’s per-response log-softmax terms, and the two objectives differ only by a constant factor. Otherwise, they are different functions of the scores, which is the case for about 80–90% of the groups with dominance in every dataset. Most of these groups contain several responses with the same outcomes that dominate the same responses: POLPO requires each dominated response to follow all of them jointly, whereas GraphDPO adds a separate softmax term for each dominating response. For APPS Introductory and AceCode, about 18–27% of the groups with dominance also contain responses with distinct outcomes that dominate the same response.

Figure 10. Comparison of POLPO’s objective with GraphDPO’s on the training groups of Figure 9 that contain dominance, per fifth of training. The groups are divided by whether POLPO’s objective equals GraphDPO’s up to a constant factor (every response has at most one immediate dominator) or differs because tied responses or responses with distinct outcomes dominate the same response.

Learning Signals and Pareto-Order Structure in Instruction Following

We extend the rollout analyses of Appendices E.2 and E.3 to IFM5, MulDimIF, and MathIF with thinking enabled. We analyze initial-policy and final-policy response groups: 988 groups for IFM5, 800 for MulDimIF, and 375 for MathIF. A group contains responses to a prompt. The final groups for each method come from the policy trained by that method; thus, final-method comparisons reflect both the objective and the policy’s sampled responses. These endpoint summaries differ from the single-response benchmark scores in § 4.3. We also report the number of dominance pairs in training rollouts over time in Figure 11.

Figure 11. Mean number of strict dominance pairs per group containing at least one dominance pair, in instruction-following training rollouts. Each point represents a 20-step window; the last MathIF point covers only steps 321–325 and is placed at their midpoint. IFM5 and MulDimIF results show the mean over three training seeds, with shading indicating ± one standard deviation across seeds; MathIF uses one seed. The panels have different vertical scales. The maximum possible pair count is 120 for N=16N = 16 and 28 for N=8N = 8.

Learning-signal availability. As in the coding analysis, a group supplies a POLPO signal if it contains a strict Pareto-dominance pair, a GRPO–Rate signal if its responses have different fractions of satisfied checks, and a GRPO–All signal if it contains both a fully successful response and a response that is not fully successful. For MathIF, the checks include mathematical correctness as well as the instruction constraints (Eq. (41)). A group is solved here only when every response in it satisfies every check; an unsolved group is any other group. This group-level notion differs from the single-response success metrics in the main experiments.

Table 18 reports signal shares over all groups and over unsolved groups. At initialization, POLPO obtains a signal from 47.7%, 74.8%, and 75.2% of groups on IFM5, MulDimIF, and MathIF, respectively, compared with 17.7%, 43.0%, and 26.4% for GRPO–All and 47.7%, 74.8%, and 75.5% for GRPO–Rate. At the POLPO endpoint, the all-group signal shares decrease to 14.0%, 11.1%, and 52.5%, while the solved shares increase to 56.5%, 84.4%, and 38.9%. Among final unsolved groups, POLPO obtains a signal from 32.1%, 71.2%, and 86.0% of groups, compared with 27.2%, 64.3%, and 67.4% for GRPO–All and 41.5%, 80.1%, and 86.1% for GRPO–Rate. These final comparisons use each method’s own rollouts and therefore reflect both differences in signal criteria and differences in sampled responses. The all-group and unsolved-group views provide complementary information.

MethodInitial signalFinal signalSolved
AllUnsolvedAllUnsolvedInitial →\to final
IFM5 (n=988n = 988)
POLPO47.757.714.032.117.4 →\to 56.5
GRPO–All17.721.413.127.217.4 →\to 51.9
GRPO–Rate47.757.719.141.517.4 →\to 53.9
MulDimIF (n=800n = 800)
POLPO74.889.011.171.216.0 →\to 84.4
GRPO–All43.051.212.464.316.0 →\to 80.8
GRPO–Rate74.889.015.180.116.0 →\to 81.1
MathIF, thinking enabled (n=375n = 375)
POLPO75.279.252.586.05.1 →\to 38.9
GRPO–All26.427.843.567.45.1 →\to 35.5
GRPO–Rate75.579.559.586.15.1 →\to 30.9

Table 18. Learning-signal availability (%) in instruction-following rollout groups. Each method uses its own signal criterion. Initial and final signal shares use all groups or only unsolved groups; solved shares are over all groups. Final groups are sampled from the corresponding method’s trained policy.

Pareto-order structure. Table 19 partitions the initial and POLPO-final groups using the same categories as Figure 9. The share of genuinely partial orders is 8.9% on initial IFM5, 31.2% on initial MulDimIF, and 29.3% on initial MathIF; it falls to 1.4%, 0.5%, and 11.5%, respectively, at the POLPO endpoint. Meanwhile, the share of groups with identical outcome vectors rises from 52.1% to 84.7% on IFM5, from 25.1% to 88.9% on MulDimIF, and from 23.5% to 47.2% on MathIF. Identical outcomes alone do not imply that all responses are fully successful. Groups with differing outcomes but no dominance pair account for at most 1.3% of groups in these snapshots.

PolicynnIdentical outcomesDifferent, no dominanceRanking with tiesGenuinely partial
IFM5
Initial98852.10.238.88.9
POLPO final98884.71.312.61.4
MulDimIF
Initial80025.10.143.531.2
POLPO final80088.90.010.60.5
MathIF, thinking enabled
Initial37523.51.345.929.3
POLPO final37547.20.341.111.5

Table 19. Structure of initial-policy and POLPO-final instruction-following rollout groups (% of all groups). Identical means that all verification vectors match. The second category has different vectors but no dominance pair. The remaining categories contain dominance: the distinct vectors form a ranking with ties, or the order is genuinely partial, with incomparable distinct vectors. Percentages may not sum to 100 because of rounding.

POLPO and GraphDPO objectives. Table 20 compares the objectives on the subset of groups that contain dominance, following Figure 10. Across the six dataset–policy snapshots, the objectives agree up to a constant factor on 2.2–11.0% of dominance groups; they differ on the remainder. Differences attributed to tied responses account for 61.7–95.5% of dominance groups. Differences attributed to distinct outcome classes are more frequent initially (12.3%, 22.9%, and 27.3% on IFM5, MulDimIF, and MathIF) than at the POLPO endpoint (5.8%, 1.1%, and 7.6%). These shares describe objective structure on sampled groups, rather than measured differences in model performance.

PolicyDominance groupsSameDifferent: tied responsesDifferent: distinct outcome classes
IFM5
Initial4717.280.512.3
POLPO final1385.888.45.8
MulDimIF
Initial5982.274.922.9
POLPO final893.495.51.1
MathIF, thinking enabled
Initial28211.061.727.3
POLPO final1976.685.87.6

Table 20. POLPO versus GraphDPO objectives on instruction-following groups with at least one dominance pair. Percentages use the number of dominance groups in each row as the denominator. “Same” means equal up to a constant factor; the other columns distinguish differences attributed to tied responses and to distinct outcome classes, as in Figure 10.

Dominance-pair counts during training. Figure 11 tracks the mean number of strict dominance pairs per group, conditional on the group containing at least one such pair. From the first to the last reported window, the mean changes from 42.8 to 36.6 for IFM5 and from 42.7 to 31.4 for MulDimIF. For MathIF with thinking enabled, it changes from 14.1 in steps 1–20 to 11.9 in steps 321–325. These are conditional pair counts; they do not measure the fraction of groups that provide a learning signal. Group sizes differ across the datasets, so the maximum possible number of pairs is 120 for IFM5 and MulDimIF (N=16N = 16), but 28 for MathIF (N=8N = 8).

Largest incomparability component at the endpoints. For the initial policy and the final POLPO checkpoint, Table 21 summarizes the largest connected component of the incomparability graph within each group that contains a dominance pair. The graph connects responses that are incomparable under Pareto dominance (Appendix § 11.§ 3). These snapshots use responses sampled from training prompts with seed 43. Among the selected groups, the mean largest-component size changes from 8.9 to 10.7 for IFM5, from 10.9 to 11.6 for MulDimIF, and from 4.4 to 5.1 for MathIF with thinking enabled. The initial and final statistics are conditioned on their respective dominance groups; they describe the sampled group structures rather than changes within a fixed set of groups.

PolicyNNnnMeanMedianP95Max
IFM5
Initial164718.9101516
POLPO final1613810.7131516
MulDimIF
Initial1659810.9121516
POLPO final168911.6131515
MathIF, thinking enabled
Initial82824.4478
POLPO final81975.1678

Table 21. Largest incomparability-component size per group containing at least one dominance pair, for initial-policy and POLPO-final rollouts sampled from training prompts with seed 43. NN is the number of responses per group and nn is the number of groups in the conditional subset. P95 is the 95th percentile.

Additional MathIF Results

With thinking disabled, POLPO achieves the highest overall Joint score among the reported methods: 21.4%, compared with 19.3% for GRPO–Rate and 20.2% for GRPO–All (Table 6). The following breakdowns show where these gains arise. With thinking enabled, POLPO reaches 33.8% Joint, compared with 30.7% for GRPO–Rate and 22.6% for GRPO–All. The non-thinking breakdowns are discussed first; the thinking-mode breakdowns follow in Table 24 and Table 25.

MethodHAccAccJoint
K=1K = 1K=2K = 2K=3K = 3K=1K = 1K=2K = 2K=3K = 3K=1K = 1K=2K = 2K=3K = 3
Initial model40.022.912.931.422.121.412.93.62.1
GRPO–All50.740.035.031.425.724.329.320.018.6
GRPO–Rate81.470.060.042.936.437.137.127.927.1
GDPO69.359.347.133.625.732.129.320.020.7
GraphDPO68.655.045.733.625.730.731.421.421.4
DPO–Pareto87.174.356.445.037.138.640.028.627.1
POLPO87.979.367.145.737.137.940.730.730.0

Table 24. MathIF results (%) by constraint count KK with thinking enabled and a 16,384-token evaluation response limit, with 140 examples per count. HAcc measures complete constraint satisfaction, Acc measures mathematical correctness, and Joint requires both. Bold indicates the best result among the methods shown in each column.

SourceKKnnInitialGRPO–AllGRPO–RateGDPOGraphDPODPO–ParetoPOLPO
GSM8K13030.046.773.353.350.070.060.0
GSM8K23010.033.350.033.340.053.346.7
GSM8K3303.320.036.733.326.743.350.0
GSM8KAll9014.433.353.340.038.955.652.2
MATH-50013016.760.063.356.763.363.370.0
MATH-5002303.330.040.033.336.746.756.7
MATH-5003300.040.043.333.333.340.056.7
MATH-500All906.743.348.941.144.450.061.1
Minerva1303.36.713.33.313.316.76.7
Minerva2303.310.016.710.06.710.010.0
Minerva3303.33.313.33.36.73.33.3
MinervaAll903.36.714.45.68.910.06.7
OlympiadBench1306.720.020.020.016.730.040.0
OlympiadBench2300.010.016.76.710.013.323.3
OlympiadBench3303.316.730.026.730.033.330.0
OlympiadBenchAll903.315.622.217.818.925.631.1
AIME1205.05.05.05.05.010.020.0
AIME2200.015.010.015.010.015.010.0
AIME3200.010.05.00.05.010.00.0
AIMEAll601.710.06.76.76.711.710.0

Table 25. MathIF joint success (%) by source and constraint count with thinking enabled and a 16,384-token evaluation response limit. Joint success requires mathematical correctness and satisfaction of every instruction constraint. Rows marked All pool the three constraint counts for that source.

Satisfying multiple constraints while answering correctly. Table 22 shows that POLPO achieves the highest complete constraint satisfaction (HAcc) at every constraint count. For two and three constraints, its Joint scores are 17.1% and 17.9%, compared with 13.6% and 14.3% for GRPO–Rate. With three constraints, both methods have the same mathematical accuracy at the reported precision (27.1%), but POLPO has higher Joint success. Thus, more of POLPO’s mathematically correct responses also satisfy every instruction constraint. POLPO matches GRPO–All in Joint success at one constraint and exceeds it at two and three constraints. GRPO–All has higher mathematical accuracy at two and three constraints, while GRPO–Rate leads on accuracy at one constraint. These results show an advantage in meeting the combined requirements of correctness and instruction adherence. The advantage over GRPO–Rate is concentrated in the multiple-constraint settings: with one constraint, POLPO’s Joint score is slightly lower (29.3% versus 30.0%).

KKHAccH_{\mathrm{Acc}}AccAccJointJoint
KKInit.AllRatePOLPOInit.AllRatePOLPOInit.AllRatePOLPO
156.478.685.789.315.032.933.630.710.729.330.029.3
222.950.069.378.610.025.720.722.92.915.713.617.1
314.338.672.976.416.435.727.127.13.615.714.317.9

Table 22. MathIF results (%) by constraint count, with 140 examples per count. Within each metric, columns are the initial model (Init.), GRPO–All (All), GRPO–Rate (Rate), and POLPO (POLPO). All models use non-thinking mode.

Results across benchmark sources. Table 23 shows that POLPO exceeds GRPO–Rate in pooled Joint success on all five benchmark sources and achieves or ties the highest score on four of them. On MATH-500, POLPO reaches 37.8%, compared with 35.6% for GRPO–Rate and 33.3% for GRPO–All; on Minerva, it reaches 8.9%, compared with 5.6% and 6.7%, respectively. On OlympiadBench, POLPO reaches 13.3%, compared with 12.2% for GRPO–All and 11.1% for GRPO–Rate. On AIME, only POLPO obtains a joint success, although this amounts to just one of the 60 examples. GSM8K is the exception to POLPO’s leading pooled score: its 38.9% exceeds GRPO–Rate (37.8%) but remains below GRPO–All (42.2%). The improvements over GRPO–Rate therefore occur across sources, while the comparison with GRPO–All depends on the source.

SourceKKnnInitialGRPO–AllGRPO–RatePOLPO
GSM8K13026.756.760.063.3
GSM8K23010.033.323.323.3
GSM8K3306.736.730.030.0
GSM8KAll9014.442.237.838.9
MATH-50013016.750.060.053.3
MATH-5002303.330.026.733.3
MATH-5003303.320.020.026.7
MATH-500All907.833.335.637.8
Minerva1306.710.06.76.7
Minerva2300.06.76.713.3
Minerva3303.33.33.36.7
MinervaAll903.36.75.68.9
OlympiadBench1300.020.013.313.3
OlympiadBench2300.03.36.710.0
OlympiadBench3303.313.313.316.7
OlympiadBenchAll901.112.211.113.3
AIME1200.00.00.00.0
AIME2200.00.00.00.0
AIME3200.00.00.05.0
AIMEAll600.00.00.01.7

Table 23. MathIF joint success (%) by source and constraint count. Joint success requires mathematical correctness and satisfaction of every instruction constraint. All models use non-thinking mode. Rows marked All pool the three constraint counts for that source.

Thinking-mode breakdowns. With thinking enabled, POLPO has the highest HAcc at each constraint count among the methods shown in Table 24. Its Joint scores are 40.7%, 30.7%, and 30.0% for one, two, and three constraints, respectively, compared with 40.0%, 28.6%, and 27.1% for DPO–Pareto and 37.1%, 27.9%, and 27.1% for GRPO–Rate. Across sources, POLPO leads the methods shown on MATH-500 and OlympiadBench; DPO–Pareto leads on GSM8K and AIME, and GRPO–Rate leads on Minerva. The source subsets are small, especially AIME (n=60n = 60).

Extended Related Work

This appendix complements Section 5 with related optimization and evaluation methods beyond the direct comparison between scalar aggregation and partial-order likelihoods in multi-verifier RLVR.

Additional Approaches to Multiple Verification Signals

IFEval provides automatically checkable instruction constraints that underpin later work on verifiable instruction following (Zhou et al., 2023). VerIF combines code-based checks for hard constraints with language-model judgments for soft constraints, then aggregates their outcomes for GRPO training [26]; its feedback therefore includes learned judgments as well as executable checks. MDP-GRPO uses the mean constraint-satisfaction reward and modifies sampling and advantage estimation to address difficult reward distributions in multi-constraint instruction following [31].

Beyond the aggregation methods discussed in the main text, GD2^{2}PO addresses conflicts between component advantages through rollout masking and prompt reweighting [16]. Blockwise advantage estimation applies objective-specific advantages to the corresponding output segments [25]. These approaches show that using multiple rewards need not mean assigning one undifferentiated signal to every token. POLPO addresses a different design choice: it uses comparisons between complete responses, without assuming a correspondence between verification criteria and output segments.

Policy Optimization and Listwise RLVR

Reinforcement learning from human feedback trains policies using learned preference rewards [23], while RLVR obtains feedback from automatic verification [12, 7]. GRPO constructs advantages from rewards within a response group [33] and uses the clipped policy surrogate of PPO [32]. See Appendix § 9.§ 2 for the definitions needed for the gradient comparison in this paper.

Listwise Policy Optimization interprets group-based RLVR as projection onto target distributions over sampled responses [29]. Its targets are constructed from scalar rewards, and its update coefficients can depend on current policy scores and sum to zero within the group. These properties are therefore not unique to POLPO. The distinction is the source of the coefficients: POLPO differentiates the probability of a verifier-induced partial-order event, marginalizing over compatible complete rankings rather than projecting onto a scalar-reward target distribution.

Listwise and Set-Level Preference Optimization

DPO uses policy-to-reference log-probability ratios in a Bradley–Terry comparison model and extends this construction to complete rankings with the Plackett–Luce model [30]. The complete-ranking negative log-likelihood is the ListMLE loss [37]; ListNet provides another listwise learning-to-rank formulation [4]. PRO [34] and LiPO [20] bring learning from ranked or scored response lists to language-model alignment. POLPO instead specifies a partial-order event and sums the probabilities of the complete rankings that satisfy it.

Related methods also learn from sets rather than individual pairs. In recommendation, S-DPO contrasts one positive item with several negatives, corresponding to the PL probability that the positive is selected first [5]. Mult-DPO handles multiple positives, negatives, and preference levels with a multinomial surrogate that upper-bounds the corresponding marginalized PL loss (Zhu et al., 2026). Multi-Preference Optimization generalizes Bradley–Terry comparisons to chosen and rejected sets [8]. These set-based objectives address particular comparison structures. The PL likelihood for a general partial order, formed by summing over compatible complete rankings, is established in the ranking literature [15]; ordered-partition likelihoods have also been studied explicitly [22]. POLPO adopts this probabilistic construction for verifier-induced comparisons between model responses and optimizes it through DPO-style policy scores in an online sampling-and-update procedure.

Verifier-Guided Preferences and Prompt Optimization

Verifier outcomes can also generate pairwise preference data for reasoning. Iterative Reasoning Preference Optimization pairs correct and incorrect responses and adds a negative log-likelihood term on the correct response [24]. DPO-VP constructs correct–incorrect pairs from binary verifiable rewards and trains iteratively [35]. These methods connect verification to preference optimization, while POLPO uses the comparison structure of a response group and models its specified comparisons as one ranking event.

ParetoPrompt uses dominance relations between prompts for preference-based policy optimization (Zhao et al., 2025). This is related through its use of multiple criteria, but its optimization objects are prompts. POLPO constructs comparisons between responses to the same prompt and updates the response policy through their joint partial-order likelihood.

References

  1. [1]Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton. Program synthesis with large language models. arXiv preprint arXiv:2108.07732, 2021. doi: 10.48550/arXiv.2108.07732. URL https://arxiv.org/abs/2108.07732.
  2. [2]Ryan Bahlous-Boldi, Isha Puri, Idan Shenfeld, Akarsh Kumar, Mehul Damani, Sebastian Risi, Omar Khattab, Zhang-Wei Hong, and Pulkit Agrawal. Vector policy optimization: Training for diversity improves test-time search. arXiv preprint arXiv:2605.22817, 2026. doi: 10.48550/arXiv.2605.22817. URL https://arxiv.org/abs/2605.22817.
  3. [3]Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3–4):324–345, 1952. doi: 10.1093/biomet/39.3-4.324. URL https://doi.org/10.1093/biomet/39.3-4.324.
  4. [4]Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li. Learning to rank: From pairwise approach to listwise approach. In Proceedings of the 24th International Conference on Machine Learning, pp. 129–136. Association for Computing Machinery, 2007. doi: 10.1145/1273496.1273513. URL https://doi.org/10.1145/1273496.1273513.
  5. [5]Yuxin Chen, Junfei Tan, An Zhang, Zhengyi Yang, Leheng Sheng, Enzhi Zhang, Xiang Wang, and Tat-Seng Chua. On softmax direct preference optimization for recommendation. In Advances in Neural Information Processing Systems, volume 37, pp. 27463–27489. Curran Associates, Inc., 2024. doi: 10.52202/079017-0863. URL https://proceedings.neurips.cc/paper_files/paper/2024/hash/30732ddb12d9faf7180f5d0e8b5b5da7-Abstract_Conference.html.DOI
  6. [6]Tingchen Fu, Yafu Li, Jiawei Gu, Xiaoye Qu, and Yu Cheng. Scaling reasoning, losing control: Evaluating instruction following in large reasoning models. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 40445–40463. Association for Computational Linguistics, 2026. doi: 10.18653/v1/2026.acl-long.1878. URL https://aclanthology.org/2026.acl-long.1878/.
  7. [7]Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, et al. DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning. Nature, 645:633–638, 2025. doi: 10.1038/s41586-025-09422-z. URL https://www.nature.com/articles/s41586-025-09422-z.DOI
  8. [8]Taneesh Gupta, Rahul Madhavan, Xuchao Zhang, Nagarajan Natarajan, Chetan Bansal, and Sar-van Rajmohan. Multi-preference optimization: Generalizing DPO via set-level contrasts. arXiv preprint arXiv:2412.04628, 2024. doi: 10.48550/arXiv.2412.04628. URL https://arxiv.org/abs/2412.04628.
  9. [9]Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. Measuring coding challenge competence with APPS. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, volume 1, 2021a. URL https://datasets-benchmarks-proceedings.neurips.cc/paper/2021/hash/c24cd76e1ce41366a4bbe8a49b02a028-Abstract-round2.html.
  10. [10]Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In J. Vanschoren and S. Yeung (eds.), Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, volume 1, 2021b. URL https://datasets-benchmarks-proceedings.neurips.cc/paper/2021/hash/be83ab3ecd0db773eb2dc1b0a17836a1-Abstract-round2.html.
  11. [11]Jian Hu, Jason Klein Liu, Haotian Xu, and Wei Shen. REINFORCE++: Stabilizing critic-free policy optimization with global advantage normalization. arXiv preprint arXiv:2501.03262, 2025. doi: 10.48550/arXiv.2501.03262. URL https://arxiv.org/abs/2501.03262.
  12. [12]Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James Validad Miranda, Alisa Liu, Nouha Dziri, Xinxi Lyu, Yuling Gu, Saumya Malik, Victoria Graf, Jena D. Hwang, Jiangjiang Yang, Ronan Le Bras, Oyvind Tafjord, Christopher Wilhelm, Luca Soldaini, Noah A. Smith, Yizhong Wang, Pradeep Dasigi, and Hanneah Hajishirzi. Tulu 3: Pushing frontiers in open language model post-training. In Second Conference on Language Modeling, 2025. URL https://openreview.net/forum?id=1iUbGfHHpH.arxiv.org/abs/2411.15124
  13. [13]Junyi Li, Xiaowei Qian, Yingyi Zhang, Wenlin Zhang, Guojing Li, Sheng Zhang, Xiao Han, Yichao Wang, and Xiangyu Zhao. Towards Pareto-optimal tool-integrated agents with Pareto ranking policy optimization. In Proceedings of the 43rd International Conference on Machine Learning, 2026a. URL https://openreview.net/forum?id=9sg34nj13o.arxiv.org/abs/2606.16111
  14. [14]Xin-Ye Li, Ren-Biao Liu, Yun-Ji Zhang, Hui Sun, Zheng Xie, and Ming Li. Exploring pass-rate reward in reinforcement learning for code generation. arXiv preprint arXiv:2605.02944, 2026b. doi: 10.48550/arXiv.2605.02944. URL https://arxiv.org/abs/2605.02944.
  15. [15]Ao Liu, Zhibing Zhao, Chao Liao, Pinyan Lu, and Lirong Xia. Learning Plackett-Luce mixtures from partial preferences. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):4328–4335, 2019. doi: 10.1609/aaai.v33i01.33014328.DOI
  16. [16]Haotian Liu, Yihao Liu, Jingwei Ni, Siyuan Huang, Xinpeng Liu, Pengyu Cheng, Jiajun Song, Ruijin Ding, Junfeng Li, Zhechao Yu, Mengyu Zhou, Hongteng Xu, Xiaoxi Jiang, and Guanjun Jiang. GD²PO: Mitigating multi-reward conflicts via group-dynamic reward-decoupled policy optimization. arXiv preprint arXiv:2606.16771, 2026a. doi: 10.48550/arXiv.2606.16771. URL https://arxiv.org/abs/2606.16771.
  17. [17]Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Lingming Zhang. Is your code generated by ChatGPT really correct? rigorous evaluation of large language models for code generation. In Advances in Neural Information Processing Systems, volume 36, pp. 21558–21572. Curran Associates, Inc., 2023. doi: 10.52202/725280-0943. URL https://papers.neurips.cc/ paper_files/paper/2023/hash/43e9d647ccd3e4b7b5baab53f0368686—Abstract—Conference.html.
  18. [18]Ning Liu, Chuanneng Sun, Kristina Klinkner, and Shervin Malmasi. Beyond pairs: Your language model is secretly optimizing a preference graph. arXiv preprint arXiv:2605.08037, 2026b. doi: 10.48550/arXiv.2605.08037. URL https://arxiv.org/abs/2605.08037.
  19. [19]Shih-Yang Liu, Xin Dong, Ximing Lu, Shizhe Diao, Peter Belcak, Mingjie Liu, Min-Hung Chen, Hongxu Yin, Yu-Chiang Frank Wang, Kwang-Ting Cheng, Yejin Choi, Jan Kautz, and Pavlo Molchanov. GDPO: Group reward-decoupled normalization policy optimization for multi-reward RL optimization. In Proceedings of the 43rd International Conference on Machine Learning, 2026c. URL https://openreview.net/forum?id=Y1rHxA58If.arxiv.org/abs/2601.05242
  20. [20]Tianqi Liu, Zhen Qin, Junru Wu, Jiaming Shen, Misha Khalman, Rishabh Joshi, Yao Zhao, Mohammad Saleh, Simon Baumgartner, Jialu Liu, Peter J. Liu, and Xuanhui Wang. LiPO: List-wise preference optimization through learning-to-rank. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 2404–2420. Association for Computational Linguistics, 2025. doi: 10.18653/v1/2025.naacl-long.121. URL https://aclanthology.org/2025.naacl-long.121/.DOI
  21. [21]R. Duncan Luce. Individual Choice Behavior: A Theoretical Analysis. John Wiley & Sons, New York, 1959. URL https://books.google.com/books?id=a80DAQAAIAAJ.
  22. [22]Jiaqi Ma, Xinyang Yi, Weijing Tang, Zhe Zhao, Lichan Hong, Ed Chi, and Qiaozhu Mei. Learning-to-rank with partitioned preference: Fast estimation for the Plackett–Luce model. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 928–936. PMLR, 2021. URL https://proceedings.mlr.press/v130/ma21a.html.arxiv.org/abs/2006.05067
  23. [23]Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, volume 35, pp. 27730–27744. Curran Associates, Inc., 2022. doi: 10.52202/068431-2011. URL https://papers.nips.cc/paper_files/paper/2022/hash/b1efde53be364a73914f58850a001731-Abstract-Conference.html.DOI
  24. [24]Richard Yuanzhe Pang, Weizhe Yuan, Kyunghyun Cho, He He, Sainbayar Sukhbaatar, and Jason Weston. Iterative reasoning preference optimization. In Advances in Neural Information Processing Systems, volume 37, pp. 116617–116637. Curran Associates, Inc., 2024. doi: 10.52202/079017-3702. URL https://papers.nips.cc/paper_files/paper/2024/hash/d37c9ad425fe5b65304d500c6edcba00-Abstract-Conference.html.DOI
  25. [25]Kirill Pavlenko, Alexander Golubev, Simon Karasik, and Boris Yangel. Blockwise advantage estimation for multi-objective RL with verifiable rewards. arXiv preprint arXiv:2602.10231, 2026. doi: 10.48550/arXiv.2602.10231. URL https://arxiv.org/abs/2602.10231.
  26. [26]Hao Peng, Yunjia Qi, Xiaozhi Wang, Bin Xu, Lei Hou, and Juanzi Li. VerIF: Verification engineering for reinforcement learning in instruction following. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pp. 30324–30339. Association for Computational Linguistics, 2025. doi: 10.18653/v1/2025.emnlp-main.1542. URL https://aclanthology.org/2025.emnlp-main.1542/.DOI
  27. [27]R. L. Plackett. The analysis of permutations. Journal of the Royal Statistical Society: Series C (Applied Statistics), 24(2):193–202, 1975. doi: 10.2307/2346567. URL https://academic.oup.com/jrsssc/article/24/2/193/6953554.DOI
  28. [28]Valentina Pyatkin, Saumya Malik, Victoria Graf, Hamish Ivison, Shengyi Huang, Pradeep Dasigi, Nathan Lambert, and Hannaneh Hajishirzi. Generalizing verifiable instruction following. In Advances in Neural Information Processing Systems, volume 38, 2025. doi: 10.52202/085713-1 645. URL https://proceedings.neurips.cc/paper_files/paper/2025/hash/46499a0622ecf568b72d17b61e45dbd5-Abstract_Datasets_and_Benchmarks_Track.html. Datasets and Benchmarks Track.
  29. [29]Yun Qu, Qi Wang, Yixiu Mao, Heming Zou, Yuhang Jiang, Yingyue Li, Wutong Xu, Lizhou Cai, Weijie Liu, Clive Bai, Kai Yang, Yangkun Chen, Saiyong Yang, and Xiangyang Ji. Listwise policy optimization: Group-based RLVR as target-projection on the LLM response simplex. arXiv preprint arXiv:2605.06139, 2026. doi: 10.48550/arXiv.2605.06139. URL https://arxiv.org/abs/2605.06139.
  30. [30]Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 53728–53741. Curran Associates, Inc., 2023. doi: 10.52202/075280-2338. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/a85b405ed65c6477a4fe8302b5e06ce7-Paper-Conference.pdf.DOI
  31. [31]Mohammad Mahdi Salmani-Zarchi, Zahra Rahimi, Hesham Faili, and Mohammad Javad Dousti. MDP-GRPO: Stabilized group relative policy optimization for multi-constraint instruction following. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 42784–42797. Association for Computational Linguistics, 2026. doi: 10.18653/v1/2026.acl-long.1982. URL https://aclanthology.org/2026.acl-long.1982/.
  32. [32]John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. doi: 10.48550/arXiv.1707.06347. URL https://arxiv.org/abs/1707.06347.
  33. [33]Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. DeepSeekMath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024. doi: 10.48550/arXiv.2402.03300. URL https://arxiv.org/abs/2402.03300.
  34. [34]Feifan Song, Bowen Yu, Minghao Li, Haiyang Yu, Fei Huang, Yongbin Li, and Houfeng Wang. Preference ranking optimization for human alignment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 18990–18998, 2024. doi: 10.1609/aaai.v38i17.29865. URL https://ojs.aaai.org/index.php/AAAI/article/view/29865.DOI
  35. [35]Songjun Tu, Jiahai Lin, Xiangyu Tian, Qichao Zhang, Lining Li, Yuqian Fu, Nan Xu, Wei He, Xianguan Lan, Dongmei Jiang, and Dongbin Zhao. Enhancing LLM reasoning with iterative DPO: A comprehensive empirical investigation. In Second Conference on Language Modeling, 2025. URL https://openreview.net/forum?id=OgWh4J7bkT.arxiv.org/abs/2503.12854
  36. [36]Longwen Wang, Yirui Liu, Xuan’er Wu, Xiaohui Hu, Yuankai Fan, Kaidong Yu, Qizhen Weng, Wei Xi, and Xuelong Li. Beyond binary: Turning partial success into dense verifiable rewards for reinforcement learning in code generation. arXiv preprint arXiv:2601.03525, 2026. doi: 10.48550/arXiv.2601.03525. URL https://arxiv.org/abs/2601.03525.
  37. [37]Fen Xia, Tie-Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li. Listwise approach to learning to rank: Theory and algorithm. In Proceedings of the 25th International Conference on Machine Learning, pp. 1192–1199. Association for Computing Machinery, 2008. doi: 10.1145/1390156.1390306. URL https://doi.org/10.1145/1390156.1390306.
  38. [38]Junjie Ye, Caishuang Huang, Zhuohan Chen, Wenjie Fu, Chenyuan Yang, Leyi Yang, Yilong Wu, Peng Wang, Meng Zhou, Xiaolong Yang, Tao Gui, Qi Zhang, Zhongchao Shi, Jianping Fan, and Xuanjing Huang. MulDimLF: A multi-dimensional constraint framework for evaluating and improving instruction following in large language models. In Findings of the Association for Computational Linguistics: ACL 2026, pp. 2078–2104. Association for Computational Linguistics, 2026. doi: 10.18653/v1/2026.findings-acl.99. URL https://aclanthology.org/2026.findings-acl.99/.DOI

Paper details

vlnc:W_7mdqhza2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Code, Codex

View statement
Looking for related papers…
Contents