Proof.: The API returns the (re-ordered) token \(0\) as long as the logit bias added is smaller than \(\mathsf{logit}_{i}-\mathsf{logit}_{0}\). By the assumption, we know that \(\mathsf{logit}_{i}-\mathsf{logit}_{0}\in[-B,0]\). The algorithm ensures that \(\beta_{i}\geq\mathsf{logit}_{i}-\mathsf{logit}_{0}\geq\alpha_{i}\) at each iteration, as can be seen easily by an inductive argument. Further, \(\beta_{i}-\alpha_{i}\) decreases by a factor of \(2\) in each iteration, and hence at termination, we can see that the true value of \(\mathsf{logit}_{i}-\mathsf{logit}_{0}\) is sandwiched in an interval of length \(\varepsilon\). Furthermore, it is clear that the number of iterations is at most \(\log_{2}\left(\frac{B}{\varepsilon}\right)\) and hence so is the query cost of this algorithm.