Differentially Private Statistical Inference for Rankings from Pairwise Comparisons

Xintao Xia, Jia GuarXiv 2026 · arXiv

TL;DR

This paper introduces a robust framework for ranking items (like Large Language Models) from pairwise comparisons while strictly protecting individual preference data using edge differential privacy. By combining objective perturbation with a novel bias-correction and bootstrap calibration, the authors provide the first unified method for generating reliable confidence intervals and top-K membership tests for private rankings.

What Problem Does This Paper Address?

Human feedback is the gold standard for evaluating LLMs—think of platforms like Chatbot Arena where users pick a winner between two model responses. However, these pairwise comparison records often contain sensitive individual preferences. While Differential Privacy (DP) offers a way to analyze data without leaking individual records, most existing work in private ranking focuses only on point estimation (finding the best guess for the rank).

The missing piece is statistical inference: how certain are we about these ranks? If a model is ranked #1, is it significantly better than #2, or is that just noise? Standard statistical tools fail here because the noise added for privacy and the regularization needed for stable optimization introduce biases that ruin traditional confidence intervals.

Methods

The authors build their approach on the Bradley–Terry (BT) model, a standard probabilistic model for pairwise comparisons. To make the ranking private, they use objective perturbation:

  1. Regularization: They add a ridge penalty ($\ell_2$ norm) to the negative log-likelihood to ensure the optimization problem is "well-behaved" (strongly convex).
  2. Perturbation: They add a random Laplace noise vector to the objective function before minimizing it.

The core innovation lies in how they handle the resulting estimator ($\tilde{\theta}$):

  • Leave-one-out Analysis: They develop a new mathematical proof technique to establish tight error bounds for how far the private estimate is from the true scores.
  • Bias-Aware Calibration: Recognizing that the ridge penalty shrinks scores toward zero (bias) and the Laplace noise adds variance, they develop a "Gaussian–Laplace calibration." This method adjusts the confidence intervals to account for both sampling randomness and privacy-induced noise.
  • Parametric Bootstrap: For complex questions like "Is this model in the top 10?", they use a bootstrap procedure that simulates the ranking process multiple times to create simultaneous confidence sets for ranks.

Datasets

The paper evaluates the method using two primary sources:

  • Synthetic Simulations: Data generated from Erdős–Rényi graphs (where pairs of items are compared with a fixed probability $p$) to verify that their confidence intervals actually hit the target 95% coverage rate across different privacy budgets ($\epsilon$).
  • LLM Creative Writing Benchmark: A real-world application using a snapshot of the Arena text leaderboard (October 2026). They analyzed 99 LLMs by having them write dramatic scenes based on Hamlet, using GPT-6.1 Sol as an automated judge to generate the pairwise comparisons.

Key Insights and Ideas

  • Privacy is "Free" for Post-Processing: A major highlight is that once the initial private score estimator is released, all subsequent steps—bias correction, variance estimation, and bootstrap—require no additional privacy budget. They are considered "post-processing" of a private release.
  • The Density Advantage: The authors show that if the comparison graph is sufficiently dense, the method remains accurate even in "privacy-dominated" regimes where the noise added for privacy is larger than the natural sampling error of the data.
  • Bias Correction is Non-Negotiable: In finite samples with tight privacy budgets ($\epsilon=1$), standard Wald intervals (which ignore bias) suffer from severe undercoverage (dropping to ~70%). The authors' bias-corrected procedure successfully restores coverage to the nominal 95% level.

Key Results

  • Statistical Validity: In simulations, the proposed bias-corrected intervals maintained near-95% coverage across various privacy levels, while standard methods failed as privacy demands increased.
  • LLM Ranking Performance: In the creative writing task, the method successfully identified top-tier models like GPT-5.5 and Claude Sonnet 4.6.
  • Cost of Privacy: The authors quantified the "cost" of privacy as an increase in the width of the rank confidence sets. For example, at a moderate privacy level ($\epsilon=2.5$), the rank uncertainty for a mid-tier model like Kimi-K2 only increased slightly compared to the non-private benchmark, demonstrating that high-utility inference is possible under DP.

Limitations and Future Work

  • User-Level Privacy: The current work uses "edge" differential privacy, which protects individual comparison records. However, if one user contributes many comparisons, "user-level" DP would be required to fully protect that individual's identity, which is a more challenging constraint.
  • Heterogeneous Comparisons: The model assumes every pair has the same probability of being compared. Real-world leaderboards often have highly non-uniform comparison patterns (e.g., popular models are compared more often), which requires further theoretical extension.
  • Adaptive Selection: The paper assumes the comparison graph is fixed or random. In practice, platforms often use active learning to pick which models to compare next; accounting for this adaptivity under DP remains an open problem.

Summary updated

Abstract

Reliable inference for rankings of large language models based on human pairwise comparisons must preserve the privacy of individual preference records. To meet this need, we develop methods for score and rank inference under the Bradley-Terry model with edge differential privacy. For an objective-perturbed estimator, a new leave-one-out analysis establishes finite-sample bounds on Euclidean and entrywise estimation errors. For sufficiently dense comparison graphs, the error bounds extend to smaller privacy budgets, including regimes in which its privacy term dominates its statistical term. A uniform asymptotic expansion yields asymptotically valid confidence intervals for individual scores and pairwise score differences. To improve finite-sample performance, we account for both regularization bias and privacy-induced randomness by combining a plug-in ridge-bias correction with Gaussian-Laplace calibration. We further establish a bootstrap procedure for simultaneous rank inference, providing asymptotically valid confidence sets for individual ranks and tests of top-$K$ membership. When the comparison probability is public and known, all proposed inferential procedures require no additional privacy budget. We evaluate finite-sample performance through simulations and apply the proposed methods to rank large language models for creative writing.
BibTeX
@misc{xia2026differentially,
  author = {Xintao Xia and Jia Gu},
  title = {{Differentially Private Statistical Inference for Rankings from Pairwise Comparisons}},
  year = {2026},
  eprint = {2611.13485},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13485},
}
Figure