Source-linked AI summary
LightLDA: Big Topic Models on Modest Compute Clusters
Jinhui Yuan, Fei Gao, Qirong Ho, Wei Dai, Jinliang Wei, Xun Zheng, Eric P. Xing, Tie-Yan Liu, Wei-Ying Ma
TL;DR
LightLDA addresses the challenge of training web-scale topic models whose data and parameter sizes exceed the practical capacity of modest clusters. It combines an O(1) Metropolis-Hastings sampler with structure-aware model and data parallelism, hybrid storage, and asynchronous execution. The system trains a 1-trillion-parameter model on 200 billion tokens using 8 machines, with runtime falling from 180 to 60 hours on 24 machines.
Problem
Web-scale topic modeling requires massive data and model sizes, while prior systems generally relied on industrial-scale clusters and faced inference or memory bottlenecks.
Method
LightLDA combines an O(1) Metropolis-Hastings sampler with structure-aware model parallelism, differential storage, and bounded-asynchronous data parallelism on Petuum.
Results
1 trillion model parameters and 200 billion tokens were trained in 180 hours on 8 machines, falling to 60 hours on 24 machines.
Takeaways & Limitations
LightLDA puts very large LDA data and model sizes within reach of small compute clusters while providing near-linear scalability in cores and machines.
Takeaways & Limitations
NUMA effects remain significant, and the authors identify proper NUMA-aware programming as a better long-term solution.
Abstract
from arXiv · showhide
When building large-scale machine learning (ML) programs, such as big topic models or deep neural nets, one usually assumes such tasks can only be attempted with industrial-sized clusters with thousands of nodes, which are out of reach for most practitioners or academic researchers. We consider this challenge in the context of topic modeling on web-scale corpora, and show that with a modest cluster of as few as 8 machines, we can train a topic model with 1 million topics and a 1-million-word vocabulary (for a total of 1 trillion parameters), on a document collection with 200 billion tokens -- a scale not yet reported even with thousands of machines. Our major contributions include: 1) a new, highly efficient O(1) Metropolis-Hastings sampling algorithm, whose running cost is (surprisingly) agnostic of model size, and empirically converges nearly an order of magnitude faster than current state-of-the-art Gibbs samplers; 2) a structure-aware model-parallel scheme, which leverages dependencies within the topic model, yielding a sampling strategy that is frugal on machine memory and network communication; 3) a differential data-structure for model storage, which uses separate data structures for high- and low-frequency words to allow extremely large models to fit in memory, while maintaining high inference speed; and 4) a bounded asynchronous data-parallel scheme, which allows efficient distributed processing of massive data via a parameter server. Our distribution strategy is an instance of the model-and-data-parallel programming model underlying the Petuum framework for general distributed ML, and was implemented on top of the Petuum open-source system. We provide experimental evidence showing how this development puts massive models within reach on a small cluster while still enjoying proportional time cost reductions with increasing cluster size, in comparison with alternative options.
1 Introduction
LightLDA targets web-scale topic modeling without requiring industrial-sized clusters. It combines algorithmic and systems innovations to train trillion-parameter models on modest clusters while reducing costs and preserving scalability.
- Web-scale corpora require topic models with millions of topics and vocabulary words, creating parameter spaces far larger than conventional LDA settings.
- Large-scale LDA systems have processed billions of documents using thousands of machines, but such clusters impose substantial setup, power, and maintenance costs.
- LightLDA partitions both data and model across machines, streams them to use memory and network resources efficiently, and applies an O(1) Metropolis-Hastings sampler.
- 1 trillion model parameters and 200 billion tokens were trained in 180 hours on 8 machines, falling to 60 hours on 24 machines.
- LightLDA combines a fast MCMC sampler with a Petuum-based distributed architecture as a cost-effective alternative to general-purpose platforms and bespoke systems.
2 Challenges and Related Work
Prior LDA work scaled through faster inference, distributed systems, or both, but generally relied on large clusters and faced bottlenecks in sampling, partitioning, or data representation. LightLDA addresses these constraints with a faster sampler and a different data-and-model-parallel strategy.
- LDA recovers coherent topics and document-topic mixtures, motivating efforts to scale inference to increasingly large data and model sizes.
- Existing implementations trained on billions of documents using thousands to tens of thousands of CPU cores, often with SparseLDA or collapsed Gibbs inference as an efficiency limit.
- LightLDA introduces an O(1)-per-token Metropolis-Hastings sampler reported as nearly an order of magnitude faster than SparseLDA.
- Prior systems differed in data- versus model-parallel partitioning, with globally shared models, grid-like partitioning, or pipelined designs imposing communication, memory, or sampler constraints.
- PLDA+ and Peacock grouped token indicators by word to reduce each worker’s model storage, whereas LightLDA adopts a different data-and-model-parallel strategy for memory and CPU efficiency.
3 Structure-Aware Model Parallelism for LDA
Structure-aware model parallelism partitions LDA’s model according to the words present in streamed data blocks. Workers process small model slices sequentially, reducing local memory needs and avoiding unnecessary model movement while preserving fast token sampling.
- Models with up to one million topics can contain trillions of parameters, making conservative model partitioning necessary because documents may touch much of the model.
- Figure 1 orders sampling by model slices V1, V2, and so forth, skipping vocabulary cells absent from each sparse document before loading the next data block.
- LDA partitions token indicators and document-topic counts as data, while the word-topic table forms the model required during token sampling.
- Data blocks are annotated with their instantiated vocabulary words, allowing workers to load a small set of corresponding word-topic rows as a model slice.
- Workers sample all tokens associated with one model slice before advancing, avoiding repeated slice swapping and reducing communication overhead.
- The strategy sends model slices to the data because the data is larger and the model becomes sparser as sampling converges.
4 Fast Sampling Algorithm for LDA
LightLDA accelerates LDA sampling by combining cheap Metropolis-Hastings proposals with factorized, sparsity-aware sampling. Its doc- and word-proposals support O(1) or sparse-time draws while alternating proposals improves exploration of the model space.
- Motivation: O(K) sampling per token is infeasible at K = 1 million, motivating SparseLDA and AliasLDA accelerations.SparseLDA exploits sparsity, while AliasLDA combines alias tables with Metropolis-Hastings.
- Proposal design: LightLDA factorizes the conditional distribution into O(1) proposals that alternate between document-dependent and word-dependent structure.The factorization targets proposals that are cheaper to sample while retaining probability mass near likely topics.
- Word proposal: The word-proposal uses a mixture of sparse word-specific and dense globally shared alias tables, reducing each word’s table construction to O(Kw).The shared dense table is amortized across vocabulary words, while the sparse table stores topics associated with the word.
- Document proposal: The doc-proposal samples its document-frequency component directly from token topic indicators, which serve as an alias table without explicit construction.This avoids building an alias table for the document-dependent component.
- Mixing: Cycling the doc- and word-proposals improves mixing by allowing each proposal to explore modes that the other proposal misses.Figure 4 illustrates a mode poorly explored by the doc-proposal but well explored by the word-proposal.
- Mixing: Using only one proposal can require many MH steps because it concentrates on document or word modes and leaves other modes unexplored quickly.The word-proposal favors topics concentrated in words, whereas the doc-proposal favors topics concentrated in documents.
5 Hybrid Data Structures for Power-Law Words
Scaling LDA to million-topic, million-word models creates severe memory demands, while sparse storage can hurt random-access sampling speed. LightLDA therefore combines frequency-aware storage choices to reduce memory use while preserving throughput.
- Memory challenge: 4 terabytes are required to store a dense 1-million-by-1-million word-topic matrix with 32-bit integer entries.With 128 GB of RAM per machine, storing this matrix alone would require 32 machines, before system overheads.
- Frequency structure: Power-law word frequencies make most word-topic rows extremely sparse, motivating sparse representations such as hash maps.A web-scale corpus contained over 3000 billion tokens, yet only 300 words exceeded the 32-bit term-frequency limit.
- Speed–memory trade-off: Pure hash maps cause a several-fold performance loss versus dense arrays because MCMC samplers rely heavily on random memory references.This affects SparseLDA, AliasLDA, and LightLDA’s Metropolis-Hastings sampler.
- Hybrid solution: LightLDA stores hot-word rows as dense arrays and long-tail rows as open-addressing or quadratic-probing hash tables.This hybrid design directs frequent accesses to fast dense arrays while retaining sparse storage for most rows.
- Hybrid solution: 10% of vocabulary words cover almost 95% of tokens, while the remaining 90% cover only 5%, supporting the hybrid allocation.The frequency split explains why most accesses use dense arrays while most rows remain sparse hash tables.
6 System Implementation
LightLDA implements distributed LDA by placing model state in a parameter server, keeping corpus shards local, and coordinating structure-aware model slices with pipelined and bounded-asynchronous execution. These choices target the memory, communication, and I/O costs of trillion-parameter models.
- System architecture: A trillion-parameter LDA model can require terabytes of memory, making distributed storage and parameter synchronization necessary.The system architecture is designed to reduce the resulting network communication costs.
- System architecture: The parameter server provides a distributed shared-memory interface while extending the machine memory hierarchy across workers.Each machine divides RAM between local client use and remote parameter storage.
- Parameter storage: The parameter server stores the word-topic table and topic summary row, using 32-bit integers for the table and 64-bit integers for the summary row.The word-topic table combines dense arrays and sparse hash maps, and becomes increasingly sparse as sampling progresses.
- Data placement: Workers keep shuffled corpus shards on local disks, avoiding network exchange of input data during inference.Each worker accesses only its local data shard while model parameters are accessed through the parameter server.
- Data placement: Data shards are split into blocks and streamed into memory because web-scale shards can reach hundreds of gigabytes or several terabytes.The out-of-core design also supports warm-start recovery after failures by resuming from swapped-to-disk state.
- Pipelined execution: Pipelining overlaps computation, disk I/O, and network transfers, while bounded asynchronous execution removes network waiting at adjacent iteration boundaries.The implementation uses Stale Synchronous Parallel, which the passage states outperforms Bulk Synchronous Parallel.
- Structure-aware execution: Model slices mix hot and long-tail words after frequency-based sorting and shuffling, improving load balance across slices.Token-topic pairs are sorted once by shuffled vocabulary position so tokens for each model slice are contiguous within data blocks.
- Hardware considerations: Hyper-threading and thread core affinity produced a 30% performance gain, while NUMA effects remained significant and were only partially addressed.The paper identifies NUMA-aware programming as a better long-term solution.
7 Experimental Results
LightLDA scales nearly linearly across computational resources and enables trillion-parameter LDA training on modest clusters. Its sampler converges faster than SparseLDA and AliasLDA, while the cycle proposal preserves quality across document and word likelihoods.
- Scalability: LightLDA shows near-linear scaling within one machine and across distributed resources, although initial distributed iterations suffer communication bottlenecks.The bottleneck arises because the early model is dense and saturates the cluster’s 1 Gbps Ethernet.
- Large-scale training: 1 trillion model parameters are trained on 200 billion tokens using 8 or 24 machines, with convergence within 5 days or 2 days, respectively.The experiment uses a 1-million-word vocabulary and 1 million topics.
- Large-scale training: 2 billion non-zero word-topic entries remain after 100 iterations, representing 1% of the 200 billion tokens.The converged model is therefore sparse despite its nominal parameter count exceeding the token count.
- Algorithm versus baselines: LightLDA runs around 3 to 5 times as fast as AliasLDA and converges faster in time than SparseLDA and AliasLDA.SparseLDA makes the best progress per iteration, but LightLDA’s shorter iterations improve convergence per unit time.
- Algorithm versus baselines: The cycle proposal is nearly as good as SparseLDA while jointly representing documents and vocabulary, unlike either the doc-proposal or word-proposal alone.The doc- and word-proposals each fail to maximize the likelihood associated with the other component.
8 Conclusions
LightLDA combines an O(1) Metropolis-Hastings sampler with structure-aware model parallelism and bounded-asynchronous data parallelism to process very large LDA workloads on small clusters. Its hybrid data structure balances memory efficiency and sampling performance, while the authors suggest broader applicability of these design ideas.
- 8 Conclusions: LightLDA combines an O(1) Metropolis-Hastings sampler, structure-aware model parallelism, and bounded-asynchronous data parallelism for large-scale distributed LDA.The implementation uses the Petuum framework.
- 8 Conclusions: A hybrid data structure balances memory efficiency with sampling performance in the distributed implementation.
- 8 Conclusions: The authors suggest applying the sampler decomposition and parallelism concepts to inference in other graphical models and large-scale ML systems.