Restriction-Stable Preference Margins

Methods that align language models with pairwise preference data can use how much better the winning answer is, not only which answer won. The best of them do. Margin Matching Preference Optimization (MMPO), for example, turns a 1–10 quality gap into a soft training target. These methods depend on a trustworthy number for that gap, and in practice the number comes from a single call to a judge model, which is noisy and sometimes wrong in a systematic way. This note proposes a different way to get the number: hide random subsets of sentences in both answers and measure how often the judge's verdict survives. The idea is borrowed from circuit complexity. There, a random restriction fixes a random subset of a function's inputs, and the switching lemma says that simple-but-wide functions collapse to near-constants under such restrictions.

A preference with real support behaves like a function that stays decided under partial erasure. A preference that hinges on one fragile surface cue, or on judge noise, flips as soon as that cue is hidden. The derandomization literature supplies a second tool. Instead of spending many independent random erasures per pair, it offers small, deliberately structured families of erasure patterns (bounded-independence designs) that reproduce the relevant averages with far fewer judge calls. The proposal is to build this estimator, test whether it predicts held-out human magnitude better than the direct Likert-style judge scores that current methods rely on, and test whether it improves margin-aware training downstream.

Core Claim

Fix a prompt $x$ and a response pair split into $n$ sentence-level spans, counted jointly across both responses. A restriction $\rho$ keeps each span with probability $1-p$ and replaces it with a neutral placeholder otherwise. Let $J(x, y_w|_\rho, y_l|_\rho) \in \{0,1\}$ be the judge's verdict on the restricted pair. We define the restriction-stable margin as

$$m(p) = 2\,\mathbb{E}_\rho\!\left[J(x, y_w|_\rho, y_l|_\rho)\right] - 1,$$

which is the expected bias of the judge's verdict after erasure. It is the direct analogue of the "bias function" tracked across rounds of mild restrictions in Better Pseudorandom Generators from Milder Pseudorandom Restrictions. That paper studies how such a bias evolves when about half the variables are fixed per step. We borrow the object and the moderate restriction rate, not their seed-length analysis.

The claim has two parts. The first is empirical: $m(p)$ at moderate $p$ (around 0.3 to 0.5) correlates better with held-out human rating gaps than a single judge's direct score difference does, and when used as the margin in MMPO or Offset DPO (DPO with a margin offset, ODPO) it yields better-aligned policies. The second is methodological: at a fixed budget of $B$ judge calls per pair, estimating $m(p)$ with a pairwise-independent restriction design gives a lower-variance margin than $B$ independent random restrictions. The pairwise-independent designs used here are orthogonal arrays built from Hadamard matrices, with $B \approx n+1$ runs. The variance gain comes from the design's ability to cancel the main-effect component of the judge's response exactly.

The theoretical motivation for the second part comes from Bounded Independence Fools Halfspaces. That paper shows $k$-wise independent inputs fool any linear threshold function with error $\epsilon$ once $k = O(\log^2(1/\epsilon)/\epsilon^2)$. A judge that roughly sums per-span evidence and thresholds it is such a function of the keep/erase indicators. The same result also constrains the proposal. Its guarantee needs large $k$ for small $\epsilon$, so it does not justify strength-2 designs on its own terms. Whether low-strength designs suffice for real judges is an empirical question the experiments must answer, not something the theory already settles.

Research Program

The first component is the estimator itself. We segment each response into sentences, capping $n$ at 32 spans per pair by merging short sentences. We then generate restriction families of three kinds: independent random restrictions, strength-2 orthogonal arrays, and strength-3 orthogonal arrays at matched budgets $B \in \{8, 16, 32\}$. Each restricted pair is scored with an open judge. We use Qwen3-30B, because Learning from Saturated Data already uses it as the reference judge against which small-model self-judgments were found to anti-correlate. Every restricted pair is scored in both presentation orders so that position bias cancels.

We compute $m(p)$ at three rates, along with the slope of $m(p)$ as $p$ increases. The slope measures how quickly the verdict decays: fast decay suggests a verdict resting on a few spans, while slow decay suggests redundant support.

The second component plugs the estimator into existing magnitude-aware objectives without changing them. These objectives supply the training method; we contribute only the margin. Margin Matching Preference Optimization trains toward the soft target $\sigma(\gamma m)$. Direct Preference Optimization with an Offset requires the implicit reward gap to exceed an offset derived from the quality gap. Don't Forget Your Reward Values regresses the log-probability-ratio gap onto a normalized reward gap. All three accept any scalar margin, so swapping in $m(p)$ is a controlled intervention.

We deliberately do not attempt a continuous-valued switching lemma. The only magnitude-valued switching lemma in the file, Learning pseudo-Boolean k-DNF and Submodular Functions, works for integer ranges $\{0,\dots,k\}$ at a cost of $k^{O(k\log k/\epsilon)}$. That bound becomes vacuous for fine-grained margins, so the circuit-complexity connection here is limited to the restriction-and-bias viewpoint and to bounded-independence sampling designs. We are not porting proofs.

The third component is a small analysis. We ask which pairs the new margin reorders relative to direct judge scores. We then check whether the reordered pairs concentrate in the failure modes the file documents: judge anti-correlation on reasoning (Learning from Saturated Data), and margin collapse after instruction tuning.

