Low-Rank Correlations, Sparse Counts: Exact Sampling for Correlated Topic Models at Ten Thousand Topics

A topic model describes each document as a mixture of themes ("topics"), where each topic is a distribution over words. The correlated topic model goes further and learns which topics tend to appear together, for example "genomics" with "cancer", using a $K \times K$ covariance matrix over topics. That matrix is the bottleneck. With $K$ topics it costs $O(K^2)$ memory and at least $O(K^2)$ work per document, so the only fast exact sampler we have stalls at around a thousand topics. The low-rank alternative that does scale gives up exact posterior sampling and uses a variational approximation instead. This proposal argues that the two kinds of structure in a correlated topic model should be handled by different tools. Topic co-occurrence is dense but approximately low-rank, so it belongs in a small factor model whose subspace is found by a singular value decomposition (SVD, the factorization that gives the best rank-$r$ approximation of a matrix). Word–topic assignments are discrete and extremely sparse, so they belong in a sampler that touches only nonzero counts.

Concretely, we write the topic covariance as low-rank plus diagonal, $\Sigma = WW^\top + \mathrm{diag}(\delta)$ with $W \in \mathbb{R}^{K \times r}$ and $r \ll K$. We introduce one $r$-dimensional latent factor per document, which makes every topic weight conditionally independent given that factor. We then combine Pólya-Gamma augmentation, which turns the softmax likelihood into a Gaussian one, with a topic–word matrix that contains exact zeros. Each step of the resulting Gibbs sampler is exact for the model. A token assignment costs $O(K_{v})$, the number of topics the word actually belongs to, and a document's topic weights cost $O(Kr)$ instead of $O(K^2)$. SVD has two specific jobs. It chooses the rank $r$ and initializes the subspace from a cheap sparse-LDA burn-in, and it serves as a diagnostic for whether low-rank truncation erases correlations among minority topics. The claim to be tested is that this sampler matches or beats the variational low-rank model on held-out likelihood at equal wall-clock time, at $K$ between $10^3$ and $10^4$, where the dense exact sampler cannot run.

What Prior Work Leaves Open

Three papers frame the problem. Scalable Inference for Logistic-Normal Topic Models motivates exact sampling. Its Pólya-Gamma Gibbs sampler for the correlated topic model (gCTM) finished on NYTimes in 2 hours "whereas the variational version could not finish within a week". It still keeps a dense $K\times K$ covariance, which is the quadratic barrier we remove. Efficient Correlated Topic Modeling with Topic Embedding is the closest prior work. It replaces the covariance with low-dimensional topic embeddings and uses a sparsity-aware sampler inside stochastic variational inference, reaching 100,000 topics on PubMed. It learns the embeddings by gradient steps under a variational approximation. We keep the low-rank idea but sample the posterior exactly, and we get the subspace from an SVD rather than from end-to-end optimization. Pólya Urn Latent Dirichlet Allocation supplies the sparse half of the method. Replacing Gamma draws with Poisson draws puts exact zeros in the topic–word matrix and gives per-token cost $O(\min\{K_d, K_v\})$. That paper covers only uncorrelated LDA, and its approximation is exact only asymptotically, a constraint we inherit.

Two papers constrain the design. Clustered Sub-Matrix Singular Value Decomposition shows that global SVD truncation favours dominant, high-variance directions and discards minority structure. The same risk applies to a rank-$r$ topic covariance, so the diagonal term and an explicit minority-correlation test are built into the plan. Rethinking LDA: Moment Matching for Discrete ICA and Anchor-Free Correlated Topic Modeling both use spectral decompositions of word co-occurrences to recover topics. The first finds that a spectral initialization improves the final likelihood of variational inference. Both produce topic vectors that violate the probability simplex and need heuristic repair. We avoid that problem by never applying SVD to word distributions. SVD is applied only to the unconstrained Gaussian log-weights, where negative entries are legitimate.

Core Mechanism

For document $d$, topic weights are $\theta_d = \mathrm{softmax}(\eta_d)$, and the log-weights are generated as

