# Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 59 references that are in the map.
- First posted on arXiv 19 Apr 2021.

## Builds on (most cited first, 14 of 14)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [GPflow: A Gaussian process library using TensorFlow](https://mlsanity.com/paper/1610.08733/) (2016)
- [Efficiently Sampling Functions from Gaussian Process Posteriors](https://mlsanity.com/paper/2002.09309/) (2020)
- [Variational Bayesian Optimal Experimental Design](https://mlsanity.com/paper/1903.05480/) (2019)
- [Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2001.11659/) (2020)
- [Interactive Weak Supervision: Learning Useful Heuristics for Data Labeling](https://mlsanity.com/paper/2012.06046/) (2020)
- [Constant-Time Predictive Distributions for Gaussian Processes](https://mlsanity.com/paper/1803.06058/) (2018)
- [Efficient Bayesian Experimental Design for Implicit Models](https://mlsanity.com/paper/1810.09912/) (2018)
- [Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization](https://mlsanity.com/paper/2006.11267/) (2020)
- [Route Planning in Transportation Networks](https://mlsanity.com/paper/1504.05140/) (2015)
- [Sequential Bayesian Experimental Design for Implicit Models via Mutual Information](https://mlsanity.com/paper/2003.09379/) (2020)

## Built on by (most cited first, 30 of 33)

- [Modern Bayesian Experimental Design](https://mlsanity.com/paper/2302.14545/) (2023)
- [Joint Entropy Search for Multi-objective Bayesian Optimization](https://mlsanity.com/paper/2210.02905/) (2022)
- [Discovering Many Diverse Solutions with Bayesian Optimization](https://mlsanity.com/paper/2210.10953/) (2022)
- [BED-LLM: Intelligent Information Gathering with LLMs and Bayesian Experimental Design](https://mlsanity.com/paper/2508.21184/) (2025)
- [A General Framework for User-Guided Bayesian Optimization](https://mlsanity.com/paper/2311.14645/) (2023)
- [Amortized Bayesian Experimental Design for Decision-Making](https://mlsanity.com/paper/2411.02064/) (2024)
- [An Experimental Design Perspective on Model-Based Reinforcement Learning](https://mlsanity.com/paper/2112.05244/) (2021)
- [Stationary Kernels and Gaussian Processes on Lie Groups and their Homogeneous Spaces II: non-compact symmetric spaces](https://mlsanity.com/paper/2301.13088/) (2023)
- [Tanimoto Random Features for Scalable Molecular Machine Learning](https://mlsanity.com/paper/2306.14809/) (2023)
- [DiscoBAX: Discovery of Optimal Intervention Sets in Genomic Experiment Design](https://mlsanity.com/paper/2312.04064/) (2023)
- [Generalizing Bayesian Optimization with Decision-theoretic Entropies](https://mlsanity.com/paper/2210.01383/) (2022)
- [Exploration via Planning for Information about the Optimal Trajectory](https://mlsanity.com/paper/2210.04642/) (2022)
- [Near-optimal Policy Identification in Active Reinforcement Learning](https://mlsanity.com/paper/2212.09510/) (2022)
- [Advancing Deep Active Learning & Data Subset Selection: Unifying Principles with Information-Theory Intuitions](https://mlsanity.com/paper/2401.04305/) (2024)
- [Active Fourier Auditor for Estimating Distributional Properties of ML Models](https://mlsanity.com/paper/2410.08111/) (2024)
- [CO-BED: Information-Theoretic Contextual Optimization via Bayesian Experimental Design](https://mlsanity.com/paper/2302.14015/) (2023)
- [Improving Accuracy of Interpretability Measures in Hyperparameter Optimization via Bayesian Algorithm Execution](https://mlsanity.com/paper/2206.05447/) (2022)
- [Fairness Auditing with Multi-Agent Collaboration](https://mlsanity.com/paper/2402.08522/) (2024)
- [Practical Bayesian Algorithm Execution via Posterior Sampling](https://mlsanity.com/paper/2410.20596/) (2024)
- [End-to-End Optimal Detector Design with Mutual Information Surrogates](https://mlsanity.com/paper/2503.14342/) (2025)
- [Informed Initialization for Bayesian Optimization and Active Learning](https://mlsanity.com/paper/2510.23681/) (2025)
- [Multipoint-BAX: A New Approach for Efficiently Tuning Particle Accelerator Emittance via Virtual Objectives](https://mlsanity.com/paper/2209.04587/) (2022)
- [Efficient Determination of Safety Requirements for Perception Systems](https://mlsanity.com/paper/2307.01371/) (2023)
- [Efficient Nudged Elastic Band Method using Neural Network Bayesian Algorithm Execution](https://mlsanity.com/paper/2512.14993/) (2025)
- [Auditing Fairness under Model Updates: Fundamental Complexity and Property-Preserving Updates](https://mlsanity.com/paper/2601.05909/) (2026)
- [Quantifying Local Model Validity using Active Learning](https://mlsanity.com/paper/2406.07474/) (2024)
- [Increasing Information for Model Predictive Control with Semi-Markov Decision Processes](https://mlsanity.com/paper/2501.17256/) (2025)
- [Curiosity is Knowledge: Self-Consistent Learning and No-Regret Optimization with Active Inference](https://mlsanity.com/paper/2602.06029/) (2026)
- [Pragmatic Curiosity: A Unified Framework for Hybrid Learning and Optimization via Active Inference](https://mlsanity.com/paper/2602.06104/) (2026)
- [Many Needles in a Haystack: Active Hit Discovery for Perturbation Experiments](https://mlsanity.com/paper/2605.10196/) (2026)

## Abstract (arXiv)

In many real-world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. One example is budget constrained global optimization of f, for which Bayesian optimization is a popular method. Other properties of interest include local optima, level sets, integrals, or graph-structured information induced by f. Often, we can find an algorithm A to compute the desired property, but it may require far more than T queries to execute. Given such an A, and a prior distribution over f, we refer to the problem of inferring the output of A using T evaluations as Bayesian Algorithm Execution (BAX). To tackle this problem, we present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. Applying this to Dijkstra's algorithm, for instance, we infer shortest paths in synthetic and real-world graphs with black-box edge costs. Using evolution strategies, we yield variants of Bayesian optimization that target local, rather than global, optima. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm. Our method is closely connected to other Bayesian optimal experimental design procedures such as entropy search methods and optimal sensor placement using Gaussian processes.