How Many Bits Does a Preference Cycle Cost?

Preference data for aligning language models is increasingly collected in separate places: different annotator pools, different online communities, different rating aspects. Each place may have consistent preferences internally. Their aggregate often is not. Pooling groups that each rank responses consistently can still produce a cycle in which A beats B, B beats C and C beats A (the Condorcet paradox). Game-theoretic alignment methods target exactly this structure, because the "Nash" response distribution, the one no alternative beats more than half the time, can differ from what a single reward score would pick. This raises a concrete systems question that nobody has posed: if each group can send the aggregator only a few bits about its preferences, what should it send, and how much decision quality is lost?

We propose to treat this as a distributed lossy compression problem with a game-theoretic loss. Each group encodes its estimated matrix of pairwise preference logits. A matrix is skew-symmetric when its $(i,j)$ entry equals minus its $(j,i)$ entry, as pairwise preferences do. The aggregator reconstructs the pooled matrix and computes its Nash mixture. The core technical move is to borrow a known universality result for distributed compression under squared error, the Gaussian worst-case theorem. We combine it with a simple stability bound for zero-sum games. Together they give a rate guarantee on Nash exploitability that holds for any preference distribution with a given second-order structure. We then test empirically whether this guarantee is tight, and whether bits spent on the cyclic part of the preferences are worth their cost.

Core Claim

The claim has two parts. The first is a coding scheme with a provable guarantee. Each of $k$ groups fits a local skew-symmetric preference model and applies a fixed random orthogonal transform across the large pool of (prompt, response-pair) coordinates. It then runs a Gaussian distributed code, with quantization and binning designed only from an estimated joint covariance $K$. For any true distribution with covariance $K$, this scheme achieves the rate–distortion performance of the Gaussian case. That follows directly from Worst-Case Source for Distributed Compression with Quadratic Distortion, which proves that whatever is achievable for a jointly Gaussian source in a $k$-encoder network is achievable within $\epsilon$ for every source with the same covariance. Its construction mixes symbols with unitary transforms until a central limit theorem makes them Gaussian; Network Compression: Worst Case Analysis extends this to general topologies. That theorem's known weakness is latency, since it needs very long blocks over time. In our setting the "block" is the set of item pairs across many prompts, which is collected offline, so the weakness does not apply.

The second part transfers the guarantee to the loss that matters for alignment. Let $P$ be the true pooled preference matrix, $\hat P$ the reconstruction, $E=\hat P-P$, and $\hat x$ the Nash mixture of $\hat P$. A standard perturbation argument for zero-sum games gives

$$\mathrm{expl}_P(\hat x) \;\le\; 2\,\max_{ij}|E_{ij}| \;\le\; 2\,\|E\|_F .$$

Here exploitability is the largest amount by which some response distribution beats $\hat x$ under the true preferences. The bound holds because the game value moves by at most the largest entry change, once for $\hat x$ and once for the comparison. Combining the two parts gives a universal upper bound on expected exploitability as a function of rate.

The open scientific question is whether Gaussian sources are also the worst case when distortion is measured directly by exploitability. Exploitability is a max-type, non-quadratic loss. The worst-case theorem's authors flag exactly this kind of loss as unresolved. We will search for counterexamples rather than assume an answer.

Research Program

The local estimator comes from Learning Inconsistent Preferences with Gaussian Processes. That paper models pairwise preferences directly with a skew-symmetric kernel, without a latent utility, and reports 78% accuracy against 51% for a scalar-utility Gaussian process on cyclic chameleon contests. We use it so that sparse local comparison data becomes a dense logit matrix before coding. That method is centralized and has no notion of rate; our contribution starts where it stops.

Two analyses accompany the coding scheme. The first decomposes each matrix into a transitive part, which is explainable by per-item scores, and a cyclic residual. This is the Hodge decomposition from ranking. Reverse water-filling over the joint covariance then shows how an optimal code splits bits between the two parts as rate varies. The second analysis accounts for the price of universality. $K$ is unknown and must be estimated from a pilot sample and described to the decoder. We charge those bits explicitly, following the logic of quantized types in Fine Asymptotics for Universal One-to-One Compression of Parametric Sources, which bounds model-description cost at finite blocklength.

Multiterminal Source Coding under Logarithmic Loss gives the exact rate region when the decoder outputs soft predictions of the raw comparison outcomes. We compute that region numerically on small synthetic instances with A Generalization of Blahut-Arimoto Algorithm to Compute Rate-Distortion Regions of Multiterminal Source Coding Under Logarithmic Loss. This serves as a reference for how well the outcomes themselves can be predicted, which is a different target from the matrix and Nash quality we optimize. It assumes a known distribution, which we do not. Mismatched Multiterminal Source Coding motivates the design: codes built for the wrong joint distribution degrade badly, and the worst-case route avoids committing to any distribution beyond $K$.