$$\eta_d = \mu + W s_d + \epsilon_d, \qquad s_d \sim \mathcal{N}(0, I_r), \qquad \epsilon_{dk} \sim \mathcal{N}(0, \delta_k),$$

where $\mu \in \mathbb{R}^K$ is a mean, $s_d$ is the document's $r$-dimensional factor, and $\delta_k$ is a topic-specific residual variance. Given $s_d$, the prior on each coordinate $\eta_{dk}$ is a univariate Gaussian. Following Scalable Inference for Logistic-Normal Topic Models, the likelihood of $\eta_{dk}$ given the other coordinates becomes Gaussian after drawing $\lambda_{dk} \sim \mathrm{PG}(N_d, \eta_{dk} - \zeta_{dk})$. Here $N_d$ is the document length and $\zeta_{dk} = \log\sum_{j\neq k} e^{\eta_{dj}}$ is maintained as a running sum. Each coordinate update is therefore $O(1)$, and gCTM's $O(1)$ Gaussian approximation applies to long documents. Sampling $s_d$ given $\eta_d$ is a Gaussian draw costing $O(Kr + r^3)$. Sampling the rows of $W$ given all $s_d$ is a standard Bayesian factor-analysis update costing $O(DKr)$ per sweep, where $D$ is the number of documents. No $K\times K$ object is ever formed. Token assignments use a Poisson Pólya-urn topic–word matrix $\Phi$, so

$$p(z_i = k \mid \cdot) \propto \theta_{dk}\,\phi_{k w_i}, \qquad k \in \mathrm{supp}(\phi_{\cdot w_i}),$$

which costs $O(K_{w_i})$ through alias tables over the word's nonzero topics. Under the low-rank-plus-diagonal model the whole sampler is exact apart from the Pólya-urn approximation of $\Phi$, which vanishes asymptotically. Per sweep the cost is $O(N\bar K_v + DKr)$, against roughly $O(N\bar K_d + DK^2)$ for dense gCTM, where $N$ is the total token count and $\bar K_v$, $\bar K_d$ are the average numbers of active topics per word and per document.

The SVD enters at a single point. We run a few hundred sweeps of plain Pólya-urn LDA, form the $D\times K$ matrix of centered smoothed log document–topic proportions, and compute a randomized truncated SVD. Its leading right singular vectors, scaled by their singular values, initialize $W$. The scaled left singular vectors initialize $s_d$. The rank $r$ is set at the largest gap in the singular value spectrum. After sampling, we compare the posterior spectrum of $WW^\top$ with the empirical spectrum to see whether the sampler has moved away from the spectral starting point.

Research Program

The work has three parts. The first is the sampler: a multithreaded CPU implementation of the Gibbs steps above, with the Pólya-urn token step parallelized over documents as in Pólya Urn Latent Dirichlet Allocation. The second is a synthetic study. Corpora are generated from correlated topic models with a planted rank-$r$ covariance plus small dense blocks of correlated minority topics, which tests the failure mode described in Clustered Sub-Matrix Singular Value Decomposition. We measure recovery of the planted covariance, separately for dominant and minority blocks, as $r$ varies. The third is a scaling study on real corpora that measures how held-out likelihood and wall-clock time trade off as $K$ grows and the dense sampler falls behind.

One risk needs stating now. The document-level step is $O(Kr)$ and not sublinear in $K$, because logistic-normal weights are dense. At $K=10^5$ on all of PubMed this term dominates, so we target $K \le 2\times10^4$. That is well above the gCTM ceiling, but it is not the 100,000 topics of the variational model.

Baselines

The naive reference point is uncorrelated sparse LDA, meaning Pólya-urn LDA from Pólya Urn Latent Dirichlet Allocation at the same $K$. It is the model with no correlation structure, and its per-token cost is the floor our sampler should approach. The file reports that at 1,000 topics it cut $z$-sampling time by "approximately 20%" and made $\Phi$ sampling "4 to 8 times faster". It reports no held-out likelihood. We run it with the same vocabulary, the same Dirichlet hyperparameters, the same number of threads and the same wall-clock budget. Beating it means higher held-out document-completion log-likelihood at equal time. If we lose, correlations are not worth their cost at that $K$.

