Bayesian Binary Search

## Abstract

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.

## 1 Introduction

The concept of organizing data for efficient searching has ancient roots. One of the earliest known examples is the Inakibit-Anu tablet from Babylon (c. 200 BCE), which contained approximately 500 sorted sexagesimal numbers and their reciprocals, facilitating easier searches Knuth (). Similar sorting techniques were evident in name lists discovered on the Aegean Islands. The Catholicon, a Latin dictionary completed in 1286 CE, marked a significant advance by introducing rules for complete alphabetical classification Knuth ().

The documented modern era of search algorithms began in 1946 when John Mauchly first mentioned binary search during the seminal Moore School Lectures Knuth (). This was followed by William Wesley Peterson’s introduction of interpolation search in 1957 Peterson (). A limitation of early binary search algorithms was their restriction to arrays with lengths one less than a power of two. This constraint was overcome in 1960 by Derrick Henry Lehmer, who published a generalized binary search algorithm applicable to arrays of any length Lehmer (). A significant optimization came in 1962 when Hermann Bottenbruch presented an ALGOL 60 implementation of binary search that moved the equality comparison to the end of the process Bottenbruch (). While this increased the average number of iterations by one, it reduced the number of comparisons per iteration to one, potentially improving efficiency. Further refinements to binary search continued, with A. K. Chandra of Stanford University developing the uniform binary search in 1971 Knuth (). This variant aimed to provide more consistent performance across different input distributions. In the realm of computational geometry, Bernard Chazelle and Leonidas J. Guibas introduced fractional cascading in 1986 Chazelle & Guibas (). This technique provided a method to solve various search problems efficiently in geometric contexts, broadening the application of search algorithms beyond simple sorted lists. More recently, (Mohammed et al., ), proposed a hybrid search algorithm combining binary search and interpolated search to optimize search on datasets with non-uniform distributions.

The bisection method, a fundamental technique in numerical analysis, shares conceptual similarities with binary search. This method, also known as the interval halving method, binary chopping, or Bolzano’s method, has origins of the bisection method can be traced back to ancient mathematics. However, its formal description is often attributed to Bolzano’s work in the early 19th century Russ (). Bolzano’s theorem, which guarantees the existence of a root in a continuous function that changes sign over an interval, provides the theoretical basis for the bisection method. In the context of root-finding algorithms, Burden & Faires () provide a comprehensive treatment of the bisection method, discussing its convergence properties and error bounds. They highlight the method’s robustness and guaranteed convergence, albeit at a relatively slow linear rate. Variants of the bisection method have been developed to improve efficiency and applicability. Horstein () first introduced probabilistic bisection. Hansen & Walster () employed interval analysis and bisection to develop reliable methods for finding global optima. Their work demonstrates how bisection principles can be extended beyond simple root-finding to more complex optimization problems.

The connection between bisection and binary search in computer science was explored by Knuth (), who discussed both methods in the context of searching and optimization algorithms. This connection underlies our approach in leveraging probabilistic techniques to enhance binary search. Recent work has focused on adapting bisection methods to handle uncertainty and noise. Waeber et al. () introduced a probabilistic bisection algorithm for noisy root-finding problems. Their method, which updates a probability distribution over the root location based on noisy measurements, shares conceptual similarities with our Bayesian Binary Search approach. In the context of stochastic optimization, Jedynak et al. () developed a probabilistic bisection algorithm for binary classification problems. Their work demonstrates how Bayesian updating can be incorporated into the bisection process, providing a precedent for our probabilistic approach to binary search. The bisection method has also found applications in various fields beyond pure mathematics. For instance, Nievergelt () discussed the use of parallel bisection methods in scientific computing, highlighting the potential for algorithmic improvements through parallelization.

Probabilistic machine learning, as described by Ghahramani (), provides a framework for reasoning about uncertainty in data and models. Gaussian Processes (GPs), a cornerstone of many probabilistic machine learning methods, were extensively explored by Rasmussen & Williams (). GPs offer a flexible, non-parametric approach to modeling distributions over functions, making them particularly suitable for tasks involving uncertainty quantification. In recent years, Bayesian deep learning has emerged as a powerful approach to combining the expressiveness of deep neural networks with principled uncertainty quantification. Wang & Yeung () provide a comprehensive survey of Bayesian deep learning techniques, discussing various methods for incorporating uncertainty into deep neural networks and their applications in complex, high-dimensional problems. The field of Bayesian Optimization, which shares conceptual similarities with our work, has seen substantial growth. Shahriari et al. () provide a comprehensive overview of Bayesian Optimization techniques, highlighting their effectiveness in optimizing expensive-to-evaluate functions. These methods typically use GPs, Bayesian Neural Networks (BNNs) or other probabilistic models to guide the optimization process, analogous to our use of probability density estimates in Bayesian Binary Search.

## 2 Methodology

### 2.1 Classical Binary Search/Bisection

Binary search is an efficient algorithm for finding a target value in a defined search space. It repeatedly divides the search interval in half, eliminating half of the remaining space at each step. The algorithm maintains two boundaries, low and high, and computes the midpoint mid = (low + high) / 2. By evaluating the midpoint and comparing it to the target value, it determines which half of the search space to explore next, updating either low or high accordingly. This process continues until the target is found or the search space is exhausted. The efficiency of binary search stems from its ability to halve the potential search space with each iteration, resulting in a logarithmic time complexity.

