Bayesian Binary Search

Authors: Vikash Singh, Matthew Khanzadeh, Vincent Davis, Harrison Rush, Emanuele Rossi, Jesse Shrader, Pietro Lio
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords: bayesian, binary search, bitcoin, lightning network

Abstract:
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.

Decision: reject
Reviewer scores: 1, 3, 6, 5

Reviews and discussion:
<thread>
creation date:
1729439638299

thread_type:
official_review

<thread_object>
creator: reviewer_fj8u

<content>
summary:
The authors revisit bisection by introducing a probability density over the search interval rather than the usual uniform assumption. The main change is to cut where the probability reaches 50% rather than in the middle of the search interval. To estimate the required probability density, several alternatives are proposed. Then some simulation experiments are proposed.

strengths:
- The experiments show some improvements over a simple baseline.
- A realistic application is considered: probing channel balances in the Bitcoin Lightning Network.

weaknesses:
- The problem definition lacks the assumptions: for instance, bisection can only work if the underlying function is monotonous.  Otherwise, the problem may be of contour or level set estimation.
- It is not possible to separate the contribution from what already exists in the literature.
- The comparison is against a single simple baseline. Why not including comparisons with some of the cited references, like Waeber et al., or Jedynak et al?

questions:
Could you clarify the assumptions and highlight better the contribution? 
Under which conditions is the search provably successful? How does it depend on the estimated pdf error?

How is the variance over repeated runs zero in some tables? Perhaps the problem is too simple?

For Bayesian optimization: see e.g., Garnett, R. (2023). Bayesian optimization. Cambridge University Press. And for other probabilistic bisection algorithms: 
- Rodriguez, S., & Ludkovski, M. (2020). Probabilistic bisection with spatial metamodels. European Journal of Operational Research, 286(2), 588-603.
- Frazier, P. I., Henderson, S. G., & Waeber, R. (2019). Probabilistic bisection converges almost as quickly as stochastic approximation. Mathematics of Operations Research, 44(2), 651-667.

Typos:
- specifoed
- Maxmimum
</content>
</thread_object>

</thread>
<thread>
creation date:
1730035753748

thread_type:
official_review

<thread_object>
creator: reviewer_xdts

<content>
summary:
This paper introduces Bayesian Binary Search (BBS), a probabilistic approach compared to the traditional binary search, and it aims to improve search efficiency when the target distribution is non-uniform and the probing is expensive. BBS modifies the traditional binary search by replacing the midpoint splitting with median splitting w.r.t an estimated PDF.

Contributions include
1. Novel algorithm framework: the formulation of BBS integrates PDFs into binary search, and various of PDF estimation methods are supported in this framework. This framework promises better efficiency for non-uniform distribution, while reduces to traditional binary search when the distribution is uniform.
2. BBS demonstrates robust performance through KL divergence simulations, which shows graceful degradation as PDF estimation accuracy decreases
3. Showcase a real-world application in Bitcoin Lightning Network. The development of random forest PDF estimation methods using network features is itself valuable for practical implementations with BBS.

strengths:
Originality
1. Creatively combines classical binary search with probabilistic methods and introduces a flexible framework for incorporating various of PDF estimation methods
2. Provides a new perspective on search optimization through statistical learning

Quality
1. Clear mathematical formulation and intuitive algorithm design
2. Rigorous analysis of robustness of BBS through KL divergence degradation simulation

Clarity
1. The paper is well structured and the clarity is pretty good

Significance
1. Interesting application to Bitcoin Lightning Network
2. This proposed framework can be easily implemented using various existing ML tools, and its significant performance improvements make it highly practical

weaknesses:
1. Lack the theoretic analysis of optimality of median split strategy
2. Lack theoretic analysis for convergence bounds with imperfect PDF estimation
3. The paper mentioned a few methods for PDF estimation (RF, GPR, BNN, etc.), however, only RF was used for the Bitcoin Lighting Network problem. Since PDF estimation is a crucial piece in the algorithm framework, it is necessary to offer comparative analysis among different PDF estimation approaches, as well as discussion of the trade-offs.
4. Simulation study covered only the three basic distributions, but for real-world applications, it is common that the distribution is heavy-tailed or complex. I would expect more comprehensive analysis over real-world distribution patterns

