# Bayesian Binary Search

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 22 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Builds on (most cited first, 4 of 4)

- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Towards Bayesian Deep Learning: A Framework and Some Existing Methods](https://mlsanity.com/paper/1608.06884/) (2016)
- [Channel Balance Interpolation in the Lightning Network via Machine Learning](https://mlsanity.com/paper/2405.12087/) (2024)
- [Probing Channel Balances in the Lightning Network](https://mlsanity.com/paper/2004.00333/) (2020)

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

- [Predicting Channel Closures in the Lightning Network with Machine Learning](https://mlsanity.com/paper/2605.12759/) (2026)

## Abstract (arXiv)

We present Bayesian Binary Search (BBS), a novel probabilistic variant of the classical binary search/bisection algorithm. BBS leverages machine learning/statistical techniques to estimate the probability density of the search space and modifies the bisection step to split based on probability density rather than the traditional midpoint, allowing for the learned distribution of the search space to guide the search algorithm. Search space density estimation can flexibly be performed using supervised probabilistic machine learning techniques (e.g., Gaussian process regression, Bayesian neural networks, quantile regression) or unsupervised learning algorithms (e.g., Gaussian mixture models, kernel density estimation (KDE), maximum likelihood estimation (MLE)). We demonstrate significant efficiency gains of using BBS on both simulated data across a variety of distributions and in a real-world binary search use case of probing channel balances in the Bitcoin Lightning Network, for which we have deployed the BBS algorithm in a production setting.