### 2.2 Bayesian Binary Search (BBS)

#### 2.2.1 Problem Formulation

Given a search space $S$ and a target value $t$, our aim is to locate $t$ in $S$, or produce a specifoed range for t with a given tolerance. Unlike classical binary search, we assume that the distribution of potential target locations is not uniform across $S$. We represent this non-uniform distribution using a probability density function (PDF) $p(x)$, where $x\in S$. We formulate the binary search algorithm in two parts: search space density estimation, which produces a PDF that is fed into a modified binary search algorithm which begins at the median of the PDF and bisects in probability density space. BBS is equivalent to basic binary search when the search space PDF estimation process is replaced with the assumption of a uniformly distributed target space. This formulation maps to a binary search problem on a sorted array in the following way: the search space S corresponds to the sorted array, the target value t is the element being searched for, and the PDF p(x) represents the probability of finding the target at each index in the array using interpolation.

### 2.3 Search Space Probability Density Function Estimation

The effectiveness of BBS depends on the accuracy of the PDF estimation. Some methods for estimating $p(x)$ can include:

#### 2.3.1 Supervised Learning Approaches

- •
Gaussian Process Regression (GPR): GPR provides a non-parametric way to model the PDF, offering both a mean prediction and uncertainty estimates.
- •
Bayesian Neural Networks (BNN): BNNs combine the flexibility of neural networks with Bayesian inference, allowing for uncertainty quantification in the predictions.
- •
Quantile Regression: Quantile regression estimates the conditional quantiles of a response variable, providing a more comprehensive view of the relationship between variables across different parts of the distribution, without assuming a particular parametric form for the underlying distribution.

#### 2.3.2 Unsupervised Learning Approaches

- •
Gaussian Mixture Models (GMM): GMMs (typically fit using the Expectation-Maximization (EM) algorithm) can model complex, multimodal distributions by representing the PDF as a weighted sum of Gaussian components.
- •
Kernel Density Estimation (KDE): KDE is a non-parametric method for estimating PDFs, which can capture complex shapes without assuming a specific functional form.
- •
Maxmimum Likelihood Estimation (MLE): MLE is a method of estimating the parameters of a probability distribution by maximizing a likelihood function. It can be used to fit various parametric distributions (e.g., normal, exponential, Poisson) to data, providing a PDF that best explains the observed samples according to the chosen distribution family.

### 2.4 Binary Search with Probabilistic Bisection

BBS modifies the classical binary search by replacing the midpoint calculation with a probabilistic bisection step. Instead of dividing the search space at the midpoint, BBS divides it at the median of the current PDF. Formally, at each step, we find $x^{*}$ such that:

$$ $\int_{low}^{x^{*}}p(x)dx=\int_{x^{*}}^{high}p(x)dx=0.5$ (1) $$

After each comparison, we update the PDF based on the result. If the target is found to be in the lower half, we set $p(x)=0$ for $x>x^{*}$ and renormalize the PDF. Similarly, if the target is in the upper half, we set $p(x)=0$ for $x<x^{*}$ and renormalize.

Figure: Algorithm 1 Bayesian Binary Search

Figure: Algorithm 2 Estimate Search Space Probability Density Function (PDF)

Figure: Algorithm 3 FindMedian Function

Figure: Algorithm 4 UpdatePDF Function

Figure: Algorithm 5 Sign Function

We evaluate BBS against basic binary search on both simulated data across several distributions and a real world example of binary search/bisection of probing channels in the Bitcoin Lightning Network, for which accessing the search space is an expensive operations (time and liquidity) Tikhomirov et al. ().

### 2.5 Experiments on Simulated Data

We evaluate the performance of BBS against binary search on simulated data from several distributions: normal, bimodal and exponential. The results of the normal distribution experiments are shown below, while the results of the bimodal and exponential distributions can be found in the appendix. We additionally show experiments for which the estimated search space density function does not match the target search space as measured by Kullback-Leibler (KL) Divergence. We demonstrate how BBS performance degrades as the estimated search space density drifts further from the target distribution, and eventually can cause the BBS to perform worse than basic binary search.

#### 2.5.1 Experimental Setup

To evaluate the performance of BBS compared to the standard binary search in the context of normal distributions, we conducted a series of experiments with the following setup:

#### 2.5.2 Distribution Parameters

For the normal distribution experiments, we used the following parameters:

- •
Mean ($\mu$): 0
- •
Standard Deviation ($\sigma$): 100

#### 2.5.3 Target Values Generation

We generated 1,000 target values by sampling from the specified normal distribution. Each target value was obtained by drawing a random sample $x$ from the distribution and applying the floor function to ensure integer targets: $target=\text{floor}(x)$.

#### 2.5.4 Search Procedure

For each target value, both search algorithms attempt to locate the target within a specified precision ($\epsilon$), set to 8. The search space is initialized based on the properties of the normal distribution:

