E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time

Thank you for your overall positive review, and for remarking that our algorithm provides "strong provable guarantees" that "address a longstanding challenge in topic modeling", and that it improves interpretability and achieves strong empirical performance.

We recognize that your remaining reservations and reason for a score of 3 instead of 4 or 5 relate to clarifying some aspects of the experiments and adding a new baseline (FASTopic). We address these aspects and add FASTopic to all plots below, and we would appreciate it if you would consider improving your score in light of our response.

Re: "In the experiments, how about the performance with larger numbers of topics? Like 50 to 100 topics."

• Our experiments already do this, and there is a subtle aspect to clarify here. Specifically, we set all baselines' number of topics $k=100$ in all experiments (except BERTopic, where $k$ is not user-specified). For E-LDA, the overall number of topics that are assigned is not user-specified. Instead, for E-LDA, we specify $\kappa$ (note $\kappa \ne k$, see our paper lines 182-7, right column): "...we seek a MAP solution where documents have varying counts of topics, but the average number of topics linked to each document is bounded by $\kappa$. Thus, choosing a smaller $\kappa$ yields a sparser solution...". For example, if we set $\kappa=5$, then a single document is assigned approximately 5 topics on average, even though there are many topics overall.

• Fig. $b$ on p. 8 then shows that the choice of $\kappa$ has minimal effect on performance. E-LDA obtains solutions of high coherence regardless of whether users set it to compute a sparse summary of their texts (where each document has $\kappa=1$ one topic, like BERTopic) or a nuanced and dense one (where each document is assigned to $\kappa=10$ topics).

Re: "Can you evaluate the inferred topic distributions $\theta_d$ of documents?"

• In our use-case, documents' underlying topic distributions $\theta_d$ are nuisance parameters, and we do not estimate them directly (see discussion in Section 3). Instead, we infer the topic assignments $z$ from which each word and document were probably drawn. It is nonstandard to plot topic assignments, yet we recognize your point, and we have begun preparing some additional plots for our camera-ready manuscript.

Re: "The datasets are of medium size. Can E-LDA still perform well on large-scale datasets? What is its empirical execution time?"

• Here is our performance on an additional larger dataset of 54,595 short texts (DBLP, Pan et al. 2016, mean length of 5 words), which is particularly challenging for some models:

https://imgur.com/a/LO1bUqw

On this larger dataset, E-LDA's efficient theoretic design allows it to complete in 2.8 seconds.

• We discuss execution time briefly in paper lines 371-4 (right column). Our research-grade Python code of our non-parallel algorithm takes an average of 2.7 seconds on Experiments Set 1, which is ~4.6 times faster than the highly optimized Java MALLET Gibbs sampler on the same processor.

• We could achieve additional speedups by offloading bottlenecked operations (the elementwise products in the Update subroutine) to a GPU.

• For very large data, our parallel algorithm offers a similar approximation guarantee in logarithmic parallel time, which is a further exponential speedup in overall runtime (see Section 6 and Appendices I and J).

Re: Adding a 7th baseline, FASTopic (Wu et al., NeurIPS 2024).

• Thank you for this suggestion. Here are the plots with FASTopic (in light blue):

https://imgur.com/4GobskW

E-LDA co-occurrence outperforms FASTopic by a factor of 2.83 to 5.84 on Reuters, 3.11 to 4.77 on Congress, and 2.24 to 4.20 on NewsGroups. FASTopic is the best of the baselines on NewsGroups, and it performs similarly to BERTopic on the other datasets.

Re: Reference list is missing recent surveys [1], [2], [3].

• Thank you for these references! We have incorporated them into our camera-ready draft.

Re: Typo where AVITM's publication date was replaced by BERTopic's in the reference in the paper, and Fig. 2 has only subcaptions.

• Great catch! Thank you for pointing this out---we have updated our paper accordingly.

Re: our statement that we compare against an LLM-based topic model.

