Feasibility Is the Audit: Fast Subgroup Recovery from Hard Preferences

When people tell a learning system that one option is better than another, they are giving it more than a noisy score. A preference that is reliable, not a coin flip, rules out every parameter setting that would rank the pair the other way. Learning Parametric Distributions from Samples and Preferences shows that such deterministic preferences let an estimator converge at rate $O(1/n)$ instead of the usual $O(1/\sqrt{n})$. The proof assumes everyone shares one true parameter. Real feedback comes from populations with hidden subgroups whose tastes conflict. Position: Aggregate Preference Optimization Hides a Posterior Identifiability Failure for Pluralistic Alignment shows that a pooled preference model then reports a small aggregate error while failing badly on each subgroup. In their setup, opposing groups are averaged into apparent indifference.

This note argues that under hard preferences, the conflict between subgroups is itself the signal. When pooled hard constraints have no common solution, the pattern of which constraints clash shows who belongs together. We propose an estimator that partitions anonymous feedback sessions into groups whose constraints are each satisfiable, and then fits each group inside its own feasible region. We claim three things. Each subgroup, including the smallest, keeps the fast $O(1/n_k)$ rate in its own data count $n_k$. Held-out constraint violations give a validation signal for choosing the number of groups that needs no group labels and is not dominated by the majority. Reporting the worst group's parameter error, rather than the pooled error, exposes failures that standard reporting hides.

Core Claim

Pooled hard-constraint estimation breaks in a specific way when preferences come from a mixture. The constraint set $C_n$ becomes empty, because group A's half-spaces contradict group B's. The usual fix is to soften the constraints into a logistic Bradley–Terry model (the standard model where the chance of preferring one item is a sigmoid of the utility difference). Softening restores feasibility, but it falls back to the slow rate. It also produces exactly the neutrality illusion the position paper documents: a fitted norm of about 0.09 against true subgroup norms of 3.16. We propose to keep the constraints hard and give up the single-parameter assumption instead.

Before going further, an identifiability fact shapes the whole design. If preference pairs arrive with no linkage at all, and utilities are linear, then any $\theta$ and $-\theta$ together satisfy every possible constraint. The trivial two-group "cover" always exists, so pure anonymous pairwise constraints cannot identify a mixture. Mixture recovery therefore needs an anchor. We study two anchors that are realistic and do not require group labels.

The first anchor is session linkage. The system knows that a handful of preferences came from the same anonymous session, though not which group that session belongs to. The second anchor is accompanying samples, as in Jourdan et al. These are draws from the group's own distribution, and their likelihood pulls each component toward a non-degenerate solution.

Let sessions $s = 1, \dots, S$ each contribute a constraint set $C_s = \{\theta : \langle \theta, \Delta_{s,i} \rangle \ge 0 \ \forall i\}$, where $\Delta_{s,i}$ is the feature difference between the preferred and rejected item. Let $L_s(\theta)$ be the session's sample log-likelihood, which is zero if the session has no samples. The estimator solves

$$ \max_{z,\ \theta_1,\dots,\theta_K} \ \sum_{s} L_s(\theta_{z_s}) \quad \text{subject to} \quad \theta_{z_s} \in C_s \ \text{for all } s, $$

where $z_s \in \{1,\dots,K\}$ assigns session $s$ to a group. To tolerate annotator error, we replace hard feasibility with a cap on the number of violated constraints per group. This is a robust variant that limits how far noise can pull an estimate, the rigidity problem that the research file flags for single-group estimators.

The quantity we report is the worst-group error $\max_k \|\hat\theta_k - \theta_k\|$, alongside the pooled error. We conjecture that this scales as $O(1/n_{\min})$, where $n_{\min}$ is the minority group's constraint count. The conjecture follows from applying the Jourdan et al. polytope argument within each correctly assigned group. The open part is bounding the effect of misassignment.

Why This Is Not Already Done

