Traditional ranking models operate under a closed-world assumption: they assume a fixed, finite universe of items. Whether ranking a set of movies, products, or political candidates, classical frameworks assume that every possible option is known beforehand.
However, real-world preference data rarely fits into a neat, finite box. New books are published every day, search engines must index an ever-evolving web, and generative language models can produce an infinite variety of text responses. When the choice set is open-ended or countably infinite, standard ranking models break down. They cannot assign probabilities to items they have never seen, nor can they quantify the likelihood that a completely new item will suddenly appear at the top of a preference list.
To solve this, a powerful research direction has emerged: extending classical ranking frameworks to handle unbounded choice sets. By leveraging Bayesian nonparametrics and infinite permutations, these models allow us to reason about open worlds where the pool of candidates is limitless.
The Problem with Finite Assumptions
As noted by Qinghua Liu et al. in Model-Based Learning from Preference Data, probabilistic models provide an essential foundation for preference learning because they quantify uncertainty and handle partial data. Yet, traditional choice models like the Plackett-Luce (PL) model require a fixed denominator.
In a standard PL model, each item $i$ has a latent scale parameter $\lambda_i > 0$ representing its quality or desirability. The probability of choosing item $i$ from a finite set $A$ is:
$$P(i \mid A) = \frac{\lambda_i}{\sum_{j \in A} \lambda_j}$$
If $A$ is infinite or unbounded, the denominator explodes, and the probability of selecting any individual item drops to zero unless we introduce a mechanism to distribute a finite amount of "desirability mass" across an infinite number of items.
Intuition: The Infinite Jar of Pebbles
To extend ranking to an infinite pool, we need a way to generate an infinite sequence of items where the total desirability remains finite. In Bayesian nonparametric models for ranked data., Francois Caron et al. solve this by modeling the items and their weights as random draws from a stochastic process—specifically, a completely random measure like a gamma process.
Imagine an infinite jar filled with pebbles. Each pebble represents an item, and the physical size of the pebble represents its latent desirability ($\lambda_i$). The mathematical properties of the gamma process ensure two crucial things:
- There are an infinite number of pebbles in the jar.
- If you add up the sizes of all the pebbles combined, the total mass is finite.
Because the total mass is finite, the jar contains a few very large pebbles, a moderate number of medium pebbles, and a massive, infinitely long tail of microscopic pebbles.
Size-Biased Permutations
How do we construct a top-$t$ ranking from this infinite jar? We reach in and pull out a pebble. The probability of grabbing any specific pebble is directly proportional to its size relative to the total mass of the jar.
Once we select a pebble, we set it aside and reach back into the jar to select the next one. The probability of choosing the second pebble is proportional to its size relative to the remaining mass in the jar.
This sequential selection mechanism is known as a size-biased permutation. As Francois Caron et al. demonstrate in Bayesian nonparametric Plackett-Luce models for the analysis of clustered ranked data, this process is the exact mathematical equivalent of the Plackett-Luce model generalized to an infinite item pool. The items that appear in our observed rankings are simply the largest pebbles drawn during this size-biased sampling process.
Infinite Pool (Gamma Process)
[ █ Big Item 1 ] [ ▆ Medium Item 2 ] [ ▄ Item 3 ] [ ▂ Item 4 ] ... [ . Infinite Tail ]
│
▼ Size-Biased Selection (Probability ∝ Mass)
Rank 1: [ █ Big Item 1 ]
│
▼ Remaining Mass Re-normalized
Rank 2: [ ▆ Medium Item 2 ]
Quantifying the Unseen
The true elegance of this framework lies in how it handles novelty. In a closed-world model, the probability of encountering a brand-new item is zero. But in the infinite jar model, after we have pulled out $t$ pebbles, there is still a sea of tiny, unobserved pebbles remaining in the jar.
Because the total mass of the jar is a known quantity, the authors show that we can calculate the exact remaining mass of all unobserved items combined. This remaining mass acts as a dedicated weight for "the unknown."
When predicting the next item in a sequence, the model can explicitly calculate a novelty probability—the chance that the next item will be a newcomer that has never appeared in historical data. This allows researchers to statistically compare different ranking systems to see how open or closed they are to novel entries.
Distance-Based Infinite Rankings
The Plackett-Luce model is not the only framework that can be generalized to infinite sets. While the PL model relies on utility and sequential choice, distance-based models like the Mallows model operate on the concept of permutations deviating from a central consensus.
In Estimation and clustering with infinite rankings, Le Bao introduces the Infinite Generalized Mallows (IGM) model. Instead of assigning latent masses to items, the IGM model defines a probability distribution over top-$t$ orderings of an infinite set. The core intuition is that there exists an ideal, infinite "central ordering" of all items. The probability of observing any specific partial ranking decreases exponentially based on its distance (often measured via Kendall's tau) from this central infinite sequence. This allows applications like search engines to model consensus across an infinite pool of documents while only ever observing the top few results.
Why This Matters for Modern AI
Shifting from closed-world to open-world preference modeling is becoming increasingly vital as machine learning interfaces with complex human environments. For example, in language model alignment, the space of possible textual responses is infinitely large and highly subjective.
While papers like Aligning Language Models with Human Preferences via a Bayesian Approach by Jiashuo Wang et al. focus on using Bayesian methods to capture annotator disagreement and uncertainty, the broader mathematical bridge provided by infinite ranking models offers a path forward for evaluating generative systems. When the choices available to an agent cannot be enumerated, treating preferences as size-biased samples from an infinite pool provides the exact mathematical flexibility required to model discovery, novelty, and the open-ended nature of human choice.
Key Foundational Work
Bayesian nonparametric models for ranked data. (2012) — contributed 7 concept elements to this direction.
Bayesian nonparametric Plackett-Luce models for the analysis of clustered ranked data (2012) — contributed 6 concept elements to this direction.
Estimation and Clustering with Infinite Rankings (2008) — contributed 4 concept elements to this direction.