acceptodds
Under review as a conference paper at ICLR 2027

Generative Refinement for Low-Budget Black Box Optimization

Abstract

Black-box optimization is a fundamental tool in science and engineering for optimizing objectives when gradient information is unavailable. It becomes especially difficult when the objective function is expensive to evaluate, limiting the evaluation budget to a few tens or hundreds of queries, and when good solutions occupy complex, low-measure regions of the search space. Generative models can supply useful structural priors in such settings, but existing generative BBO approaches bring significant evaluation cost. We identify three design principles for generative optimization under such low-budget conditions: avoid objective learning, optimize in candidate space, and make every evaluation count. Together, these principles motivate separating structural modeling from objective-driven search. We instantiate them in SPARROW, a simple sequential optimizer that maintains a persistent, ranked archive of evaluated candidates and uses a fixed, unconditional generative sampler solely as a corruption–refinement operator. SPARROW requires only access to the sampler's corruption and refinement processes, and never needs to evaluate the objective to train or guide it. Across three complementary settings, probing thin feasible geometry, disconnected high-performing regions, and failure-prone evaluations, SPARROW outperforms classical and generative baselines under strict evaluation budgets. These results demonstrate that separating structural priors from objective-driven search can be effective when evaluations are scarce and the search geometry is challenging.

Primary area:
optimization
Keywords:
Black-box optimization, Generative models, Low-budget optimization, Diffusion models, Evolutionary optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_xuYSOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes an algorithm for sequential black-box optimization (BBO) using a single generative model to propose candidates in settings where the evaluation budget is very low. In contrast to other methods in the literature, the proposed algorithm, SPARROW, requires no retraining/fine-tuning of the generative model, nor any guidance component or objective model. Candidates are simply generated by a combination of rank-based resampling, empirical improvement directions, and generative refinements based on the pretrained generative model. Experiments on a range of high-dimensional optimization problems are presented comparing the proposed method against BBO baselines.

Critical strengths
  • The proposed method has basically no "moving parts". Given a pre-trained generative model, there is no need to retrain it nor any other model during the optimization process in SPARROW. This can make the method computationally very lightweight in terms of runtime per iteration, saving a significant amount computational resources.

  • SPARROW presents significant performance improvements with respect to all baselines it was compared against across the experiments in the paper.

  • Theoretical results in the appendix support some key arguments in the paper.

  • The paper is relatively easy to read, though some parts need minor revisions.

Critical weaknesses

Related work. There have been a few methods combining BO with generative models, which make some sort of a "bridge" between classical BBO and generative BBO. I'd suggest having a look for latent-space BO methods (e.g., Gruver et al., 2023) and non-latent-space BO with generative models (Oliveira et al., 2026). References are below. Although these methods still require refitting an objective surrogate and/or a generative model, these and related methods may lead to more suitable alternatives than the more classic BO baselines which SPARROW is compared against.

Background. I believe the background in Sec. 4.1 needs some revision in its definitions of the corruption and refinement operators. The operators are defined as mappings between state spaces, but their outputs are later used as probability distributions over the state space. The two are incompatible and need a better, formal definition. Otherwise, what is currently there is not making much sense. Also note that, a deterministic transition operator would be compatible with a flow-based model, like flow matching, where noise appears only at the beginning before the state transitions take place. Diffusion, however, involves stochastic state transitions, since Gaussian noise is inject at each state transition (in discrete-time approximations).

Minor. BBO is mentioned without prior definition in the abstract. The smallest amendment would be to place it in parentheses right next to the first mention of "black-box optimization" in the first sentence.

References

  • Gruver, N., Stanton, S., Frey, N., Rudner, T. G. J., Hotzel, I., Lafrance-Vanasse, J., Rajpal, A., Cho, K., & Wilson, A. G. (2023). Protein Design with Guided Discrete Diffusion. Advances in Neural Information Processing Systems (NeurIPS), 36.
  • Oliveira, R., Steinberg, D. M., & Bonilla, E. V. (2026). Generative Bayesian Optimization: Generative Models as Acquisition Functions. The Fourteenth International Conference on Learning Representations (ICLR).