This work is distinct from Distributed Direct Preference Optimization. That paper analyzes federated and decentralized training of a scoring-based preference model with uncompressed parameter exchange and names communication compression as open. We compress preference summaries rather than gradients, and we keep the cyclic structure its Bradley-Terry model discards.

Baselines

The naive reference point is each group sending nothing beyond its majority pick per prompt. The aggregator then outputs the plurality winner. This costs about $\log_2 17$ bits per prompt on UltraFeedback, which has 17 completions per prompt.

The strongest competitor, and a real threat, is per-group Bradley-Terry scores fused in probability space. Each group fits one score per response and sends those quantized scores, about $n$ numbers instead of $n(n-1)/2$. The aggregator converts each group's scores into pairwise probabilities, averages the probabilities across groups, and solves for the Nash mixture. If every group is internally transitive, this reconstructs the pooled cyclic matrix almost exactly at much lower rate than our scheme. Averaging probabilities rather than scores preserves Condorcet cycles that arise between groups. We run it with the same local data, the same entropy-coded uniform quantizer, and the same bit budget sweep, and tune its quantizer step on the same validation prompts. We beat it only if we reach lower exploitability at equal total bits. We expect that to happen when groups are themselves intransitive; if it does not, that is the finding.

A second baseline is independent per-group compression. It uses the same transform and quantizer but no binning, so it ignores cross-group correlation. Comparing it with our scheme isolates the value of distributed coding, which theory such as Generalized Gaussian Multiterminal Source Coding: The Symmetric Case predicts can vanish in some correlation regimes. A third baseline is lossless universal coding of the raw comparison outcomes, which wins when groups hold few comparisons. Our ablations remove the random orthogonal transform, to test whether universality matters on real non-Gaussian data, and force all bits onto the transitive component, which isolates the value of the cyclic residual. No reported result was found on Lacuna for rate versus exploitability on any preference benchmark, so every baseline curve will be produced here.

Why not just…?

Why not just send Bradley-Terry scores per group? Because it fails exactly when groups are internally cyclic. The GPGP results show such within-population cycles are real: a scalar utility drops chameleon accuracy from 78% to 51% (Learning Inconsistent Preferences with Gaussian Processes). It also fails when the useful summary is the correlation structure across groups rather than each group's ranking. We will not argue past it. The experiments sweep within-group intransitivity from zero upward, and if score-sending matches us on real splits, we will report that the cyclic budget is unnecessary in practice.

Why not just compress DPO gradients with sparsification or sign quantization? That presupposes training a scoring-based model, whose convergence analysis in Distributed Direct Preference Optimization assumes transitivity. Self-play work shows such models cycle or underperform when cycles exist (COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferences). Gradient compression also cannot exploit correlation between groups. We include a downstream comparison against it at matched bits.

Why not just model every group as an independent Gaussian? Ignoring the joint covariance throws away the binning gain that the worst-case theorem is built on. The independent-compression baseline measures exactly this loss.

Proposed Experiments

We use three groups of datasets. On UltraFeedback (UltraFeedback: Boosting Language Models with High-quality Feedback), each rating aspect is a group: instruction-following, truthfulness, honesty and helpfulness. On Stanford Human Preferences, each subreddit is a group. On HH-RLHF, the helpful and harmless splits are the two groups. Synthetic Rock-Paper-Scissors bandits with tunable within-group and between-group cycles give controlled settings with known ground truth, and the NFL and chameleon contest data test non-language domains. The primary metric is exploitability of the fused Nash mixture under the held-out, uncompressed pooled matrix, plotted against total bits. The theoretical upper bound is drawn on the same plot.

The first decisive check tests the extremality question directly. We build non-Gaussian sources matched in covariance: mixtures of transitive groups, single sparse cycles, and heavy-tailed logits. We then test whether any of them exceeds the Gaussian exploitability curve under our code. A sustained violation would show that Gaussian extremality fails for exploitability, which would be a substantive negative result.

The second check asks whether the cyclic allocation pays off downstream. We train a self-play aligner on fused preference models at three bit budgets and evaluate AlpacaEval 2 length-controlled win rate. Our self-play recipe follows Nash-MD from Nash Learning from Human Feedback and COMAL's prox update. The uncompressed reference point is COMAL's reported win rate of over 60.2% against DPO, IPO and INPO with Llama-3-8B-Instruct (COMAL). Success means recovering most of the uncompressed model's advantage over a Bradley-Terry-trained policy at a small fraction of the raw data's bits, and beating probability-space score fusion at matched rate on the splits where groups are internally intransitive.