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:
- Regularization: They add a ridge penalty ($\ell_2$ norm) to the negative log-likelihood to ensure the optimization problem is "well-behaved" (strongly convex).
- 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