A Zeroth-Order Paradigm for LLM Preference Alignment

AI summary

Overview

Research area: Large language model post-training and preference alignment, at the intersection of zeroth-order/derivative-free optimization and alignment theory.

Technical level: Advanced. The core ideas are intuitive, but the paper's backbone is convergence analysis for derivative-free optimization, sparse 1-bit signal recovery, reverse-KL regularization, and coverage-based generalization bounds.

Scope: The paper proposes ComPO, a comparison-oracle-based zeroth-order alignment method that extracts training signal from low-margin ("noisy") preference pairs which direct alignment methods such as DPO handle badly, and provides offline convergence guarantees plus an online variant with a coverage-based performance bound.

What This Paper Is About

Direct alignment methods like DPO improve the relative likelihood margin between preferred and dispreferred responses, but they can simultaneously lower the absolute probability of the preferred response—a failure mode called likelihood displacement that can turn safe refusals into unsafe compliance. The problem is worst for low-margin preference pairs, where the model already assigns similar likelihoods to both responses, and the standard fix (filtering those pairs out) discards information. This paper asks whether such pairs can instead be treated as weak comparison signals about a latent alignment objective, and whether a derivative-free method built on those signals can align LLMs more reliably than optimizing a fixed margin-based loss.

Key Contributions

1. ComPO, a comparison-oracle alignment framework. The method never differentiates a preference loss. Instead it perturbs the policy, asks a one-bit question—did this perturbation raise the likelihood of the preferred response and lower that of the dispreferred response?—and aggregates the answers into a normalized update direction using a sparse 1-bit compressed-sensing estimator.

2. A practical offline implementation and data partition. Only output-layer weights are perturbed while the rest of the model is frozen; the exact optimization for the update direction is replaced by a normalized sum of signed perturbations with entry-wise clipping. The dataset is split by the reference model's likelihood margin: clean pairs go to a standard method (DPO/SimPO), low-margin pairs go to ComPO, so nothing is discarded.

3. An online extension with reverse-KL control. Online ComPO keeps the offline comparison direction but uses unlabeled generations from the current policy to regularize against the reference policy, with a basic accept-or-reject feasibility rule and a practical step-size adaptation using online samples, damping, and replay.

4. Theory and evaluation. A best-iterate convergence guarantee for the offline scheme under smoothness, gradient sparsity, and oracle compatibility; a feasibility-plus-performance guarantee for the online scheme under local coverage. Experiments span Mistral, Llama, Gemma-2, Qwen3, and Gemma-3.

Main Findings

• Noisy pairs carry usable signal, but not through a margin loss. Low-margin pairs—defined as those where the reference model's log-likelihood difference is below a threshold—are exactly where a fixed DPO-style objective tends to misbehave. ComPO extracts directional information from them without optimizing a differentiable loss on them, complementing standard direct alignment applied to clean pairs.

• Offline convergence with dimension-light query cost. Under smoothness, approximately sparse gradients, and compatibility between the comparison oracle and a latent objective, the basic offline scheme reaches an ε-stationary point with high probability. For a fixed sparsity level s, the number of preference-comparison oracle calls grows only logarithmically in the ambient dimension d, because the method exploits gradient sparsity to escape the usual dimension-dependent cost of comparison-based optimization.

• Online feasibility is preserved by construction. Starting from a policy inside a reverse-KL ball of radius τ around the reference, the accept-or-reject rule keeps every iterate inside that ball.

• Coverage-based performance bound. If the reference policy satisfies local reverse-KL coverage at radius τ, then the suboptimality gap against the best policy in that neighborhood is bounded by a constant times the square root of the in-distribution pairwise reward error. Local coverage remains a separate assumption and is not implied by the KL constraint itself.

• Empirical gains across five model families. ComPO improves over existing direct alignment methods on Mistral, Llama, Gemma-2, Qwen3, and Gemma-3 base and instruction-tuned models, including on length-controlled win rates. Pair-level likelihood diagnostics are consistent with mitigation of likelihood displacement.

• Length effects are observed but not the target. ComPO is not designed to control verbosity. The authors interpret higher length-controlled win rates as better judged performance after adjusting for response length, not as direct evidence that responses got shorter.

• Online damping and replay matter. The journal extension evaluates online regularization and replay, showing these design choices affect the online variant's behavior.

Methodology in Plain English

The starting observation is a mismatch: DPO optimizes a proxy objective—maximize the likelihood margin—and this proxy works well only when the preference signal is strong. For pairs where the model already finds both responses about equally plausible, the proxy can push probability mass in unintended directions.

ComPO sidesteps the proxy entirely. It treats the true alignment objective as a latent function that cannot be written down or differentiated. To make progress on it, the method takes the current model, adds a small random perturbation to its output layer, and asks a simple question of each perturbed version: does this version make the preferred answer more likely than before and the dispreferred answer less likely? The answer is a single bit—yes or no.

Collecting many such bits across many random perturbations gives a one-bit measurement of the unknown objective's local gradient direction, in the same way that compressed sensing recovers a signal from sign measurements. The method solves a sparse recovery problem to convert those bits into a normalized update direction, and steps the model in that direction. Because the question is only "is this direction better?", small-margin pairs can contribute without ever being fed into a margin-maximizing loss.