• We often hear BERTopic referred to as an "LLM-based topic model", presumably because BERTopic operates on sentence embeddings generated by pretrained transformer language models. We used this description, but we share your discomfort with calling BERTopic "LLM-based", since in 2025, BERT is no longer a "large" language model (and it's trained differently than LLM's). We will revise this description to be more precise.

We believe that these clarifications and additional plots/baseline have addressed your remaining reservations, and we would appreciate it if you would update your review accordingly.

Thank you for your thoughtful and detailed review, and your comment that "The approach proposed in this paper enhances the LDA model from a novel perspective and offers theoretical guarantees...demonstrating high originality and inspiration for future work in the field."

We recognize that your main question relates to the stability of our approach, as it is well-known that many topic models obtain vastly different results from different random seeds (per the Hoyle et al EMNLP paper).

We are grateful that you raised this important point. When we presented this work a couple weeks ago, a colleague who is a prominent social scientist studying text analysis commented that he believed the stability of our approach is a high-impact contribution for practical applications, and he emphasized that we do not emphasize this contribution sufficiently in our writeup, so it is not clearly apparent. We realize that this deserves greater attention.

Our approach improves stability in three key ways:

1. E-LDA's deterministic optimization leads to perfect stability under the Hoyle et al. definition. Our approach is the first topic model with deterministic, non-gradient-based optimization. Our non-parallel algorithm, FastGreedy-E-LDA has no random seeds, so re-running the algorithm yields an exactly identical, near-optimal solution. Under the stability metric defined by Hoyle et al. (i.e., pairwise topic distance across runs), our model therefore achieves zero distance, i.e., perfect stability.

2. Stable, monotonic convergence of posterior probability. Due to the submodularity of our objective, FastGreedy-E-LDA also exhibits stable, monotonic convergence towards its near-optimal posterior probability. Specifically, as we show in the plots in Appendix Q Figs. a and b (starting at line 1375), each iteration of FastGreedy-E-LDA improves the posterior probability, and each subsequent improvement is slightly less than the previous improvement (i.e. diminishing returns), yielding a smooth and concave convergence of the posterior objective. Conveniently, this is also true on a per-document basis: each document's posterior probability also converges monotonically.

We contrast our smooth and monotonic convergence with the stochastic convergence of any alternative topic model optimization routine. We also emphasize that alternatives may have some very low-performing runs due to local modes/unlucky random seed, whereas our approach does not experience these issues since we provably obtain a near-optimal solution.

3. Stable coherence over different solution sizes (different sparsities). Fig 2.b (paper line 401) plots the stability of E-LDA’s topic coherence as we grow its solutions from sparse to dense (i.e., over the course of optimization). We observe that running our algorithm with very different sparsity constraints yields solutions that are quite stable in terms of topic coherence.

---Responses to additional questions/suggestions---

Re: Adding a very recent baseline***.

• Thank you for this suggestion. We note that reviewer ZFSN agrees and suggests FASTopic (Wu et al., NeurIPS 2024). Here are the plots with FASTopic added (in light blue):

https://imgur.com/4GobskW

E-LDA co-occurrence outperforms FASTopic by a factor of 2.83 to 5.84 on Reuters, 3.11 to 4.77 on Congress, and 2.24 to 4.20 on NewsGroups. FASTopic is the best of the baselines on NewsGroups, and it performs similarly to BERTopic on the other datasets.

Re: Figures 1 and 2 are missing captions, and there is an extra ‘(for example)’ on line 70.

• Great catch---thank you! We've corrected both.

Re: Figure 1 seems a bit cluttered, and it is recommended that the authors reorganize it.

• Agreed -- it had to be compressed in order to fit the 8-page submission limit. We will revise and improve layout in the camera-ready version, where we have 9 pages.

Re: use of italics, bold, upper and lower case, and brackets.

• Thank you for this constructive feedback. Our goal was to provide a description of our techniques that could be useful to researchers in three very different fields: NLP, combinatorial optimization, and applied econometrics/social science. We noted that each of these fields have very different expectations about how the technical aspects should be described and which aspects should be highlighted. We agree with you that we can reduce the use of italics and brackets and also streamline some areas, and we're revising accordingly.

