# Bayesian Binary Search
## 2 Methodology
### Probabilistic Bisection Step
#### 3.1.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. #### 3.1.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. ### 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. If the payment fails, then the balance on that side of the channel is lower than the payment amount; if it succeeds, then the balance is greater than or equal to the payment amount. Typically, it is currently performed using a basic binary search/bisection. The response of a given probe can be viewed as an oracle, which is a continuous and monotonic function, making it suitable for the bisection method as it guarantees that there is only one root of the function. Each probe is computationally expensive and fundamentally constrained in this domain due to the max HTLC (Hashed Timelock Contract) limit (483 on Lightning Network Daemon (LND), the most popular Lightning Node implementation) on each channel in the Lightning Node software implementation for security purposes. Probes occupying this limit fundamentally constrain network throughput, which could otherwise process real payments. The Lightning Network can potentially be probed millions of times a week, underscoring the importance of designing an algorithm that optimizes efficiency. To demonstrate the computational complexity of executing probes on the Lightning Network, we probed 1500 channels from our Lightning Node, with an average hop length of 2.26. The probe time average for each channel has a mean of 3.1 s and a standard deviation of 0.7 s. The density estimation step per channel here in comparison (random forest inference and KDE) takes 0.18 s, and only needs to be performed once per channel. The added overhead of density estimation here is significantly outweighed by the probing computational cost and the domain max HTLC constraint. 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 constructed a PDF from the prediction of the random forest using Kernel Density Estimation (KDE) on the predictions of individual predictors (trees) in the ensemble. Alternatively, we could have used Bayesian Neural Networks or a Gaussian Process Regressor (results in Appendix A), but the random forest yielded superior predictive performance in our experiments [21]. #### 3.2.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\}\).