Compote: Collapse-Resistant Multiple Hypothesis Learning For Sequential Recommendation

Introduction

Recommender systems filter vast product catalogues where their ranking dictates item visibility, directly driving discovery, engagement, and revenue [5]. As an example, Sequential recommendation predicts the next item from ordered interactions, closely mirroring real-world deployment where user preferences evolve and recent user’s interaction history is most informative (Rendle et al., 2010). There exists essentially two paradigms for sequential recommendation, both of which learn a single conditional model of the next item. The first family encodes the history with an autoregressive sequence model and scores items against a learned embedding table, moving from recurrent [7] and convolutional (Tang and Wang, 2018) encoders to causal self-attention [9], backbone of later variants (Sun et al., 2019; Zhou et al., 2020; Zhai et al., 2024). The second family treats retrieval as generation (Tay et al., 2022): TIGER (Rajput et al., 2023) quantizes item content embeddings into semantic identifiers and decodes the next item’s identifier token by token, which helps or rare items at the cost of a content encoder, a learned tokenizer and beam search. Both families nonetheless learn a single conditional model of the next item: one query representation, one score vector, one ranked list.

Next-item prediction is ambiguous. An user’s interaction history rarely determines the next item: it points to a set of plausible continuations, often in unrelated parts of the catalogue, so the next-item distribution is multimodal and a single query vector trained with cross-entropy settles between the modes instead of matching any one. Multi-interest learning addresses this by representing each user with several vectors, extracted by dynamic routing over capsules in MIND (Li et al., 2019), by multi-head attention with a diversity–accuracy aggregation step in ComiRec [4], or by activating a few concepts from a shared pool in SINE (Tan et al., 2021). REMI (Xie et al., 2023) keeps the same architecture and instead adds interest-aware hard negatives and a regularizer against routing collapse, where all interests attend to the same historical item. These methods already rely on a form of winner-takes-all (WTA) training, but it comes with the routing architecture and WTA is rarely examined as an objective in its own right. As a result, the optimal interests are not characterized, and diversity is usually encouraged through the architecture or additional penalties.

Our approach: COMPOTE. We frame next-item prediction as an inherently ambiguous learning problem and adopt multiple-choice learning (MCL) [6, 11] (Rupprecht et al. 2017), where a model outputs $M$ candidate hypotheses, but optimizes only the best-performing head. While this winner-takes-all objective effectively quantizes the conditional next-item distribution [12], it is prone to sub-optimal local minima where heads that underperform early permanently deactivate. Annealed MCL (Perera et al., 2024) mitigates this initialization sensitivity by annealing a soft-assignment temperature during training. We adapt this formulation to discrete catalogues with COllapse-resistant Multiple hyPOThesis lEarning (COMPOTE; § 2). A shared causal transformer feeds $M$ prediction heads, each defining a distinct distribution over the catalogue, which are optimized via the objective function $\ell_{\tau}$ in Equation (3) where $\tau$ is the temperature parameter. At high temperatures, all heads update uniformly; as the temperature vanishes, the objective smoothly converges to pure winner-takes-all. For inference and retrieval, we introduce max-similarity, a normalizer-free counterpart to the loss’s max-pooling operator (Proposition 5), which matches max-pooling accuracy on standard benchmarks while bypassing catalogue-wide softmax operations (§ 4.1).

Contributions. Methodologically, we propose COMPOTE, extending annealed multiple-choice learning to sequential recommendation alongside an efficient, normalizer-free retrieval rule (§ 2). On the theoretical front, we first establish a generalization bound scaling logarithmically in the number of hypotheses $M$ (Theorem 4). We further characterize the optimal hypotheses in the winner-takes-all limit, showing they partition the conditional item distribution into maximum-entropy regions (Theorem 7) and that pooled hypothesis scores preserve the Bayes ranking up to saturation ties (Proposition 6), proving head specialization emerges naturally without explicit diversity regularizers. Finally, across three Amazon Reviews 2023 benchmarks, COMPOTE consistently outperforms ID-based, generative, and multi-interest sequential baselines using item IDs alone, with capacity-matched ablations attributing these gains directly to the annealed MCL objective rather than model scaling, ensembling, or expert routing (§ 4).

Problem Statement and Architecture

We consider a supervised learning setting where a query $\mathbf{x} \in\mathcal{X}$ has an associated relevant item $\mathbf{y}$ in a catalogue $\mathcal{Y}$ of $N$ items, and the goal is to learn a model $q : \mathcal{X} \to\mathcal{S}_N$ mapping a query to a ranking of the items, i.e., a permutation of $\{1,\ldots,N\}$. Data pairs $(\mathbf{x},\mathbf{y}) \sim\mathbb{P}_{\mathbf{x},\mathbf{y}}$ are drawn i.i.d. from an unknown underlying probability distribution over $\mathcal{X} \times\mathcal{Y}$. In recommendation, queries are user histories and items are the entities being recommended (products, movies, etc.). We define $\Delta^{N-1} = \{\mathbf{p} \in[0,1]^N : \lVert\mathbf{p} \rVert_1 = 1\}$ as the $(N-1)$-dimensional probability simplex over $\mathcal{Y}$.

Datasets. We instantiate this setting on three categories from the Amazon 2023 review corpus ([8]): MUSICAL INSTRUMENTS, INDUSTRIAL AND SCIENTIFIC, and VIDEO GAMES. A query $\mathbf{x}$ is a user’s chronologically ordered interaction history, and the target $\mathbf{y}$ is the next reviewed item. Each category contains approximately 25,000 items and between 50,000 and 95,000 users (Table 5). Because each user contributes few observations relative to the catalog size, several next items may be plausible given the same history.

Dataset	#Users	#Items	#Interactions	Sparsity	Avg. len
Instrument	57,439	24,587	511,836	99.964%	8.91
Scientific	50,985	25,848	412,947	99.969%	8.10
Game	94,762	25,612	814,586	99.966%	8.60

Next-item Prediction with Multiple Hypotheses. As motivated in the introduction, the model aims at performing next-item prediction via multiple hypotheses. It can be formalized as a function $f : \mathcal{X} \to(\Delta^{N-1})^M$ that returns, for every hypothesis $m \le M$, a probability distribution $\mathbf{f}_m(\mathbf{x}) \in\Delta^{N-1}$ over the catalog, where $\mathbf{p}_{m,i} \triangleq f_m(\mathbf{x})_i$ is the probability that hypothesis $m$ assigns to item $i$ being relevant to query $\mathbf{x}$. The exact architecture of $f$ used in COMPOTE is detailed in Figure 1. At inference, the $M$ per-encoder distributions $\mathbf{p} = f(\mathbf{x})$ are combined into a single score vector over the catalog, which is then sorted to output the ranking

Learning Problem

Ideally, to learn $f$ avoiding hypothesis collapse, we would like to use the winner-takes-all loss, defined for a given prediction $\mathbf{p}=f(\mathbf{x})\in(\Delta^{N-1})^M$ as

Optimizing directly $\ell^{\mathrm{WTA}}$ is usually challenging because of the discontinuity introduced, which leads many people to resort to annealing methods. Following this path, we use the following loss function defined for temperature $\tau>0$ (to be annealed towards $0$) as

As the following result illustrates, annealing on $\ell_{\tau}$ leads to optimizing $\ell^{\mathrm{WTA}}$.

Proof can be found in Section A.2. This allows to extend by continuity the definition of $\ell_{\tau}$ to $\tau=0$ and consider $\tau\ge0$ in the remainder for statements and proofs.

Parallel with Annealed Multiple-Choice Learning (MCL). Methods employing a winner-takes-all strategy exist in other domains, such as audio source separation, under the framework of multiple-choice learning (MCL). In fact, our loss $\ell_{\tau}$ recovers a formulation from this domain, namely annealed MCL, yet existing literature does not address how to recombine these hypotheses for inference. Our primary contribution is demonstrating, both theoretically and empirically, that $\omega$ – Equation (1) – is the principled choice for hypothesis aggregation in recommender systems. Formally, the annealed MCL ((Perera et al., 2024)) objective function is defined as

