Discrete Conditional Diffusion for Reranking in Recommendation

Xiao Lin, Xiaokai Chen, Chenyang Wang, Hantao Shu, Linfeng Song, Biao Li, Peng Jiang

TL;DR

This paper introduces Discrete Conditional Diffusion Reranking (DCDR), a novel framework that adapts diffusion models for the challenging task of reranking items in recommendation systems. DCDR overcomes the discrete nature of item sequences and the need for user-centric generation by employing a discrete forward process and a conditional reverse process, leading to significant improvements in recommendation quality and successful real-world deployment.

What Problem Does This Paper Address?

Modern recommender systems often employ a multi-stage approach, where an initial ranking is refined by a "reranking" stage. This reranking stage is crucial because it considers the complex interplay between items in a list, aiming to present a sequence that maximizes user satisfaction. However, reranking faces several challenges:

  • Combinatorial Search Space: The number of possible item permutations is astronomically large, making exhaustive search infeasible.
  • Discrete Data: Unlike image or text generation, recommendation deals with discrete item IDs, which traditional diffusion models, primarily designed for continuous data, struggle with.
  • User Intent: The goal isn't just to generate any sequence, but one that aligns with user interests and is likely to elicit positive feedback (e.g., clicks, likes).
  • Efficiency: Real-world recommender systems need to be fast, and the iterative nature of diffusion models can be computationally expensive during inference.

Previous approaches often used an "evaluator-generator" paradigm, but struggled with the inherent complexities of discrete data and user-specific generation.

Methods

DCDR tackles these challenges by building upon the diffusion model framework but adapting it for discrete recommendation sequences:

  • Discrete Forward Process: Instead of adding continuous Gaussian noise, DCDR introduces discrete operations to corrupt item sequences. Two specific operations are proposed:
  • Permutation-level Operation: This treats the entire sequence as a permutation and adds noise by swapping items within the sequence. This is suitable when the number of items to be displayed is fixed.
  • Token-level Operation: This operates on individual item positions, adding noise by substituting an item at a specific position with another item. This is useful when the final list is a subset of a larger initial list. Crucially, these discrete operations are designed to have "tractable posteriors," meaning the probabilities of transitioning between states can be calculated efficiently, which is essential for training.

  • Conditional Reverse Process: To ensure the generated sequences align with user interests, DCDR incorporates a conditional reverse process. The denoising model is conditioned on "expected user responses" (e.g., predicted likes or watch completions). During training, real user feedback is used as the condition. During inference, a desired feedback profile (e.g., all positive) can be set.

  • Inference Optimizations: To address efficiency concerns, DCDR employs several strategies for deployment:
  • Starting Sequence: Instead of starting from pure noise, the inference begins with the initial ranked list from the previous stage, providing a better starting point.
  • Beam Search: To improve robustness, the model generates multiple candidate sequences at each step and keeps the top K, which are then evaluated.
  • Early Stopping: The inference process can terminate early if the generated sequence's likelihood of matching the expected conditions stops improving significantly, saving computation.
  • Sequence Evaluator: An additional model is used to score and select the best sequence from the candidates generated by the beam search.

Datasets

The paper uses two datasets for offline experiments:

  • Avito: A public dataset of user search logs containing impressions of multiple ads on a search page, with user feedback (clicks). The dataset has approximately 53 million lists.
  • VideoRerank: A dataset collected from Kuaishou, a short-video app, containing real item sequences displayed to users in complete sessions, with implicit feedback. This dataset includes over 100,000 users and over 1.2 million items.

Key Insights and Ideas

  • Diffusion for Discrete Data is Non-Trivial: The paper highlights that directly applying continuous diffusion models to discrete item sequences is suboptimal. The core innovation lies in designing discrete forward processes with tractable posteriors.
  • Conditioning is Key for Recommendation: Simply generating sequences isn't enough; they must cater to user preferences. Conditioning the reverse process on expected user feedback is a critical step towards this goal.
  • Real-World Deployment Requires Practical Optimizations: The success of DCDR in a large-scale video app underscores the importance of inference optimizations like starting with an initial ranking, beam search, and early stopping, which balance generation quality with computational cost.
  • Generality of the Framework: The DCDR framework is presented as flexible, allowing for various discrete operations and contextual features to be incorporated, making it adaptable to different recommendation scenarios.

