acceptodds
Under review as a conference paper at ICLR 2027

Axiom Satisfiability of Linear Rewards in Alignment

Abstract

Learning from human preference data is the dominant route to aligning language models with human values. In the linear social choice model, where rewards are linear in a fixed feature representation of prompt-response pairs, Ge et al. (2024) show that fitting such a reward by minimizing any non-decreasing convex loss, including Bradley-Terry-Luce (BTL), fails Pareto Optimality (PO) and Pairwise Majority Consistency (PMC). Moreover, no rule reading only the majority relation can satisfy PO once the output is required to be linearly induced. We ask what it costs to enforce these axioms anyway. To this end, we relax the linear model to allow per-candidate additive slack. We compute the relaxed linear reward with the smallest total slack that satisfies the axioms with a margin , the minimum required difference between two reward values. Our solution satisfies the axioms under no assumptions about the voters or how comparisons were collected. We bound the optimal total slack by when is at most for candidates. Furthermore, we exhibit an instance that forces this bound, concluding that the rate is tight up to constants. In practice, the number of candidates far exceeds the feature dimension, and only a linear reward can be evaluated on unseen responses. We therefore introduce a new method that charges the linear part for each comparison it gets wrong. It simultaneously minimizes the total slack and the number of violations, with a parameter that trades off between them. We show that the total slack is monotone but saturating in : raising it reduces the violations of the deployed linear reward and increases the slack, yet the slack stays below , where and are the diameter and dimension of the features, respectively. Experiments on both synthetic and real-life preference data with per-annotator labels corroborate our theoretical result and show that the linear reward output by our method beats linear BTL.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
linear reward model, social choice theory, social choice axiom, ai alignment

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_pn7QOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper extends Ge et al (2024) by asking how much we need to depart from a linear reward representation in order to satisfy desirable social choice axioms. In particular, it focuses on PO and PMC, and adds (candidate-specific) corrections to the linear reward, minimizing their total size (in L1) subject to satisfying these axioms. I view this essentially as measuring the "cost of enforcing the axioms relative to a given representation" -- if the linear class cannot realize the required ranking, how much (candidate-specific) deviation from linearity is needed to make it possible?

Critical strengths

I think overall the problem is interesting and well motivated.

Critical weaknesses
  • While it is possible I did not follow the mathematical derivation correctly, I believe that some of the claims made in Section 4.1 are either incomplete or not correct when taken at face value. Specifically, the variable uabu_{ab} (line 293) is defined as a binary variable that equals one if ⟨θ,xa−xb⟩<η\langle \theta, x_a-x_b\rangle < \eta. This is not the same thing as the number of reversed pairs -- a pair can be ranked in the correct order, with $0 < \langle \theta, x_a-x_b\rangle < \eta$ and still have uab=1u_{ab}=1. This seems to affect the interpretation of uu as KT distance throughout Section 4.1, including Lemmas 3--4.

  • My main conceptual pushback is about generalization, or more broadly the extent to which this problem is useful to study. In alignment, the reason we need to learn a reward function from a restricted hypothesis class is that the candidate space is effectively unbounded. We only observe preferences over a tiny set of responses, but the learned reward must ultimately score new responses. I view the linear model in Ge et al. (and the polynomial extension in Hollender and Kraiczy) mainly as tractable cases for studying this more general issue -- the reward model needs enough shared structure to generalize to unseen candidates, but that same restriction can constrain which aggregate rankings it can represent.

From this perspective, I am not sure how to interpret candidate-specific "slack" as addressing the same issue. Giving every observed candidate its own free correction makes essentially any finite ranking realizable, but those corrections contain no shared structure that tells us how to score a new candidate. In that sense, the "slack" solves the finite-sample representation problem partly through memorization, while the original alignment problem is precisely to find a representation that generalizes beyond the finite candidate set.

  • I found the motivation around Example 1 somewhat misleading -- the key issue in Ge et al is not that something like PO/PMC may be impossible to realize within the linear class -- a PO-respecting linear reward always exists. The negative result is that standard loss-based aggregation can nevertheless select a linear reward that violates PO. In other words, the issue is the aggregation rule, not a lack of representational capacity. Example 1 instead illustrates a different failure mode, where the desired ranking itself lies outside the linear class. I think the paper should distinguish these two issues more clearly in the introduction.

  • When the paper relaxes uabu_{ab} from a binary variable to a continuous variable in LP3, the resulting objective term is essentially hinge loss. This is already a well-known loss in this setting -- in particular, Ge et al explicitly consider hinge loss as a special case of their loss-based framework. So the hinge-loss component of LP3 does not itself seem conceptually new. The potentially new component is combining this loss with the candidate-specific slack and the preprocessing of the majority graph. I think the paper should clarify what this combination provides beyond standard hinge-loss optimization.

