Abstract
Scaling Bayesian inference for models like Latent Dirichlet Allocation (LDA) often encounters a "parameter explosion" bottleneck, where the memory required to store count matrices exceeds the capacity of individual nodes in distributed systems. This paper introduces a sketching-based approach that utilizes Count-Min (CM) sketches combined with approximate counters to represent these massive matrices compactly. We provide a theoretical proof of convergence, showing that the equilibrium distribution of the sketched MCMC chain approaches the true posterior as sketch parameters are tuned. Experimental results on the English Wikipedia corpus demonstrate that our method reduces memory usage by up to 75% and significantly decreases communication overhead in distributed settings while maintaining model performance.
Introduction
In large-scale data analysis, Bayesian models such as Latent Dirichlet Allocation (LDA) and Hidden Markov Models (HMMs) are essential tools. However, as the vocabulary and number of topics grow, the associated parameter matrices—tracking frequencies of word-topic pairs—become prohibitively large. For instance, a model with 1 million words and 1,000 topics requires a billion-entry matrix. In distributed computing environments, synchronizing these massive matrices across nodes creates a significant communication bottleneck. While previous research has focused on reducing dataset size via coresets, this work addresses the memory and communication costs of the parameters themselves through probabilistic data structures known as sketches.
Methodology
The proposed method replaces standard count matrices with a hybrid sketching architecture:
- Count-Min Sketch (CM): A 2D matrix indexed by multiple hash functions. Each update increments several buckets, reducing space at the cost of potential overestimation due to collisions.
- Approximate Counters (Morris Counters): These counters store a probabilistic representation of integers on a logarithmic scale, allowing large counts to be tracked using only a few bits.
The authors explore two variants: Independent Counters, where each bucket in the CM sketch has its own random update logic, and Correlated Counters, which use a single random seed to update all buckets for a specific entry. The latter enables "conservative updates," which mitigate the overestimation bias inherent in CM sketches.
A key contribution of this work is the theoretical proof of convergence. Using Markov kernel theory, the authors demonstrate that the "sketched" MCMC chain remains stable and its equilibrium distribution converges to the exact model's posterior as the sketch size increases.
Experimental Evaluation
The approach was evaluated using the English Wikipedia corpus, consisting of 6.7 million articles and a vocabulary of 291,000 unique words. Model quality was measured using perplexity on a held-out set of 10,000 Reuters documents.
Statistical Convergence
The experiments confirmed that while sketched models may initially exhibit higher error, they eventually converge to the same performance level as the exact "plain" model.
Efficiency and Speedup
The combination of CM sketches and approximate counters (CM+A) proved highly efficient. By shrinking the parameter matrix, the authors drastically reduced the communication time between nodes in distributed MCMC.
As shown in the results, a CM+A configuration ($l=3, \log_2(w)=15$) achieved an iteration time of approximately 12.6 seconds, nearly matching the "plain" model's 12.1 seconds, while using only a fraction of the memory (98.3 vs 1164.0 $\times 10^5$ bytes). In contrast, using CM sketches without approximate counters for the same parameters resulted in a much slower iteration time of ~22.8 seconds.
Discussion and Conclusion
The "Aha" moment of this research lies in the realization that the biases of CM sketches (overestimation) and approximate counters (underestimation) do not cause the MCMC chain to diverge. Instead, the chain remains stable, and the reduced memory footprint translates directly into faster distributed execution.
However, there are trade-offs. Hashing introduces local CPU overhead, making the "plain" array faster on single machines with sufficient RAM. Additionally, the method introduces new hyperparameters (number of hashes, sketch width, counter base) that require tuning. Future work aims to extend this rigorous theoretical framework to other distributions beyond the Dirichlet-Categorical family, such as Gaussian or Poisson models.
Summary updated