The closest work is the position paper on aggregate preference optimization. It diagnoses the identifiability failure in synthetic mixture-of-Bradley–Terry data. It reports an 8× gap between aggregate mean squared error (0.008) and per-subgroup error (0.06–0.07), and a masking ratio that grows from 1.08 to 4.32 as subgroup diversity increases. It proposes no estimator and studies only stochastic preferences. Our work moves to hard preferences, says exactly which anchors restore identifiability, and builds and tests an estimator.

Jourdan et al. supply our core technique: maximizing likelihood inside the polytope of satisfied constraints, with matching $O(1/n)$ upper and lower bounds. Their setting has a single population.

Multitask Coactive Learning shares a global vector across users through its Balanced Perceptron. It requires explicit user IDs and measures average effort across users. Our sessions are anonymous fragments, and the groups must be discovered.

Multi-Objective Bayesian Optimization with Active Preference Learning treats improvement requests as directional information, but it assumes one decision maker.

Blind Pareto Fairness and Subgroup Robustness protects unknown subgroups through an adversarial game and proves a minimum protectable group size $\rho^*$. We borrow its group-blind stance. We expect a similar floor to appear: groups with fewer than about $d$ linked constraints cannot be told apart. Whether that floor shows up empirically is a constraint on our claims, not something to argue away.

The aggregate-masking literature motivates the reporting choice. That includes Rethink reporting of evaluation results in AI, the validation-trap findings of Simple data balancing achieves competitive worst-group-accuracy, and Efficient Bias Mitigation Without Privileged Information. Those papers show that model selection on aggregate validation metrics favors the majority. Held-out constraint violations, counted per session, are our proposed group-blind alternative.

Research Program

The work has three parts.

The first part is analysis. We will prove the $\theta / -\theta$ non-identifiability for unlinked pairs. We will then give sufficient conditions for identifiability under each anchor. For session linkage, this means sessions with enough constraints whose feasible cones for different groups are disjoint. For samples, it means separation in the sample likelihood. Finally, we will bound worst-group error as $O(1/n_{\min})$ plus a misassignment term that decays with session length.

The second part is the algorithm. Exact assignment is combinatorial, so we use an alternating scheme. In the assignment step, each session goes to the group whose feasible region it is compatible with, using a linear feasibility check, with ties broken by sample likelihood. In the fitting step, each group's parameter is fit by the polytope-constrained likelihood maximization of Jourdan et al. We initialize from a soft mixture fit. The number of groups $K$ is chosen by the held-out violation rate, computed per session and summarized by its worst decile rather than its mean. This targets the validation trap directly.

The third part is diagnostics. A pooled model's violations are concentrated in particular sessions, and that concentration itself flags hidden groups. We will test whether it does so before any mixture is fit, which would make it a cheap audit tool for existing preference datasets.

Baselines

The naive reference point is a pooled Bradley–Terry model fit by maximum likelihood on all sessions. This is the standard practice the position paper criticizes. In its testbed, the reported failure is an aggregate error of 0.008 against subgroup errors of 0.06–0.07, with a fitted norm of 0.09 against a true 3.16. Beating it means worst-group error well below 0.06 on the same 200-pair, 100-annotator, two-group, five-attribute configuration.

Pooled hard-constraint estimation with violation slack is the direct single-group analogue from Jourdan et al. It shows what hard constraints buy when the mixture is ignored.

The strongest competitor is a session-linked mixture of Bradley–Terry models fit by expectation-maximization. It uses the same anchor, the same $K$-selection budget, and the same random restarts as our method. It is strongest because it is exactly what a careful practitioner would try first. It is also identifiable under the same anchors, so it isolates the remaining question: whether hard constraints beat soft ones. No reported result for a mixture-of-Bradley–Terry estimator on these testbeds was found on Lacuna, so we will run it ourselves. Beating it means a steeper worst-group error curve, a log-log slope near −1 versus near −1/2, at low annotation noise. We will also locate the noise level at which the advantage disappears.

The key ablation keeps our assignment procedure but swaps hard feasibility for logistic loss inside each group. If the ablation matches the full method, the gains come from clustering rather than from hard constraints.

