# Firefly Monte Carlo: Exact MCMC with Subsets of Data

arXiv: https://arxiv.org/abs/1403.5693 · HTML: https://mlsanity.com/paper/1403.5693/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2014.

## Built on by (most cited first, 23 of 23)

- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [A Survey of Monte Carlo Methods for Parameter Estimation](https://mlsanity.com/paper/2107.11820/) (2021)
- [Surrogate Likelihoods for Variational Annealed Importance Sampling](https://mlsanity.com/paper/2112.12194/) (2021)
- [Bayesian inference via sparse Hamiltonian flows](https://mlsanity.com/paper/2203.05723/) (2022)
- [Mitigating belief projection in explainable artificial intelligence via Bayesian Teaching](https://mlsanity.com/paper/2102.03919/) (2021)
- [Fast Bayesian Coresets via Subsampling and Quasi-Newton Refinement](https://mlsanity.com/paper/2203.09675/) (2022)
- [Energy based diffusion generator for efficient sampling of Boltzmann distributions](https://mlsanity.com/paper/2401.02080/) (2024)
- [Entropy-MCMC: Sampling from Flat Basins with Ease](https://mlsanity.com/paper/2310.05401/) (2023)
- [Variational Inference for Bayesian Neural Networks under Model and Parameter Uncertainty](https://mlsanity.com/paper/2305.00934/) (2023)
- [Coreset Markov Chain Monte Carlo](https://mlsanity.com/paper/2310.17063/) (2023)
- [Bayesian Pseudo-Coresets via Contrastive Divergence](https://mlsanity.com/paper/2303.11278/) (2023)
- [Machine Learning and the Future of Bayesian Computation](https://mlsanity.com/paper/2304.11251/) (2023)
- [Structure Learning with Adaptive Random Neighborhood Informed MCMC](https://mlsanity.com/paper/2311.00599/) (2023)
- [General bounds on the quality of Bayesian coresets](https://mlsanity.com/paper/2405.11780/) (2024)
- [On MCMC for variationally sparse Gaussian processes: A pseudo-marginal approach](https://mlsanity.com/paper/2103.03321/) (2021)
- [CEDAR: Communication Efficient Distributed Analysis for Regressions](https://mlsanity.com/paper/2207.00306/) (2022)
- [Bayesian Computation in Deep Learning](https://mlsanity.com/paper/2502.18300/) (2025)
- [Scalable Bayesian Monte Carlo: fast uncertainty estimation beyond deep ensembles](https://mlsanity.com/paper/2505.13585/) (2025)
- [How To Train Your Program: a Probabilistic Programming Pattern for Bayesian Learning From Data](https://mlsanity.com/paper/2105.03650/) (2021)
- [Cyclical Kernel Adaptive Metropolis](https://mlsanity.com/paper/2206.14421/) (2022)
- [The surrogate Gibbs-posterior of a corrected stochastic MALA: Towards uncertainty quantification for neural networks](https://mlsanity.com/paper/2310.09335/) (2023)
- [Markov chain Monte Carlo without evaluating the target: an auxiliary variable approach](https://mlsanity.com/paper/2406.05242/) (2024)
- [Efficient MCMC Sampling with Expensive-to-Compute and Irregular Likelihoods](https://mlsanity.com/paper/2505.10448/) (2025)

## Abstract (arXiv)

Markov chain Monte Carlo (MCMC) is a popular and successful general-purpose tool for Bayesian inference. However, MCMC cannot be practically applied to large data sets because of the prohibitive cost of evaluating every likelihood term at every iteration. Here we present Firefly Monte Carlo (FlyMC) an auxiliary variable MCMC algorithm that only queries the likelihoods of a potentially small subset of the data at each iteration yet simulates from the exact posterior distribution, in contrast to recent proposals that are approximate even in the asymptotic limit. FlyMC is compatible with a wide variety of modern MCMC algorithms, and only requires a lower bound on the per-datum likelihood factors. In experiments, we find that FlyMC generates samples from the posterior more than an order of magnitude faster than regular MCMC, opening up MCMC methods to larger datasets than were previously considered feasible.