For real-scale LLMs, the exact sparse recovery is replaced by a cheaper approximation: sum the signed perturbations, normalize, and zero out small entries. Only the output layer is perturbed; the rest of the network is frozen. The training pipeline splits data by the reference model's likelihood margin—clean pairs go to DPO or SimPO, low-margin pairs go to ComPO.

The online variant adds a leash. Since the comparison direction comes from a fixed offline dataset, the model could drift arbitrarily far from the reference. Online ComPO draws unlabeled samples from the current policy, estimates the reverse KL divergence from the reference, and uses it to gate or damp updates—accepting a candidate step only when the divergence stays within a prescribed radius. This is what lets the analysis restrict attention to a neighborhood of the reference policy rather than the entire policy class.

Why This Matters

Impact on research. The paper reframes a known empirical failure mode of direct alignment as a data-geometry problem with an algorithmic answer. Prior work (notably the CHES-score filtering approach) responded to likelihood displacement by removing problematic pairs from training. ComPO argues those pairs should be reused through a different mechanism, and supplies the optimization theory to justify it. It also connects LLM alignment to comparison-based zeroth-order optimization and 1-bit compressed sensing, opening a channel between two literatures that have rarely interacted.

Real-world applications:

• Safety-critical assistants. Likelihood displacement can shift probability mass toward unsafe compliance—the paper cites a Gemma-2B-it case where DPO training turns a refusal into compliance with a harmful request. A method that preserves the absolute likelihood of preferred responses directly targets that failure.

• Cost-efficient post-training. ComPO avoids a separate reward model, keeps the memory and compute profile of direct alignment, and freezes all but the output layer during the comparison phase—attractive for teams without large RLHF infrastructure.

• Salvaging preference data. Preference datasets often contain many near-tied pairs. Instead of discarding them, pipelines can route them to ComPO and recover value from data that filtering would waste.

• Reducing verbosity-driven inference cost. Length inflation from alignment training raises serving costs without quality gains; improving length-controlled win rates at equal or better quality has direct serving implications.

Industry relevance. The method targets the exact workflow most organizations use for post-training—supervised fine-tuning followed by direct preference optimization on a fixed preference set. It is designed as a drop-in complement to DPO and SimPO rather than a replacement, and the practical variant's output-layer-only perturbation keeps the engineering surface small.

Future Directions

• Closing the gap between the basic and practical schemes. The theory assumes the reverse KL is evaluated exactly and the sparse recovery is solved exactly; the practical algorithm uses sampled estimates, output-layer-only perturbations, and thresholding. Quantifying how these approximations degrade the guarantees is open.

• Relaxing the structural assumptions. Convergence relies on smoothness, approximate gradient sparsity, and exact compatibility between the comparison oracle and a latent objective. Whether these can be weakened—or empirically verified—for real transformer policies is unresolved.

• Understanding and controlling length effects mechanistically. The paper observes length-controlled gains without claiming ComPO shortens responses. A mechanistic account of why some alignment methods inflate length and whether ComPO's update geometry changes that would strengthen the practical case.

• Scaling the perturbation space and the feedback type. Extending beyond output-layer perturbations, and generalizing the oracle from pairwise preference to rankings or k-wise comparisons, are natural extensions of the same framework.

• Adaptive data partitioning. The clean/noisy split depends on a threshold on the reference model's likelihood margin. Choosing that threshold adaptively, or combining ComPO with embedding-similarity-based curation rather than replacing it, is an obvious practical refinement.

Target Audience

Alignment and post-training researchers who work on preference optimization and want an alternative to margin-based objectives; optimization theorists interested in zeroth-order and comparison-based methods applied at LLM scale; and ML engineers building alignment pipelines who need a method that leverages low-margin preference data without reward-model infrastructure. Readers should be comfortable with KL-regularized policy optimization and basic convergence analysis to get full value from the theory sections, though the algorithmic idea and empirical results are accessible without that background.

Authors’ abstract

Direct preference alignment methods are widely used to align large language models (LLMs) with human preferences because of their computational and memory efficiency. However, likelihood displacement motivates alternative ways to extract information from preference pairs with small likelihood margins. In this paper, we propose and analyze Comparison-based Preference Optimization (ComPO), a zeroth-order alignment method based on comparison oracles. ComPO extracts directional information from these pairs without directly optimizing a differentiable preference loss on them. We establish a convergence guarantee for its basic offline scheme under smoothness, gradient sparsity, and compatibility between the oracle and a latent objective. We further introduce online ComPO, which retains the offline comparison mechanism and uses unlabeled policy generations for reverse-KL control relative to a reference policy. Following the coverage perspective of preference fine-tuning, we establish a performance guarantee for a basic constrained scheme under local coverage and in-distribution pairwise reward accuracy. Experiments on Mistral, Llama, Gemma-2, Qwen3, and Gemma-3 models demonstrate improvements over existing direct alignment methods, including length-controlled win rates, with pair-level diagnostics providing evidence consistent with mitigating likelihood displacement.