Compote: Collapse-Resistant Multiple Hypothesis Learning For Sequential Recommendation

Louis Castres Saint Martin, Clement Calauzenes, Alain Rakotomamonjy, Patrick GallinariarXiv 2026 · arXiv

In the world of sequential recommendation, predicting the "next item" is a bit like predicting the next word in a sentence—it’s inherently ambiguous. If you just bought a guitar, you might next look for strings, a case, or maybe a completely unrelated video game you've been eyeing. Standard recommendation models try to squash all these diverse possibilities into a single "average" prediction vector. The result? A "jack of all trades, master of none" model that often misses the mark.

A new paper from researchers at Criteo AI Lab and Sorbonne Université introduces COMPOTE, a method that embraces this ambiguity by learning multiple specialized "hypotheses" for what a user might want next.

TL;DR

COMPOTE is a multi-hypothesis transformer that uses an annealed "winner-takes-all" objective to force different prediction heads to specialize in distinct regions of a product catalog. It outperforms state-of-the-art generative and multi-interest models on major benchmarks while remaining efficient enough for large-scale deployment.

What Problem Does This Paper Address?

Most sequential recommenders (like SASRec or BERT4Rec) represent a user's history as a single vector. When a user's history suggests multiple plausible futures—a phenomenon called multimodality—these models typically settle for a point in the middle of those possibilities. This "conflation of intent" leads to blurry recommendations.

While "multi-interest" models exist, they often suffer from head collapse, where all the different "interest" vectors eventually converge to represent the same thing. COMPOTE aims to solve this by ensuring that multiple hypotheses remain distinct and cover the entire catalog effectively.

Methods

The core of COMPOTE is a shared transformer backbone that feeds into $M$ independent hypothesis heads.

The COMPOTE architecture: a shared transformer trunk followed by multiple specialized prediction heads.

The "secret sauce" is the training objective: Annealed Multiple-Choice Learning (MCL).

  1. Early Training: The model uses a "soft" assignment where all heads are supervised by every interaction. This helps all heads get a good start.
  2. Late Training: The supervision "anneals" toward a winner-takes-all (WTA) strategy. Only the head that is currently most accurate for a specific user history gets updated for that example.

This competition forces heads to specialize. If Head A is already good at predicting "Musical Instruments," it will "win" those examples and become even more specialized, leaving "Video Games" to Head B.

For deployment, the authors introduce a max-similarity rule. Instead of calculating expensive softmaxes over the whole catalog for every head, they simply take the maximum cosine similarity across all heads. This makes COMPOTE compatible with standard, high-speed vector databases.

Datasets

The authors evaluated COMPOTE on three categories from the Amazon Reviews 2023 corpus:

  • Musical Instruments (~25k items, 57k users)
  • Industrial and Scientific (~26k items, 51k users)
  • Video Games (~26k items, 95k users)

These datasets are particularly challenging because they are sparse and contain many plausible "next items" for any given history.

Key Insights and Ideas

  • Head Specialization is Emergent: You don't need complex routing architectures or explicit diversity penalties. The annealed WTA loss naturally "tiles" the product catalog, with each head becoming an expert for a specific sector.
  • The "Log M" Law: Theoretically and empirically, the authors show that adding more hypotheses ($M$) doesn't lead to massive overfitting. The generalization error only grows logarithmically with $M$, meaning you can use multiple heads to capture diversity without a huge penalty in reliability.
  • Efficiency without Sacrifice: The "max-similarity" inference rule (shown in Figure 4) performs just as well as the theoretically optimal "max-softmax" rule but bypasses the need for catalog-wide normalization. This is a huge win for engineering teams.

Key Results

COMPOTE consistently outperformed strong baselines, including ID-based models (SASRec, HSTU), generative models (TIGER), and existing multi-interest models (MIND, ComiRec).

Main performance results across three Amazon datasets. COMPOTE takes the lead in almost every metric.

In their ablation studies, the researchers proved that COMPOTE's gains aren't just from having more parameters. A single-head model with the same number of parameters (MCT-SASRec) still performed worse than the multi-hypothesis COMPOTE.

Table 3: Ablation over the prediction head and the training objective (%). Variants share the same encoder backbone and parameter budget, and rank items with max-similarity aggregation (Equa- tion (10)): MCT-SASRec is a single-hypothesis iso-parameter head, MCT-EnsCE uses an ensemble cross-entropy objective, and MCT-Router routes queries to a single expert. Bold: best.

Limitations and Future Work

While COMPOTE is highly effective using item IDs alone, it doesn't currently incorporate item content (like text or images). The authors suggest that combining COMPOTE's multi-hypothesis approach with semantic identifiers (like those used in generative models) could further improve recommendations, especially for rare "long-tail" items.

Additionally, while the model effectively "tiles" the catalog, these tiles are somewhat static. Future research could explore how to make this tiling more dynamic and responsive to shifting global trends.

Summary updated

Abstract

Next-item prediction is inherently ambiguous: a single interaction history often admits multiple plausible continuations across distinct catalogue regions. Standard sequential recommenders compress these alternatives into a single prediction, conflating user intents. We introduce COllapse-resistant Multiple hyPOThesis lEarning (COMPOTE), a multi-hypothesis transformer trained with an annealed objective that transitions from uniform supervision to a winner-takes-all assignment. This mechanism forces hypotheses to specialize into distinct catalogue regions, while inference relies on an efficient, normalizer-free max-similarity rule. Theoretically, we show that in the population case, the optimal solutions partition the conditional next-item distribution according to a max-entropy quantization principle, while pooled scores preserve the Bayes-optimal ranking. We also prove a generalization bound scaling logarithmically with the number of hypotheses. Across three Amazon Reviews 2023 benchmarks, COMPOTE outperforms strong ID-based, generative, and multi-interest baselines using item IDs alone. Matched-capacity ablations confirm that performance gains stem directly from the annealed objective, preventing the head collapse observed in conventional multi-head architectures, rather than added capacity, ensembling, or routing.
BibTeX
@misc{martin2026compote,
  author = {Louis Castres Saint Martin and Clement Calauzenes and Alain Rakotomamonjy and Patrick Gallinari},
  title = {{Compote: Collapse-Resistant Multiple Hypothesis Learning For Sequential Recommendation}},
  year = {2026},
  eprint = {2610.37005},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.37005},
}
Figure