- •
Lower Bound ($lo$): $\text{floor}(\mu-4.2\times\sigma)$
- •
Upper Bound ($hi$): $\text{ceil}(\mu+4.2\times\sigma)$

The algorithms iteratively narrow down the search space until the target is found within the acceptable error margin.

#### 2.5.5 Metrics Collected

We collected the following performance metrics:

- •
Number of Steps: Total iterations required to find each target.
- •
Bracket Size: The range ($hi-lo$) at each step of the search.

**Table 1: $\mu=0.0$, $\sigma=10000.0$, $N=500$**
| $\epsilon$ | Percent Decrease | Basic Mean Steps | BBS Mean Steps |
| --- | --- | --- | --- |
| 1 | 6.30% | 16.47 $\pm$ 0.50 | 15.43 $\pm$ 1.19 |
| 2 | 6.36% | 15.68 $\pm$ 0.47 | 14.68 $\pm$ 1.15 |
| 3 | 6.17% | 15.00 $\pm$ 0.00 | 14.07 $\pm$ 1.15 |
| 4 | 8.76% | 15.00 $\pm$ 0.00 | 13.69 $\pm$ 1.11 |
| 5 | 5.06% | 14.15 $\pm$ 0.36 | 13.43 $\pm$ 1.02 |
| 6 | 6.16% | 14.00 $\pm$ 0.00 | 13.14 $\pm$ 1.09 |
| 7 | 8.07% | 14.00 $\pm$ 0.00 | 12.87 $\pm$ 1.16 |
| 8 | 9.39% | 14.00 $\pm$ 0.00 | 12.69 $\pm$ 1.12 |
| 9 | 10.27% | 14.00 $\pm$ 0.00 | 12.56 $\pm$ 1.08 |
| 10 | 6.14% | 13.28 $\pm$ 0.45 | 12.47 $\pm$ 1.01 |
| 11 | 4.63% | 13.00 $\pm$ 0.00 | 12.40 $\pm$ 0.99 |
| 12 | 5.88% | 13.00 $\pm$ 0.00 | 12.24 $\pm$ 1.05 |
| 13 | 7.43% | 13.00 $\pm$ 0.00 | 12.03 $\pm$ 1.13 |
| 14 | 8.51% | 13.00 $\pm$ 0.00 | 11.89 $\pm$ 1.15 |
| 15 | 9.32% | 13.00 $\pm$ 0.00 | 11.79 $\pm$ 1.15 |
| 16 | 9.89% | 13.00 $\pm$ 0.00 | 11.71 $\pm$ 1.12 |
| 17 | 10.49% | 13.00 $\pm$ 0.00 | 11.64 $\pm$ 1.11 |
| 18 | 11.03% | 13.00 $\pm$ 0.00 | 11.57 $\pm$ 1.09 |
| 19 | 11.42% | 13.00 $\pm$ 0.00 | 11.52 $\pm$ 1.05 |
| 20 | 8.38% | 12.53 $\pm$ 0.50 | 11.48 $\pm$ 1.03 |
| 21 | 4.52% | 12.00 $\pm$ 0.00 | 11.46 $\pm$ 1.01 |
| 22 | 4.80% | 12.00 $\pm$ 0.00 | 11.42 $\pm$ 0.97 |
| 23 | 5.07% | 12.00 $\pm$ 0.00 | 11.39 $\pm$ 0.95 |
| 24 | 5.83% | 12.00 $\pm$ 0.00 | 11.30 $\pm$ 1.01 |
| 25 | 7.12% | 12.00 $\pm$ 0.00 | 11.15 $\pm$ 1.10 |
| 26 | 8.03% | 12.00 $\pm$ 0.00 | 11.04 $\pm$ 1.13 |
| 27 | 8.43% | 12.00 $\pm$ 0.00 | 10.99 $\pm$ 1.14 |
| 28 | 9.17% | 12.00 $\pm$ 0.00 | 10.90 $\pm$ 1.15 |
| 29 | 9.55% | 12.00 $\pm$ 0.00 | 10.85 $\pm$ 1.15 |
| 30 | 10.02% | 12.00 $\pm$ 0.00 | 10.80 $\pm$ 1.15 |
| 31 | 10.33% | 12.00 $\pm$ 0.00 | 10.76 $\pm$ 1.14 |
| 32 | 10.57% | 12.00 $\pm$ 0.00 | 10.73 $\pm$ 1.13 |

Figure: Figure 1: Normal Distribution: Basic vs. BBS Convergence Comparison
Refer to caption: x1.png

### 2.6 Experiments on Lightning Network Channel Probing

Probing a channel in the Lightning Network is the construction of a fake payment to be sent through the network to obtain information on the balance of a channel. Typically, it is currently performed using a basic binary search.

For search space density estimation in the Lightning Network channel probing experiment, we detail a random forest model to predict the search target (channel balance in this case). We construct a PDF from the prediction of the random forest using kernel density estimation (KDE) on the predictions of individual predictors (trees) in the ensemble. We alternatively could use Bayesian Neural Networks or a Gaussian Process Regressor, but the random forest yielded superior predictive performance in our experiments (Rossi et al., ).

#### 2.6.1 Description of Channel Balance Prediction Task

