PaperlayerView exact revision on arXiv

Source-linked AI summary

Compote: Collapse-Resistant Multiple Hypothesis Learning For Sequential Recommendation

Louis Castres Saint Martin, Clement Calauzenes, Alain Rakotomamonjy, Patrick Gallinari

arXiv:2610.37005v1cs.LGcs.IR

TL;DR

A single interaction history can admit several plausible next items, while standard sequential recommenders learn one conditional prediction. COMPOTE trains multiple hypotheses with an annealed objective, and across three Amazon Reviews 2023 benchmarks it outperforms ID-based, generative, and multi-interest baselines using item IDs alone.

  • Problem

    A single history can support plausible next items in unrelated catalogue regions, but standard sequential recommenders learn one conditional next-item model.

    Source: §1 · p. 1

  • Method

    COMPOTE adapts annealed multiple-choice learning to train M catalogue-distribution heads, transitioning from uniform updates toward winner-takes-all.

    Source: §1 · p. 2, §2 · p. 2

  • Results

    Across three Amazon Reviews 2023 benchmarks, COMPOTE outperforms ID-based, generative, and multi-interest baselines using item IDs alone.

    Source: §1 · p. 2

  • Takeaways & Limitations

    In the winner-takes-all limit, optimal hypotheses partition the conditional item distribution into maximum-entropy regions, while pooled scores preserve Bayes ranking up to saturation ties.

    Source: §1 · p. 2, §4 · p. 5

    The Bayes-ranking guarantee has a saturation exception when two items’ pooled scores both reach 1.

    Source: §4 · p. 5

Abstract

from arXiv · show

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.

1 INTRODUCTION

Sequential recommendation often faces several plausible next items across unrelated catalogue regions, while conventional models learn a single conditional prediction. COMPOTE applies annealed multiple-choice learning to train specialized hypotheses and reports gains over strong baselines across three benchmarks.

1 INTRODUCTION

  • A single interaction history can point to plausible next items in unrelated catalogue regions, so a single query vector may settle between modes rather than match one.Existing sequential models use one query representation, score vector, and ranked list.Source: §1 · p. 1
  • Prior multi-interest methods use winner-takes-all training with routing architectures, while diversity is commonly encouraged through architecture or added penalties.The introduction notes that winner-takes-all is rarely examined as an objective in its own right.Source: §1 · p. 2
  • COMPOTE adapts annealed multiple-choice learning to sequential recommendation, moving from uniform head updates at high temperatures toward winner-takes-all as temperature vanishes.A shared causal transformer feeds M prediction heads, each defining a catalogue distribution.Source: §1 · p. 2
  • Across three Amazon Reviews 2023 benchmarks, COMPOTE outperforms ID-based, generative, and multi-interest baselines using item IDs alone.Capacity-matched ablations attribute the gains to the annealed objective rather than model scaling, ensembling, or expert routing.Source: §1 · p. 2

2 PROBLEM STATEMENT AND ARCHITECTURE

The paper formalizes next-item recommendation as ranking catalogue items from a query history. COMPOTE uses a shared causal-transformer trunk and multiple independent heads to produce catalogue distributions and a final ranking.

2 PROBLEM STATEMENT AND ARCHITECTURE

  • The evaluation uses three Amazon 2023 review categories, with chronologically ordered user histories as queries and the next reviewed item as the target.Each category has approximately 25,000 items and 50,000–95,000 users.Source: §2 · p. 2
  • The model maps each query to M probability distributions over catalogue items, then combines their scores into one ranking.The learning setup treats query–item pairs as i.i.d. draws from an underlying distribution.Source: §2 · pp. 2–3
  • A shared causal-transformer trunk produces the latest-position representation, which feeds M independent hypothesis heads and a confidence-score head.The hypothesis heads each produce a vector, while the confidence head estimates which head is the best expert for the query.Source: Figure 1 · p. 3, §2 · p. 3

3 LEARNING PROBLEM

The learning objective softens winner-takes-all training with a temperature that is annealed toward zero. The analysis gives generalization guarantees and explains how the number of hypotheses and probability floors affect the bound.

