To understand why ranking is computationally difficult, consider the difference between classification and ranking. In a standard classification problem with $n$ classes, a model outputs a probability distribution over $n$ discrete choices. The size of this output space grows linearly with $n$.
In contrast, a ranking task requires ordering a set of $n$ items. The number of possible total orderings is $n!$ ($n$ factorial). If $n = 10$, there are over 3.6 million possible permutations. If $n = 20$, the number of permutations exceeds $2 \times 10^{18}$. This combinatorial explosion means that any naive attempt to model a probability distribution over full rankings, or to find an optimal ranking by evaluating every possibility, is fundamentally impossible.
As Lebanon et al. note, this factorial growth makes it computationally intractable to calculate full ranking distributions as the item universe expands. The core challenge across this research direction is finding mathematical and algorithmic mechanisms to bypass this $n!$ bottleneck while preserving the rich, listwise interactions that define human preferences.
Where the Explosion Hurts Most
The combinatorial explosion manifests as a severe bottleneck in three main areas of machine learning:
1. Loss Optimization and Evaluation Metrics
Information retrieval metrics like Normalized Discounted Cumulative Gain (NDCG) and mean Average Precision (mAP) depend on the exact positions of items. Because these metrics are discrete and non-differentiable, directly optimizing them requires computing expectations over all possible permutations. As Valizadegan et al. demonstrate, calculating the exact expected NDCG becomes intractable for practical list sizes because it requires summing over a factorial number of orderings. Similarly, when evaluating vector embeddings, resolving numerical ties requires averaging over all valid permutations of tied items, a cost that Nicolaou et al. show can quickly become prohibitive.
2. Probabilistic Inference and Partition Functions
Probabilistic ranking models define the likelihood of a ranking based on its distance from a central consensus ranking. To make this a valid probability distribution, the model must divide by a normalization constant (the partition function) that sums the distances over all $n!$ permutations. Qin et al. point out that this makes exact inference impossible for large-scale meta-search or recommendation datasets without efficient decomposition methods.
3. Off-Policy Evaluation (OPE)
In recommendation systems, we often want to evaluate a new ranking policy using historical logs generated by an older policy. This is typically done via Inverse Propensity Scoring (IPS). However, because the action space consists of $n!$ permutations, the probability that the historical policy and the new policy chose the exact same sequence is incredibly small. Kiyohara et al. and Kiyohara et al. explain that this combinatorial explosion causes extreme data sparsity and massive variance, rendering standard OPE techniques unreliable without structural assumptions about user behavior.
Strategies for Taming the Complexity
Researchers have developed several distinct paradigms to circumvent the factorial state space.
Stochastic Sampling and Prefix Approximations
Instead of computing probabilities over the entire permutation space, a common strategy is to focus only on the top-$k$ items. In many real-world applications, users only look at the first few results anyway. Luo et al. address this by sampling a small subset of permutation classes rather than computing the full distribution, making higher-order Top-$k$ models computationally feasible. Similarly, Dasgupta et al. develop mathematically tractable generalizations of the Mallows model specifically for top-$k$ prefix lists, providing provable algorithmic guarantees for sampling and reconstruction without scaling with the entire item universe.
Geometric and Continuous Relaxations
Another elegant approach maps the discrete, combinatorial space of permutations into a continuous domain where gradients can flow. Ailon leverages geometric abstractions like the permutahedron—a polytope whose vertices correspond to permutations—to transform the discrete online ranking problem into a continuous optimization problem, reducing per-step computation time to near-linear.
Taking this further into deep learning, Grover introduces a continuous relaxation of the sorting operator. By smoothing the discrete sorting step, gradients can be backpropagated directly through listwise ranking losses, allowing models to scale efficiently to large item lists.
Problem Decomposition: Pairwise and Setwise Reductions
If modeling the entire permutation is too expensive, the problem can be broken down into smaller, local interactions. While traditional pairwise approaches compare items in isolation, Wang et al. propose a "setwise" approach. By assuming a user prefers a single item over an entire unobserved set of items, their framework avoids both the logical inconsistencies of pairwise models and the factorial bottlenecks of full listwise models.
Conclusion
The shift from treating ranking as a massive, discrete search space to a structured, relaxed, or decomposed problem has allowed learning-to-rank algorithms to scale to millions of items. By understanding that the $n!$ complexity can be bypassed through smart geometric relaxations, top-$k$ approximations, and structural decompositions, modern systems can optimize for global list quality in near-linear time.