Questions for authors
  1. Although I could understand the first two design principles, "make every evaluation count" is still unclear to me. There's a mention of "SMC" (Sequential Monte Carlo?), but it's unclear how that relates to generative optimization problems. Is there any other concrete reference that can be cited to aid the discussion in that section?

  2. The algorithm is interesting, but it seems to have been put together a bit ad-hoc. Why this way of selecting directions (sampling two pairs of data points uniformly at random xax_a and xbx_b) in a usually non-linear problem was applied?

  3. How would the method deal with observation noise? It's briefly mentioned in Sec. 4.1 that rank-based optimization is more robust to evaluation noise, but that's not very clear, and observation noise is usually a significant detail to consider in practical BBO problems, especially when involving real physical processes. Some of the assumptions in the method and the analysis in the appendix seem to consider that observation noise is non-existent or negligible.

3 comments

We thank the reviewer for the constructive feedback and detailed suggestions.

Related Works. We agree that generative and latent-space BO deserve more attention. We added a discussion of Gruver et al. (2023), Oliveira et al. (2026), and related approaches to our related work section (Section 2.2). Importantly, our airfoil experiments already compare against GP and TuRBO operating in the same learned 256D latent space. More advanced methods also adapt their surrogate or generator using objective feedback, which we explicitly decided to avoid in Section 5.3 because using a mischaracterized model for acquisition can compromise the entire subsequent exploration. We further clarify this in Section 5.3 of the revised paper.

Corruption-Refinement Formalism. We agree that Section 4.1 conflates deterministic mappings with stochastic operators. We clarified the section in the revised paper.

Making every evaluation count. Methods such as RERD (Uehara et al., 2025), guide the generation through Sequential Monte Carlo sampling along the generation trajectory. This consumes multiple objective evaluations that are discarded at the end of the generation cycle. In contrast, SPARROW uses one single evaluation per proposal and retains every evaluation. This allows us to use the most available information at any stage of optimization. We clarify this in Section 3 of the revised paper and cite RERD explicitly.

Directional Mutation The mutation is a differential-evolution-inspired (Lampinen & Storn, 2004) stochastic bias. Differences between randomly sampled archive candidates provide diverse directions, oriented toward the better-ranked candidate. We do not assume these are ascent directions for nonlinear objectives, nor that their influence necessarily survives refinement. As shown by the lambda=0 ablation in Section 5.7, mutation offers a measured benefit but is not essential to performance.

Observation Noise Rank-based selection is a standard, well established choice in evolutionary BBO and its benefits under noisy evaluations have been widely recognized (e.g. CMA-ES and IGO). Intuitively, evaluation noise does not affect the ordering unless it is important enough for evaluations to cross. This makes the rank-based signal completely unaffected by small enough noise. We conducted an additional ablation on the 64D tube under Gaussian (e.g. sensor noise) and heavy-tailed (e.g. sensor interferences) Cauchy observation noise, comparing SPARROW against a tuned value-based variant. Within the strict (B=100) budget, we use 90 search evaluations and reserve 10 to reevaluate the five top-ranked candidates twice, returning the candidate with the highest median observation. Consistent with this motivation, SPARROW retains its performance advantage under mild noise and across a broad range of heavy-tailed noise levels. We include these results in Section 5.7 and Appendix G of the revised paper. We leave explicit noise-aware optimization to future work.

Minor correction. We newly define BBO at its first occurrence in the abstract.

Reviewer_xuYSOpenReview ↗

Main concerns addressed

I thank the authors for their detailed responses and the additional experiments. After reading the revised manuscript, I consider my main concerns addressed. One remaining minor suggestion is to provide more complete technical details for GPGuide, particularly how the final-candidate estimate and its guidance gradient are computed, since this is a custom baseline.

I am maintaining my current score for now and remain open to revisiting it in light of upcoming discussions with the other reviewers and the AC.

Thank you for the positive feedback. We will expand Appendix H.4 to document the step-by-step GPGuide algorithm more clearly, including the final-candidate estimation and guidance-gradient computation, to facilitate reproducibility.

Reviewer_NCDoOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes SPARROW (Sequential Proposal via Archival Rank-based Refinement for Optimization under Weak feedback), a generative black-box optimization method for the very-low-budget regime (VLB-BBO). The authors first argue for three design principles for VLB-BBO: avoid objective learning, optimize in candidate space, and make every evaluation count. Based on these principles, SPARROW combines a ranked archive with a fixed generative corruption-refinement operator. At each iteration, a parent is sampled from an exponential rank-based distribution. It is then corrupted to a rank-dependent noise level, mutated by a rank-derived directional step, and refined by the sampler, which biases it back toward the sampler support. SPARROW is evaluated on three complementary VLB-BBO scenarios and shows the strongest final performance on all three.

