Scalable Model-Based Clustering with Sequential Monte Carlo

Connie TrojanPavel MyshkovPaul FearnheadJames HensmanTom MinkaChristopher Nemeth

article2026arXiv0 citations

Proposes a scalable Sequential Monte Carlo algorithm for online clustering that overcomes critical memory bottlenecks by decomposing cluster uncertainty into approximately independent subproblems.

Listen

Real-time clustering is critical for tasks such as building automated knowledge bases from text, where ambiguous references to entities must be resolved on the fly without a predefined set of categories. Sequential Monte Carlo (SMC) methods naturally capture evolving uncertainty in streaming data, but standard implementations become computationally prohibitive as data volumes expand. The article introduces a scalable online framework called split SMC to address these memory and runtime bottlenecks in large-scale clustering problems.

The main objective of the article is to demonstrate that decomposing streaming clustering problems into approximately independent subproblems significantly improves computational efficiency and clustering accuracy compared to standard online and offline methods. The authors evaluated the approach across synthetic spatial benchmarks (overlapping circles and Gaussian mixtures) and real-world entity-linking text datasets containing up to 200 clusters and nearly 2,000 observations. To accelerate neural model evaluations, lightweight surrogate models were integrated as proposal mechanisms.

The evaluations yielded several key findings:

Split SMC consistently achieved higher log-posterior probabilities and clustering accuracy (F1 scores ranging from 0.68 to 0.88) compared to vanilla SMC, while matching or exceeding the accuracy of traditional offline algorithms.
In large-scale text benchmarks, split SMC processed streaming data in minutes (e.g., 11 minutes on REBEL-200), whereas traditional offline methods failed to converge within a 10,000-second budget.
Incorporating simple surrogate models to filter candidate assignments reduced expensive neural network evaluations and prevented early overfitting to noisy data, leading to better overall accuracy.

These results demonstrate that online clustering can achieve the statistical quality of offline batch methods at a fraction of the computational and financial cost. For enterprise applications such as continuous knowledge base construction, this enables real-time updating without the latency and infrastructure overhead required by batch re-clustering.

Organizations handling continuous text streams should consider adopting factorized online sampling architectures like split SMC, particularly alongside surrogate models to control computational expense. However, decision-makers should note that performance depends on the alignment between surrogate models and data characteristics; when tested on out-of-domain text data with high name variation, split SMC exhibited minor accuracy trade-offs. Further domain-specific calibration of surrogate models is recommended before deploying the method in specialized production pipelines.

Lancaster University Microsoft clustering methods knowledge base text data sequential Monte Carlo model-based clustering Dirichlet process mixture models

arXiv: 2604.14810 microsoft/smc-clustering

Paper: Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks, Arnaud Doucet et al. (2000). This paper establishes the foundational principles of Rao-Blackwellised Sequential Monte Carlo and particle filtering for dynamic networks, which are crucial for understanding how the source decomposes state spaces into structured subproblems.
Paper: CONDENSATION—Conditional Density Propagation for Visual Tracking, MICHAEL ISARD et al. (1998). This foundational work introduces Sequential Monte Carlo sampling over evolving probability distributions, providing the essential particle filtering framework adapted by the source for sequential clustering under uncertainty.
Paper: The Infinite Gaussian Mixture Model, Carl Edward Rasmussen (1999). This paper introduces the infinite Gaussian mixture model for automated cluster complexity inference, laying theoretical groundwork for model-based clustering with an unknown and growing number of components.
Paper: Unsupervised Learning of Finite Mixture Models, Mário A. T. Figueiredo et al. (2002). Figueiredo and Jain provide key principles of model-based clustering and unsupervised mixture estimation that motivate the source's probabilistic approach to resolving cluster uncertainty.
Paper: Clustering with Bregman Divergences, Arindam Banerjee et al. (2005). This paper unifies parametric clustering and exponential family mixture models, offering valuable background on handling complex data distributions like those in text-based knowledge base construction.
Paper: A Framework for Clustering Evolving Data Streams, Charu C. Aggarwal et al. (2003). Aggarwal et al. present the core concepts and trade-offs of online streaming clustering and state maintenance that the source targets using sequential probabilistic inference.

