The preprint reports that GRAPE achieved an average 5.4-fold attack speedup over the baselines and reduced final average prompt regret by 3.8 log units compared with the second-best method.
The result is split across two tasks. In adversarial attacks, the endpoint was the number of queries needed to reach the first successful attack. In prompt optimization, it was final log simple regret, with lower values indicating a better final search result.
A search that follows the local gradient
GRAPE is a two-stage local Bayesian-optimization framework. It first sharpens the local gradient posterior, an estimate of how the objective is changing nearby, using a closed-form acquisition. It then chooses the direction with the largest expected decrease conditional on descent.
In the reported experiments, the refinement stage had a budget of five queries, followed by at most 30 exploitation steps. Direction search used 10 restarts plus a warm start. Prompt optimization ran for 200 iterations from five random prompts.
The underlying question was whether refinement queries reduce uncertainty at a fixed point, and whether progress-aware exploitation picks a productive direction as uncertainty fades.
Under the stated Gaussian-process framework, the first theoretical result says that informative refinement queries strictly reduce total uncertainty about the local gradient. An uninformative candidate is the exception.
The second result is asymptotic, meaning it describes a limit rather than a guarantee after a fixed number of queries. If overall posterior uncertainty tends to zero and the estimated gradient converges to a nonzero true gradient, the selected direction converges to normalized steepest descent.
What the benchmark tests found
The image benchmark used randomly selected MNIST and CIFAR-10 images in spaces with 784 and 1,024 dimensions, respectively.
In the attack runs, GRAPE averaged 216 queries on MNIST, with a standard deviation of 42, and 341 on CIFAR-10, with a standard deviation of 53. NeST-BO averaged 719 plus or minus 136 queries on MNIST and 1,123 plus or minus 197 on CIFAR-10. The results were reported over 10 independent runs.
Under a fixed budget of 2,000 queries, GRAPE also reached the highest attack success rate earliest on both datasets. Those curves used 50 randomly selected images per dataset.
The prompt test used a BoLT pool of 5,014 mathematical-reasoning prompts. Candidates were scored by MATH-500 accuracy under Qwen3-14B, while the search was run with 128, 256, 512 and 768 embedding dimensions retained.
On that benchmark, GRAPE reached the deep low-regret region below -10 sooner than NeST-BO and finished with the lowest regret at every tested embedding dimension. At 768 dimensions, its improvement over NeST-BO was roughly three additional log units.
The result comes with conditions
The paper reports means and standard deviations and assesses differences with paired, two-sided Wilcoxon signed-rank tests by run. P-values below 0.05 mark improvements.
The qualifications matter. The uncertainty result is conditional on the stated Gaussian-process framework, while the steepest-descent result requires vanishing posterior covariance trace and a posterior mean that converges to a nonzero true gradient.
GRAPE is a local optimizer, and the evidence here comes from the MNIST and CIFAR-10 attack settings plus one BoLT prompt pool tested at four embedding dimensions. The findings describe performance in those benchmark settings, not a guarantee of a global optimum or universal superiority across high-dimensional objectives.
The tests also do not show that adversarial query efficiency translates into improved real-world security or that prompt regret measures general language-model quality.
Paper data and sources
Original title: GRAPE: Gradient Refinement and Progress-Aware Exploitation for Query-Efficient High-Dimensional Bayesian Optimization
Authors: Richard Cornelius Suwandi, Feng Yin
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text