and the following proposition establishes the link between the two losses.

Proof can be found in Section A.3. An important detail strengthens the link: In Perera et al. (2024), during the optimization, the gradient is only backpropagated through $\log p_{m,y}$ and not through $\gamma_m(\mathbf{y},\mathbf{p})$ – i.e. there is a stop-gradient operator on the $\gamma_j(\mathbf{y},\mathbf{p})$ term. The following result shows the two learning paradigm coincide exactly in practice. Proof can be found in Section A.4.

Learning Guarantees. We have discussed the loss function we use to train the model and have established a connection with the annealed MCL loss. We now turn to the theoretical analysis of the learning guarantees associated with this loss function. While in practice, we learn $f$ by minimizing the empirical risk $\widehat{\mathcal{L}}_{\tau}(f) = \mathcal{L}_{\tau}(f,\widehat{P}_S)$ over a training dataset, during training, $\tau$ goes to 0. Thus the learning guarantees need to be provided for the limiting loss $\ell^{\mathrm{WTA}}$. Over a training dataset $S = \{(\mathbf{x}_i,y_i)\}_{i=1}^n \sim P_{n,y}$, the empirical risk is denoted $\widehat{\mathcal{L}}^{\mathrm{WTA}}(f) = \mathcal{L}^{\mathrm{WTA}}(f,\widehat{P}_S)$ where $\widehat{P}_S$ is the empirical distribution of $S$. In order to get insights on the impact of the number of hypotheses $M$ on the learning problem, we are here interested in the generalization gap between the empirical WTA loss and the expected WTA loss $\mathcal{L}^{\mathrm{WTA}}(f,P_S)$ and provide a bound on this gap in terms of the Rademacher complexity of the hypothesis class $\mathcal{F}$ and the number of hypotheses $M$. Proof is given in Section D.2.

Insights from the bounds:

• The generalization gap is controlled by the Rademacher complexities of the individual heads, scaled by $1/\epsilon$. As the minimum predicted probability $\epsilon$ decreases, the bounds become looser, reflecting increased uncertainty in predictions. Ensuring a lower bound on predicted probabilities, via label smoothing, temperature scaling, or KL regularisation, therefore yields tighter guarantees.

• Theorem 4 shows that the number of hypotheses $M$ impacts the bound only through a $\mathcal{O}(\sqrt{\ln M/n})$ term, on top of the complexity of the best head. Adding more hypotheses therefore does not linearly increase the risk of overfitting, provided that the individual head complexities are controlled. Hence, one can benefit from the diversity of multiple heads without a proportional increase in generalization error.

We provide an empirical validation of this theoretical insight in § 18 in which we also discuss the practical implications of the saturation phenomenon described in Proposition 6 in § 4.

Learning Stabilization. We observe that training $f$ can be stabilized through the joint learning of the confidence score head via a binary cross-entropy loss over $\hat{\gamma}$ (see Figure 1). This finding aligns with the fact that the min operator is non-smooth and can be challenging to optimize. While beneficial, this effect is not the primary driver of the overall performance gains (see ablation study in Section G). Consequently, the formalization and technical details of this stabilization term are deferred to the appendix (see Section H).

COMPOTE leads to Optimal Ranking

This section explains why the max-pooling aggregation $\omega$ defined in Equation (1) is the natural choice when learning $f$ with $\ell_\tau$. In fact, the max-pooling aggregation $\omega$ can be seen as the limit for a temperature $\tau\to0$ of some aggregation $\omega^\tau$ (defined below), which cross-entropy is exactly $\ell_\tau$.

Proof can be found in Section B.1. Notice that $\omega^\tau(\mathbf{p})$ does not necessarily lie in $\Delta^{N-1}$, thus $\mathcal{L}_\tau(f) = -\mathbb{E}_{\mathbf{x},y}[\log\omega^\tau_y(f(\mathbf{x}))]$ can be lower than the Bayes risk $\inf_{q:\mathcal{X}\to\Delta^{N-1}}-\mathbb{E}_{\mathbf{x},y}[\log q_y(\mathbf{x})]$. Because $\omega^\tau(\mathbf{p})$ and $\omega(\mathbf{p})$ do not necessarily belong to the simplex, they do not recover the Bayes predictor (they are not a probability). However, for prediction $\mathbf{p}^\star$ that minimizes $\ell^{\mathrm{WTA}}$ in expectation, $\omega(\mathbf{p}^\star)$ ranks the items in the same order as the Bayes predictor, as formalized by the following statement.

Proof can be found in Section B.2. The ranking prediction associated to COMPOTE thus preserves the order of the Bayes predictor strictly, except in the single saturation case $\omega_a(\mathbf{p}^\star)=\omega_b(\mathbf{p}^\star)=1$; understanding this failure case is informative for the choice of $M$. Intuitively, it happens when (given some $x$) at least two items $a$ and $b$ have large probabilities $q^\star_a,q^\star_b \ge1/M$: for this $x$, one hypothesis $m$ will be such that $p^\star_{m,i}=\mathbb{1}_{[i=a]}$ (see Theorem 7 for why this happens), another hypothesis $m'$ will be such that $p^\star_{m',i}=\mathbb{1}_{[i=b]}$. Hence, even though $q^\star_a>q^\star_b$, then $\phi_a=\phi_b=1$. This advocates for using values for $M$ that are not too large, which is validated experimentally in Figure 5.

The performance of using the aggregation $\omega$ over the learning done via annealing of $\ell_\tau$ is also validated empirically in the recommendation setting on several Amazon 2023 datasets.

Preprocessing and protocol. We evaluate on the three Amazon 2023 subsets introduced in § 2. Following prior work (Rajput et al., 2023; Zhou et al., 2020; Zheng et al., 2025), we apply the benchmark 5-core filtering (Amazon Reviews’23 Benchmark, 2023), which iteratively discards users and items with fewer than five interactions, and truncate histories to 50 items at both training and test time. We adopt the leave-one-out split of Kang and McAuley [9]: the last interaction of each user is the test target, the penultimate one is used for validation and the remainder for training. We report Hit Rate (H@$K$) and NDCG (N@$K$) for $K \in\{5,10\}$, computed by ranking the entire catalog rather than sampled negatives; since each test instance has a single relevant item, H@$K$ coincides with Recall@$K$.