We thank you for your positive review, and we are sincerely grateful for your many detailed and thoughtful comments. We respond below to your specific points about comparing our computational complexity with alternatives, interpretability, causal inference, and the additional references.

Re: the reviewer's comment "The algorithms converge to near-optimal posterior probability in logarithmic parallel computation time (adaptivity) exponentially faster than any known LDA algorithm... the claim ... would benefit from more explicit comparisons to the computational complexity of a wide range of LDA algorithms."

• Thank you for this suggestion, and we appreciate the opportunity to delineate this contribution. The only mainstream topic models with provable convergence guarantees are those of the anchor word variants of Arora et al.'s group (2013, 2016, 2018) and the SVD approach of Anandkumar et al., (2012, 2014). Setting aside their differences in assumptions and objectives, both have polynomial time complexity, and neither has logarithmic adaptivity in parallel. For example, the Arora et al. (2013, 2018) approach computes a co-occurrence matrix, then computes anchor words ($O(|V|^2 + |V|k/\epsilon^2)$) and topic recovery ($O(|V|^2k + Vk^3/\epsilon^2)$). Anchor word selection is inherently sequential (each iteration depends on the previous one), so there is no known parallel algorithm with logarithmic adaptivity. Furthermore, this procedure only obtains topics, not document distributions or assignments—those require additional data-dependent complexity (Arora et al. 2016). Similarly, in the Anandkumar approach, SVD is a major bottleneck, as there is no known generic log-adaptive SVD algorithm.

• The most popular solvers for LDA—VI and Gibbs sampling—have no known polynomial time bounds for convergence/mixing. Even in parallel implementations, both require global synchronization after each iteration, which precludes logarithmic adaptivity.