questions:
1. Beyond Lightning Network, can you elaborate on other applications you think would benefit most from BBS?
2. What characteristics make an application suitable for BBS?
3. Other than median splitting strategy, have you considered other strategies in probability space, and what are the trade-offs?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730462306503

thread_type:
official_review

<thread_object>
creator: reviewer_vb7p

<content>
summary:
The authors present a modified version of the standard binary search algorithm by incorporating probabilistic techniques. They consider the input to their Bayesian Binary Search (BBS) algorithm as an ordered sequence of integers, $x_1, \ldots, x_n$, where each $x_i$ is assumed to be an IID sample from an unknown distribution $\mathbb{P}$.

If the distribution $\mathbb{P}$ were known and had a density function $p$, binary search could be optimized by using the median $m$ of the distribution as the pivot:
$$
\int_{-\infty}^m p(x) \, \mathrm{d}x = 0.5
$$
instead of using the midpoint of the current upper and lower bounds in the sequence.

Since the distribution $\mathbb{P}$ is typically unknown, the authors propose estimating the density of the sequence $x_1, \ldots, x_n$ to obtain an approximation $\hat{\mathbb{P}}$ of $\mathbb{P}$, using it as a surrogate in their probabilistic binary search algorithm.

The authors conduct an empirical evaluation of the algorithm, using synthetic data generated from a discretized univariate Gaussian distribution and a real-world dataset from the Lightning Network.

strengths:
BBS is shown to improve efficiency in non-uniform search spaces, as evidenced by lower average steps to reach target values compared to standard binary search, especially in scenarios with a known or estimable distribution of search targets.

The real-world example on the Lightning Network demonstrates a potential real-world use of the algorithm, if implemented appropriately.

weaknesses:
There is nothing "Bayesian" about the proposed algorithm. Perhaps a more appropriate name would be "Probabilistic Binary Search".

On the Lightning network experiment:

The primary weakness of the experiment lies in a misalignment between the stated motivation for Bayesian Binary Search (BBS) and its actual implementation.

- The experiment does not apply BBS to actual probing in the Lightning Network, where probing costs (in terms of network resources and latency) are the main concern. Instead, they simulate probing by using inexpensive predictions from a random forest model, which removes the practical need for BBS to reduce costly network probes.

- Since predictions from the random forest are computationally cheap, the added complexity of BBS (which relies on density estimation and probabilistic bisection) offers limited benefit in this context. 

- There is no reported raw computation time. The added computational overhead of first performing density estimation would likely be much larger than the marginal gains achieved when performing BBS over binary search.

In summary, the experiment does not convincingly demonstrate BBS’s utility in addressing real-world probing expenses. Without actual network interaction, it fails to showcase how BBS would reduce probing costs in a live setting, which is the central argument for its use.

questions:
Have the authors considered demonstrating the use of BBS in a live, online setting, where probing costs are relevant? Since the current experiment is based on offline predictions, it’s unclear if the BBS approach would indeed reduce costs in a real-world probing scenario within the Lightning Network.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730693435280

thread_type:
official_review

<thread_object>
creator: reviewer_4wab

<content>
summary:
This work proposes to use bayesian method to do binary search where the midpoint is not equal to the average of an internal, in contrast to the classical binary search method.

Although this idea sounds interesting, I am not convinced by the proposed method, either based on the experimental results or the presentation.

Experiment:
The authors spent so much time listing all variants of binary search in the introduction. However, during the experiments, the authors only compare with the most basic baseline, ignoring everything the authors have discussed at the beginning.

strengths:
The authors ask a good research question --- how we should perform binary search when the uniform distribution assumption does not hold.

weaknesses:
Lack of baselines. The authors discuss many variants of binary search during introduction. However, none of them are used as baselines for comparison other than the classical binary search method.

Plus, the proposed method described here is not very different from doing active learning using Gaussian Process.

One more thing, doing density estimation can be time consuming. This could ultimately slow down the the search process and be much slower than the classical binary search method.