Paper: Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings, Leonardo Kuffo et al. (2026). This work explores scaling and memory-efficiency strategies for vector embedding clustering through dimensionality reduction and quantization, offering complementary practical scaling techniques for large-scale text embeddings.

Cover for Scalable Model-Based Clustering with Sequential Monte Carlo

Abstract

In online clustering problems, there is often a large amount of uncertainty over possible cluster assignments that cannot be resolved until more data are observed. This difficulty is compounded when clusters follow complex distributions, as is the case with text data. Sequential Monte Carlo (SMC) methods give a natural way of representing and updating this uncertainty over time, but have prohibitive memory requirements for large-scale problems. We propose a novel SMC algorithm that decomposes clustering problems into approximately independent subproblems, allowing a more compact representation of the algorithm state. Our approach is motivated by the knowledge base construction problem, and we show that our method is able to accurately and efficiently solve clustering problems in this setting and others where traditional SMC struggles.

Topics

clustering methods knowledge base text data data clustering

Keywords

sequential Monte Carlo model-based clustering Dirichlet process mixture models Gaussian mixture model online clustering Gibbs sampling Bayesian inference hierarchical clustering

1 INTRODUCTION
1.1 Knowledge Base Construction
1.2 Model-based clustering
2 BACKGROUND
2.1 Bayesian Clustering Models
2.2 Sequential Monte Carlo
3 SEQUENTIAL CLUSTERING METHODOLOGY
3.1 Notation
3.2 Split Step
3.3 Update Step
3.4 Merge Step
3.5 Surrogate Models
4 EXPERIMENTS
4.1 Circles
4.2 Gaussian Mixture
4.3 Knowledge Base Construction
5 DISCUSSION
6 Acknowledgements
References
A ADDITIONAL RESULTS
A.1 Full Results and Runtime Comparison
A.2 Particle Set Size Comparison
A.2.1 Effective Particle Set Size in Split SMC
A.3 Surrogate Model Ablation
B PROOFS
B.1 Posterior Factorisation
B.2 Greedy Resampling
C SPLIT SMC ALGORITHM DETAILS
C.1 Surrogate Proposal
D EXPERIMENTAL DETAILS
D.1 Offline Algorithms
D.2 Experiments
D.2.1 Text Data

Knowls

Knowl 1 — Split Sequential Monte Carlo Framework for Online Clustering
model/method
In Dirichlet process mixture model (DPMM) clustering, standard Sequential Monte Carlo (SMC) filters struggle because the number of possible partitions grows exponentially with dataset size $t$ , causing rapid particle degeneracy and high memory usage. Split Sequential Monte Carlo addresses this by exploiting conditional independence under the DPMM prior: when subsets of data do not share clusters, their joint posterior distribution factorises into independent subproblems.

Let $x_{1:t}$ denote observations up to time $t$ . The dataset is dynamically partitioned into $S$ disjoint subproblems $E_t = \{E_t^1, E_t^2, \dots, E_t^S\}$ such that $\bigcup_{s=1}^S E_t^s = x_{1:t}$ . Each subproblem maintains an independent particle approximation:

$\mathcal{P}_t^s = \left\{ p_t^{(s,i)} \right\}_{i=1}^{m_s}, \quad \left\{ w_t^{(s,i)} \right\}_{i=1}^{m_s}$

where $p_t^{(s,i)}$ is a partition of the observations in $E_t^s$ , $w_t^{(s,i)}$ is its associated weight, and $m_s \le m$ is the number of particles for subproblem $s$ . The joint posterior over all clusterings of $x_{1:t}$ is represented implicitly as the product space $\bigotimes_{s=1}^S \mathcal{P}_t^s$ . When a new observation arrives, only the relevant subproblem is expanded and resampled, and subproblems are dynamically split or merged based on posterior co-occurrence.
Knowl 2 — Reverse KL Divergence Minimization via Subproblem Factorization
theoretical result
Let $p$ denote the posterior distribution over clusterings of a dataset $X = x_{1:t}$ induced by a Dirichlet process mixture model. Suppose $X$ is partitioned into disjoint subsets $E^1$ and $E^2$ , and let $p_{ij}$ denote the true posterior probability of clustering configuration $(i, j)$ , where $i \in \{1, \dots, I\}$ indexes clusterings of $E^1$ and $j \in \{1, \dots, J\}$ indexes clusterings of $E^2$ . Under the DPMM, if no clusters contain points from both $E^1$ and $E^2$ , the posterior factorises as $p_{ij} = p_i^1 p_j^2$ .

