In many core machine learning algorithms, we frequently need to sample from a discrete probability distribution over a large number of categories. Whether we are selecting a negative sample from a vocabulary of a billion words, choosing a latent topic for a token from thousands of possibilities, or searching for the nearest vector in a massive database, we face a fundamental computational bottleneck.
The naive way to sample from a discrete distribution with $N$ categories is to compute the cumulative distribution function (CDF) and perform a binary search. This requires $O(\log N)$ time. When $N$ is large and sampling must be performed billions of times, even logarithmic complexity becomes a severe drag on performance.
To overcome this, a powerful family of techniques has emerged across different domains of machine learning. By combining a classic data structure known as the alias method with Markov Chain Monte Carlo (MCMC) frameworks, researchers have unlocked constant-time ($O(1)$) discrete sampling. This means the time required to draw a sample can be completely decoupled from the size of the vocabulary, the number of topics, or the dimensionality of the search space.
The Core Intuition: Probability Stacking and the Alias Method
To understand why constant-time sampling is possible, we must first look at how the alias method transforms a discrete probability distribution.
Imagine a histogram representing a discrete probability mass function (PMF) over $N$ items. The total area under the histogram sums to 1, meaning the average probability per item is exactly $1/N$. If we scale the histogram so that the average height is 1, some items will have a height greater than 1 ("tall" items), and others will have a height less than 1 ("short" items).
The core insight of the alias method—often conceptualized as "probability stacking"—is that we can systematically cut off the excess probability from the tall items and pour it into the valleys of the short items. Because the average height is exactly 1, we can always arrange these pieces so that every single one of the $N$ columns has a total height of exactly 1. Crucially, we can do this such that each column contains parts of at most two items: a portion of its original item, and a portion of an "alias" item borrowed from a taller column.
Unscaled PMF: Scaled & Stacked (Alias Table):
█ [Item A] [Alias C] [Alias A]
█ █ [Item B] [Item C] [Item D]
█ █ █ █ Bin 1 Bin 2 Bin 3
A B C D (All bins have identical height = 1)
Once this uniform lookup structure is pre-computed, sampling becomes an incredibly simple two-step process:
- Pick a bin: Choose one of the $N$ columns uniformly at random. This takes $O(1)$ time.
- Flip a coin: Look inside that column and flip a biased coin to decide whether to return the column's original item or its designated alias item. This also takes $O(1)$ time.
As Jon Parker et al. demonstrate, this mechanism completely avoids the logarithmic complexity of binary search by creating a uniform lookup structure across the probability mass. The cost of drawing an individual sample is entirely independent of $N$.
The Dynamic Dilemma: Coupling Alias Tables with Metropolis-Hastings
If the alias method is so efficient, why isn't it used everywhere? The catch lies in the setup cost. Constructing an alias table requires $O(N)$ time. If the underlying probability distribution is static, this one-time cost is negligible. However, in many machine learning algorithms—such as Gibbs sampling for topic models or training energy-based models—the probabilities change after every single sample. Rebuilding an $O(N)$ table at every step would completely destroy the computational savings.
The breakthrough that made constant-time sampling practical for dynamic machine learning was combining the alias method with Metropolis-Hastings (MH) sampling.
Instead of building an alias table for the exact, rapidly changing target distribution $P(x)$, we build an alias table for a static or slowly changing proposal distribution $Q(x)$. Because $Q(x)$ is stable, we can afford the $O(N)$ setup cost to build its alias table. The hybrid algorithm then works as follows:
- Propose: Draw a candidate sample $x^*$ from $Q(x)$ in $O(1)$ time using the pre-computed alias table.
- Correct: Accept or reject the proposal with a Metropolis-Hastings acceptance probability $\alpha = \min\left(1, \frac{P(x^*)Q(x)}{P(x)Q(x^*)}\right)$.
If $Q(x)$ is a reasonably good approximation of $P(x)$, the acceptance rate will be high. This formulation allows the algorithm to maintain an amortized $O(1)$ sampling complexity per step, bypassing the need to re-normalize or rebuild the data structure when the target distribution shifts.
Application 1: Scaling Word Embeddings and Deep Networks
This hybrid architecture has proven vital for training models on massive vocabularies. For instance, when training Restricted Boltzmann Machines (RBMs) on large text corpora, calculating the exact gradient requires sampling from a discrete distribution over the entire vocabulary. George E. Dahl et al. integrated the alias method into an MH framework, using the marginal frequency of words as a static proposal distribution. This kept the proposal step efficient regardless of the number of categories, yielding training speeds independent of vocabulary size.
A similar bottleneck occurs in word embedding models like Word2Vec, where negative sampling requires drawing "noise" words from a large vocabulary. Stergios Stergiou et al. utilized the alias method within a distributed framework to draw negative samples in constant time. By decoupling the sampling cost from the dataset size, they scaled negative sampling to vocabularies exceeding one billion words.
Application 2: High-Dimensional Topic Modeling
Perhaps the most extensive application of this paradigm is in Latent Dirichlet Allocation (LDA) and its variants. Standard Gibbs samplers for LDA must sample a topic assignment for every single token in a corpus, a process that scales linearly with the total number of topics ($K$).
To break this bottleneck, researchers turned to alias-driven MH samplers:
- WarpLDA: Jianfei Chen et al. developed WarpLDA, which models the proposal distribution as a mixture of multinomials and applies alias sampling to achieve $O(1)$ per-token sampling complexity. This architecture was designed to optimize memory access patterns so that the sampling structures fit entirely within the L3 cache.
- Asynchronous and Parallel Systems: Rolf Jagerman et al. integrated an MH sampling strategy into an asynchronous parameter server framework (APS-LDA), ensuring that topic updates remained $O(1)$ per token even when scaling to web-scale datasets. Similarly, Måns Magnusson et al. and Jingwei Zhang et al. demonstrated that combining MH steps with alias tables allows parallel samplers to achieve massive speedups on corpora containing thousands of topics.
- Sublinear Scaling via Sparsity: When distributions are highly sparse, the combination can be optimized even further. Rashidul Islam et al. combined a Metropolis-Hastings Walker with alias tables to propose new topic assignments in time proportional only to the active components in a document rather than the total topic count. James R. Foulds applied an annealed version of this Walker mechanism to assign latent topics to word occurrences in sublinear time for mixed-membership word embeddings.
Jun Zhu et al. synthesized these advancements, highlighting how achieving constant time complexity per token by decoupling the sampling cost from the total number of topics or documents serves as a foundational pillar for scaling probabilistic machine learning.
Application 3: Beyond Text — Vector Search and Point Processes
The utility of constant-time discrete sampling extends far beyond text and topic modeling. It has also been adapted to solve fundamental problems in geometric retrieval and subset selection.
Maximum Inner Product Search (MIPS)
In large-scale retrieval, the goal of MIPS is to find the vector in a database that maximizes the inner product with a query vector. Traditional approaches rely on tree structures or locality-sensitive hashing, which can degrade in high dimensions.
Qin Ding et al. re-framed MIPS as a sampling problem. By treating the inner products as an unnormalized discrete distribution, they integrated alias tables directly into the search phase. This allowed them to draw database indices in constant time, making the retrieval phase entirely independent of the database size or the feature dimensionality.
Determinantal Point Processes (DPPs)
DPPs are probabilistic models used to select diverse subsets of items. Sampling from a DPP is notoriously expensive because it involves updating probabilities based on geometric interactions between items.
To accelerate this, Simon Barthelmé et al. designed a rejection sampling loop that integrates a pre-computed alias data structure for constant-time proposal generation. By minimizing the overhead of drawing candidate items, they shifted the primary computational cost away from proposal generation and onto the linear algebra required for the acceptance test, making DPPs practical for much larger datasets.
Alternative Structures for Constant-Time Updates
While the combination of the alias method and Metropolis-Hastings is highly popular, it is not the only way to achieve constant-time sampling. When the underlying parameters change too rapidly for an alias table to be useful, alternative data structures can be employed.
For example, in large-scale simulations of influence propagation across networks, the state of a node changes continuously, altering the transition probabilities of its neighbors. To handle this without global re-normalization, Vincent Yun Lou et al. partitioned transition rate parameters into fixed-length shards based on powers of two. This specialized data structure allows for both constant-time sampling and constant-time updates, avoiding the need to rebuild a centralized lookup table when individual nodes change state.
Summary
The transition from $O(\log N)$ or $O(N)$ sampling to $O(1)$ constant-time sampling represents a major milestone in scaling machine learning. By flattening arbitrary discrete distributions into uniform, two-element lookup tables, the alias method provides a mathematical shortcut to draw samples instantly. When paired with Metropolis-Hastings to handle dynamic updates, this paradigm allows modern architectures to process billions of documents, words, and vectors without getting bogged down by the size of the underlying space.
Key Foundational Work
Training Restricted Boltzmann Machines on Word Observations (2012) — contributed 1 concept elements to this direction.
Spoofing Large Probability Mass Functions to Improve Sampling Times and Reduce Memory Costs (2014) — contributed 1 concept elements to this direction.
Modeling Non-Progressive Phenomena for Influence Propagation (2014) — contributed 1 concept elements to this direction.