questions:
Can you compare with all baselines you listed in your introduction paragraph and report results during rebuttal?

How is your method different from active learning via the help of Gaussian Process?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732907824766

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Clarifying Context/Contribution

comment:
We want to thank the reviewers for the thoughtful review and for providing the opportunity to improve the submission with this feedback. The authors would first like to provide some helpful context that we initially encountered this search problem in a real life context (Lightning Network), in which there was a real bisection problem for which we had previously developed a supervised machine learning model to predict the search target (Lightning channel balance). Each search space access here had a time cost, capital cost, and a fundamental domain scalability cost (max htlc limit for Lightning Nodes [akin to max incoming connections for Linux servers], fundamentally impacting network wide payment throughput). Such probing happens at large scale today (millions per day and growing with the network) by large industrial players and startups alike.

[Max HTLC Limit:] (https://docs.lightning.engineering/the-lightning-network/multihop-payments/hash-time-lock-contract-htlc)

The current industrial procedure is to use standard bisection, so we were inspired to understand how we could somehow leverage this ML model to improve the efficiency of search. Ultimately we realized that converting the model into a supervised probabilistic machine learning model which outputs a distribution would allow us to bisect in probability density space, allowing us to leverage our model’s knowledge about this distribution to guide the search.

This prompted us to delve into the literature to see if this was written about, and we were unable to find work that combined this sort of statistical learning with binary search in this way prompting us to write this paper and submit to this conference.

We started by trying to find out what gains would be achieved by bisecting in probability density space vs. regular bisection on a normal distribution, and to our surprise no closed form solution for the convergence of bisecting density space, nor any numerical/experimental results were found in the literature. Even without supervised/unsupervised density estimation, we could not find bisection in the density space well defined in the literature, which made sense given it only makes sense to use if there is a reason to believe a search space is distributed a certain way.

In contextualizing this contribution we primarily believe this to be a binary search/bisection paper via applied machine learning/statistical learning rather than an ML theory paper itself. The way this problem was presented to us in real life was more akin to a number guessing game in a bounded continuous space, in which the oracle would be able to tell us if our search target was above or below the probe, but not when we exactly reached the probe, allowing us to search till we were confident the target was within a given range (epsilon). As such the experiments are structured in this way, impacting our benchmarking approach. We hope this explanation clarifies the contribution of the paper and our general approach.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper presents Bayesian Binary Search (BBS), which modifies traditional binary search by using probability density estimates to guide the search process rather than midpoint splitting. It includes an interesting application to the Bitcoin Lightning Network. However, the approach received mixed reviews from strong reject (4wAb) to "marginally above acceptance threshold" (XdTs), with the average score being well below the “accept” rating..

In terms of strengths, the novel combination of probabilistic methods with binary search that showed improved efficiency in non-uniform search spaces (XdTs and vb7P for ) and the good performance on the “real-world” Lightning Network application (though vb7P raised concerns about experimental methodology).

Multiple reviewers identified consistent critical weaknesses: Reviewer XdTs and Fj8u highlighted a lack of theoretical analysis regarding optimality and convergence bounds; Reviewer 4wAb criticized the limited empirical evaluation and missing baseline comparisons.  The authors pushed back on this, but Fj8u suggested a way of adapting baselines used in the noisy context.  Reviewer 4wAb, Fj8u, (as well as myself) noted the paper's poor fit for ICLR due to its lack of connection to representation learning. Reviewer vb7P questioned computational overhead considerations.

The reviewers and the AC recommend another venue such as AISTATS or ICML where this work might be a better fit. There could be a nice paper here if the authors focused on (1) Developing theoretical foundations, specifically addressing the convergence and optimality concerns raised by Reviewers XdTs and Fj8u; (2) Expanding empirical evaluation to include the sophisticated baselines mentioned by Reviewer 4wAb and the complex distributions requested by Reviewer XdTs; and (3) Addressing Reviewer vb7P's concerns about computational overhead and terminology. The authors' responses show awareness of these issues, particularly in adding Beta and Lognormal distribution results, but more substantial development is needed in both theoretical and empirical aspects before publication.