Key Results

  • Offline Performance: DCDR consistently outperforms state-of-the-art reranking baselines (PRM, DLCM, SetRank, EGRerank) on both the Avito and VideoRerank datasets, achieving significant improvements in AUC and NDCG@3 metrics.
  • Comparison with DiffusionLM-R: DCDR-T and DCDR-P show superior performance compared to a modified DiffusionLM (DiffusionLM-R) adapted for discrete data, demonstrating the benefits of DCDR's discrete diffusion approach.
  • Online A/B Testing: In a real-world A/B test on Kuaishou, DCDR-P achieved significant relative improvements over the baseline PRM in key user engagement metrics: +0.341% in Views, +0.884% in Likes, +1.100% in Follows, +1.299% in Collects, and +1.358% in Downloads.
  • Efficiency: While diffusion models inherently have latency, the paper notes that DCDR's computation costs and latency are acceptable for real-time recommendation services.

Limitations and Future Work

  • Hyperparameter Tuning: The paper mentions that hyperparameter settings (beam size, noise scale, number of steps) are crucial and were tuned for optimal performance. Further research could explore more automated or adaptive hyperparameter selection.
  • Noise Schedule: The current work uses a simple noise schedule (constant $\beta_t$). The authors suggest exploring advanced noise schedule mechanisms for potentially further improvements.
  • Efficiency and Controllability: While DCDR is efficient enough for deployment, future work could focus on further enhancing inference speed and controllability of the generation process.
  • Generalizability of Discrete Operations: The paper proposes two discrete operations and notes that others can be incorporated. Future work could explore a wider range of discrete operations tailored to specific recommendation contexts.

Summary updated

Abstract

Reranking plays a crucial role in modern multi-stage recommender systems by rearranging the initial ranking list to model interplay between items. Considering the inherent challenges of reranking such as combinatorial searching space, some previous studies have adopted the evaluator-generator paradigm, with a generator producing feasible sequences and a evaluator selecting the best one based on estimated listwise utility. This paper explores the potential of diffusion models for generating high-quality sequences in reranking tasks, as the intrinsic nature of diffusion models is to improve generation quality by iterative refinements of generated samples. However, we argue that it is nontrivial to take diffusion models as the generator in the context of recommendation. Firstly, diffusion models primarily operate in continuous data space, differing from the discrete data space of item permutations. Secondly, the recommendation task is different from conventional generation tasks as the purpose of recommender systems is to fulfill user interests. Lastly, real-life recommender systems require efficiency, posing challenges for the inference of diffusion models.To overcome these challenges, we propose a novel Discrete Conditional Diffusion Reranking (DCDR) framework for recommendation. DCDR extends traditional diffusion models by introducing a discrete forward process with tractable posteriors, which adds noise to item sequences through step-wise discrete operations (e.g., swapping). Additionally, DCDR incorporates a conditional reverse process that generates item sequences conditioned on expected user responses. For efficient and robust inference, we propose several optimizations to enable the deployment of DCDR in real-life recommender systems. Extensive offline experiments conducted on public datasets demonstrate that DCDR outperforms state-of-the-art reranking methods. Furthermore, DCDR has been deployed in a real-world video app with over 300 million daily active users, significantly enhancing online recommendation quality.
BibTeX
@inproceedings{lin2024discrete,
  author = {Xiao Lin and Xiaokai Chen and Chenyang Wang and Hantao Shu and Linfeng Song and Biao Li and Peng Jiang},
  title = {{Discrete Conditional Diffusion for Reranking in Recommendation}},
  booktitle = {The Web Conference},
  year = {2024},
  url = {https://openreview.net/forum?id=Iw1OYZePoo},
}
Figure