The Lightning Network can be modeled as a directed graph $G=(V,E)$, where $V$ represents the set of nodes and $E$ represents the set of edges. Each node $u$ and each edge $(u,v)$ have associated features, denoted by $\mathbf{x}_{u}\in\mathbb{R}^{k}$ for nodes and $\mathbf{e}_{(u,v)}$ for edges, which contain specific information about those nodes and edges. Additionally, each edge $(u,v)$ has a scalar value $y_{(u,v)}\geq 0$, representing the pre-allocated balance for transactions from $u$ to $v$.

Graph $G$ has the constraint that if an edge exists in one direction, it must also exist in the opposite direction, i.e., $(u,v)\in E\iff(v,u)\in E$. The set of two edges between any two nodes is called a channel, denoted as $\{(u,v),(v,u)\}$. For simplicity, we represent a channel by the set of its two nodes: $\{u,v\}$. The total capacity of the channel $\{u,v\}$ is defined as $c_{\{u,v\}}=y_{(u,v)}+y_{(v,u)}$.

We are provided with the total channel capacities $c_{\{u,v\}}$ for all channels in the graph, but we only know the individual values $y_{(u,v)}$ for a subset of edges. Note that knowing $y_{(u,v)}$ allows us to determine $y_{(v,u)}$, since $y_{(v,u)}=c_{\{u,v\}}-y_{(u,v)}$. Therefore, we can focus on predicting $y_{(u,v)}$.

Moreover, since we are given $c_{\{u,v\}}$ for all edges, and we know $0\leq y_{(u,v)}\leq c_{\{u,v\}}$, we also have that $y_{(u,v)}=p_{(u,v)}c_{\{u,v\}}$, where $0\leq p_{(u,v)}\leq 1$. Intuitively, $p_{(u,v)}$ is the proportion of the channel capacity which belongs to the $(u,v)$ direction. From this, we see that we focus on predicting $p_{(u,v)}$, and then use it to obtain $y_{(u,v)}$.

Therefore, our primary task is to predict $p_{(u,v)}$ for all edges where it is not observed.

#### 2.6.2 Data Collection and Preprocessing

The data used in this experiment is a combination of publicly available information from the Lightning Network and crowdsourced information from nodes in the network.
A snapshot of the network from December 15th, 2023 is used in this experiment. Balance information for each node is represented by its local balance, recorded at one-minute intervals over the preceding hour. This data is converted into a probability density function (PDF) through kernel density estimation. Subsequently, a balance value is sampled from each PDF, serving as the representative local balance for the corresponding channel within the dataset.

### 2.7 Methodology

The following section outlines the details of our modeling approach.

#### 2.7.1 Modeling

We will predict $p_{(u,v)}$ by learning a parametric function:

$$ $\hat{p}_{(u,v)}=f_{\Theta}(u,v,G,\mathbf{x}_{u},\mathbf{x}_{v},\mathbf{e}_{(u, v)},c_{\{u,v\}})$ $$

where $\Theta$ are learnable weights, $\mathbf{x}_{u}$, $\mathbf{x}_{v}$ and $\mathbf{e}_{(u,v)}$ are the node and edge features respectively, while $c_{\{u,v\}}$ is the capacity of the channel.
While several choices are possible for $f_{\Theta}$, such as multi-layer perceptrons ( Rosenblatt ()) or Graph Neural Networks, we focus on Random Forests for this work given their simplicity and efficacy. In particular, our Random Forest (RF) model operates on the concatenation of the features of the source and destination nodes as well as the edge features:

$$ $\hat{p}_{(u,v)}=\mathrm{RF}(x_{u}||z_{u}||x_{v}||z_{v}||e_{(u,v)})$ $$

The model is trained using a Mean Squared Error loss.

#### 2.7.2 Node Features

- •
Node Feature Flags
0-1 vector indicating which of the features each node supports. For example, feature flag 19, the wumbo flag.
- •
Capacity Centrality
The node’s capacity divided by the network’s capacity. This indicates how much of the network’s capacity is incident to a node.
- •
Fee Ratio
Ratio of the mean cost of a nodes outgoing fees to the mean cost of its incoming fees.

#### 2.7.3 Edge Features

- •
Time Lock Delta
The number of blocks a relayed payment is locked into an HTLC.
- •
Min HTLC
The minimum amount this edge will route. (denominated in millisats)
- •
Max HTLC msat
The maximum amount this edge will route. (denominated in millisats)
- •
Fee Rate millimsat
Proportional fee to route a payment along an edge. (denominated in millimillisats)
- •
Fee Base msat
Fixed fee to route a payment along an edge. (denominated in millisats)

#### 2.7.4 Positional Encodings

Positional encoding is essential for capturing the structural context of nodes, as graphs lack inherent sequential order. Utilizing eigenvectors of the graph Laplacian matrix as positional encodings provides a robust solution to this challenge. These eigenvectors highlight key structural patterns, enriching node features with information about the overall topology of the graphDwivedi et al. (). By integrating these spectral properties, machine learning models can effectively recognize and utilize global characteristics, enhancing performance in tasks like node classification and community detection.

#### 2.7.5 Concatenated Prediction ML Model