Two references bracket the comparison. The upper reference is the Balanced Perceptron and per-group polytope estimation given oracle group IDs. The lower personalization reference fits each session independently, as in the individual learners of Multitask Coactive Learning.

Why not just…?

Why not just fit a mixture of Bradley–Terry models with EM? This is the real threat, and the proposal is built around testing it. With session linkage, soft mixtures can recover groups, and under heavy annotation noise they may simply be better. Jourdan et al. prove that stochastic preferences stay at the slow rate, which predicts a gap at low noise. Our noise sweep, with the mixture-of-Bradley–Terry model as the headline competitor, decides where each method wins. If no low-noise regime favors hard constraints, the main claim fails.

Why not just collect more annotations for a pooled model? The position paper shows the failure is structural. The masking ratio grows with diversity, not with sample scarcity, and the norm collapse persists as data grows. Our scaling experiment will reproduce this plateau as the pooled baseline's worst-group curve.

Why not just cluster sessions by their loss under a pooled model, TAB-style, and refit? Efficient Bias Mitigation Without Privileged Information does this for classification, reaching 81.85% worst-group accuracy versus 55.98% for standard training on Colour-MNIST Even-Odd. For Robust Worst-Group Accuracy, Ignore Group Annotations uses a deliberately biased head to find the minority, as RAD. Both are offline two-pass procedures, and TAB uses $k=2$ clustering. We will run a two-pass loss-clustering variant as a baseline. Our claim is narrower: per-session feasibility is a sharper clustering signal than loss magnitude, especially for more than two groups. That is testable in the $K=3$–$5$ synthetic sweeps.

Why not just use oracle group labels with balancing or Group DRO? Group labels are rarely available. Stromberg et al. report that label-reliant methods on CelebA drop from 86% to below 79% at 20% group-label noise, while RAD-UW holds at about 83.5%. We include oracle-label estimation as an upper bound, not a competitor.

Proposed Experiments

We start with the synthetic parametric families of Jourdan et al.: multivariate Gaussian, Laplace, and Rayleigh. We extend them to mixtures of 2–5 components, with minority shares from 50% down to 5%, dimension $d$ from 2 to 50, and label-flip noise from 0 to 20%. For each method we plot worst-group and pooled parameter error against $n$. The decisive check is whether worst-group error follows slope −1 in $n_{\min}$ for our estimator while the soft mixture follows −1/2. We also locate where the minority becomes undetectable as its share shrinks, and compare that point to a $\rho^*$-style floor.

Next we replicate the position paper's pluralistic testbed exactly: two groups, five attributes, 200 pairs, 100 annotators, with diversity swept from 0 to 3. We add session linkage, where each annotator is one anonymous session. We report the masking ratio for every method. Success means a masking ratio near 1 across the sweep and recovered norms near 3.16. A separate run on unlinked pairs should confirm the predicted non-identifiability.

To move toward realistic features, we will use the five HelpSteer attributes, as used by Arithmetic Control of LLMs for Diverse User Preferences: Directional Preference Alignment with Multi-Objective Rewards, as the utility features. Simulated annotator groups follow distinct direction vectors over those attributes, for example one group that values conciseness and one that values verbosity. Responses are compared by those vectors with controlled noise. The ECML/PKDD 2006 spam benchmark from Multitask Coactive Learning provides a real heterogeneous population. We will hide its 15 user IDs and treat each user's emails as unlabeled sessions. The question is whether the estimator recovers a smaller number of latent taste groups and whether it approaches oracle-ID Balanced Perceptron performance. That paper's reported improvement over individual learners is not quantified in the file.

Across all settings, the label-free validation check compares choosing $K$ by the worst-decile held-out violation rate against choosing it by mean held-out likelihood. Choosing by the mean is the aggregate selection rule that the validation-trap literature warns about. Success means the violation-based choice finds the true $K$, or matches oracle-selected worst-group error, more often.

The project fails cleanly if the logistic ablation or the session-linked soft mixture matches our worst-group curves at every noise level. It also fails if session-level violation concentration does not separate groups better than pooled loss does.