Questions for authors
  • Could you address my concern about the theoretical derivation in Section 4?

  • In Ge et al., PMC requires the output to agree with the majority ranking only when such a ranking exists and is realizable by a linear reward. In your model, the latter requirement seems to disappear because the candidate-specific slack makes any ranking over the observed candidates realizable. Could you clarify whether your definition of PMC is intentionally stronger than the one in Ge et al.? In particular, if the majority relation is acyclic but cannot be represented by any linear reward, Ge et al.'s PMC does not require the linear model to realize it, while your Def 1 does require the slack-augmented reward to realize it. If so, how should we interpret the statement that LP2 and LCPO satisfy the "same axioms"?

3 comments

We thank the reviewer for useful feedback, comments, and careful reading.

Theoretical derivation in Section 4: Correct. In the ILP, Eqn 7 should, ideally, be uabL>−⟨θxa−xb⟩u_{ab}L > -\langle\mathbf{\theta} x_a-x_b\rangle. This does not affect the proof of Lemma 3 and Lemma 4. We will update the equation.In LP3, for implemneting the strict inequality we write, uabL≥η−⟨θxa−xb⟩u_{ab}L \geq \eta -\langle\mathbf{\theta} x_a-x_b\rangle. Note that η\eta is a hyperparameter and we can set η<κ\eta < \kappa as defined in Section 4.2. Then, there cannot be a pair (a,b)(a,b) such that 0<⟨θ,xa−xb⟩<η0 < \langle \theta, x_a - x_b\rangle < \eta.

Generalization: The augmented reward (θ,ε)(\theta, \varepsilon) satisfies PO and PMC exactly on the observed comparisons, with no assumption on the voters or the feature geometry. No loss-based rule, including BTL, offers this guarantee. The linear part θ\theta is the deployable object, and the held-out results characterize how it transfers to new prompts. Extending exact axiom satisfaction beyond the observed comparisons is the natural next question. Our framework makes it precise, since the slack identifies the generalizing representation of which candidates would need to be corrected. We conjecture that on unrestricted data, the performance of our model could be comparable to that of loss-based models, e.g., BTL. However, as shown in Hollender et al., the main open question is identifying restrictions on preferences when the performance of loss-based models and our model differ.

Candidate-specific slack: Since we have no assumptions about the behavior of the data, it may be that no linear reward model can produce the ranking required to satisfy the PO and majority constraints. Previous work by Ge et al. and by Hollender and Kraiczy both assumes restrictions on the data. Even if we assume that there is a ground truth θ0\theta_0 and the required ranking can be modeled by it, the data might have noise, and thus we don't get a linearly realizable input. The slack values let us obtain a θ\theta close to θ0\theta_0.

Example 1: We do not claim in Example 1 that Ge et al. fail in the linear class. However, the human preferences may not be in the linear class. Our main contribution is to design a rule that can be applied even when the preferences cannot be modeled by a linear reward function. To understand the difference between our rule and Ge et al., consider this: The first step of leximax Copeland in Ge et al. is "It ranks first the candidate with the highest Copeland score that can be feasibly ranked first under some parameter vector θ." Now consider the execution of this step on Example 1 where the human feedback is b>c>ab>c>a. There is no value of θ∈R\theta \in \mathbb{R} such that bb comes first, as explained in Example 1. Thus, PO is not satisfied. We have explained it at the end of Section 3. This also shows that a PO-respecting linear reward does not always exist. We will clarify it in the introduction.