Our model predicts $p_{(u,v)}$ as a function of the concatenation of the features of the source and destination nodes as well as edge features:

$$ $\hat{p}_{(u,v)}=\mathrm{RF}(x_{u}||x_{v}||e_{(u,v)})$ $$

#### 2.7.6 Model Training Details and Performance

We set aside $10\%$ of the observed $y_{(u,v)}$ as our test set and $10\%$ as our validation set. The RF model trained for balance prediction has an MAE of 1.08, an R of 0.612 and $R^{2}$ of 0.365. For the BBS experiments, we use the predictions on the validation set (89 channels). For validation set channels, we feed the predictions of each tree in the ensemble (100) into a kernel density estimation (KDE) process to construct the search space PDF. Using these constructed PDFs, we compare BBS with basic binary search in measuring how many probes it would take to ascertain the balance of a given channel.

**Table 2: Lightning Channel Probing Comparison**
| $\epsilon$ | Percent Decrease | Basic Mean Steps | BBS Mean Steps |
| --- | --- | --- | --- |
| 128 | 3.07% | 14.26 $\pm$ 2.26 | 13.82 $\pm$ 2.35 |
| 256 | 3.31% | 13.26 $\pm$ 2.26 | 12.82 $\pm$ 2.35 |
| 512 | 3.57% | 12.26 $\pm$ 2.26 | 11.82 $\pm$ 2.35 |
| 1024 | 3.89% | 11.26 $\pm$ 2.26 | 10.82 $\pm$ 2.35 |
| 2048 | 4.27% | 10.26 $\pm$ 2.26 | 9.82 $\pm$ 2.35 |
| 4096 | 4.73% | 9.26 $\pm$ 2.26 | 8.82 $\pm$ 2.35 |
| 8192 | 5.03% | 8.26 $\pm$ 2.26 | 7.84 $\pm$ 2.30 |
| 16384 | 5.73% | 7.26 $\pm$ 2.26 | 6.84 $\pm$ 2.29 |

Figure: Figure 2: Lightning Probing Experiment: Basic vs. BBS Convergence Comparison
Refer to caption: x2.png

## 3 Discussion

Our experimental results demonstrate the potential of Bayesian Binary Search (BBS) as a promising alternative to classical binary search/bisection, particularly in scenarios where the search space exhibits non-uniform distributions and is costly to access. The performance improvements observed in both simulated environments and real-world applications, such as probing payment channels in the Bitcoin Lightning Network, highlight the promise of BBS. However, it is important to consider these findings in a broader context and acknowledge the limitations and implications of our work.

### 3.1 Theoretical Alignment and Performance Gains

The superior performance of BBS over classical binary search in non-uniform distributions aligns with our theoretical expectations. By leveraging probabilistic information about the search space, BBS can make more informed decisions at each step, leading to faster convergence on average. This is particularly evident in our simulated experiments with skewed distributions, where BBS consistently required fewer steps to locate the target. The ability of BBS to adapt to the underlying distribution of the search space represents an advance in the design of search algorithms, and a fusion of search theory and probabilistic machine learning/statistical learning.

### 3.2 Real-World Application and Implications

In the context of the Bitcoin Lightning Network, the improvement in probing efficiency could have significant practical implications. Faster and more accurate channel capacity discovery can enhance routing algorithms, potentially leading to improved transaction success rates. Crucially, probes in the Lightning Network consume network-wide computational resources, as each probe requires processing by multiple nodes along potential payment routes. By using BBS to enhance probe efficiency, we effectively reduce unnecessary network load, akin to removing spam from the system. This reduction in network overhead could lead to improved overall network performance and scalability.

### 3.3 Limitations and Challenges

Despite the promising results, several limitations of our study should be acknowledged:

- 1.
Computational Overhead: The improved search efficiency of BBS comes at the cost of increased computational complexity, particularly in the PDF estimation step. This overhead may offset the reduction in search steps for certain applications, especially those dealing with small search spaces or requiring extremely fast operation.
- 2.
PDF Estimation Accuracy: The performance of BBS is heavily dependent on the accuracy of the PDF estimation. In scenarios where the underlying distribution is highly complex or rapidly changing, the chosen PDF estimation method may struggle to provide accurate probabilities, potentially leading to suboptimal performance.

### 3.4 Future Research Directions

Our findings open up several exciting avenues for future research:

- 1.
Adaptive PDF Estimation: Developing methods to dynamically adjust the PDF estimation technique based on the observed search space characteristics could further improve the robustness and efficiency of BBS.
- 2.
Theoretical Bounds: While we provide empirical evidence of BBS’s effectiveness, deriving tighter theoretical bounds on its performance under various distribution types would strengthen its theoretical foundation.
- 3.
Application to Other Domains: Exploring the applicability of BBS to other areas such as database indexing, computational biology, or optimization algorithms could reveal new use cases and challenges.

### 3.5 Conclusion