3 LEARNING PROBLEM

  • Direct winner-takes-all training is challenging because its loss is discontinuous, motivating an annealed objective.The temperature parameter is annealed toward zero.Source: §3 · p. 3
  • At high temperatures, annealed multiple-choice learning updates heads uniformly, and as temperature vanishes it converges to pure winner-takes-all.The paper relates its objective to annealed MCL used in audio source separation.Source: §3 · p. 3
  • For inference, the paper presents its hypothesis aggregation as a principled choice not addressed by the earlier annealed-MCL literature.The cited literature does not address how to recombine hypotheses at inference.Source: §3 · p. 3
  • The paper identifies its loss with annealed MCL and states that the two learning paradigms have matching gradients in practice.The cited MCL formulation backpropagates through the head log-probability but not through the soft assignment weights.Source: §3 · pp. 3–4
  • Theorem 4 bounds the gap between empirical and expected winner-takes-all loss using individual-head Rademacher complexities and the number of hypotheses.The bound assumes all head probabilities are at least ϵ > 0.Source: §3 · p. 4
  • The generalization gap scales with head complexities divided by the minimum predicted probability ϵ, so smaller ϵ makes the bound looser.Label smoothing, temperature scaling, or KL regularization can enforce a probability lower bound and tighten the guarantees.Source: §3 · p. 4
  • The number of hypotheses affects the bound through an O(√(ln M/n)) term rather than a linear increase in M.The paper states that additional hypotheses need not proportionally increase overfitting risk when individual-head complexities are controlled.Source: §3 · p. 4

4 COMPOTE LEADS TO OPTIMAL RANKING

COMPOTE's max-pooling aggregation preserves Bayes-optimal ranking except for a specified saturation tie, and its max-similarity inference rule avoids the per-head catalogue normalizer without measurable ranking loss. Across three Amazon 2023 subsets, it leads most reported benchmark columns and outperforms matched-capacity single-head, ensemble, and routing variants.

4 COMPOTE LEADS TO OPTIMAL RANKING

  • At an expected winner-takes-all optimum, pooled scores rank items in the Bayes-predictor order except when both scores saturate at 1.The stated saturation case can occur when two items each have probability at least 1/M; the authors advocate using M values that are not too large.Source: §4 · p. 5
  • The evaluation uses three Amazon 2023 subsets, 5-core filtering, histories truncated to 50 items, and leave-one-out splits, ranking the entire catalogue with H@K and N@K.The reported cutoffs are K ∈ {5, 10}; with one relevant test item, H@K coincides with Recall@K.Source: §4 · p. 5
  • COMPOTE is best in 11 of 12 Table 1 columns; against TIGER, it improves N@5 by 9.7% on Scientific and 9.6% on Game, and ties on Instrument (2.44 →2.45).TIGER uses semantic identifiers derived from item text and beam search, while COMPOTE uses item identifiers alone and ranks the catalogue in a single forward pass.Source: Table 1 · p. 6, §4 · p. 6

4.1 FAST RETRIEVAL FOR COMPOTE

  • Using max-similarity scores instead of per-head softmax scores yields no measurable ranking-accuracy loss, and removes the need for the catalogue normalizer at inference.For the same trained Game model with M = 3 heads, Table 2 compares aggregators by whether ranking requires the per-head partition function.Source: §4.1 · p. 6, Table 2 · p. 7

4.2 ABLATIONS: WHERE DO THE GAINS COME FROM?

  • Under matched parameter budgets, COMPOTE outperforms the single-hypothesis, ensemble, and routing variants on every dataset and metric.The cited N@5 comparisons include 2.45 versus 2.34 on Instrument, 1.92 versus 1.71 on Scientific, and 4.01 versus 3.78 on Game for COMPOTE versus MCT-SASRec; MCT-Router also trails on all three datasets.Source: §4.2 · p. 7, Table 3 · p. 7

5 HYPOTHESIS SPECIALIZATION

COMPOTE produces complementary, non-collapsed hypotheses that partition the catalogue. The learned partition is query-dependent and balances next-item probability mass across heads.

5.1 COLLAPSE AND ORACLE EVIDENCE

  • MCT-EnsCE and MCT-Router reach S = 1.00 on all three datasets, while COMPOTE obtains 0.64, 0.61, and 0.58 on INSTRUMENT, SCIENTIFIC, and GAME.The paper concludes that architectural multiplicity or learned routing alone does not prevent collapse.Source: §5.1 · pp. 7–8
  • Oracle head selection raises N@5 by 53% (2.45 →3.75) on INSTRUMENT, 83% (1.92 →3.52) on SCIENTIFIC, and 94% (4.01 →7.78) on GAME.The oracle is not deployable, but its gains show that COMPOTE's distinct heads contain complementary ranking signal.Source: §5.1 · p. 8