Baselines. We compare against seven ID-based sequential recommenders (Caser (Tang and Wang, 2018), HGN (Ma et al., 2019), GRU4Rec ([7]), BERT4Rec (Sun et al., 2019), SAS-Rec ([9]), HSTU (Zhai et al., 2024) and S3-Rec (Zhou et al., 2020)) and against the generative recommender TIGER (Rajput et al., 2023), whose numbers we take from Zheng et al. (2025). Because COMPOTE predicts several hypotheses per query, we also compare against six multi-interest recommenders that represent a user by several vectors: MIND (Li et al., 2019), ComiRec-DR and ComiRec-SA ([4]), SINE (Tan et al., 2021), Re4 (Zhang et al.,

2022. and REMI (Xie et al., 2023), which we train ourselves under the protocol above. Section F describes each method.

In Table 1, COMPOTE is best in 11 of the 12 columns, the exception being H@10 on Scientific where HSTU (4.29) and TIGER (4.22) edge it out (4.20). Against TIGER, the strongest baseline on NDCG, COMPOTE improves N@5 by 9.7% on Scientific and 9.6% on Game, and ties on Instrument (2.44 $\to$ 2.45). Note that TIGER performs autoregressive generative retrieval over semantic identifiers derived from item text and decodes them with beam search at inference, while COMPOTE sees item identifiers only and ranks the catalogue in a single forward pass: modelling the multimodality of the next-item distribution suffices to beat a content-aware generative recommender.

Method	Instrument H@5	Instrument H@10	Instrument N@5	Instrument N@10	Scientific H@5	Scientific H@10	Scientific N@5	Scientific N@10	Game H@5	Game H@10	Game N@5	Game N@10
Caser (Tang and Wang, 2018)	2.41	3.86	1.51	1.97	1.59	2.57	1.01	1.32	3.30	5.53	2.09	2.81
HGN (Ma et al., 2019)	3.21	5.17	2.02	2.65	2.12	3.51	1.31	1.76	4.24	6.87	2.71	3.56
GRU4Rec [7]	3.24	5.01	2.09	2.66	2.02	3.38	1.29	1.73	4.99	7.99	3.20	4.16
BERT4Rec (Sun et al., 2019)	3.07	4.85	1.95	2.52	1.86	2.96	1.19	1.55	4.60	7.35	2.98	3.86
SASRec [9]	3.33	5.23	2.13	2.74	2.59	4.12	1.50	1.99	5.35	8.47	3.31	4.38
HSTU (Zhai et al., 2024)	3.43	5.77	1.91	2.71	2.71	4.29	1.47	1.98	5.78	9.03	3.34	4.42
S3-Rec (Zhou et al., 2020)	3.17	4.96	1.99	2.57	2.63	4.18	1.71	2.19	4.85	7.69	3.15	4.06
TIGER (Rajput et al., 2023)	3.70	5.64	2.44	3.06	2.64	4.22	1.75	2.26	5.59	8.68	3.66	4.67
MIND (Li et al., 2019)	2.71	4.42	1.65	2.20	2.11	3.29	1.27	1.65	3.22	5.20	1.99	2.65
ComiRec-DR [4]	2.67	4.37	1.64	2.19	2.14	3.41	1.30	1.72	3.21	5.23	1.96	2.60
ComiRec-SA [4]	2.64	4.31	1.62	2.15	2.08	3.31	1.26	1.65	3.20	5.19	1.95	2.61
SINE (Tan et al., 2021)	3.08	5.20	1.52	2.24	2.36	3.83	1.21	1.68	5.26	8.80	2.77	3.87
Re4 (Zhang et al., 2022)	2.13	3.74	1.23	1.66	1.61	2.66	0.95	1.27	3.15	5.61	1.98	2.68
REMI (Xie et al., 2023)	2.73	4.34	1.71	2.22	2.20	3.86	1.21	1.70	4.14	7.42	2.29	3.30
COMPOTE (ours)	3.75	5.83	2.45	3.10	2.84	4.20	1.92	2.35	6.06	9.26	4.01	5.04

Multi-interest models trade precision for coverage. Multi-interest recommenders are the closest analogue of COMPOTE, yet none reaches the second-best value of any column, and only SINE on Game H@10 (8.80) exceeds SASRec. SINE is within 5% of COMPOTE on that column but 31% below on N@5 (2.77 against 4.01): maximising over interest vectors widens the candidate pool without placing the target near the top, whereas COMPOTE improves both.

Fast Retrieval for COMPOTE

For large-scale recommender systems, it is desirable to have a model that is compatible with vector databases to enable a retrieval scaling sublinearly with $N$. As $f_{m,i}(\mathbf{x}) = \operatorname{softmax}(\cos(h_m(\mathbf{x}),\mathbf{e}_i)/\beta)$ (see Figure 1), there is already a dependency linear in $N$ with the computation of the softmax. This section shows that, for the purpose of ranking the items for recommendation, the softmax can be dropped at inference – it is possible to apply $\omega$ directly on the cosine similarities to obtain scores to rank the items. Formally, it means replace at inference $g = \operatorname{argsort} \circ\omega\circ f$ by

Due to the following identity: $\log\max_{m \le M}(\operatorname{softmax}_i(s_{m,.})) = \max_{m \le M}(s_{m,i} - \log Z_m)$ where $Z_m = \sum_{i=1}^{N} \exp(s_{m,i})$, $g$ and $\tilde{g}$ rank items identically if $Z_m$ is constant across the hypotheses. This turns out to happen in practice as the standard deviation of $Z_m$ across hypotheses is largely lower that its value (Figure 3). Experiments confirm this as using $\tilde{g}$ rather than $g$ comes at no loss in ranking accuracy (Table 2).

Aggregator	Normalizer	H@5	H@10	N@5	N@10
$g$ – ”max softmax”	required	6.04	9.27	4.01	5.05
$\tilde{g}$ – ”max cosine similarity”	not required	6.06	9.26	4.01	5.04

This equivalence is a key deployment result: the model requires neither a catalog-wide softmax nor its normalizer, making the model directly compatible with standard vector databases. For this reason, we report most of the results with $\tilde{g}$ (ex: Table 3).

Method
	Instrument				Scientific				Game
	H@5	H@10	N@5	N@10	H@5	H@10	N@5	N@10	H@5	H@10	N@5	N@10
MCT-SASRec	3.63	5.70	2.34	2.97	2.55	3.87	1.71	2.13	5.73	8.84	3.78	4.78
MCT-EnsCE	3.54	5.53	2.28	2.96	2.42	3.80	1.60	2.03	5.74	8.81	3.78	4.77
MCT-Router	3.57	5.48	2.28	2.89	2.40	3.60	1.64	2.00	5.74	8.81	3.78	4.77
COMPOTE (ours)	3.75	5.83	2.45	3.10	2.84	4.20	1.92	2.35	6.06	9.26	4.01	5.04

Ablations: Where Do the Gains Come From?

COMPOTE could outperform a single-head model for three distinct reasons, additional capacity, naive ensembling, or mixture-of-experts (MoE) routing. We isolate each with a matched-capacity variant (Table 3). COMPOTE outperforms all three on every dataset and metric.

Not a bigger model: MCT-SASRec spends the parameter budget of COMPOTE on a single hypothesis with a deeper prediction head. It is the strongest of the three variants and still trails COMPOTE everywhere (N@5 of 2.34 against 2.45 on Instrument, 1.71 against 1.92 on Scientific, 3.78 against 4.01 on Game). At equal capacity, the multi-hypothesis parameterization beats a deeper single-hypothesis head.

Not an ensemble: MCT-EnsCE keeps the architecture of COMPOTE but trains every head on every example with equal weight, without confidence supervision or annealing. It minimizes

the $\tau\to\infty$ limit of the soft assignment in Equation (4). It falls below COMPOTE on every dataset and metric, so the gains are not explained by architectural multiplicity or naive ensembling alone.

Not a mixture of experts: MCT-Router follows the routing recipe of multi-interest recommendation (§ 1): it keeps the shared encoder and replaces the training of COMPOTE by a learned gate that selects one expert per query. It trails COMPOTE everywhere (N@5 of 2.28 against 2.45 on Instrument, 1.64 against 1.92 on Scientific, 3.78 against 4.01 on Game). The next section traces this gap to head collapse: without the annealed winner-takes-all objective, routing fails to induce distinct hypotheses (§ 5.1).

Hypothesis Specialization

We first show that, unlike the matched-capacity variants of Section 4.2, COMPOTE learns hypotheses that do not collapse and carry complementary rankings. We then explain this phenomenon by characterizing what each hypothesis $p_m^\star$ learns at the winner-takes-all limit $\tau\to0$.

Collapse and Oracle Evidence

We quantify collapse through the mean pairwise cosine similarity of the head outputs. For a query $x$, let $\bar{\mathbf{h}}_m(x)=\mathbf{h}_m(x)/\lVert\mathbf{h}_m(x)\rVert_2$ and define $S(x)=\frac{1}{M(M-1)}\sum_{j,k=1}^{M}\bar{\mathbf{h}}_j(x)^\mathsf{T}\bar{\mathbf{h}}_k(x)$. We report its test-set average; $S=1$ means that all heads have the same direction. MCT-EnsCE and MCT-Router reach $S=1.00$ on all three datasets, whereas COMPOTE obtains 0.64, 0.61 and 0.58 on InstruMENT, SCIENTIFIC and GAME, respectively (Table 6). Thus, neither architectural multiplicity nor learned routing is sufficient to prevent collapse.

Method	Instrument	Scientific	Game
MCT-EnsCE	1.00	1.00	1.00
MCT-Router	1.00	1.00	1.00
COMPOTE (ours)	0.64	0.61	0.58

Oracle head selection. To test whether COMPOTE’s distinct heads contain complementary rankings, we compare the max-similarity rule of Equation (10) with an oracle that observes the target and selects the head assigning it the highest similarity,

then ranks every item using $s_{m^{\mathrm{orc}}(\mathbf{x},y),i}(\mathbf{x})$. The oracle is not deployable, but it measures whether one hypothesis ranks the target substantially better than the aggregated list. For MCT-EnsCE and MCT-Router, aggregated and oracle N@5 coincide exactly on every dataset: selecting among collapsed heads cannot help (Table 7). For COMPOTE, oracle selection raises N@5 by 53% on INSTRUMENT (2.45 → 3.75), 83% on SCIENTIFIC (1.92 → 3.52) and 94% on GAME (4.01 → 7.78). The ranking gains therefore coincide with a qualitative change in the learned predictor: COMPOTE produces distinct heads whose rankings contain complementary signal.

Method	Instrument		Scientific		Game
	Aggregated	Oracle	Aggregated	Oracle	Aggregated	Oracle
MCT-EnsCE	2.28	2.28	1.60	1.60	3.78	3.78
MCT-Router	2.28	2.28	1.64	1.64	3.78	3.78
COMPOTE (ours)	2.45	3.75	1.92	3.52	4.01	7.78

These findings raise a structural question: why does COMPOTE’s training create complementary hypotheses, whereas ensemble and routed objectives collapse?

What Each Hypothesis Learns

For a fixed query, Theorem 7 describes the optimal hypotheses through three properties:

• (P1) Partition. The catalog splits into disjoint cells $\mathcal{Y}_1,\ldots,\mathcal{Y}_M$, each hypothesis supported on its own cell.

• (P2) Faithfulness within cells. On $\mathcal{Y}_m$, $p_m^\star$ is $q^\star$ renormalized by $Q_m$: each hypothesis ranks the items of its cell exactly as the Bayes predictor does, and therefore still depends on the query through $q^\star$.

• (P3) Balance. The partition maximizes the entropy of $(Q_m)_{m=1}^{M}$, so the cells split the mass of $q^\star$ as evenly as the catalogue allows.

Proof can be found in Section K.1.

COMPOTE is trained at $\tau>0$ with softmax heads, so the exact zeros of Equation (12) cannot be reached. We test each property through its observable signature. Mirroring the tessellation of Theorem 7, the empirical cell of head $m$ on query $\mathbf{x}$ is $\mathcal{Y}_m(\mathbf{x})=\{y\in\mathcal{Y}:m=\operatorname*{argmax}_{m'}f_{m',y}(\mathbf{x})\}$, and the winning head of a test pair $(\mathbf{x},y)$ is the head whose cell contains $y$. All diagnostic metrics are computed on GAME, with $M=3$ unless stated otherwise, and Table 4 reports them for $M\in\{3,4,5\}$. The protocol is detailed in § 21, which also reports the same partition on SCIENTIFIC.

$M$	In-cell mass	Win frequency (%)	Sector share (%)	$\hat{\mathcal{L}}^{\mathrm{WTA}}$	$\hat{\mathcal{L}}^{\mathrm{WTA}} + \log M$	Sector agreement
3	0.929	[32.0, 34.4]	[27.9, 36.3]	7.32	8.41	98.5%
4	0.915	[24.5, 25.6]	[23.4, 27.1]	7.02	8.41	98.7%
5	0.937	[18.9, 21.1]	[15.5, 25.3]	6.71	8.32	99.4%

(P1) The hypotheses partition the catalogue. The non-collapsed head directions of Table 6 are a first signature of (P1). The partition holds for the full distributions and not only for the top of the rankings: each head keeps between 91.5% and 93.7% of its softmax mass inside its own cell, for every $M$. The retrieved sets are therefore nearly disjoint. The top-10 lists of two heads on the same query have a mean Jaccard overlap of 0.008, and 91.8% of the catalogue items retrieved at test time are reached by a single head only. Both sharpen with $M$, reaching 0.001 and 98.6% at $M=5$. Figure 2 shows the resulting partition: projected onto the plane of the head directions, the catalogue splits into three sectors, one per hypothesis.

(P2) Each hypothesis remains query-dependent. By (P2), a hypothesis is not a fixed list of items: its ranking follows $q^\star(x)$. Empirically, the top-10 of a given head overlaps by only 0.017 to 0.026 Jaccard between two different histories, and in Figure 2 the head closest to the target changes from query to query. (P1) and (P2) together explain the oracle gap in Table 7. At the optimum, the target $y$ belongs to a single cell $\mathcal{Y}_m$, where it competes only with the other items of $\mathcal{Y}_m$, ranked by $q^\star$. Selecting that head therefore ranks $y$ no worse than the Bayes predictor over the full catalogue. The cosine oracle of Equation (11) makes exactly this choice, as it picks the winning head on 98.9% to 99.7% of test pairs. This is the behavior of COMPOTE, where the oracle-selected head ranks the target substantially higher than the pooled list, while collapsed models exhibit no oracle gain.

(P3) The cells split the mass evenly. The win frequency of a head (the fraction of test targets it wins), estimates $\mathbb{E}_x[Q_m(x)]$ without access to $q^\star$. Win frequencies stay within 1.6 points of $1/M$ for every $M$, and their normalized entropy exceeds 0.999. Balance holds in mass and not in item counts: the heads own between 15.5% and 25.3% of the catalogue at $M = 5$, yet each wins close to 20% of the targets. This is the balance (P3) predicts, since $Q_m$ weights items by $q^\star$, so a head with fewer items holds items that are more often the next one. Balance also matters for aggregation: if $Q_m = 1/M$ for all $m$, Equation (12) gives $\omega(\mathbf{p}^\star) = Mq^\star$, so max-pooling recovers the Bayes ranking exactly. Balance also fixes the value of the optimal loss, and Section K.3 checks that the test loss follows the predicted $\log M$ law.

Discussion and Conclusion

We introduced COMPOTE, which uses annealed multiple-hypothesis learning to produce complementary rankings for sequential recommendation. Our theoretical and empirical results show that it prevents head collapse, preserves ranking quality, and improves performance across three benchmarks. We leave combining COMPOTE with semantic identifiers for future work, which could improve recommendations for rare items. It also remains to explain why its theoretically query-dependent cells form an almost static catalogue tiling and how this structure relates to item-embedding geometry (Section M).

AI Use Statement

We used generative AI tools to polish the manuscript, primarily by correcting grammar and improving clarity, and to assist with portions of the experimental code. Parts of the theoretical proofs (the generalization bounds) were also drafted with the help of generative AI, but all proofs were verified and corrected by the authors.

Acknowledgments

This project was provided with computing HPC and storage resources by GENCI at IDRIS thanks to the grant 2026-A0191016862 on the supercomputer Jean Zay’s V100 partition.

Proofs

Preliminary results

Proof. The log-sum-exp is the convex conjugate of the negative entropy.

Proof of prop:tau-to-wta

Proof of Proposition 1. The proof is a direct consequence of Proposition 8 as $\lim_{\tau\to0^{+}}\operatorname{softmax}\left(\frac{1}{\tau}\log(\mathbf{p}_{\cdot,\mathbf{y}})\right) = \max_{m \le M}\frac{1}{\tau}\log(p_{m,\mathbf{y}})$.

Proof of prop:loss-tau-to-awta

Proof of Proposition 2. This is a direct consequence of Proposition 8.

Proof of cor:awta-gradient

Proof of Corollary 3.

On the other hand, differentiating $\ell_{\tau}(\mathbf{y},\mathbf{p}^{\theta})=-\tau\log\left(\sum_{m\le M}(p_{m,y}^{\theta})^{1/\tau}\right)$ directly gives

This concludes the proof.

Proofs of sec:compote-to-ranking

Proof of prop:loss-via-pooling

Proof of Proposition 5. Fix $(\mathbf{y},\mathbf{p})$. For $\tau>0$, by definition of $\omega^{\tau}$ in (19),

the last equality being the definition of $\ell_{\tau}$ in (3).

For $\tau=0$, understood as the limit $\tau\to0^{+}$ on both sides, $\omega^{0}=\omega$ gives $-\log\left(\omega_y^{0}(\mathbf{p})\right)=-\log\max_{m\le M}p_{m,y}=\ell^{\mathrm{WTA}}(\mathbf{y},\mathbf{p})$, which equals $\lim_{\tau\to0+}\ell_{\tau}(\mathbf{y},\mathbf{p})$ by Proposition 1.

Proof of prop:emax-ranking

Proof of Proposition 6. Denote the inner risk by $L(\mathbf{p})=\mathbb{E}_{\mathbf{y}\sim\mathbf{q}^{\star}}[\ell^{\mathrm{WTA}}(\mathbf{y},\mathbf{p})]$. By Proposition 5,

so that, $L(\mathbf{p}^{\star})$ being finite, $\omega_y(\mathbf{p}^{\star})>0$ for every $y$ with $q_y^{\star}>0$. Fix $a,b\in\mathcal{Y}$ with $q_a^{\star}>q_b^{\star}$; in particular $q_a^{\star}>0$ and $\omega_a(\mathbf{p}^{\star})>0$.

Weak inequality. Assume $\omega_b(\mathbf{p}^{\star})>0$, the conclusion being trivial otherwise, and let $\Pi_{ab}$ be the operator associated with the transposition $\pi=(a\ b)$. Then

the terms at $y\notin\{a,b\}$ cancelling and the remaining logarithms being finite. Since $L(\Pi_{ab}\mathbf{p}^{\star})\ge L(\mathbf{p}^{\star})$ and $q_a^{\star}>q_b^{\star}$, this gives $\omega_a(\mathbf{p}^{\star})\ge\omega_b(\mathbf{p}^{\star})$.

Strictness up to saturation. Assume now $\omega_a(\mathbf{p}^{\star})=\omega_b(\mathbf{p}^{\star})$; we show that this common value is 1. Let $(\mathcal{Y}_m)_{m\le M}$ be the tessellation of Theorem 7, $m(y)$ the index of the cell containing $y$ and $Q_m$ the mass of $\mathcal{Y}_m$, so that $\omega_y(\mathbf{p}^{\star})=p_{m(y),y}^{\star}=q_y^{\star}/Q_{m(y)}$ whenever $Q_{m(y)}>0$, and, by equation (22),

Suppose first $q_b^{\star}>0$, so that $Q_A,Q_B>0$ where $A=m(a)$ and $B=m(b)$. The items $a$ and $b$ lie in distinct cells: were they in the same cell, the ratio $\omega_a(\mathbf{p}^{\star})/\omega_b(\mathbf{p}^{\star})=q_a^{\star}/q_b^{\star}>1$ would contradict the assumed equality. Exchanging $a$ and $b$ between the two cells produces a partition of $\mathcal{Y}$ with masses $Q_A-u$ and $Q_B+u$, where $u=q_a^{\star}-q_b^{\star}>0$, the other cells being unchanged; the predictor it defines through equation 12 is admissible, so equation (25) and the optimality of $\mathbf{p}^{\star}$ give

Writing $\Delta=Q_A-Q_B$, we have $g'(t)=\log\frac{Q_B+t}{Q_A-t}$, so $g$ decreases on $(-\infty,\Delta/2]$ and increases on $[\Delta/2,Q_A)$; being symmetric about $\Delta/2$, it satisfies $g(u)\ge g(0)$ with $u>0$ only if $u\ge\Delta$. Consequently

using $q_a^{\star}\ge q_b^{\star}+\Delta$ and $Q_B\ge q_b^{\star}$ if $\Delta>0$, and $q_a^{\star}>q_b^{\star}$ with $Q_A\le Q_B$ if $\Delta\le0$. The assumed equality reads $\omega_a(\mathbf{p}^{\star})-\omega_b(\mathbf{p}^{\star})=(q_a^{\star}Q_B-q_b^{\star}Q_A)/(Q_AQ_B)=0$ and therefore forces $\Delta>0$, $q_a^{\star}=q_b^{\star}+\Delta$ and $Q_B=q_b^{\star}$, whence $\omega_b(\mathbf{p}^{\star})=q_b^{\star}/Q_B=1$.

Suppose finally $q_b^{\star}=0$. If $Q_B>0$ then $\omega_b(\mathbf{p}^{\star})=q_b^{\star}/Q_B=0<\omega_a(\mathbf{p}^{\star})$, excluding the equality. Otherwise every $y\in\mathcal{Y}_B$ has $q_y^{\star}=0$; let $\mathbf{p}'$ be $\mathbf{p}^{\star}$ with head $B$ replaced by $\mathbf{e}_a$. For $y\notin\mathcal{Y}_B\cup\{a\}$ the maximum defining $\omega_y$ is attained by a head other than $B$, so $\omega_y(\mathbf{p}')=\omega_y(\mathbf{p}^{\star})$; the items of $\mathcal{Y}_B$ carry no mass; and $\omega_a(\mathbf{p}')=1\ge\omega_a(\mathbf{p}^{\star})$. Hence $L(\mathbf{p}')\le L(\mathbf{p}^{\star})$ with equality only if $\omega_a(\mathbf{p}^{\star})=1$, and the optimality of $\mathbf{p}^{\star}$ forces $\omega_a(\mathbf{p}^{\star})=1$. □