Bayesian Binary Search represents a significant step towards more adaptive and efficient search algorithms. By incorporating probabilistic information, BBS demonstrates the potential to outperform classical binary search in non-uniform distributions, as evidenced by our experiments in both simulated and real-world scenarios. In the context of the Lightning Network, BBS not only improves search efficiency but also contributes to reducing unnecessary network load, potentially enhancing the overall performance and scalability of the system. The promising results open up new possibilities for optimizing search processes in various domains. As we continue to navigate increasingly complex and data-rich environments, algorithms like BBS that can adapt to the underlying structure of the problem space will become increasingly valuable. Future work in this direction has the potential to not only improve search efficiency but also to deepen our understanding of how probabilistic approaches can enhance fundamental algorithms in computer science and their real-world applications.

## Appendix A Appendix

### A.1 BBS on Imperfect Search Space Density Estimation

The performance of BBS depends on the accuracy of the search space density estimation. To demonstrate the performance of BBS on varying degrees of accuracy in search space density estimation, we run experiments in which the estimated search space probability density function is a given Kullback-Leibler (KL) divergence from the target normal distribution of the search space.

We derive a new normal distribution with a specified KL divergence to a target distribution below:

Given:

- •
Target distribution: $N(\mu_{1},\sigma_{1}^{2})$
- •
Desired KL divergence: $D$

We want to find parameters $\mu_{2}$ and $\sigma_{2}$ for a new distribution $N(\mu_{2},\sigma_{2}^{2})$ such that:

$$ $KL(N(\mu_{1},\sigma_{1}^{2})||N(\mu_{2},\sigma_{2}^{2}))=D$ $$

The KL divergence between two normal distributions is given by:

$$ $KL(N(\mu_{1},\sigma_{1}^{2})||N(\mu_{2},\sigma_{2}^{2}))=\log\frac{\sigma_{2}} {\sigma_{1}}+\frac{\sigma_{1}^{2}+(\mu_{1}-\mu_{2})^{2}}{2\sigma_{2}^{2}}- \frac{1}{2}$ $$

For simplicity, let’s assume $\sigma_{2}=\sigma_{1}$. Then the equation simplifies to:

$$ $D=\frac{(\mu_{1}-\mu_{2})^{2}}{2\sigma_{1}^{2}}$ $$

Solving for $\mu_{2}$:

$$ $\displaystyle D$ $\displaystyle=\frac{(\mu_{1}-\mu_{2})^{2}}{2\sigma_{1}^{2}}$ $\displaystyle 2D\sigma_{1}^{2}$ $\displaystyle=(\mu_{1}-\mu_{2})^{2}$ $\displaystyle\sqrt{2D\sigma_{1}^{2}}$ $\displaystyle=|\mu_{1}-\mu_{2}|$ $\displaystyle\mu_{2}$ $\displaystyle=\mu_{1}\pm\sqrt{2D\sigma_{1}^{2}}$ $$

We choose the positive solution:

$$ $\mu_{2}=\mu_{1}+\sqrt{2D\sigma_{1}^{2}}$ $$

Therefore, the parameters of the new distribution are:

$$ $\displaystyle\mu_{2}$ $\displaystyle=\mu_{1}+\sqrt{2D\sigma_{1}^{2}}$ $\displaystyle\sigma_{2}$ $\displaystyle=\sigma_{1}$ $$

This ensures that:

$$ $KL(N(\mu_{1},\sigma_{1}^{2})||N(\mu_{2},\sigma_{2}^{2}))=D$ $$

**Table 3: $\mu=0.0$, $\sigma=1000.0$, $\epsilon=10$, $N=200$**
| KLD | Percent Decrease | Basic Mean Steps | Bayesian Mean Steps |
| --- | --- | --- | --- |
| 0.0 | 9.40% | 10.00 $\pm$ 0.00 | 9.06 $\pm$ 0.95 |
| 0.05 | 8.85% | 10.00 $\pm$ 0.00 | 9.12 $\pm$ 1.07 |
| 0.1 | 7.70% | 10.00 $\pm$ 0.00 | 9.23 $\pm$ 1.12 |
| 0.15 | 6.95% | 10.00 $\pm$ 0.00 | 9.30 $\pm$ 1.19 |
| 0.2 | 6.35% | 10.00 $\pm$ 0.00 | 9.37 $\pm$ 1.26 |
| 0.25 | 6.15% | 10.00 $\pm$ 0.00 | 9.38 $\pm$ 1.34 |
| 0.3 | 4.90% | 10.00 $\pm$ 0.00 | 9.51 $\pm$ 1.40 |
| 0.35 | 4.35% | 10.00 $\pm$ 0.00 | 9.56 $\pm$ 1.44 |
| 0.4 | 3.00% | 10.00 $\pm$ 0.00 | 9.70 $\pm$ 1.42 |
| 0.45 | 2.25% | 10.00 $\pm$ 0.00 | 9.78 $\pm$ 1.56 |
| 0.5 | 1.20% | 10.00 $\pm$ 0.00 | 9.88 $\pm$ 1.62 |
| 0.55 | 0.60% | 10.00 $\pm$ 0.00 | 9.94 $\pm$ 1.65 |
| 0.6 | 0.60% | 10.00 $\pm$ 0.00 | 9.94 $\pm$ 1.66 |
| 0.65 | -0.20% | 10.00 $\pm$ 0.00 | 10.02 $\pm$ 1.77 |
| 0.7 | -0.90% | 10.00 $\pm$ 0.00 | 10.09 $\pm$ 1.80 |
| 0.75 | -1.90% | 10.00 $\pm$ 0.00 | 10.19 $\pm$ 1.87 |
| 0.8 | -2.75% | 10.00 $\pm$ 0.00 | 10.28 $\pm$ 1.94 |
| 0.85 | -3.35% | 10.00 $\pm$ 0.00 | 10.34 $\pm$ 2.00 |
| 0.9 | -4.10% | 10.00 $\pm$ 0.00 | 10.41 $\pm$ 2.00 |
| 0.95 | -4.85% | 10.00 $\pm$ 0.00 | 10.48 $\pm$ 2.03 |

