# GRAPE: Gradient Refinement and Progress-Aware Exploitation for Query-Efficient High-Dimensional Bayesian Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 48 references that are in the map.
- First posted on arXiv 25 Aug 2026.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Matryoshka Representation Learning](https://mlsanity.com/paper/2205.13147/) (2022)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search](https://mlsanity.com/paper/1910.11858/) (2019)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [EmbeddingGemma: Powerful and Lightweight Text Representations](https://mlsanity.com/paper/2509.20354/) (2025)
- [Vanilla Bayesian Optimization Performs Great in High Dimensions](https://mlsanity.com/paper/2402.02229/) (2024)
- [Safe Controller Optimization for Quadrotors with Gaussian Processes](https://mlsanity.com/paper/1509.01066/) (2015)
- [HPO-B: A Large-Scale Reproducible Benchmark for Black-Box HPO based on OpenML](https://mlsanity.com/paper/2106.06257/) (2021)
- [Local policy search with Bayesian optimization](https://mlsanity.com/paper/2106.11899/) (2021)
- [Standard Gaussian Process is All You Need for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2402.02746/) (2024)
- [Local Bayesian optimization via maximizing probability of descent](https://mlsanity.com/paper/2210.11662/) (2022)
- [TREGO: a Trust-Region Framework for Efficient Global Optimization](https://mlsanity.com/paper/2101.06808/) (2021)
- [On the Convergence of Prior-Guided Zeroth-Order Optimization Algorithms](https://mlsanity.com/paper/2107.10110/) (2021)
- [Optimization, fast and slow: optimally switching between local and Bayesian optimization](https://mlsanity.com/paper/1805.08610/) (2018)
- [The Behavior and Convergence of Local Bayesian Optimization](https://mlsanity.com/paper/2305.15572/) (2023)
- [Understanding High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2502.09198/) (2025)
- [Adaptive Kernel Design for Bayesian Optimization Is a Piece of CAKE with LLMs](https://mlsanity.com/paper/2509.17998/) (2025)
- [We Still Don't Understand High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2512.00170/) (2025)
- [Minimizing UCB: a Better Local Search Strategy in Local Bayesian Optimization](https://mlsanity.com/paper/2405.15285/) (2024)
- [NeST-BO: Fast Local Bayesian Optimization via Newton-Step Targeting of Gradient and Hessian Information](https://mlsanity.com/paper/2510.05516/) (2025)
- [BoLT: A Benchmark to Democratize Black-box Optimization Research for Expensive LLM Tasks](https://mlsanity.com/paper/2605.17000/) (2026)

## Abstract (arXiv)

Optimizing expensive, high-dimensional black-box functions remains a central challenge in modern machine learning and scientific discovery. While local Bayesian optimization mitigates the curse of dimensionality, existing techniques often prioritize the probability of descent over the magnitude of progress. This leads to overly conservative steps that yield negligible improvement, wasting queries on directions that are nearly certain to descend but offer little decrease. We introduce Gradient Refinement and Progress-Aware Exploitation (GRAPE), a two-stage framework that first sharpens the local gradient posterior via a closed-form acquisition function, then selects update directions by maximizing the expected decrease conditional on descent. Theoretical analysis proves that this gradient refinement stage monotonically minimizes local uncertainty and that the progress-aware direction converges to true steepest descent as the posterior sharpens. Empirically, GRAPE demonstrates superior query efficiency across high-dimensional tasks: in black-box adversarial attacks, it achieves an average 5.4× speedup over baselines, and on large language model prompt optimization tasks, it outperforms the second best method by a reduction of 3.8 log-units in the final average regret.