Per-Head Normalizer

Protocol. For the $M=3$ game checkpoint of Table 2, we compute $\log Z_m(\mathbf{x})=\log\sum_{i\le N}\exp(s_{m,i}(\mathbf{x}))$ over all $N=25{,}612$ items for each of the 94,762 test queries, with $s_{m,i}=\cos(h_m,e_i)/\beta$ and $\beta=0.07$.

The normalizer is head-independent. The three distributions nearly overlap (Figure 3), with means 13.67, 13.63, and 13.79. At fixed $x$, the cross-head standard deviation of $\log Z_m(x)$ is 0.13 on average; its range has median 0.28, 95th percentile 0.62, and maximum 1.10.

Effect on the ranking. Because $\log\max_m \operatorname{softmax}_i(s_{m,\cdot}) = \max_m(s_{m,i} - \log Z_m)$, a ranking change requires max-cosine scores within $\beta$ times the cross-head range: 0.020 for the median query, 0.043 at the 95th percentile, and 0.077 at most. Accordingly, Table 2 shows no measurable loss from dropping the normalizer.

Generalization Bound

Proof of thm:wta-generalization

We first provide here a generalization bound for the log-loss in Theorem 9, which is a direct consequence of the Rademacher complexity of the hypothesis class $\mathcal{F}^M$. We then provide a refined version of the generalization bound in Theorem 4, which has a milder dependence on the number of heads $M$.

