A Zeroth-Order Paradigm for LLM Preference Alignment
Peter Chen, Xi Chen, Wotao Yin, Tianyi Lin
cs.CL, cs.AI, cs.LG
2026-09-17
ComPO treats low-margin pairs as comparison oracles via output-layer perturbations. Mistral-Instruct AE2 LC 24.14% to 26.17%; Gemma-3-4B-it Arena-Hard 57.7% to 63.7%.
Direct alignment methods such as DPO skip a reward model and still hit likelihood displacement: the preferred-versus-dispreferred margin grows while the absolute probability of the preferred response falls, and mass slides onto replies with the opposite meaning. Razin et al. showed that dropping pairs that look too similar under CHES can beat adding SFT regularization. Dropping them also throws the pairs away. A small likelihood margin is not the same as a wrong label. Locally, the pair can still say which nearby parameters raise the preferred response and lower the dispreferred one.
The DPO margin loss is a proxy. It works when the pair is cleanly separated. On tiny-margin pairs, optimizing that same differentiable loss is a good way to shove probability mass somewhere else. Those pairs are more useful as comparison signals than as loss samples.
ComPO is zeroth-order. It perturbs the current parameters, asks whether preferred log-likelihood went up and dispreferred log-likelihood went down, and records +1 or −1. Those one-bit measurements estimate an approximately sparse unit direction. The basic scheme perturbs all parameters and has a best-iterate guarantee under smoothness, gradient sparsity, and oracle compatibility with a latent objective; query count is only logarithmic in dimension.
The practical scheme perturbs only the output layer. The direction is a normalized sum of signed perturbations, then small coordinates are zeroed. An update happens only if the fraction of "better" perturbations exceeds λ. Pairs with reference log-likelihood gap at most δmargin=3 are called noisy; the rest are clean. DPO or SimPO runs on clean pairs first, then ComPO on the noisy slice.
The online variant still takes its direction from offline noisy pairs. It samples the current policy on unlabeled prompts, computes a length-normalized reverse-KL proxy, and shrinks the step when that statistic exceeds a threshold. Mini-batches that pass the gate enter a replay buffer. This heuristic does not enforce the hard KL constraint in the theorem.
Offline data is UltraFeedback. On Mistral-7B-Instruct, AlpacaEval 2 LC is 16.54 after SFT, 24.14 after DPO, 23.89 after clean-only DPO, and 26.17 after clean+ComPO, with raw win rate 16.71 to 18.32. MT-Bench moves from 5.86 to 7.69. Arena-Hard with GPT-4 Turbo drops from 14.4 to 10.5; the same setup with a GPT-4.1 judge rises from 10.40 to 11.20. The judge flips the story. Llama-3-8B-Instruct is cleaner: LC 32.59 to 35.79, Arena-Hard 22.9 to 23.1.
On published SimPO checkpoints, Gemma-2-9B-it LC goes 60.36 to 62.42 and Mistral-Instruct 40.22 to 42.27. Applying ComPO on a full DPO checkpoint, no clean split, lifts Mistral-Instruct LC from 24.14 to 27.03. A Llama-3-Instruct pair moves from (−46.761, −47.410) to (−46.728, −47.520). AlpacaEval is strongest when λg keeps about 1%-6% of output-layer entries. Raising noisy pairs from 100 to 300 lifts mean WR from 19.21 to 20.07. Perturbing two extra MLP layers plus the output layer lifts mean LC from 25.02 to 26.00.
Online damping and replay, GPT-4.1 judges: Qwen3-4B-Base LC goes DPO 15.28, offline ComPO 16.20, damping 17.43, replay 18.57. Gemma-3-4B-it Arena-Hard goes 57.7 to 63.3 with damping and 63.7 with replay.
Low-margin pairs do not have to be discarded or fed to the same DPO loss. Comparison oracles are a third path: direct alignment on clean pairs, direction-only updates on noisy ones. Output-layer perturbations with 1600-1800 queries can sit on top of an existing DPO or SimPO checkpoint. Anyone aligning on UltraFeedback-style data can split on margin and try it. The contribution is data geometry, not a new reward model.
Practical updates touch almost only the output layer, so they are not the theorem. Mistral-Instruct regresses on Arena-Hard with GPT-4 Turbo, while the main table still leads with LC. A higher length-controlled win rate does not mean shorter replies. Online damping uses a length-normalized statistic, not sequence-level reverse KL, so the hard-constraint theorem does not apply. Oracle compatibility is an assumption about a latent function nobody can inspect. Main tables are mostly single-run point estimates; only ablations report five-run means. δmargin=3 is a heuristic; CHES might cut the data more accurately, and the paper does not compare the two filters.