Skip to content

Hypothesis Testing for Generalized Thurstone Models

🕒 Published (v1): 2025-12-02 16:32 UTC · Source: Arxiv · Venue: ICML 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper develops a minimax hypothesis testing framework to determine whether pairwise comparison data is generated by a Generalized Thurstone Model (GTM) — a class of parametric ranking models that includes Bradley-Terry-Luce as a special case. The authors derive tight bounds on the critical detection threshold (scaling as Θ((nk)^{-1/2}) for complete graphs), propose a concrete test statistic with time-uniform error guarantees, and validate the framework on the LMSYS Chatbot Arena LLM leaderboard dataset.

Problem

Prior work on GTMs focused almost exclusively on parameter estimation and uncertainty quantification, leaving unanswered the foundational question: does a given pairwise comparison dataset actually conform to a GTM? Without a rigorous goodness-of-fit test, practitioners cannot justify applying the GTM framework or know when to fall back to non-parametric alternatives. No previously analyzed hypothesis test existed for GTMs in the general case.

Method

The authors formulate a composite minimax hypothesis testing problem: H₀ = data is from some GTM T_F with choice function F; H₁ = data is from a pairwise comparison model at Frobenius-norm separation ≥ ε from any T_F model. Key steps:

  1. Separation distance approximation (Theorem 3.1): Show that the true separation distance inf_w ‖P − F(w)‖_F is sandwiched by ‖P − F(w)‖_F up to a constant c₁, where w is the maximum-likelihood GTM weight vector under misspecification. This makes the testing problem tractable.

  2. Test statistic (eq. 15): Sample-split the data into Z₁ (for MLE parameter estimation ŵ) and Z₂ (for computing T). T is an unbiased plug-in estimator of ‖P − F(w*)‖²_F. Reject H₀ if T > γ/(nk).

  3. Upper bound (Theorem 3.2): Prove ε²_c ≤ c₂/(nk) for general connected observation graphs via error bounds on MLE under model misspecification in the ‖·‖_L semi-norm, then apply Chebyshev's inequality.

  4. Lower bound (Theorem 3.4): Use the Ingster-Suslina method with a cycle-decomposition construction on super-Eulerian graphs, generalizing prior BTL-only arguments to arbitrary GTMs and Frobenius-norm separation.

  5. Sequential/time-uniform bounds (Theorem 3.7): Exploit a reverse martingale structure in the test statistic to obtain bounds on type I/II errors that hold uniformly over all sample sizes k ≥ 2, using a specialized time-uniform Hanson-Wright inequality.

  6. Empirical threshold selection: Parametric bootstrap — simulate GTM data under random weights, compute the 95th percentile of the scaled statistic k·T/n as the decision threshold γ.

Key Contributions

  • Rigorous minimax formulation of goodness-of-fit testing for GTMs using a Frobenius-norm separation distance.
  • Upper bound ε²_c = O(1/(nk)) and matching lower bound ε²_c = Ω(1/(nk)) for complete graphs (tight up to constants).
  • Graph-topology-dependent bounds for d-regular graphs, single cycles, and toroidal grids (see Table 1).
  • MLE error bounds under model misspecification in ‖·‖_L semi-norm (Theorem 3.3), generalizing Shah et al. (2016) from the GTM case to arbitrary pairwise comparison models.
  • Time-uniform type I/II error bounds via reverse martingale + specialized Hanson-Wright inequality, enabling sequential testing.
  • Time-uniform confidence intervals for the null hypothesis (Proposition 3.8).
  • Empirical validation on LMSYS Chatbot Arena: finds that BTL/Thurstone models fit well for ≤9 top-ranked LLMs but deviate significantly for n ≥ 21.

Results

  • Complete graph: ε²_c = Θ(1/(nk)) — bounds are tight (matching upper and lower).
  • d-regular graph (constant d): upper O(1/nk), lower Ω(1/n²k) — tight in k, gap in n.
  • Single cycle: upper O(1/nk), lower Ω(1/n²k).
  • Toroidal grid: upper O(1/nk), lower Ω(1/n^{7/4}k).
  • BTL lower bound for single cycle improves prior result of Ω(1/√(n³k)) to Ω(1/√(n²k)) in Frobenius norm.
  • LMSYS experiment: BTL and Thurstone fit the top ~9 LLMs well (~10% of bootstrap samples exceed threshold), but for n=21, ~60% of samples exceed the threshold, indicating poor model fit at larger group sizes.
  • Scaled threshold γ (95th percentile of k·T/n) is empirically stable across n and k for complete graphs, confirming the theoretical 1/(nk) scaling.

Limitations

  • Lower bounds are proven only for super-Eulerian graphs; gaps between upper and lower bounds remain for non-complete graph topologies (e.g., single cycle: O(1/nk) vs. Ω(1/n²k) in n).
  • Assumes pairwise probabilities p_{ij} ∈ [δ, 1−δ] (bounded dynamic range) — may be violated for highly imbalanced agents.
  • Assumes a known, fixed choice function F; testing which F best fits the data is handled only empirically, not theoretically.
  • Sequential framework assumes one comparison per edge per time step; variable-rate observation generalization is noted but not fully developed.
  • LMSYS experiment retains directionality of comparisons (position bias), which GTMs cannot natively model — the asymmetry is acknowledged but not corrected.

Relevance to Agentic AI / LLM Agents

GTMs and their BTL special case underlie the pairwise preference data used in RLHF and LLM leaderboard evaluation (e.g., LMSYS Chatbot Arena, Elo ratings) — settings where LLM agents are ranked against each other. This paper provides a principled statistical test for whether the Bradley-Terry or Thurstone model is a valid assumption before using it for preference learning or ranking, directly addressing a blind spot in how preference data is modeled during alignment training and evaluation. The finding that BTL/Thurstone fits degrade for larger LLM comparison pools (n ≥ 21 in LMSYS) is practically significant for benchmark designers and anyone using pairwise human preference data to train or evaluate agents.