Proof of Theorem 9. Step 1: Boundedness and Lipschitz continuity of the loss function. Consider the scalar loss function $-\log(t)$ restricted to $t \in[\epsilon,1]$.

• Upper Bound ($B$): Since $t \ge\epsilon$, the loss is non-negative and bounded above by:

@page 15/26 starts_mid=0 ends_mid=1 The normalizer is head-independent. The three distributions nearly overlap (Figure 3), with means 13.67, 13.63, and 13.79. At fixed $x$, the cross-head standard deviation of $\log Z_m(x)$ is 0.13 on average; its range has median 0.28, 95th percentile 0.62, and maximum 1.10.

Effect on the ranking. Because $\log\max_m \operatorname{softmax}_i(s_{m,\cdot}) = \max_m(s_{m,i} - \log Z_m)$, a ranking change requires max-cosine scores within $\beta$ times the cross-head range: 0.020 for the median query, 0.043 at the 95th percentile, and 0.077 at most. Accordingly, Table 2 shows no measurable loss from dropping the normalizer.

Generalization Bound

Proof of thm:wta-generalization

We first provide here a generalization bound for the log-loss in Theorem 9, which is a direct consequence of the Rademacher complexity of the hypothesis class $\mathcal{F}^M$. We then provide a refined version of the generalization bound in Theorem 4, which has a milder dependence on the number of heads $M$.

Proof of Theorem 9. Step 1: Boundedness and Lipschitz continuity of the loss function. Consider the scalar loss function $-\log(t)$ restricted to $t \in[\epsilon,1]$.