• Similarly, BERTopic and neural topic models have no guarantees, and they typically proceed via sequential optimizations (e.g. BERTopic's UMAP requires sequential computations in parallel), so there is no known logarithmic parallel approach.

Re: the reviewer's comment "The interpretability of topics is somewhat subjective, and while the authors' method provides a more structured way to connect topics and keywords, it might not fully guarantee interpretability in all contexts."

• We agree—the term interpretability has been used to refer to many different concepts in the topic modeling literature, and we do not claim that our approach is "interpretable" in a general sense. However, our method conveys a specific property that is novel among topic models, yet familiar and desirable to researchers trained in econometrics. As you correctly note, each topic in our model is formally associated with a keyword, such that the probability mass that the topic assigns to each word in the vocabulary is a known function of that word's co-occurrence with the keyword. In social science applications, where the goal is often parameter estimation, it is desirable to adopt models in which parameters correspond to known functions—for example, in a GLM, a regression coefficient represents the expected change in the dependent variable given a unit change in a feature. We distinguish this property from other topic models, where a topic may assign mass to a word for reasons that are opaque and specific to a (somewhat arbitrary) optimization routine.

Re: the reviewer's comment "Unlike alternatives, our approach can maintain the independence assumptions necessary to use the learned topic model for downstream causal inference..." ...While the authors' approach may be better than some alternatives, it's difficult to definitively claim that it fully maintains independence assumptions in all cases. .

• We agree, and we provide additional discussion of how our approach can be used for causal inference in Appendices J, K, L, and M. There is an important nuance here: Unlike alternatives, our approach obtains topic assignments that are well-defined as causal treatments, and that can be computed out-of-sample (with provable guarantees) to maintain document-to-document independence assumptions that are necessary (but not sufficient) for SUTVA. However, in virtually any causal inference setting, including when using our approach, it is possible that independence assumptions are still violated (for example, by unobserved confounders).

Re: the reviewer's comment that "The paper is very thorough in its discussion of the topic modeling literature" but should add the missing Ash et al. review paper and additional text-as-data and causality+NLP citations.

• Thank you for this helpful suggestion! We have added this reference and we are expanding our literature review accordingly to take advantage of the expanded page limit in the camera ready version.

Thank you for your overall positive review, and for your positive comments about our "rigorous theory" and "solid empirical results." We also thank you for your positive comments that the paper "is interesting and gives insight to the community."

We believe we address your remaining reservations here and would appreciate it if you would consider improving your score in light of our response.

The main concern and reason for a score of 3 instead of 4 or 5 seems to be:

1. Whether our algorithm also performs well on short texts. We note that our Reuters News Wires dataset consists of short texts (mean of 80 words, see Appendix J). Here is our performance on an additional larger dataset of 54,595 very short texts (DBLP, Pan et al. 2016, with a mean length of 5 words):

   https://imgur.com/a/LO1bUqw

2. Your assessment about impact here: "While the combination is original, individual elements: submodular greedy algorithms, FAST parallelization, and coherence metrics are well-established. The innovation lies in their application to LDA, but this may feel incremental."

We strongly believe that this is a high-impact paper. Specifically, we strongly believe that the ICML community will be interested in the first practical algorithms with provable guarantees for a central problem in topic modeling, as well as a novel, non-gradient-based way to solve topic models that is exponentially faster than all known algorithms (the best known guarantees of any kind for LDA are poly-time). Provable guarantees for topic models have long been considered one of the most desirable results in NLP, and our paper describes the first new theoretic guarantees for topic modeling in several years.

While it is true that these building blocks of submodular optimization, low-adaptivity parallel optimization, and coherence are well-established, we emphasize that:

• The connection between submodularity and LDA is wholly unknown, and the analysis is nontrivial;

• Even given access to our submodular formulation of LDA (eq. 3), it is practically infeasible to obtain solutions using generic fast submodular optimization techniques, such as Lazier-than-Lazy-Greedy or FAST low-adaptive parallelization. Specifically, our nonparallel algorithm obtains a per-iteration complexity that scales logarithmically with the size of the data $|D|$, and obtains its approximation guarantee deterministically (Theorem 2). In contrast:

  • Vanilla Greedy matches our approximation guarantee, but each iteration has complexity that scales polynomially in the size of the data $|D|$ (proof in Appendix F);

  • As we prove in Appendix H, the state-of-the-art generic nonparallel algorithm for submodular maximization, Lazier-than-Lazy-Greedy, has a per-iteration complexity of $O(\ell |\Phi| |D| log(1/\epsilon))$, plus sampling complexity. This linear dependence on the data $|D|$ makes it practically infeasible for most datasets. Appendix H also shows that Lazier-than-Lazy-Greedy remains slower than our algorithm even when accelerated with our techniques. Its approximation guarantee is also worse than ours by an ε factor and only holds in expectation, whereas our guarantees are deterministic.

  • It is also practically infeasible to use low-adaptivity parallel algorithms like FAST for this problem without our techniques because their practical compute time is dominated by compute-heavy objective function evaluations that scale as a function of the data size $|D|$. Appendices I and J show how to remove this data size dependency and accelerate them to just $O(\ell)$ or $O(\ell | |\Phi|)$. This enables fast parallel solutions in practice.

---Responses to additional questions---

Re: How were neural and LLM-based baselines tuned?

• We provide replication code in the Supplemental Materials and details in Appendix P (line 1353 on). For ETM, AVITM, and BERTopic, we used the authors' codes. We set k=100 topics, except for BERTopic where k not user-specified, and we set all other parameters to match those in the authors' papers. So, for example, we set BERTopic to use the all-MiniLM-L6-v2 transformer per Maarten Grootendorst.

Re: Why is AVITM’s performance notably poor?

• Our experience in many projects is that AVITM performs very well on some data, but poorly on others absent much custom preprocessing/tuning (see Appendix lines 1357-9). We confirmed that when we swap the AVITM authors' exact preprocessed datasets into our codebase and switch to their metrics, then we can replicate their results, so its poor performance on our datasets is just due to its instability on some data. We expect it can be improved with custom tuning of batch size and preprocessing, etc., but that is beyond our scope (and we do zero tuning for E-LDA).

We believe that our responses address your remaining questions, and we would sincerely appreciate it if you would consider updating your score.