Let $\hat{p}$ be an approximate distribution supported on clusterings where no datapoints in $E^1$ and $E^2$ share a cluster, with marginal distributions $b_i = \sum_j \hat{p}_{ij}$ over $E^1$ clusterings and $c_j = \sum_i \hat{p}_{ij}$ over $E^2$ clusterings. Let $\hat{p}^M$ be the product distribution defined by $\hat{p}_{ij}^M = b_i c_j$ .

For any joint distribution $q$ with marginals $b$ and $c$ , the reverse Kullback-Leibler divergence satisfies:

$\mathrm{KL}(q \parallel p) = -H(q) - \sum_{i} b_i \log p_i^1 - \sum_{j} c_j \log p_j^2$

where $H(q)$ is the Shannon entropy of $q$ . Since entropy is maximized when $q$ is the product of its marginals ( $H(q) \le H(b) + H(c)$ ), the distribution $q$ that minimizes $\mathrm{KL}(q \parallel p)$ is $q = \hat{p}^M = b \otimes c$ . Consequently:

$\mathrm{KL}(\hat{p}^M \parallel p) \le \mathrm{KL}(\hat{p} \parallel p)$

This result extends by induction to partitions with $S > 2$ disjoint subsets.
Knowl 3 — Optimality of Greedy Resampling Under Reverse KL Divergence
theoretical result
Let $x$ and $y$ be discrete probability distributions with $\mathcal{Y} := \mathrm{support}(y) \subseteq \mathrm{support}(x)$ . The reverse Kullback-Leibler divergence is lower bounded by:

$\mathrm{KL}(y \parallel x) \ge -\log \sum_{i \in \mathcal{Y}} x_i$

with equality holding if and only if $y_i = x_i / \sum_{j \in \mathcal{Y}} x_j$ for all $i \in \mathcal{Y}$ .

When constructing a particle approximation $y$ of fixed support size $|\mathcal{Y}| = m$ from a discrete distribution $x$ , the reverse KL divergence $\mathrm{KL}(y \parallel x)$ is minimized by selecting the $m$ atoms of $x$ with the largest probabilities and renormalizing their weights. This confirms that deterministic greedy resampling of top-weight particles is optimal in the reverse KL sense.
Knowl 4 — Split Sequential Monte Carlo Online Clustering Algorithm
algorithm
The Split SMC algorithm processes observations sequentially, updating independent subproblem particle sets and restructuring them via merge and split operations.
Input: Stream of observations $x_1, x_2, \dots, x_T$ , max particles per subproblem $m$ , DPMM likelihood and concentration $\alpha$
Output: Particle approximation of posterior clusterings
Initialize $E_1^1 = \{x_1\}$ , $\mathcal{P}_1^1 = \{\{\{x_1\}\}\}$ , $w_1^{(1,1)} = 1$ , $S = 1$
for $t = 2$ to $T$ do
    // 1. Putative expansion
     $\tilde{\mathcal{P}}_t \leftarrow \emptyset$
    for each subproblem $s \in \{1, \dots, S\}$ do
        for each particle $p \in \mathcal{P}_{t-1}^s$ with weight $w$ do
            for each cluster $c \in p$ do
                 $p' \leftarrow (p \setminus \{c\}) \cup \{c \cup \{x_t\}\}$
                 $w' \leftarrow w \cdot p(x_t \in c \mid p, x_{1:t-1})$
                Add $(p', w', s)$ to $\tilde{\mathcal{P}}_t$
             $p_{singleton} \leftarrow p \cup \{\{x_t\}\}$
             $w_{singleton} \leftarrow w \cdot p(x_t \in \emptyset \mid p, x_{1:t-1})$
            Add $(p_{singleton}, w_{singleton}, s)$ to $\tilde{\mathcal{P}}_t$
    Keep singleton assignment $p_{singleton}$ only for the subproblem $s$ with highest likelihood; discard other singletons
    Greedily select top $m$ weighted putative particles from $\tilde{\mathcal{P}}_t$

    // 2. Merge check
     $\mathcal{S}_{active} \leftarrow \{s : \text{total weight of putative particles in subproblem } s > 1/m\}$
    if $|\mathcal{S}_{active}| == 1$ then
        Assign $x_t$ to subproblem $s^* \in \mathcal{S}_{active}$ , update $\mathcal{P}_t^{s^*}$ with resampled particles
    else
        Merge subproblems in $\mathcal{S}_{active}$ by forming Cartesian product $\bigotimes_{j \in \mathcal{S}_{active}} \mathcal{P}_{t-1}^j$
        Resample merged particle set to $m$ particles using greedy selection (or multinomial merge if $|\mathcal{S}_{active}| > 2$ )

    // 3. Split step
    for each affected subproblem $s$ do
        Construct graph $G=(V, E)$ where $V = E_t^s$ and $(u, v) \in E$ if $u, v$ co-occur in any cluster across particles in $\mathcal{P}_t^s$
        Find connected components $\{K_1, K_2, \dots\}$ of $G$
        if number of components $> 1$ then
            Replace subproblem $s$ with a new independent subproblem for each connected component $K_r$
            Compute marginal clusterings and weights for each new subproblem