• Upper Bound ($B$): Since $t \ge\epsilon$, the loss is non-negative and bounded above by:

Thus, for every sample $(x_i, y_i)$, $\min_{m\in[M]}(-\log f_{m,y_i}(x_i)) \in[0,B]$.

• Lipschitz Continuity ($L_\epsilon$): By the Mean Value Theorem, the Lipschitz constant is bounded by the supremum of the derivative:

Therefore, for any $t_1,t_2 \ge\epsilon$, we have $|(-\log t_1)-(-\log t_2)| \le\frac{1}{\epsilon}|t_1-t_2|$.

Step 2: Concentration via McDiarmid’s Inequality.

We want to show that the empirical loss on $n$ finite samples $\widehat{\mathcal{L}}^{\mathrm{WTA}}_S(f)$ is close to the true expected loss $\mathcal{L}^{\mathrm{WTA}}(f)$ uniformly across all possible models in our hypothesis class $\mathcal{F}^M$. Define the worst-case generalisation gap function:

Suppose we change a single data point in $S=\{(x_1,y_1),\ldots,(x_n,y_n)\}$ to create a neighboring dataset $S'=\{(x_1,y_1),\ldots,(x_i',y_i'),\ldots,(x_n,y_n)\}$. The change in $\Phi(S)$ can be bounded as:

Because changing one sample alters $\Phi(S)$ by at most $c_i=\frac{\log(1/\epsilon)}{n}$, we can apply McDiarmid’s inequality to bound the deviation of $\Phi(S)$ from its expectation [3]:

Evaluating $\sum_{i=1}^n c_i^2=n\cdot\left(\frac{\log(1/\epsilon)}{n}\right)^2=\frac{\log^2(1/\epsilon)}{n}$. Set the probability tail $\exp\left(\frac{-2t^2n}{\log^2(1/\epsilon)}\right)=\frac{\delta}{2}$. Then, solving for $t$ gives

Thus, with probability at least $1-\frac{\delta}{2}$:

Step 3: Symmetrization and min-operator decomposition.

Our goal now is to bound the expected supremum $\mathbb{E}_S\left[\sup_{f\in\mathcal{F}^M}\left(\mathcal{L}^{\mathrm{WTA}}-\widehat{\mathcal{L}}^{\mathrm{WTA}}_S\right)\right]$ in terms of the Rademacher complexity of the hypothesis class $\mathcal{F}^M$. For doing so, we can redefine $\mathbb{E}_S[\Phi(S)]$ as follows:

where $S'$ is an independent ghost sample drawn from the same distribution. Then by gathering the terms, and using Jensen’s inequality, we can pull the expectation over $S'$ outside of the supremum:

Now, since $(x_i,y_i)$ and $(x_i',y_i')$ are identically distributed, introducing independent random sign variables $\sigma_i\in\{-1,+1\}$ with $\mathbb{P}(\sigma_i=1)=1/2$ does not change the distribution of their difference:

and using the triangle inequality leads to the following decomposition:

where $\widehat{\mathcal{R}}_{S}(\mathcal{G}_{\mathrm{emax}})$ is the empirical Rademacher complexity of the composite pointwise minimum class:

and $\mathcal{R}_{n}(\mathcal{G}_{\mathrm{emax}})=\mathbb{E}_{S}[\widehat{\mathcal{R}}_{S}(\mathcal{G}_{\mathrm{emax}})]$.

For a fixed sample $S$, using the structural property of Rademacher complexity under pointwise minimum operators over $M$ hypothesis classes (decomposition of the pointwise minimum as a weighted sum of indicator functions and using results from Bartlett and Mendelson [2]), we bound $\widehat{\mathcal{R}}_{S}(\mathcal{G}_{\mathrm{emax}})$ as:

where $\mathcal{F}_{m,y}=\{x\mapsto f_{m,y}(x):f\in\mathcal{F}\}$. Since $t\mapsto-\log t$ is $(1/\epsilon)$-Lipschitz on $[\epsilon,1]$, applying Talagrand’s Contraction Lemma (Mohri and Medina (2014); Ledoux and Talagrand [10]) yields:

Taking expectations $\mathbb{E}_{S}$ on both sides gives $\mathcal{R}_{n}(\mathcal{G}_{\mathrm{emax}})\leq\frac{1}{\epsilon}\sum_{m=1}^{M}\mathcal{R}_{n}(\mathcal{F}_{m,y})$.

Final combination. Substituting into $\mathbb{E}_{S}[\Phi(S)]\leq2\mathcal{R}_{n}(\mathcal{G}_{\mathrm{emax}})$ and applying concentration yields the stated bound.

Proof of cor:wta-generalization-refined

Proof of Theorem 4. To prove the theorem, we need to show that the expected Rademacher complexity of the minimum operator over $M$ heads satisfies:

and plugging this bound into the generalization bound of Theorem 9 gives the desired result. Basically, we replace the crude sum over heads in Equation (30) by this Massart-type control of the minimum operator, which yields a sharper dependence on $M$. Hence, we only need to prove Equation (32). That is done in the following steps.

Let $\mathcal{G}_{m}=\{(x,y)\mapsto-\log f_{m,y}(x):f_m\in\mathcal{F}\}$ be the loss function class for head $m$, where each function $g_m\in\mathcal{G}_{m}$ takes values in $[0,B]$ with $B=\log(1/\epsilon)$.

Let $g_m(z_i)=-\log f_{m,y}(x_i)$, where $z_i=(x_i,y_i)$. We analyze the empirical Rademacher process for a fixed sample $S$:

Pointwise minimum upper bound. For any given input $z_i$ and any choice of functions $(g_1,\ldots,g_M)$, the minimum can be written as:

Instead of summing over all $m$, we decouple the choice of the minimizing head index $m^*$ from the individual head function space. For any fixed sequence of functions $(g_1,\ldots,g_M)$, we have:

$\alpha$-cover discretization of the minima vector. To apply Massart’s Lemma over the finite $M$ choices of heads, we construct an empirical $L_2$-net $\mathcal{N}(\alpha,\mathcal{G}_m,S)$ for each function class $\mathcal{G}_m$ at scale $\alpha>0$. Hence, for every $g_m\in\mathcal{G}_m$, there exists a net element $\bar{g}_m\in\mathcal{N}(\alpha,\mathcal{G}_m,S)$ such that:

Then, using Cauchy–Schwarz, the discretization error introduced by replacing $g_{m_i^*}$ with its closest net element $\bar{g}_{m_i^*}$ is bounded by:

Decomposing into single head and Massart’s finite maximum. For any tuple of true functions $(g_1,\ldots,g_M)\in\mathcal{G}_1\times\cdots\times\mathcal{G}_M$, we find their corresponding net approximations $(\bar{g}_1,\ldots,\bar{g}_M)\in\mathcal{N}^M$. The empirical sum splits into:

Taking the supremum over all valid choices of tuples:

where the final term is at most $\alpha$, which gives us the following upper bound on the empirical Rademacher process:

Since $m_i^*\in[M]$, we decompose $\bar{g}_{m_i^*}(z_i)$ into an arbitrary reference head (say $m=1$) plus a residual vector in $\mathbb{R}^n$ representing the candidate selection among $M$ heads:

Then, taking expectation gives the following decomposition of the empirical Rademacher process:

where $v_m(i)=\bar{g}_m(z_i)-\bar{g}_1(z_i)\in[-B,B]$ as $\bar{g}_m$ and $\bar{g}_1$ are both in the loss function class $\mathcal{G}_m$ and hence bounded by $B=\log(1/\epsilon)$.

For $M$ vectors $\mathbf{v}_1,\ldots,\mathbf{v}_M\in\mathbb{R}^n$ with bounded norm $\lVert\mathbf{v}_m\rVert_2\leq\sqrt{n}B$, Massart’s Finite Class Lemma (Massart, 2000, Lemma 5.2) states that:

We apply Talagrand’s Contraction Lemma on the single-head term and use the fact that the loss function is $1/\epsilon$-Lipschitz. In addition, by taking the infimum over all valid cover radii $\alpha>0$ (or letting $\alpha=1/\sqrt{n}$), the residual discretization error $\alpha$ is absorbed into the standard covering-number bound of the individual head complexity $\mathcal{R}_n(\mathcal{F}_{1,y})$. This gives us the following upper bound on the empirical Rademacher process:

Finally, since the choice of head $m=1$ as reference was arbitrary, we take the maximum over all $m\in[M]$:

Substituting this refined bound for $\mathcal{R}_n(\mathcal{G}_{\mathrm{emax}})$ into the symmetrization argument of Section D.1 and combining with McDiarmid’s inequality yields the corollary.

Dataset Description

We use three category subsets of the Amazon 2023 review corpus (Hou et al., [8]) MUSICAL INSTRUMENTS, INDUSTRIAL AND SCIENTIFIC, and VIDEO GAMES, abbreviated Instrument, Scientific, and Game which span May 1996 to September 2023. Following prior work (Rajput et al., 2023; Zhou et al., 2020; Zheng et al., 2025), we apply the benchmark 5-core filtering (Amazon Reviews’23 Benchmark, [1]), which iteratively discards users and items with fewer than five interactions. We then group the interactions by user, order them chronologically, and truncate the histories to 50 items at both training and test time. The resulting statistics are reported in Table 5.

Compared Models

We detail here the baselines summarized in § 4. Numbers for the sequential and generative recommenders come from Zheng et al. (2025), who train them with RecBole (Zhao et al., 2021) under a common protocol and tune them by grid search. The multi-interest models are trained by us.

ID-based sequential recommenders.

1. Caser (Tang and Wang, 2018) applies horizontal and vertical convolutions to the embedded interaction sequence, capturing both positional and skip-behaviour patterns.

2. HGN (Ma et al., 2019) combines feature-level and instance-level gating to modulate item embeddings according to the user representation.

3. GRU4Rec [7] encodes the interaction sequence with gated recurrent units trained for session-based next-item prediction.

4. BERT4Rec (Sun et al., 2019) uses a bidirectional transformer encoder trained with a masked-item objective, so that each position is predicted from both past and future context.

5. SASRec [9] uses a unidirectional (causal) self-attention encoder and predicts the next item by inner product with the item embeddings; it is the closest single-hypothesis analogue of our backbone.

6. HSTU (Zhai et al., 2024) introduces hierarchical sequential transducers that consume actions and timestamps jointly, and is designed for scalability while remaining ID-based.

7. S3-Rec (Zhou et al., 2020) pre-trains the sequence encoder with self-supervised objectives built from item–attribute correlations, then fine-tunes it for next-item prediction.

Generative recommender. TIGER (Rajput et al., 2023) quantizes item text embeddings into semantic identifiers with an RQ-VAE and casts recommendation as autoregressive generation of the target identifier, retrieving items by beam search over the identifier space.

Multi-interest recommenders. These models represent a user by $M$ vectors instead of one, and are the closest existing analogue of our multi-hypothesis parameterization. We train them with the sampled-softmax objective and the readout rule of their reference implementations, and rank the catalogue by the maximum inner product over the $M$ interest vectors, which is the retrieval rule all of them adopt.

1. MIND (Li et al., 2019) extracts interests with a dynamic-routing capsule network over the history and trains the interest whose inner product with the target is largest.

2. ComiRec [4] comes in two variants: ComiRec-DR keeps the capsule routing of MIND with a bilinear mapping, while ComiRec-SA replaces it by a multi-head self-attentive pooling of the history.

3. SINE (Tan et al., 2021) selects a sparse subset of concepts from a large learned concept pool, forms one interest per selected concept, and aggregates them back into a single user vector used for retrieval.

4. Re4 (Zhang et al., 2022) augments ComiRec-SA with three backward-flow regularizers—contrasting interests against each other, realigning the attention with the retrieval criterion, and reconstructing the assigned items from each interest.

5. REMI (Xie et al., 2023) augments ComiRec-SA with interest-aware hard-negative mining in the sampled softmax and a variance-based regularizer on the item-to-interest routing matrix that prevents routing collapse.

Ablation on the Score-Loss Weight

This appendix measures how much of the performance of COMPOTE comes from the score loss of Equation (37), whose weight in the training objective is $\alpha$ (Equation (39)).

Protocol. We train COMPOTE on SCIENTIFIC with $M = 3$ for $\alpha\in\{0, 0.05, 0.1, 0.2, 0.3, 0.5, 0.7\}$, all other hyperparameters being fixed to the values of Section 4. Rankings use max-similarity aggregation (Equation (1)), which does not read $\hat{\gamma}$ at inference. The score loss can therefore only change the ranking through its gradient on the shared encoder; the oracle assignments it regresses are detached from the computation graph. We report N@5 at the best checkpoint.

The score loss helps. The best weight, $\alpha= 0.1$, reaches 1.91 N@5 against 1.82 without the score loss (Figure 4), and four of the six positive weights improve over $\alpha= 0$. We use $\alpha= 0.1$ in all other experiments.

It is not the main contributor. With $\alpha= 0$, COMPOTE already outperforms every single-hypothesis variant of Table 3 on SCIENTIFIC: 1.82 N@5 against 1.71 for MCT-SASRec, 1.64 for MCT-Router and 1.60 for MCT-EnsCE. The gain over single-hypothesis training is therefore obtained by the multiple-hypothesis objective alone. Moreover, the curve is not monotonic: $\alpha= 0.2$ and $\alpha= 0.5$ fall below $\alpha= 0$, so the effect of the score loss is of the same order as the variation across weights. The score loss acts as an auxiliary regularizer of the shared encoder rather than as the source of the improvement.

The Confidence-Score Stabilization

This appendix formalizes the regularization term mentioned at the end of § 3. It is an auxiliary supervised objective attached to the confidence-score head $\hat{\gamma}$ of Figure 1, which is trained to predict which hypothesis the target item belongs to.

Confidence-score head. Recall the architecture of Figure 1: the shared causal encoder maps the history to the hidden state $\mathbf{z} = \operatorname{Enc}(\mathbf{x}) \in\mathbb{R}^{d}$ at the most recent position, the $M$ hypothesis heads $h_1,\ldots,h_M$ map $\mathbf{z}$ to query representations $\mathbf{h}_m(\mathbf{x}) \in\mathbb{R}^{d}$, and the catalogue scores $s_{m,i}(\mathbf{x})$ of Equation (10) are turned into the per-hypothesis distributions $f_{m,\cdot}(\mathbf{x}) = \operatorname{softmax}_{i}\left(s_{m,\cdot}(\mathbf{x})\right) \in\Delta^{N-1}$. In parallel, an MLP taking the same $\mathbf{z}$ as input, followed by a coordinate-wise sigmoid, defines the confidence-score head

where $\hat{\gamma}_m(\mathbf{x})$ is read as the predicted probability that hypothesis $m$ is the one containing the target of query $\mathbf{x}$. Note that the $M$ outputs are independent sigmoids and not a softmax: $\hat{\gamma}(\mathbf{x})$ need not sum to one.

Supervision target: belonging to $\mathcal{Y}_m$. Following the tessellation of Theorem 7, the empirical cell of hypothesis $m$ on query $\mathbf{x}$ is the set of items for which $m$ is the most confident hypothesis,

so that $(\mathcal{Y}_m(\mathbf{x}))_{m\le M}$ is a partition of $\mathcal{Y}$ up to ties. The winning hypothesis of a training pair $(\mathbf{x},y)$ is the index of the cell that contains the target,

which is exactly the hypothesis realizing the min in $\ell^{\mathrm{WTA}}(\mathbf{y},f(\mathbf{x}))$. The regression target of $\hat{\gamma}$ is the corresponding membership vector

which is a one-hot vector, with its non-zero coordinate at $m^\star(\mathbf{x}, \mathbf{y})$.

Binary cross-entropy on $\hat{\gamma}$. The regularizer is the binary cross-entropy between the membership indicators equation (36) and the predicted confidences, summed over the $M$ coordinates,

