Introduction
In fields like drug discovery and materials science, researchers often search for "needles in a haystack"—rare molecules or alloys with highly specific, desirable properties. Traditionally, this involves active search: sequentially picking a data point, testing it with an expensive "oracle" (like a lab experiment), and using the result to inform the next choice.
The primary bottleneck in this process is cost, as high-fidelity lab experiments are slow and expensive. However, researchers frequently have access to "low-fidelity" surrogates, such as computational simulations, which are cheap and fast but less accurate. This paper introduces MF-ENS (Multifidelity Expected Number of Successes), a novel algorithm designed to solve the multifidelity active search problem. By intelligently balancing a strict experimental budget between expensive, high-fidelity (H) tests and cheap, low-fidelity (L) tests, MF-ENS significantly boosts discovery rates. Unlike "greedy" methods that only look one step ahead, MF-ENS uses a nonmyopic, budget-aware strategy to plan for long-term success.
Methods: The MF-ENS Algorithm
The authors frame the active search problem using Bayesian decision theory. Because calculating the mathematically optimal policy is computationally intractable—requiring a lookahead through every possible future outcome—they propose MF-ENS as an efficient approximation.
Key technical components of the algorithm include:
- Two-Stage Rollout: To decide the next query, the algorithm simulates a future scenario. It assumes that after the current query, it will perform a batch of cheap L-fidelity queries to gather information, followed by a final batch of H-fidelity queries to "collect" targets.
- Nonmyopic Planning: By considering the remaining budget, the algorithm naturally transitions from exploration (using cheap queries to learn the landscape) to exploitation (using expensive queries on the most promising candidates).
- Multifidelity k-NN: The standard k-nearest neighbor classifier is extended to handle data from multiple fidelities, utilizing a damping factor to account for the lower reliability of the noisy oracle.
- Efficient Pruning: To handle massive datasets (100,000+ points), the authors implement "branch-and-bound" pruning. This allows the algorithm to skip calculating scores for points that mathematically cannot be the best next choice.
Experimental Setup
The researchers evaluated MF-ENS on three scientific discovery benchmarks:
- BindingDB (Drug Discovery): Searching for chemical compounds that bind to specific proteins, using 50 different protein targets and 100,000 compounds from the ZINC database.
- BMG (Materials Science): Searching for alloys capable of forming "Bulk Metallic Glasses," prized for their toughness, across a dataset of over 106,000 alloys.
- Simulated Noise: To systematically test the algorithm, they simulated low-fidelity oracles by taking true labels and "flipping" them based on a controllable noise parameter.
Key Insights and Results
MF-ENS consistently outperformed all baselines, including state-of-the-art single-fidelity methods and common multifidelity heuristics like Upper Confidence Bound (UCB).
The Value of "Cheap" Information: Even highly noisy simulations drastically improved the efficiency of expensive experiments. On the drug discovery datasets, MF-ENS found roughly 10–15% more targets than the single-fidelity baseline given the exact same high-fidelity budget. Ignoring low-fidelity data proved to be a significant missed opportunity.
Patience Pays Off: Myopic (greedy) policies tend to pick points with the highest immediate probability of being a target. MF-ENS, however, often starts by querying points it is uncertain about. This early "exploration" phase builds a robust model, leading to a much higher "catch rate" in the final stages of the search. As the budget vanishes, the algorithm becomes increasingly greedy, perfectly adapting its behavior to the remaining time.
Statistical tests (paired t-tests) confirmed that these performance gains were highly significant, returning p-values of less than $10^{-5}$ across the experiments.
Limitations and Future Work
While highly effective, the current MF-ENS model has a few limitations:
- Synchronous Assumption: The model assumes a fixed ratio ($k$) between the speed of the two oracles. Adapting the algorithm for asynchronous queries—where experiments finish at irregular, unpredictable times—is a promising direction for future research.
- Independence Heuristic: To keep the math tractable, the policy assumes labels are conditionally independent during the "lookahead" phase. A more complex model of label correlation could potentially yield even better results.
- Real-world Noise: The study primarily relied on simulated noise for the low-fidelity oracle. Testing the algorithm on datasets with "natural" multifidelity labels (e.g., comparing a coarse physics simulation directly to a fine-grained one) remains an important next step for real-world deployment.
Summary updated