Learning Correlated Reward Models: Statistical Barriers and Opportunities
Authors: Yeshwanth Cherapanamjeri
Constantinos Costis Daskalakis
Gabriele Farina
Sobhan Mohammadpour
Venue: ICLR 2026 Poster (2026)
Keywords: reward model
RLHF
choice model
random utility model
Primary area: generative models
TL;DR: We show how to learn correlated probits.

Abstract: Random Utility Models (RUMs) are a classical framework for modeling user preferences and play a key role in reward modeling for Reinforcement Learning from Human Feedback (RLHF). However, a crucial shortcoming of many of these techniques is the Independence of Irrelevant Alternatives (IIA) assumption, which collapses \emph{all} human preferences to a universal underlying utility function, yielding a coarse approximation of the range of human preferences. On the other hand, statistical and computational guarantees for models avoiding this assumption are scarce. In this paper, we investigate the statistical and computational challenges of learning a \emph{correlated} probit model, a fundamental RUM that avoids the IIA assumption. First, we establish that the classical data collection paradigm of pairwise preference data is \emph{fundamentally insufficient} to learn correlational information, explaining the lack of statistical and computational guarantees in this setting. Next, we demonstrate that \emph{best-of-three} preference data provably overcomes these shortcomings, and devise a statistically and computationally efficient estimator with near-optimal performance. These results highlight the benefits of higher-order preference data in learning correlated utilities, allowing for more fine-grained modeling of human preferences. Finally, we validate these theoretical guarantees on several real-world datasets, demonstrating improved personalization of human preferences.

Published as a conference paper at ICLR 2026
LEARNING CORRELATED REWARD MODELS: STATISTICAL BARRIERS AND OPPORTUNITIES
Yeshwanth Cherapanamjeri MIT
Constantinos Daskalakis MIT
Gabriele Farina
Sobhan Mohammadpour MIT
MIT
ABSTRACT
Random Utility Models (RUMs) are a classical framework for modeling user preferences and play key role in reward modeling for Reinforcement Learn- ing from Human Feedback (RLHF). However, a crucial shortcoming of many of these techniques is the Independence of Irrelevant Alternatives (IIA) assumption, which collapses all human preferences to universal underlying utility function, yielding a coarse approximation of the range of human preferences. On the other hand, statistical and computational guarantees for models avoiding this assump- tion are scarce. In this paper, we investigate the statistical and computational challenges of learning a correlated probit model, fundamental RUM that avoids the IIA assumption. First, we establish that the classical data collection paradigm of pairwise preference data is fundamentally insufficient learn correlational in- formation, explaining the lack of statistical and computational guarantees in this setting. Next, we demonstrate that best-of-three preference data provably over- comes these shortcomings, and devise statistically and computationally efficient estimator with near-optimal performance. These results highlight the benefits of higher-order preference data in learning correlated utilities, allowing for more fine-grained modeling of human preferences. Finally, we validate these theoreti- cal guarantees on several real-world datasets, demonstrating improved personal- ization of human preferences.
INTRODUCTION
Random Utility Models (RUMs) (Train, 2009) are the leading framework for modelling human pref- erences. Classical applications dating back to the 1960s include mathematical psychology (Luce, 1959), transportation science (Ben-Akiva, 1973), econometries (McFadden, 1980), and marketing (Rust and Zahorik, 1993). More recently, they are a core component of the Reinforcement Learning from Human Feedback (RLHF) pipeline (Christiano et al., 2017), used to align Large Language Models (LLMs) with human preferences. Unfortunately, many classical RUMs adopt the Indepen- dence of Irrelevant Alternatives (IIA) assumption. In the context of LLMs, the IIA posits universal underlying utility function for all users of system. A growing body of work highlights the limits of this approach (Bai al.. 2022; Casper al., 2023; Sorensen et al., 2024: Anwar et al., 2024; Conitzer et al., 2024) in capturing the full range of human preferences.
Formally, RUM models utilities over set of items as high-dimensional random vector, X A classical choice is the logit model, where each component X; is independent and distributed according to Gumbel distribution X; ~ Gumbel(us). The IIA assumption implies that for any unobserved item (or response), the model assigns the same average utility irrespective of the user's past preferences.
In this paper, we investigate the statistical challenges of learning correlated utility models, focusing in particular on the correlated probit model where X (i, E). By explicitly modeling correla- tions, these techniques allow past user behavior to inform future responses, providing more accu-
For RLHF, the items correspond to (prompt, response) pairs

---

Published as a conference paper at ICLR 2026
rate representation of human preferences. However, in contrast to the logit model, little is known about the statistical and computational challenges of learning these models: i) What data is needed to learn them? and ii) How many samples do we need?
We make key advancements on several fronts: 1) We show that the conventional paradigm of pair- wise preference data is fundamentally insufficient learn these models, 2) On the other hand, tine-way--peffeenee data is both necessary and sufficient and finally. 3) Validate the efficacy of higher-order preference data in accurately modelling correlated user preferences. Our results high- light fundamental drawbacks in conventional data collection pipelines and suggest deliberate amend- ments to address these shortcomings. Prior to our work, even identifiability results. disregarding any statistical considerations, did not exist. Hence, we establish the first identifiability guarantees and complement them with a near-optimal polynomial-time estimator.
2 RELATED WORK
A wealth of ideas exists for modeling rewards. However, we focus on choice modeling, where sub- jective preferences between items expressed. Consequently, we find a treatment of reward mod- els like step-wise reward models (Havrilla et al., 2024) and process reward models (Luo et al., 2023) beyond the scope of this work. We are interested in models that can make counterfactual choices from preference data. Outside of machine learning, choice models have been successfully applied to planning problems like public transport scheduling (Wei et al., 2022), effect of price markups (Gallego and Wang. 2014), airline scheduling (Wei et al., 2020), EV charging station placement (Lamontagne et al., 2023), and toll placement Osorio and Atasoy (2021).
Random Unility Models (RUMs) are among the most common models of human behavior in math- ematical psychology, econometrics, transportation, and marketing (e.g.. see McFadden, 2001, Nobel Prize lecture on RUMs). RUMs impose structure on the choice model by assuming that the agents are rational, meaning that when confronted with a finite set of alternatives, they choose the one that maximizes their (latent) utility. The agent's unobserved utility is commonly modeled as a random variable to acknowledge the heterogeneity of utilities. Formally, an agent is assumed to have a random utility vector X, where X; is the utility of choosing some alternative from the set of all possible alternatives C, and, when presented with a subset R S C of alternatives, the agent chooses the alternative I satisfying
IR. E arg max X BER
Given observations of the form t T, common challenge is learn the dis- tribution of the latent X. Obtaining an estimate X of X not only gives us an estimate In of IR. for any subset of alternatives R. but it also allows making predictions about the welfare of R, G(R) == max,eR X,. It is important to note that learning the distribution of X from preference data is inherently underconstrained as adding the same potentially stochastic value to all components of X yields no change in the distribution of
The most popular RUM is the logit (Train, 2009, Chapter 3) or also sometimes referred to as Luce Shephard-McFadeee
model, or, in the binary case (i.e. |C] = 2), the Bradley- -erry model. The logit is the only RUM that satisfies independence of irrelevant alternatives (IIA) (Luce, 1959), that is, the ratio of the probabilities of choosing two alternatives is independent of the presence of other alternatives. The logit enjoys many useful properties, for instance, it can be learned using pairwise comparisons, it can learn any distribution over the set of full alternatives?, and is easy to calculate via a softmax. Unfortunately, if the utilities are correlated, the logit cannot be used make correct counterfactual predictions. A classical example showcasing this impossibility is the red bus/blue bus problem introduced by Debreu (1960). If half of the populations prefer red buses over blue buses and half of the population prefers red buses made by company A over those made by company B, then IIA implies that 2/3 of the population prefers red buses made by A or over blue buses, a contradiction. In practice, as shown by Benson et al. (2016), many datasets do not satisfy the IIA assumption. We continue our discussion on choice modeling in Appendix A
by setting the utilities the log probabilities
2

---

