Differentiable Fast Top-K Selection for Large-Scale Recommendation

• URL: http://arxiv.org/abs/2510.11472v2
• Date: Tue, 04 Nov 2025 07:56:33 GMT
• Title: Differentiable Fast Top-K Selection for Large-Scale Recommendation
• Abstract summary: Cascade ranking is a widely adopted paradigm in large-scale information retrieval systems for Top-K item selection.<n>The Top-K operator is non-differentiable, hindering end-to-end training.<n>We propose DFTopK, a novel differentiable Top-K operator achieving optimal $O(n)$ time complexity.
• Score: 32.393027548279214
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cascade ranking is a widely adopted paradigm in large-scale information retrieval systems for Top-K item selection. However, the Top-K operator is non-differentiable, hindering end-to-end training. Existing methods include Learning-to-Rank approaches (e.g., LambdaLoss), which optimize ranking metrics like NDCG and suffer from objective misalignment, and differentiable sorting-based methods (e.g., ARF, LCRON), which relax permutation matrices for direct Top-K optimization but introduce gradient conflicts through matrix aggregation. A promising alternative is to directly construct a differentiable approximation of the Top-K selection operator, bypassing the use of soft permutation matrices. However, even state-of-the-art differentiable Top-K operator (e.g., LapSum) require $O(n \log n)$ complexity due to their dependence on sorting for solving the threshold. Thus, we propose DFTopK, a novel differentiable Top-K operator achieving optimal $O(n)$ time complexity. By relaxing normalization constraints, DFTopK admits a closed-form solution and avoids sorting. DFTopK also avoids the gradient conflicts inherent in differentiable sorting-based methods. We evaluate DFTopK on both the public benchmark RecFLow and an industrial system. Experimental results show that DFTopK significantly improves training efficiency while achieving superior performance, which enables us to scale up training samples more efficiently. In the online A/B test, DFTopK yielded a +1.77% revenue lift with the same computational budget compared to the baseline. To the best of our knowledge, this work is the first to introduce differentiable Top-K operators into recommendation systems and the first to achieve theoretically optimal linear-time complexity for Top-K selection. We have open-sourced our implementation to facilitate future research in both academia and industry.

Related papers

• Efficient Differentiable Approximation of Generalized Low-rank Regularization [64.73416824444328]
  Low-rank regularization (LRR) has been widely applied in various machine learning tasks.<n>In this paper, we propose an efficient differentiable approximation of LRR.
  arXiv  Detail & Related papers  (2025-05-21T11:49:17Z)
• LapSum - One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection [10.025684286258937]
  We present a novel technique for constructing differentiable order-type operations, including soft ranking, soft top-k selection, and soft permutations.<n>Our approach leverages an efficient closed-form formula for the inverse of the function LapSum, defined as the sum of Laplace distributions.
  arXiv  Detail & Related papers  (2025-03-08T14:53:36Z)
• Adaptive Neural Ranking Framework: Toward Maximized Business Goal for Cascade Ranking Systems [33.46891569350896]
  Cascade ranking is widely used for large-scale top-k selection problems in online advertising and recommendation systems. Previous works on learning-to-rank usually focus on letting the model learn the complete order or top-k order. We name this method as Adaptive Neural Ranking Framework (abbreviated as ARF)
  arXiv  Detail & Related papers  (2023-10-16T14:43:02Z)
• Optimizing Partial Area Under the Top-k Curve: Theory and Practice [151.5072746015253]
  We develop a novel metric named partial Area Under the top-k Curve (AUTKC) AUTKC has a better discrimination ability, and its Bayes optimal score function could give a correct top-K ranking with respect to the conditional probability. We present an empirical surrogate risk minimization framework to optimize the proposed metric.
  arXiv  Detail & Related papers  (2022-09-03T11:09:13Z)
• Probabilistic Permutation Graph Search: Black-Box Optimization for Fairness in Ranking [53.94413894017409]
  We present a novel way of representing permutation distributions, based on the notion of permutation graphs. Similar to PL, our distribution representation, called PPG, can be used for black-box optimization of fairness.
  arXiv  Detail & Related papers  (2022-04-28T20:38:34Z)
• PiRank: Learning To Rank via Differentiable Sorting [85.28916333414145]
  We propose PiRank, a new class of differentiable surrogates for ranking. We show that PiRank exactly recovers the desired metrics in the limit of zero temperature.
  arXiv  Detail & Related papers  (2020-12-12T05:07:36Z)
• A Differentiable Ranking Metric Using Relaxed Sorting Operation for Top-K Recommender Systems [1.2617078020344619]
  A recommender system generates personalized recommendations by computing the preference score of items, sorting the items according to the score, and filtering top-K items with high scores. While sorting and ranking items are integral for this recommendation procedure, it is nontrivial to incorporate them in the process of end-to-end model training. This incurs the inconsistency issue between existing learning objectives and ranking metrics of recommenders. We present DRM that mitigates the inconsistency and improves recommendation performance by employing the differentiable relaxation of ranking metrics.
  arXiv  Detail & Related papers  (2020-08-30T10:57:33Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)
• Fast Differentiable Sorting and Ranking [36.40586857569459]
  We propose the first differentiable sorting and ranking operators with $O(n log n)$ time and $O(n)$ space complexity. We achieve this feat by constructing differentiable operators as projections onto the permutahedron, the convex hull of permutations, and using a reduction to isotonic optimization.
  arXiv  Detail & Related papers  (2020-02-20T17:11:09Z)
• Differentiable Top-k Operator with Optimal Transport [135.36099648554054]
  The SOFT top-k operator approximates the output of the top-k operation as the solution of an Entropic Optimal Transport (EOT) problem. We apply the proposed operator to the k-nearest neighbors and beam search algorithms, and demonstrate improved performance.
  arXiv  Detail & Related papers  (2020-02-16T04:57:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.