Figure: Figure 3: Basic vs BBS Convergence with KLD Separation of Estimated Search Space PDF and Actual PDF
Refer to caption: x3.png

**Table 4: Bimodal Params, $\mu_{1}=0,\sigma_{1}=1000,\mu_{2}=4000,\sigma_{2}=1000,w_{1}=0.5$**
| $\epsilon$ | Percent Decrease | Basic Mean Steps | Bayesian Mean Steps |
| --- | --- | --- | --- |
| 1 | 3.14% | 13.38 $\pm$ 0.49 | 12.96 $\pm$ 0.99 |
| 2 | 2.38% | 12.58 $\pm$ 0.50 | 12.28 $\pm$ 0.90 |
| 3 | 2.67% | 12.00 $\pm$ 0.00 | 11.68 $\pm$ 0.79 |
| 4 | 4.22% | 11.86 $\pm$ 0.35 | 11.36 $\pm$ 0.72 |
| 5 | 0.36% | 11.00 $\pm$ 0.00 | 10.96 $\pm$ 0.78 |
| 6 | 2.91% | 11.00 $\pm$ 0.00 | 10.68 $\pm$ 0.82 |
| 7 | 4.55% | 11.00 $\pm$ 0.00 | 10.50 $\pm$ 0.74 |
| 8 | 5.27% | 11.00 $\pm$ 0.00 | 10.42 $\pm$ 0.64 |
| 9 | 1.53% | 10.48 $\pm$ 0.50 | 10.32 $\pm$ 0.51 |
| 10 | 0.40% | 10.00 $\pm$ 0.00 | 9.96 $\pm$ 0.78 |
| 11 | 2.80% | 10.00 $\pm$ 0.00 | 9.72 $\pm$ 0.81 |
| 12 | 3.80% | 10.00 $\pm$ 0.00 | 9.62 $\pm$ 0.75 |
| 13 | 4.40% | 10.00 $\pm$ 0.00 | 9.56 $\pm$ 0.76 |
| 14 | 5.00% | 10.00 $\pm$ 0.00 | 9.50 $\pm$ 0.71 |
| 15 | 5.60% | 10.00 $\pm$ 0.00 | 9.44 $\pm$ 0.67 |
| 16 | 5.80% | 10.00 $\pm$ 0.00 | 9.42 $\pm$ 0.64 |
| 17 | 6.40% | 10.00 $\pm$ 0.00 | 9.36 $\pm$ 0.56 |
| 18 | 6.60% | 10.00 $\pm$ 0.00 | 9.34 $\pm$ 0.52 |
| 19 | -1.98% | 9.08 $\pm$ 0.27 | 9.26 $\pm$ 0.56 |
| 20 | 0.00% | 9.00 $\pm$ 0.00 | 9.00 $\pm$ 0.78 |
| 21 | 1.78% | 9.00 $\pm$ 0.00 | 8.84 $\pm$ 0.84 |
| 22 | 2.67% | 9.00 $\pm$ 0.00 | 8.76 $\pm$ 0.74 |
| 23 | 3.78% | 9.00 $\pm$ 0.00 | 8.66 $\pm$ 0.75 |
| 24 | 4.00% | 9.00 $\pm$ 0.00 | 8.64 $\pm$ 0.75 |
| 25 | 4.00% | 9.00 $\pm$ 0.00 | 8.64 $\pm$ 0.75 |
| 26 | 4.44% | 9.00 $\pm$ 0.00 | 8.60 $\pm$ 0.76 |
| 27 | 4.44% | 9.00 $\pm$ 0.00 | 8.60 $\pm$ 0.76 |
| 28 | 5.11% | 9.00 $\pm$ 0.00 | 8.54 $\pm$ 0.76 |
| 29 | 6.00% | 9.00 $\pm$ 0.00 | 8.46 $\pm$ 0.68 |
| 30 | 6.22% | 9.00 $\pm$ 0.00 | 8.44 $\pm$ 0.67 |
| 31 | 6.44% | 9.00 $\pm$ 0.00 | 8.42 $\pm$ 0.64 |
| 32 | 6.67% | 9.00 $\pm$ 0.00 | 8.40 $\pm$ 0.61 |

Figure: Figure 4: Bimodal Distribution: Basic vs. BBS Convergence Comparison
Refer to caption: x4.png