LP3 and Hinge loss are not the same. LP3 uses a scaled pairwise hinge-loss penalty, with an additional optimization objective minimizing slack and explicitly enforcing PO and PMC using corrected rewards. The standard pairwise hinge loss for a PO or majority pair ℓhinge(θ;a,b)=max⁡0,η−⟨θ,xa−xb⟩\ell_{\mathrm{hinge}}(\theta;a,b)=\max\\{0,\eta-\langle\theta,x_a-x_b\rangle\\}. This loss penalizes a pair whenever the candidate aa does not achieve the required margin η\eta over candidate bb. In LP3, the relaxed variable uab≥0u_{ab}\geq 0 satisfies Luab≥η−⟨θ,xa−xb⟩L u_{ab}\geq \eta-\langle\theta,x_a-x_b\rangle. Consequently, LP3 can be rewritten as: min⁡θ,ϵ∑i=1m∣ϵi∣+λL∑(a,b)∈Pℓhinge(θ;a,b)\quad\min_{\theta,\epsilon}\sum_{i=1}^{m}|\epsilon_i|+\frac{\lambda}{L}\sum_{(a,b)\in P}\ell_{\mathrm{hinge}}(\theta;a,b) s.t ⟨θ,xa−xb⟩+(ϵa−ϵb)≥η,∀(a,b)∈P\langle\theta,x_a-x_b\rangle+(\epsilon_a-\epsilon_b)\geq\eta, \forall(a,b)\in P, and the remaining constraints of LP3. In other words, LP3 can be viewed as a regularized pairwise hinge loss formulation, where the regularization is not simply an L1L_1 or L2L_2 penalty on θ\theta. Instead, it minimizes the L1L_1-norm of candidate-wise slack ϵ\epsilon, while requiring those corrections to ensure the axioms. We will add the relation to hinge loss for clarification. Furthermore, our experiments showed that linear hinge loss performs worse than LP3. We added this in the experiments as well (See reply for reviewer CW6f).

PMC Definition: You are correct that ours is stronger. An axiom definition should not be model dependent. The PMC axiom in Ge et al. assumes the output ranking is linearly feasible, i.e., the human preference profile is linearly realizable. We intentionally write the standard definition, which is independent of the model. The claim that LP2 and LCPO satisfy "the same axioms" is removed. The accurate statement is: LCPO's linear reward satisfies conditional PMC; LP2's augmented reward satisfies unconditional PMC; and LP2's slack is zero exactly when its linear part alone suffices at margin η\eta.

Thank you for the response. Your clarification on PMC makes sense to me and resolves my concern. On Section 4, I agree that the issue looks fixable. I would just clarify when a correctly ranked pair can still count as a violation.

More broadly, I see the value of asking how much the scores need to change to satisfy the axioms on a given set of candidates. What is still unclear to me is whether learning those corrections helps the model rank new responses.

Thank you for the thoughtful response.

Finding generalization using the slack varaibles/correction is the next direction of research. We have already shown in Section 4.2 how the correction variables help us find a certificate of realizability based on the feature geometry. It should also be noted that in Proposition 4, we have shown that using the dual variable of <θ,xa−xb>+(εa−εb)−η≥0<\theta, x_a - x_b> + (\varepsilon_a - \varepsilon_b) - \eta \ge 0, i.e., μab\mu_{ab} helps us to get the linear realizability characteristic based on the feature values (feature-balanced flow). So, finding the characteristic of the feature geometry will give a much stronger result than Hollender et al. (2026).

Reviewer_CW6fOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies whether linear reward models can satisfy social choice axioms such as Pareto Optimality (PO) and Pairwise Majority Consistency (PMC). The authors add a slack term to each candidate's linear reward and solve a linear program for the smallest total slack that makes these axioms hold. When the majority graph has cycles, they first remove a feedback arc set. Since only the linear part can be used on new responses, they also propose LP3, which penalizes pairs that the linear part ranks wrongly. The paper gives bounds on the total slack and a condition for when a linear reward can satisfy all constraints. Experiments on synthetic and real preference data show fewer axiom violations than linear BTL.

Critical strengths
  1. Clear question and simple formulation

The paper asks a clear question: what does it take to enforce PO and PMC on a linear reward. The answer is a single linear program that is always feasible. Compared to LCPO, it does not need to assume that each voter’s ranking is linearly induced, and it solves one LP instead of O(m2)O(m^2).

  1. Clean realizability certificate

Proposition 2 uses Gordan’s theorem to give an exact condition for when a linear reward can satisfy all constraints. The flow view on the majority graph is easy to read and useful.

Critical weaknesses
  1. The evaluation is in-sample and favors the proposed method

