Bagel: A Fast Bayesian Online Changepoint Detection Algorithm for Linear Models via Posterior Merging
Abstract
Bayesian online changepoint detection provides a natural framework for quantifying uncertainty about whether and when a change has occurred. It also enables the use of prior information which can increase detection power. Exact Bayesian inference sequentially updates the posterior of whether and when a change has occurred. We present a unified approach to calculating and updating this posterior for a class of regression models covering standard changepoint scenarios, such as changes in mean and slope, whilst also allowing common structure such as seasonal effects. However, naive implementation has a computational cost that increases linearly over time. We, further, introduce approximate updates that keep this cost constant. These are based on novel ideas of merging changepoint times, and are an alternative to existing pruning approaches. We show that merging enables better approximations of the posterior of when a change occurs. Furthermore, we introduce a novel condition for merging that accounts for both the posterior probability of the changepoint times and the similarity of their corresponding post-change parameters. We show that this is more accurate than conditions that only consider the former. We demonstrate the advantage of our approach on simulated data, and the Azure LLM inference traces.
Related
- Posterior Regimes and Latent Deception: Variational Bayesian Inference in Hidden Markov Models for Sequential Fraud Detection in Financial Transactions
- Changepoint detection methods as a practical tool for assessment of ecological restoration
- Adaptive online kernel changepoint detection
- Accelerating posterior sampling in Bayesian inverse problems with diffusion models: an online-offline perspective
- Sieve-free ReLU Bayesian priors with near-minimax posterior contraction
BibTeX
@misc{yang2026bagel,
title = {{Bagel: A Fast Bayesian Online Changepoint Detection Algorithm for Linear Models via Posterior Merging}},
author = {Ziyang Yang and Paul Fearnhead and Dan Grose},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03230},
eprint = {2611.03230},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03230},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bagel: A Fast Bayesian Online Changepoint Detection Algorithm for Linear Models via Posterior Merging
AU - Ziyang Yang
AU - Paul Fearnhead
AU - Dan Grose
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03230
UR - https://arxiv.org/abs/2611.03230
AB - Bayesian online changepoint detection provides a natural framework for quantifying uncertainty about whether and when a change has occurred. It also enables the use of prior information which can increase detection power. Exact Bayesian inference sequentially updates the posterior of whether and when a change has occurred. We present a unified approach to calculating and updating this posterior for a class of regression models covering standard changepoint scenarios, such as changes in mean and slope, whilst also allowing common structure such as seasonal effects. However, naive implementation has a computational cost that increases linearly over time. We, further, introduce approximate updates that keep this cost constant. These are based on novel ideas of merging changepoint times, and are an alternative to existing pruning approaches. We show that merging enables better approximations of the posterior of when a change occurs. Furthermore, we introduce a novel condition for merging that accounts for both the posterior probability of the changepoint times and the similarity of their corresponding post-change parameters. We show that this is more accurate than conditions that only consider the former. We demonstrate the advantage of our approach on simulated data, and the Azure LLM inference traces.
ER -