# Generalized Binary Search For Split-Neighborly Problems

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2018.

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

- [Teaching an Active Learner with Contrastive Examples](https://mlsanity.com/paper/2110.14888/) (2021)
- [Geometry-Aware Active Learning of Pattern Rankings via Choquet-Based Aggregation](https://mlsanity.com/paper/2507.14217/) (2025)

## Abstract (arXiv)

In sequential hypothesis testing, Generalized Binary Search (GBS) greedily chooses the test with the highest information gain at each step. It is known that GBS obtains the gold standard query cost of O(log n) for problems satisfying the k-neighborly condition, which requires any two tests to be connected by a sequence of tests where neighboring tests disagree on at most k hypotheses. In this paper, we introduce a weaker condition, split-neighborly, which requires that for the set of hypotheses two neighbors disagree on, any subset is splittable by some test. For four problems that are not k-neighborly for any constant k, we prove that they are split-neighborly, which allows us to obtain the optimal O(log n) worst-case query cost.