return Final particle set
Knowl 5 — Subproblem Splitting via Particle Co-occurrence Graphs
definition
In the split step of Split SMC, independence between subsets of data is detected by constructing an undirected co-occurrence graph $G = (V, E)$ for each active subproblem $E_t^s$ .

The vertex set is the set of observations in that subproblem, $V = E_t^s$ . An undirected edge $(u, v) \in E$ is added between observations $u, v \in E_t^s$ if and only if there exists at least one particle $p \in \mathcal{P}_t^s$ in which $u$ and $v$ belong to the same cluster $c \in p$ .

The graph $G$ is decomposed into its connected components $\{E_t^{s, 1}, \dots, E_t^{s, C}\}$ . If $C > 1$ , the subproblem is replaced by $C$ new independent subproblems. For each component $E_t^{s, k}$ , its marginal particle set and weights are given by:

$\mathcal{P}_t^{s, k} = \left\{ p \cap C_t^{s, k} \mid p \in \mathcal{P}_t^s \right\}, \quad w_t^{(s, k, i)} = \sum_{j=1}^{|\mathcal{P}_t^s|} w_t^{(s, j)} \mathbb{I}\left[ p_t^{(s, k, i)} \subseteq p_t^{(s, j)} \right]$

where $C_t^{s, k} = \left\{ c \in \bigcup_{p \in \mathcal{P}_t^s} p : c \subseteq E_t^{s, k} \right\}$ is the set of all clusters containing only elements of $E_t^{s, k}$ .
Knowl 6 — Subproblem Merging and Multinomial Merge Fallback
model/method
When a newly observed data point $x_t$ receives non-zero assignment probability across multiple existing subproblems $\mathcal{S} \subseteq \{1, \dots, S\}$ , the subproblem decomposition must be unified into a single joint subproblem.

For exact merging, each updated putative particle $\tilde{p}_t(s, i, c)$ is paired with every particle configuration $p'$ from the Cartesian product $\bigotimes_{j \in \mathcal{S} \setminus \{s\}} \mathcal{P}_{t-1}^j$ :

$p_{\mathrm{joint}} = \tilde{p}_t(s, i, c) \cup p', \quad w_{\mathrm{joint}} = \tilde{w}_t(s, i, c) \times \prod_{j \in \mathcal{S} \setminus \{s\}} w_{t-1}^{(j, \cdot)}$

The merged particle set is formed by greedily selecting the $m$ top-weighted joint configurations.

