E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Authors: Adam Breuer
Venue: ICML 2025 poster (2025)
Keywords: Topic models; Causal inference; Social Science; Latent Dirichlet Allocation (LDA); Natural language processing; Text.
Primary area: general_machine_learning->unsupervised_and_semisupervised_learning
TL;DR: We provide a novel non-gradient-based, combinatorial approach to estimating topic models with strong provable guarantees. We show that this solves key problems in topic modeling for social science applications.

Abstract: In this paper, we provide the first practical algorithms with provable guarantees for the problem of inferring the topics assigned to each document in an LDA topic model. This is the primary inference problem for many applications of topic models in social science, data exploration, and causal inference settings. We obtain this result by showing a novel non-gradient-based, combinatorial approach to estimating topic models. This yields algorithms that converge to near-optimal posterior probability in logarithmic parallel computation time (adaptivity)---exponentially faster than any known LDA algorithm.  We also show that our approach can provide interpretability guarantees such that each learned topic is formally associated with a known keyword. Finally, we show that unlike alternatives, our approach can maintain the independence assumptions necessary to use the learned topic model for downstream causal inference methods that allow researchers to study topics as treatments. In terms of practical performance, our approach consistently returns solutions of higher semantic quality than solutions from state-of-the-art LDA algorithms, neural topic models, and LLM-based topic models across a diverse range of text datasets and evaluation parameters.

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Adam Breuer'
Abstract
Djourelova, 2023; Blanes Vidal et al., 2012; Catalinae, 2016; Griffiths and Steyvers, 2004; Hall et al., 2008; Laud- erdale and Clark, 2014; Martin and McCrain, 2019; Diet- rich et al., 2019; Mueller and Rauh, 2018; Pan and Chen, 2018; Tingley, 2017). These models seek to learn the la- tent thematic structure that describes the content of a text dataset. Specifically, topic models posit that each docu- ment's words were drawn from (latent) document-specinf mixture of (latent) topics, where each topic is distribution over all words in a vocabulary.
In this paper, we provide the first practical algo- rithms with provable guarantees for the problem of inferring the topics assigned to each document in an LDA topic model. This is the primary in- ference problem for many applications of topic models in social science, data exploration, and causal inference settings. We obtain this result by showing novel non- con-gradient-based combinato- rial approach to estimating topic models. This yields algorithms that converge to near-optimal posterior probability in logarithmic parallel com- faster
For many applications of topic models, the primary goal is to estimate the set of latent topics, which provides simple yet semantically rich summary of the data. In contrast, for the majority of applications in social science and data ex- ploration, practitioners' primary goal is infer each doc- ument's most probable assigned topics. These document- level topic assignments
putation time (eeppivvtyy-xxpneetttt than any known LDA algorithm. We also show that approach can provide interpretability guarantees such that each learned topic is for- mally associated with known keyword. Fi- nally, we show that unlike alternatives, our ap- proach can maintain the independence assump- tions necessary to use the learned topie model for downstream causal inference methods that allow researchers to study topics treatments. In terms of practical performance, our approach consistently returns solutions of higher seman- tic quality than solutions from state-of-the-art LDA algorithms, neural topic models, and LLM- based topie models across a diverse range of text datasets and evaluation parameters.
then used document labels that can be piped into downstream document-level regres- sion analysis or causal inference methods.
Social scientists continue to strongly prefer LDA for this task over recent neural and LLM/BERT-based topic models for two reasons. First, social science research designs fa- vor parametric models that are amenable to analysis. This is particularly important when using topic model outputs as labels for downstream models whose theoretic guaran- tees require that labels are well-estimated, consistent, con- ditionally independent, etc. Second, social scientists as- sume that the latent LDA topic space semantically inter- pretable. However, there are three key challenges.
1. Introduction
known provable guarantees for the topic assignment problem. First, it is well-known that full pos- terior inference of LDA parameters is NP-hard even with just 2 topics (Arora et al., 2012). Under various assump- tions, it is possible to approximate LDA's set of topics in poly-time (Anandkumar et al., 2012; Arora et al., 2012; 2013; 2016a; 2018). However, even if these latent topics are known, it is still NP-hard in general to learn LDA's Maximum A Posteriori (MAP) assignments (i.e., which topic probably generated each word in a given document) (Sontag and Roy, 201 1). Practitioners therefore resort to heuristic inference techniques such as variational infer- ence (Blei et al., 2003) or Gibbs samplers (Griffiths and
There
Topic models such as Latent Dirichlet Allocation (LDA) (Blei et al., 2003) have become central numerous high- profile streams of social science research ranging from the history of science to economics and political science (Ash and Hansen, 2023; Barberá et al., 2019; Bybee et al., 2024;
'Department of Computer Science, Dartmouth College. Hanover, NH. USA. Correspondence to: Adam Breuer brduer dartmouth.eduu Code available at: https: 1 it hub.
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Our contribution. We show the first practical algo- rithms that near-optimally solve the Maximum A Posteriori (MAP) topic-word assignment problem for LhA-that is, we provably obtain the near-optimal topic from which each word (and document) in the dataset was probably drawn.
Steyvers, 2004). These approaches are well-motivated, but they seek only locally modal solutions and produce poorly fit results on some datasets (Gerlach et al., 2018).
Existing algorithms are generally incompatible with causal inference. Second, there has been much recent in- terest in causal inference frameworks that consider doc- uments' topics as treatments or outcomes (Egami et al., 2022: Feder et al., 2021; 2022; Fong and Grimmer, 2016; 2023; Hu and Li, 2021; Veitch et al., 2020). Obtaining doc- uments' topic assignments for these frameworks requires 2nd round of inference using out-of-sample inference algo- rithms. However, out-of-sample algorithms also lack ap- proximation guarantees, which undermines the usual guar- antees for causal inference and yields spurious inferences with unbounded bias (Battaglia et al., 2024).
We contrast our approach with standard LDA algorithms, which fix a small set of topics and use gradients adjust them incrementally towards local mode. That standard approach relies hyperparameters to encourage desir- ably sparse set of topics in document's underlying distribu- tions. Then, after fitting a model, practitioners typically compute topics' coherence scores, prune low-coherence topics, and manually label topics with heuristic keywords.
We invert this approach to develop a combinatorial up- proach to estimating topic models. Suppose we have very large 'candidate set' of topics from which the sparse set of topics in the solution are selected. It is easy to ob- tain this candidate set from other algorithms. Alternatively, we show we can simply initialize it to all feasible topics that meet standard interpretability criteria, so any topic se- lected for the solution will ascribe mass via a known func- tion of some keyword. Then, instead of relying on gra- dients and heuristic we proceed combinatorially. Specifically, we consider the MAP assignment problem under an explicit sparsity con- straint that upper-bounds the mean number of topics from which each document was drawn. This approach conveys multiple theoretic advantages for social science applica- tions as we discuss below, and it brings LDA into line with recent techniques in clustering and data summarization.
Existing algorithms learn and assign some uninter- pretable topics. Finally, social scientists continue to prefer parametric topic models like LDA over neural and LLM- based models because they assume that the latent LDA topic space is interpretable. However, practitioners who wish to understand LDA results must manually parse top- ies that are arbitrary distributions over e.g. 20,000 words in search of semantic meaning, then subjectively choose topic 'label' (e.g. "this topic is about 'physics"") a bur- densome and subjective process that was famously com- pared to 'reading tea leaves' (Chang et al., 2009; Lau et al., 2014). In practice, researchers find that 10% of the topics learned by standard algorithms are fully nonsensical, and many more are partially nonsensical (Mimno et al., 201 1). These problems have led to vast research post-hoe eval- uation of topics' semantic quality and inspired recent ex- citement about algorithms that attempt to heuristically as- sociate topics with keywords (Eshima et al., 2020; Doshi- Velez et al., 2015; Mimno et al., 2011; Röder et al., 2015). However, we lack a formal means to guarantee that each topic ascribes probability mass in an interpretable way, such via known function of a known keyword.
hyperparameters,
Provable guarantees. Our algorithm obtains a determinis- ric worst-case 1-1/e approximation of the constrained log MAP probability objective (i.e. the most probable topic from which each word was drawn) in a number of itera- tions that is linear in the count of documents, where each iteration's 's runtime is just logarithmic in the count of doc- uments. We also give parallel algorithm that converges w.p. in logarithmic iterations (adaptivity). This is expo- nentially faster than any known LDA algorithm. Because our algorithms can also perform out-of-sample inference, they also provide a means to use LDA for causal inference with provable approximation guarantees.
These various problems make LDA an outlier among related ML techniques. Seminal work of Blei et al. (2003) shows that LDA is a hierarchical extension of clustering (e.g. 'mixture of unigrams'). Yet unlike LDA, cluster- ing models have recently benefited from theoretic break- throughs in combinatorial optimization that yielded fast algorithms with oparmml approximation guarantees. These include exemplar-based problem formulations that convey additional interpretability advantages and other de- sirable properties (Breuer et al., 2020; Balkanski et al., 2019; Liu et al., 2013; Mirzasoleiman et al., 2013; 2015).
Practical performance. Finally, we show that our algo- rithms consistently learn solutions of higher semantic qual- ity (coherence) than those found by state-of-the-ae LDA al- gorithms, neural topic models, and LLM/BERT-based topic models. These improvements hold across a diverse set of text datasets and evaluation parameters.
o o
Technical overview. From a purely technical perspective, there are four major challenges addressed in this work.
Can the breakthroughs in optimization that recently revolutionized clustering algorithms also yield simi- larly fast, optrool interpretable topic models?
The first is to show that under certain conditions, the clas- sic LDA MAP assignment problem can be cast as a com-
000
2

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
binatorial optimization problem whose objective function exhibits the key diminishing returns property known as monotone submodularity. Submodularity is heavily stud- ied in clustering, data summarization, and NLP problems, but surprisingly, its connection to topic models remained undiscovered (Gomes and Krause, 2010; Mirzasoleiman et al., 2015; 2016; Lin and Bilmes, 2011). Due to this prop- erty, the problem admits near-optimal solutions via generic Greedy algorithms (Nemhauser et al., 1978). Unfortu- nately, vanilla Greedy algorithms are practically infeasible for this objective because their runtime complexity scales as a third order polynomial in terms of the number of doc- uments. In fact, because this objective is defined on sets of copie-to-document connections (links), not documents, solving it for even modest text corpora requires us to solve some of the largest combinatorial optimization problems considered in any academic research in terms of the sizes of the ground set (potential links) and solution set. Therefore, our second challenge is to design fast serial algorithm for this problem with the same near-optimal Greedy approxi- mation guarantee by leveraging the special independence structure of LDA's probabilistic model. We then show that our techniques also apply very recent parallel adaptive sampling algorithms (Balkanski and Singer, 2018; Breuer et al., 2020). We leverage this to obtain near-optimal MAP solutions w.h.p. in logarithmic parallel time.
distribution over all words corresponding topic z. We re- fer to the h topics as candidate topics to distinguish them from realized topics that are actually sampled. Denote by c the set of candidate topic distributions {oi..... @ by Z all latent realized topics žd,; assigned to each word in d E D; by θ all documents' topic mixtures (fI...., 0 p ): and by Wd,rr the count of words in d that are drawn from topic т. Afte integrating O out of the joint model proba- bility, and assuming + is fixed (i.e. topics are already es- timated), we obtain the canonical MAP topic-word assign- ment problem studied by Sontag and Roy (201 1) (App. A):
log P(Z D) x Σ DED
[d]
k
log Call Dear) ).
+
log [(na, +a,)
1=1
lskelihood
spansity
k a4) log r
k
k log I(a,)
+ log
ar (++l
constant
MAP assignments are desirable for data exploration & causal inference. Maximizing eq. 1 for a set Tb of topics gives the MAP assignment i.e. the topic žd,; that each word in the dataset was probably drawn from. This is concrete, easy to interpret, and well-defined as a causal treatment.
Because our techniques are combinatorial, they permit the researcher to define the (possibly very large) 'candidate set' of topics from which the solution topics will be se- lected. This set can be obtained from existing algorithms, but this does not address the interpretability problems de- scribed above. Therefore, our third challenge is to show that it is possible to efficiently generate this candidate set of topics via standard coherence functions that are widely used to measure topics' interpretive quality ex-post. Fi- nally, our fourth challenge to show that our techniques enforce document independences (SUTVA, etc.) required for downstream causal inference frameworks. This enables causal inference research designs on documents' LDA top- ics that inherit near-optimal approximation guarantees.
MAP assignment is NP-hard even for 1 document, and we lack a practical approximation (Sontag and Roy, 2011). Instead, standard data exploration and causal in- ference applications resort to using documents' underly- ing topic mixtures 6d. which are considered more tractable (Sontag and Roy, 2011; Arora et al., 201 This is disad- vantageous, as interpreting 0g requires manually inspecting per-document k-dimensional distribution-over-ll topic- distributions (inel. many unrealized topics). Also, 0g is ill- defined as causal treatment (Fong and Grimmer, 2016).
3. MAP problem with realized topic sparsity
In this work, we take inspiration from recent techniques in clustering and feature selection (Askari et al., 2020; Khanna et al., 2017: Qian and Singer, 2019) to show that LDA's MAP assignment problem is tractable in the infi- nite limit of documents" topic sparsity prior a under ex- plicit sparsity (cardinality) constraints. In other LDA use- cases that seek documents' underlying topic mixtures Oa, is standard to choose a uniform prior over 0a by setting a=1. In contrast, 0g are nuisance parameters in our use- case, whereas over our parameters of interest: the realized MAP topic as- signments from which words were drawn. Thus, we do not have the user choose a prior a to heuristically push each document's 's underlying distribution to favor few topics. In- stead, we say (by a - oo) that all topics were equally
2. LDA MAP topic-word assignment problem
The LDA model states that the data is a corpus (set) D of documents and each document d E D is a multiset of words: d [Wi, ..., W]a]]. Suppose there are & top- ies, where each topic is distribution over all words in the vocabulary. LDA states that the text corpus is gen- erated as follows: For each document d, we sample document length |d] and document mixture distribution 02 ~ Dirichlet(a) over the topics. Then, to draw each of the d)] words in d, we sample a topic žd,; E fl,....k}, k}. where zd,i ~ (ategoricall(a)) and from this topic we sample a word wa Categorical( ..)..). where Φ. is the
corresponds to uniform probability
3

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
likely priori (each document's underlying topic distribu- tion becomes a point centered on the topic simplex), but for each document only few topics (e.g., an avg. of 4 per document) were actually drawn. This choice also conveys a linguistic advantage, as the conventional reliance on a is known to drive degenerate unimodal solutions-a main source of linguistic criticism (Gerlach et al., 2018; Wallach al.. 2009a). We now give Theorem which forms the basis of our approach. We defer the proof to App. B.
It is intractable to try all subsets Ta for each document find the unconditional MAP Za. yet we can approximate this solution for all documents. Consider a bipartite graph between topics T E o and documents d E D. Denote set of links F := (T = d) (Figs. la & lb arrows), and let Ea denote topics with links to d. We will say that words in d may only have been drawn from topic T if E includes a link from T to d. Now we see that the solution to the expression in Theorem is equivalent to maximizing the following set function:
Theorem 1. lim (argmax log P(Z
a0000
z
Objective function: S(B) max
log P(ZID,
(3)
|d| Σ
argimax Z
log Cat(wrallzids )a..))
Σ max (log o5 (voa,s) T
[d
dED =1
Our goal is now to describe a combinatorial objective func- tion that admits a fast and near-optimal solution to the above expression under the explicit sparsity constraint that each document's 's words should be assigned to few topics on average. Absent this constraint, App. D shows that sparsity (expected number of topics per document) is well approx- imated by (i/ID)) (d= e (I), yet we desire to explicitly compel sparse solutions. First, observe that if we knew the subset Ta S ① of candidate topics that were realized in single document d, then finding document d's MAP toric-word assignments, argmaxz, P(Zald (d. Ta), is easy: just assign each word to the topie in Ta with the high- est probability of drawing it: 2d,; = argmaxxera 6, (..)) Summing these gives d's max conditional log posterior:
find
argmax (F
S(E) s.t. |B| EE 2 1, vd
As LDA is a hierarchical extension of clustering (Blei et al., 2003), note that f is a hierarchical generalization of an ob- jective that is well-studied in (exemplar) clustering, data summarization, and facility location (Gomes and Krause, 2010; Lindgren et al., 2016; Mirzasoleiman al., 2015; Pokutta et al., 2020). By maximizing f subject to the car- dinality constraint |E' S Ri)D), we seek MAP solution where documents have varying counts of topics, but the av- erage number of topics linked to each document is bounded by K. Thus, choosing a smaller As yields a sparser solution.
One challenge is that ff is undefined when some document has no links in F. We address this by extending the ini- tialization technique of Gomes and Krause (2010) by link- ing each document to single improper placeholder topic p
[d]
max log P(Z)TT)) Zu
=
max(log o, (wa,))
rETa
All Condidate to sardwark :
All AlLDssuments 11
Iog posterior objective (tE)
Mr. Speaker, my good friend mentioned what how hxppened since China has joined the WTO. I think he neglectel
borders
that
defieit with
China
Chins saared, that eillions of johs have the Unittdd States to go to China...
logg postertor probabilty
defieit
disinformation
Chairnan... There misinforrstion
going the public right
of
Trag
now. found this infortunacly being passed out to vetennss in my own district...
misinformation
president
Speakor,, the way respect for the will of the taagi people ... the presidens can begin to demonetate this reapeci by parting an end the attempted menipulation of liui public opinion news writion by pezzagon
frng begins gemuine
veterans
WTO
6 1 num. loptc-doc connectionn
Ryzzyya
(a) Top: Objective ff after Greedy iteration. Note that topic-to-document link was added to solution set E.
All Candidate Topies zardvark
Decuments
log posterlor objective (05)
Mr. Speaker, good fiend mentioned liappaned since Chita has joined the WIO. think he has neglected to mention that our trade detien with China has soured, that millions States to go China...
borders
Chana
log probablit
deficit
mistnneemtionn
2.
Mr. Chaiman... There is a tremendous amount of misinfommtion that going anound the public right now, found this unfoetanately heing possed veteruas in my own district...
Irag
misinformmrinn
president
3. Mr. Spenieer, the way out of lmg begins by genaine respect for the will the people the presidett respect by putting
WIU
can begin demomstaate to the atteupted cuupulation of trag) public opinioe with fake news writenn by pestagon contracturs..
Implc-doc connections
ryznyva
(b) Bottom: j after 5 iterations. Each word is (re- Jassigned (see colors) to its most likely topic of those linked to its document per eq. 2.
Figure 1: Illustration of E-LDA approach to topic modeling. Note submodular 'diminishing returns' in f.
4

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
with infinitesimal probability on each word, then maximiz- ing (equivalent to maximizing f): f(F) ((EUP) f(P), where P is the set of placeholder topics.
marginal value (increase in the log probability objective / of one link to document d' is independent of everything ex- cept the current best topic associated with each word in d. With suitable memoizations and heap data structure, we replace an O[[$] D29) runtime factor with an Ollog (D)) factor. We can also initialize each document with its best link. App. G details our strategies for leveraging LDA's structure to obtain fast convergence.
Objective f(E) is a monotone submodular function. Observe that f is monotone, as adding more links to E can- not decrease fEE due to the max function in f. f is also submodular (see App. C): Consider the marginal value fA( == ((EUA))
f(E) of adding links A {[-=d]} to E. As the set of topics linked to dl in E grows, any topic E A will be the maximum- maximum-probabiltty topic for (weakly) fewer words in d, so it will contribute fewer terms to f. and the marginal value of adding it to E is weakly decreasing: fE(A) 2 for (4), VT E A S & de D
In this algorithm, P P|d]i|v] memoizes the log probability of each word in the data per the current iteration's 's topic-word assignments Z: P1 || memoizes the current summed log probability of each document per the current Z; M [DD (+) memoizes all current marginal values of links; and on mem- oizes each document's best not-yet-added topic and its marginal value in max-heap, so the best link can be ac- cessed in Ollog DI). We denote by O the Hadamard prod- uct, and by 1 a matrix of 1's, and we denote all entries corresponding to document d by e.g. [d,:]. We denote by EMAX(a, b) the elementwise maximum of a and b.
4. Greedy guarantees a near-optimal global & per-doc solution but is practically infeasible
Consider the simple Greedy algorithm that iteratively adds to E the link with the greatest marginal value. Because f is monotone submodular, it is well-known that Greedy returns a list of topic-document links E, where the first j links in E are a near-optimal 1 - 1/e approximation to the MAP topic-word assignments s.t. [E] < j. Thus, one chooses sparsity constraint xi DI as an upper bound, then a single run of Greedy gives near-optimal solutions for any number of topies from an average of 1 to k per document. Also, as ff is a sum of (per-document) monotone submodular functions, the topies E. that Greedy assigns to each document d obtain 1 - L/c approximation to d's optimal MAP value for any |Eal topics (see App. E). Unfortunately, Greedy is practically infeasible, as each of its D iterations is [[) (see App. F).
FastInitialize Compute each document' 's first linked topic. input Doc-word matrix D Dipix topic matrix | P D|XiV] + log(c) ..D -D
PIXIDI <- 1 1x Pp
M | + D ΦT -
4
E + the DJ links corresp. to the max value per row of M
=1p= = |D]
for link [t"=d"] E E do:
P.p. P. m -UPDATE(T*='") D, P.P.P.PP.M.... m. return E, P. p, M, m
FastGreedy---LDA Main routine.
input Doc-word matrix Dinix VV topic matrix & L|
5. Fast practical algorithms for big data
sparsity upper-bound i E, P.P. p. M, m t FASTINITTALIZE(D. T) for (K - D) steps do
We now describe how to leverage LDA's independence as- sumptions to obtain serial and parallel algorithms that find MAP solutions with these same near-optimal guarantees faster than mainstream LDA algorithms find locally modal solutions. Our algorithms solve some of the largest sub- modular optimization problems studied anywhere in terms of the size of the ground set and solution set (see App. P). We call our approach Exemplar-I.DA (E-LDA) reflect the inspiration of exemplar data summarization.
t" d' +- the topic and doc. corresp. to extract max(m)
E. +- [r"=d"]
P.P. P. M, m UUPDATE(F*=<d) D, & M,
return E
Update: Update the heap with the current log prob. of d and each word in d after adding a new link to the solution, then update marginal values of each link that includes d.
We now describe FASTGREEDY- BARREDYY--LDDAE LDA, FASTINITIAL- IZF, and the subroutine UPDATEHEAP. FASTGREEDY-F- LDA computes the ordered set E' of near optimal topics assigned to documents, which implies (via eq. 2) the near- optimal topic 2d,i from which each word was drawn. It in- herits the deterministic near-optimal guarantees of Greedy, but its iterations are exponentially faster.
input Doc-word matrix D VVi. topic matrix $ |
link (d", storage P.P. M,
pid"] pld'] + Mid", t']
P(d :| + EMAX dd .:]. $ ] O Did",
d. + Φ O Did" :l:...:DId" . :]]
Mid" :I + 1 EMAX(P(d" ;:], .a.) - -pdd']
m f- insert max M[d";:]
In brief, the key idea that enables each speedup is that the
return P.p.M.
5

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Theorem 2. FASTGREEDY-E-LLDA returns a solution E in DI iterations each of complexity O(log ||+ +( In the worst-case, f(E) is a 1 - 1/e approximation to the log posterior value of the (optimal) LDA MAP topic-word as- signments (eq. 3) subject to the user-chosen sparsity (car- dinality) constraint [E] S D); The value f (E((i) of the first j links in E is a - 1/j appreximation to the log posterior value of the optimal LDA log MAP topic-word assignments, eq. 3, subject to |E| S j: The topics Eid connected to each document d obtain a log posterior value E max Ea (log Φr (ual) that is a 1 L/e approx- imation the log posterior value of the single-document MAP topic-word assignments for document d that contain no more than |Fa) topics; The first j links in Fa give a 1 - 1fe approximation to the log posterior value of the MAP topic-word assignments for d subject to |Ea]= S j. We defer the proof to App. G.
7. Exemplar-LDA: Learning LDA on candidate set of interpretable topics
While we can obtain the candidate set & of topics from existing algorithms (see Arora et al. (2018)), this does not address the interpretability problems described above. We now show that our algorithms enable a new way to solve topic models by learning LDA from the large candidate set of all topics that meet standard interpretability criteria, Specifically, we generate interpretable candidate topics via coherence functions that are already widely used to assess topic quality post hoc. For example, UMASS coherence (Mimno et al., 201 1) measures the raw similarity between a word-of-interest wt and any other word e E V as the ra- tio of documents D'.- that contain w" to documents Dw- that contain both w* and v. st s(w", v) UMASs ID=t.vlte Any such similarity function can be used to define new topic 'about' word of interest wn by ascribing distribu- tional mass to each word u E V in proportion to s(w", .)). For example, to generate a new topic "h about the word of interest 'physics', we set ø[v] x s( s("pyssics', v) for each word in the vocabulary. A topic generated in this way has a formal interpretation, as it ascribes mass per a simple function that is known to the researcher. At a high level, such a topic is 'rigorously labeled' by its word. To obtain a candidate set & of topics, we simply generate topic for every word w² E V (or for every phrase e.g. w" E (V U 2-grams U 3-grams)). We emphasize that we don't require all topics to be good, but merely that the top- ics we want to learn are included in this large candidate set. We consider three topic generating functions:
6. Near optimal solutions in log parallel time
Because have proven that f is monotone submodu- lar, we could in theory use the recent breakthrough in low-adaptivity parallel algorithms to obtain near-optimal solutions in logarithmic parallel time (adaptivity) (Balka- nski and Singer, 2018; Balkanski et al., 2019; Breuer et al., 2020; Chekuri and Quanrud, 2019; Ene et al., 2019; Fahrbach et al., 2019). The challenge is that simulating a single query for f is [(xx tion, yielding infeasible runtimes in practice. By extending our techniques, we show we can in fact simulate each query in time that is both practically fast and independent of the size of the data DD. enabling fast parallel solutions in prac- tice. We focus on the FAST algorithm (Breuer et al., 2020) because it is practical and because it evaluates one link at a time, not sets of links, so our techniques above apply. We defer the full algorithm and analysis to App. I and J.
D(²) in a vanilla implementa-
UMass: dw- [u] s(w", v)) ,()""))UMn"
This ironically yields low-coherence solutions see Section and App. Q-
Exp-UMass: -w- x cxp(s(w", (e)s(w"""UUMa UMMAsS. This ap- proach generates high quality sparse topics.
Co-occurrence: In exemplar clustering and data summa- rization, it is standard to measure points' similarity via their features' dot product. We extend this to LDA, and the re- sult is highly performant. In LDA 'points' are documents, 'features' are words, and the dot product counts word co- occurrences. So, we generate topics via: do den-nccurrence [u] x exp( +e.. Recall that Theorem had all a priors equal for simplicity, yielding 0[r] + 1/|0/ VT. Instead, consider the case where the probability of drawing the topic associated with word w" is proportional to wn's overall popularity (total co-occurrences): if d dco-occurrence is the r'th topic, then 0[T] Evev exp((Dur.c) .el + e). Now, f sim- plifies to a (hierarchical extension of a) familiar data sum- marization objective with topics as the 'exemplars', , and we optimize on the raw dot products (App. O gives details):
Theorem 3. Breuer et al. (2020). For n: De| > 2)og(28-12)
(1(1-3))
and E (0,0.1), where E = log( log 1l)) FAST with 2+e sample complexity m -(133e) log( delo 4eloR|011D)) (211)) has at 662 20 DI + 45
most 5- [= adaptive rounds, 2s
[=I queries. and achieves 1
approximation to the log MAP topic-word assignments (eq.
3) s.t. sparsity constraint [E| < x|D) with prob. 1 - 6.
Theorem 4. For the MAP objective f. each query in FAST can be simalated in runtime that is either (Ef) or (1) with suitable memoization. We defer analysis to App. J.
(Dw
[d]
f - max [log P(Z]D,E) ΣΣ max Dww (
EB
dED
6

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
8. Near-optimal out-of-sample inference & downstream causal inference:
the semantic quality of baselines' topies to the topics that E-LDA learns when its candidate set is initialized by our topic generators. We measure topics' semantic quality via standard UMass coherence, which correlates with human quality judgments (Mimno et al., 2011; Röder et al., 2015).
We now highlight an important application for our results. There is now great excitement in the social sciences about using LDA topics as treatments for downstream causal in- ference frameworks that infer how topics cause outcomes. A key challenge is that these frameworks require (1) that treatments (topics) are independent of topic assignments, and (2) that each document's causal response is inddpen- dent of other documents' assigned topics (SUTVA). To en- force this, the gold-standard approach splits documents into training/test sets, learns a topic model on the training set, then infers test set documents' topics using (separate) out- of-sample algorithms (Egami et al., 2022). However, even if the training set L.DA model is optimally fit, standard out- of-sample algorithms used for the test set have no guaran- tees. They are also too complex to manually vet, and they are known to exhibit bias and sensitivity to random initial- ization (Wallach et al., 2009b; Egami et al., 2022). This results in spurious and/or biased causal inferences.
Code. Python code & data (see App. P) can be found at: https: /ttp:/gggthbb..t// com.//reuureLaaa///-DD
Baselines. We consider three LDA baseline algorithms, each run with & 100 topics and averaged over 10 runs per dataset: (/) Gibbs - The MALLET Gibbs LDA solver with the usual uninformative prior a=1; (2) Gibbs-Bayy Bayes (G-B)- - Gibbs with Bayesian o, tuning; (3) Gibbs-Sparse (G-S) - A Gibbs solver with a=0.1. For the log posterior experiments, we also give randk baseline equal to the log posterior of the Gibbs assignments after randomly permut- ing topics (mean of 30 permutations/rum). For topic coher- ence experiments (Experiments Set 2), we add recent neu- ral and LLM-based baselines: BERTopic (Grootendorst, 2022), AVITM (Srivastava and Sutton, 2017), ETM (Dieng et al., 2020), and FASTopic (Wu et al., 2024b).
In contrast, we can modify í to enforce the required inde- pendences for the -aa-pll test set inference. We then obtain the near-optimal 1 1 1/c approximation to each doe- ument's d's log MAP assignments in Ka iterations each of complexity that is just ()) To do this, we solve:
Datasets. We consider three well-studied social science datasets: Reuters news articles (Lewis, 1997), US Con- gressional speeches (Thomas et al., 2006), and social media posts from political news discussion boards (Lang, 1995).
Experiments Set 1 Results. Table 1 and App. P give the log posterior values of the assignments (f values). Our algorithms obtain uniformly higher probability assign- ments (p < 10-11) on all 90 experiments (3 3 baselines x 10 runs). E-LDA obtains these results despite using baselines' topics and constraining its solution to the same assignment sparsity chosen by baselines' algorithms.
Out-of-sample objective f*:
(EE)= max log P(Zald, Ea)
Σ
max (log or (wa,s) FE
find argmax ft (Ed) s.t. |Ed S Kas Eal 2 (r=d),rE0
(4)
Appendices K & M give details. The resulting MAP assignments are well-defined as treatments (unlike docu- ments' underlying topic mixtures 0z). This approach also conveys the interpretability advantages of our topic gener- ators, which are paramount in the causal inference setting.
Gibbs E-LDA randic
G-B
E-IDDA rands: |G-S
E-LDA rands
Congress
-2.05 -1.78
-10.92|
2.47
-2.22
-10.22|
2.43
-2.4
-1031
Reuters
-2.80
-2.52
-16.54
(3666
-3.43
-15.19|
3.44
4.13
-15.41
NewsGroups -1.57
-1.40
-6.71
|1.70
-1.61
-6.57
|1168
-1.55
-6.52
Table 1: Log posterior of assignments (f value) with same
9. Experiments
topics & sparsity (10 run avg., values x x10%, see App. P).
Our goal in this section is to show that beyond its prov- able guarantees and interpretability properties, E-LDA out- performs baselines in the two dimensions that social sci- ence researchers prioritize: posterior probability and topic coherence. We conduct two sets of experiments. In the first set, we solve LDA models using the main variations of the MALLET Gibbs LDA baseline (McCallum) that is standard in social science. We test whether our algorithms obtain better topic-word assignments in terms of posterior probability even when constrained to use the Gibbs topics and keep the same avg. sparsity as the Gibbs assignments.
The research-grade Python codes of our non- parallel algorithm take 2-3 sec., approximately the same time it takes for the highly optimized MALLET Java Gibbs algorithm to run just 1-2 of its ~ outer loop iterations.
Runtimes.
Experiments Set 2 Results: Topics' Semantic Quality. Fig. 2a compares the mean topic coherence of our solu- tions to baselines. E-LDA CO-OCCURRENCE and EXP- UMASS solutions obtain 2.53-4.20 and 1.18-1.67 times better mean coherence, respectively, compared to the Gibbs topics when coherence scores computed based on the 5 top words per topic (leftmost points in Fig. 2a). This suggests that E-L.DAss topics are significantly better than
In the second set of experiments, we add neural and LLM/BERTTbaasdd topic model baselines, and we compare
7

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Reuters
Congress
NewsGroups
E-LDA co-occumence
sip-UMess
E-IDA UMass
Gayes
Gibba-spane
BERTopic
ETM
-1-
Popi
10
15
25
10
15
25
10
15
20
25
num. top words in topic
top words In topic
num. top words in topic
Experiments Set 2: E-LDA topic coherence vs. baselines for various num. top words h" (10 run avg.).
Reuters
Congress
NewsGroups
minan colarence
co-occurrence
mean
E-LDA expsUMass
2.5
7.5
10
2,5
7,5
10
2.5
5.0
7.5
10.0
topics per doc
topics per doc
topics per doc
(b) Consistency E-LDA's coherence as solutions grow from sparse to dense, 1 1-+10 topics-per-documeet.
Gibbs topies at conveying small and closely-related set of 'keywords' that are more semantically evocative of their topic's subject matter. As we recompute coherence based on h* 10, ................................ 25 top words per topic (rightmost points in Fig. 2a), E-LDA CO-OCCURRENCE and EXP-UMASS topics outperform Gibbs by a factor that increases to 2.92- 3.21 and 1.93-2.33, respectively. This suggests that each E-LDA topic also captures more subtle semantic relation- ships beyond a handful of keywords, whereas Gibbs topics tend exhibit more noise their top words. Because coherence is a logarithmic mea- sure, E-LDA's several-fold improvement may be viewed as an exponential improvement in the degree to which E- LDA topics emphasize co-appearing words. Sparse and Bayesian variants of the Gibbs baselines improve slightly over the standard Gibbs on 2 of the 3 datasets, but nei- ther obtains the semantic quality of CO-OCCURRENCE and EXP-UMASS. Disaggregating the results, note that (i) E-LDA CO-OCCURRENCE'S plotted mean topic coherence outperforms the best single topic's 's coherence of all Gibbs baselines' topics; and (ii) E-LDA CO-OCCURRENCE worst topic's coherence outperforms the mean topic coherence of all Gibbs baselines. This holds regardless of h²
to ETM (better on Reuters, slightly worse on NewsGroups).
Fig. 2a also plots the coherence of E-LDA initialized with unmodified UMASS topic generator. This basic approach performs relatively poorly (see App. Q), sug- gesting that E-LDA's high coherence obtained via Co- OCCURRENCE and EXP-UMASS topics are indicative of high semantic quality and not simply due to their gener- ating function's similarity the function used to compute post hoc coherence. We note that the candidate three of our topic generators have identical mean coherence (coherence only depends on ranking, which is invariant to the exponential). The mean coherence of the candidate sets is 22.9, -1.9, -1.8 for Reuters, Congress, and NewsGroups. Observe that these mean coherences are significantly worse than the mean coherence of CO-OCCURRENCE and EXP- UMASS solutions topics in Fig. 2a. This is because our algorithms tend to select high-coherence topics from the candidate set under these (sparser) topic generators.
of all
move down the list of
Consistency of E-LDA's semantic quality advantage across sparse and dense solutions. Fig. 2b plots the con- sistency E-LDA's topic coherences as we grow its solu- tions from a maximally sparse arrangement of topic-per- document (equivalent
document clustering) to a rel- atively dense 10 lopics-per-docuneee Here, observe that E-LDA's solutions exhibit remarkable consistency in terms of their high coherence regardless of the sparsity of the desired solution size. In short, E-LDDA returns solutions of consistently high semantic quality regardless of whether researchers set them produce a simple and sparse sum- mary of their text data nuanced and dense one.
Considering neural and LLM-based baselines, E-LDA CO-OCCURRENCE outperforms BERTopic, AVITM, and FASTopic by factors of 3.04-4.70, 5.96-10.17, and 2.24- 5.84, respectively. It also outperforms ETM by factors of 1.19-2.36, despite the fact that ETM was designed as a coherence-improving algorithm. E-LDA EXP-UMASS out- performs BERTopic, AVITM, and FASTopic by factors of 1.46-2.72, 3.08-7.09, 1.48-2.67 resp., and compares well
8

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
10. Conclusion
able guarantees. In International conference on machine learning, pages 280-288. PMLR, 2013.
In this paper, we showed a novel combinatorial approach to topic modeling that efficiently and near-optimally solves LDA topic-word assignments under explicit sparsity con- straints. We also showed that approach permits practi- tioners to restrict the learned topics to those that meet stan- dard interpretability criteria. Importantly, these guarantees and interpretability properties also apply when topics are used for causal inference. Finally, we showed that this ap- proach learns topics of high semantic quality.
Sanjeev Arora, Rong Ge, Ravi Kannan, and Ankur Moitra. Computing nonnegative matrix factorization provably. SIAM Journal on Computing, 45(4):1582- 1611, 2016a.
Sanjeev Arora, Rong Ge, Frederic Koehler, Tengyu Ma, and Ankur Moitra. Provable algorithms for inference in topic models. In International Conference on Machine Learning, pages 2859-2867. PMLR, 2016b.
We have focused on LDA and sparsity constraints because these the most practical tools for social science re- search. However, we emphasize that our techniques gen- cralize to many topic model variations. They can also be solved under more sophisticated constraints such as pack- ing or matroid constraints that permit significant flcxibil- ity compared to standard algorithms in terms of encoding domain-specific information into text models.
Sanjeev Arora, Rong Ge, Yoni Halpem, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, and Michael Zhu. Learning topic models provably and efficiently. volume 61, pages 85-93. ACM, 2018.
Elliott Ash and Stephen Hansen. Text algorithms eco- nomics. Annual Review of Economics, 15(1):659-688 2023.
Acknowledgments
Armin Askari, Alexandre d' Aspremont, and Laurent El Ghaoui Naive feature selection: Sparsity in naive bayes. In International Conference on Artificial Intelli- gence and Statistics, pages 1813-1822. PMLR, 2020.
The author is grateful for research support from OpenAI, and for valuable comments and suggestions from Maximilian Fox, Kosuke Imai, Alastair Iain Johnston, and Brandon Stewart.
Eric Balkanski and Yaron Singer. The adaptive complexity of maximizing a submodular function. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pages 1138-1151, 2018.
Impact statement
Mainstream social science applications for topic models models include text modeling for ethically fraught areas. For decisionmaking in such areas, it is ethically desirable and, increasingly, legally mandated to adopt models with strong guarantees and/or interpretability properties (Mad- iega, 2021). While neural and LLM/BERT-baseee topic models have recently shown impressive fidelity for text modeling in general, they lack such properties. We see our work as addressing this important gap.
Eric Balkanski, Aviad Rubinstein, and Yaron Singer. An optimal approximation for submodular maximization under a matroid constraint in the adaptive complex- ity model. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 66- 77, 2019.
Pablo Barberá, Andreu Casas, Jonathan Nagler, Patrick J Egan, Richard Bonneau, John T Jost, and Joshua A Tucker. Who leads? who follows? measuring issue at- tention and agenda setting by legislators and the mass public using social media data. American Political Sci- ence Review, 183(4))8839901, 2019.
References
Anima Anandkumar, Dean P Foster, Daniel J Hsu, Sham M Kakade, and Yi-Kai Liu. A spectral algorithm for latent dirichlet allocation. Advances in neural information pro- cessing systems, 25, 2012.
Laura Battaglia, Timothy Christensen, Stephen Hansen, and Szymon Sacher. Inference for regression with vari- ables generated by machine learning. arXiv preprint 24Xiv:2402.15588 2024.
Sanjeev Arora, Rong Ge, and Ankur Moitra. Learning topic models- going beyond svd. In 2012 IEEE 53rd annual symposium on foundations of computer science, pages 1-10. IEEE, 2012.
Jordi Blanes Vidal, Mirko Draca, and Christian Fons- Rosen. Revolving door lobbyists. The American Eco- nomic Review, 102(7):3731, 2012.
Sanjeev Arora, Rong Ge, Yonatan Halpern, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, and Michael Zhu. practical algorithm for topic modeling with prov-
David M Blei, Andrew Y Ng, and Michael Jordan. La- tent dirichlet allocation. Journal of machine Learning research, 393 2003.

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Adam Breuer, Eric Balkanski, and Yaron Singer. The fast algorithm for submodular maximization. In Interna- tional Conference on Machine Learning, pages 1134- 1143. PMLR, 2020.
Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadi- moghaddam. Submodular maximization with optimal approximation, adaptivity and query complexity, SODA, 2019.
Leland Bybee, Bryan Kelly, Asaf Manela, and Dacheng Xiu. Business news and business cycles. The Journal of Finance, 3955:310533 2024.
Amir Feder, Nadav Oved, Uri Shalit, and Roi Reichart. Causalm: Causal model explanation through counterfac- tual language models. Computational Linguistics, 47(2): 333-386 2021.
Amy Catalinac. From pork to policy: The rise of program- matic campaigning in Japanese elections. The Journal of Politics, 78(1):1-18, 2016.
Amir Feder, Katherine A Keith, Emaad Manzoor, Reid Pryzant, Dhanya Sridhar, Zach Wood-Doughty, Jacob Eisenstein, Justin Grimmer, Roi Reichart, Margaret E Roberts, et al. Causal inference in natural language pro- cessing: Estimation, prediction, interpretation and be- yond. Transactions of the Association for Computational Linguistics, 10: 138-11811 2022.
Jonathan Chang, Sean Gerrish, Chong Wang, Jordan Boyd- Graber, and David Blei. Reading tea leaves: How hu- mans interpret topic models. Advances in neural infor- mation processing systems, 22, 2009.
Chandra Chekuri and Kent Quanrud. Submodular function maximization in parallel via the multilinear relaxation. SODA, 2019.
Christian Fong and Justin Grimmer. Discovery of treat- ments from text corpora. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 1600-1609, 2016.
Siddhartha Chib. Marginal likelihood from the gibbs out- put. Journal of the American statistical association, 90 (432):1313-1321, 1995.
Christian Fong and Justin Grimmer. Causal inference with latent treatments. American Journal of Political Science, 67(2):374-385 2023.
Adji B Dieng, Francisco JR Ruiz, and David Blei. Topic modeling in embedding spaces. Transactions of the Association for Computational Linguisties, 8:439 453, 2020.
Martin Gerlach, Tiago P Peixoto, and Eduardo G Altmann. A network approach to topic models. Science advances, 4(7):eaaq 2018.
Bryce J Dietrich, Matthew Hayes, and Diana Z O' O'brien. Pitch perfect: Vocal pitch and the emotional intensity of congressional speech. American Political Science Re- view, 113(4):941-662 2019.
Ryan Gomes and Andreas Krause. Budgeted nonparamet- ric learning from data streams. In ICML, volume 1, page 3. Citeseer, 2010.
Thomas L Griffiths and Mark Steyvers. Finding scientific topics. Proceedings of the National academy of Sci- ences, 101
Milena Djourelova. Persuasion through slanted language: Evidence from the media coverage of immigration. American economic review, 113(3):800-835, 2023.
2004.
Justin Grimmer, Margaret Roberts, and Brandon M Stew- art. Text as data: A new framework for machine learn- ing and the social sciences. Princeton University Press, 2022.
Finale Doshi- Velez, Byron C Wallace, and Ryan Adams. Graph-sparse Ida: topic model with structured spar- sity. In Twent-Ninth AAAI conference on artificial in- telligence, 2015.
Maarten Grootendorst. Bertopic: Neural topic model- ing with a Mlass-base tf-idf procedure. arXiv preprint arXiv:2203.0577 2022.
Naoki Egami, Christian J Fong, Justin Grimmer, Mar- garet E. Roberts, and Brandon Stewart. How to make causal inferences using texts. Science Advances, 8(42): eabg2652, 2022.
Carlos Guestrin, Andreas Krause, and Ajit Paul Singh. Near-optimal sensor placements in gaussian processes. Proceedings of the 22nd international conference on Machine learning, pages 265-272 2005.
Alina Ene, Huy L Nguyen, and Adrian Vladu. Submodular maximization with matroid and packing constraints in parallel. STOC, 2019.
David Hall, Dan Jurafsky, and Christopher D Manning. Studying the history of ideas using topic models. In Pro- ceedings of the 2008 conference on empirical methods in natural language processing, pages 363-371, 2008
Shusei Eshima, Kosuke Imai, and Tomoya Sasaki. Keyword assisted topic models. arXiv preprint 05X45:2004.05664, 2020.
10

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Zhiting Hu and Li Erran Li. A causal lens for controllable text generation. Advances in Neural Information Pro- cessing Systems, 34:24941-24955, 2021.
Ming- Yu Liu, Oncel Tuzel, Srikumar Ramalingam, and Rama Chellappa. Entropy-rate clustering: Cluster anal- ysis via maximizing a submodular function subject to matroid constraint. IEEE Transactions on Pattern Anal- ysis and Machine Intelligence, 36(1):99-112, 2013.
Rishabh Iyer and Jeffrey Bilmes. A memoization frame- work for scaling submodular optimization to large scale problems. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2340-2349. PMLR, 2019.
Tambiama Madiega. Artificial intelligence act. European Purliament: European Parliamentary Research Service, 2021.
Zheng Tracy Ke, Pengsheng Ji, Jiashun Jin, and Wanshan Li. Recent advances in text analysis. Annual Review of Statistics and Its Application, I1())annurev, 2024.
Gregory J Martin and Joshua McCrain. Local news and na- tional politics. American Political Science Review, 113 (2):372-384, 2019.
Rajiv Khanna, Ethan Elenberg, Alex Dimakis, Sahand Ne-
Andrew Kachites McCallum. Mallet: A machine learning for languagetoolkit. http://mallet. cs. umass. edu.
gahban, and Joydeep Ghosh. Scalable greedy feature se- lection via weak submodularity. In Artificial Intelligence and Statistics, pages 1560-1568 PMLR, 2017.
David Mimno, Hanna Wallach, Edmund Talley, Miriam Leenders, and Andrew McCallum. Optimizing seman- tic coherence in topic models. In Proceedings of the 2011 conference on empirical methods in natural lan- guage processing, pages 262-272, 2011..
Ken Lang. Newsweeder: Learning to filter netnews. In Machine learning proceedings 1995, pages 331-339. El- sevier, 1995.
Jey Han Lau, David Newman, and Timothy Baldwin. Ma- chine reading tea leaves: Automatically evaluating topic coherence and topic model quality. In Proceedings of the 14th Conference of the European Chapter of the As- sociation for Computational Linguistics, pages 530-539, 2014.
Michel Minoux. Accelerated greedy algorithms for maxi- mizing submodular set functions. In Optimization tech- niques, pages 243.243. Springer, 1978.
Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization: Identifying representative elements in massive data. In Advances in Newral Information Processing Systems, pages 2049-2057, 2013.
Benjamin Lauderdale and Tom Clark. Scaling po-
litically meaningful dimensions using texts and votes. American Journal of Political Science, 58(3):754-771, 2014.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
David Lewis. Reuters-21578 text categorization test col- lection. Distribution 1.0, AT&T Labs-Research, 1997.
Wei Li and Andrew McCallum. Pachinko allocation: Dag- structured mixture models of topic correlations. In Pro- ceedings of the 23rd international conference on Ma- chine learning, pages 577-584, 2006.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submodular maximiza- tion: Personalized data summarization. In ICML, pages 1358-1367, 2016.
Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Proceedings of the 49th annual meeting of the association for computational lin- guistics: human language technologies, pages 510-520, 2011.
Iman Modarressi, Jann Spiess, and Amar Venugopal. Causal inference outcomes learned from text. arXiv preprini arXiv:2503.00725. 2025.
Hannes Mueller and Christopher Rauh. Reading between the lines: Prediction of political violence using news- paper text. American Political Science Review, 112(2):
Erik Lindgren, Shanshan Wu, and Alexandros G Dimakis. Leveraging sparsity for efficient submodular data sum- marization. Advances in Neural Information Processing Systems, 29, 2016.
358-375, 2018
George L Nemhauser and Laurence A Wolsey. Best algo- rithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3(3): 177-188, 1978.
Zachary Lipton.. The mythos of model interpretability: In machine learning, the concept of interpretability is both important and slippery. Queue, 16(3):31-57, 2018.

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
George L. Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical Program- ming, (4(1):265-294 1978.
floor-debate transcripts. In Proceedings the 2006 Con- ference on Empirical Methods in Natural Language Pro- cessing, pages 327-335, 2006.
Dustin Tingley. Rising power on the mind. International Organization, pages S165-S188, 2017.
Michael Newton and Adrian E Raftery. Approximate bayesian inference with the weighted likelihood boot- strap. Journal of the Royal Statistical Society Series B: Statistical Methodology, 56(1):3-26, 1994.
Victor Veitch, Dhanya Sridhar, and David Blei. Adapt- ing text embeddings for causal inference. In Conference on Uncertainty Artificial Intelligence, pages 919-928. PMLR, 2020.
Jennifer Pan and Kaiping Chen. Concealing corruption: How chinese officials distort upward reporting of online grievances. The American Political Science Review, 112 (3):602-620) 2018.
Hanna Wallach, David Mimno, and Andrew McCallum. Rethinking Ida: Why priors matter. Advances in neural information processing systems, 22, 2009a.
Judea Pearl. Causality. Cambridge university press, 2009.
Hanna M Wallach, lain Murray, Ruslan Salakhutdinov, and
Sebastian Pokutta, Mohit Singh, and Alfredo Torrico, On the unreasonable effectiveness of the greedy algorithm: Greedy adapts to sharpness. In International Conference on Machine Learning, pages 7772-7782. PMLR, 2020.
David Mimno. Evaluation methods for topic models. In Proceedings of the 26th annual international conference on machine learning, pages 1105-1112, 2009b.
Hanna Megan Wallach. Structured topic models for lan- guage. PhD thesis, University of Cambridge Cambridge, UK, 2008
Sharon Qian and Yaron Singer. Fast parallel algorithms for statistical subset selection problems. In Advances in Neural Information Processing Systems, pages 5073- 5082, 2019.
Xiaobao Wu, Xinshuai Dong, Thong Thanh Nguyen, and Anh Tuan Luu. Effective neural topic modeling with embedding clustering regularization. In International Conference on Machine Learning, pages 37335-37357. PMLR, 2023.
Michael Röder, Andreas Both, and Alexander Hinneburg. Exploring the space of topic coherence measures. In Pro- ceedings of the eighth ACM international conference on Web search and data mining, pages 399-408, 4099 2015.
Xiaobao Wu, Thong Nguyen, and Anh Tuan Luu, A survey neural topic models: methods, applications, and chal- lenges. Artificial Intelligence Review, 57(2):18, 2024a.
Donald B Rubin. Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of educational Psychology. 66(5):688, 1974.
Xiaobao Wu, Thong Nguyen, Delvin Zhang, William Yang Wang, and Anh Tuan Luu. Fastopic: Pretrained trans- former is fast, adaptive, stable, and transferable topic model. Advances in Neural Information Processing Sys- tems, 11844477-8488. 2024b.
Donald B Rubin. Randomization analysis of experimental data: The fisher randomization test comment. Journal of the American statistical association, 75(371):591-593, 1980.
David Sontag and Dan Roy. Complexity of inference in la- tent dirichlet allocation. Advances in neural information processing systems, 24, 2.11.
Xiaobao Wu, Fengjun Pan, and Luu Anh Tuan. Towards the topmost: A topic modeling system toolkit. In Proceed- ings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 3: System Demon- strations), pages 31-41, 2024c.
Akash Srivastava and Charles Sutton. Autoencoding vari- ational inference for topic models. arXiv preprint 17X1v:1703.01488, 2017.
Luwei Ying, Jacob M Montgomery, and Brandon M Stew- art. Topics, concepts, and measurement: A crowd- sourced procedure for validating topics as measures. Po- litical Analysis, 30(4):570-58, 2022.
Silvia Terragni, Elisabetta Fersini, Bruno Giovanni Galuzzi, Pietro Tropeano, and Antonio Candelieri. Oc- tis: Comparing and optimizing topic models is simple! In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguis- lics: System Demonstrations, pages 263-270, 2021.
Matt Thomas, Bo Pang, and Lilliam Lee. Get out the vote: determining support or opposition from congressional
12

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
A. The LDA Model & Integrating out 0d
The LDA model states that the data is a corpus (set) of documents, where each document D is multiset words: = [wy..... w14]- Suppose there are k topics, where each topic is a distribution over all words in the vocabulary. LDA states that the text corpus is generated follows: For each document d, we sample a document length di and document mixture distribution 0₂ Dirichlet(a) over the k topics. Then, draw each of the |d] words in d, sample topic dds E (l,...,A)) k.), where ād,i Culeggorical(0a (0a), and from this topic we sample a word Wafi Calegorical where 63 is the distribution over all words corresponding to topic 2:
LDA generative model
input Corpus D of empty documents (multisets) di...., di topics Φ1 0R. parameters À for document d E D
draw document length |d] ~ Poisson(A)
draw document distribution over topics 0₂ ~ Dirichlet(a)
for document- word index = 1,...,
draw topic Zd, (ate draw word wa, (ategoricall
dii] f- Wd,
return D
Now, denote by Z all latent topics zd,; corresponding each word in D; by O all documents' topic mixtures ( D and by & the set of all topics ( dx The joint model probability is:
[d] II
la, B,A) = II dED t=1
Cat(za,100) x II Dir(Osla) dED
(5)
[d] Cat(wa,lza,s rsa.) x II
II II dED
Dir(ox13,) x II
Poi(ld] X)
T=1
dED
The second Dir term is the Dirichlet(3) prior on topics, and ej and 02 are normalizing constants.
Documents' topic mixtures 0u can be integrated out of LDA's joint probability follows. We seek:
d
P(Z, 4 (1, x
Cat 10)) x Cı II
Dir(Oala) d0s deD
D 1=1
bdl
x II
Cat(waslzass &ea.) x II Dir(du13,) x II
Poi(ld] A)
de D ==
dED
Documents are conditionally independent from each other. Denote the last three terms by Q:
[d] II
II dED
Cat(za,10a) x ci II (ir(Oala) daa Ω E=1
dED
Now, denote by 0,.7 and a, the 7'th elements of fg and a, respectively. Substituting the standard Dirichlet prior, we have:
r a7) I ((a)) r=1
II 00 II 1=1
0s,ea dd x Ω
deD D
Changing variables in the product over each documents' words, and letting nd,- denote the count of words in document d
13

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
that are assigned to topic so Yd, L, we have 0 S ndd, S |d];
VId| Σ
nd,r = [d]. We have:
(7))
II dED
r=
02. d0, x
(((r))
d,T
r=1
r=1
II
T=l (r)
00 +0,+,
+nd, -1 d0 Ω
DED
7=
[(a+)
Multiplying by fraction that equal to 1:
II re== ar) IT= [(ndr + aa)) dED II== [(a+) r Rd, + a+)
T( Bd. + a,)
II
gartns---1
d0a x 9
d,r
M(nd,r + a+)
==1
Observe that the integral is now over the entire domain of a Dirichlet PDF, so it evaluates to 1:
a+) II. [(na,r + a+)
II IED
(a,
r Adrr + a7)
[d]
x
II d=
Cat(waslzdi dra.) x 02 II Dir(ox18,) x II Poi([d] X) dED
(6)
Ignoring the nuisance document length term (which is standard (Blei et al., 2003)), then for a fixed set of topics we arrive at the canonical MAP topic assignment inference problem studied seminal work by Sontag and Roy (2011). Taking logarithms of the following gives the expression in Section 2:
P(ZID) x II T( (c)) II T(na, + ar)
[d]
II s=1
Cat(wa, deas))
(7)
r a + (d) II I((a))
deD
B. Deferred proof of Theorem
Theorem.
d log Cat (ai,aallzzd &zca)
lim (argmax log P)) = arrgmax a 000
(8)
z
dED
Proof. From Section
we have:
log D)
Σ
log Cot(wa, Zd,is Pzae)
log [(na, + a7)
deD
likelshond
sparsity
log r
a7) log T
Or + [d)
log T(ar)
We will the following well-known asymptotic property of P functions: for E C. lim I(g + +r) I(g)q", After
taking logs and rearranging, have the property lim,-po log (og(T())))
T(ko+r) log(kq) for 0.
14

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Consider the limit for single document, and let L denote the likelihood term that is independent of a. Rearranging,
have:
r ai + +d))
& Σ
P(a + nd.r)
+ L)
lim
log
log
a
r( R
(c))
T(a:)
T=1
I'kk + (d) ((ka)
l' + Tdd,))
k
-lim
log
log
+0
Σ r=1
0
+ C
[(xx)
T=l
Applying our asymptotic property with q ka, r= |d] and noting k. > 0 we have:
r(ka [d])
T(a + md,7)
lim
log
Σ log
r(ka)
I(a)
a-+00
r(ka + [d])
k -
+ log
|d] log(ko))
Σ r=1
0 +
T(ka)
I + na.s) T(a)
-im
log
|d| log(ka)
Σ
Applying our asymptotic property & times with a, nd. for 1... k we have:
I(a + na.r)
k
I(a na,r) nd, log az )) + L r(a)
lim
log
|d] log(ka)
log
a-+00
I(a)
k
lim
dd log(ka) + Σ
nd, log a +
a-+20
lim
|d| log(ko) + log + L
a-100
lim
|d| log k
L
|d] log k:
After substituting for L and adding up this single-document limit over all documents have:
|d log Cat(w, Snd))
lim (argmax log P(Z(D)) = arrgmax - 000
log(k))
Σ
|d +
Z
dED
d=
[d]
argmaa
log Cat 24,4 Dara) as the left term above is const. independent of a.
dED 1=1
C. Deferred proof of submodularity Recall that original objective function f from eq. is:
Objective function: f(E) max [log P(Z)D, E']
(10)
max (log di (wa,))) EEE
dED
find
argmax FE
f(L) s.t. | < R|D Eal 2 1, Vd
We noted that one challenge is that f is undefined when some document has no links in E. We addressed this by extending the initialization technique of Gomes and Krause (2010) by linking each document to single improper placeholder topic p
15

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
with infinitesimal probability on each word, then maximizing / (equivalent to maximizing f: ((BUP) I(P), where P is the set of placeholder topics.
We now show that objective f(E) is monotone submodular function. First, observe that the objective f is monotone, as adding more links to E cannot decrease f(E) due to the max function. Now, consider the marginal value fe(A) = ((EUA) f(E) of adding links A = {[T = d} to E.
(A(A)) = - ((E) is our marginal value function. (f(EUP)
=f(EUAUP)- - -11 f(P))
dd
14
max dED ((ELUUU
(log G,,' (wa,))) -
ΣΣ
dED Σ
max (log o, (wa,e)
EP
[d|
max (log o- (wa,))) - Σ (E(UU
max (log o," [wa
T"EP EP
dED i=
dED 1=1
14
ΣΣ
max (E(UUU
(log o,, (wa,s)
Σ
max (log (+(wa,))) rE(BaUP)
(11)
dED
dED
For a single document d, we have:
dd
[d]
max "EEEUAUP))
(log (waas)
max (log or (wa,s)) FE(UU
[d]
max (E((EUAUP)
(,og,,(waa,)))
max TE(EUUP)
(log or [wa
A'
Denote by 1(.) a function that takes the value of 1 its argument is true and 0 otherwise. Now:
[d]
(((
max(log (wa,)) ''EA
max (log oh (wa,))) 1 m rE(F.UP)
max (Ør (dr(wa,)))) (12) rE(PoUP)
EA
Observe that as the set Ea grows (i.e. Eg is expanded to include more topics linked to d), the first term, max,' EA (log oe (w,,l)))) is fixed and the second term, maxre(E,urg) (log Φ (wa,]), is nondecreasing. Therefore, observe (1) the sum E max, (log , (wa,s)) max,e(F (log or [wa,,)) is nonincreasing. Then observe (2) that any topic A will be the maximum- -oooouaiiltobbottttyyyoooy topic for (weakly) fewer words in d, thus it will contribute (weakly) fewer terms to f due to the 1(-) function. Putting these together, we have that the marginal value of adding A to Eg is weakly decreasing as Ea grows: (F,(() 2 Jry (A), VAa C. EG T T A C b and d E D.
Finally, this analysis supposed corpus of single document. However, per line 11, f is a sum of |D] per-document submodular functions. Sums of submodular functions are also submodular.
D. Unconstrained problem formulations & expected number of unique topics per document
Observe that in the unconstrained case (i.e. where each document can have unlimited topics up to one unique topic per word), then finding d's MAP topic-word assignments, argmax,, P(Zal d), is easy. In that case, we just assign each word in the data to the topic in with the highest probability of drawing it: 24,; = argmax,eæ Φ (.all Summing these, we have:
14
max log P(ZID)
Σ
max(log of (wa,l) T
(13)
deD =11
16

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
However, this unconstrained problem returns practically unusable, maximally overfit solutions where each word in docu- ment may be associated with a different topic. In the analysis below, show below that in the unconstrained problem, the expected number of unique lopies-per-document is well-approximated by [ e -111/19). For practical-sized datasets such as (for example) Twitter datasets commonly used in social science research, | exceeds the word count of any single document (Tweet). In that case, the unconstrained MAP solution assigns each document a number of unique topics that approaches one unique topic-per-word. In other words, the unconstrained MAP solution returns a 'worst-case overfit'. Even when the number of topics is the same as the wordcount of a document (e.g. 100), the unconstrained problem's 's MAP solution assigns each 100-word tweet [ e -4 100 e --10/1100 z 63.2 unique topics per 100-word document in expectation. As such, the unconstrained problem formulation yields unusably dense solutions for practical problem instances.
Indeed, as we discussed in Section 2, one of the primary problems with using documents' underlying distributions Og for downstream social science analysis is that for many practical datasets such as Twitter data, the number of topics required to adequately model the dataset exceeds the length of any document: > |d]. As such, a document's 's underlying topic distribution vector 0& is not a dimensionality reduction (which often the goal of using L.DA social science application domains), but dimensionality expansion. Absent sparsity constraint, the MAP topic-word assignments exhibit similarly undesirable dimensionality. These issues motivate our pparsity-constrain
problem formulation.
More formally, we obtain the expected average number of topics per document in the MAP solution for a given uncon- strained problem (i.e. where each document can have unlimited topics up to one unique topic per word) as follows. For a
single document, in the infinite limit of a the probability of drawing zero words from topic T is (+1-1) [0
[4]
The prob-
ability of drawing at least one word from topic the complement - -11 [d]
Therefore the expected number
of unique topics in document d is [ [1 [ J. To understand how this scales, we can rearrange and use the |d]
(1
standard limit approximation to obtain the useful approximation [ [10 -1)
~ [ e e-14//19)).
[+]
To obtain the expected average number of unique topics per document in the corpus, we just take the expectation over all
documents, 1 EdeD C - (0())1) |d|
= 1011-1111 1/1D1) =1
Edep(1-
Applying this to our approximation
[D]
[
gives [ - (1-1 EsED(1 - 1/|$/) d1
[D]
Unconstrained problem with known 0. Alternatively one could also consider a variant of the unconstrained problem formulation where we assume that documents' underlying topic distributions 0₂ are also known. In that case, we could easily obtain the MAP topic-word assignments by maximizing:
max log P(ZID)
ΣΣ
Σ
maxg (2(r] (+(w,)))) reb
(14)
dED
However, the assumption that fu are known is very strong. Mainstream algorithms such as Gibbs provide no guarantees for 0g It is possible to obtain estimates of 0g via e.g. the algorithms of Arora et al. (2016b), but these algorithms yield 0g with errors that are o(1 (()) In other words, for that approach, solutions that are more desirably sparse exhibit more errors in terms of 0a yielding more errors in terms of the resulting MAP topic-word assignments. We contrast these problems with the near optimal deterministic guarantces of our approach.
E. Simple Greedy Algorithm
Consider the simple Greedy algorithm that grows the solution set of (opic-to-document links by iteratively adding the link with the greatest marginal contribution to f. We formalize this algorithm and derive its complexity below. While it is prac- tically infeasible, it has near-optimal global and per-document approximation guarantees. Our optimized FASTGREEDY- E-LDA algorithm accelerates this simple Greedy algorithm while maintaining the same guarantees.
17

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Sinpi--Gredyy-E-L..AA
input Corpus D, Candidate topic set o Sparsity constraint upper- initialize E <- P for x| D steps do
upper-bound bound Phantom topic links P
T d=] + the topic-doc link that adds the highest marginal value, argmax SN((T + d))
rE0,EED
E t -r==0 dr) return EXP
Where each phantom topic Ophantom in the phantom topic links a topic with constant (improper) small probability on all words, e.g. [1-10]IV].
1-1/e Approximation Guarantee. For completeness, we show SIMPLE-GREEDY' 1/ee approximation guarantee via the classic result of Nemhauser and Wolsey (1978). Let EOPT denote the optimal (maximum value) solution size k|D), with value P(EOPT) OPT. Let E' denote its iterations 0 < S D|D]:
solution at iteration i. We claim via induction that for
- - 5(1 (1- K F(EOPT)
(15)
This is trivially true for i = O. First, consider SIMPLE-GRES GREEDY'S solution Ei-1 at a previous iteration i 1. Because there are 10\E"~11 I x| D| more elements in EOPT than in Ei-1, and the 'best' one we can add E now is what EMPLE-GREEDY will add first, then we have (by subadditivity):
((EOPT) - j(Ei-t)
Σ (a)
OE DEFOPTIES (
(f(EOPT) -fo---j(--)) f(E S fa))
(16)
K D
Now, returning to our hypothesis, we expand left-hand-side (i.e. 'separate out' the last link that was added to SIMPLE- GREEDY'S solution at iteration i):
((EOPT) j(E') i(EOPT) ((EE)) j(E - is: (ai;)
j(DOPT)- - x -((0PP)-(((--1)) substituting eq. 16
-1 x!D| -(LLEOTT)((E"""
1
$ (1 1
wD)) f(EOPT)
Now set i = x|D), rearrange, and use (1 | < 1/e to obtain f(E) 2 (1 1/P)OPT.
F. Complexity of SIMPLE-GREEDY
We now derive the complexity of the vanilla SIMPLE-GREEDS algorithm described in Section 4 and compare it to the ACCELERATTED--GREDDEEEE.
algorithm described here:
Simple-Greedy completes in ki x iterations. Each iteration i of Cemple-Greedy computes the marginal value of [ -i links. Without the speedups described in BASTGREEDY-E-LDAA computing one of these marginal values entails solving U + d)) f(E'), where [T + d) is a new topic-doe link (where E* denotes the solution at iteration i). Computing a value of f requires, for each document in D, finding the max log probability of each word in d among Eg topics (or Ea + 1 topics for f(E' [r = d)), then summing the result. Denote the number of words in the longest document by Thus each marginal value requires Eall)) which is OEk) ). An iteration of Simple-Gree Greedy requires computing O (D)) such marginal values, so each iteration (
18

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
G. FASTGREEDY-E-LDA details and analysis
We now describe the main ideas we use to obtain FASTGREDY-E-LDA'S fast theoretic and practical runtimes while maintaining the deterministic near-optimal guarantees of the vanilla SIMPLEGREEDY algorithm. We analyze complexity below.
Improving the per-iteration complexity by the first DD Simple-Greedy evaluates the marginal value of all [D] @ links each iteration. These costly operations can be avoided through thoughtful design. Specifically, after link [r* + d'] added to the solution set E, the topic-word assignments for document d' may be updated, but these are independent of all other documents' assignments in LDA. Therefore, the marginal value of all links that do not include d' are unchanged in the next iteration. These may be memoized (lyer and Bilmes, 2019) rather than recomputed, so each iteration we only need to recompute marginal values of at most | remaining links to d'. Then, rather than check the maximum marginal valued link out of the [ links to add to our solution each iteration, we save and update the best link for each document in a max-heap. Thus, we extract the best element in O(log (D)) instead of O( DD)).
Improving the per-iteration complexity by another 2| D|fftooor. In vanilla implementation, computing a single marginal value of new link [T = d] requires summing over the log- preebabbbilities of all [D] documents. However, due to the conditional independence of documents in LDA, only the log probability of d' changes each iteration. After cancelling these terms from the difference fæ([T + d)) = f(E [T + d) fE(),, we can compute the marginal value of SE[[T= = d] by summing only over the words in d, which accelerates computation by a factor of D| each iteration.
Improving the per-iteration complexity by another x--fctor. We can also memoize the log probabilities associated with the current topic-word assignments 21,d- Then, when compute marginal value, we need not find the max log probability for each word among the Eg topics connected to d, which saves an additional x factor per iteration.
Fast start. Because documents in LDA are conditionally independent and each document must be drawn from at least one topic, we can efficiently initialize the set E by adding a link between each document and the highest marginal value topic for that document. This yields the first [D] links after computing a single round of marginal values (equivalent one step of the for-loop instead of [D] rounds). Moreover, this first round of marginal values can be efficiently computed as the product of the document word matrix and कh minus the phantom topic values (see the FASTINITIALIZE subroutine).
Lazy updates. Our approach can also leverage lazy updates. Lazy updates offer no provable improvement in the worst-case, but often result in dramatic practical speedups (Minoux, 1978; Mirzasoleiman et al., 2015). In particular, it is practically advantageous to lazily update the marginal values M M[d,, :]. as we do not need to know all marginal values, but just the best one, which in the best case removes an O({+)) factor of computation each iteration. Also, when recomputing the marginal value of a link over various iterations, if the link does not improve the log probability of a word in an iteration then it will not improve the log probability of that word in any subsequent iteration, so we can skip the word in the marginal value summation.
Fast indexing via the heap. In a practical fast implementation, each row of P and M can be stored in the heap in attached (c.g. in tuple) to their corresponding elements to avoid the cost of indexing into DI-sized storage.
To simplify analysis, we will regard the addition of each of the |D] initial links added by FASTINITIALIZE as 'iterations' of FASTGREEDY-E-LDA, despite the fact that these initial 'iterations' are slightly faster. FASTGREEDY-E-LDA. completes in D) iterations. Each iteration extracts the maximum- maximum-marginal marginal-valuu link [t" = d'] from the max-heap m, which is Olog DD). The next line updates the current log probabilities corresponding to 'd''s current topic-word assignments i., =d.|d)- which is bounded by the wordcount of the longest document, O()). The total log probability of document d is then updated in constant time (via memoization). Then the marginal values for all remaining links to d' are updated, and we also check which of these links has the greatest marginal value, which has complexity O) Finally, we insert this link with the greatest marginal value for d' into the max- max-heap heap m, which is Ologg D)). We have a total per-iteration complexity of just O(log [D] + E (((1)
Complexity of MASTGREEDY-E-LDEE
19

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
H. Comparison with Lanieer-han--lzzie--rrree
We now show that FASTGREEDY-E-LDA has better complexity than the fastest generic serial algorithm for submodular optimization, LAAZEER-THAN-LLAY-GRREEE (LTLG) (Mirzasoleiman et al., 2015), despite the fact that FASTGREEDY-E- LDA obtains deterministically near-optimal solutions whereas LTLG's guarantees hold only in expectation.
Lazier-Than--Laae Than-lazy-Greedy (LTTLG) input Corpus D. Candidate topic set Φ, Sparsity constraint upper- K, Phantom topic links initialize E' + for i {l...., ki DI} steps do
R f- a random subset of remaining topic-document links [T + d] not in E E $, E D
[ + d'] + the topic-doc link in R with the highest marginal value, argmax FE([T + d)) TE0,dED
E t [r" +rdd d"]
return EXP
Complexity of LAZIER- SEAIER-TTHN-LLAZ-GREEEEE (Mirzasoleiman et al., 2015). L.L.G is the fastest generic probabilis- tic serial algorithm for maximizing a submodular function (Mirzasoleiman et al. 2015). It obtains (1-1/e-é) approxima- tion guarantee in expectation, where e user-chosen. To accomplish this, LTLG proceeds identically to SIMPLE- -REELY except that at each of its D] iterations rather than evaluating the marginal value of all remaining links, it evaluates a ran- dom set of only [0|| x| (og(1/c) = | log(1/c) links sampled uniformly at random from the remaining links not yet added to the solution. It then adds the highest marginal value link in this random sample to the solution.
x
When applied to our objective f. LTLG can also be accelerated via our memoization techniques (P and p in FASTGREEDY-E-LLDA) which alleviate the need to sum over all [D] documents' log probabilities and maximize over all already-linked topics for each marginal value. After applying these speedups, each marginal value can be computed at a cost of (f). Finding the best sample of all marginal values for an iteration is O( [ log(1/e) (i.e. the sample complexity per iteration).
The result is a per-iteration complexity of ((({)\/Kk) ((g(//)) for each of the x D| iterations. However, this ignores the additional complexity of drawing | log(1/e) random samples each iteration, as well as the complexity of indexing into the memoized values each iteration. In practice, these random generation and indexing costs are significant, as the ground set is large. Also, unlike in the FASTGREEDY---LD: algorithm, the elements accessed each iteration by LTLG are non-prox non-praxi in memory (and associated with many different documents) due to the uniform random sampling, so there is no obvious way to apply the heap technique to improve indexing costs.
I. Deferred description of the FAST parallel algorithm
We reprint the FAST-FULL outer-loop and FAST algorithms from Breuer et al. (2020) below using our E-LDA notation for completeness. As in that paper, the purpose of the outer loop algorithm is generate various guesses E V of the optimal constrained E-LDA objective value, which is denoted by OPT == max f(E) s.t. |E' < x] These guesses of OPT are then used to instantiate the inner FAST algorithm. This inner FAST algorithm then binary searches over these guesses for the largest guess v that obtains a solution E that is a - 1 approximation to v, resulting in an overall E-LDDA solution that is near optimal.
Algorithm 1 FAST-FULL: the full algorithm
input function f. cardinality constraint k, accuracy parameter
S + the highest value x| D) links ir = d]
V f- GEOM(J((?* + d')), max Eirades [[[T = d), e)
o* + B-SEARCH(max(UU E V :(E.) 2 (1 - 1/e)o})
where E, + FAST(v)
return Eayx
20

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
The main routine FAST generates every iteration a uniformly random sequence d1:.... [[x] of the remaining set X of topic-document links that have not yet been discarded. After the preprocessing step which adds the current solution E some topic-document links guaranteed to have high marginal contribution, the algorithm identifies the maximum sequence prefix length i* (i.e. the first i" links of the sequence) such that there is a large fraction of not-yet-added links in X with high contribution to E U 1,, and adds this sequence prefix of topic-document links to the current solution E.
Algorithm 2 FAST: the Fast Adaptive Sequencing Technique algorithm
input f. constraint x:| D), guess for OPT, accuracy parameter e, sample complexity
E 5-0 0
while [E| < k: DI and number of iterations < e-1 do
X + [1[T + d], T 1... |$] d D), (1- (1-)
while X + 0 and |E| < k| do
(Denote single links [t + d] by a to simplify notation)
01..... axx < SEQUENCE(X.
A 1 a1....,a;
E E fafa: fEUA, (a:) 2 f
Xo + {a E X fE(A) 2 f}
if X1) I (1 X| then
X + Xo and continue to next iteration R - SAMPI.E(X, m m),
I + GEOM(L, x| 15)
R - faE R: SELAL,, (a) 21}. f.. :f
1* 4- B-SFARCH(max(L |R 2 (1-22) (R())
E EUA.-
return E
J. Deferred analysis of simulating FAST
As described in Theorem 3 (Breuer et al., 2020) and above, the parallel FAST algorithm obtains near-optimal solutions w.p. in a number of parallel rounds of objective function evaluations that is logarithmic in the number of documents. However, each E-LDA objective function evaluation in FAST is ( ( in a vanilla implementation, which results in computationally infeasible runtimes for FAST in practice (note that, whereas tive function evaluations on no more than x| D| links, FAST computes objective function evaluations on sets up and including the entire ground set of | links). Our goal in this section is describe how the same optimizations de- scribed for the serial algorithms above can also be applied to FAST when solving E-LDA. The result is log-time parallel algorithm with near-optimal approximation guarantees where each parallel round of function evaluations is practically fast, with runtime that is independent of the size of the data DJ. Specifically, after applying speedups, each function evaluation has worst-case complexity bounded by either just ((f) or ()
computes objec-
The key idea necessary to obtain fast simulated queries practically fast on the E-LDA objective is to observe that all steps of FAST except the sequence preprocessing and the binary search require function evaluations of the marginal values of single topic-document links, not sets of links, to the current solution E. As such, for these steps of the FAST algorithm, the same memoization strategies described above may be applied. Specifically, we memoize (as in P (D) x|V] above) the log probability of each word in the data per the current iteration's 's topic-word assignments Z; we memoize (as in in Pix|D] above) the current summed log probability of each document per the current Z: we memoize (as in M x| above) all current marginal values of links. Note that unlike in the serial FASTGREEDY E--LLEED--E--DA-AAA algorithm, there is no need to memoize each document's best not-yer-added topic and its marginal value a max-heap im (FAST does not seek the highest marginal valued link). By the same arguments as above, these memoizations permit the marginal value of any single link to be simulated in runtime just (() as before.
However, in sequence preprocessing steps (E < (a: SEJA, (a.) 2 i3) and binary search (i" <- B-SEARCH.... ...) steps, FAST evaluates the marginal value of singleton links to a union of the current solution E and a new sequence A of other links. Due to documents' independence in LDA, the marginal value of a link to document d is independent of all links to other documents. A new sequence A of links cannot contain more than ( links to document d, so we have a worst-case complexity bounded by (f(+b)) to simulate query of the marginal value of any link these FAST steps. We note that
21

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
because it is very unlikely that randomly drawn sequence will contain all links to the same document, in expectation the runtime complexity of each simulated marginal value query is far less. We thus obtain a practically efficient fast parallel algorithm capable of solving E-LDA near-optimally for truly enormous information-age datasets.
K. LDA for downstream causal inference: Topics as treatments
We review the main problems that prevent researchers from studying the topics inferred by mainstream LDA algorithms as treatments or outcomes downstream causal inference frameworks:
1. Fundamental Problem of Causal Inference with Latent Variables (FPCILV). First, causal inference frameworks assume that the set of treatments is fixed and the treatment assignments are randomized. However, in LDA we infer the treatments (topics) from the dataset. This means that under a different random treatment assignment, the texts would be different, and thus the treatments (topics) we infer would also be different. As such, topics qua treatments are not well-defined. Egami et al. (2022) has recently described this problem as the Fundamental Problem of Causal Inference with Latent Variables (FPCILV).
2. Stable Unit Treatment Variable Assumption (SUTVA). Second, causal inference frameworks such as Potential Outcomes (Rubin, 1974) and Directed Acyclic Graphs (DAGs) (Pearl, 2009) require the data conform to the Stable Unit Treatment Variable Assumption (SUTVA) (Rubin, 1980), which is satisfied when the response of an observation depends only on its own treatment assignment, not other observations' treatment assignments. However, even when the documents themselves exhibit this independence, the topics that any mainstream LDA algorithm (Gibbs, Variational Inference, etc.) ascribes to one document depend on the other documents in the dataset, which violates SUTVA. Thus, documents' topic assignments that are inferred by mainstream LDA algorithms cannot be directly used by a downstream causal inference framework (Egami et al., 2022).
3. out-le LDA algorithms have unbounded mismeasurement, high computational cost, and lack interpretability. These techniques also highlight another problem: To enforce FPCILV and SUTVA, the gold-standard approach splits documents into training/test sets, learns a topic model on the training set, then infers test set documents' topics using (separate) out-of-sample algorithms (Egami et al., 2022). However, standard LDA inference algorithms designed for out-of-sample inferences have unbounded mismeasurement in theory, and it is well known that they are biased and/or highly sensitive to random initializations in practice (Wallach et al., 2009b; Egami et al., 2022).' In other words, even if the original LDA algorithm run the training set correctly infers the topics and training set document mixtures, the (different) out-of-sample LDA algorithm run test documents may mismeasure documents' topics in the test set, leading to spurious causal inferences (Battaglia et al., 2024). Mismeasurement is particularly problematic in this setting because most valid treatment effects in the social sciences are small.
4. Topic mixtures are not well-defined treatments. Practitioners seeking to use documents' underlying topic mixtures O. as treatments have noted that such treatments are not well-defined for a separate reason (Fong and Grimmer, 2016). Specifically, documents' underlying topic mixtures must sum to 1 (i.e. ||0alla 1, v0a). so an observation (document) cannot have more [or less] of topic-of-interest without a proportional decrease [or increase] in the various other topics, which may be accomplished in infinite ways.?
When topics are instead used as outcomes instead of treatments, analogous versions of many of these problems continue to apply (Modarressi et al., 2025).
'Specifically, mainstream routines to do out-of-sample inference for IDA include Harmonic Mean (Newton and Raftery, 1994), Importance Sampling (Li and McCallum, 2006) (incl. Empirical Likelihood (McCallum)). Chib-Style Estimation (Chib, 1995). Left- ti-Right Evaluation (Wallach, 2008), and Variational Inference- based methods (Blei et al., 2003; Egami al., 2022). One interesting exception with impressive theoretic properties is (Arora et al., 2016b). though its performance is known to be suboptimal on real data. "In general, there is also another potential problem that prevents researchers from studying latent topics in a causal inference frame- work. Namely, there could exist unmeasured treatments (e-g. topics) that confound the measured treatment's effect (Fong and Grimmer, 2023). However, we note it standard to assume 'no unmeasured confounders' in other causal inference settings, and LDA explic- itly specifies the assumption conditional independences that obviate this problem. Moreover, the best known means to proceed absent this assumption has no provable guarantees in terms of identifying the correct topics, and it also lacks all of E-LDA's interpretability and scalability properties (Fong and Grimmer, 2023). We therefore argue that E-LDA offers an advantageous means to obtain causal inferences compared to this state-of-the-ar approach.
22

---

which applies the E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
L. MAP topic assignments are well-defined as treatments
Rather than considering documents underlying topic mixtures 02 as treatments (which are ill-defined as they must sum to 1), it is natural consider topic-word assignments. For example, define the treatment as a document's 's count of words assigned topic of interest. This treatment is well-defined, as is natural to imagine counterfactual document that shorter or longer (e.g. where fewer or additional words were added from sopic-of-interente while holding constant the counts of words drawn from each other topic. Alternatively, one could instead define treatments as the presence or absence of topic of interest in a document's MAP assignments.
M. Exemplar-LDA for downstream causal inference
We now describe how to modify our approach to perform out-of-sample inference such that can infer the topic assign- ments for 'test-set' (held-out) documents without violating FPCILV and SUTVA. Specifically, optimize the E-LDA objective subject to the modified sparsity constraint that single document d is generated by more than [El S Ka topics, where Kd is a user-chosen sparsity constraint that can be document-sppecffe Formally, we seek
[d]
Out-of objective f*: f*((Et (Ed) = max log P(Zald, Ea)
Σ
max max oy [wa,s)) TEEx
find argmax ft (Ea) subject to (r=d).ret
|Eal S Kgt EE 21
(17)
In this case, it is natural to use information from the 'training set' to inform the choice of the out-of-sample document's topic sparsity constraint Kg. For example, this may be accomplished via a simple regression (e.g. Tobit regression) of the count of assignments the training set solution documents as a function their length. This predictor can then be applied each held-out document to obtain an appropriate K. for each test-set document.
N. Outto--Sammle-PasGrreee---LLLLL
For completeness, we now give the accelerated version same speedups used in FASTGREEDY-E-LLDA to out-of-sample inference of assignments for each document independently. The main difference that (in parallel), and there no need for a heap data structure keep track of the best marginal value link across all documents. Note explicitly write the loop over |] documents (which can be computed in parallel) as it is convenient to initialize all documents' first links the same time.
E-LDA can computed independently for each document
input Doc-word matrix D D topic matrix 4 ||/i v documents' sparsity upper-bounds {Ma) E, P. P. M, + FASTINITIALIZE(D, 2
for each document do (in parallel)
for Ka steps do
Ea + [ + d where t* is the topic corresp. max M[d,:] P[d, :] t elementwise max of [dd and o(t", D :]
p[d] < p/d] Mid,t)
M[d,:] <- | (elementwise max of P [d.]] and + [D
p(d]
Eg + Ea U Ea
return
Importantly, these changes preserve the per-document near-optimal approximation guarantee that is relevant to causal inference applications (where it is advantageous to have a guarantee that each observation i.e. document is near-optimally measured). Finally, this approach conveys the additional advantage that each document can be optimized independently in parallel and we no longer pay the runtime cost of maintaining the max heap. This yields a parallel algorithm that not only preserves SUTVA independence, but also obtains this near-optimal solution in just maxa (Fa) parallel iterations, each of improved complexity that just Of)
23

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Deferred analysis of objective f with CO-OCCURRENCE topics
We now show that with topics &w- [e] exp(I .il + e) and 0[r] x Evev exp( n- ,el + e) where т is the topic generated about word w", v then the E-LDA objective simplifies to an hierarchical extension of a familiar submodular objective function used in data summarization: f(E) max log P,Z)D,E) EdED E max,Er, ( wea..)) Proof.
P(D, Z, (,,3,0,4)
II I (at(wass/zaa Cat 0a)
dED Evev exp( Dwn (ol attee))
exp(ID N0 mase +c)
Ever exp( Dur,, +e)
+e)
Et=1 Exevexp(( exp(IDws w-
simplifying and taking logs:
[d]
A Σ Σ
log P(D, |a.3,0,
Dwn mad
+
loo
exp(1Dwr,o) +c)
dED
eVV
[d]
D Dw ma.
const.
dED
After dropping constants, the E-LDA MAP objective becomes:
14
f(E) = max llog P(Z
= ΣΣ
Σ
max( D wes,))
(18)
TEEa
dEDi=1 i=1
P. Experiments: Additional details
Additional details. We select the three datasets in these experiments because they reflect a diverse range of styles and genres that capture mainstream data of interest in social science applications. Reuters new article briefs (Lewis, 1997) have vocabulary of [V| = 24,035 words and mean document length of 80.6 words; US Congressional speeches (Thomas et al., 2006) have vocabulary of [V| 13,857 and mean document length of 149.0 (though document lengths vary widely in that dataset); and NewsGroups social media discussion board posts (Lang, 1995) have vocabulary of [V] = 20,254 and a mean document length of 228.4.
Datasets:
For second set of experiments, we initialize to contain one topic generated for each word wt E [V] for each of the topic generators.
Monotone convergence near-optimal solutions. Figs. and 3b plot the convergence of E-LDA's objective values using the (top row) EXP-UMAS, topic generator and the (bottom row) CO-OCCURRENCE topic generator. Note that unlike benchmarks, our algorithms converge monotonically increase the number of topics assigned to each document from sparse 1 per document (equivalent to a document clustering) to relatively dense 10 per document (note the labels on top of the x-axes).
Experiments Set 1: Objective values over multiple experimental runs. Table reprints the values from Experiments Set with standard deviations added in parentheses. We excluded these from the body of the paper in the interest of making each baseline's values visually easier to compare across the table. For each baseline (Gibbs, Gibbs-Bayes, Gibbs -aabss- E-LDA's objective values are higher for all 90 experiments, and the difference for each benchmark and each dataset is statistically significant at the p< 10-10 level per standard 2-sided t-tests.
Experiments Set 2: evaluating the semantic quality of learned topics. In Experiments Set 2, we are interested in comparing the semantic quality of topics generated by E-LDA to those generated by ofate-of-the-art Gibbs-based LDA solvers. We measure topic quality via the widely-used UMass coherence measure (Mimno et al., 2011; Röder et al., 2015). Recall that UMass coherence measures the (log) probability that the top (i.e. highest-probability) h² words in a topic
24

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Gibbs
E-LDA
randæ:
Congress (x 10%)
-2.05 (0.00834)
-1.78 (0.00631)
-10.92 (0.0926)
Reuters (x (x10%
-2.80 (0.0114)
-2.52 (0.00948)
-16.54 (0.226)
NewsGroups (x (x10))
-1.57 (0.00536)
-1.40 (0.00450)
-6.71 (0.0754)
G-B
E-LDA
rands:
Congress (x 10%)
| -2,47 (0.00948)
-2.22 (0.00941)
-10.22 (0.344)
Reuters (x 109)
-3.66 (0.0107)
-3.43 (0.0128)
-15.19 (0.126)
NewsGroups (x 10%)
|| -1.70 (0.00399) -1.61 (0.00428)
-6.57 (0.0879)
|| G-S
E-LDA
randk
Congress (x (x10%)
|| -2.43 (0.00349)
-2.14 (0.00338)
-10.31 (0.0156)
Reuters (x 10%)
|| -3.49 (0.0111)
-3.13 (0.00956) -15.41 (0.170)
NewsGroups (x10%)
-1.68 (0.00347)
-1.55 (0.00247) -6.52 (0.0770)
Table 2: Experiments set I: Log posterior of assignments (f value) with same topics sparsity (10 run avg.). values reprinted from Table I with added standard deviations in parentheses. All means and standard deviations are scaled by x 100 for comparability.
co-appear in documents in the corpus. Specifically, for a given topic т, the normalized coherence is:
h" h-1
D +
C(T,N()= = 1: -1) h=2 1=
log
(19)
D
where Dr,, is the set of documents that contain the hith most probable word according to topic т, Dr,, is the set that contain both the h'th and l'th most probable words according to topic т, and is a small constant that precludes the log(0) case. We choose the normalized variant that includes the (- Σhz factor because it render coherence scores comparable across different choices of h", as in Figs. 2a (z-axes).
Experiments Set 2: Baseline coherence variation over multiple runs. FASTGREEDY-E-LDA is deterministic, so its performance is always consistent across multiple runs. In contrast, Gibbs baselines' solution quality varies from one run to the next. Fig. reprints the main Gibbs baseline's 's mean coherence scores from Fig 2a with added error bars showing its best and worst mean- wwwerence-per--eeeeee over 10 re-runs show the range of its typical performance. Observe that even by re-running the baseline 10 times, no single run obtains coherence comparable to either of the E-LDA solutions.
Experiments Set 2: Additional baselines. For topic coherence experiments (Set 2), we add recent neural and LLM-based baselines: BERTopic (Grootendorst, 2022), AVITM (Srivastava and Sutton, 2017), ETM (Dieng et al., 2020), and FASTopic eW al., 20.4 We use the authors' codebases for each of these baselines (note that ETM and AVTTM are now integrated with the OCTIS library (Terragni et al., 2021), 1). and FASTopic is now integrated with the Topmost library (Wu et al., 2024c), and we set parameters to be identical to the parameters their respective papers. terms of performance, ETM the best-performing baseline. This matches expectations, as ETM was explicitly designed coherence-ing -etereccciimpooiinggee algorithm per (Dieng et al., 2020) (see also, e.g., Wu et al. (2024a)). We note that AVITM's poor coherence matches anecdotal experience that this algorithm obtains good coherence on some datasets but requires customized parameter tuning to obtain competitive performance on others.
Scale of experiments. We note that the largest submodular problems in the literature are social network problems with ground sets of ~0 elements. Our experiments described above consider > 10 links. See Breuer et al. (2020), Mirza- soleiman et al. (2013), and Guestrin al. (2005).
25

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
Congress
NewsGroups
mean mbsic per SDC
mean Rop c5 per doc
mean shopic pCt SDC
10
Cityettve: koy P1000.00 2)
Obyechee Pop P12
Chyectin Ios PPPp.
14b:0
E-LDA (ec--UNass)
Iteratio
Rerofion
Iteration
(a) Convergence of E-LDA's objective values using the EXP-UMASS topic generator.
Congress
NewsGroups
mein mopks perdsc
meat Ropics per d01
mean wiokks per perdte
10
10
Ollecchnnn Ing P12 F)
Oljecttee Mog
occamance)
2:50400
230-48
25000
50000 Iteration
79390
10090
5000
30000
Beralion
Ieeatonn
(b) Convergence using the CO-OCCURRENCE topic generator.
Figure 3: Convergence of E-LDA's objective values f using the (top row) EXP- EXP-UMASS topic generator and the (bottom
row) CO-OCCURRENCE topic generator.
Q. Deferred discussion of unmodified UMASS topic generator
We include the UMASS topic generator both build intuition, and also because poor post-hoc coherence scores provide clear illustration that other topic generators are not obtaining high post-hoc coherence merely due their similarity with the UMass coherence function. In particular, each assign probability mass too uniformly across the vocabulary, resulting in un-sparse topics with unfocused semantic meaning. We note that comparable property is referred to as "topic collapsing" when it arises in the context of recent neural topic modeling algorithms (Wu et al., 2023).
note that the unmodified UMASS generator produces topics that
To be clear, post-hoc coherence scores only weigh the ranking words in a topic according to their probability mass, so order-preserving transformations of topic distributions have no effect on topic's 's post-hoc coherence. Thus, the generated of candidate topies using the UMASS generator has the same coherence score as EXP- MAP- and CO-OCCURRENCE topics. However, UMASS's too-uniform topics cause algorithm to do poor job of selecting (for each document)
Reuters
Congress
NewsGroups
meann conarance
mesn coherence
meain coherance
-2.0
-.5
E-LDA (co-occurrence)
E-LDA (exp-UMM (exp-UMass)
10
15
20
25
10
15
20
10
15
20
25
words toplc
top words In toplc
top words In topic
Figure 4: reprint the main Gibbs baseline from Experiments Set 2 (Fig 2a) with added error bars showing its best and worst mean-coherence--err-uuu over the 10 experimental runs.
26

---

E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time
small, diverse of focused topics that each well-represent subset of the document's words. This explains why the exponential transformations in EXP-UMASS and CO-OCCURRENCE produce much more focused topics, and also why the solution set of topics using these generators has far better post-hoc coherence scores than alternatives.
R. CO-OCCURRENCE vs. EXP-UMASS topic generators in practice
We briefly note some practical experiences with the results using CO-OCCURRENCE vs. EXP-UMASS topic generators. Because CO-OCCURRENCE favors topics associated with rigorous topic labels w² that are more popular, this results in fewer unique topics overall, and in topies that more focused on familiar/popular concepts. In contrast, using EXP- UMASS topics tends result in solutions that reflect more subtlety, including wider variety of topics and less-common topic labels w". In practice, we prefer to use CO-OCCURRENCE as a 'first cut' to familiarize ourselves with an unknown dataset, and then to apply EXP-UMASS to tease out subtler meanings for final analysis.
S. Interpretability & simulateability: Additional discussion
We briefly note separate interpretability advantage of our approach that is particularly relevant to practitioners working on problem instances in social science and causal inference. Specifically, because all mainstream topic modeling algorithms baadd, their routines too complex for human researcher to vet. Put differently, practitioner cannot look into the algorithm's 's operations to obtain an answer to the question "Why did the algorithm assign the 'physics' topic to this document?". This aspect of interpretability is variously referred to as 'simulateability" (Lipton, 2018). We note that this problem also a focal point recent social science methodology discussions- sec, c.g., Grimmer et al. (2022), Ying al. (2022), and Ke et al. (2024).
In contrast, our Greedy-based algorithms intuitively familiar the human process of connecting topies documents. Therefore, it is easy to answer such question for solution obtained by our algorithms. For example, the answer will be "The 'physics' topic was assigned to this document because it most improved the description of the document, which was previously described only by 'space' and 'particle' topics (i.e. the topics that were linked in Eg before 'physics')." By "most improved', we mean that the 'physics' topic offered the greatest increase the probability of that document's words compared to all remaining topics.
27


Reviews:
[{"review_id": "hfO3uw03JI", "reviewer": "Reviewer_hQes", "summary": "The paper introduces Exemplar-LDA (E-LDA), a novel combinatorial approach to Latent Dirichlet Allocation (LDA) topic modeling, addressing the NP-hard problem of inferring document-topic assignments. Unlike traditional gradient-based methods, E-LDA uses a non-gradient, submodular optimization framework, achieving near-optimal Maximum A Posteriori (MAP) solutions in logarithmic parallel time. It ensures interpretability by associating topics with keywords and supports causal inference applications. Experiments on datasets like Reuters and Congressional speeches show E-LDA outperforms Gibbs LDA, neural, and LLM-based models in posterior probability and topic coherence, offering faster convergence and higher semantic quality across sparse to dense solutions.\n\n## update after rebuttal\n\nAfter viewing the reply and other comments, I decided to keep my rating as an acceptance score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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.\"**\n\n**We believe we address your remaining reservations here and would appreciate it if you would consider improving your score in light of our response.**\n\n **The main concern and reason for a score of 3 instead of 4 or 5 seems to be:**\n \n 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):\n\n     ***https://imgur.com/a/LO1bUqw***\n\n  \n2.  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.\"*\n \nWe 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.\n\nWhile it is true that these building blocks of submodular optimization, low-adaptivity parallel optimization, and coherence are well-established, we emphasize that:\n\n  - The connection between submodularity and LDA is wholly unknown, and the analysis is nontrivial;\n  - 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:\n\n     -  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*);\n \n     -  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.\n\n     - 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.\n\n***---Responses to additional questions---***\n\n**Re:** How were neural and LLM-based baselines tuned?\n\n- 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.\n\n**Re:** Why is AVITM’s performance notably poor?\n\n- 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).\n\n*We believe that our responses address your remaining questions, and we would sincerely appreciate it if you would consider updating your score.*", "claims_and_evidence": "Most claims are supported by clear and convincing evidence, blending rigorous theory (submodularity, complexity analysis) with solid empirical results. \n\nConcerns:\n\nOnly three datasets (Reuters, Congress, NewsGroups) are tested, all from social science domains. Some short texts should included in the experiments.", "methods_and_evaluation_criteria": "The developed methods: combinatorial optimization, interpretable topic generation, and causal inference adaptation well address the problem’s challenges: guarantees, interpretability, and causal compatibility. And the experiments also show the improvements of the model.", "theoretical_claims": "The proofs in the submission seem correct.", "experimental_designs_or_analyses": "The experimental results well support the proposed model.", "relation_to_broader_scientific_literature": "I think this paper is interesting and gives insight to the community.", "essential_references_not_discussed": "The experiments in this paper is solid.", "other_strengths_and_weaknesses": "Weaknesses:\n\n1) 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.\n\n2) It is better to add more datasets, such as short texts.", "other_comments_or_suggestions": "None", "questions_for_authors": "How were the neural and LLM-based baselines tuned in the experiments and why was AVITM’s performance notably poor", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QldCIEoC6o", "reviewer": "Reviewer_jKFV", "summary": "The paper introduces new algorithms for Latent Dirichlet Allocation (LDA). The algorithms address the problem of inferring the topics assigned to each document in an LDA topic model. The approach is non-gradient-based and combinatorial.    \n\nThe algorithms converge to near-optimal posterior probability in logarithmic parallel computation time. The approach also provides interpretability guarantees, associating each learned topic with a known keyword. Unlike alternative approaches, this approach can maintain the independence assumptions necessary for downstream causal inference methods that use the learned topic model to study topics as treatments.    \n\nThe authors argue their approach returns solutions of higher semantic quality than state-of-the-art LDA algorithms, neural topic models, and LLM-based topic models across a range of text datasets and evaluation parameters.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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.**\n\n**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.\"*\n\n- 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.\n\n- 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.\n\n- 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.\n\n**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.\"*\n\n- 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.\n\n**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. .*\n\n- 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). \n\n**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.\n\n - 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.", "claims_and_evidence": "Claims Supported by Evidence:\n\n\n- \"The proposed algorithm obtains a deterministic worst-case 1−1/e approximation of the constrained log MAP probability objective.\" This claim is supported by the detailed description of the algorithm, the theorems presented, and the proofs provided in the appendix. The authors also provide experimental results that align with this claim.  \n- \"The algorithm can learn solutions of higher semantic quality (coherence) than those found by state-of-the-art LDA algorithms, neural topic models, and LLM-based topic models.\" The authors present results from experiments comparing their algorithm to several baselines, using measures of semantic quality, providing evidence that supports this claim.  \n\n\nClaims With Less Clear Evidence:\n\n\n- \"The algorithms converge to near-optimal posterior probability in logarithmic parallel computation time (adaptivity) exponentially faster than any known LDA algorithm.\" While the authors provide a theorem and analysis related to the parallel computation time, the claim of being \"exponentially faster\" than any known LDA algorithm is a strong statement that would benefit from more explicit comparisons to the computational complexity of a wide range of LDA algorithms. The analysis focuses on the FAST algorithm and its properties but does not provide a clear comparison showing the exponential speedup relative to other LDA algorithms.  \n\n- \"The approach also provides interpretability guarantees, such that each learned topic is formally associated with a known keyword.\" The authors describe how they generate candidate topics based on coherence functions and keywords. While this associates topics with keywords, the degree to which this provides a formal guarantee of interpretability could be debated. 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.  \n\n- \"Unlike alternatives, our approach can maintain the independence assumptions necessary to use the learned topic model for downstream causal inference methods that allow researchers to study topics as treatments.\" The authors discuss the limitations of other LDA approaches for causal inference and how their method addresses some of these limitations. However, the complexities of causal inference and the potential for other factors to influence independence assumptions make this claim a bit unspecified. 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. It is important to note that still in many realistic social science usecase using this topic model for downstream causal inference can create bias (for example if there are fixed effects).", "methods_and_evaluation_criteria": "Methods:\n\n- The authors frame the LDA topic-word assignment problem as a combinatorial optimization problem. The formulation allows the authors to leverage submodularity, which enables approximation guarantees.\n\n- The authors propose efficient algorithms (FASTGREEDY-E-LDA, FAST) to solve the combinatorial optimization problem. These algorithms incorporate several speedup techniques, like memoization, heap data structures, and lazy updates. The algorithms make sense for the problem, as one of the main challenges with applying submodular optimization to LDA is the computational cost.\n\n- For interpretability, the authors suggest generating candidate topics using coherence functions. Using standard coherence functions ensures that the generated topics are aligned with human judgment of semantic quality.\n\n- The authors also modify their approach to handle out-of-sample inference for causal inference. Given the challenges of using topic models in causal inference, the modifications are appropriate to this usecase.\n\n\nEvaluation Criteria:\n\n- The authors use log posterior probability as one of their evaluation metrics. This is a natural choice, as it directly measures how well the model fits the data under the LDA assumptions.\n\n- The authors use UMass coherence to measure the semantic quality of the topics. This is a widely used metric that correlates with human judgment. They also examine other properties of the learned topics, like how the model behaves as the number of topics per document increases.\n\n- The baselines used for comparison are appropriate, as they include traditional LDA algorithms, neural topic models, and LLM-based topic models. This covers a wide range of existing approaches and demonstrates the advantages of the proposed method over different types of competitors.\n\n\nThe datasets used (Reuters, US Congressional speeches, and social media posts) are standard datasets in topic modeling and represent a variety of text types.", "theoretical_claims": "Yes, the theoretical claims seems well supported by the accompanying proofs.", "experimental_designs_or_analyses": "I didn't check too carefully, but it looks like a pretty standard experimental design and analysis. See my answer to \"Methods And Evaluation Criteria\"", "relation_to_broader_scientific_literature": "The paper is very thorough in its discussion of the topic modeling literature. \n\nAuthors can do a better job in highlighting the causal inference use-case. References and discussion of how economists and other causality-intensive social sciences use topic models would drastically improve the paper.", "essential_references_not_discussed": "Many of the text-as-data literature, and the causality+NLP literature are missing here.\nAn example of an essential missing reference on application of topic models for causality is Ash et al.'s \"Text Algorithms in Economics\".", "other_strengths_and_weaknesses": "See my answer to \"Claims And Evidence\".", "other_comments_or_suggestions": "-", "questions_for_authors": "See \"Claims And Evidence\" and \"Methods And Evaluation Criteria\".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jfxuRBxZ0I", "reviewer": "Reviewer_vCQj", "summary": "The authors present a novel non-gradient-based, combinatorial approach for estimating topic model parameters. The model converges to an algorithm that achieves near-optimal posterior probability in logarithmic parallel computation time, significantly faster than known algorithms for LDA. Furthermore, this manuscript demonstrates that candidate topics can be efficiently generated using standard coherence functions and that the document independence required for downstream causal inference frameworks can be guaranteed.\n\n## update after rebuttal\nThanks to the authors for their responses, which address my previous questions. Thus, I maintain my positive score on this submission.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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.\"**\n\n\nWe 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). \n\nWe 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.\n\n**Our approach improves stability in three key ways:**\n\n   **1. E-LDA's deterministic optimization leads to perfect stability under the Hoyle et al. definition.**\nOur 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.\n\n   **2. Stable, monotonic convergence of posterior probability.**\nDue 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.\n\n 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.\n \n   **3. Stable coherence over different solution sizes (different sparsities).**\nFig 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.\n\n***---Responses to additional questions/suggestions---***\n\n\n**Re:** Adding a very recent baseline***. \n\n- 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):\n\n ***https://imgur.com/4GobskW***\n\n *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.\n\n \n\n\n\n\n**Re:** Figures 1 and 2 are missing captions, and there is an extra ‘(for example)’ on line 70.\n\n- Great catch---thank you! We've corrected both.\n\n**Re:** Figure 1 seems a bit cluttered, and it is recommended that the authors reorganize it.\n\n- 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.\n\n**Re:**  use of italics, bold, upper and lower case, and brackets.\n\n- 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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "There is no obvious problem with the theorem proof in the submission.", "experimental_designs_or_analyses": "The topic consistency and run speed evaluated in this submission are closely related to the topic modeling domain as well as to the contributions of this study.", "relation_to_broader_scientific_literature": "The paper intuitively reconstructs the process of topic modeling using greedy algorithms and enhances the interpretability of topic models, providing enlightening insights for related fields.", "essential_references_not_discussed": "The important literature relevant to the contribution of this paper has been discussed.", "other_strengths_and_weaknesses": "Strengths:\nThe approach proposed in this paper enhances the LDA model from a novel perspective and offers theoretical guarantees regarding the model’s speed of convergence and its independence in downstream inference applications, demonstrating high originality and inspiration for future work in the field.\n\nWeaknesses:\n- Previous work [1] has found that some topic models exhibit poor stability, meaning that even with similar topic quality, the models may generate vastly different topic words for different random seeds. While the manuscript emphasizes the progress of the method proposed in this paper in terms of interpretability and downstream tasks, the lack of sufficient robustness in the model may diminish the value of these innovations. I believe the authors should have conducted further analysis on this aspect.\n- Some more recent baseline methods should be included for comparison. The baseline models used in this paper, such as ETM, are commonly regarded as simple baselines, whereas in recent years, neural topic models have demonstrated significant improvements in topic quality.\n- The authors should demonstrate the model’s interpretability using some simple examples.\n\n[1] Hoyle A M, Goel P, Sarkar R, et al. Are Neural Topic Models Broken?. EMNLP Findings. 2022: 5321-5344.", "other_comments_or_suggestions": "- Figures 1 and 2 are missing captions.\n- Figure 1 seems a bit cluttered, and it is recommended that the authors reorganize it.\n- There is an extra ‘(for example)’ on line 70.\n- In the manuscript, the authors make extensive use of italics, bold, upper and lower case, and brackets to convey emphasis and additional information. I believe that the excessive use of these marks detracts from the readability of the text and I suggest that the authors could have used a more concise writing style.", "questions_for_authors": "The manuscript repeatedly emphasizes the interpretability of traditional LDA methods in comparison to neural topic models and LLM-based topic models in the introduction. I would like to request the authors to provide further explanation on this part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xjlrmcb9w4", "reviewer": "Reviewer_ZFSN", "summary": "The paper introduces a novel approach to Latent Dirichlet Allocation (LDA) topic modeling by developing a combinatorial method to efficiently infer topic assignments with strong interpretability guarantees. The proposed method, Exemplar-LDA (E-LDA), departs from traditional gradient-based approaches and instead leverages combinatorial optimization techniques inspired by clustering and data summarization. The authors claim that this method provides near-optimal posterior probability solutions exponentially faster than existing LDA algorithms, ensures interpretability by associating each learned topic with a known keyword, and is compatible with causal inference applications. The experimental results demonstrate that E-LDA achieves better topic coherence and posterior probability compared to traditional LDA and neural topic models.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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.**\n\n**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.**\n\n**Re:** \"In the experiments, how about the performance with larger numbers of topics? Like 50 to 100 topics.\"\n\n- 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. \n\n- 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).\n\n**Re:** \"Can you evaluate the inferred topic distributions $\\theta_d$ of documents?\"\n\n- 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.\n\n**Re:** \"The datasets are of medium size. Can E-LDA still perform well on large-scale datasets? What is its empirical execution time?\"\n\n- 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:\n\n ***https://imgur.com/a/LO1bUqw***\n \n  On this larger dataset, E-LDA's efficient theoretic design allows it to complete in 2.8 seconds.\n\n- 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. \n\n- We could achieve additional speedups by offloading bottlenecked operations (the elementwise products in the *Update* subroutine) to a GPU.\n\n- 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).\n\n**Re:** Adding a 7th baseline, ***FASTopic (Wu et al., NeurIPS 2024)***. \n\n- Thank you for this suggestion. Here are the plots with ***FASTopic*** (in light blue):\n\n ***https://imgur.com/4GobskW***\n\n 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.\n\n**Re:** Reference list is missing recent surveys [1], [2], [3].\n\n- Thank you for these references! We have incorporated them into our camera-ready draft.\n\n**Re:** Typo where AVITM's publication date was replaced by BERTopic's in the reference in the paper, and Fig. 2 has only subcaptions.\n\n- Great catch! Thank you for pointing this out---we have updated our paper accordingly.\n\n**Re:** our statement that we compare against an LLM-based topic model.\n\n- 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.\n\n**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.**", "claims_and_evidence": "1. The paper provides provable guarantees for topic inference in LDA, addressing a long-standing challenge in probabilistic topic modeling.\n1. Unlike conventional LDA methods that often produce topics requiring manual interpretation, E-LDA ensures that each topic is formally associated with a known keyword, which significantly improves interpretability.\n1. The experimental results show that E-LDA outperforms previous LDA and neural topic models on topic coherence.", "methods_and_evaluation_criteria": "1. In the experiments, how about the performance with larger numbers of topics? Like 50 to 100 topics.\n1. For the experiments, can you also evaluate the inferred topic distributions of documents, $\\theta_d$?", "theoretical_claims": "I checked the proofs and theoretical claims.", "experimental_designs_or_analyses": "I checked the experimental designs. It lacks some important baselines and evaluations.\n\n1. The mentioned datasets are of medium size. Can E-LDA still perform well on large-scale datasets? What is its empirical execution time?\n1. In Section 9, the neural topic modeling baselines are a bit old. The authors should compare with some recent ones, like FASTopic(https://arxiv.org/pdf/2405.17978).", "relation_to_broader_scientific_literature": "The contribution in this paper may provide a good alternative baseline for LDA.", "essential_references_not_discussed": "The reference list is a bit outdated. Consider adding some recent topic modeling survey papers:\n\n[1] A Survey on Neural Topic Models: Methods, Applications, and Challenges  \n[2] Topic Modeling Algorithms and Applications: A survey  \n[3] The Evolution of Topic Modeling", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "1. AVITM was proposed in 2017, but the paper denotes its publication time as 2022.\n2. Neither of BERTopic, AVITM, and ETM is LLM-based.\n3. Figure 2 only has subcaptions.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper contributes a novel and theoretically grounded approach to topic modeling, offering improvements in interpretability, inference speed, and potential causal applications. While some experimental limitations  such as  outdated baselines (currently best neural topic model assuming you use a Dirichlet prior, is ECRTM [1] to my knowledge, which extends ETM), lack of sufficient datasets, and limited evaluation with a causal inference pipeline exist, the core methodology is sound, the empirical results are competitive, and the ideas are innovative and timely. With modest revisions and expanded evaluation, this work has strong potential to impact both topic modeling and broader text-as-data research communities. In particular, the conclusion should not be shifted to the Impact Statement which could be counted as cheating the page limit.

[1] Xiaobao Wu, Xinshuai Dong, Thong Thanh Nguyen, and Anh Tuan Luu. 2023. Effective neural topic modeling with embedding clustering regularization. In International Conference on Machine Learning, pages 37335–37357. PMLR.
Decision: Accept (poster)