5.2 WHAT EACH HYPOTHESIS LEARNS

  • The optimal hypotheses partition the catalogue into disjoint cells, rank within each cell as the Bayes predictor does, and maximize the entropy of cell masses.The partition splits conditional item mass as evenly as the catalogue allows.Source: §5.2 · p. 8
  • Each head retains 91.5%–93.7% of its softmax mass in its own cell, while same-query top-10 lists average 0.008 Jaccard overlap.At M = 5, overlap reaches 0.001 and 98.6% of retrieved catalogue items are reached by only one head; Figure 2 depicts the three-sector partition.Source: §5.2 · p. 8, Figure 2 · p. 9
  • A head's ranking remains query-dependent: its top-10 overlap across histories is only 0.017–0.026 Jaccard, and it wins 98.9%–99.7% of test pairs selected by the cosine oracle.At the optimum, the target belongs to one cell and competes there against items in that cell.Source: §5.2 · p. 9
  • Head win frequencies stay within 1.6 points of 1/M, with normalized entropy above 0.999, even though heads own only 15.5%–25.3% of items at M = 5.Each head wins close to 20% of targets at M = 5, reflecting balance in probability mass rather than item counts.Source: §5.2 · p. 9

6 DISCUSSION AND CONCLUSION

COMPOTE uses annealed multiple-hypothesis learning to produce complementary rankings, prevent head collapse, preserve ranking quality, and improve performance across three benchmarks. The paper identifies rare-item recommendations and the geometry of its learned catalogue tiling as directions for future work.

6 DISCUSSION AND CONCLUSION

  • COMPOTE produces complementary rankings, prevents head collapse, preserves ranking quality, and improves performance across three benchmarks.The authors leave combining COMPOTE with semantic identifiers for future work, noting that this could improve recommendations for rare items.Source: §6 · p. 9
  • The authors leave unexplained why theoretically query-dependent cells form an almost static catalogue tiling and how that structure relates to item-embedding geometry.They also identify semantic identifiers as a possible future route to better recommendations for rare items.Source: §6 · p. 9
  • Generative AI tools assisted with manuscript polishing, portions of experimental code, and drafts of parts of the generalization-bound proofs, which the authors verified and corrected.Source: AI USE STATEMENT · p. 10

B.1 PROOF OF PROPOSITION 5

  • As τ approaches 0, the annealed loss converges to the winner-takes-all loss.Source: §B.1 · p. 13

B.2 PROOF OF PROPOSITION 6

The proof characterizes when max-similarity aggregation preserves the Bayes ranking, with equality possible only at saturation. The per-head normalizers are nearly alike in the measured checkpoint, and the generalization proof uses Rademacher complexity and concentration.

B.2 PROOF OF PROPOSITION 6

  • At an optimal prediction, ωa(p⋆) > ωb(p⋆), unless both scores equal 1, the saturation case.The proof establishes the weak ordering and then shows equality forces the common value to be 1.Source: §B.2 · p. 14

C PER-HEAD NORMALIZER

  • Across 94,762 GAME queries, the three per-head log-normalizer distributions nearly overlap, with cross-head standard deviation 0.13 versus mean 13.7.The small cross-head range limits ranking changes from omitting normalizers; Table 2 reports no measurable loss.Source: C PER-HEAD NORMALIZER · p. 15, Figure 3 · p. 15

D.1 PROOF OF THEOREM 9

  • The log-loss generalization proof bounds the minimum-over-head complexity using Rademacher complexity, then combines it with concentration.The refined bound has milder dependence on M than the initial bound.Source: §D.1 · pp. 15, 17

D.2 PROOF OF THEOREM 4

Theorem 4 refines the log-loss generalization bound by controlling the minimum over M heads rather than summing head complexities. The experiments use preprocessed Amazon review categories and compare COMPOTE with sequential, generative, and multi-interest recommenders.

D.2 PROOF OF THEOREM 4

  • Theorem 4 sharpens the generalization bound’s dependence on M by replacing a crude sum over heads with control of the minimum operator.The proof combines single-head complexity with a finite-maximum term involving M.Source: §D.2 · p. 17

E DATASET DESCRIPTION

  • The benchmarks use five-core-filtered Amazon 2023 interactions, chronologically ordered and truncated to 50-item histories for training and testing.The categories are Musical Instruments, Industrial and Scientific, and Video Games.Source: E DATASET DESCRIPTION · p. 19

F COMPARED MODELS

  • The comparison covers ID-based sequential, generative, and multi-interest recommenders, with multi-interest models trained using their reference readouts and max-inner-product retrieval.Sequential and generative baseline numbers come from Zheng et al. (2025); the multi-interest models are trained by the authors.Source: F COMPARED MODELS · pp. 19–20

G ABLATION ON THE SCORE-LOSS WEIGHT

The score loss improves the best reported setting but is not the source of COMPOTE’s advantage over single-hypothesis variants. The appendix also describes its confidence-score supervision and reports that ranking quality plateaus beyond three hypotheses, with saturation a possible concern at larger M.