Published as a conference paper at ICLR 2026
3 PROBLEM SETUP, AND THE NEED FOR BEST-OF-THRES OBSERVATIONS
Here, we avoid the restrictive IIA assumption and assume, instead, that the utilities follow the classical probit model with X 2.), We aim recover (u, 2) from only the choices arg (iER) X; made for various subsets R C [n]. For binary choice, R. is pairs of elements (i,j) [n]². Similarly, for the three-way choice setting, is triplets (i.j.k E [m] Note that (H, 2) are not fully identifiable in this setting: for any X (u, Σ), X' defined as follows, in-
duces the same ranking probabilities for any > 0, ((X - + Σ, X:) Hence, we adopt the following necessary normalization J., E.
Assumption 3.1. For X (1,, E). assume, without changing the choice distributions, that (n, 0, Σ1 0, and
Tr
Consequently, X lives on the hyperplane 1 X = 0. Furthermore, we assume E has rank 1.
Unfortunately, the classical paradigm of pairwise comparisons (R 2) is insufficient for recover- ing (p, 2), even accounting for Assumption 3.1. Its proof deferred to Appendix E.2.
Theorem 3.2. For any n 3 3 and μ. E satisfying Assumption 3.1, there exists an infinite sel S:
Vi,j [n), D' S
IP
{X, > x2) =
P X~N(W(E')
{x; X,}.
X~N(HE)
Theorem 3.2 indicates that pairwise comparison data is fundamentally unable to account for correla- tions in the probit model. While the full proof of Theorem 3.2 is somewhat involved, the particular setting with μ 0 is instructive. Here, observe that for any pair of distinct alternatives, i, the probability that X, > X, is 1/2 irrespective the value Σ. Hence, correlational information is fundamentally impossible to learn given only access to pairwise comparisons.
IDENTIFIABILITY
Theorem 3.2 prompts the natural question: can higher order preference data help? We answer the question in the affirmative and show that best-of-thre observations (Theorem 4.4) are sufficient and from Theorem 3.2, necessary to recover μt, Σ. Observing that:
PP (X; X, > Xx) = (X, Xx} P (X; Xú, Xt),
(RANK-PROB)
may assume access to three-way ranking probabilities.
4.1 THE CASE OF THREE ALTERNATIVES
As stepping stone towards identifying probit models with an arbitrary number n of alternatives, we focus on the case n = 3 and establish the following theorem.
Theorem 4.1. (n, Σ) are uniquely identifiable from the three-way observation probabilities.
This result will serve as the basis for the general case in Subsection 4.2. A probit model satisfying the constraints in Assumption 3.1 defines a bivariate normal distribution that lies in the plane defined by X O. We start by projecting the utilities onto lower-dimensional space:
Vi 1/2
[//66
1/v6
-2/V6
Xi X2 Xg
X1
1/v6
1/v2
V 122
+
X2
1/V6
11v/2
(1)
1/V2 -1/2
2//66
PT
Under the transformation P. the probit model X (N, E) is mapped some bivariate normal distribution (,, E). Upon identification of the parameters j and Σ in two dimensions, recover the original parameters y and E through the transformation:
p PT and = S.P.
3

---

Published as a conference paper at ICLR 2026
V.A
00.4
Event
09.3
X1 > X2 X
Pone 1 X 0
X1 X3 X2
Xa X4 X2
1011
0.2
03
04
X3 X2
X2 2 X3 X
X2 3 X1 X
X-
Figure 1: The probabilities P [X2 > X3 >> Xx). for permutations, (i.j. of (1, correspond the probability mass in each of the six slices of the plane denoted through 6
Defining,
C1 = 0 : = v3/2
V3/2
-1/2 C3 ==
1/2
the probability of the events {X; > x,). are satisfy the following:
P(Xi > X2) P 0}, P(X2 > X3) P 0), P(Xi > =
with each three- way permutation corresponding to the intersections of the corresponding halfspaces. The projection and the partitioning of the 2-dimensional space are illustrated in Figure 1.
We will further transform V, rendering the distribution isotropic. Define 1-1 as a solution of
3-123 I.
Note that 1/1 is unique up to an orthonormal transformation on the left. We will fix a convenient choice subsequently. For now, observe that 1 and 51/2 = ((S-1/2)-1) satisfy:
Vær, E R2 (11, = "-12
Setting 21 c₁ and x2 V. now observe:
(5,/2,,, x-122) with 1/1//2 N I) where = 1/2
Lastly, note that:
$11/204
Vi [3] (G, V) 0
Cc. 1/2 where ट. =
||$22/20211
Note that É-1/2V is isotropic. Defining,
a; :===2 ट, i and a;j = = ", Our first technical result identifies as from observational data. Lemma 4.2. The quantities ag are identifiable from three-way ranking probabilities.
Proof. Note that
P(cTV 0} - -P(1=P((- (P(1X > 20
Po (c. > 0) (((.,
As ((.) is a strictly increasing function, (Ce, (1) is recoverable from the observables.
In the next lemma, we use the values a from Lemma 4.2 to establish a monotonic relationship between (c,, Cy) and the probability of the events in Figure 1. However, the precise choice of events depends on the og- Note that for any distinct i, E [3]. there exist signings 81,8; E {+1} such
that s, (c, sy(C, > 0 and the events {s, (11// (č,, 1-//2v) S,,,, < <)) correspond to
combinations of or more events in Figure and hence, observable. By instantiating the sub- sequent lemma with the signed vectors StCi, syZ, we recover the oi by relating it to the probability
of the event 8: (T, 1-1/2V), 83 SG E-122/) < 60. Its proof is deferred to Appendix E.
4

---

Published as a conference paper at ICLR 2026
Lemma 4.3. Let 01, U2 E R² be two independent unit vectors and & R² be such that d1 (U1, (1.E))d2 d2 = (U2, E) 3 0. Then,
012 == (U1, 22))
is identifiable from d,, d2, and
112 = I[( (X, 02) & 03 for X 1),,
Proof of Theorem 4.1. We will show that //2 is recoverable from the observation probabilities. Σ is then obtainable from the fact that = ($1/2) 5// From Lemma 4.2, we recover a; = (G, 7i) for i E [3] and from Lemma 4.3, we recover Oij (G.C)) for * E [3]. Without loss of generality, we assume that for some 8, t by relaxing the scale constraint Tr Σ 1:
[ f1 [
f1 =
[
a12
E1
01 LV
(I-aa a2
13
The signs of the second component of the vector are determined by fixing the sign of ///2c (this is an orthonormal transformation) and for E1/22c,, follows from the fact that C3 C1 + c2. Noting that 013 o 0/12 (as otherwise, we obtain permutation observations with 0 probability), we obtain:
012
11 0
111
013
a1
[] +
12
LV
a
V
12
-s
Since the above forms invertible system, we obtain the values of 8, recovery of Σ (and consequently, Σ) via the invertible system:
0. This now enables the
11 le 02]
80:2
0
8V
To recover is, note that č and ō2 form a basis for IR² and observing that these are determined by Eq. (2), we identify ÿ.. Noting that 1/122 = μú, we recover ja and by our previous discussion. M
4.2 IDENTIFIABILITY MORE THAN THREE ALTERNATIVES
We now utilize Theorem 4.1 to establish identifiability for an arbitrary number of alternatives, n. Theorem 4.1 recovers μ, Σ restricted to tuples of 3 alternatives up to the symmetries in Assump- tion 3.1. However, the sub-maut sub-matrices of μ. Σ (or more precisely, f and Σ restricted to these alterna- tives) could potentially violate these assumptions. Hence, we establish that there is unique pair, J4, Σ, consistent with the equivalence class of parameters identified by Theorem 4.1 for all choices of 3 alternatives. In what follows, we will use Pijk and Eijj denote the parameters μ and Σ restricted to the tuple i,j and k, projected onto the two-dimensional subspace orthogonal to 1.
Theorem 4.4. μ. E are uniquely identifiable from the three-way observation probabilities.
Proof. First, note for any distinct indices j, k. Theorem 4.1 yields Piikk Ligk satisfying:
tijkFiikk = fāizk and t Enfe = Enjk
for some scaling tijk 0. Denoting Cij = 1 Cj. have:
cJ TigEee = cijy Eijuccss = cigy Deij By = TfEcss
The first step uses the fact that c Eighe c.j Dighej.. Since scaling E (and μ) produces the same solution, we may assume without loss of generality that 4123 = 1. Noting that this allows the recovery of Ec12, the above equality enables determination of the f12 for all & [n]. This further enables the determination of tişt for all distinct k,j E [n]. Another application of the argument finally yields the values of Liza for all distinct i, k [n].
Furthermore, observe that for all distinct j, E [m) with aij == Eny:
C 22 2
co os + Ojj 20
5

---

Published as a conference paper at ICLR 2026
Furthermore, noting that Css O, determine aij cij Enj for all i,j E [n]. Observe that
Eay = na + Tr(2) -
ij = no + Tr(E).
==1
==1
where the last step is due to fact that 1 p E1 0. By further summing over i, get
C2 ( Tr())
which now enables recovery Tr(E) and from the above discussion da and consequently, diy for all i.j. Hence, we have identified E. For the mean, observe again the following:
(tigAAl1)))) = Gyplisk = Híj-
The last step is valid because all of the elements of jajk were shifted by the same amount to obtain Pigks and consequently, their difference did not change. Since lifk are determined, this determines j4 Mj for all j (note the choice of μi is arbitrary). Letting 3j MI Pý, we have:
Σ B, nf
Σ My np1.
This determines j4r and, consequently, the remaining py- This concludes the proof as (μ, Σ) have been recovered up to the universal symmetries previously described.
L
5 FINITE-SAMPLE GUARANTEES: UPPER AND LOWER BOUNDS
In this section, we extend our identifiability results Section 4 to estimation. The key conceptual advancement over Section 4 is in the aggregation procedure which combines the standardized esti- mators of the 3 item setting (Subsection 4. into solution for the item setting (Subsection 4.2). The procedure described in Subsection 4.2 wasteful as it requires estimating all 3 3 sub-matrices of Σ, resulting in total of (nn)) total 3 3 matrices. We show that this can be substantially improved upon using a much smaller number (Ó(n²)) of sub-matrices in Theorem 5.2. We then establish a statistical lower bound demonstrating the near-optimality of our estimator: We start with our estimation guarantees. In addition Assumption 3.1, we require the following assumption:
Assumption 5.1. (Observabilityy For any three alternatives i, j. k E [n] and X ~ N(,, E):
P j k}
for some > 0.
Intuitively, Assumption 5.1 avoids worst-case scenarios where overwhelming difference in utili- ties renders a choice unobservable, making some parameters impossible to estimate. We now state main estimation guarantee for the general n-item setting.
Theorem 5.2. Let (n", "") satisfy Assumptions 3.1 and 5.1 with Tr(E') = n. Then, for any 8 E (0, 1/2), given there a polynomial time algorithm which when allowed N observations of rank-3 permutations from Choico(j*" "i',,,))
,E") of choice, returns estimates, (p, E), satisfying:
1| 10o & and Σ E-E"" -' E
with probability at least 1 5 as long N Cn2--22- 24 log(n//)) logooo/(((/) (n/(7e)).
Next, we present a lower bound that shows that Theorem 5.2 is near-optimal. We introduce some notation before proceeding. An estimator, T. is parameterized by of tuples {((i, &), i,j, & E [n). i * j * k + i}. The estimator then obtains NisA samples from Choico Mi Eigh) for each i, and outputs estimates (μ, E). Furthermore, we denote:
Ny = Σ Nigk-
As before, adopt Assumption 3.1 for normalization and state main lower bound below.

---

Published as a conference paper at ICLR 2026
501
11 100
540
10
8
Figure 2: Center: ground truth covariance matrix, two figures on the right, covariance matrix learned from best-of-three observations, two figure on the left, covariance matrix learned from pairwise comparisons. We reproduce larger version these plots in Appendix F.
Theorem 5.3. Let N. 8,e (0, For any estimator T parameterized by ((i.5. k), N4 such that Ne & g- (og(1/0)/ for some it # j E [m], there ex- ist two choice models, parameterized by (0,E*) and (0, )1 with:
Tr(E')= =TC))=T(E3)) = n and || - 100 26
satisfying:
max Px~(T(Choicc(0.5) E)) [IT(X) Σ (E 221)
6.
We pause for a few remarks. Firstly, note that each pair (i..) must appear in at least (i(E exper- iments. Since each sample only accounts for O(1) pairs, this result implies lower bound of s(n²))
on the number of unique experiments for any successful estimator matching Theorem 5.2. Finally, note that this argument also implies that the total number of samples is at least Q(n2e Q(n2==2log(1/// (og)) again matching Theorem 5.2 terms of n, d, and S.
EXPERIMENTS
We empirically evaluate modeling correlations. We use datasets of ratings and rankings. rating datasets users are asked to assign a numerical value to alternatives. In contrasts, ranking datasets contain the ordered list of preferences. We convert rankings to ratings and vice versa by using the index as rating and assuming alternatives with higher ratings are preferred over alternatives with lower ratings. The data gathering process can either be organic i.e., users rate movies they watch, or structured, every
ranks all food items on the menu.
We use two types of models on these datasets: RUMs and matrix completion models, both trained with gradient based methods. For RUMs, we use logit and probit models learned from two way comparisons and probit models learned from three way comparisons. In all cases we use the max- imum likelihood estimate. RUMs do not take the user input and directly create a model for the population. Matrix completion (Koren et al., 2009) learns the ratings for all users in the training set, we then use the counts of users the training set to approximate the probability of certain events. For sanity checks, we include model we refer to direct, which is similar to matrix completion, except we compute the desired quantities directly on the training set. We argue that this model is unrealistic in some scenarios, for instance where the set of alternative and user is large when the ratings are grouped but anonymous. In particular, we find that matrix completion needs many ob- servations per user to learn the distribution of choices. Still, since these matrix completion models the whole population, we expect them to be able to learn correlated preferences.
In the first set of experiments sample six choices from user, we present the ranking of four of the alternatives as context and predict the preference over the remaining two alternatives. We start with synthetic data sampled from probit model as compare our results to the ground
7

---

Published as a conference paper at ICLR 2026
structure
logit
matris completion occuracy quaatile
probii (pairwise) accuracy quaazile
prubit (best of-three) occuracy quantile
occuracy quantile
0,25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
D
0.50
0.50
0.50
0.50
0.50)
01500
01.50
0.50
0.50
0.50
0.50
0.50
D
bin
0.500
0.50
01.50
0.78
0.78
0.778
0145
0.50
0..54
0.79
0.79
0.79
0.50
0.51
0.50
0.50
0.50
00.50
0.50
0.67
0.67
0.67
0.47
0.51
0.55
0.67
0.67
0.67
0.70
0.70
0.71
0.68
0.70
0.70
0.66
0.66
0.07
0.68
0.70
0.70
hin
0.79
0.79
0.50
0.94
0.95
0.95
0.95
0.95
0.95
0:94
0.95
0.95
0.71
0.72
0.63
0.63
0.64
0.71
0.71
0.71
0.67
0.68
0.69
0.71
0.71
0.71
Table 1: Accuracy of different methods on the synthetic dataset. Notice how the direct method
matches best-of-three probit.
logit
matrix completion accuracy quantile
direct accuracy quantilo
probit (puirwise) accuracy quantill
probit (best of of-theee) accuracy quantile
accuracy quantile
dds. Feat.
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
jokes
onchot
onchot
0.61
0.61
0.61
0.61
0.61
0.61
0.61
0.62
0.63
0.59
0.59
0.59
0.61
0.61
0.61
ml
Ilm
0.57
0.57
0.57
0.59
0.59
0.60
0.57
0.57
0.58
0.56
0.56
0.56
0.57
0.57
0.57
ml
10k
1lm
0.59
0.59
0.59
0.60
0.60
0.60
0.50
0.60
0.60
0.57
0.57
0.57
0.59
0.59
0.59
ml
50k
Iim
0.59
0.39
0.59
0.58
0.58
0.58
0.59
0.59
0.60
0.55
0.55
0.56
0.59
0.59
0.59
mll
onchoo
0.62
0.62
0.62
0.60
0.60
0.60
0.57
0.58
0.58
0.60
0.60
0.60
0.61
0.61
0.62
ml
10k
onchuu
0.61
0.61
0.61
0.60
0.60
0.60
0.58
0.59
0.59
0.59
0.59
0.59
0.61
0.61
0.61
ml
onchot
0.59
0.59
0.58
0.55
0.55
0.59
0.60
uf
10k
lim
0.59
0.59
0.59
0.59
0.59
0.59
0.56
0.56
0.57
0.58
0.58
0.58
0.59
0.59
0.59
nf
100k
Iim
0.61
0.61
0.61
0.61
0.61
0.61
0.61
0.61
0.61
0.59
0.59
0.59
0.61
0.61
0.61
nf
150k
Ilm
0.61
0.61
0.61
0.60
0.60
0.60
0.60
0.60
0.61
0.56
0.56
0.56
0,61
0.61
0.61
of
10k
onchot
0.61
03.61
0.62
0.59
0.59
0.59
0.57
0.57
0.57
0.59
0.59
0.60
0.61
0.61
0.61
of
100k
onchot
0.62
0.62
0.62
0.61
0.61
0.61
0.61
0.61
0.61
0.59
0.59
0.59
0.62
0.62
0.62
of
150k
onchot
0.61
0.61
0.61
0.60
0.60
0.61
0.59
0.60
0.60
0.56
0.56
0.56
0.61
0.61
0.61
suchi
0.65
0.65
0.66
0.51
0.64
0.64
0.64
0.65
0.65
sushi A
onchut
0.65
0.66
0.66
0.67
0.67
0.68
0.68
0.68
0.68
0.65
0.65
0.65
0.68
0.68
0.68
sushi
onchot
0.67
0.67
0.68
0.68
0.50
0.66
0.66
0.67
0.68
Table 2: Prediction accuracy for different model and datasets. The column labeled "var." denotes the variants. For movie datasets, nf (Netflix) and ml (MovieLens) the number denotes the number of ratings movie needed to be included. For the sushi dataset, the dataset is split into 2 categories. The column labeled "feat." " denotes the features fed to the model. Rows marked with Ilm use the embedding of Qwen3 Emmeddingg-0 6B (Zhang et al., 2025).
truth. In Figure 2, we show the recovered covariance matrices with pairwise and best-of-three ob- servations using probit RUM. We can see that the model learned from pairwise comparisons learns nonexistent correlations in the uncorrelated case while in the correlated case, initialization can play an important role as apparent by the change in value in the first cell of the second row. We report the performance in Table 1. The location μ can either be zero sampled randomly, the covariance matrix can either be the identity matrix I, diagonal random rl, plus minus one bin, and random r. In all cases the best-of-three probit matches the performance direct method (with simulation).
For real data, we use the data from a sushi preference dataset (Kamishima, 2003), the eigen-tase taste joke dataset (Goldberg et al., 2001), Netflix prize (Netflix, Inc., 2006), and the Movielenns dataset (Harper and Konstan, 2). The sushi dataset is the only ranking dataset. It's A variant is the only dataset where every user rank every alternative. The results are presented in Table 2. We observe that training with best-of-three observations lead to great improvement over probit models trained with best-of-two observations. The mean effect are strong in these datasets and the improvement over the logit is modest. Table 3 lists some movies with strong correlations in the Netflix and MovieLense datasets. In particular we note that we find sequels like Spider-Man (2002) and Spider-Man 2 (2004) or Kill Bill Vol. 1 (2003) and Kill Bill Vol. 2 (2004) to have strong positive correlations while we find a strong negative correlation between more critically acclaimed movies like Memento (2000) and Eternal Sunshine of the Spotless Mind (2004) compared to Hollywood comedy and blockbusters like Perl Harbor (2001) or Cheaper by the Dozen (2003). In Figure 7, we see that sea urchins are very divisive and that preference for cucumber sushi negatively correlates with preference for toro (fatty tuna) sushi.
We finish this section with welfare maximization experiment. We evaluate the welfare maximiz- ing subset of alternatives given a fixed size, i.c., solve the following equation for some fixed N, maxRcc.|R/=> E [maxier X,). We use the models from the previous experiments to generate wel-
8

---

Published as a conference paper at ICLR 2026
Netlix
Indepenkance Day
Translation (2003)
Spider-Mar
Spider-Man (2004)
0.56
Maid in Manhattan (20002)
The Royal Tenenbaums (2001)
-0.42
Adaptation (2002)
Lost in Translation (2003)
0.57
Miss Congeniality (2000)
The Marrx (1999)
-0.41
Kill Bill: Vol. (2003)
Kill Bill: Vol. (2004)
0.57
Memento (2000)
Pearl Harbor (2001)
0.41
Fight Clab (1999)
The Usual Suspects (1995)
0.59
Double Jeopardy (1999)
Fternal Sunshine of the Spo...
-0.40
Lord of the Rings: The Retu...
Load of the Rings: The Two
0.64
Cheuper
(2003)
Memento
Finding Nemo
(...
screes)
Independacce Day (1996)
The Royal Tenenbaums (2001)
-0.40
American Beauty (1999)
Being John Malkevich (19 (1999)
0.66
Anchorman: Legend
Speed (1994)
Rings: Fell...
Lord Rings:
0.66
MovicLens
Much Ado About Nothing (1993)
Truth About Cats & Dogs. Th...
-0.46
Bravehaar (1995)
Litlle Women (1994)
0.53
Much Ado About Noching (1993)
What's Faring Gilbeer Grape..
-0.42
Crow, The (1994)
Mariel's Weddligg (1994)
0.53
Dangarous Minds (1995)
White Nighimare Before Christmus...
Seven
Fulber Bride Part
Mrs. Doubtlire (1993)
-0.39
Johnny Mremonic (1995)
Robin Hood: Mon in Tights G..
0.55
Little Women (1994)
Seven (n.ka.. Sc7en) (1995)
Congo (1995).
Speed (1994)
0.55
Ace Ventura: When Nature Ca...
Little Women (1994)
-0.39
City Stäckers II: The Legen...
Little Women (1994)
0.59
Congo (1995)
Get Shorty (1995)
-0.38
Farher of the Bride Pari I...
GoldenFye (1995)
0.61
Johany Mnemonic (1995)
Nothing (1993)
Hudmncker Proxy, (1994)
Romance (1993)
Table 3: Left to right, movies with the lowest and highest correlations probit learned from the Netflix (top) and Moviel (bottom) datasets. A table with more movie pair is produced in Appendix F.
10a
percentage
4x
choice
choice
choice
logit
probit
probit (painwise)
Figure 3: Preference of the welfare maximizing choices, left to right for 1,2, 3.
fare maximizing subsets of size to 3 in the sushi-A dataset. Figure 3 illustrates what percentage of corresponds
the test population have their ith preferred alternative in the set, c.g., the bar with to the ratio of people who have at least their third favorite alternative in the set. We acknowledge that this quantity does not directly correlate with welfare welfare is sensitive the magnitude of utility change whereas this plot is not. It might not make significant utility difference for someone their second third choice are present but it affects this plot. Nonetheless, we see that for subsets of size and 3, more people have their preferred sushi on the menu. The optimal size one menu, for all RUMs, toro (fatty tuna), the optimal size menu according to the logit toro (fatty tuna) and maguro (tuna) while our probit suggests uni (sea urchin) and maguro (fatty tuna) instead. Looking the output the model in Figure 7 we see that the utility of uni (sea urchin) has high variance and correlates negatively with the utility of toro (fatty tuna) and maguro (tuna). This difference in menu highlights the problem with not modeling correlations properly, a menu of two alternatives that are high utility is not much better than one with only one alternative if they are very correlated. The probit learned from pairwise comparisons instead suggests anago (eel) and toro (fatty tuna) instead.
CONCLUSIONS AND FUTURE DIRECTIONS
In this paper, we investigated the methodological shortcomings of learning correlated reward models from simple preference data. We established the statistical deficiency of pairwise comparisons for identifying correlation and showed that best-of-three preferences are provably sufficient. Our anal- ysis culminated in a statistically and computationally efficient estimator for this setting, complete with finite-saman sample guarantees. Ultimately, findings show that modeling preference correlations not only feasible but essential for enabling more advanced applications like in-context learning and the strategic sampling of alternatives.

---

Published as a conference paper at ICLR 2026
REFERENCES
Simon P Anderson, André De Palma, and J-F Thisse. 1988. A representative consumer theory of the logit model. International Economic Review (1988), 461-466.
Usman Anwar. Abulhair Saparov, Javier Rando, Daniel Paleka, Miles Turpin, Peter Hase, Ekdeep Singh Lubana, Erik Jenner, Stephen Casper, Oliver Sourbut, Benjamin L. Edelman, Zhaowei Zhang, Mario Günther, Anton Korinek, José Hernández-Oralloe Lewis Hammond, Eric Bigelow, Alexander Pan, Lauro Langosco, Tomasz Korbak, Heidi Chenyu Zhang, Ruiqi Zhong, Seán Ô hEigeartaigh. Gabriel Recchia, Giulio Corsi, Alan Chan, Markus Anderljung. Lilian Ed- wards, Aleksandar Petrov, Christian Schröder de Witt, Sumeet Ramesh Motwani, Yoshua Ben- gio, Danqi Chen, Philip Torr, Samuel Albanie, Tegan Maharaj, Jakob Nicolaus Foerster, Florian Tramèr, He He, Atoosa Kasirzadch, Yejin Choi, and David Krueger. 2024. Foundational Chal- lenges in Assuring Aligmment and Safety of Large Language Models. Trans. Mach. Learn. Res. 2024 (2024). https: : openreview....c net/ forum? wewrruummi=oootoosee do=oTkossPkka
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Ols- son, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran- Johnson, Ethan Perez, Jamie Kerr, Jared Mueller, Jeffrey Ladish, Joshua Landau, Kamal Ndousse, Kamile Lukosiute, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noemí Mer- cado, Nova DasSarma, Robert Lasenby, Robin Larson, Sam Ringer, Scott Johnston, Shauna Kravec, Sheer El Showk, Stanislav Fort, Tamera Lanham, Timothy Telleen-Lawton, Tom Con- erly, Tom Henighan, Tristan Hume, Samuel R. Bowman, Zac Laffield-Dodde Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan. 2022. Con- stitutional AI: Harmlessness from AI Feedback. CoRR abs/2212.0800 (2022). https: //doi. oro/ 10. 4 48550 ARR.VV/ 2212. 08073 arXiv:221
Moshe E. Ben-Akiva. 1973. Structure of passenger travel demand models. Ph. D. Dissertation. Massachusetts Institute of Technology.
Austin R Benson, Ravi Kumar, and Andrew Tomkins. 2016. On the relevance of irrelevant alterna- tives. In Proceedings of the 25th international conference on world wide web. 963-973,
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. 2013. Concentration inequalities. Oxford University Press, Oxford. A nonasymptotic theory of independence, With a foreword by Michel Ledoux.
J. Bretagnolle and C. Huber. 1979. Estimation des densités: risque minimax. Z. Wahrsch. Verw. Gebiete 47, 2 (1979), 119-
David S Bunch. 1991. Estimability in the multinomial probit model. Transportation Research Part B: Methodological 25, 1 (1991), 1-12.
David S Bunch and Ryuichi Kitamura. 1991. Probit model estimation revisited: trinomial models of household car ownership. (1991).
Clément Canonne. 2023. A short note on an inequality between KL and TV. arXiv:2202.07198
Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, Tony Tong Wang. Samuel Marks, Charbel-Raphaél Ségerie, Micah Carroll, Andi Peng, Phillip J. K. Christof- fersen, Mehul Damani, Stewart Slocum, Usman Anwar, Anand Siththaranjan, Max Nadeau, Eric J. Michaud, Jacob Pfau, Dmitrii Krasheninnikov, Xin Chen, Lauro Langosco, Peter Hase, Erdem Biyik, Anca D. Dragan, David Krueger, Dorsa Sadigh, and Dylan Hadfield- Menell. 2023. Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feed- back. Trans. Mach. Learn. Res. 2023 (2023). https: //wp//oeeevveeeeeeeeeeeeeeeeeeee net forum? id= bx2 4x44K
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017. Deep reinforcement learning from human preferences. Advances in neural information processing systems 30 (2017).
10

---

Published as a conference paper at ICLR 2026
Charles E Clark. 1961. The greatest of a finite set of random variables. Operations Research (1961), 145-162.
Vincent Conitzer, Rachel Freedman, Jobst Heitzig, Wesley H. Holliday, Bob M. Jacobs, Nathan Lambert, Milan Mossé, Eric Pacuit, Stuart Russell, Hailey Schoelkopf, Emanuel Tewolde, and William S. Zwicker. 2024. Position: Social Choice Should Guide Al Alignment in Dealing with Diverse Human Feedback. Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net. https://cpenreviie .et//
Gerard Debreu. 1960. Reviewed Work: Individual choice behavior: A theoretical analysis. The American Economic Review 50, (1960), 186-188.
Patrick Ding, Guido Imbens, Zhaonan Qu, and Yinyu Ye. 2024. Computationally Efficient Estima- tion of Large Probit Models. arXiv preprint 2xiv:2407.00377 (2024).
Guiyun Feng, Xiaobo Li, and Zizhuo Wang. 2017. On the relation between several discrete choice models. Operations research 65, 6 (2017), 1516-1525.
Guillermo Gallego and Ruxian Wang. 2014. Multiproduct price optimization and competition under the nested logit model with product-diiferretiatee price sensitivities. Operations Research 62, (2014), 450-461.
Alexandra Gessner, Oindrila Kanjilal, and Philipp Hennig. 2020. Integrals over Gaussians under lin- ear domain constraints. In International conference on artificial intelligence and statisties. PMLR, 7774-2774.
Ken Goldberg, Theresa Roeder, Dhruv Gupta, and Chris Perkins. 2001. Eigentaste: A constant time collaborative filtering algorithm. information retrieval 4, (2001), 133-151.
F Maxwell Harper and Joseph A Konstan. 2015, The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiss (2015), 1-19.
Alex Havrilla, Sharath Raparthy, Christoforus Nalmpantis, Jane Dwivedi-Yis Yu, Maksym Zhuravin- skyi, Eric Hambro, and Roberta Raileanu. 2024. Glore: When, where, and how improve Ilm reasoning via global and local refinements. arXiv preprint arXiv:2402.10966 (2024).
Josef Hofbauer and William H Sandholm. 2002. On the global convergence of stochastic fictitious play. Econometrica 70, (2002), 2265-2294.
Wagner A Kamakura. 1989. The estimation of multinomial probit models: A new calibration algo- rithm. Transportation Science 23, 4 (1989), 253-265.
Toshihiro Kamishima. 2003, Nantonac collaborative filtering: recommendation based on order re- sponses. Proceedings of the ninth ACM SIGKDD international conference on Knowledge dis- covery and data mining. 583-588
Diederik Kingma. 2014.
Adam: A method for stochastic optimization.
arXiv preprint
arXiv:1412.6980 (2014).
Ychuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix factorization techniques for recom- mender systems. Computer 42, (2009), 30-37.
Steven Lamontagne, Margarida Carvalho, Emma Frejinger, Bernard Gendron, Miguel F Anjos, and Ribal Atallah. 2023. Optimising electric vehicle charging station placement using advanced dis- crete choice models. INFORMS Journal on Computing 35, 5 (2023), 1195-1213.
Duncan Luce. 1959. Individual choice behavior. Vol. 4. Wiley New York.
Haipeng Luo. Qingfeng Sun, Can Xu, Pu Zhao, Jianguang Lou, Chongyang Tao, Xiubo Geng, Qing- wei Lin, Shifeng Chen, and Dongmei Zhang. 2023. Wizardmath: Empowering mathematical rea- soning for large language models via reinforced evol-instruct. arXiv preprint arXiv:2308.095: (2023).

---

Published as a conference paper at ICLR 2026
Daniel McFadden. 1980. Econometric models for probabilistic choice among products. Journal of Business (1980), S13-S29.
Daniel McFadden. 2001. Economic choices. American economic review 91, 3 (2001). 351-378.
Daniel McFadden and Kenneth Train. 2000. Mixed MNL. models for discrete response. Journal of applied Econometrics 15, 5 (2000), 447-470.
Ranjini Natarajan, Charles E McCulloch, and Nicholas M Kiefer. 2000. A Monte Carlo EM method for estimating multinomial probit models. Computational statistics & data analysis 34, 1 (2000),
33-50.
Netflix, Inc. 2006. Netflix Prize Data.
Carolina Osorio and Bilge Atasoy. 2021. Efficient simulation based toll optimization for large-scale networks. Transportation science 55, (2021), 1014-1024.
Leandro Pardo. 2006. Statistical inference based divergence measures. Statistics: Textbooks and Monographs, Vol. 185. Chapman & Hall/CRC, Boca Raton, FL.
Roland T Rust and Anthony Zahorik. 1993. Customer satisfaction, customer retention, and market share. Journal of retailing 69, 2 (1993), 193-215.
Jesper R-V Sørensen and Mogens Fosgerau. 2022. How McFadden met Rockafellar and learned to do more with less. Journal of Mathematical Economics 100 (2022), 102629.
Taylor Sorensen, Jared Moore, Jillian Fisher, Mitchell L. Gordon, Niloofar Mireshghallah, Christo- pher Michael Rytting, Andre Ye, Liwei Jiang, Ximing Lu, Nouha Dziri, Tim Althoff, and Yejin Choi. 2024. Position: A Roadmap to Pluralistic Alignment. In Forty-first International Con- ference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net. https:/ / https://pppeneee //ppprpeeeeeeeeeeee/eeeeeeeeeeee net forum? forum?id=gQpmmeee d=g@@pBnRäwxx.
Kenneth E Train. 2009, Discrete choice methods with simulation. Cambridge University Press.
Alexandre Tsybakov. 2009. Introduction nonparametric estimation. Springer. New York. xii+214 pages. https: /oii.oioooooo//oooo org/ 10. 00.1000011399 Revised and extended from the 2004 French original, Translated by Vladimir Zaiats.
Amos Tversky. 1972. Choice by elimination. Journal of mathematical psychology 9, 4 (1972), 341-367.
Martin J. Wainwright. 2019. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, Cambridge.
Keji Wei, Vikrant Vaze, and Alexandre Jacquillat. 2020. Airline timetable development and fleet assignment incorporating passenger choice. Transportation Science 54, (2020), 139-163.
Keji Wei, Vikrant Vaze, and Alexandre Jacquillat. 2022. Transit planning optimization under ride- hailing competition and traffic congestion. Transportation Science 56, 3 (2022), 725-749.
Yanzhao Zhang, Mingxin Li, Dingkun Long, Xin Zhang, Huan Lin, Baosong Yang, Pengjun Xie, An Yang. Dayiheng Liu, Junyang Lin, Fei Huang, and Jingren Zhou. 2025. Qwen3 Embed- ding: Advancing Text Embedding and Reranking Through Foundation Models. arXiv preprint 26X1v:2506.05176 (2025).
A
PRIOR WORK
There has been considerable interest in scaling probit estimation, with recent techniques extending the method from ten alternatives (e.g., Natarajan et al., 2000) to one hundred (e.g.. Ding et al., 2024). As show in the next section these methods cannot actually recover the correlations properly.
The nested logit (NL) relaxes the IIA axiom by grouping the alternatives in the groups and assuming IIA between the elements of the same group the groups themselves. In the cat, golden retriever,
12

---

Published as a conference paper at ICLR 2026
and borzoi example, this can mean that first, the agents choose whether they prefer cats dots and then choose between gold retrievers and borzois. In this structure, IIA holds between cats and dogs and between golden retrievers and borzois, but not between borzois and cats. In its generality, the NL is described by tree whose leaves are the alternatives. To choose an alternative, an agent starts at the root and must select one of the current node's children using IIA model. The agent repeats this process until they reach a Icaf (alternative). Ben-Akiva (1973) showed that the welfare and choice probabilities of the NL can be calculated in a bottom-up fashion as the value of each node is the log-sum-exp of the values of its children. Benson et al. (2016) show that at least (2(n²) () statistical tests are required recover the structure of the NL.
The mixed logit McFadden and Train (2000) relaxes the IIA axioms by assuming that there exists an unobserved utility that would validate IIA. Since we do not observe these utilities, we have to marginalize them. The mixed logit is defined as
( = 2} = (v,u + + A, P u, + +
sm, (u (),
In practice, the integral is evaluated using numerical methods, and the mixed logit is learned using MLE. McFadden and Train (2000) showed that if they take the limit of 7 to O, this model converges to RUM with utility A because the softmax converges to the indicator function, returning one when A; > Aj for all j and zero otherwise.
Over the years, many choice models have been developed and RUMs by no means the only class of choice models. We can characterize them by
representation power, for instance, the logit cannot represent correlated choices,
2. number of parameters, while the logit has n |C] parameters, the probit has n(n + 3)/2 parameters, and
3. whether they provide some notion of welfare.
Representative agents models (RAM), are defined as
[IR = 1] arg max (x,, uR) D2 (2x(()) (Tz) TEA(R)
for some utility vector u restricted the set of alternative R, some strictly convex regularizer Qx, and the probability simplex over R. denoted by ARR). RAMs also provide an expected welfare function, but learning a regularizer for all possible sets of alternatives may not be trivial. Taking Q to be the negative entropy yields the same model as the logit (Anderson et al., 1988). Generally, an equivalent RAM exists for every RUM but not vice-versa (Hofbauer and Sandholm, 2002). As noted by works like Sørensen and Fosgerau (2022), working with RAMs may be more convenient for mathematical purposes. We refer to Feng et al. (2017) for a class halfway between RAMs and RUMs.
Tversky (1972) introduces a different class of models, where each agent splits the set of alternatives in desirable and an undesirable subset. While the model has an exponential number of parameters (in terms of the number of alternatives) and requires a different type of data, is subset-consistent for all possible choice models.
A wealth of work exists approximations for the probit model starting with Clark (1961). Clark approximates max X, Y) with a normal distribution. We refer to Kamakura (1989) and Bunch and Kitamura (1991) for references to other approximation methods. We note that Bunch and Kitamura (1991) finds that none of the approximations consistently outperform others, and all have critical failure modes. Compared to simulation- based methods, one of the most significant weaknesses of this type of work is the inability to trade compute for accuracy.
Train (2009. Chapter 5) and Bunch (1991) mention several ways of removing the symmetries in esti- mating probit models and how to verify that the parametrization is "correct". Interestingly, they omit our reparametrization. McFadden (1980) claim that the primary issue with the probit is evaluating and differentiating the choice probabilities.
Notation. We use R and N to denote the set of real and natural numbers respectively. For n E N, R" and Baxx denote the set of n-dimensional vectors and n. dimensional matrices respectively.
13

---

Published as a conference paper at ICLR 2026
Furthermore, S" and S"x* correspond to the of unit vectors and positive semi-definite matrices of dimension n. For n E N. [n] is shorthand for {l...., ,n We denote the pdf and edf a standard Gaussian & and 4, respectively. For matrix A, Tr(AA) and det(A) denote the trace and determinant of A. For two vectors & and in IR, (x, y) is their inner product. We use TV and KT. for the total variation and Kullback-Leibler divergence. Lastly, Choice(ps E), for μ TR" and " E R refers to the choice model defined by a RUM whose utilities follow multivariate normal distribution (n, 2) whose mean is μ and covariance matrix is E.
B ESTIMATION WITH THREE ALTERNATIVES: PROOF OF THEOREM B.
Here, we extend the arguments of Theorem 4. presented in Subsection 4.1 the setting of estima- tion, where one aims to. Recall, our observability assumption from Section 5:
Assumption 5.1. (Observabilityy For any three alternatives i, k E [x]] and X ~ NN, E):
P P
for some > 0.
The main theorem of the section is stated below:
Theorem B.1. Let (1, Σ) R 33x3 satisfy Assumption 5.1 for some " 0 and E, 10.1/2). Then, there is an algorithm which when given n i..d samples from Choice(μ, E), returns estimates, (i, 2) satisfying for some t >> 0:
1| - A E
(1 E)PE x5 E (1+
Tr(P)), Tr(:.) > 2
with probability at least as long as n > Ce Cc 2 log( (0g) log/ (1/(re)). (og(()))))((
We begin with some useful technical results. The first concerns the maximizer of the minimum of the Gaussian masses of two symmetric cones defined by the intersection of two half-spaces.
Lemma B.2. Let U1. E S?. Then, we have:
arg max (min (Px-Ntnn((XX e1), (X, v2) > 0), PX un), (X, (x, & 0)}) = O.
"
Proof. Consider any μ A 0. Note, that without loss of generality, we may assume:
sin(O) ] cos 02
ssin ()) cos
U1
for some 0 e [0, x/2]. Now, observe:
00
2 tau
(a - 11)² (1) 1222
& = (Xx, v2) > 0) =
2x Ju
exp
dyde
tan 0 tan
2
(-x 111111 2 + (y -M2)²
& = [[=Px-innn((X,,) v2) < <0) 2n
exp
dydæ
- tan
When > 0, (x + )1) > 2 for all x > 0 and consequently:
tan 0
x² + 222
2
exp
dydæ.
2x
Similarly for in with & taking the place of & Therefore, for any nz: arg max min(f1, E2) 0.
14

---

Published as a conference paper at ICLR 2026
Claim B.3. We have for any t > 0:
exp {
(x - 1)²
arg max
2 dr = 0.
1
Proof. First, define
f(n) = 1" exp { (x- -1)2
da.
We now have:
d dp 1() /" (w-N)) 1))
(x - 2x) dr
-/u0u00 exp (-u exp
(1-W)992 (1tW)//2
{- (t+ nx) 2
(t - 11)
exp
2
2
Hence, we have:
< 0 i 0
d
f())
cf otherwise
du
0
Hence, μ is the unique minimizer of (() concluding the proof of the claim.
From Claim B.3, we get for any p2 + O:
1
tan 0
exp (2 + +²²²
dyde
2T Jo -rrtan
2
(x=~((0,1) ((X, v1), (X, v2) 0) = ((X,). (X,02) & <0}
concluding the proof of the lemma.
The following lemma establishes the probabilistic concentration properties required for our result with the parameter ह to be chosen subsequently.
Lemma B.4. There exists constant C' > 0 such that:
Vel, 02 E ( s. H 12:
1((,, (X), > 0} - (x 203 E
71 1=1
Vu E {
1 1( v) > 0} - PXxNNuDD > E
with probability at least - 5 if Clog(1/8)/3
Proof. The lemma follows from Hoeffding's inequality (Theorem E.1) along with union bound over the 18 events in the conclusion of the lemma.
The next lemma shows that permutation probabilities remain stable under mild perturbations of the center of Gaussian.
Lemma B.5. Let μ I and S be set such that:
P (X E E
Then, we have:
Vy' E BB(,s)) PPx-NW ( -
-P E S)| & 4e [x S).
15

---

Published as a conference paper at ICLR 2026
Proof. Let 1
0 without loss of generality and defining 2(v 2(vlog(1/((s)) + +e), we have:
1
1
p p'1l2
P(X E ES
exp
dx
2π
2
1
100 111
| 1 1'112
exp
dr JS exp
2T
SSBB(0.r
2
| - 11113)
dr + (Ro-Nwsnn(GG rr}
exp
2T SSB(0,r)
2
1
| 1a112 dr + +Po-Nio. 2 t}
exp
2T
ShB(0,r)
1
|00| + ||a|12 - 2(x,, n²) jda Po r-
exp
2TT SSB(0.r)
2
1
|0012 2(zx
exp
dx + 7
2T ShB(0ir)
|x:1
2TT (Sn3(a.))
exp for) exp
dr + YE
exp P (X ES + 7e (exp(er) + + Px-N (X E S)..
For the lower bound, we have:
1
| - 1/ dr
P(X S) = 2x g
exp
1
|| - M/
dr + / JSrB(or))
|x 1
JSnE(a.))
exp
exp
dx
2x
2
2
1
|| - 11/13
exp
dr
2x
SSB(O.r)
2
||0|| + 1/ 2(xx, v2)
exp
do
2R
2
1
||
exp ( (-E(E + +r]
exp
dx
2π
SnB(0.r)
exp (-E(E +r]
||0112
||
exp
dr
exp
2 dx
2T
55
2
SSB((,r))
exp
(-5(E +r)}
|
1|=-112
2
exp
dx
exp
dx
2T
2
(R((B(O.r)
2
= exp {-e(E + (P
(X E -xx-vo.n(x/x]] r))
> c(e + () (XES)
> (1 22(E + +))) (X e S}
which concludes the proof of the result.
We also require the upper bound on the Gaussian tail. Lemma B.6. For all t 2 0, we have:
t2
FX-NOD(X>> >
< 2
exp
We will now adapt the three steps outlined Section for estimation. These proofs are similar to those for identifiability but substantially more technical. We will adopt a more streamlined
16

---

Published as a conference paper at ICLR 2026
notation for this proof. Recall that Section required two projections, the first to reduce the dimen- sionality to 2 (Figure 1) and another to reduce the 2-dimensional Gaussian to the isotropic setting. Here, we will instead work with single transformation. We start by defining:
1
1
=
02 = 1 c3 =
-
0
For the utility vector I' MH, Σ), we observe the permutation
> ug when (c1, >
and (c2, O. Similar conditions may be derived for all other permutations. Note that c1 02 and Og are linearly dependent + C3. and any two form a basis for the subspace orthogonal to 1.
Consider the linear transformations Σ 1/2 E R and / E R2x3 where
Σ 5-1-2((E-1/3)
Id(2),
(3)
Σ (x1/(()) = Id(2)
(4)
E1/2 44 [1] and
(5)
[ 12
E1/202
where l2 > 0.
(6)
Since we assume that has rank 2, (3) must have a solution. Since the left-hand side of (3) invariant to rotations and reflections, without loss of generality, (5) and (6) can be satisfied. Observe that this implies a similar property for ca as ej + C2 = C3.
Let 1/2 p and consider the transformed vectors:
E4/22
E1/20z and c3
E1/203
/ C2
|/1/2aa||
We now show that the quantities (C,, are estimable under the conclusion of Lemma B.4. This extends the identification result from Lemma 4.2.
Lemma B.7. Defining the estimates:
6 = +
1(X,, 200)
03 and
and a, = (0,, M.),
we have:
|0; - arl & V2T
2 log( (17) < ā. as < V2log(177).
Proof. Recall from Lemma 4.2:
Φ (Px~N(u.)) ((,aa) 0}).
0;
Furthermore, we have from Assumption 5.1 and Lemma B.4:
n
?
1(x, > 0) < 1
7
1=1
Therefore, we get from Lemma B.6:
log 1/7) < az 0z & / 22llgg11/
Using this fact, we obtain:
E ( [(a)) | (x))dr
x22
1
a; 6c
min 2E(a,,a
cxp
a;
2TT
2
2
By re-arranging the above, get:
10s - -2--6 E 2
concluding the proof of the lemma.
17

---

Published as a conference paper at ICLR 2026
Next, we adapt the second step of our identification argument (Lemmaa 4.3) to estimation. As before, this step is substantially more involved to account for the statistical noise.
Lemma B.8. Let μs IR² and vi, v2 be two linearly independent unit vectors. Suppose, further that estimates di 3 d2 z are known estimates such that:
| ()),p)) & & and [dz (v2, pb) E.
Furthermore, assume that the following hold:
Yuz E {=vi), u2 { PPx~N(., ((X, u1), u2) > 03 > ? and we have access to estimates, oo Pass with:
[io1,22 Px~N(unn (XX $1), (X, 82) 0f s.
Then, we may recover estimate B such that:
1 (11, v2)1 - aa Vlog(1/(13))
from d1, dz, and Ff
Proof. As in the proof of Lemma 4.3, may assume U1 e2 and (u2) > without loss of generality. Since, U2 is a unit vector, it may be parameterized as v(0)) for 0* E [0, with v(0) defined follows:
sin(0) v(0) - -cos(o) for A E [0,
Now, defining (i()):
[i(0) d, where jı(0) d cos(()) + dz sin(
((0) =
Our estimate of 0* (with cos(IT 0-) (2)) is defined below:
0 arg min (e
max
(x (0) where fx .s (0)
| (Xx_NaeL))(Xxe)) 82) 0) -/
Our proof that is close to 0" will proceed in two steps:
1. In the first step, we show that is solution with small error
2. Next, we show that all points outside a small interval around have large error.
Claim B.9, We have:
vsa E ( 82 E {+02} Ln ( < 64c Vlog(1/(7E))
y
|| ((00') < - ?
Proof. Observe from the rotational symmetry of standard Gaussian that for any u1, u2 E St:
Px= uI), (X, u2) > 0} arccos (u1, u2))
2T
Hence, applying Lemma B.2 with the vectors (0), 02) yields:
0r < π 2m7y
2x
Similarly, applying Lemma B.2 with the vectors (V1, -1:) yields:
0r > 2my
Hence, we get:
2my & T - 2 - sin( > -2my = 4y.
18

---

Published as a conference paper at ICLR 2026
Now, observing that:
di cos 1
1
sin (1*)
d1
we get:
di cos + d2
di cos + its
1| - 7000)|1 <
+ 111 dz
sin(f") (8r)
(6*)
dj dz (l0)
+ < 1_ 7 Id2 2zl (zllcsc(00))
yielding the first claim. The second now follows from Lemma B.5.
We now proceed to the second step of the proof. We start by bounding 70(0)).
Claim B.10. We have:
(T()0) < [a(0') & (20gg11/22))
Proof. Furthermore, observe that:
v0 0, far m)) (0r, 02) > 0) S (x in 20
A0 2 .
: {a: : (z, u1), (2, > 0) S fa : x > 20.
As a consequence, in both cases:
P PX-N(un 3 0} 3,
Hence, we get from Lemma B.6:
1n 2 - 220g(1122))
Similarly, we get
44 E
0, π
: {x: : (r. -u)) u22) > 0} C {x: <
2
AA E
2 n
fm: (x,, mi, (x, -2)) > 0} C (x :: ().
We, hence, get consequence:
Px <0} >
Lemma 8.6 similarly yields:
in & 2 /2log(1/(22)
Note, before:
di casi0 c + e d1
Finally, we get from Claim B.9:
| - ((0
[7(00) < (2log(1/(2)) +
concluding the proof of the claim.
Similar to Lemma 4.3, define:
700) = ((X v1), (2, < 0}.
The next claim lower bounds the derivative of क in interval around 0*.
19

---

Published as a conference paper at ICLR 2026
Claim B.11. We have:
40 E :00.)))((())))))
7. 16
40 10, 0n] (0) >
0 = 0" + == E (oolool(11)))
with 0 = 0"
Proof. The proof that (0) 0 for all 0 E (0, TT is identical to that of the corresponding result in Lemma 4.3. We now proceed the second claim. Observe as in the proof of Lemma 4.3 that:
1
(r cos (i)))² + sin
sin(()) (0) 2z)²
(0)
exp 2n
rdr
T0 + dc
1
y2 2r(cos(0)) (in(O)
exp
J
2m
exp
rdr
700)2 + RP
22 2r 2c(os (r(cos00) (0) + sin sin (0));)
exp
exp
rdr
2T
((0)2 + 2
2(( (d.l)
r2
exp
exp
rd
2
2T
T( + 21 + 2(1((0))++ (2
1
1
2
exp
2
16
16
16
where the last inequality follows from the following:
[x(0)] [ā(00)| + (0,, 01) max
17' (0)
8E(9: 6m.
d de cos(O)
/log(2/7)
|=(00)] + (0n, 01) max
< [0(00) + (0,. -0)
#c 6x]
sin (0)
72
concluding the proof of the claim with Claim B.10.
From Claim B. we get that:
v
V0 0n (0)) 700)) +
16
A0 < 0, 70)) > 700)
16
Consequently, we obtain from Claim B.9 and picking C" large enough:
vy
64s
128e
A# > 0p -())= - -0. >
Vlo((1/(75)}
> Vlo((1/(7E)
16
y
?
64g
2y
128
A0 < 0: - -()) E Vlg((1/(7E))
< γ
Vlog(1/(1))),
16
Hence, we get that Ø E [0,, 0n]. Defining 3 = - cos the conclusion follows from the 1- Lipschitzness of the function cO).
Proof of Theorem B.I. The proof proceeds similarly to that of Theorem 4.1. Let È be parameter that will be chosen subsequently. We have from Lemma B.4 that:
Yer, U2 E (
3 s.t. 01 R 02:
Σ 1((,,, 01), (Xa, U2) 2 0} PX (X,v)) 02) > 20} 3 n 1=1
20

---

Published as a conference paper at ICLR 2026
Ve E {ta))==l n
(( > 0} - PX > 20} <
with probability at least when n > C(log(1/8)/22) We condition on this event in the remainder of the proof. Recall the definition of the vectors:
E1/2
/ and j = Σ- 1/2
From Lemma B.7, we obtain estimates, 0g such that:
85 = 6' K7, (4) ãs <
7
An application of Lemma B.8 now yields estimates B. for all i.j E [3] such that:
(lol((1/(77)) = = BBg (ā, & C ?
We now fix the normalization of 1// and assume without loss of generality that:
g1/2 = [] x//222 =
312
and E3/2c3 = [[ Bi3
813
[V
8i
Noting that C₁ + 02 = C32 we get similarly to before:
0
313
312
8
13
As observed in Theorem 4.1, the above equations allow for identifiability of Σ. However, for es- timation, we incur errors due to inaccurate estimates of quantities Big and s. We start with the corresponding empirical approximation of the above equality:
1 [
B13
B12
Bi
VI
B
In our first claim, we bound the approximation error of the above matrices by their empirical coun- terparts. Define:
81
B1g
31z
B, V
Vi,j E [3] Bij
and Bij =
B
V
B7
3
Our approximation guarantees stated below:
Claim B. We have:
det BBy))
2y and del (Bjg)
>
Y
π
| 11. [
<
4et
BBg B &
7
[B5 ||
<
π
and ||
<
2π
7
8 73
| B &
Proof. We have consequence of Lemma B.2 and Assumption 5.1 that (τ, cos(Org) for some 7 < Oú & π - 7. Similarly, we get from the approximation guarantees of Lemma B.8 that the empirical estimates satisfy (2,, C5) cos(O.,) for 7/2 & G. & 7/2. Consequently, have:
|det (By) > |sin(0:;)) > and det B.y)) > sin( > 7
2
π
21

---

Published as a conference paper at ICLR 2026
establishing the first result of the claim. For the second, we have:
|B,y < |B,,]l = V2
and similarly for Baj. For the third, observe again from the guarantees of 0;j and 0:
|1 B3 - 11 3/
(Be, + B1y) - (.y))
2ct
V1- 18/ + V1 3/g
7
and consequently,
2st 4=t
B Bulll & BBg Biy 11 & 2.
7
For the fourth claim, we have:
| ||
|B min! (Bis)
ddet BBj)) ]
and similarly, for Bij. For the final claim, we have:
7 B. B,j¹11 < mminl BB,j B,j²1 < Bij Bij || = || B,y BiJ I1
|| BBj -Bij Bi, Biy 11= |1(BiB - B
2T Bis Buyll & 8Tet
< Bis - B.y Buglll B <
72
Our next claim bounds the magnitude of s and the relative error of its approximation by s. Claim B.13. We have:
1 and s 3),1t 8 &
8
max {s,t)
2
7:
Proof. For the first claim, observe the following
B1st $128 = 1
s t 1,
implying the lower bound. For the upper bound: and the conclusion follows from Claim 12.. For the second, we have:
max {s,t) <
Bys
B
Is 31 F < (B
Bys')
<B
Bzs
and the conclusion follows from Claim B.
The remainder of the proof proceeds in two cases: 1) 3 > oo 2) 3. We start with the first:
Case 1: $ > f. Since and C2 are basis for the subspace orthogonal to 1, we may write:
E1/2 = AC' where C' = and A E R2x2
Therefore, we get:
D//2CT = A(CCT)=
31122
A =
312
1 0
(CCT)-1.
0 sv1 K
0
0
22

---

Published as a conference paper at ICLR 2026
We may write its empirical counterpart:
1
312
0
)-
=
0
Bi
0
8
Noting that ((CCT)-1)
1, get from Claims B.12 and B.13:
0]
1
0
1
0
0
0
| All
<
B12
- B1
B - B12)
B12
0
8
8
$
< (B12 - B12)
0
(
[
0
8
+
B12
0
8- - 3
0
4st
2m
8
< B B1el max {1,5} + | fi2llss 3
+
2
24
7
?
7
703
Furthermore, we have for any v E IR with | 1 1:
|uul| = B12
1 0
(CCT)-1o)
> Omin (B12) amin
[
0
min ((CCT)-2)
0 8
min {1, 1
7
12T
where the inquality follows from an explicit calculation for (CCT)-2, Claim B.13 for the middle term and Claim B.12 for the first term. Similarly, note that:
(1 0 2) m ((CCT)-)
|
B12 0
(CCT)-1o)
-to
< mmax (B12) Fmaax
2x 7
< 2 max (1,
1<
from Claims B. and 13. Consequently, we obtain for ||a||| =
o A Au T. AT Au
|c|| | |3 All
|| ||| || ||lll 111 ||
< (||| + ([A Ajoll <
4
+ I|A - 211) I1A
All
120
74
From the above three displays, we get:
(1- (1-st)ATA A A < (1 + AAA A where et 5et
76
Finally, defining estimate 11 ÁC and since > CT AC, get:
(1 - _ Σ Σ (1+
Case 2: f> S. Here, we use ej and 03 as a basis for the subspace orthogonal to 1 and write:
I1/2 = AC where C = and A E R2X2
Therefore, we get:
= A(CCT) 1
tβ13 W1 - B
1
313
1 0 t
(C
A
VI
Bi
The remainder of the proof is identical to the previous setting with taking the role of s and Bia (resp B1T) that of B12 (resp B1x). This concludes the estimation guarantees for Σ.
Estimating μ: To estimate μ4, adopt the Byd and C' from the previous two cases and note:
[ai
7 == Σ 1/2 n, B = Q = p= ( CT AT = AT AT (B with Q =
0s
23

---

Published as a conference paper at ICLR 2026
Empirically, we use the estimates:
01 A= ( with @=
ai
Therefore, we get that:
2(1IA (BT))) II] TBIKQ (B))) (B
< ( (IT))) + ||AT - - Vlog(1/7))
For the first term, we have by Claim B.12:
2T
2n²
I| (AT |A IITI |||||
<
7 7
73
For the second, we have:
(AT(BT") -
| A) + 1I
BT A
<
||
||
|1|
Al
|B
BT
ĀlI
24st
2T et
+
73
73
7
71
Plugging this back into (7) yields:
200 v 1og(1/7)
1 Hll &
Now, setting:
Eq 10
E
log(L/(77))
for some small constant c, the theorem follows by the definitions of et and et.
C ESTIMATION MULTIPLE ALTERNATIVES
In Appendix B, we extended Theorem 4.1 to an algorithm with estimation guarantees (Theorem B.1) that is robust to statistical noise. Hence, we now have procedure that allows recovering the param- eters Σ on 3 x 3 sub-matrices (up to the symmetries described in Assumption 3.1). We now prove the main result of Section 5, Theorem 5.2, stated below for convenience, which uses the estimation algorithm for 3 items to construct one for the general n-item setting.
Theorem 5.2. Let (n*, E¹) satisfy Assumptions 3.1 and 5.1 with Tr(E*) n. Then, for any 5,5 E 1/2), given there is a polynomial time algorithm which when allowed N observations of rank-3 permutations from Choice( (x,"")) of its choice, returns estimates, (TI, E), satisfying:
|| - n² 1120 & and Σ Σ &E
with probability at least as long as N > Cn2 22 24 log log (n/(7e))
In Theorem 4.4, we showed that μ, E can be recovered from exact specifications of all 3 sub- matrices. However, this approach has 2 substantial drawbacks:
1. It requires comparison data for all of the 2(n²)) sub-matrices
2. The sub-matrices need to be specified exactly which is infeasible with statistical noise
24

---

Published as a conference paper at ICLR 2026
To reduce the number of sub-matrices required, formally relate estimation guarantees to the structure of sub-graphs on the following graph:
G= - E)
V ((i,)) (m) x (n] :
- (((.)) (., ( :
Observe that each potential sub-matrix corresponds an edge of the graph and the vertices cor- respond to entries of 2 that we aim to recover. Furthermore, note that particular choice of sub- matrices corresponds to sub-graph. The properties of this sub-graph relate to both of the afore- mentioned challenges:
1. The sub-graph being connected suffices for recovering E from 3 x sub-matrices
2. The error of this aggregation process scales linearly with the diameter the sub-graph
The next result (efficiently) constructs sub-graph with drastically fewer edges (O(n²) O(n)) while maintaining connectivity of the sub-gran sub-graph with small (logarithmic) diameter.
Lemma C.1. There exists a subgraph G' = (V, E") with E' C E satisfying:
|E| E n
Vel, v2 V dist (v1, v2) & 4(log(n) +).
Proof. We will construct our edge follows:
1. For any i E [n],, let V4 = [m] {i}
2. Consider a complete binary tree T; = (V,, E,) on V/
3. For any (j,k)= E E,, add edge ({i,j), (i,k)) to G¹.
First, observe that E' c CE construction. Next, we have:
E'
< n E n(n 2) < n²
For the final claim, have from the construction of E' and T; being complete binary tree:
vi + j + k + : distar ((i,j), (ú, k}) < 2(log(n) + 1).
Hence, we get:
dist ((t,j), (ke, (7) < distor (fi.j), (j. + dist ([j, (k, < 4(log(n) + +1)
concluding the proof the lemma.
Before we proceed, we introduce some notation to ease exposition. We will now run the algorithm of Theorem B. on the tuples (i. k) such that (fi.j), ; {j. k}) e E'. Let (figks Eigs) be the estimates obtained through this process. We will abuse notation and write j, k) E E" for the set of tuples. will be convenient to index matrices with alternatives rather than numerical indices. We will typically use Gú 6 - Ej with e; and ej corresponding the vectors with 1 for item and respectively and 0 elsewhere. the context estimates E, e, and ey (and consequently, c,y) will denote vectors in R for the positions corresponding and j while in the context of E, they will denote vectors in R
We now recover Σ* by solving the following convex program:
arg mint t
V.JjkEE' (1 t) Ci
c Eai
Eygnch cJ Eigh
< < (1+
c 5
Cigh Cak
Ca Eca
Tr(E))
25

---

Published as a conference paper at ICLR 2026
Σ1 = 0
We assume that the estimates, Eigt are obtained by the algorithm of Theorem B.1 with failure probability 8' 6/(2²²) and accuracy & for parameter غ to be decided subsequently. Letting Σ denote the solution to the above (linear) program and noting that > a solution with t = E, we get that Σ has cost most E. We require brief technical result bounding the largest entry of Σ.
Lemma C.2. We have:
ΣN 100 log(8/7)
Proof. By Markov's inequality, there exist two indices k such that Ejj: Exa 2. We start by bounding the distance between jij and pax Let X ~ N (uijk Eigh) and we have:
p P(Ix, Myl > 2 log(4//))
< 2
P(Ix= pul > 2 log 1oglo (l0((4/)))
< 2
From the above two inequalities and Assumption 5.1:
min (P(X; > XxX, < xx)) 31,
we get the following set of inequalities by the probabilistic method:
HS + 2v log((/))
> pt 2V/og(44/7 = #i My & 4 llg(4/7)
M3 - 22 log(4/) E Pr + 2 (lg(44/))
= Pkk - M1 > -4 4/lol//////
The above two inequalities yield:
M4 mal & 4 1vlo(4/77)
(8)
Next, we have again:
P P|1x |X, My1 >> 2 2olo((877)
W V
201 00122001-1
2012
P(IXs= pul > 2 1og(8/7)
By a union bound and using Eq. (8), we get:
Pf P(X,, E [Mg 8ylog(8/7).w 8/lo(88/7) }
> ?
Denoting the event in the above probability by E, we now have from Assumption 5.1:
7 < PX, [X,, Xx]] = P(X, XeJn) + +P[X; E (X,, n
< P X, E [n -
16 1og(o////7) + ?
V 2
4
By rearranging the above inequality,
64
100 log(8) (8/r)
VIn < 3 Vlog(8/7)
En <
22
We now show that E is close Σ
Lemma C.3. We have:
Wi,j E [n]
Eigl Cr ((lg(n)) + 1) 1og(8/7)E.
26

---

Published as a conference paper at ICLR 2026
Proof. First, observe from the fact that Σ1 0:
n
cfEc, = Di + Enj 25
Ciyy Eey = nIa + Tr(E) .nE + n.
(9)
==1
Furthermore, we have from the guarantees of Theorem B.1 that:
cij
Gj
Vi,j, E² (1 45)
& (1+ 42)
Cak
C. Csk
Putting these together with the constraints on E, we get:
Vi,j E E': (1 6E) "j Cn cz
Eoy
G3 Ctj
< (1 68)
Ca
C,k Cik
From Lemma C.I, that for any { and (k: 1) there exists path up == [i. .1...., ur = [k
with T v 4(log(n) + 1) with (1=-1,0)) vi) E E' for all i E (T]. Now observing that:
Cop Eces
T
CT
Ecu-.
Cop Eer
Co. Eee
1=1
Cup D Coo
c Σ Cu-1
En 1=1
We get for any i, i, k, k,, with i # j and l: + l:
(1 s1 E cij
Eeij
Cij
(1 + Et)
where et =00g(lo)))) + 1).
Cal Sens
C22 Cx
Now, consider the ratios:
ci Sais
Vi * ::yy
Mmin
min ray and Fmax max rtj. 13
c3j Cij
1)
As a consequence, we have for any i, i,j,k, k.
Tmin $ Tiax & (1 + 87) rmin-
Hence, we get:
Σ cij Eay n EEE + +1) = 2n2
=2n = =e c. C.
Tmin (2n?) = Tmin Σ
Gj E Σ
EJics = 2n² < mmax Σ CoTTeen oij & (1 e² Imin e1+mmmmm (2n?).
ij
Therefore, we get:
Tmin E E Tmax < (1 + (1+e!) emnn = (1 el) rmin & Tmax & (1+
Plugging this into to Eq. (9), we get:
n
(1==))((2++1)- = (1-e*) Σ ay n(E++1) < (1++))
Σ af (1=)))((27++1)
5=1
By re-arranging the above, we get:
Vi: E End & (2% + 1).
For the off-diagonal terms, observe:
Σnj cJ Less
En
Eng (++t)eeE - (1 (1- + Σラソ) + 22t
& +2
2
2
Similarly, we get:
En Eng
- -,
+ + - -2
Eny 2
< - +1).
2
Putting the above two displays together, we get:
Σig Eiyl & 26 ( + Eii + 1)
which with Lemma C.2, concludes the proof of the lemma.
27

---

Published as a conference paper at ICLR 2026
A similar approach now allows recovering j² with related convex program
Lemma C.4. We have:
l000
|
11000
Proof. We use High and Eija (and correspondingly for their starred and barred variants) denote the restriction of and E (and their variants) to the alternatives i, and k. and projected orthogonal the vector 1. We estimate some rescaling parameters obtain E from the way estimates. Define:
Tr(Eis))
e siy Tr(Eigh)
The linear program we solve to find j is defined below:
arg min &
Wijkk [18gaTeck Pisiello EL (n. 0.
Before we proceed, we prove analogue of Lemma C.2 which bounds the mean of μ..
Lemma C.5. We have:
40 10gg(8/>)
Vi [m] |pd <
Proof. First, define:
im max nas and im min us-
Consider the random variable:
Y Xiss Xim for X ~ (N, 2))
We have from Lemma C.2:
400 400 log(8/7)
E| = Piys - Mim. and Var(Y) <
72 = 0²_
However, also have:
P(Y <0)>> 12 < -(Migs pimm } 2 7.
Hence, we get from Lemma B.6:
|A < Piss Him & <0/21oog(1/),
concluding the proof of the lemma.
First, let:
Eig = 3 5. and pīju BighFliyk
be such that:
(1 E)-z & Eeje & (1 + E) 11 Puikell & E
guaranteed by Theorem B. Note that:
Fi Vl,m m E ki (1 - st )o Diz EyghCi & on Eigherm & (1+ Emm Cm.
As consequence, we have:
(1 - et) Σ
Am CignCim = (1- (1-61)671 -e)))TT(Eii))
& Σ
Cim Eig = 66 (T((E))))
Im
Im
< (1+ + Σ
ci = (1 +1+e (
Im
28

---

Published as a conference paper at ICLR 2026
As consequence, we get:
(1 & Tr(Eig)) & (1+ (1+El) Tr(Eija).
Similarly, we get that:
(1- Tr( < Tr(SS)) & (1+ Tr Tr(S)t))
Consequently, get that:
(1 -1- 4 = (1-467) Tr(Eij))
Tr(Eiga)
& Syy < (1 (1+ 4s
(1 + 4
Tr(Siju)
Tr(Sigh)
Hence, obtain:
|18jk - Migull < BickPlisk - Higall + 186ja - 8.gk |1
< Biyke - Mijall + 3lyn ll Payall ll + 3 (P
Miis Mija || + Siy 4e 4 Beylllau
+ Sijkel (1 + 4 4 II).
(10)
For the final term, we get from the guarantees of Theorem B.1 that:
1
1200 log(8/ (8/y)
Tr(Eih)) 2
Tr
Sikk
and consequently, we get from Lemmas C.2 and C.5:
Siga [[ak (l + +) = |1A + 3igh 160 1og(8/7)
40 (8/()/))
200 log( (8/7)
7
Plugging this into Eq. (10), we get:
|8aghTTik - Misall 1000 1000log(8/7) et.
To conclude the proof of the lemma, let:
iM == arg max(m4 14)) and im == arg min( m.)
Note now that:
Σ F.
0 -
Σ m (T M > O and (T,, (5 <
Furthermore, there exists ls such that iM, im A E.. Therefore, we have by the triangle inequality:
Pipse Wine Am wlll
< 2
4e 2 T im (Tireiim pissstmnk)
= (T (G - (Tr... (.... > 1 --111 -111
where the last inequality follows from the fact that each of the terms in the sum are positive and one of them is equal to ||7z fr" loo
Proof of Theorem 5.2. The theorem follows from Lemmas C.3 and C.4 by setting:
728
8 n
c 1og(8/n) log)n) and 8'
and applying Theorem B.I with parameters E and 8' for the elements i. k E E' from Lemma C.I. A union bound yields the corresponding guarantees on failure probability failure probability. 1
29

---

Published as a conference paper at ICLR 2026
D PROOF OF LOWER BOUND THEOREM 5.3
Here, we provide the proof of Theorem 5.3 restated below for convenience which shows that the guarantees of Theorem 5.2 are almost tight.
Theorem 5.3. Let n E N. 5,E E (0,2* For any estimator T parameterized by
{(Gi,) k); t4 such that 5= E E-2
2 1og(116) for some it # 3 E [n], there ex-
ist two choice models, parameterized by (0, m²) and (0, )²) with:
Tr(E') = Tr((2)) n and || - -2 E,
satisfying:
( (IT(()) =0 4 2 6.
max Px Px-(T(Cholo(0.33) (
Proof. Let T be an estimator with 51 & = log(1 (1/5)/4 for some i" j5" We define:
11
11
Σ
1
1
n
n
n
Σ
n1
(1 + ez + e T.)
1 11
n 1)
From the following calculations:
11
1 1 ((0-11)) )))
11
11
Tr(E')= Tr
n- Tr 1
((-- 11
(1
11
Tr(2.)) (n - 1) - -((e/n)
Tr
(1 + EeP. ej. + =.e
n
n
(I Ee + +ecgre7t) (1
11
Tr
(n - 1) 2(E/n) n
-- 11
n - I+EIr
(enee + te).
(n - 1) 2((en))
11 T (eree. )
n
n- - =
(n- 1) -2(e/n)
n
n 1 2 ) =n. n,
(n- 1) - 22(=/n)
we see that _ and 2² are normalized. Furthermore, we have:
E2 Σ² lmx
> 1-.2 -
-5-- lez = e.. S...e ege
n
6
1
11
11
eja
n n-
n
e. E.-e Eee ej-
n
T
I
11
Cj- = =e.E e.eeee
+ n-1
1
n
11
11 T
1
I
(I (e + e.)-e.)))
1
ej-
+
(n 1) - 2(5/m)
n
n2
n 1
11
1- 11
1
+ e/p
( + sepeet)
C5-
+
(n 1)- - 2(e/n)
n
n
n
n1. 1
(n 1) - 2(5/n))
ne
c 1- 11T
n
(e + e
1
11T
n
Cj-
(n
1)((n - 1) 22/n)
2
ne
1
+
T
T
11
Cz-
2
28/n
(n 1 1) - 2((//n)
n
(n - 1)((n - -5/m1/n
E(n? - '2n + 2)
2
E(n(n - 1)(n - 2) + 2(n 1) 2)
n((n 1) - 2(s/n))
n(n 1)((n
1) 25/n)
n(n 1)((1)((nn 1) 2s/n)
30

---

Published as a conference paper at ICLR 2026
(n 1) -2 n(n 1) - 1) 10-22 22/n)
E(n 2)
n 1 2z/n)
We will now compute the Kl-diiergeece between (T, Choico(O, and (T, Choice E²) We have by the definition of T
Nikk
Nus
KT((T, Choice(O, E " [T, (hoice((,,3)) = KT.
x
yisk
kik t=1
1=1
where
X Choice((O, )) and Y Choice((O, 21
and from the tensorization the KL-divergence, we have:
Nisk
Nayk yisk
KL((T, (O, Choice E2)))
Σ KL
II 1=1
X
Y
kfk
1=1
Σ
Neju KL (Xiss sprissit...
kjk
We now observe from the definitions of 1 and > for all j,
Xiiik Choice I) Yijk Choice 0, E
[ {1 [I+E(ENeJJ tejee.)) otherwise
if (i & (i.j,))
where yi
Since Eisk I for all i,j, such that (i",j*) & (1.j,k) k3, we get: KL((T, Choice(O, (T, Choice Σ²)))
Σ G... (C JC
Noj KL (xisd)ppiss...
Now, we have by the data-processing inequality and utilizing the closed form solution for the KL- divergence between two multivariate Gaussians (Pardo, 2006, Exercise in Section 1.6) for W (O, I) and Z ~ NO0 EiJ.A):
1/ Tr(1 D.iik - 1) + log (de((S(Jk)) ))
det(())
KL (xis.eeprist)) < KL (W
2
(1-22) < E²
0 + log
for & & 1/2. By substituting this back, we get:
KL((T, Choice(O, |2,, Choice )))))
Σ
Noja KL (xtrs)pprra))
(0 (C
Σ
NiJAE Ne
We now get consequence of the Bretagnolle- inequality (Lemma E.2):
2 exp ( (NNr < 1 1 V8 1-26.
1
TV Choice(0. Y²)), (T, Choice(0, E²)) <
We now have by the minimax characterization of the Bayes risk:
max IP (x-(r,Choice(0.2)) [IT(X) (E
( - 3ox 1 ワ -1 (1-20)
by application of Le Cam's method (WWainwright, 2019, Section 15.2)). concluding the proof. 1
31

---

Published as a conference paper at ICLR 2026
E MISCELLANEOUS TECHNICAL RESULTS
Here, we include technical results used in the proofs of our theorems. We start with Hoeffding's inequality.
Theorem E.1. Boucheron al. (2013) Let X1,..., Xn be independent random variables such that X; takes values in [01,br, bi] almost surely for all & n. Let
a
==
Σ Xx E(X.)). 1=1
Then for every 2
21
P(S > f)
<
exp
Ei=( (b, a,)²
We will make use of the following inequality which will be crucial in obtaining the high-probability lower bounds in the respective statements:
Lemma E.2 ( Bretagnolle and Huber (1979); Tsybakov (2009); Canonne (2023)), We have for any two distributions, P and Q:
TV(P,Q) < eexp(KKL(P]OO)
E. PROOF LEMMA 4.3
Lemma 4.3. Let 01, U2 E RR2 be two independent unit vectors and & R2 be such that dj =
(VI,E), d2 == (U2, E) > 0. Then,
012
(U1, U2)
is identifiable from d2, d2, and
112 = (P), (2, & for X ~ N((s
Proof. Without loss of generality, due to the invariance of an isotropic Gaussian to rotations and reflections, we may assume d1 / d2, U1 = 62. and (V2)1 > O. Since v2 is a unit vector, it may be parameterized U2 v(0)) for 0* E [0, π.] with v0) defined as follows:
sin( cos for 0 E [0,
(0) -
Now, (()) satisfying the first two constraints imposed by d1, d2 for the vectors in and u(0) given by the following expression:
[(()] {(O) = di
where {(0) = di cos(O) + d2 sin(()
Claim E.3. We have for 8 e (0, T):
{0(0)= O.
Proof. Observe from the chain rule that:
(0)) (d, cos(O) + da)
di -di d2 cos cos(O) (0)
<
sin? 0
sin²(0)
for 0 E (T) concluding the proof of the claim.
Continuing with the proof, define:
70) P((X, vi), (()) < <0) for X ~ ~N(((()),
Our next claim shows that 7()) is also monotonic in 0.
32

---

Published as a conference paper at ICLR 2026
Claim E.4. We have for 8 s))
7((0) > 0.
Proof. First, observe the following:
( T), (v(0), <0) = ((rco(()) rin(())))))))) :r > 0, (
(o:: (11, ()(0) < 0} {(z, y) y & 0. < ycot(f))
As consequence, we get by switching to polar coordinates:
(r - {(O)) (rsin(a) - di)²
7(0)
exp
dardr.
0
2T
2
Hence, we get by the Leibniz integral rule:
00 d
T+
(r cos((a) [(0))² + (rsin(a)-ddp - di)²
(0)
exp
da rdr
do
2T
2
00
(r + E(0))² + (rsin(0) + d1)²
exp
grdr +
2x
0
xx+
(roos(a) - [[))) + (rsin(a) - -di)² a/8) dardr
cxp
00
2T
2
00
cos(s))) + E(0)) + (in + dz)
exp
rdr +
0
2m
2
(rcos(a) + -
d1)²
(r (rcos(a) - (rco(())-E(0)) ((00))"(0)dorrl)
exp
2m
2
(reos(0) + E()))² + (0) + d1)²
exp
(rdr +
JU
2x
2
(0)
00
1
(rcos(a) E()))² + (rsin(a) - -d,22
} (r cos(a) - ((r))r
exp
2n
For the second term, have:
+0
cro((a) - [()))² (rsin(a) dd)²
(r - E(0))
exp
2m
2
y (0)
(x [(0))² (v d1
(1r -((()))dr
exp
2T
2
()) 12 (
(y d2)
exp
-t
dtdy
2x
2
1
(y) - -1)
exp
(-exp(-t))
dy
2T
2
11
(y - d1) (y-d
cot(O) - =(
exp
exp
dy-
2π
2
Noting that the above integral is negative, the previous two displays and Claim E.3 now yield: ((0)) > for 0 (0)
concluding the proof of the claim.
From, Claim E.4, we get that there exists a unique solution 8* such that 7(8") = =? Observing that (V1, 02) c0*) establishes the lemma.
33

---

Published as a conference paper at ICLR 2026
E.2 PROOF OF THEOREM 3.2
Here, we present the proof of Theorem 3.2, stated below for convenience.
Theorem 3.2. For any n. 3 3 and μr, E satisfying Assumption 3.1, there exists an infinite set S:
Vi,j [m], nl, E' E S::
IP
[X; > x,) X~N(x'
P (x; x))
(~)(HE)
Proof. We will establish the result for mildly different normalization of the parameters, (H, E). Formally, will assume that:
p1 O, Σn Tr(E) = -
(DIFF-FORM)
We will establish the equivalence between DIFF-FORM and Assumption 3.1 subsequently. DIFF- FORM motivated by the observation that for any Nu, E), X' generated by the following transformation:
Vie [n] x (
for any / >> 0 induces the same set of rankings. This results in deterministically fixing the utility of the first item to 0 resulting in the first two constraints and the third chosen for normalization. As before, we assume that the rank of 2 is
1.
Now, consider any (n, 2 satisfying DIFF-FORM. Let X (M, 2.). First, observe that: (DIFF-PROB)
X; X3 Nw
My Li,s Egg -2
145
Note that since has rank n (and satisfies Dej = 0), Oij > 0. We will now establish our results in two different cases:
Case 1: Fij = n.. In this case, observe that since of rank defining:
E = c.e] + tze
we have for some v > 0:
Yg E [0, v) E + SE satisfies DIFF-FORM and has rank n
Note, furthermore that for any X' NNw,
Ak, [n], k + 1 {k. : X1) P
X
P F(X; > X²} - = P X
Hence,
S' (1, SE) E [0, m|} consists of infinite of solutions with the same pairwise rankings.
Case 2: Di 1: p4 0. For this case, consider the matrix Σ:
Ei
+
k = i
Σg
k = and <l < i
ΣN
Σxs
if = i and
Egi
otherwise
Note that for small enough v. Σ remains positive-semiidffnite with rank 1. Furthermore,
X NH, Σ) and NV,, Σ) induce the same distribution over pairwise rankings of the n alter- natives. Finally, observe that (H, Σ) satisfy the conditions of DIFF-FORM except for Tr(E) = ntv..
To restore this, we simply rescale the (H, Σ) to obtain:
t n n
1 1
Σ
Σ
n
V
Now, (p', E') induce the same distribution over pairwise preferences (n, E). Furthermore, (p', E') distinct from E) # μ' and Σ * E'. Since (n', E') may be constructed for all small enough v, there exist infinitely many solutions satisfying DIFF-FORM with the same distribution over pairwise rankings.
34

---

Published as a conference paper at ICLR 2026
Case 3: Vi,j [n] Ms # Mj. In this setting, start by modifying the parameter μ as follows:
+ 0, || < 1, Un 0: = μ + v'u
for some / to be chosen subsequently. We will now construct an alternative solution from jú by setting An and the entries of Σ, the corresponding covariance matrix accordingly. Note from DIFF- PROB, to ensure that the pairwise ranking probabilities do not change, we must:
Vi E 12,n-17 E
sii p4i
Σx
Next, we will set:
Σnn 11- Ea and pin
Ene
Pa-
Enn
1=2
Note that the above settings result in the correct pairwise probabilities as long as is chosen small enough. From DIFF-PROB, this setting preserves the pairwise ranking probabilities between the first alternative and all other alternatives in the list. To ensure the correct pairwise ranking probabilities between other pairs, j. with * and i * 1, we will set the values of Σig accordingly. To do this, observe from DIFF-PROB, it suffices to set Es such that:
p4 My
Ea Σn 25gg
En Σn 2Enng
We now prove that (jt, Σ) valid solution satisfying DIFF-FORM. The first three constraints are satisfied by construction. Furthermore, (īi, Σ) achieve the same pairwise observation probabilities by DIFF-PROB. The only remaining constraint is to prove that is positive semidefinite and has rank n 1. do this, note that oij 0 for all # j. Des > for all i E [n], Pi * Uý. and consequently, we have that:
where E is symmetric, satisfies En: 0 for all E [m]]. and | < 1. Furthermore, v may be made arbitrarily small by an appropriate choice of v/. Since the sub matrix corresponding to the last n rows and columns of Σ is full rank and positive definite, the corresponding matrix of Σ also full rank and positive definite by making y correspondingly small. Hence, Σ itself of rank n and positive semidefinite. Since such solution may be constructed for arbitrary choices of this concludes the proof in this case as well.
The theorem under Assumption 3.1 is consequence of the following claim.
Claim E.5. Let
V {1, E): (p, satisfy Assumption 3.1)
4 = (11, Σ) (n, Σ) satisfy DIFF-FORM).
Then, there exists invertible mapping f U4 V, such that for any (p, E) U. f(, induces the same distribution over the rankings of the n alternatives.
Proof. Letting:
11T n
My 1 and My - IeT,
will show that:
f(p,E) Mun My t
where t. = T
(MAP)
Vi
the required transformation. First, observe:
11
11
My I
le
le)
n
11T
My My =
le
+ 1e
11
7
35

---

Published as a conference paper at ICLR 2026
Consequently, have:
VH, Eu My My E
Vp, E V: My EMMYEMEM =.
Hence, t >> 0 in MAP and the mapping f is well defined. Next, observe that for any X ~ (u, J E), My X has distribution N (M,u, My Myy) and induces the same distribution over rankings. There- fore, [u, Σ) induces the same distribution over rankings as (1, E), Finally, to show that s' is invert- U:
ible, define g
MvR Mv
Tr ΣM²)
gu. 2)
where
(INV-MAP)
Vt
n
Note that g is well defined as t due the definition of My My and its operation (J,, Σ) V. Similarly, g(,, 2)) induces the same distribution over rankings as (v, 23). Finally, we have:
g f(u, )) My My MyMMMMMMMM
11 Tr(MeMMM 12
My (T)
Vt1t2
tat2
nt1
MVM
My My My Tr(M, My EM, M2)/n
TMMMy (.MMMMM
Σ VT(E)/(m)) (n)
My
where the third and fourth incquality follow from the fact that (H, E) E U.
Claim E.5 establishes that there exists one-to-one mapping between pairs (μ, Σ) satisfying As- sumption 3.1 and DIFF-FORM which induce the same distribution over rankings. Hence, identifi- ability under one parameterization implies identifiability under the other. Therefore, the existence of infinitely many solutions satisfying DIFF-FORM with the same pairwise ranking probabilities as any (p, Σ) E U1 satisfying implies the existencec of infinitely many solutions satisfying Assump- tion 3.1 with the same pairwise ranking probabilities as any particlar (H, Σ) E V concluding the proof of the theorem.
F IMPLEMENTATION DETAILS
Figure 6 shows multiple Gaussian distributions with the same pairwise probabilities.
We split the users into a train and validation sets (90% train, 10%validatoon) for testing. For the Netflix and MovieLens datasets, only take movies with more than ratings, e.g., n 10a for nf-10k. For datasets where we convert ratings to rankings, we assume that alternatives with first sample
same rankings can be shuffled in the ranking. To sample the six alternatives, with probability proportional to the number of choices made, then we sample the choices uniformly, lastly, we sort the choices according the ratings and query format. For the LLM experiments, we use "the movie database" (TMBD) to generate the input, the correctness of the TMBD ID, including mapping correctly to TV show or movie, was manually verified for both datasets. We omit alternatives that do not have clear entries in TMBD. Examples of such movies are double features like "The Fly (1986) The Fly (1989) double feature" were omitted.. We use linear network for all experiments. For the probit experiments, we output the Cholesky decomposition of the covariance matrix. We use the Adam optimizer (Kingma, 2014) with a learning rate of 3e-4 for RUM and 0.01 otherwise. For the matrix factorization model we learn 128 embedding for users and alternatives with a per user and per alternative hias. We do 9000 gradient steps with batch size of 1024 on RUMs and 1000 gradient steps with a batch size of 10240 matrix factorization models. We train the matrix factorization models with the Huber loss.
For the probit models learned from 3-way comparisons, we project the problem in 2D using the P matrix introduced the main body of the text to both speed up the calculation, which is done via numerical integration over coarse grid, and remove the symmetries present in the loss land- scape. To calculate conditioned outcome probability, we use rejection sampling to measure the high-dimensional integrals instead of methods like Gessner et al. (2020).
36

---

Published as a conference paper at ICLR 2026
1,80
0.21
0.
0.06
0..1
0.26
0.12 -0.2
0 0.63
0.14
0.12
-..6
0.21
0.24
-0.09
0.05
-0.21
8,38
0.01
0.29
0.17
-0.15
-0.99
0:13
1 0.14
8.78
0.06
-0.1
0.03
-0.06
-0.05
0.355
0.112
0.01
0.68
0..01
-0.
34
-0.02
00.02
-0.15
00.12
-0.06
0.63
0.08
-0.03
-0.29
-0.01
-0..1
3.06
-0.29
0.00
3.82
0.10
-024
00.02
00.2
-0.36
00.33
0.08
1.03
-0.11
00.35
0.14
-0.2
10.12
0.17
-0.34
3.10
0,78
-0.04
-0.12
-0.05
-0.21
0.03
-0.03
-0.11
0,80
-0.2.5
-0.17
-0.05
-0.26
0.15
15
-..0
0.24
-0
0.04
-0.08
0.08
0.24
0.066
00.99
-0.35
-0.25
-0.26
0.08
0.12
0.09
0.02
0.02 0.12
0.08
0.21
0.09
0.05
0.01
0.14
0.17
0.26
0.18
00.22
0.13
-0.15
-0.22
-0.05
0.08
-0.21
0.35
0.05
-0.35
-0.21
-0.28
-0.05
-0.18
0.84
0.39
0.03
0.10
0.13
0.12
0.09
0.11
0.09
-0.09
0.38
-0
-0.10
C.
14 13 -0.
-.100..11...
12
0010
0.11
0.10
6 14
0.13
1.
0212
0100
0.13
00.4
1.80
0.16
00.4
0..6
0114
-0.12
-0. 13
10.13
-0.66
-0.13
0.
-0.13
0.09
0 0.10
0.14
0.13
0.11
0 10
-0.11
-0 12 -0.12
-0
-0.12
3,88
-0.12
00.09 -0, -0. 10.10 14
0.12
0.33
8.32
0.100
0.
-0.14
-0.09
-0.10
-0.09
0.32
00.10
-0.
-0.13
-0.08
-0.11 -0.10
-0.10
0.1
0.10
0.35
0.14
10
11 0
0..10
0.0%
M
0.11
0.12
0.10
0.12
0.10
0..09
0.008
0.77
0.14
0.13
0.09
00.3 0.10
-0.14
0.13
13
1,0%
10.13
1.
00.15
-0.15
-0.13
-0.14
-0.
14
1.0%
-0.15
13
16
-015
-0.1111
14
-0
-0.15
0,20
0..1
00.15
12
0.12
-0.13
-0.13
00.15
0
0.13
-.166
-0111
-0.09 -0
0.10
1.
0.13
-0 11
-0.12
09.9
0.008
0.10
-0.09
-0.13
0.13
0.30
-0.12 -1.1
-0.10 0..00-0.113
0.113 02
0.15
15.15
-0.22
8/88
-0.11
00.011
-0.11
-0.13
-..6
0
12
B.91
-0.11
0.09 0.09 0.10 0.15 0. 0.09
...11
00.355
0.100 0 10 0.10 0.15 0. 0.
0.11
Figure 4: Larger version of the first row of Figure 2. Top to bottom rows: pairwise, ground truth, fsst-of-three.
37

---

Published as a conference paper at ICLR 2026
1,80
0.07
0.20
0.47
0.01
00.10
0.16
-0.3
0 1,88
0.30
0.
-0.39
0.00
-0.04
0.16
0.33
-0.07
8.44
0.27
0.24
0.38
0..55
0.01
-0.10
1 0.30
8:33
00.30
-0.22
0.44
-0.13
0.08
0.11
0.20
0.27
0.32
3.28
-0.28
-0.12
0.07
-9.19
00.11
-0.30
0.36
0.25
-0.38
18
0.06
-.110
-0.47
0.24
0.28
3.E.
-0.27
0.34
-0.18
0.23
00.39
0.22
0.25
0.38
-0.29
0.03
-0.15
0.21
0.01
8.38
-0.28
00.27
8,38
-0.30
0.08
-0.27
0.00
0.44
-0.38
-0.29
0,700
-0.
0.08
-0.31
10.100
15
0.11
8.04
-0.3
0.47
-0.17
0.33
0.004
-..13
0..88
0.03
-0.23
0L58
-0.29
0.34
3.16
0.01
0.07
0.18
0.05
0.32
0.26
0.16
0.08
0/06
0.15
0.08
0.29
0.31
0.25
-0.33
0.10
0.23
-0.27
0.33
-0.26
0.38
-0.33
-0.13
0.
0.21
-0.31
0.34
-0.25
0.38
1.00
0.13
0.25
0.60
0.07
.0.17
0:18
0.36
0.1.
0.38
-0.33
-0.28
0.41
-0.22
0.04
-0113
0.25
0
0.54
0.13
0.29
0.12
0 32
0.600
0.34
3.87
0.39
0.11
0..22
0.27
0.07
-0.13
-0.39
-0.50
+0.03
-0.25
0..7
0.
0.29
11
0..50
00.30
0.18
0.04
0.12
-0.32
0..3
-0.30
0.
-0.38
-0
-0.32
0.27
-0.
25
0.49
-0.88
0.68
2
3
1,88
0.14
-0.26
-0.60
0.08
-0.17
0.17
-0.35
1,00
0.12
-0.24
-0.61
0.07
-0.17
0.17
-0.35
0.28
-3.13
0.36
1..26
0.33
0.005
3.35
.0.13
-0.88
0.11
-0.1
0.24
00.32
0,03
0.33
00.11
0..30
0.11
0.32
-0.60
0.28
0.3G
3.38
+0.38
0.11
-0.35
0:28
-0.61
-0.26
0.33
-0.38
0.09
-0.32
0.28
0.08
0/4
-3.13
0..38
-0.51
-0.03
-0.25
0.07
0.40
-0.11
-0.38
-0.50
-0 -0.03
-0.26
-0.17
0.22
0.28
0.11
-0.51
0.000
-0.28
0:48
00.1
00.21
0..30
0.09
-..50
0,80
-0. 28
0.49
0.17
0.04
0.11
-0.35
00.03
-0.28
8.51
-0.37
6
0.17
0.02
0.11
-0.32
0.03
-0.28
0.31
-0.38
0.35
0.
13
0.31
3.26
.0.25
0.48
-0.37
00.315
0.35
0.13
00.3
0.28
0.26
0 0.4
-0.38
Figure 5: Larger version of the second row of Figure 2. Top to bottom rows: pairwise, ground truth, sst-of-three..
38

---

Published as a conference paper at ICLR 2026
0.2
0.4
0.6
0.6
0.8
Figure 6: Two probit models where P.Y X) rightmost).
0.5 (two leftmost) and P(Y > X) 0.75 (two
0.455
0.34
7.15
01/91
11004
1912
4.02
0:34
01
-8.04
-0.11
-2.29
+1.03
5.05
-0.0
9:31
0:49
8:54
0.01
3.14
0.00
4.03
62
0.0
0.24
5:38
-0.11
2:41
0.03
-0.02
12.04
-.20
0.05
0-2-
-2.01
0.05
4..14
11:2
11:33
9.39
40.24
7:15
01:11
4..82
1::13
0..22
0.02
0.05
0.02
5.24
0.15
2:20
0.05
0.03
0.13
0.02
Nape
9.14
0.:05
0:25
1.19
0.34
AET
6.4
4.11
-0.5
..14
12.2%
-3.00
15.2
9.76
0:22
3.99
0.17
1.24
04
3.24
10.17
2.24
1.90
-0.2%
+3.24
0.11
0.22
0:34
0.2%
2.10
1.21
9.12
0:23
0:22
8:03
0.11
0.23
2.02
9.47
3.10
0:25
0.11
6.1
3:21
3:02
1:3b
1::14
2.04
Sieb
1:20
0.66
Figure 7: probit model learned from best-of-three observation from sushi-a
39

---

Published as a conference paper at ICLR 2026
Teleyraeeii Tayy (1961)
Taa Tranilatice (2853)
0.15
Coos (7000
SWAT (700))
0.05
Naki Maaaasa- (200)
The Rosi Towsharo (2001)
-.42
Lon Trantakis (200)
Napdon Drenekk (204)
045
Congreaity
Repert
Spule
Hather (500))
Dedgihull Tree Uiddwinng (7030)
Shush Menens (2080)
4.0
Dodile Jopaaly (1955)
Zarra Suslee Spotico Miad (204)
0.43
Kil Siz: Vil 2 2.00
045
Chapee
Ielepaabeii Tay (1955)
(7001)
(Norl)
Guollahee (197)
0.6
Atchetsa: The Le Jox Dugundy 2010
Speed (173))
0.43
(100)
Cold Maszaa (2005)
045
Ataricu (1990)
Vald Mariaann 2h075
Star (194))
0.0
Pybr (199))
Stadd Madana: 22K2
0.23
Ooes 80 Secoede (2000)
The Bocoa (260)
045
Madatan Spebos Miel (N00)
-3.3
Raxavay Book
Sapeass The Fedlow sfrw (001
040
SirFoon (1967)
Chedboor (1481)
Nabi (197)1
Snoci Itees Alatura (200))
0.33
Tvo Wedoo Netar (XCC)
Wisi Mizzon Mar (2000)
04:
Deat Surber (201)
Roys (780))
(2201)
-335
De Patic (200L)
Teab Jokks (2201)
043
Drowe
Beeg 34n Madanidh (199)
Juearoo Brikk (1969)
0.35
Spead:1154)
Top (1
043
Ackpedic (2012) 2001
betsendou: Day
-.37
Adrazias (1984)
Flcxo (1966
043
Aik (1961)
Dobblc Joquady (196))
Kil B1L Vol (2905)
0.37
Adazzici (2942)
Si0m er (230k)
04:
Max Blac
Junn May
-.37
Bon to Day Dap (200))
The Woldis (2301)
043
(7001)
(1978)
(194)
Asazicas Beaty (199)
Peadi Haater (2805)
4.35
Day Dacia (1187)
Skeplcnn Scakk (1953)
043
Bxcrdl Stuakacc 2e Speticn Misd (204))
Scouab
-.35
Nemete/ 2160)
The Reysal (1000) The Caaal Stapect (1595)
(200)
042
(1667)
Kil Bal Vil
Mia Coegeaslly (300))
The Roya Towataro (2201)
-..3
Tie Slzze of Ie Lasb (1951)
042
Berad St of Speticn Masd (204))
Gooutal's
(199))
-3.5
Dreac
Proty Wonms (1634)
042
(363))
Choipe 27 de 2200
The Loaal Supecia (2935)
-.35
Aucamsa: The Legend of Bon Buruandy (204))
Napdise Dymaniic (200))
042
Fighs Val ((h05)
Tee Works Netie (002)
-033
hras (1805)
(1993)
Baanney (199)
043
(2003)
SUll Bill: Vcl (23M))
Peadi Hatber (2000)
-.33
Ascamsa: The Lagend of Boe Buruaddy (204))
Dedechad: Thec Unketos Stary (DKM)
047
Fight (1999)
Jadao 2000) (300))
-033
Faa Clas (1997)
Kil BL:: No. 1,2003)
043
Sparies (M01)
Masi Minhaminn (100))
(000)
0.31
Cone Fleae Abllier wi (7007)
Baradl Se of De Spetion Miad (2004)
2002
-3.4
Bacal Val
dee Spoticu Maddl (2044)
043
Wi
The Fedlow skip afe (700))
18 (7065)
(994))
0.31
Lowlor the Rlng The follewday the king (1001
Lead of the Ring The Reters the King (hi)))
Metaczaa
-334
Bacal Suadiae de Spoticu Stuai (204))
Boya Teaishaun
044
(7000)
(200.)
The Fellow dllp
(7001)
Blxck (Tre5)
(000
0.11
Rgx Caa (1990)
The Siberi The Lends: (1941)
0
Aschessa:: 11037
Roe, Buppaad (004)
Co 2i (2000)
-334
Doez 90 (2000)
The thut Paakoa (2001)
044
(199))
(1000)
Puly Furkow (196))
Tia Works Norioe (7807)
0.11
Lowlo' Be Blgg The Relowdday tri Ring (300))
The Masic (1999)
Seag Mulankds:1999
Thenasz (300))
-333
Aranicaa Boaty (199)
Lertie de Rags Piclew tu Xlng (2001)
045
(hodhheens (1941)
kibe (3800)
0.11
Napdiom Desaret (101))
Ciles sy (1306)
(115))A
Royal Tosshara (2001)
-333
Arazicza Boaty
Los Trandakk (1966
045
Sporins Mini (104)
Indirs foom w out Creaad dn (1960)
Midi Madattn (707)
0.11
legeed Bun Surgaudy (1005
Studdy A (aechcCnn)
6.5
Brigiig Dows Hoav (200)
Mecretta
-333
Stake Smakk (190)
You're
045
Maric (1999)
(199))
Voen E6 (001
0.11
(1999)
Cran mv-0 sach (7030)
0.55
Lad De Rtap:
Towar (230))
Roc
-333
Xencre/2000
045
(1301)
The Paree (1030)
Th- Bryul Tomeshree (7001)
0.11
(N87)
The Regul Trarchures (700))
0.55
Loc in Tranliada (2005)
Fazzas (200))
-333
Bragit Dova Hone (2000
Chotpet by de Dooit (20C))
045
Mivi (1 (1200)
(190)
0.33
lade Q (NVH)
Men Fienn (1001)
0.55
Maa Madatas 2012
-332
Aranicaa Beaty (199:
Saadin Dysnntic 2004)
045
(2001)
Areniiue Reatyy (1990)
Treanio Back (1969)
0.33
Sawt Megrodin (1965)
Sapewee (1998) Araciccs Buary (1095)
0.0
Brigging Dows Hoac (300)
Bii Vol (2003)
-332
Adrezin (2012)
0.4
Diee 50 Severd. (000))
Villiae Dsfla Bany (200))
0.33
Loc Tire al (N05))
0.0
Claetharc (1984)
T. (2200)
-332
Chea (192))
Orous (1976)
0.4
KI1 Kill Vol (N00)
Wh1 Woree West 2200
0.33
Broslear (1955)
1n Inkperirne Day (190)
0.03
Napilaas Dysuziic 1203))
12PM0)
-332
Raswvy Brakk (199))
(po5k
048
Last in Teendaaiio (7597)
Midl in Marluttnn (M075
0.33
Swee Nevee Alfara (2007)
Two Weeks Notioo (1F0)
0.19
Nazinall Thuaar (204)
-332
(177))))
Sacoadi (2000)
0.4
Bringnng Dras the Noae (700))
Tusken Th Loo Arl (1981)
0.33
MincCingee 2200:
The Wenking Mareer (1.01)
0.55
Bay (30k)
Swatt Alaturus (200))
-3322
Aramica Buatt// 1999
Pulo Tlsse
040
Last in Thanlalion (2007)
Tortl Siver 11900
0333
(newn's Flvea (2001)
Ownen's TTae (106)
0.55
Chaethrrazs (1944)
Mtad 2X02
-131
Deabi kopaat
0.5
Manavs Ioc (3000)
Moovingg Horae (001)
-3:1
Beng Miee Miloniaa 1959)
Riemel Stackie ofe Spedios Mind (2004)
0.55
S.W.T (200))
(3501)
0331
ason (N05)
Rrgul Tranohares.cCe))
0.5
Mra dall- 2001:
Rock (1955)
4131
Bong Vie Mi (a
Menemen (7060)
0.5
Alrag Caroa Spale: (3001)
Vicneeto 75000
031
Legaly Boke (001)
Maginkas (199)
0.5
Peal Hurber (3301)
The Godfiderr (1977)
4.31
Mavlin Malaane (367)
What Moreen Wart (2800)
0.5
Taoea Suuliee Speebos Mixl (NH0)
31
Maalie Makkane (D67)
Sunnd Fiora aer (200))
055
(200)
Aravicu Revttyy (1/M0)
Smasfii (2801)
4131
Perd Stadioee Spetiss (200)
Minemen (1060)
051
(Roothatens (191)
Vocco Hove 2000
0331
Adverio (X00)
Bevn (oha
035
Big Dakyy (1969)
of Los Ark (1R0))
43:1
Miceriis (395)
Low Tounslatio Ch00)
0.5
Dan (197))
Mysio Riwe (100)
4131
Wil (200))
Kit 911 2.0004
055
(506)
The Lsaal Surper (1995)
.0:1
Lowio' Bhe Rig. The Reaes of the King (000))
Lovi the Rings The Two Towen (000)
0.4
Eanggree (199)
Royal
en (1001)
43:1
Fidling Neww (eddeooen 2000)
Skonk: (Pall Lomenn 2h00)
045
(1985)
Last in Trendattin (2005)
lamonny (1955)
.0:11
Lowto' the Wings The Retowalayy ihe King (3001)
Lo the Hings The Two Trwers (200))
0.65
Kuy (1994)
The Leage of Berandaay my Gentieee (2003)
31
ledias frae andite Trapler boon (1984)
Riados Last (190))
047
Surpeci
(2000)
Table 4: Left to right, movies with the lowest and highest correlations in a probit learned from the Netflix dataset.
40

---

Published as a conference paper at ICLR 2026
Teleyraeeii Tayy (1961)
Taa Tranilatice (2853)
0.15
Coos (7000
SWAT (700))
0.05
Naki Maaaasa- (200)
The Rosi Towsharo (2001)
-.42
Lon Trantakis (200)
Napdon Drenekk (204)
045
Congreaity
Repert
Spule
Hather (500))
Dedgihull Tree Uiddwinng (7030)
Shush Menens (2080)
4.0
Dodile Jopaaly (1955)
Zarra Suslee Spotico Miad (204)
0.43
Kil Siz: Vil 2 2.00
045
Chapee
Ielepaabeii Tay (1955)
(7001)
(Norl)
Guollahee (197)
0.6
Atchetsa: The Le Jox Dugundy 2010
Speed (173))
0.43
(100)
Cold Maszaa (2005)
045
Ataricu (1990)
Vald Mariaann 2h075
Star (194))
0.0
Pybr (199))
Stadd Madana: 22K2
0.23
Ooes 80 Secoede (2000)
The Bocoa (260)
045
Madatan Spebos Miel (N00)
-3.3
Raxavay Book
Sapeass The Fedlow sfrw (001
040
SirFoon (1967)
Chedboor (1481)
Nabi (197)1
Snoci Itees Alatura (200))
0.33
Tvo Wedoo Netar (XCC)
Wisi Mizzon Mar (2000)
04:
Deat Surber (201)
Roys (780))
(2201)
-335
De Patic (200L)
Teab Jokks (2201)
043
Drowe
Beeg 34n Madanidh (199)
Juearoo Brikk (1969)
0.35
Spead:1154)
Top (1
043
Ackpedic (2012) 2001
betsendou Day
-.37
Adrazias (1984)
Flcxo (1966
043
Aik (1961)
Dobblc Joquady (196))
Kil B1L Vol (2905)
0.37
Adazzici (2942)
Si0m er (230k)
04:
Max Blac (2202)
Junn May
-.37
Bon to Day Dap (200))
The Woldis (2301)
043
(7001)
(1978)
(194)
Asazicas Beaty (199)
Peadi Haater (2805)
4.35
Day Dacia (1187)
Skeplcnn Scakk (1953)
043
Bxcrdl Stuakacc 2e Speticn Misd (204))
Scouab
-.35
Nemete/ 2160)
The Reysal (1000) The Caaal Stapect (1595)
(200)
042
(1667)
Kil Bal Vil
Mia Coegeaslly (300))
The Roya Towataro (2201)
-..3
Tie Slzze of Ie Lasb (1951)
042
Berad St of Speticn Masd (204))
Gooutal's
(199))
-3.5
Dreac
Proty Wonms (1634)
042
(363))
Choipe 27 de 2200
The Loaal Supecia (2935)
-.35
Aucamsa: The Legend of Bon Buruandy (204))
Napdise Dymaniic (200))
042
Fighs Val ((h05)
Tee Works Netie (002)
-033
hras (1805)
(1993)
Baanney (199)
043
(2003)
SUll Bill: Vcl (23M))
Peadi Hatber (2000)
-.33
Ascamsa: The Lagend of Boe Buruaddy (204))
Dedechad: Thec Unketos Stary (DKM)
047
Fight (1999)
Jadao 2000) (300))
-033
Faa Clas (1997)
Kil BL:: No. 1,2003)
043
Sparies (M01)
Masi Minhaminn (100))
(100)
0.31
Cone Fleae Abllier wi (7007)
Baradl Se of De Spetion Miad (2004)
2002
-3.4
Bacal Val
dee Spoticu Maddl (2044)
043
Wi
The Fedlow skip afe (700))
18 (7065)
(994))
0.31
Lowlor the Rlng The follewday the king (1001
Lead of the Ring The Reters the King (hi)))
Metaczaa
-334
Bacal Suadiae de Spoticu Stuai (204))
Boya Teaishaun
044
(7000)
(200.)
The Fellow dllp
(7001)
Blxck (Tre5)
(000
0.11
Rgx Caa (1990)
The Siberi The Lends: (1941)
0
Aschessa:: 11037
Roe, Buppaad (004)
Co 2i (2000)
-334
Doez 90 (2000)
The thut Paakoa (2001)
044
(199))
(1000)
Puly Furkow (196)
Tia Works Norioe (7807)
0.11
Lowlo' Be Blgg The Relowdday tri Ring (300))
The Masic (1999)
Seag Mulankds:1999
Thenasz (300))
-333
Aranicaa Boaty (199)
Lertie de Rags Piclew tu Xlng (2001)
045
(hodhheens (1941)
kibe (3800)
0.11
Napdiom Desaret (101))
Ciles sy (1306)
(115))A
Royal Tosshara (2001)
-333
Arazicza Boaty
Los Trandakk (1966
045
Sporins Mini (104)
Indurs foom w out Creadd dn (1960)
Midi Madattn (707)
0.11
legeed Bun Surgaudy (1005
Studdy A (aechcCnn)
6.5
Brigiig Dows Hoav (200)
Mecretta
-333
Stake Smakk (190)
You're
045
Maric (1999)
(199))
Voen E6 (001
0.11
(1999)
Cran mv-0 sach (7030)
0.55
Lad De Rtap:
Towar (230))
Roc
-333
Xencre/2000
045
(1301)
The Paree (1030)
Th- Bryul Tomeehree (7001)
0.11
(N87)
The Regul Trarchures (700))
0.55
Loc in Tranliada (2005)
Fazzas (200))
-333
Bragit Dova Hone (2000
Chotpet by de Dooit (20C))
045
Mivi (1 (1200)
(190)
0.33
lade Q (NVH)
Men Fienn (1001)
0.55
Maa Madatas 2012
-332
Aranicaa Beaty (199:
Saadin Dysnntic 2004)
045
(2001)
Areniiue Reatyy (1990)
Treanio Back (1969)
0.33
Sawt Megrodin (1965)
Sapewee (1998) Araciccs Buary (1095)
0.0
Brigging Dows Hoac (300)
Bii Vol (2003)
-332
Adrezin (2012)
0.4
Diee 50 Severd. (000))
Villiae Dsfla Bany (200))
0.33
Loc Tire al (N05))
0.0
Claetharc (1984)
T. (2200)
-332
Chea (192))
Orous (1976)
0.4
KG1 Kill Vol (N00)
Wh1 Woree West: 2200
0.33
Broslear (1955)
1n Inkperirne Day (190)
0.03
Napilaas Dysuziic 1203))
12PM0)
-332
Raswvy Brakk (199))
(po5k
048
Last in Teendaaiio (7597)
Midl in Marluttnn (N075
0.33
Swee Nevee Alfara (2007)
Two Weeks Notioo (1F0)
0.19
Nazinall Thuaar (204)
-332
Cas (177))))
Sacoadi (2000)
0.4
Bringnng Dras the Noae (700))
Tusken Th Loo Arl (1981)
0.33
MincCingee 2200:
The Wenking Mareer (1.01)
0.55
Bay (30k)
Swatt Alaturus (200))
-3322
Aramica Buatt// 1999
Pulo Tlsse
040
Last in Thanlalion (2007)
Tortl Siver 11900
0333
(newn's Flvea (2001)
Ownen's TTae (106)
0.55
Chaethrrazs (1944)
Mtad 2X02
-131
Deabi kopaat
0.5
Manavs Ioc (3000)
Moovingg Horae (001)
-3:1
Beng Miee Miloniaa 1959)
Riemel Stackie ofe Spedios Mind (2004)
0.55
S.W.T (200))
(3501)
0331
ason (N05)
Rrgul Tranohares.cCe))
0.5
Mra dall- 2001:
Rock (1955)
4131
Bong Vie Mi (a
Menemen (7060)
0.5
Alrag Caroa Spale: (3001)
Vicneeto 75000
031
Legaly Boke (001)
Magankas (199)
0.5
Peal Hurber (3301)
The Godfiderr (1977)
4.31
Mavlin Malanne (367)
What Moreen Wart (2800)
0.5
Taoea Suuliee Speebos Mixl (NH0)
31
Maalie Makkane (D67)
Sunnd Fiora aer (200))
055
(200)
Aravicu Revttyy (1/M0)
Smasfii (2801)
4131
Perd Stadioee Spetiss (200)
Minemen (1060)
051
(Roothatens (191)
Vocco Hove 2000
0331
Adverio (X00)
Bevn (oha
035
Big Dakyy (1969)
of Los Ark (1R0))
41:1
Miceriis (395)
Low Tounslatio Ch00)
0.5
Dan (197))
Mysio Riwe (100)
4131
Wil (200))
Kit 911 2.0004
055
(3065)
The Lsaal Surper (1995)
.0:1
Lowio' Bhe Rig. The Reaes of the King (000))
Lovi the Rings The Two Towen (000)
0.4
Eanggree (199)
Royal
en (1001)
43:1
Fidling Neww (eddeooen 2000)
Skonk: (Pall Lomenn 2h00)
045
(1985)
Last in Trendattin (2005)
lamwnny (1959)
.0:11
Lowto' the Wings The Retowalayy ihe King (3001)
Lo the Hings The Two Troers (200))
0.65
Kuy (1994)
The Leage of Berandaay my Gentieee (2003)
31
ledias frae andite Trapler boon (1984)
Risdos Last (190))
047
Surpeci
(2000)
Table 5: Left to right, movies with the lowest and highest correlations in a probit learned from the Movielens dataset.
41

---

Published as a conference paper at ICLR 2026
logit accuracy quantile
matrix completion accuracy quantile
probit (pairwisc) accuracy quantile
probit (best-of-three) accuracy quantile
dds.
var.
feat.
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
jokes
onehot
onehot
0.61
0.61
0.61
0.61
0.61
0.61
0.59
0.59
0.59
0.61
0.61
0.61
split-jokes
default
onchot
0.55
0.55
0.54
0.54
0.53
0.53
0.56
0.54
0.54
onchot
0.62
0.62
0.60
0.60
0.60
0.60
0.60
0.60
0.61
0.62
0.62
split-ml
ml-1k
onchot
0.63
0.63
0.63
0.59
0.59
0.59
0.61
0.61
0.61
0.62
0.62
0.63
ml
10k
onchot
0.61
0.61
0.61
0.60
0.60
0.60
0.59
0.59
0.59
0.61
0.61
0.61
split-ml
ml-10k
onchot
0.62
0.62
0.59
0.59
0.59
0.60
0.60
0.60
0.62
0.62
50k
onchot
0.59
0.59
0.58
0.58
0.58
0.55
0.55
0.60
0.60
split-ml
ml-S0k
onchot
0.61
0.61
0.61
0.56
0.56
0.56
0.57
0.57
0.57
0.61
0.61
0.61
of
10k
onchot
0.61
0.61
0.62
0.59
0.59
0.59
0.59
0.59
0.60
0.61
0.61
0.61
split-nf
nf-10k
onchot
0.64
0.64
0.60
0.60
0.60
0.62
0.62
0.62
0.63
0.64
of
100k
onchot
0.62
0.62
0.61
0.61
0.59
0.62
0.62
0.62
split-nf
n0-100k
onchot
0.64
0.64
0.65
0.61
0.62
0.62
0.62
0.62
0.62
0.64
0.64
0.64
of
150k
onchot
0.61
0.61
0.61
0.60
0.60
0.60
0.56
0.56
0.56
0.61
0.61
0.61
split-nf
n5-150k
onchot
0.64
0.64
0.60
0.61
0.61
0.62
0.62
0.62
0.63
sushi
default
0.66
0.66
0.67
0.65
susit-sushi
B
default
0.63
0.63
0.64
0.54
0.54
0.54
0.56
0.57
0.58
0.60
0.61
0.62
sushi
A
onchot
0.65
0.65
0.65
0.67
0.67
0.67
0.64
0.65
0.65
0.67
0.67
0.67
sulit-sushi
onchot
0.64
0.64
0.65
0.51
0.53
0.54
0.58
0.59
0.59
0.61
0.62
sushi
onehot 0.67
0.67
0.67
split-sushi
B
onchot 0.62
0.62
0.63
0.53
0.54
0.54
0.57
0.58
0.58
0.58
0.60
0.60
Table 6: Rerun of the experiments in Table 2 with the additional limitation that each user only
supply 5 ratings. This small change tanks the performance of the matrix factorization as the model cannot accurately capture users.
42


Reviews:
[{"review_id": "Ha9Z4dyEpL", "reviewer": "Reviewer_AY4G", "summary": "This paper considers a correlated probit model of preferences that avoids the Independence of Irrelevant alternatives (IIA) assumption; for this model, the paper shows that pairwise preference data isn't sufficient for provably learning the correlations, and suggests the use of three way preference data to provably solve for the parameters of this model.", "questions": "One question that I am interested in thinking about (and getting the authors to weigh in on) is what does this imply for policy learning in RLHF setups -- in particular, I am thinking about situations involving intransitive preferences.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. A very clearly written paper, a concrete model / setup and clear theoretical results.\n2. Interesting observations, and a particularly relevant problem in the current scheme of RLHF based pipelines for training foundation models.", "weaknesses": "1. In principle, this is a fairly stylized model and its applicability to realistic setups, particularly in RLHF is questionable in the sense of how useful it can be compared to optimizing the standard pairwise loss.\n2. This specific connection to training improved reward models (in RLHF) is not explored as part of the empirical evaluations which could've helped bolster the results offered by this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CscsWVkGZ6", "reviewer": "Reviewer_ZMzz", "summary": "This paper studies RUMs and explores the statistical and computational challenges of learning a correlated probit model that avoids the IIA assumption.\nThe authors first prove that pairwise preference data is fundamentally insufficient to capture correlation among utilities.\nThey then show that best-of-three preference data is both identifiable and sufficient, and propose a statistically and computationally efficient estimator that achieves near-optimal performance.", "questions": "- How strong is Assumption 3.1? Could the authors elaborate on its necessity and implications?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "I think that the contribution of this paper is significant, particularly Theorem 3.2, which rigorously proves that the classical pairwise comparison paradigm is fundamentally insufficient for recovering the parameters of a correlated probit model.\nThis finding challenges long-standing assumptions in choice modeling and clearly explains why existing methods fail to capture correlations in human preferences.\nMoreover, the paper provides both theoretical and practical advances by establishing the first identifiability and finite-sample guarantees for correlated Random Utility Models.\nOverall, the work offers a novel perspective on preference learning to the community.", "weaknesses": "Despite its strong theoretical contributions, the paper also has a few weaknesses and open questions.\n\n- In Theorem 5.2, the sample complexity depends on $\\gamma^{-24}$. Since $\\gamma$ can be extremely small in practical settings, this dependence may lead to an unrealistic sample requirement. It would be important to discuss whether this exponent can be tightened or whether a refined analysis could yield a more favorable dependence on $\\gamma$.\n\n- While the paper motivates its setting through RLHF, it treats each item as a single (prompt, response) pair. In RLHF, however, the prompt space is effectively infinite and highly structured. It remains unclear how the proposed framework could be extended to handle such a large or continuous prompt and action space. \n\n- I think this work is also highly related to general preference modeling frameworks, such as [1] and [2].\nCould the authors compare their proposed framework with these prior approaches and clarify the key similarities and differences?\n\n---\n[1] Ye, Chenlu, et al. \"Online iterative reinforcement learning from human feedback with general preference model.\" NeurIPS, 2024.\n[2] Zhang, Yuheng, et al. \"Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning.\", ICLR 2025.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m1AiAIuwqq", "reviewer": "Reviewer_GvjC", "summary": "This paper focusses on learning correlated utility models—parameterized as a correlated probit model——to avoid the IIA assumptions required by RUMs. The paper first proves that pairwise comparison data is insufficient to identify the data generating model. The paper then proves that best-of-three observations are both sufficient and necessary to learn the data generating probit model, and provides finite sample guarantees. Finally, the paper presents a series of experiments evaluating the use of best-of-three observations to learn the parameters of a probit model for 3 real-world datasets and 1 synthetic dataset.", "questions": "When does the best-of-three-probit model outperform the direct matrix completion method?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper explores an interesting question and provides substantive theoretical analysis to support their conclusion: pairwise comparisons are not sufficient to recover the parameters of a correlated choice model, but best-of-three comparisons are. This conclusion is interesting and, to the best of my knowledge, addresses an important gap in existing literature.", "weaknesses": "My main concerns are with the experiments in Section 6. Across all datasets, the proposed best-of-three-probit model matches or underperforms the direct matrix completion method. The authors claim that the direct matrix completion method is unrealistic in some scenarios—particularly when the set of alternatives and users is large—-but do not evaluate their method on those scenarios. Therefore, as far as I can tell, how their method also performs with larger alternatives/user sets remains an open question. Given the experimental evidence the authors do provide, there is no clear empirical benefit to using the best-of-three-probit model. I will raise my score if the authors can provide empirical evidence indicating where their best-of-three-probit model outperforms all other baselines. \n\nAlso, regarding Figure 3: the authors call this a “welfare maximizing experiment” but then note that the quantity they evaluate by “does not directly correlate with welfare as welfare is sensitive to the magnitude of utility change whereas this plot is not”. The authors should therefore change the name and how they discuss this experiment to avoid confusion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sZR5b0KH8G", "reviewer": "Reviewer_taUP", "summary": "The paper demonstrates that pairwise preference data is insufficient to learn correlated utility models in Random Utility Models (RUMs), specifically the correlated probit model. It proves that best-of-three comparisons are both necessary and sufficient for identifiability, proposes a near-optimal estimator, and empirically validates its advantages over traditional models in capturing human preference correlations.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is clearly written and logically organized, presenting formal identifiability theorems that rigorously establish the necessity and sufficiency of triplet comparisons for learning correlated probit models.\n\n2. The paper delivers a persuasive critique of the Independence of Irrelevant Alternatives (IIA) assumption commonly used in RLHF, and introduces a well-justified alternative that enables more nuanced and personalized preference modeling.\n\n3. The experimental results, though modest in some cases, effectively demonstrate the advantages of triplet-based modeling on real-world datasets (e.g., Netflix, MovieLens, Sushi).", "weaknesses": "While I am not a domain expert, I would like to offer a few comments based on my understanding of the paper. One notable limitation is the absence of experiments conducted in an actual RLHF setting (whether in reinforcement learning tasks or fine-tuning large language models). Although the theoretical and empirical results (i.e., the correlations) on general preference datasets are compelling, they may not fully demonstrate the practical value of the proposed approach. Without experiments in the RLHF context, it remains unclear how well the method performs in the scenarios it is ultimately intended to support.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)