Critical strengths

The empirical performance is strong. The exponential rank-based selection, the rank-controlled corruption and mutation, as well as the refinement through the sampler are sensible design choices.

Critical weaknesses

The contribution of each module could be clearer. The asymptotic consistency proof relies only on the worst-ranked parent leading to resampling from the prior. The λ\lambda ablation also shows a weak effect of mutation. The main effective components seem to be the exponential rank-based parent selection (the maximum-entropy distribution) and the rank-dependent corruption-refinement. However, ablations of each design choice are not fully presented. For example, it’s hard to tell how much the rank-based design contributes.

Questions for authors
  1. After the directional step, the point is further transformed by the corruption-refinement operator. Could you explain why the improvement from the step is expected to survive this transformation?
  2. See weaknesses: at line 181, it’s stated that rank-based updates trade magnitude information for robustness and invariance. An ablation would strengthen this claim. For example, could you replace the ranks with (normalized) objective values in parent selection and in the corruption level?
3 comments

We thank the reviewer for the constructive feedback.

Directional mutation. As discussed in Section 4.2, directional mutation provides a stochastic bias toward higher-performing regions, not a guaranteed improvement direction. Of course, total corruption would completely destroy this bias, rendering the directional step useless. However, SPARROW is able to explore locally with light corruption, which affects the bias less. The lambda ablation in the revised Section 5.7 confirms that its contribution is positive but limited, making it beneficial but not critical to SPARROW's performance.

Rank-based contribution. Rank-based updates are well established in evolutionary BBO, notably in CMA-ES and Information-Geometric Optimization (Ollivier et al., 2017), which is why we adopted it. Following your suggestion, we performed an additional ablation on our tube task, which we report in Section 5.7 and Appendix G of the revised paper. We replaced ranks by normalized objective values in parent selection and corruption strength, using the same tuning protocol as for all other baselines. Rank-based SPARROW largely outperforms the value-based variant on the 64D tube at B=100 (0.304 vs 0.261 median best objective), which further validates our initial choice.

Additional ablations Further, we would like to draw the reviewers attention to the additional ablations in Section 5.7 and Appendix G, that also clarify the individual contributions of each design choice better. We show that retaining the full archive improves performance over limited-memory variants. We also show that rank-dependent corruption substantially outperforms tuned fixed corruption on Hopper, while achieving comparable performance on the tube and airfoil tasks. Finally, under noisy evaluations, rank-based SPARROW maintains an advantage over its tuned value-based alternative on the tube task.

Thank you for the rebuttal and the additional ablations. Overall, the ablations justify the design choices in the default SPARROW. Although I find that the consistency proof offers little guarantee in the low-budget regime, the empirical results are fairly strong. I will keep my positive score.

Thank you for the positive feedback. We agree that our consistency result provides only an asymptotic guarantee, with limited implications for the low-budget regime. While this distinction is already discussed in the paper, we will also highlight it in the Limitations section and identify stronger finite-budget guarantees as a direction for future work.

Reviewer_9EUQOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents SPARROW, a black-box optimizer for settings with few objective evaluations. It selects and mutates candidates using a ranked archive, then refines them with a fixed generative model trained without objective labels. SPARROW achieves higher median scores than the tested baselines on the thin-tube, HopperController, and airfoil tasks under matched evaluation budgets.

Critical strengths
  1. SPARROW uses a fixed generative prior trained without objective labels and guides the search through evaluated candidates, avoiding the need to fit an objective model from very few observations.
  2. SPARROW outperforms the tested baselines on the thin-tube, HopperController, and airfoil tasks with a budget of 100 objective evaluations.
Critical weaknesses
  1. Diffusion-ES [1] already uses an unconditional diffusion model to mutate candidates during evolutionary search, but the paper does not compare against it. EvoGD [2] also uses learned generators to improve airfoils through evolutionary search, but is not discussed in the related work.
  2. Section 5.7 includes parameter sensitivity tests and a variant without directional mutation. However, the paper does not compare keeping the full archive with keeping a smaller set, or rank-dependent corruption with a fixed corruption level.

[1] Diffusion-ES: Gradient-free Planning with Diffusion for Autonomous and Instruction-guided Driving. CVPR 2024. [2] Evolutionary generative design of supercritical airfoils: an automated approach driven by small data. Complex & Intelligent Systems