G ABLATION ON THE SCORE-LOSS WEIGHT

H THE CONFIDENCE-SCORE STABILIZATION

  • The confidence head predicts which hypothesis contains the target, using detached, recomputed cell assignments as one-hot supervision.Its binary cross-entropy gradients flow through the confidence head and shared encoder, not through the hypothesis heads.Source: H THE CONFIDENCE-SCORE STABILIZATION · pp. 21–22

I IMPACT OF THE NUMBER OF HYPOTHESES M ON LEARNING

  • On SCIENTIFIC, ranking quality improves from M = 1 to M = 3 and then plateaus as M increases to 12.The passage says larger M can also increase the chance of max-similarity saturation, which can degrade ranking quality.Source: I IMPACT OF THE NUMBER OF HYPOTHESES M… · p. 22

K.1 PROOF OF THEOREM 7

The appendix relates optimal winner-takes-all prediction to a partition of the item space and gives its risk in terms of partition-mass entropy. Empirically, the test loss approximately follows the predicted log M scaling for M from 3 to 5.

K.1 PROOF OF THEOREM 7

  • The optimal winner-takes-all risk is attained by minimizing risk over M-way tessellations of the item space.The appendix identifies the optimal tessellation’s risk as the minimum across such partitions.Source: §K.1 · pp. 23–24

K.2 OPTIMAL RISK

  • The optimal risk equals H(q⋆) − H(Q) and is at least H(q⋆) − log M, with equality when every cell mass is 1/M.Q is the vector of cell masses.Source: §K.2 · p. 24

K.3 THE LOSS FOLLOWS THE log M LAW

  • For M = 3, 4, and 5, test loss plus log M varies by less than 0.1, approximately following the predicted scaling law.From M = 3 to M = 5, the winning head’s geometric-mean target probability is multiplied by about 1.83, versus 1.67 predicted under exact balance.Source: §K.3 · p. 24

L LATENT TILING ACROSS M

Across GAME checkpoints, increasing the number of hypotheses sharpens catalogue tiling, while head selection by cosine similarity closely matches selection by softmax probability. The diagnostics also find low overlap between heads on SCIENTIFIC.

L LATENT TILING ACROSS M

  • The diagnostics use all 94,762 test pairs for win frequencies, static sectors, sector agreement, in-cell mass, and winner-takes-all loss; top-10 overlap measures use 4,000 sampled queries.In-cell mass and winner-takes-all loss use softmax probabilities with β = 0.07.Source: L LATENT TILING ACROSS M · p. 24
  • 0.008 to 0.001 cross-head top-10 Jaccard and 98.9% to 99.8% region loyalty as M rises from 3 to 5 show sharper tiling on GAME.These trends describe how closely training approaches the theorem’s exact partition, not a change in the optimum itself.Source: Table 8 · p. 25, L LATENT TILING ACROSS M · p. 25, Figure 6 · p. 25
  • 98.9%, 99.4%, and 99.7% of test pairs select the same winning head under cosine similarity and softmax probability for M = 3, 4, and 5.The oracle uses cosine similarity, while the theorem’s cells use probabilities with head-specific softmax normalizers.Source: L LATENT TILING ACROSS M · p. 25
  • On SCIENTIFIC with M = 3, heads have mean same-query top-10 Jaccard overlap of 0.001, while each head’s lists overlap 0.025–0.044 across histories.94.5% of retrieved catalogue items are reached by one head only, while the across-history overlap indicates that heads still adapt to queries.Source: L LATENT TILING ACROSS M · p. 25

M BEYOND THE THEOREM: A STATIC TILING

Static sectors nearly predict each target’s winning head, and most top-10 items remain within their head’s sector. This fixed catalogue tiling leaves ranking within each tile to adapt to the history.

M BEYOND THE THEOREM: A STATIC TILING

  • 98.5% to 99.4% of test targets’ static sectors predict their winning head, and more than 98.9% of each head’s top-10 items lie in its sector.The learned tiling is fixed across the catalogue; ranking within each tile adapts to the history.Source: M BEYOND THE THEOREM: A STATIC TILING · p. 25
  • For a user whose likely next items all lie in one tile, Q(x) concentrates on one head, which then gets no boost from the partition; win-frequency balance holds only on average over queries.Figure 7 depicts normalized catalogue items, target next items, and head query embeddings for three SCIENTIFIC test sequences.Source: M BEYOND THE THEOREM: A STATIC TILING · pp. 25–26, Figure 7 · p. 26
Loading 2610.37005v1…