Baselines

The naive reference point is standard DPO, which uses no margin, trained on the same pairs with the same base model, steps, and hyperparameter search.

The strongest existing competitor is MMPO with direct judge margins. The margin there is the difference of 1–10 Likert scores, exactly as in Margin Matching Preference Optimization, which reports an 11% MT-Bench improvement over DPO for Gemma-7B trained on human feedback. It is the strongest competitor because it already consumes a judge's magnitude signal through the same soft-target loss we use. Any gain we show must therefore come from the margin, not the objective. For a fair comparison, the MMPO-Likert baseline gets the same judge model and the same total number of judge calls per pair: its $B$ calls are spent on repeated Likert scoring with sampling, averaged. It also gets the same $\gamma$ search. Beating it means a statistically significant MT-Bench and AlpacaEval 2.0 gain at matched judge budget, reproduced on at least two seeds.

For value regression, VCB is the reference: Don't Forget Your Reward Values reports a 20.9% GPT-4 win-rate lead over DPO on Reddit TL;DR. We run VCB with direct judge rewards versus VCB with $m(p)$.

For margin quality as distinct from training, the reference is the pairwise difference model of Reward Difference Optimization. It reports 71.5% test accuracy on Anthropic HH, against 68–69% for pointwise reward models. We train it on the same HelpSteer2 split, which lets us ask whether a learned pairwise model already captures what restrictions measure.

The ablation isolating the proposal's key ingredient is the independent-random-restriction estimator at the same budget and rate. If the orthogonal-array estimator is not measurably lower-variance than this ablation, the derandomization contribution is null and we will say so.

Why not just…?

Why not just average several judge samples? Repeated sampling reduces the judge's sampling noise but not its systematic errors. The anti-correlation reported in Learning from Saturated Data is a bias, which averaging preserves. Restrictions change the evidence the judge sees, so a verdict driven by one misleading cue gets diluted. This is exactly the MMPO-Likert baseline at matched budget. If it matches our estimator's correlation with human gaps, the restriction idea adds nothing, and the experiment will show it.

Why not just do leave-one-span-out ablation? Leave-one-out measures sensitivity at the full input. When evidence is redundant, as with a response that is wrong in five places, removing any single span leaves the verdict unchanged, so every influence reads zero and the pair looks unimportant. Averaging over restrictions at $p \approx 0.4$ captures such interactions. Leave-one-out costs about $n$ calls, the same as a strength-2 array, so we run it at equal budget. We treat it as a real threat on pairs where a single flaw decides the verdict.

Why not just train a pairwise difference model? The difference model of Reward Difference Optimization is cheap at inference time and a strong competitor. However, it needs labeled magnitude data and inherits whatever cues its training labels contain. Our estimator is training-free and can be applied to a learned scorer as well: restrictions can be applied to the difference model itself. The experiment reports both, and reports whether combining them helps.

Why not just use independent random masks and forget derandomization? This may well be sufficient. The structured designs only help if the judge's verdict is dominated by low-order effects that the designs estimate exactly. The matched-budget ablation decides the question. We expect the gap to shrink as $B$ grows and to matter most at $B \le 16$, which is the regime that matters for labeling large datasets.

Proposed Experiments

We first measure margin quality with no training involved. On HelpSteer2 (HelpSteer2), we build pairs from same-prompt responses and treat the human helpfulness rating difference as ground-truth magnitude. Its reported annotator agreement of Cohen's $\kappa$ = 0.791 sets a ceiling on attainable agreement. We report Spearman correlation between each margin estimator and the human gap, and bootstrap variance of each estimator at $B \in \{8,16,32\}$. We repeat the analysis on GSM8K pairs, labeled correct versus incorrect with graded partial credit, to test the anti-correlation regime.

The decisive check has two conditions. The restriction-stable margin must beat direct judge scoring at matched budget on HelpSteer2 correlation. It must also be non-negative-correlated on GSM8K, where small-model self-judgments are reported to anti-correlate with the Qwen3-30B judge (Learning from Saturated Data).

We then measure downstream effects. We train Gemma-7B with DPO, MMPO-Likert, MMPO-restriction, ODPO in both margin variants, and VCB in both margin variants. Training data is UltraFeedback (ULTRAFEEDBACK), using its 64k prompts, with judge calls re-issued under our budget. We evaluate on MT-Bench, AlpacaEval 2.0, and RewardBench-style pair accuracy of the implicit reward. As a secondary setting, we train on Reddit TL;DR with Pythia-2.8B to match the VCB setup, and measure out-of-distribution transfer to CNN/DailyMail. On the file's evidence, Reward Difference Optimization reports capability loss on unrelated tasks such as summarization when losses are weighted by quality differences, so we check for this alignment tax explicitly.

The proposal is falsified if either of two things happens. The first is that restriction margins fail to beat averaged Likert margins at equal judge budget on both the HelpSteer2 correlation and the MT-Bench comparison. The second is that the structured designs show no variance advantage over independent restrictions. The second failure would reduce the contribution to a masking heuristic, and the paper would be written that way.