LP3 directly penalizes the pairs that the linear part ranks wrongly. The reported metric is the violation rate on the same pairs. BTL instead optimizes likelihood. So LP3 is trained on the evaluation metric, and the comparison is not fair. More importantly, the paper’s motivation is that only θ\theta can be used on unseen responses, but no experiment tests θ\theta on held-out candidates or pairs. The BTL baseline also seems undertrained. It uses SLSQP with at most 100 iterations in 768 dimensions. In Table 1 its total violation rate is 17.51%, more than ten times that of LP3. With PCA-reduced features (Tables 2 and 3), the gap is much smaller, and BTL even has the lowest PO violations in several settings. I would like to see held-out evaluation, a BTL baseline trained to convergence, and a ranking SVM baseline that applies a hinge loss on the majority edges.

  1. The method is close to known ones

The paper says the total slack measures the cost of the axioms. But the slack size depends on two choices: the margin η\eta and the box ∥θ∥∞≤1\|\theta\|_\infty \le 1. Change them, and the slack changes too. In the experiments, η\eta is 10−510^{-5} and the slack is about 10−310^{-3}. That is almost zero, so the slack does not show much in practice. The bounds are also easy to get. For example, the upper bound comes from setting θ=0\theta = 0 and spacing the slack along one ranking. The O(1)O(1) bound when η≤1/m2\eta \le 1/m^2 is just rescaling. Last, if we drop the slack and relax the integer variables, the linear part of LP3 is trained with a hinge loss on the majority pairs. This is basically a ranking SVM. It is not clear what the method adds beyond that.

Questions for authors
  1. How does θ\theta from LP3 perform on candidates or pairs not used in the LP?

  2. How should the size of the total slack be read, given that it depends on η\eta and the box constraint? Does the ranking of methods change for larger η\eta?

2 comments

We thank the reviewer for useful feedback, comments, and careful reading.

Slack and η:\eta: Ideally, η\eta should be zero. We use η\eta to implement the strict inequality. Thus, η\eta is a hyperparameter that is set to an infinitesimally small number, definitely less than min⁡{1m2,1λ∣P∣}\min \{\frac{1}{m^2}, \frac{1}{\lambda|\mathcal{P}|}\}. Thus, the real upper bound on epsilon is governed by the remaining terms in Theorem 2.

In experiments, slack ∥ε⋆∥1\|\varepsilon^\star\|_1 is about 10−310^{-3} for η=10−5\eta=10^{-5} and changing η\eta would change the slack. So, one should look at the normalized slack ∥ε⋆∥1/η\|\varepsilon^\star\|_1/\eta, which is about 10210^2 in this case, showing its importance.

The main contribution is the design of a simple reward function and an algorithm that enable us to efficiently find a good θ\theta even when the data is not linearly realizable.

LP3 and Hinge loss: See the same section of the official comment to reviewer pn7Q.

BTL trained to convergence and SVM baseline: We trained linear BTL to convergence using L-BFGS-B, where we added an L2L_2 norm regularization over θ\theta. We also trained an SVM baseline that applies hinge loss on the majority edges with L2 regularization using the scikit-learn LinearSVC function. The experiment is done on the Habermas dataset under the same settings as in the main text (500 questions and 768 dimensions). We tabulate the violations below. We observe that LP3 has significantly fewer violations compared to the Linear BTL and Hinge baselines.

MethodTotal Violation (%)PO Violation (%)Majority Violation (%)∥ε∥1\|\varepsilon\|_1 (10−310^{-3})
LP22.08 ±\pm 1.700.95 ±\pm 0.712.44 ±\pm 2.052.07 ±\pm 1.53
LP31.73 ±\pm 1.480.47 ±\pm 0.442.15 ±\pm 1.852.52 ±\pm 1.89
Linear BTL27.52 ±\pm 1.0510.59 ±\pm 0.6333.26 ±\pm 1.24--
Linear Hinge19.84 ±\pm 1.262.50 ±\pm 0.4725.67 ±\pm 1.63--

Held-out evaluation: Thank you for this important suggestion. The augmented reward (θ,ε)(\theta, \varepsilon) satisfies PO and PMC exactly on the observed comparisons, with no assumption on the voters or the feature geometry. No loss-based rule, including BTL, offers this guarantee. The linear part θ\theta is the deployable object, and the held-out results characterize how it transfers to new prompts. Extending exact axiom satisfaction beyond the observed comparisons is the natural next question. Our framework makes it precise, since the slack identifies which candidates a generalizing representation would need to correct. We conjecture that on unrestricted data, our model's performance could be comparable to that of loss-based models, e.g., BTL. However, as shown in Hollender et al. (ICLR 2026), the main open question here is identifying restrictions on preferences when the performance of loss-based models and our model differ.