**Table 5: Exponential Params, scale=10000**
| $\epsilon$ | Percent Decrease | Basic Mean Steps | Bayesian Mean Steps |
| --- | --- | --- | --- |
| 1 | 12.86% | 16.87 $\pm$ 0.34 | 14.70 $\pm$ 1.41 |
| 2 | 13.03% | 16.00 $\pm$ 0.00 | 13.91 $\pm$ 1.34 |
| 3 | 14.40% | 15.55 $\pm$ 0.50 | 13.31 $\pm$ 1.37 |
| 4 | 13.07% | 15.00 $\pm$ 0.00 | 13.04 $\pm$ 1.33 |
| 5 | 15.10% | 15.00 $\pm$ 0.00 | 12.73 $\pm$ 1.35 |
| 6 | 17.17% | 15.00 $\pm$ 0.00 | 12.43 $\pm$ 1.36 |
| 7 | 13.01% | 14.03 $\pm$ 0.16 | 12.20 $\pm$ 1.37 |
| 8 | 13.75% | 14.00 $\pm$ 0.00 | 12.07 $\pm$ 1.34 |
| 9 | 14.39% | 14.00 $\pm$ 0.00 | 11.98 $\pm$ 1.31 |
| 10 | 15.54% | 14.00 $\pm$ 0.00 | 11.82 $\pm$ 1.34 |
| 11 | 16.89% | 14.00 $\pm$ 0.00 | 11.63 $\pm$ 1.36 |
| 12 | 18.11% | 14.00 $\pm$ 0.00 | 11.46 $\pm$ 1.36 |
| 13 | 19.00% | 14.00 $\pm$ 0.00 | 11.34 $\pm$ 1.35 |
| 14 | 13.83% | 13.05 $\pm$ 0.23 | 11.25 $\pm$ 1.36 |
| 15 | 14.27% | 13.00 $\pm$ 0.00 | 11.14 $\pm$ 1.37 |
| 16 | 14.62% | 13.00 $\pm$ 0.00 | 11.10 $\pm$ 1.37 |
| 17 | 15.00% | 13.00 $\pm$ 0.00 | 11.05 $\pm$ 1.34 |
| 18 | 15.38% | 13.00 $\pm$ 0.00 | 11.00 $\pm$ 1.32 |
| 19 | 15.65% | 13.00 $\pm$ 0.00 | 10.96 $\pm$ 1.32 |
| 20 | 16.42% | 13.00 $\pm$ 0.00 | 10.87 $\pm$ 1.34 |
| 21 | 17.35% | 13.00 $\pm$ 0.00 | 10.74 $\pm$ 1.36 |
| 22 | 18.19% | 13.00 $\pm$ 0.00 | 10.63 $\pm$ 1.36 |
| 23 | 18.50% | 13.00 $\pm$ 0.00 | 10.60 $\pm$ 1.37 |
| 24 | 19.08% | 13.00 $\pm$ 0.00 | 10.52 $\pm$ 1.34 |
| 25 | 19.81% | 13.00 $\pm$ 0.00 | 10.43 $\pm$ 1.35 |
| 26 | 20.15% | 13.00 $\pm$ 0.00 | 10.38 $\pm$ 1.34 |
| 27 | 20.77% | 13.00 $\pm$ 0.00 | 10.30 $\pm$ 1.34 |
| 28 | 15.42% | 12.13 $\pm$ 0.34 | 10.26 $\pm$ 1.36 |
| 29 | 14.92% | 12.00 $\pm$ 0.00 | 10.21 $\pm$ 1.37 |
| 30 | 15.42% | 12.00 $\pm$ 0.00 | 10.15 $\pm$ 1.37 |
| 31 | 15.58% | 12.00 $\pm$ 0.00 | 10.13 $\pm$ 1.37 |
| 32 | 15.75% | 12.00 $\pm$ 0.00 | 10.11 $\pm$ 1.37 |

Figure: Figure 5: Exponential Distribution: Basic vs. BBS Convergence Comparison
Refer to caption: x5.png

### A.2 Binary Search Tree Visualization Comparison

To visualize the difference between the execution of BBS and standard binary search in a normally distributed search space $\mu=5$, $\sigma=1.15$, we show binary search trees (BSTs) for basic binary search and BBS over 10000 iterations of the experiment. We observe a significantly higher percentage of BBS searches terminating at a depth of 2, where all basic searches in this experiment terminate at depth 3 or 4. The bracket represents the search interval, and the number below for internal nodes represents the median of that search interval. The number below the bracket for the green leaf nodes represent how many times the search terminated at that leaf.

Figure: Figure 6: Binary Search Tree
Refer to caption: x6.png

Figure: Figure 7: Bayesian Binary Search Tree
Refer to caption: x7.png

## Peer Reviews

confidence: 3
contribution: 1
initial_rating: 1
presentation: 1
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?
soundness: 1
strengths: The authors ask a good research question --- how we should perform binary search when the uniform distribution assumption does not hold.
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.
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.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 1
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.
soundness: 2
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.
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.
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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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?
soundness: 3
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
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.
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

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
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
soundness: 2
strengths: - The experiments show some improvements over a simple baseline.
- A realistic application is considered: probing channel balances in the Bitcoin Lightning Network.
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.
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?

Meta-review: 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.

Decision: Reject