The strongest exact competitor is dense gCTM from Scalable Inference for Logistic-Normal Topic Models. Its reported results are 2 hours on NYTimes against more than a week for variational CTM, and "7.5x faster" than variational CTM on NIPS. The file contains no reported perplexity values. We reimplement it in the same codebase and run it at $K \in \{500, 1000, 2000\}$, where it is feasible. At small $K$ we need to match its held-out likelihood to within run-to-run variance. At larger $K$ we need lower time per sweep.

The strongest scalable competitor is the topic embedding model of Efficient Correlated Topic Modeling with Topic Embedding. Its reported results are 100,000 topics on 8.2M PubMed documents, and convergence on NYTimes "in a few hours" where vanilla CTM failed to finish in two days. No reported held-out likelihood value was found on Lacuna for this model. Our sampler and this model get the same embedding dimension $r$, the same $K$, the same hardware and an equal tuning budget over learning rate or hyperparameters. Beating it means higher held-out likelihood and higher 20Newsgroups classification accuracy at equal wall-clock time.

Three ablations isolate the key ingredients. Setting $r=0$ keeps only the diagonal and gives an independent logistic-normal model, which isolates the value of the low-rank factor. Random initialization of $W$ in place of the SVD initialization isolates the spectral step. A dense $\Phi$ in place of the Pólya-urn $\Phi$ isolates the sparse token step.

Why not just…?

Why not just use the topic embedding model's variational inference, which already scales further? This alternative is the main threat. The case for exact sampling rests on gCTM's evidence that the mean-field approximation hurts both prediction and runtime (Scalable Inference for Logistic-Normal Topic Models). That evidence compares against dense variational CTM, not against low-rank stochastic variational inference. The equal-time held-out likelihood comparison in this proposal settles the question directly. If the variational model wins or ties at every $K$, the exactness argument fails, and the right outcome is to say so.

Why not just fit uncorrelated sparse LDA and compute topic correlations afterwards with an SVD of the document–topic counts? This costs almost nothing extra and may recover similar correlation structure. What it cannot do is let correlations sharpen the topic assignments of short or ambiguous documents during inference. The $r=0$ versus $r>0$ comparison on held-out likelihood, and especially on short 20Newsgroups documents, tests this directly. If the gain is negligible, post-hoc SVD is sufficient and should be recommended.

Why not just keep dense gCTM and cap $K$ near a thousand? At $K\le1000$ that may well be enough, and the experiments will show it if our model only ties there. The argument for our model depends on regimes that need more topics, such as PubMed, where finer topics are the goal. There, dense covariance memory alone grows quadratically. We report the $K$ at which the dense sampler exceeds a fixed memory and time budget.

Why not just spectrally initialize a standard sampler and stop there? Rethinking LDA: Moment Matching for Discrete ICA already shows that spectral initialization helps, so on its own it would not be a new contribution. That is why the SVD initialization appears here only as an ablation and not as the claim.

Proposed Experiments

The benchmarks are NIPS and Enron for small-scale checks against dense gCTM, NYTimes for the main correlated-model comparison at $K$ from 1,000 to 10,000, a PubMed subset (1–2M abstracts) for $K$ up to 20,000, and 20Newsgroups for downstream document classification as used in Efficient Correlated Topic Modeling with Topic Embedding. The metrics are held-out log-likelihood by document completion, topic coherence, seconds per sweep, peak memory, and on synthetic data the recovery error of the planted covariance, reported separately for dominant and minority blocks.

Three checks decide whether the proposal succeeds. First, at $K=1000$ on NYTimes, the low-rank sampler must match dense gCTM's held-out likelihood. If it does not, rank-$r$ covariance throws away real signal. Second, at $K\ge5000$, it must beat the topic embedding model on held-out likelihood at equal wall-clock time. If it does not, exact sampling is not worth its cost. Third, on synthetic corpora, the diagonal-plus-low-rank model must recover minority correlation blocks no worse than a dense model fit to the same data. If global truncation erases them, as Clustered Sub-Matrix Singular Value Decomposition would predict, the next step is a block-structured factor initialized by SVD within clusters, and we will report that result rather than hide it.