# BayesSum: Bayesian Quadrature in Discrete Spaces

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 38 of its 88 references that are in the map.
- First posted on arXiv 18 Dec 2025.

## Builds on (most cited first, 30 of 38)

- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Control functionals for Monte Carlo integration](https://mlsanity.com/paper/1410.2392/) (2014)
- [Bayesian Optimisation over Multiple Continuous and Categorical Inputs](https://mlsanity.com/paper/1906.08878/) (2019)
- [Bayesian Probabilistic Numerical Methods](https://mlsanity.com/paper/1702.03673/) (2017)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Stein Points](https://mlsanity.com/paper/1803.10161/) (2018)
- [Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization](https://mlsanity.com/paper/2210.10199/) (2022)
- [Sampling for Inference in Probabilistic Models with Fast Bayesian Quadrature](https://mlsanity.com/paper/1411.0439/) (2014)
- [Convergence Guarantees for Gaussian Process Means With Misspecified Likelihoods and Smoothness](https://mlsanity.com/paper/2001.10818/) (2020)
- [Probabilistic Integration: A Role in Statistical Computation?](https://mlsanity.com/paper/1512.00933/) (2015)
- [Positively Weighted Kernel Quadrature via Subsampling](https://mlsanity.com/paper/2107.09597/) (2021)
- [Gradient Estimation with Discrete Stein Operators](https://mlsanity.com/paper/2202.09497/) (2022)
- [Convergence Guarantees for Adaptive Bayesian Quadrature Methods](https://mlsanity.com/paper/1905.10271/) (2019)
- [Active Multi-Information Source Bayesian Quadrature](https://mlsanity.com/paper/1903.11331/) (2019)
- [Sampling-based Nystr"om Approximation and Kernel Quadrature](https://mlsanity.com/paper/2301.09517/) (2023)
- [On Russian Roulette Estimates for Bayesian Inference with Doubly-Intractable Likelihoods](https://mlsanity.com/paper/1306.4032/) (2013)
- [Convergence Analysis of Deterministic Kernel-Based Quadrature Rules in Misspecified Settings](https://mlsanity.com/paper/1709.00147/) (2017)
- [Bayesian Quadrature for Multiple Related Integrals](https://mlsanity.com/paper/1801.04153/) (2018)
- [Convergence guarantees for kernel-based quadrature rules in misspecified settings](https://mlsanity.com/paper/1605.07254/) (2016)
- [Stein Variational Gradient Descent as Moment Matching](https://mlsanity.com/paper/1810.11693/) (2018)
- [Vector-Valued Control Variates](https://mlsanity.com/paper/2109.08944/) (2021)
- [Optimally-Weighted Estimators of the Maximum Mean Discrepancy for Likelihood-Free Inference](https://mlsanity.com/paper/2301.11674/) (2023)
- [Kernel quadrature with randomly pivoted Cholesky](https://mlsanity.com/paper/2306.03955/) (2023)
- [A Bayes-Sard Cubature Method](https://mlsanity.com/paper/1804.03016/) (2018)
- [A Review of Multivariate Distributions for Count Data Derived from the Poisson Distribution](https://mlsanity.com/paper/1609.00066/) (2016)
- [Conditional Bayesian Quadrature](https://mlsanity.com/paper/2406.16530/) (2024)
- [A Dictionary of Closed-Form Kernel Mean Embeddings](https://mlsanity.com/paper/2504.18830/) (2025)
- [Symmetry Exploits for Bayesian Cubature Methods](https://mlsanity.com/paper/1809.10227/) (2018)
- [Multilevel Bayesian Quadrature](https://mlsanity.com/paper/2210.08329/) (2022)
- [Biological Sequence Kernels with Guaranteed Flexibility](https://mlsanity.com/paper/2304.03775/) (2023)

## Abstract (arXiv)

This paper addresses the challenging computational problem of estimating intractable expectations over discrete domains. Existing approaches, including Monte Carlo and Russian Roulette estimators, are consistent but often require a large number of samples to achieve accurate results. We propose a novel estimator, BayesSum, which is an extension of Bayesian quadrature to discrete domains. It is more sample efficient than alternatives due to its ability to make use of prior information about the integrand through a Gaussian process. We show this through theory, deriving a convergence rate significantly faster than Monte Carlo in a broad range of settings. We also demonstrate empirically that our proposed method does indeed require fewer samples on several synthetic settings as well as for parameter estimation for Conway-Maxwell-Poisson and Potts models.