To prevent computational bottlenecks when $|\mathcal{S}| > 2$ and at least 3 subproblems have more than one particle, a three-stage multinomial merge is used instead:
1. Sample $m$ assignments of $x_t$ with replacement from the marginal distribution of assignment weights.
2. For each sampled assignment, independently sample one particle from each other involved subproblem.
3. Combine the clusters and merge duplicate particles.
Knowl 7 — Surrogate Proposal Mechanism for Expensive Likelihood Models
model/method
Evaluating complex cluster likelihoods (e.g. neural language models or variational diffusion models) for every putative cluster assignment in online SMC can be computationally prohibitive. Split SMC uses a lightweight surrogate likelihood $p_{\mathrm{surr}}$ as a proposal mechanism.

In each update step:
1. Candidate cluster assignments are scored under the surrogate DPMM posterior.
2. The top $m'$ non-singleton particles are greedily selected according to surrogate weights.
3. Putative particles corresponding to singleton cluster creation ( $c = \emptyset$ ) are automatically retained to prevent premature pruning due to potential miscalibration between the surrogate likelihood and the target DPMM concentration parameter $\alpha$ .
4. Only the retained proposed particles and singletons (at most $m' + 1$ evaluations per subproblem particle) are evaluated under the expensive target likelihood model.
5. The particles are re-weighted by their target posterior weights and greedily resampled down to $m$ particles.

Knowl 8 — Empirical Performance Comparison Across Synthetic and NLP Clustering Tasks

data/table

Split Sequential Monte Carlo ( $m = 100$ ) was evaluated against Greedy clustering, standard Vanilla SMC ( $m = 100$ ), MCMC (Gibbs / Metropolis-within-Gibbs), and Agglomerative clustering across 2D geometric datasets (Circles with 306 points / 15 clusters; GMM with 700 points / 80 clusters) and Wikipedia/Twitter entity fragment datasets (REBEL-50, REBEL-200, TweetNERD).

Dataset	Metric	Greedy	SMC	Split SMC	MCMC	Agglomerative
Circles	Log posterior	-906 (175)	-202 (92)	10 (74)	187 (15)	-81 (48)
	F1	0.46 (0.06)	0.73 (0.04)	0.82 (0.05)	0.81 (0.02)	0.73 (0.04)
	Runtime (min)	1.4	1.6	5.1	54.7	54.7
Gaussian Mixture	Log posterior	-1539 (34)	-1497 (30)	-1424 (7)	-1428 (2)	-1425 (0)
	F1	0.78 (0.03)	0.81 (0.03)	0.88 (0.01)	0.88 (0.01)	0.87 (0.00)
	Runtime (min)	0.2	0.4	1.7	54.4	239.9
REBEL-50	Log posterior	-8674 (27)	-8791 (52)	-8644 (17)	-8709 (19)	-8543 (0)
	F1	0.66 (0.01)	0.65 (0.01)	0.68 (0.01)	0.63 (0.01)	0.63 (0.00)
	Runtime (min)	1.4	1.4	1.6	172.8	172.2
REBEL-200	Log posterior	-35382 (115)	-36096 (137)	-35297 (108)	–	–
	F1	0.69 (0.01)	0.69 (0.01)	0.70 (0.01)	–	–
	Runtime (min)	6.6	18.5	11.0	–	–
TweetNERD	Log posterior	-31780 (123)	-32923 (221)	-31705 (110)	–	–
	F1	0.51 (0.01)	0.56 (0.01)	0.55 (0.01)	–	–
	Runtime (min)	163.7	51.5	128.0	–	–

Split SMC consistently outperforms Vanilla SMC and Greedy clustering in log-posterior probability and F1 clustering accuracy while matching or exceeding offline MCMC and Agglomerative baselines at a fraction of their runtime. On large datasets (REBEL-200 and TweetNERD), offline baselines failed to converge within a $10^4$ -second budget.

Knowl 9 — Effective Particle Set Size Scaling in Split SMC
empirical result
Because Split SMC represents the joint distribution across $S$ subproblems as a product space $\bigotimes_{s=1}^S \mathcal{P}_t^s$ , the effective number of particles implicitly maintained by the algorithm is $\prod_{s=1}^S |\mathcal{P}_t^s|$ . While the physical storage and per-update computation scale at most linearly with the dataset size ( $O(S \cdot m)$ ), the effective sample size is orders of magnitude larger than standard SMC with $m$ particles.

Empirically, as the per-subproblem budget $m$ increases from small values (e.g., $m=10$ ) to larger values, the number of independent subproblems $S$ decreases slightly (since larger $m$ preserves lower-probability linking hypotheses) before leveling off. However, the log effective sample size $\sum_{s=1}^S \log m_s$ grows rapidly (reaching effective sizes on the order of $e^{30}$ for 2D Circles, $e^{130}$ for GMM, and $e^{280}$ for REBEL-200), allowing the filter to maintain uncertainty across distant entities without particle depletion.
Knowl 10 — Regularization and Accuracy Impact of Surrogate Proposals in Online Clustering
empirical result
Ablation of the surrogate proposal budget $m'$ in sequential clustering reveals that using a lightweight surrogate model (Gaussian mixture for 2D data, character-level bigram DPMM for entity text) not only reduces compute time but also regularizes online clustering.

In online clustering with complex neural likelihoods, over-optimizing the true model likelihood early in the sequence can lead to irreversible incorrect merges. On the Circles dataset, increasing model evaluations by bypassing the surrogate proposal decreased the log-posterior density and dropped F1 accuracy. On out-of-domain text data (TweetNERD), filtering candidates through the n-gram surrogate prior prevented the neural model from committing to erroneous high-entropy links, improving clustering accuracy compared to greedy unguided likelihood optimization.

Coverage note — None was omitted; all key contributions including the theoretical factorisation bounds, greedy resampling properties, algorithm mechanics, surrogate proposal framework, scaling properties, and empirical evaluation are covered.

References

1.A. Bagga and B. Baldwin. Entity-based cross-document coreferencing using the vector space model. In COLING 1998 Volume 1: The 17th International Conference on Computational Linguistics, 1998.
2.J. D. Banfield and A. E. Raftery. Model-based Gaussian and non-Gaussian clustering. Biometrics, 49(3): 803–821, 1993.
3.O. Benjelloun, H. Garcia-Molina, D. Menestrina, Q. Su, S. E. Whang, and J. Widom. Swoosh: a generic approach to entity resolution. The VLDB Journal, 18:255–276, 2009.
4.A. Bouchard-Côté, A. Doucet, and A. Roth. Particle Gibbs split-merge sampling for Bayesian inference in mixture models. Journal of Machine Learning Research, 18(28):1–39, 2017.
5.J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q. Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http://github.com/google/jax.
6.K. Canini, L. Shi, and T. Griffiths. Online inference of topics with latent Dirichlet allocation. In Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, volume 5 of Proceedings of Machine Learning Research, pages 65–72. PMLR, 16–18 Apr 2009.
7.J. Carpenter, P. Clifford, and P. Fearnhead. An improved particle filter for non-linear problems. IEE Proceedings Radar Sonar and Navigation, 146(1):2–7, 1999.
8.J.-T. Chien. The shared Dirichlet priors for Bayesian language modeling. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2081–2085, 2015.
9.T. M. Cover. Elements of Information Theory. John Wiley & Sons, 1999.
10.A. Doucet, N. Freitas, and N. Gordon. Sequential Monte Carlo Methods in Practice. Statistics for Engineering and Information Science. Springer New York, New York, NY, 2001.
11.M. D. Escobar and M. West. Bayesian density estimation and inference using mixtures. Journal of the American Statistical Association, 90(430):577–588, 1995.
12.W. Ewens. The sampling theory of selectively neutral alleles. Theoretical Population Biology, 3(1):87–112, 1972.
13.P. Fearnhead. Particle filters for mixture models with an unknown number of components. Statistics and Computing, 14(1):11–21, 2004.
14.P. Fearnhead and P. Clifford. On-line inference for hidden Markov models via particle filters. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 65(4):887–899, 2003.
15.H. Ge, Y. Chen, M. Wan, and Z. Ghahramani. Distributed inference for Dirichlet process mixture models. In F. Bach and D. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 2276–2284, Lille, France, 07–09 Jul 2015. PMLR.
16.C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant. Array programming with NumPy. Nature, 585(7825):357–362, Sept. 2020.
17.J. Heek, A. Levskaya, A. Oliver, M. Ritter, B. Rondepierre, A. Steiner, and M. van Zee. Flax: A neural network library and ecosystem for JAX, 2023. URL http://github.com/google/flax.
18.K. A. Heller and Z. Ghahramani. Bayesian hierarchical clustering. In Proceedings of the 22nd International Conference on Machine learning, pages 297–304, 2005.
19.P.-L. Huguet Cabot and R. Navigli. REBEL: Relation Extraction By End-to-end Language generation. In Findings of the Association for Computational Linguistics: EMNLP 2021. Association for Computational Linguistics, Nov. 2021.
20.A. K. Jain and R. C. Dubes. Algorithms for clustering data. Prentice-Hall, Inc., USA, 1988. ISBN 013022278X.
21.N. Kantas, A. Doucet, S. S. Singh, J. Maciejowski, and N. Chopin. On particle methods for parameter estimation in state-space models. Statistical Science, 30(3):328 – 351, 2015.
22.D. P. Kingma, T. Salimans, B. Poole, and J. Ho. Variational diffusion models. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY, USA, 2021. Curran Associates Inc.
23.T. Koo, F. Liu, and L. He. Automata-based constraints for language model decoding. In First Conference on Language Modeling, 2024.
24.I. Kruusamägi. Johannes Gutenberg (kass), 2024. CC BY-SA 4.0, via Wikimedia Commons. Cropped from original.
25.K. Kurihara, M. Welling, and Y. W. Teh. Collapsed variational Dirichlet process mixture models. In Proceedings of the 20th International Joint Conference on Artifical Intelligence, IJCAI’07, page 2796–2801, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc.
26.J. Lee, A. Chen, Z. Dai, D. Dua, D. S. Sachan, M. Boratko, Y. Luan, S. M. R. Arnold, V. Perot, S. Dalmia, H. Hu, X. Lin, P. Pasupat, A. Amini, J. R. Cole, S. Riedel, I. Naim, M.-W. Chang, and K. Guu. Can long-context language models subsume retrieval, RAG, SQL, and more? arXiv preprint 2406.13121, 2024.
27.P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W.-t. Yih, T. Rocktäschel, S. Riedel, and D. Kiela. Retrieval-augmented generation for knowledge-intensive NLP tasks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS ’20, Red Hook, NY, USA, 2020. Curran Associates Inc.
28.N. G. Marchant, A. Kaplan, D. N. Elazar, B. I. P. Rubinstein, and R. C. Steorts. d-blink: Distributed end-to-end Bayesian entity resolution. Journal of Computational and Graphical Statistics, 30(2):406–421, 2021.
29.J. McAuliffe, D. Blei, and M. Jordan. Nonparametric empirical Bayes for the Dirichlet process mixture model. Statistics and Computing, 16:5–14, 03 2006.
30.S. Mishra, A. Saini, R. Makki, S. Mehta, A. Haghighi, and A. Mollahosseini. TweetNERD - end to end entity linking benchmark for tweets. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA, 2022. Curran Associates Inc.
31.K. P. Murphy. Probabilistic Machine Learning: Advanced Topics. MIT Press, 2023. August 2022 draft.
32.R. M. Neal. Markov chain sampling methods for Dirichlet process mixture models. Journal of Computational and Graphical Statistics, 9(2):249–265, 2000.
33.A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: an imperative style, high-performance deep learning library. Curran Associates Inc., Red Hook, NY, USA, 2019.
34.D. J. Pearce. An improved algorithm for finding the strongly connected components of a directed graph. Technical report, Victoria University, Wellington, NZ, 2005.
35.M. D. Scherreik. Online clustering with Bayesian nonparametrics. 2020.
36.R. Sennrich, B. Haddow, and A. Birch. Neural machine translation of rare words with subword units. In K. Erk and N. A. Smith, editors, Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1715–1725, Berlin, Germany, Aug. 2016. Association for Computational Linguistics.
37.Ö. Sevgili, A. Shelmanov, M. Arkhipov, A. Panchenko, and C. Biemann. Neural entity linking: A survey of models based on deep learning. Semantic Web, 13(3):527–570, 2022.
38.N. Shazeer. GLU variants improve transformer. arXiv preprint 2002.05202, 2020.
39.J. Su, M. Ahmed, Y. Lu, S. Pan, W. Bo, and Y. Liu. RoFormer: Enhanced transformer with rotary position embedding. Neurocomputing, 568:127063, 2024.
40.P. Szekely, C. A. Knoblock, J. Slepicka, A. Philpot, A. Singh, C. Yin, D. Kapoor, P. Natarajan, D. Marcu, K. Knight, D. Stallard, S. S. Karunamoorthy, R. Bojanapalli, S. Minton, B. Amanatullah, T. Hughes, M. Tamayo, D. Flynt, R. Artiss, S.-F. Chang, T. Chen, G. Hiebel, and L. Ferreira. Building and using a knowledge graph to combat human trafficking. In The Semantic Web - ISWC 2015, pages 205–221, Cham, 2015. Springer International Publishing.
41.A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 6000–6010, Red Hook, NY, USA, 2017. Curran Associates Inc.
42.P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, İ. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261–272, 2020.
43.X. Wang, T. Isazawa, L. Mikaelyan, and J. Hensman. KBLam: Knowledge base augmented language model. In The Thirteenth International Conference on Learning Representations, 2025.
44.G. Weikum and M. Theobald. From information to knowledge: harvesting entities and relationships from web sources. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’10, page 65–76, New York, NY, USA, 2010. Association for Computing Machinery.
45.Wikimedia Foundation. Wikidata, 2012. URL https://www.wikidata.org.
46.J. Winn, M. Venanzi, T. Minka, I. Korostelev, J. Guiver, E. Pochernina, P. Mishkov, A. Spengler, D. Wilkins, S. Lindley, R. Banks, S. Webster, and Y. Zaykov. Enterprise Alexandria: Online high-precision enterprise knowledge base construction with typed entities. In 3rd Conference on Automated Knowledge Base Construction, 2021.
47.K. Zaporojets, L.-A. Kaffee, J. Deleu, T. Demeester, C. Develder, and I. Augenstein. TempEL: Linking dynamically evolving and newly emerging entities. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 1850–1866. Curran Associates, Inc., 2022.
48.B. Zhang and R. Sennrich. Root mean square layer normalization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.

Citation

MLA

Trojan, C., et al. “Scalable Model-Based Clustering with Sequential Monte Carlo”. arXiv, 2026, http://arxiv.org/abs/2604.14810v1.

APA

Trojan, C., Myshkov, P., Fearnhead, P., Hensman, J., Minka, T., & Nemeth, C. (2026). Scalable Model-Based Clustering with Sequential Monte Carlo. arXiv. http://arxiv.org/abs/2604.14810v1

Chicago

Trojan, C., P. Myshkov, P. Fearnhead, J. Hensman, T. Minka, and C. Nemeth. 2026. “Scalable Model-Based Clustering with Sequential Monte Carlo”. arXiv. http://arxiv.org/abs/2604.14810v1.

Harvard

Trojan, C. et al. (2026) “Scalable Model-Based Clustering with Sequential Monte Carlo”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2604.14810v1.

Vancouver

1. Trojan C, Myshkov P, Fearnhead P, Hensman J, Minka T, Nemeth C (2026) Scalable Model-Based Clustering with Sequential Monte Carlo. arXiv

BibTeX

@article{trojan2026scalable,
  title = {Scalable Model-Based Clustering with Sequential Monte Carlo},
  author = {Trojan, Connie and Myshkov, Pavel and Fearnhead, Paul and Hensman, James and Minka, Tom and Nemeth, Christopher},
  year = {2026},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2604.14810v1},
  eprint = {2604.14810}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Scalable Model-Based Clustering with Sequential Monte Carlo

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Split Sequential Monte Carlo Framework for Online Clustering

Knowl 2 — Reverse KL Divergence Minimization via Subproblem Factorization

Knowl 3 — Optimality of Greedy Resampling Under Reverse KL Divergence

Knowl 4 — Split Sequential Monte Carlo Online Clustering Algorithm

Knowl 5 — Subproblem Splitting via Particle Co-occurrence Graphs

Knowl 6 — Subproblem Merging and Multinomial Merge Fallback

Knowl 7 — Surrogate Proposal Mechanism for Expensive Likelihood Models