Questions for authors
  1. How does SPARROW compare with Diffusion-ES or EvoGD using the same generative prior and objective evaluation budget?
  2. How do the results change when the archive is limited to a smaller set of candidates or the corruption level is fixed instead of rank-dependent?
3 comments

We thank the reviewer for the suggestions and conducted additional experiments to address them.

Diffusion-ES. As requested, we implemented the original algorithm. We used the same protocol as for all other baselines to tune the population size and temperature. SPARROW substantially outperforms Diffusion-ES with the same prior and the same evaluation budget on all three tasks. We added this baseline in Section 5 of the revised version of the paper.

EvoGD. EvoGD trains objective-informed CycleGANs and surrogates on 501 CFD-evaluated airfoils. Its evolutionary search then optimizes surrogate predictions, with CFD used for final validation. This is closer to the acquisition-optimization stage of BO than to a sequential black-box optimizer. The authors mention online model updates as a possible extension but do not evaluate them. A faithful comparison under our setting would therefore require substantially adapting the published method. We newly cite EvoGD among objective-dependent generative approaches in the related work section (Section 2.2) of the revised paper, but exclude it from direct benchmarking.

Persistent archive. We performed additional experiments: Restricting the archive to the last or best K candidates, with K=10 or K=25. All experiments show reduced performance compared to our setup. Retaining all evaluations, as SPARROW does, preserves all available information at negligible cost, given the archive's small size. We discussed these results briefly in the revised Section 5.7 and provided more details in Appendix G.

Rank-dependent corruption. That's an excellent point. As requested, we ran a fixed-t ablation of SPARROW. We observed that, for the tube and the foil experiments, some fixed t can deliver performance similar to the rank-based corruption of SPARROW. Further investigation revealed that this t corresponded to the effective median t of the original SPARROW runs. This suggests that we could, for these tasks, tune a fixed t instead of gamma. However, the best found t performs substantially worse on Hopper. We hypothesize that Hopper's sharp and disconnected high-performing regions require both large exploration and fine local exploitation to get good results, making a single corruption scale insufficient. Our rank-based operation naturally provides a broader range of exploration scales. As before, we discussed these results briefly in the revised Section 5.7 and provided more details in Appendix G of the revised version of the paper.

Thank you for the additional experiments and clarifications. The Diffusion-ES comparison and new ablations address my main concerns, and I find the explanation regarding EvoGD reasonable.

I have one remaining question about the archive ablation. After restricting the archive to KK candidates, are ranks recomputed and normalized by the remaining archive size? Since the corruption level depends on normalized rank, truncation could also change the available corruption scales. For example, with γ=1\gamma=1, the best-ranked candidate would receive t=0.90t=0.90 when K=10K=10, compared with t=0.99t=0.99 in an archive of 100 candidates.

Overall, the revisions have strengthened the paper, and I will raise my rating from Weak Reject to Weak Accept.

Thank you for the positive reassessment. In our limited-archive ablations, ranks are recomputed and normalized by the size K of the retained archive. As you correctly point out, this also changes the discretization of the available corruption levels. We will add a clarification of this effect in the final version of the paper.

Comments on the paper

1 comment

We thank the reviewers for their constructive feedback. We have responded to their questions and suggestions, which helped us substantially strengthen the manuscript. We are pleased that the reviewers have acknowledged our improvements, with one reviewer increasing their score and the others maintaining their positive assessments.

Main improvements in the revised paper:

  • Additional baseline: Implemented and benchmarked Diffusion-ES using the same generative prior and objective evaluation budgets. SPARROW outperforms it across all three main tasks.
  • Expanded related work: Added discussions of Diffusion-ES, EvoGD, and recent generative and latent-space Bayesian optimization approaches, clarifying their differences from our setting.
  • New ablations: Investigated limited archive sizes (best/recent (K=10,25)), fixed versus rank-dependent corruption strength, and rank-based versus value-based optimization. These experiments further clarify the contributions and limitations of the proposed algorithm.
  • Robustness to observation noise: Added experiments with Gaussian and heavy-tailed Cauchy noise, supporting our choice of rank-based optimization.
  • Improved technical clarity: Revised the stochastic corruption–refinement formalism, clarified the directional mutation mechanism and the rationale behind our design principles, and expanded the experimental discussion.

We appreciate the reviewers' engagement and believe that the revised manuscript now provides a clearer characterization of our contributions, stronger empirical evidence, and a more transparent discussion of its limitations.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.