Generative Refinement for Low-Budget Black-Box Optimization
July 01, 2026
Abstract
Black-box optimization is a fundamental science and engineering tool that makes it possible to optimize objectives without gradient information. Unfortunately, as it often requires many function evaluations, it can be challenging when each one is costly. This is especially true when the evaluation function is noisy or failure-prone, and when high-performing solutions are confined to thin, curved, or disconnected regions of the search space. Existing methods leveraging generative models to navigate these subspaces are built to sample from reward-aligned distributions. As a result, they require a large number of evaluations to align their sampler effectively, making them impractical in low-budget settings. We propose SPARROW, an algorithm that completely decouples the generative prior from the reward signal. SPARROW can use any sampler with a known corruption process and trained on unevaluated data, as a fixed, structured proposal operator. Optimization proceeds by rank-based guidance over an archive of evaluated candidates. SPARROW can navigate complex geometries, handle unreliable reward signals, and perform effective optimization under very low evaluation budgets. We provide asymptotic convergence guarantees over the sampler support and demonstrate strong empirical performance on problems with unreliable rewards and geometrically complex landscapes.
1 Introduction↩︎
Many problems in science and engineering require optimizing without access to gradient information, as in materials design [1], drug discovery [2], [3], and engineering simulation [4], [5]. This is referred to as Black-Box Optimization (BBO). It is particularly challenging when evaluations are costly, limiting the evaluation budget to tens or hundreds of candidates rather than tens of thousands. The difficulty is magnified when the evaluation feedback is noisy or failure-prone and when good solutions lie on thin, curved or disconnected regions of the search space.
In these settings, classical approaches struggle. Bayesian optimization (BO) methods such as Gaussian processes (GP) [6] are efficient but suffer when the feedback is unreliable. Evolutionary strategies (ES) such as CMA-ES [7] are more robust but typically need more feedback to get going. All make distributional assumptions that degrade with dimensionality and complexity of the search space, leading them to waste evaluations on infeasible candidates and failing to account for the geometry of the problem.
Diffusion [8]–[10] and flow matching [11] models have recently emerged as powerful tools for representing complex, high-dimensional distributions. This has motivated their use in BBO for settings where domain data is available. Such data is however often unlabeled with respect to the chosen objective, providing structural information but no objective signal. Existing methods target a reward-weighted distribution [12]–[14], which requires either a labeled training dataset or a large number of evaluations during sampling to accurately shape the sampler. Thus, the distribution-learning paradigm is at odds with the practical objective of identifying the best single solution under a limited budget.
We propose SPARROW (Sequential Proposal via Archival Rank-based Refinement for Optimization under Weak feedback), a new BBO algorithm that decouples generative modeling from optimization. SPARROW uses a fixed, unconditional sampler as a proposal operator and requires only access to its corruption and sampling processes, regardless of internal structure. Optimization is driven by rank-based guidance over an archive of evaluated candidates, giving robustness to unreliable feedback. We provide asymptotic convergence guarantees over the sampler support and strong empirical performance on problems with low-measure feasible subspaces, disconnected high-performing regions, and unreliable feedback.
2 Related Work↩︎
We first review classical BBO methods designed to operate in relatively simple spaces. We then discuss more recent approaches that rely on generative models.
2.1 Classical Black-Box Optimization↩︎
Evolution strategies (ES) optimize black-box objectives through iterative mutation and selection over a population or archive of candidate solutions. Modern variants such as CMA-ES adapt a parametric search distribution to capture local geometry [7], while differential evolution [15] constructs mutation directions from archive pairs. A central principle across this line of work is rank-based selection, as formalized in information-geometric optimization [16] and natural evolution strategies [17], which provides invariance to monotone transformations of the objective and robustness to noise.
Bayesian optimization (BO) takes a different approach, building a surrogate of the objective and selecting candidates via an acquisition function [6]. Local variants such as TuRBO [18] restrict this search to local trust-regions, preventing the search distribution from diffusing across the full space.
All of these methods define a search distribution independently of the objective structure. When the high-performing regions are thin, curved or disconnected, they waste evaluations in bad regions, slowing or even stalling the optimization.
2.2 Generative Models for Black-Box Optimization↩︎
In recent years, generative modeling has emerged as a powerful alternative to the classical techniques described above, as they can handle more complex geometries. Most existing approaches however target reward-shifted distributions, incurring great evaluation cost.
2.2.0.1 Learning from Evaluations.
The dominant paradigm uses objective evaluations to train or adapt a generative model. Inverse approaches learn a mapping from high objective values to designs: CbAS [19] iteratively reweights and retrains a VAE; MINs [20] learn an explicit inverse mapping; DDOM [12] and Diffusion-BBO [13] train conditional diffusion models offline and online respectively; and BONET [21] models optimization trajectories with an autoregressive transformer. Forward approaches instead train a surrogate predictor and optimize it directly via gradient ascent [22]–[25]. Hybrid approaches combine the two: DEMO [26] applies gradient ascent on a surrogate, then uses a diffusion prior to project candidates back onto the data manifold; RGD [27] trains a classifier-free inverse diffusion model and injects a separately trained proxy at sampling time; and DiBO [28] iteratively retrains both a diffusion prior and an ensemble proxy to amortize posterior inference. In all cases, optimization quality depends on models fitted from evaluations, which become unreliable when the budget is small.
2.2.0.2 Fixed-Model Guidance.
Another approach keeps the generative model frozen and injects reward signals at inference time. Gradient-based methods optimize in noise space via backpropagation of estimated gradients through the sampling trajectory [29], which is prohibitively expensive in high dimensions and brittle when the objective function is unreliable. Derivative-free methods run Sequential Monte Carlo over the denoising trajectory to approximate a reward-aligned distribution [14], [30], requiring many reward evaluations per candidate regardless of dimensionality. Both families thus behave poorly in the low-budget regime.
2.2.0.3 Selection-Based Guidance.
Some methods combine a fixed generative model with a selection-based outer loop. That of [14] targets a reward-weighted distribution, requiring additional SMC-style trajectory guidance to do so, resulting in many reward evaluations per candidate. Diffusion-ES [31] relies on selection alone, but was developed as a trajectory planner for autonomous driving and evaluated exclusively on closed-loop driving benchmarks. It was never positioned as a general BBO method, assumes many cheap reward queries per round, and uses reward-value-based selection, making it brittle to noisy or failure-prone objectives.
3 Background↩︎
SPARROW relies on generative sampling, refinement by partial noising, and rank-based selection. We briefly review these techniques before discussing how we use them in the following section.
3.1 Generative Samplers and Noise Trajectories↩︎
We consider generative models that map noise to data through a trajectory. Let \(t \in [0,1]\) denote a noise level, with \(t=0\) being pure noise and \(t=1\) the data distribution, and let \(\mathcal{X}_t\) denote the space of states at noise level \(t\). We define \[S_{t \rightarrow 1} : \mathcal{X}_t \rightarrow \mathcal{X}\] the refinement operator that maps a partially noisy state to a sample in data space by following the generative trajectory. Sampling corresponds to applying \(S_{0 \rightarrow 1}\) to a draw from the noise prior.
3.2 Refinement via Partial Noising↩︎
Let \[\mathcal{N}_t : \mathcal{X} \rightarrow \mathcal{X}_t\] denote the corruption operator at noise level \(t\), which maps a candidate \(x \in \mathcal{X}\) to a noisy state \(x_t \sim \mathcal{N}_t(x)\) according to the forward process used during the training of the sampler. The composition of \(\mathcal{N}_t\) and \(S_{t\rightarrow 1}\) induces a family of stochastic transition kernels over the search space, indexed by a controllable corruption level: \[\mathcal{T}_t(x) := S_{t \rightarrow 1}(x_t), \quad \text{where } x_t \sim \mathcal{N}_t(x).\] This construction generalizes stochastic editing procedures such as SDEdit [32], where partial corruption followed by denoising biases inputs towards the sampler’s data distribution. Here, \(\mathcal{N}_t\) and \(S_{t \rightarrow 1}\) are defined abstractly. In practice, any generative sampler supporting a consistent corruption–refinement decomposition can be used, without access to its internal parametrization.
The noise level \(t\) controls the exploration scale: small \(t\) produces local refinements, large \(t\) induces global modifications. In particular, \(\mathcal{T}_0(x)\sim\nu\) for all \(x\in X\), since full corruption erases all input structure and produces samples from the prior.
3.3 Rank-based Optimization and Invariance↩︎
Rank-based optimization replaces raw objective values with their induced ordering, so that all decisions depend on \(\operatorname{rank}(x)\) rather than \(f(x)\). This yields invariance to strictly monotone transformations of the objective [7], [16], making the optimization signal robust to scaling, misspecification, and outcome-dependent noise. The tradeoff is that ranking discards magnitude information, making rank-based updates less efficient than value-based ones when reliable magnitude information is available. In our regime, however, this tradeoff is favorable: robustness and invariance outweigh efficiency when evaluations are scarce.
4 Method↩︎
SPARROW maintains a ranked archive of all previously evaluated candidates. At each iteration, it selects a parent, forms a rank-guided directional step from a random archive pair, corrupts the displaced parent to a noise level determined by its rank, and refines it back to the data manifold using a fixed pre-trained generative sampler.
4.1 Algorithmic Steps↩︎
Let \(f\) be a black-box maximization objective, \(\mathcal{T}_t\) a noise–refine operator as defined in section 3.2, and \(\mathcal{A}_k = \{(x_i, f(x_i))\}_{i=1}^{n_k}\) an archive of evaluated candidates, initialized by evaluating \(n_0\) samples from an available dataset, or drawn from the sampler. Additional samples are added one by one by going through the following steps, which are summarized by Algorithm 2 and illustrated in Figure 1:
Ranking of the archive: All subsequent operations are based on the normalized rank \[r_k(x_i) = \frac{\operatorname{rank}_{\mathcal{A}_k}(x_i)}{n_k}, \label{eq:nrank}\tag{1}\] where \(\operatorname{rank}_{\mathcal{A}_k}(x_i) \in \{1,\dots,n_k\}\) assigns rank \(1\) to the best candidate.
Parent selection: A parent is selected from the archive with probability \[x_k\sim p_{\mathrm{par}}(\cdot \mid \mathcal{A}_k)\propto\exp(-\beta\, r_k(\cdot)),\] where \(\beta > 0\) controls selection pressure.
Corruption level computation: A parent-specific corruption level is computed \[t_k = 1 - r_k(x_k)^\gamma,\quad \gamma > 0,\] where \(x_k\) is the selected parent and \(\gamma\) controls the exploration–exploitation tradeoff.
Rank-guided directional step: Two candidates \(x_a, x_b\) are drawn uniformly from \(\mathcal{A}_k\). Their difference, sign-corrected so that it points from the worse toward the better candidate, defines a mutation direction. The parent is displaced along this direction before corruption: \[x_{\mathrm{guided}} = x_k + \lambda\,(1-t_k)\operatorname{sign}(r_k(x_b)-r_k(x_a))(x_a - x_b),\] where \(\lambda > 0\) is a step-size parameter.
Noise–refine mutation: The proposal operator \(\mathcal{T}_t\), as defined in section 3.2, noises the parent \(x_{\mathrm{guided}}\) to noise level \(t_k\), and then runs the generative sampler from \(t_k\) back to \(1\) to produce a child \[x'_{k+1} \sim \mathcal{T}_{t_k}(x_{\mathrm{guided}}),\] which is then added to the archive.
These steps embody several design choices:
All selection and corruption steps only depend on ranks, making SPARROW robust to noisy and unreliable feedback. The sampler enters only as a structural prior; no objective evaluations are used to update it and optimization is done only by the rank-based guidance.
We retain the full archive of evaluated candidates. This avoids permanently discarding potentially promising regions based on potentially noisy evaluations. Discarding evaluations is wasteful when the evaluation budget is limited, and a growing archive yields progressively finer-grained rank estimates. Full archive retention is computationally feasible, since the dominant cost is objective evaluation.
The selection process samples a maximum-entropy distribution under an expected-rank constraint [33], as shown in Appendix 8. This is standard in rank-based selection schemes and assigns a non-zero selection probability to all elements of the archive. High-ranking candidates are noised less than lower-ranking ones, which favors exploitation of the former and exploration around the latter, analogous to adaptive step-size control in evolution strategies [7]. Ensuring that \(t_k(x) \in [0,1)\) for all archive members also prevents degenerate identity proposals for the best candidates and induces full prior resampling for the worst.
The mutation direction, built from random archive pairs, maintains directional diversity without requiring explicit gradient information, as proposed by differential evolution [15]. The factor \((1-t_k)\) couples the step magnitude to the corruption level: high-ranked parents yield fine-grained local refinement, while low-ranked parents yield broader exploration.
\(\beta\), \(\gamma\) and \(\lambda\) are fixed throughout optimization. This avoids fitting a high-variance exploration policy from sparse, dependent feedback, while still providing a structured exploration–exploitation tradeoff. In Section 5.5, we find that the sensitivity to these parameters is moderate.
The archive is initialized with \(n_0=4+\lfloor3\ln{D}\rfloor\) samples, following the CMA-ES population-size convention [7]. They are taken from available datasets when possible, or drawn from the sampler when necessary.
4.2 Asymptotic Convergence to the Global Optimum↩︎
Let \(\nu\) be the distribution induced by the sampler as defined in Section 3.2 and let \(S\) be the support of \(\nu\). Since \(\mathcal{T}_0(x) \sim \nu\) , if \(f\) can be evaluated without noise, we show in Appendix 9 that \[\max_{0\le j\le k} f(x_j)\xrightarrow[k\to\infty]{a.s.}\sup_{x\in\operatorname{supp}(\nu)} f(x) \; ,\] meaning that the best sample observed at iteration \(k\) converges almost surely to the global optimum over \(S\) when \(k\) goes to infinity.
This result being asymptotic and restricted to the sampler support, it does not by itself characterize finite-budget performance or settings with noisy evaluations. Finite-budget performance and performance under noise are evaluated empirically in Section 5.
5 Experiments↩︎
We evaluate SPARROW on three tasks of increasing complexity and realism. First, a synthetic objective where good solutions lie on a \(D\)-dimensional thin tube, isolating the importance of structured priors and enabling controlled ablation of the geometric difficulty. Second, the Hopper controller task from Design-Bench [34], a 5126-dimensional problem with highly disconnected high-performing regions. Third, airfoil aerodynamic optimization, a problem of direct industrial relevance where the objective is non-smooth and evaluations frequently fail.
For completeness, we provide additional results and discussion on the other Design-Bench tasks in Appendix 12. We identify structural biases in these tasks that make fair comparisons difficult, and note that their smoother, well-behaved geometries make them less suited to our setting.
5.1 Baselines↩︎
We compare SPARROW against four baselines that represent the current state-of-the-art in Black Box Optimization. CMA-ES [7] is the standard evolution strategy, maintaining an adaptive Gaussian search distribution in ambient space. GP is a Gaussian process surrogate with expected improvement acquisition and dimension-scaled length-scale priors [35], a strong standard BO baseline. TuRBO [18] augments GP with local trust regions, often more adapted as dimensionality scales. RDS (Random Diffusion Sampling) draws proposals unconditionally from the generative prior without selection or archive, which separates the contribution of rank-based guidance from the structural contribution of the prior alone.
We exclude methods that retrain a conditional generative model or fit a surrogate model from objective evaluations, as they require a large number of evaluations to fit a meaningful model, far exceeding our total budget of \(B=100\). We similarly exclude inference-time guidance methods that inject reward signals into the denoising trajectory, as single candidate usually already consumes the entire budget \(B=100\). In all these cases, the cost of shaping or approximating a reward-aligned distribution is structurally incompatible with the low-budget regime, which is precisely the gap SPARROW is designed to fill.
We ran all methods 10 times from different seeds and report median and IQR of the best objective value as a function of evaluations consumed. More implementation details are given in Appendix 13.
| 64D Tube | Airfoil \(C_l/C_d\) | HopperController | ||
|---|---|---|---|---|
| 2-3 (lr)4-4 (lr)5-5 Method | \(B=100\) | \(B=1000\) | \(B=100\) | \(B=100\) |
| CMA-ES | \(0.00_{[0.00,\, 0.00]}\) | \(0.00_{[0.00,\, 0.00]}\) | \(152.65_{[146.67,\, 155.57]}\) | \(0.00_{[0.00,\, 0.00]}\) |
| GP | \(0.07_{[0.06,\, 0.09]}\) | \(0.07_{[0.06,\, 0.09]}\) | \(158.85_{[139.20,\, 175.94]}\) | \(0.77_{[0.67,\, 0.91]}\) |
| TuRBO | \(0.07_{[0.06,\, 0.09]}\) | \(0.11_{[0.09,\, 0.14]}\) | \(130.21_{[122.88,\, 138.61]}\) | \(0.73_{[0.62,\, 0.83]}\) |
| RDS | \(0.16_{[0.14,\, 0.17]}\) | \(0.20_{[0.19,\, 0.20]}\) | \(142.10_{[127.46,\,156.78]}\) | \(0.92_{[0.85,\, 1.02]}\) |
| (ours) | \(\mathbf{0.30}_{[0.27,\, 0.32]}\) | \(\mathbf{0.36}_{[0.33,\, 0.40]}\) | \(\mathbf{180.46}_{[179.13,\, 181.54]}\) | \(\mathbf{1.32}_{[1.02,\, 1.56]}\) |
5.2 Thin High-Dimensional Tube↩︎
We define a synthetic benchmark in which optimal solutions lie near the end of a thin, curved, one-dimensional manifold embedded in a high-dimensional ambient space. Figure 1 illustrates the geometry. While synthetic, this setting shows the core challenge SPARROW is designed for: most of the search space yields poor or invalid solutions, and progress requires staying near a structured feasible region.
5.2.0.1 Experimental Setup.
The benchmark consists of a smooth curved tube of radius \(r=0.1\) with a start and finish. The objective rewards points near the finish, but only within the tube. Points outside the tube score worse than points near the start. We report main results at \(D=64\), and vary \(D \in \{8,16,32,64,128\}\) for the ablation. The sampler is trained on points sampled along the tube with a \(\mathrm{Beta}(1,3)\) distribution over arc-length, concentrating mass near the start and away from the optimum. This reflects a realistic scenario where structured data is abundant, but sparse near the optimum. Full formalism and implementation are given in Appendix 10.
5.2.0.2 Results.
Fig. 3 (left) and Tab. 1 show reward values as a function of consumed evaluation budget.
Ambient-space methods fail entirely. CMA-ES scores zero on every run: its Gaussian search distribution cannot concentrate on a tube that occupies an exponentially small volume fraction of ambient space. GP stagnates for the same reason: its surrogate is poorly calibrated when nearly all evaluated points fall outside the feasible region. TuRBO partially recovers after \(B=400\) as its trust regions contract toward the tube, but remains far below diffusion-based methods even at \(B=1000\).
Rank-based guidance adds value beyond the prior, increasingly so as dimension grows. RDS makes consistent progress, confirming that the generative prior encodes useful geometric structure. SPARROW substantially outperforms RDS at all budgets. Fig. 4 shows that both RDS and SPARROW degrade as \(D\) increases (the tube occupies a smaller fraction of ambient space) but the gap between them widens with dimension. This confirms that rank-based guidance becomes increasingly valuable precisely when the geometry is most challenging.
5.3 HopperController↩︎
HopperController is a \(D=5126\) continuous control task, in which the search space is the parameter space of a neural network policy. The objective is a combination of the hopper’s velocity, control cost, and a bonus for staying upright.
5.3.0.1 Experimental Setup.
We train an unconditional flow matching model on the HopperController training set and initialize all methods from the generative prior. Training points are excluded from initialization because the dataset contains a small number of near-optimal solutions that prevent any method from improving upon the initial archive. The objective is evaluated via the Gaussian process oracle provided by Design-Bench.
5.3.0.2 Results.
Fig. 3 (right) and Tab. 1 show results at \(B=100\). CMA-ES collapses entirely, exactly as in the tube experiment. Its Gaussian search distribution cannot operate in a \(5126\)-dimensional space with a structured feasible region. GP and TuRBO plateau near the initialization quality, their surrogates too poorly calibrated at this dimensionality to identify improvement directions. RDS makes modest progress, confirming that the generative prior encodes useful structure. SPARROW substantially outperforms all baselines, with the gap widening through the budget.
5.4 Airfoil Aerodynamic Optimization↩︎
We evaluate SPARROW on a real-world aerodynamic design task, maximizing the lift-to-drag ratio \(C_l/C_d\) of a two-dimensional airfoil computed by XFOIL [36], a widely used panel-method solver. Aerodynamic objectives are notoriously difficult due to turbulence, flow separation, and operation outside the solver’s validity range, causing frequent solver failures. We treat such failures as consumed evaluations: They count against the evaluation budget but are not added to the archive.
5.4.0.1 Experimental Setup.
We use the generative prior of DiffAirfoil [37], a diffusion model coupled to an auto-decoder that maps a 256-dimensional latent code to airfoil coordinates. We train it on the UIUC airfoil database [38] and generated NACA profiles, providing a prior over geometrically valid airfoils without aerodynamic supervision. SPARROW operates entirely in this latent space, using DiffAirfoil’s forward and reverse processes as the mutation operator \(\mathcal{T}_t\). All baselines likewise operate in the latent space; the auto-decoder is used only for decoding before evaluation by XFOIL. More details about the implemented pipeline and its latent space are given in Appendix 11.
5.4.0.2 Results.
Fig. 3 (middle) and Tab. 1 show results at \(B=100\). GP converges quickly but plateaus well below SPARROW, and CMA-ES improves only slowly. Their Gaussian search distributions are struggling to avoid the large latent regions that decode to aerodynamically poor shapes or trigger solver failures. TuRBO performs worst, likely because its trust-region decomposition assumes dense, reliable feedback, which is directly violated by XFOIL’s irregular failures.
SPARROW achieves the highest median \(C_l/C_d\) at \(B=100\) by a significant margin, and does so with a notably tight interquartile range compared to all baselines. This highlights the consistency under noisy, failure-prone evaluations that rank-based guidance can bring. The fixed generative prior steers proposals toward geometrically valid shapes, reducing the failure rate relative to ambient-space search. Together, these two properties make SPARROW well suited to the practical realities of simulation-based design.
5.5 Hyperparameter Sensitivity↩︎
Fig. 5 shows performance at \(B=100\) as each hyperparameter is varied independently around the default values \(\beta=50\), \(\gamma=1\), \(\lambda=0.1\) on the 64D tube. At low \(\beta\), parent selection becomes nearly uniform and rank information ceases to guide the search; at high \(\beta\), excessive elitism causes stagnation. At \(\gamma=0\), \(t_k = 0\) for all candidates regardless of rank, collapsing to RDS; at high \(\gamma\), top-ranked candidates receive near-zero corruption, producing near-identity proposals and stagnating around current elites. At low \(\lambda\), directional guidance vanishes; at high \(\lambda\), guided candidates land far from known good regions before refinement. In all cases SPARROW performs well across a broad intermediate range, though \(\gamma\) is the most sensitive parameter and benefits from more careful selection. For the following tasks, parameters were derived from these qualitative insights rather than exhaustive search.
For HopperController, the latent space contains disconnected feasible regions, making this the hardest structural setting among our tasks. Very low \(\beta=5\) encourages broad exploration across disconnected components rather than over-exploiting a single region. Very low \(\gamma=0.1\) delegates most structural burden to the generative prior, whose corruption–refinement operators can bridge disconnected regions in ways that rank signals alone cannot. \(\lambda=0.1\) was set by qualitative transfer from the tube experiment.
For the airfoil experiment, lower \(\beta=10\) reflects the importance of diversity in a multimodal aerodynamic landscape. Lower \(\gamma=0.5\) reduces reliance on rank signals corrupted by solver failures, delegating more feasibility burden to the generative prior. Larger \(\lambda = 2\) accounts for the greater characteristic distances in the DiffAirfoil latent space.
Across all three domains, hyperparameters were derived from qualitative reasoning rather than exhaustive search, confirming that the sensitivity analysis provides actionable guidance for new settings.
6 Limitations↩︎
SPARROW is designed for low-budget optimization on complex geometric landscapes with unreliable feedback. With simple rewards, reliable feedback, or high evaluation budgets, we expect more established methods to be more effective.
SPARROW’s performance is bounded by the sampler quality: Solutions outside the generative prior’s support are unreachable. In practice, this means SPARROW inherits any biases of the prior.
The convergence guarantee is asymptotic and restricted to noiseless evaluations over the sampler support; it provides no finite-budget characterization and does not extend to settings with corrupted or missing feedback, where robustness is instead supported empirically.
The three hyper-parameters \(\beta\), \(\gamma\), \(\lambda\) require domain-specific initialization. Section 5.5 provides a sensitivity analysis that we found sufficient to transfer across our three domains, but more principled adaptation strategies or less sensitive evolutions of SPARROW remain future work.
7 Conclusion↩︎
We introduced SPARROW, a black-box optimization method for the low-budget regime that decouples generative modeling from objective evaluation. By treating a fixed, unconditional generative sampler as a structured proposal operator and optimizing through rank-based guidance over a growing archive, SPARROW avoids the evaluation cost of reward-aligned distribution learning. The approach requires only access to the sampler’s corruption and refinement operators, is robust to noisy and failing objectives through rank-based invariance, and comes with asymptotic convergence guarantees over the sampler support.
On the 64D thin tube, ambient-space methods fail entirely while SPARROW substantially outperforms all baselines across budgets and dimensions, with the gap over random diffusion sampling widening as geometry grows more complex. On HopperController, the same pattern replicates on a standard benchmark. On the airfoil task, SPARROW achieves the highest median \(C_l/C_d\) with notably low variance under noisy, failure-prone simulation, reflecting realistic engineering design constraints.
These results establish SPARROW as a practical optimization algorithm for geometrically complex, low-budget optimization, an important class of problems that previously had no good solution.
8 Maximum-entropy derivation of rank-based parent selection↩︎
We show that the exponential rank-based selection rule \[p_i = \frac{\exp(-\beta r_i)}{\sum_j \exp(-\beta r_j)}\] arises as the maximum-entropy distribution over archive elements under a constraint on expected rank.
Let \(r_i \in [0,1]\) denote the normalized rank of candidate \(x_i\). We seek a distribution \(p=(p_1,\dots,p_n)\) that maximizes entropy \[H(p) = -\sum_i p_i \log p_i\] subject to \[\sum_i p_i = 1,\qquad\sum_i p_i r_i = \rho.\]
The Lagrangian is \[\mathcal{L}(p,\lambda,\beta)=-\sum_i p_i \log p_i+ \lambda\!\left(\sum_i p_i - 1\right)- \beta\!\left(\sum_i p_i r_i - \rho\right).\]
Setting \(\partial \mathcal{L}/\partial p_i = 0\) gives \[\log p_i = \lambda - 1 - \beta r_i,\] hence \[p_i \propto \exp(-\beta r_i).\]
The parameter \(\beta\) controls the expected rank: \(\beta=0\) yields uniform selection, while larger \(\beta\) increases preference for better-ranked candidates.
9 Asymptotic Convergence to the Global Optimum↩︎
We prove that SPARROW converges almost surely to the global optimum over the support of the unconditional sampler. The proof follows the classical framework of [39]. The key point is that SPARROW naturally satisfies its conditions: the exponential selection rule assigns positive probability to the worst-ranked candidate at every iteration, which produces an unconditional sample from \(\nu\), thereby ensuring persistent exploration of the sampler support without requiring explicit random restarts.
Let \(\nu\) denote the sampler’s resulting distribution and assume that full corruption produces an unconditional sample, i.e., \[\mathcal{T}_0(x) \sim \nu \quad \text{for all } x \in X.\] Let \(S = \operatorname{supp}(\nu)\), assume evaluations are noiseless, and let \(M = \sup_{x \in S} f(x)\). Assume that the supremum is approachable under \(\nu\), i.e., for all \(\delta > 0\), \[\nu\!\left(\{x \in S : f(x) > M - \delta\}\right) > 0.\]
Proposition 1. Under the above assumptions, \[\max_{0 \le j \le k} f(x_j)\xrightarrow[k\to\infty]{a.s.}M.\]
Proof. At iteration \(k\), the worst-ranked element has normalized rank \(r_k = 1\), hence \(t_k = 1 - 1^\gamma = 0\), and sampling from this parent yields a draw from \(\nu\). The probability of selecting the worst-ranked element is \[p_k^{\mathrm{worst}} = \frac{e^{-\beta}}{\sum_{i=1}^{n_k} e^{-\beta r_k(x_i)}} \ge \frac{e^{-\beta}}{n_k}.\] Thus, for any measurable set \(A \subseteq S\), \[\mathbb{P}(x_{k+1} \in A \mid \mathcal{A}_k) \ge \frac{e^{-\beta}}{n_k}\,\nu(A).\] Since \(n_k = n_0 + k\), we have \(\sum_{k=0}^\infty n_k^{-1} = \infty\), so any set \(A\) with \(\nu(A) > 0\) is visited infinitely often almost surely.
For any \(\delta > 0\), let \(A_\delta = \{x \in S : f(x) > M - \delta\}\). By assumption, \(\nu(A_\delta) > 0\), so proposals enter \(A_\delta\) infinitely often almost surely, implying \[\liminf_{k\to\infty} \max_{0 \le j \le k} f(x_j) \ge M - \delta.\] Since \(\delta > 0\) is arbitrary and \(\max_{j \le k} f(x_j) \le M\) for all \(k\), the result follows. ◻
10 Thin, High-Dimensional Tube↩︎
For ambient dimension \(D\), let \(c:[0,1]\to\mathbb{R}^D\) be a smooth centerline curve defined by: \[c_{2j-1}(s) = a_j \sin(2\pi j s + \phi_j), \qquad c_{2j}(s) = a_j \cos(2\pi j s + \phi_j), \qquad j=1,\dots,\lfloor D/2 \rfloor,\] where \(a_j = 1/j\) and phases \(\phi_j \sim \mathrm{Uniform}[0,2\pi]\) are sampled once and fixed across all methods and runs. Let \[d(x,\mathcal{C}) = \min_{s\in[0,1]} \|x-c(s)\|_2, \qquad s^\star(x) \in \arg\min_{s\in[0,1]} \|x-c(s)\|_2.\] The objective rewards both proximity to the tube and progress along it: \[f(x) = s^\star(x)\!\left(1 - \frac{d(x,\mathcal{C})}{r}\right),\] which is positive only inside the tube \(d(x,\mathcal{C}) \leq r\), increases toward the endpoint \(c(1)\), and penalizes deviation from the centerline continuously. Out-of-tube evaluations return a negative value; we clip reported rewards at zero.
To train the sampler, we sample \(D*1000\) arc lengths \(s \sim \mathrm{Beta}(1,3)\), place points near \(c(s)\) with isotropic Gaussian noise, and retain only samples inside the tube. The \(\mathrm{Beta}(1,3)\) distribution concentrates mass near \(s=0\). The prior captures the tube geometry without carrying any information about the objective direction.
11 DiffAirfoil↩︎
11.1 Architecture↩︎
DiffAirfoil [37] parameterizes airfoil geometry through an autodecoder originally introduced in [40]. Each airfoil is represented by a latent vector \(z \in \mathbb{R}^{256}\) and the autodecoder \(\mathcal{D}_\phi\) maps \(z\) to a set of surface coordinates by learning a deformation field applied to a fixed template airfoil profile. Geometrically valid airfoils therefore correspond to a continuous deformation of the template, which enforces smoothness and prevents degenerate geometries by construction.
The diffusion model originally proposed in [37] operates entirely in this latent space. In our implementation, we replace the diffusion sampler with a flow matching model (Appendix 13), trained on the same latent codes. This substitution is inconsequential for SPARROW: the method requires only access to corruption and refinement operators \(\mathcal{N}_t\) and \(\mathcal{S}_{t \to 1}\), which flow matching provides directly. The autodecoder \(\mathcal{D}_\phi\) is used solely for decoding proposals to airfoil coordinates before XFOIL evaluation, and is never updated.
11.2 Training Data↩︎
The autodecoder and generative prior are trained on the UIUC airfoil database [38], supplemented with generated NACA profiles, yielding \(N = 2{,}648\) geometrically valid airfoils (Table 3). No aerodynamic labels are used at any stage: the prior is purely geometric, encoding the distribution of plausible airfoil shapes without any information about lift, drag, or the objective direction.
11.3 Latent Space Structure↩︎
The 256-dimensional latent space exhibits two key properties.
11.3.0.1 Geometric structure without aerodynamic alignment.
Figure 6 shows a UMAP projection of the training latent codes, colored by \(C_l/C_d\) evaluated by XFOIL. The distribution of Cl/Cd values is spatially structured: a compact region of the latent space concentrates high-performing airfoils, while the training data mass occupies a broader, aerodynamically mediocre region. The prior therefore encodes geometric validity across the full training distribution, but is not aligned with the aerodynamic objective.
11.3.0.2 Uniform, objective-independent solver failures.
XFOIL is a panel-method solver whose convergence depends on flow conditions and airfoil geometry: turbulence, flow separation, and operation outside the solver’s validity range cause frequent, unpredictable failures. Figure 6 shows the \(C_l/C_d\) landscape exhibits a smooth objective gradient, while failures appear irregularly throughout the space. Crucially, solver failures are not concentrated near the optimum and do not reflect proximity to a geometric boundary, but constitute pure evaluation noise distributed across the latent space.
Together, these properties define the challenge: the generative prior concentrates away from the optimum, and a significant number of evaluations are wasted regardless of where the search focuses. SPARROW addresses both simultaneously. Rank-based guidance steers proposals toward better-ranked regions. Rank-based invariance makes the optimization signal robust to missing feedback, so that failed evaluations do not corrupt the search. Critically, the generative prior itself reduces the baseline failure rate by orienting the search towards neighborhoods of known valid airfoils. Classical methods operating directly in latent space more easily sample regions that exceed XFOIL’s convergence domain.
12 Design-Bench↩︎
| AntMorphology | DKittyMorphology | SuperConductor | ||
|---|---|---|---|---|
| 2-2 (lr)3-3 (lr)4-4 Method | \(B=100\) | \(B=100\) | \(B=100\) | |
| CMA-ES | \(2.67_{[2.55,\, 3.50]}\) | \(\mathbf{2.30}_{[1.71,\, 2.64]}\) | \(0.71_{[0.68,\, 0.75]}\) | |
| GP | \(\mathbf{6.96}_{[6.63,\, 7.01]}\) | \(2.09_{[1.77,\, 2.54]}\) | \(\mathbf{3.03}_{[2.77,\, 3.64]}\) | |
| TuRBO | \(5.19_{[5.15,\, 5.43]}\) | \(1.28_{[1.20,\, 1.42]}\) | \(2.70_{[2.37,\, 2.74]}\) | |
| RDS | \(4.02_{[3.93,\, 4.27]}\) | \(1.18_{[1.15,\, 1.23]}\) | \(2.11_{[1.89,\, 2.33]}\) | |
| (ours) | \(5.01_{[4.38,\, 5.32]}\) | \(1.40_{[1.28,\, 1.47]}\) | \(2.98_{[2.77,\, 3.47]}\) |
Design-Bench [34] is a standard offline BBO benchmark: For each task, methods receive a fixed dataset of evaluated candidates and a surrogate oracle, a proxy trained on that dataset, to score proposals. We use it in an online fashion, querying the oracle sequentially as optimizations generate candidates. As noted in [34], three of these tasks incorporate a key bias. The AntMorphology, DKittyMorphology, and HopperController datasets were collected using CMA-ES. This biases the results in two ways: First, the oracle is trained on CMA-ES trajectories, which densely cover regions reachable by ambient-space perturbations and are sparse elsewhere, rewarding ambient-space methods independently of solution quality. Second, our sampler is trained on the biased dataset, biasing its support towards CMA-ES friendly regions, reducing SPARROW’s structural advantage. This bias is severe at moderate dimensionality but negligible at \(D=5126\), where CMA-ES itself collapses and its trajectories offer no meaningful coverage advantage. Superconductor uses real experimental data [41] and is free of collection bias. However, its oracle retains a smoothness bias, with a comparatively low dimensionality \(D=86\).
Results on AntMorphology, DKittyMorphology, and Superconductor, shown in Figure 7 and Table 2 reflect two compounding effects: the tasks’ smoothness and relatively low complexity, combined with the benchmark bias, favor GP over SPARROW. Disentangling the two effects is difficult, but both make the tasks fall outside the regime SPARROW is built to solve. On HopperController in Section 5.3 and the airfoil task in Section 5.4, where the geometry is complex and the feedback is unreliable, SPARROW clearly outperforms competing approaches.
13 Experimental Implementation↩︎
13.1 Generative Model Architecture↩︎
![Figure 8: Flow matching model architecture, shared across all experiments. The ambient dimension d varies per task (See Appendix 13.3). The noise level t is encoded by a 64-dimensional sinusoidal embedding \tau(t) and injected into each residual block by concatenation with the hidden state. Each block applies LayerNorm, two linear layers with SiLU activation, and a residual connection. The network maps (z,t)\in\mathbb{R}^d\times[0,1] to a velocity v_\theta(z,t)\in\mathbb{R}^d.](/article/2607.00691/_pdflatex/xogiskra.png "fig:")
All generative priors share a common architecture (Figure 8): a four-block residual network with sinusoidal time conditioning, trained with a flow matching objective. The hidden dimension equals the ambient dimension \(d\) in all experiments.
13.2 Flow Matching Training↩︎
All models are trained with a linear interpolation bridge using the procedure described in Algorithm 9. Noise samples are drawn from \(\mathcal{N}(\mu_\mathcal{D}, \sigma_\mathcal{D}^2 I)\), fitted from the training dataset, and are reordered via minibatch optimal transport (Hungarian algorithm on pairwise squared \(\ell_2\) cost) to reduce training variance without altering marginal distributions. Time is sampled from \(\mathrm{Beta}(0.5, 0.5)\), which upweights the endpoints of the trajectory.
All models are trained for 100’001 steps with Adam (lr \(= 10^{-4}\)), cosine annealing with warm restarts (\(T_0 = 10'000\), \(T_\mathrm{mult} = 2\), \(\eta_\mathrm{min} = 10^{-7}\)), and mixed-precision training. Batch size is \(512\).
At sampling time, initial noise is drawn from \(\mathcal{N}(\mu_\mathcal{D}, \sigma_\mathcal{D}^2 I)\), consistent with training. Integration uses RK4 with \(\max(5,\lfloor(1 - t_\mathrm{start}) \times 100\rfloor)\) steps.
13.3 Training Datasets↩︎
| Task | Source | \(D\) | \(N\) |
|---|---|---|---|
| Thin tube | Synthetic | \(D\) | \(1'000 \times D\) |
| Airfoil | UIUC database + NACA profiles | \(256\) | \(2'648\) |
| AntMorphology | Design-Bench | \(60\) | \(10'004\) |
| DKittyMorphology | Design-Bench | \(56\) | \(10'004\) |
| HopperController | Design-Bench | \(5126\) | \(3'200\) |
| Superconductor | Design-Bench | \(86\) | \(17'014\) |
Dataset sizes for each task are given in Table 3. The thin tube prior is explained in Section 5.2 and Appendix 10. The airfoil prior is described in Appendix 11. All Design-Bench priors are trained directly on the provided training sets.
13.4 Baseline Implementations↩︎
13.4.0.1 CMA-ES.
We use the pycma [42] library with default parameters. \(x_0\) is initialized with a random training data point. \(\sigma_0\) is initialized at \(0.5\times \sigma_{\mathcal{D}}\).
13.4.0.2 GP.
We use the BoTorch [43] implementation of vanilla Bayesian optimisation with a Matérn-5/2 kernel and Expected Improvement acquisition, following [35] with their dimension-scaled length-scale priors. The GP is fit on an archive capped at \(K = 200\) points (80% top-ranked, 20% random) to control fitting cost.
13.4.0.3 TuRBO.
We implement TuRBO following the official BoTorch tutorial, with default parameters and the same archive cap of \(K=200\) points (80% top-ranked, 20% random).
In all methods, failed evaluations (e.g.solver crashes in the airfoil task) are excluded from the archives/populations but counted against the budget \(B\).
13.5 XFOIL evaluation settings.↩︎
All aerodynamic evaluations use XFOIL [36] at a fixed angle of attack \(\alpha = 0^\circ\) and Reynolds number \(Re = 10^6\), applied during both the latent space analysis of Appendix 11 and the optimization experiments of Section 5.4.
13.6 Compute↩︎
All experiments were run on a single consumer GPU (NVIDIA RTX 4060, 8GB). Generative model training took at most a few hours per task. Each optimization run completed in minutes. Consistent with our low-budget framing, we consider generative model inference as negligible relative to the cost of objective evaluation: the dominant expense in all experiments is querying \(f\), not running the sampler.
13.7 Licenses↩︎
Design-Bench [34] and BoTorch [43] are MIT licensed. pycma [42] is BSD licensed. XFOIL [36] is distributed under the GNU GPL. The airfoil coordinates of the UIUC Airfoil Database [38] are publicly available with no stated license. All are used in accordance with their respective licenses.