which, the target being one-hot, can be written equivalently as

The cells equation (34), and hence the labels equation (36), depend on $f$: they are recomputed at every training step from the current hypotheses, and are detached from the computation graph, so that no gradient flows from $\ell^{\mathrm{score}}$ back to the heads $h_m$ through $m^\star$. The only gradient path of $\ell^{\mathrm{score}}$ is through $\hat{\gamma}$, i.e. through the confidence MLP and the shared encoder producing $\mathbf{z}$.

Full training objective. Weighting this term by $\alpha>0$, the objective minimized by COMPOTE is

with $\ell_\tau$ the annealed loss of Equation (3) – equivalently $\ell_\tau^{\mathrm{aMCL}}$ of Equation (4) by Proposition 2 and Corollary 3. We use $\alpha=0.1$ in all experiments; the sensitivity to $\alpha$ is reported in Section G.

Impact of the number of hypotheses $M$ on learning

In Theorem 4 in § 3, we have established that the generalization gap between the empirical WTA loss and the expected WTA loss has a sublinear dependence on the number of hypotheses $M$. We present here an empirical validation of this theoretical insight.

Keeping the experimental setup used for performance evaluation described in § 4, we vary the number of hypotheses $M$ from 1 to 12 and measure the ranking quality on SCIENTIFIC using N@5. Figure 5 shows that increasing $M$ from 1 to 3 improves ranking quality, which suggests that having multiple hypotheses is beneficial for capturing the ambiguity of the next-item distribution. However, beyond $M=3$, the performance plateaus, indicating that adding more hypotheses does not necessarily lead to better ranking quality. This empirical finding is consistent with the sublinear dependence on $M$ in Theorem 4, and provides practical guidance for selecting an appropriate number of hypotheses in real-world applications.

For those larger value of $M$, a phenomenon we have described in Proposition 6 in § 4 can also occur, which is the saturation of the max-similarity aggregation $\omega$. § 4. We have stated that this saturation can happen when at least two items have large probabilities $q_a^\star,q_b^\star\ge1/M$. This means that as $M$ increases, the probability of this saturation event increases, which can lead to a degradation of the ranking quality.

Collapse and Oracle Evidence

Proofs of sec:hypothesis-specialization

Proof of thm:closed-form

Proof of Theorem 7. The characterization of $\mathbf{p}^{\star}$ using $Q_m$ and the tessellation $\mathcal{Y}_m$ are a direct application of Theorem 7.

The only part remaining is to prove the tessellation $\mathcal{Y}_m$ is entropy-maximizing. Given a tessellation $\mathcal{C} = \{C_1,\ldots,C_m\}$ of $\mathcal{Y}$, define

The choice $C^\star=(\mathcal{Y}_m)_{m=1}^{M}$ coincides with the optimal predictor – i.e. $\mathbf{p}^{C^\star}=\mathbf{p}^\star$, leading to

Optimal Risk

The following corollary makes explicit the value of the optimal winner-takes-all risk.

Proof of Corollary 10. By Theorem 7, $\mathbf{p}^\star=\mathbf{p}^{C^\star}$ with $C^\star=(\mathcal{Y}_m)_{m=1}^{M}$, and the computation in the proof of Theorem 7 gives

Since $Q\in\Delta^{M-1}$, $H(Q)\le\log M$, with equality if and only if $Q$ is uniform.

The Loss Follows the $\log M$ Law

Theorem 7 also predicts how the loss should change with $M$. For a given query, the optimal winner-takes-all loss is the Bayes loss minus the entropy $H(Q(x))$ of the cell masses (Corollary 10). Exact querywise balance would therefore yield a $\log M$ reduction relative to the Bayes loss. Although the win frequencies of § 5.2 establish only marginal balance, empirically $\widehat{\mathcal{L}}^{\mathrm{WTA}}+\log M$ varies by less than 0.1 across $M\in\{3,4,5\}$ (Table 4), showing that the learned models approximately follow this scaling law, where $\widehat{\mathcal{L}}^{\mathrm{WTA}}=\mathbb{E}[\min_m-\log f_{m,y}(x)]$ is the test loss. Equivalently, going from $M=3$ to $M=5$ multiplies the geometric-mean probability that the winning head assigns to the target by $e^{0.61}\approx1.83$, close to and slightly above the ratio $5/3\approx1.67$ predicted under exact balance.

Latent Tiling Across $M$

This appendix details the protocol behind Table 4, reports additional diagnostics on the three COMPOTE checkpoints trained on GAME with $M\in\{3,4,5\}$, and checks that the partition also appears on SCIENTIFIC.

Protocol. Win frequencies, static sectors, and sector agreement use the full test set of 94,762 query–target pairs. In-cell mass and the winner-takes-all loss use the softmax $f_m(x)$ over the whole catalogue, with $\beta=0.07$, on the same full test set. The in-cell mass is $\sum_{y\in\mathcal{Y}_m(x)}f_{m,y}(x)$, averaged over heads and test pairs. The static direction $\hat{\mathbf{h}}_m$ of head $m$ is the renormalized average of its normalized outputs over the test set. Writing $\bar{\mathbf{e}}_i=\mathbf{e}_i/\lVert\mathbf{e}_i\rVert_2$ for the normalized embedding of item $i$, its sector is $\operatorname*{argmax}_m\langle\bar{\mathbf{e}}_i,\hat{\mathbf{h}}_m\rangle$. Sector agreement is the fraction of test targets whose sector is their winning head. Cross-head Jaccard, region loyalty, and single-head reach are computed from the top-10 lists on 4,000 test queries sampled uniformly. Among catalogue items retrieved at least once, an item is reached by a single head if it appears in the top-10 of exactly one head. Within-head overlap compares the top-10 list of a head between randomly paired queries from this sample.

Cosine and softmax winners agree. The oracle of Equation (11) selects heads by cosine similarity, whereas the cells of Theorem 7 are defined by probabilities, and each head carries its own softmax normalizer. The two definitions of the winning head agree on 98.9%, 99.4%, and 99.7% of test pairs for $M = 3, 4, 5$.

The tiling sharpens with $M$. The static directions are well separated for every $M$ (Figure 6). Cross-head top-10 Jaccard falls from 0.008 at $M = 3$ to 0.001 at $M = 5$, while region loyalty rises from 98.9% to 99.8% (Table 8). Theorem 7 predicts an exact partition for every $M$, so this trend describes how close training gets to the optimum rather than a property of the optimum itself.

$M$	Mean off-diag. cos($\widetilde{\mathbf{h}}$)	Cross-head top-10 Jaccard	Region loyalty
3	−0.09	0.008	98.9%
4	−0.17	0.003	99.4%
5	−0.04	0.001	99.8%

The same partition appears on SCIENTIFIC. We repeat the overlap diagnostics on 4,000 sampled test queries for the COMPOTE checkpoint trained on SCIENTIFIC with $M = 3$. The top-10 lists of two heads on the same query have a mean Jaccard overlap of 0.001, and 94.5% of the catalogue items retrieved at test time are reached by a single head only. The top-10 of a given head overlaps by 0.025 to 0.044 Jaccard between two different histories, so each head still adapts to the query. Figure 7 shows three test queries. A plain PCA of the normalized catalogue already reveals three arms, and the heads sit along distinct arms, with the target close to one of them.

Beyond the Theorem: a Static Tiling

Theorem 7 allows the cells to depend on the query. To test whether they do, we average the normalized outputs of each head over the test set and assign every catalogue item to the static sector of the direction it is most aligned with (protocol in § 21). The sector of the target predicts its winning head on 98.5% to 99.4% of test pairs (last column of Table 4), and more than 98.9% of each head’s top-10 items lie in its sector. Cell membership is thus almost a function of the item alone. COMPOTE learns a fixed tiling of the catalogue, and only the ranking inside each tile adapts to the history, as (P2) requires. A static tiling cannot balance every query: for a user whose likely next items all lie in one tile, $Q(\mathbf{x})$ is concentrated on a single head, and that head gets no boost from the partition. The balance reported in § 5.2 holds on average over queries, which is what win frequencies measure.