Effect of η\eta: (θ,ε)(\theta,\varepsilon) is feasible for LP2/LP3 at margin η\eta and box radius BB iff (cθ,cε)(c\theta,c\varepsilon) is feasible at (cη,cB)(c\eta,cB). So the slack depends on η/B\eta/B, up to an overall scale. Total slack should be read as normalized with respect to the ratio η/B\eta/B.

Reviewer_CW6fOpenReview ↗

Response to rebuttal

Thank you for the response. The point that the slack depends on the ratio is helpful, and the converged BTL and hinge baselines are useful additions. However, my main concern remains largely unsolved. All comparisons are still on the same pairs, and there is no evaluation of θ\theta on held-out candidates. So I will keep my score.

Reviewer_SDPROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how linear reward models can satisfy social choice axioms when learning from human preferences. The authors propose using slack variables and linear programming to reduce preference violations. They provide theoretical analyses and experiments on synthetic and real-world data.

Critical strengths
  • The paper studies an interesting theoretical problem of aggregating human preferences for alignment.
Critical weaknesses
  • The practical relevance to current AI alignment is not very clear. The paper focuses on fixed features and linear reward models, without experiments on more complex reward models or downstream alignment tasks.
  • The experiments are relatively limited, mainly using synthetic data and one real-world dataset, with linear BTL as the main baseline.
Questions for authors
  • The paper argues that the number of candidates is much larger than the feature dimension, so linear rewards cannot represent all possible rankings. How does the ranking limitation differ between adding more responses per prompt and adding more training prompts? Also, does this limitation still apply to modern models?
  • How does the proposed linear reward model relate to reward models used in current AI alignment? Would the method still apply to more complex models?
  • The experiments use one real-world dataset Machine Deliberation. Could the authors provide experiments on more representative preference datasets or reward models?
  • Could the authors compare with other related methods, more than only linear BTL?
2 comments

We thank the reviewer for useful feedback, comments, and careful reading.

QA1

Each candidate is a prompt-response pair. Thus, both adding more responses per prompt and adding more training prompts increase the number of candidates. Moreover, constraints link responses to the same prompt, so the constraint graph is a disjoint union of per-prompt components. The slack bound decomposes accordingly: ∥ε⋆∥1≤η∑i⌊mi2/4⌋\|\varepsilon^\star\|_1\le\eta\sum_i\lfloor m_i^2/4\rfloor, where mim_i is the number of responses to prompt ii. Adding prompts increases the worst case linearly; adding responses per prompt increases it quadratically. Whether a linear reward suffices is governed by a different quantity: whether some nonnegative combination of within-prompt feature differences sums to zero (Prop. 2). That condition depends on all constrained differences jointly. A single prompt with at most d+1d+1 responses in general position is always realizable (Cor. 1), but a shared θ\theta across prompts can still fail.

QA2

A standard reward model is a linear head on learned features. Our setting is that head with the features frozen, as in Ge et al. (NeurIPS 2024) and Hollender & Kraiczy (ICLR 2026). The analysis therefore applies to last-layer training on a fixed backbone, which covers frozen-encoder and linear-probe reward models. It does not cover end-to-end fine-tuning, where the representation itself moves.

QA3

Experiments are provided to validate our theoretical model. Experiments on more datasets and extending exact axiom satisfaction beyond the observed comparisons are the natural next questions.

QA4

We also compared it with the linear hinge model.

We trained a SVM baseline that applies hinge loss on the majority edges with L2 regularization using the scikit-learn LinearSVC function. The experiment is done on the Habermas dataset under the same settings as in the main text (500 questions and 768 dimensions). We tabulate the violations below. We observe that LP3 has significantly fewer violations compared to the Linear BTL and Hinge baselines.

MethodTotal Violation (%)PO Violation (%)Majority Violation (%)∥ε∥1\|\varepsilon\|_1 (10−310^{-3})
LP22.08 ±\pm 1.700.95 ±\pm 0.712.44 ±\pm 2.052.07 ±\pm 1.53
LP31.73 ±\pm 1.480.47 ±\pm 0.442.15 ±\pm 1.852.52 ±\pm 1.89
Linear BTL27.52 ±\pm 1.0510.59 ±\pm 0.6333.26 ±\pm 1.24--
Linear Hinge19.84 ±\pm 1.262.50 ±\pm 0.4725.67 ±\pm 1.63--

Thank you for the response. My main concerns remain unaddressed. I therefore maintain my original rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.