Constant Time Sampling for Large Scale Probabilistic Models

This direction is merged into another direction: constant-time discrete sampling. Its last version stays readable and citable here.

Version 1 of 114 papers18 conceptsfrozen 2026-10-04

In many machine learning tasks, we model data as a choice among many discrete categories. Whether we are picking a word from a vocabulary of a million tokens, assigning a document to one of ten thousand topics, or recommending an item from a massive catalog, we eventually face a "linear bottleneck."

Standard methods for sampling from a discrete distribution with $K$ categories typically scale linearly—$O(K)$—or at best logarithmically—$O(\log K)$. As datasets grow to include billions of tokens and millions of categories, this dependency becomes a wall. A research direction across topic modeling, word embeddings, and generative models has emerged to break this wall, achieving constant-time $O(1)$ sampling that decouples the computational cost from the number of categories.

The Linear Bottleneck in Discrete Sampling

To understand the problem, imagine a standard Gibbs sampler for Latent Dirichlet Allocation (LDA). To update a single word's topic assignment, the algorithm must calculate the probability for every possible topic. If there are 10,000 topics, the sampler does 10,000 calculations for every single token in the corpus.

George E. Dahl and colleagues identified this same bottleneck in Restricted Boltzmann Machines (RBMs) trained on text. In Training Restricted Boltzmann Machines on Word Observations, they noted that the cost of Gibbs sampling is proportional to the vocabulary size. When the vocabulary hits hundreds of thousands of words, training grinds to a halt.

The Alias Method: $O(1)$ Intuition

The core mechanism used to break this bottleneck is the Alias Method.

The Alias Method is a clever way to represent a discrete distribution such that drawing a sample takes exactly two steps, regardless of how many categories exist. Imagine a histogram of probabilities. The Alias Method "levels" this histogram by moving probability mass from high-probability outcomes into the "valleys" of low-probability outcomes.

The result is a table where each column has a total height of 1 and contains at most two outcomes (the original outcome and its "alias"). To sample, you pick a column at random (Step 1) and then flip a biased coin to decide between the two outcomes in that column (Step 2). This process is $O(1)$.

Bridging Static Tables and Dynamic Models

The challenge is that the Alias Method requires a static distribution to build its table. In machine learning, distributions change constantly as the model learns. Rebuilding an alias table every time a parameter updates would be even slower than $O(K)$ sampling.

Researchers like Arnab Bhadury and Jun Zhu solved this by integrating the Alias Method into a Metropolis-Hastings (MH) framework. In Scaling up Dynamic Topic Models, they use a "proposal" distribution—a version of the distribution that is easy to sample from (using an alias table)—and then use an MH acceptance step to correct for the fact that the proposal is slightly "stale" or different from the true distribution.

This approach allows the sampler to:

  1. Build an alias table for a part of the distribution that changes slowly (like the global topic-word distribution).
  2. Draw samples in $O(1)$ time.
  3. Accept or reject those samples using a simple ratio.

Scaling to the Billion-Scale

This $O(1)$ trick has been applied across various domains to achieve massive speedups:

  • Topic Modeling: Jianfei Chen and the creators of WarpLDA reordered computations to ensure that the $O(1)$ sampling process stayed within the CPU's fast L3 cache. This allowed them to process 11 billion tokens per second. Similarly, Rolf Jagerman used $O(1)$ MH sampling in APS-LDA to scale topic models to web-scale datasets using asynchronous updates.
  • Word Embeddings: In Distributed Negative Sampling for Word Embeddings, Stergios Stergiou used the alias method to draw negative samples in constant time, enabling the training of Word2Vec on a billion-word vocabulary in just hours.
  • Recommendation Systems: Binbin Jin and others introduced SD-GAR, which uses alias-based sampling to bypass the linear complexity of iterating through an entire item catalog in GAN-based recommenders.

Beyond Exact Sampling

While the Alias Method provides a path to exact sampling, other researchers have explored "relaxed" versions of this idea. For instance, in Scalable Deep Unsupervised Clustering with Concrete GMVAEs, the authors use continuous relaxations to avoid marginalizing over all discrete states, effectively reducing complexity from linear to constant relative to the number of clusters.

In the work of Rashidul Islam and James R. Foulds on SparseSCVB0, they combine Metropolis-Hastings with sparse updates. By only proposing assignments from "active" components, they achieve sublinear scaling that allows for modeling 10,000 topics on the entirety of Wikipedia.

Conclusion

The shift from $O(K)$ to $O(1)$ sampling represents a fundamental change in how we view large-scale probabilistic models. By decoupling the cost of inference from the size of the vocabulary or the number of topics, these techniques—centered around the Alias Method and Metropolis-Hastings—have transformed "computationally inaccessible" models into tools that can be trained on the scale of the entire web. As Jun Zhu summarizes in Probabilistic Machine Learning, this efficiency is what allows modern Bayesian frameworks to integrate with deep learning and handle datasets at the billion-token scale.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_constant_time_sampling_for_large_scale_p_68ca50c5,
  title = {Constant Time Sampling for Large Scale Probabilistic Models},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constant-time-sampling-for-large-scale-probabilistic-models/rdr_68ca50c581a24a3f8921ab7f6aa3a81f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_constant_time_sampling_for_large_scale_p_68ca50c5_v1,
  title = {Constant Time Sampling for Large Scale Probabilistic Models},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constant-time-sampling-for-large-scale-probabilistic-models/rdr_68ca50c581a24a3f8921ab7f6aa3a81f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}