arxiv: 2605.10856 · v1 · submitted 2026-05-11 · 🪐 quant-ph · physics.data-an

Recognition: no theorem link

Improving search efficiency via adaptive acquisition function selection in discrete black-box optimization

Reo Shikanai , Masayuki Ohzeki

Authors on Pith no claims yet

Pith reviewed 2026-05-12 04:00 UTC · model grok-4.3

classification 🪐 quant-ph physics.data-an

keywords Bayesian optimizationdiscrete black-box optimizationQUBOHUBOGaussian processacquisition functionstagnation detection

0 comments

The pith

A hybrid method for discrete black-box optimization switches from BOCS to an adaptive Gaussian process on stagnation to find better solutions than random addition.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper seeks to prevent stagnation in combinatorial black-box search where candidate points grow exponentially and evaluations are costly. BOCS works well with limited data but begins repeating already-evaluated points once more observations accumulate. The authors introduce a hybrid that keeps BOCS as the main engine and activates a Gaussian process fallback, using multiple Lower Confidence Bound acquisition functions chosen adaptively, only when repetition is detected. Experiments on fully connected QUBO and HUBO problems show this yields lower objective values than simply adding random points. The gain stems from generating candidates that advance progress inside Hamming-distance neighborhoods rather than merely nearby low-energy points.

Core claim

The paper claims that its hybrid method, employing BOCS as the primary search and activating a Gaussian process with adaptively selected LCB acquisition functions upon detecting stagnation, generates alternative unevaluated points that lead to solutions with superior objective values compared to the random-point addition strategy in fully connected QUBO and HUBO black-box optimizations. Additional analyses indicate that the advantage arises from promoting progress within Hamming-distance neighborhoods and that retaining near-fully connected surrogate capacity is important for quantum annealer applications.

What carries the argument

Stagnation detection that triggers a switch from the BOCS parametric model to a Gaussian process surrogate with adaptively chosen Lower Confidence Bound acquisition functions for proposing new points.

If this is right

The hybrid finds solutions with better objective values than random-point addition on fully connected QUBO and HUBO black-box functions.
Its advantage comes from selecting points that promote search progress inside Hamming-distance neighborhoods rather than simply adding low-energy points near known good solutions.
Sparse surrogate models retain value for quantum annealer applications only when they preserve near-fully connected representational capacity.
Adaptive selection among multiple LCB functions dynamically adjusts the exploitation-exploration balance during the fallback phase.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The stagnation-triggered switch could be tested in other surrogate-based discrete optimizers that suffer from repetition once data accumulates.
Direct runs on quantum annealing hardware would check whether the observed benefit of full connectivity holds in physical settings.
Similar detection-plus-adaptive-fallback logic might reduce stagnation in continuous Bayesian optimization without requiring changes to the core model.

Load-bearing premise

Detecting search stagnation and switching to the Gaussian process with adaptive LCB selection will reliably produce useful unevaluated points that advance the search without introducing new stagnation or bias.

What would settle it

Apply both the hybrid method and the random-point addition baseline to identical fully connected QUBO instances for a fixed evaluation budget and compare final objective values; consistent failure of the hybrid to achieve lower values would falsify the performance claim.

Figures

Figures reproduced from arXiv: 2605.10856 by Masayuki Ohzeki, Reo Shikanai.

**Figure 2.** Figure 2: FIGURE 2 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: FIGURE 3 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

**Figure 4.** Figure 4: FIGURE 4 [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗

read the original abstract

In discrete-variable black-box optimization, the number of candidate solutions grows combinatorially, while each evaluation is often expensive. Therefore, it is important to identify promising solutions efficiently within a limited number of trials. Bayesian Optimization of Combinatorial Structures (BOCS), an existing parametric method, works effectively when only a small amount of data is available. However, as the number of observations increases, BOCS tends to repeatedly propose points that have already been evaluated, which leads to search stagnation. A random-point addition strategy has been proposed to address this issue when an evaluated point is proposed, but it cannot sufficiently exploit information from promising data obtained so far. In this study, we propose a hybrid method that uses BOCS as the main search framework and generates alternative unevaluated points using a Gaussian process only when search stagnation is detected. In the Gaussian-process-based component, multiple Lower Confidence Bound (LCB) acquisition functions are adaptively selected to dynamically control the balance between exploitation and exploration. Numerical experiments using fully connected Quadratic Unconstrained Binary Optimization (QUBO) and Higher-order Unconstrained Binary Optimization (HUBO) as black-box functions show that the proposed method finds solutions with better objective values than the conventional random-point addition method in both settings. Additional analyses show that its effectiveness comes from selecting points that promote search progress within Hamming-distance neighborhoods, rather than simply adding low-energy points near promising solutions. Experiments with sparse surrogate models for quantum annealer applications further suggest the importance of retaining near-fully connected representational capacity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper offers a practical hybrid fix for BOCS stagnation using an adaptive GP fallback, with experiments showing gains over random addition on QUBO and HUBO, but the evidence lacks detail on robustness.

read the letter

This paper's core move is to keep BOCS as the main engine for discrete black-box optimization but switch to a Gaussian process with adaptively selected LCB acquisition functions once stagnation is detected. That addresses a real issue where the parametric model starts repeating evaluated points as data grows, and the experiments report better final objective values than the random-point addition baseline on fully connected QUBO and HUBO instances. The Hamming-neighborhood analysis is a useful addition, showing the method advances search structure rather than just grabbing nearby low-energy points, and the sparse surrogate tests tie it to quantum annealer use cases. The adaptive LCB selection is the clearest new element compared to earlier random-addition fixes. The work is straightforward and targets a practical pain point in combinatorial optimization. The experiments are the strongest part, as they cover both QUBO and HUBO and include some post-hoc insight into why the points help. That said, the claims rest on numerical results whose statistical details, run counts, variance, and ablation on the adaptive rule versus fixed LCB or other fallbacks are not spelled out clearly. If GP fitting on binary data turns out sensitive to kernels or hyperparameters, the reported edge could shrink. The stress-test point about missing direct comparisons to non-adaptive alternatives holds weight here. This is aimed at researchers doing Bayesian optimization on discrete or quantum-related problems who already use BOCS or similar tools. A reader wanting a concrete, testable tweak with supporting runs will get value from the method and the neighborhood analysis. It deserves a serious referee because the stagnation problem is genuine and the hybrid idea is simple enough to evaluate properly. I would recommend sending it to peer review, with requests for more rigorous stats, ablations, and robustness checks.

Referee Report

2 major / 2 minor

Summary. The paper proposes a hybrid method for discrete black-box optimization that employs BOCS as the primary search framework and, upon detecting stagnation (repeated proposals of already-evaluated points), falls back to a Gaussian process surrogate that adaptively selects among multiple Lower Confidence Bound (LCB) acquisition functions to generate alternative unevaluated points. Numerical experiments on fully connected QUBO and HUBO instances report that the hybrid approach achieves better objective values than the conventional random-point addition baseline; additional post-hoc analyses link the gains to progress within Hamming-distance neighborhoods rather than simple proximity to low-energy points, and sparse-surrogate experiments underscore the value of retaining near-fully-connected representational capacity for quantum-annealer applications.

Significance. If the reported performance gains are statistically robust, the hybrid strategy offers a practical way to mitigate stagnation in combinatorial optimization without sacrificing the data-efficiency of parametric models such as BOCS. The adaptive LCB mechanism and the Hamming-neighborhood analysis provide concrete insight into how surrogate-based alternatives can advance search beyond random injection, with potential relevance to quantum-annealing workflows that rely on sparse or dense surrogate models.

major comments (2)

[Numerical experiments] The central empirical claim—that the hybrid method finds solutions with better objective values than random-point addition on QUBO and HUBO—rests on numerical experiments whose statistical details (number of independent trials, error bars, significance tests, or data-exclusion criteria) are not reported. Without these, the magnitude and reliability of the reported improvements cannot be assessed.
[Gaussian-process-based component] The manuscript presents adaptive selection among multiple LCB acquisition functions as the mechanism that dynamically balances exploitation and exploration in the GP fallback, yet no ablation is provided that isolates this adaptivity against a fixed (non-adaptive) LCB or a purely random GP proposal within the same hybrid BOCS framework. Consequently it remains unclear whether the observed advantage over random-point addition is attributable to the adaptive rule or simply to the presence of any GP-based alternative.

minor comments (2)

[Additional analyses] The abstract and later sections refer to “post-hoc analyses on Hamming neighborhoods” and “promoting search progress within Hamming-distance neighborhoods”; these should be accompanied by explicit quantitative metrics (e.g., average Hamming distance of accepted points, fraction of neighborhood improvements) and a clear description of how the neighborhoods are defined and sampled.
[Sparse surrogate models] The sparse-surrogate experiments for quantum-annealer applications are mentioned only briefly; a direct side-by-side comparison of objective-value trajectories or stagnation frequency between the sparse and dense surrogates would strengthen the claim that near-fully-connected capacity is important.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments on our manuscript. We address each major point below and will revise the paper to incorporate the suggested improvements to the empirical validation.

read point-by-point responses

Referee: [Numerical experiments] The central empirical claim—that the hybrid method finds solutions with better objective values than random-point addition on QUBO and HUBO—rests on numerical experiments whose statistical details (number of independent trials, error bars, significance tests, or data-exclusion criteria) are not reported. Without these, the magnitude and reliability of the reported improvements cannot be assessed.

Authors: We agree that the statistical details of the experiments require more explicit reporting. In the revised manuscript we will state the number of independent trials performed, add error bars to all relevant figures, include the results of statistical significance tests comparing the hybrid method to the baseline, and confirm that no data were excluded from the reported results. These changes will allow readers to properly evaluate the robustness of the observed improvements. revision: yes
Referee: [Gaussian-process-based component] The manuscript presents adaptive selection among multiple LCB acquisition functions as the mechanism that dynamically balances exploitation and exploration in the GP fallback, yet no ablation is provided that isolates this adaptivity against a fixed (non-adaptive) LCB or a purely random GP proposal within the same hybrid BOCS framework. Consequently it remains unclear whether the observed advantage over random-point addition is attributable to the adaptive rule or simply to the presence of any GP-based alternative.

Authors: The referee correctly notes the absence of an ablation isolating the adaptive LCB rule. While the current experiments demonstrate the overall hybrid method's advantage over random-point addition, we will add an ablation study in the revision. This will compare the adaptive LCB selection against both a fixed (non-adaptive) LCB and random GP proposals, all embedded in the same hybrid BOCS framework, to clarify the specific contribution of the adaptivity mechanism. revision: yes

Circularity Check

0 steps flagged

No significant circularity; empirical method with independent experimental validation

full rationale

The paper proposes a hybrid algorithmic procedure (BOCS primary search with GP-based fallback using adaptive LCB selection upon detected stagnation) and validates it solely through numerical experiments on QUBO/HUBO black-box instances, comparing objective values against a random-point-addition baseline. No derivation chain, first-principles prediction, or fitted-parameter result is claimed; performance assertions rest on direct empirical comparison rather than any equation or self-citation that reduces to the method's own inputs by construction. The approach is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The central claim rests on the empirical effectiveness of the hybrid strategy and the interpretation that gains come from Hamming-neighborhood progress; no explicit free parameters, axioms, or invented entities are stated in the abstract.

pith-pipeline@v0.9.0 · 5574 in / 1169 out tokens · 34343 ms · 2026-05-12T04:00:01.775186+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

M. Doi, Y . Nakao, T. Tanaka, M. Sako, and M. Ohzeki, ‘‘Exploration of new chemical materials using black-box optimization with the D-Wave quantum annealer,’’Frontiers in Computer Science, vol. 5, p. 1286226,

work page
[2]

Available: https://doi.org/10.3389/fcomp.2023.1286226

[Online]. Available: https://doi.org/10.3389/fcomp.2023.1286226

work page doi:10.3389/fcomp.2023.1286226 2023
[3]

Kitai, J

K. Kitai, J. Guo, S. Ju, S. Tanaka, K. Tsuda, J. Shiomi, and R. Tamura, ‘‘Designing metamaterials with quantum annealing and factorization ma- chines,’’Physical Review Research, vol. 2, no. 1, p. 013319, 2020

work page 2020
[4]

A. Tučs, F. Berenger, A. Y umoto, R. Tamura, T. Uzawa, and K. Tsuda, ‘‘Quantum annealing designs nonhemolytic antimicrobial peptides in a discrete latent space,’’ACS Medicinal Chemistry Letters, vol. 14, pp. 577– 582, 2023

work page 2023
[5]

D. R. Jones, M. Schonlau, and W. J. Welch, ‘‘Efficient global optimiza- tion of expensive black-box functions,’’Journal of Global Optimization, vol. 13, no. 4, pp. 455–492, 1998

work page 1998
[6]

Shahriari, K

B. Shahriari, K. Swersky, Z. Wang, R. P . Adams, and N. de Freitas, ‘‘Taking the human out of the loop: A review of bayesian optimization,’’ Proceedings of the IEEE, vol. 104, no. 1, pp. 148–175, 2016

work page 2016
[7]

Baptista and M

R. Baptista and M. Poloczek, ‘‘Bayesian optimization of combinatorial structures,’’ inProceedings of the 35th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, J. Dy and A. Krause, Eds., vol. 80. PMLR, 2018, pp. 462–471. [Online]. Available: https://proceedings.mlr.press/v80/baptista18a.html

work page 2018
[8]

Morita, Y

K. Morita, Y . Nishikawa, and M. Ohzeki, ‘‘Random postprocessing for combinatorial bayesian optimization,’’Journal of the Physical Society of Japan, vol. 92, no. 12, p. 123801, 2023. [Online]. Available: https://doi.org/10.7566/JPSJ.92.123801

work page doi:10.7566/jpsj.92.123801 2023
[9]

C. E. Rasmussen and C. K. I. Williams,Gaussian Processes for Machine Learning. Cambridge, MA: The MIT Press, 2006

work page 2006
[10]

M. W. Hoffman, E. Brochu, and N. de Freitas, ‘‘Portfolio allocation for bayesian optimization,’’ inProceedings of the 27th Conference on Uncertainty in Artificial Intelligence. AUAI Press, 2011, pp. 327–336. [Online]. Available: https://arxiv.org/abs/1009.5419

work page arXiv 2011
[11]

Kirkpatrick, C

S. Kirkpatrick, C. D. Gelatt, and M. P . V ecchi, ‘‘Optimization by simulated annealing,’’Science, vol. 220, no. 4598, pp. 671–680, 1983

work page 1983
[12]

Kadowaki and H

T. Kadowaki and H. Nishimori, ‘‘Quantum annealing in the transverse ising model,’’Physical Review E, vol. 58, no. 5, pp. 5355–5363, 1998. [Online]. Available: https://doi.org/10.1103/PhysRevE.58.5355

work page doi:10.1103/physreve.58.5355 1998
[13]

M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P . Bunyk, E. M. VOLUME 11, 2023 9 Authoret al.: Preparation of Papers for IEEE TRANSACTIONS and JOURNALS Chapple, J. Enderud, J. P . Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C....

work page doi:10.1038/nature10012 2023
[14]

A. S. Koshikawa, M. Ohzeki, T. Kadowaki, and K. Tanaka, ‘‘Benchmark test of black-box optimization using D-Wave quantum annealer,’’Journal of the Physical Society of Japan, vol. 90, no. 6, p. 064001, 2021. [Online]. Available: https://doi.org/10.7566/JPSJ.90.064001

work page doi:10.7566/jpsj.90.064001 2021
[15]

Otsuka, K

M. Otsuka, K. Kodama, K. Morita, and M. Ohzeki, ‘‘Filtering out mislabeled training instances using black-box optimization and quantum annealing,’’Scientific Reports, vol. 15, p. 37892, 2025. [Online]. Available: https://doi.org/10.1038/s41598-025-21686-z

work page doi:10.1038/s41598-025-21686-z 2025
[16]

Quantum knots and the number of knot mosaics

V . Choi, ‘‘Minor-embedding in adiabatic quantum computation: I. the pa- rameter setting problem,’’Quantum Information Processing, vol. 7, no. 5, pp. 193–209, 2008. [Online]. Available: https://doi.org/10.1007/s11128- 008-0082-9

work page doi:10.1007/s11128- 2008
[17]

Tasseff, T

B. Tasseff, T. Albash, Z. Morrell, M. Vuffray, A. Y . Lokhov, S. Misra, and C. Coffrin, ‘‘On the emerging potential of quantum annealing hardware for combinatorial optimization,’’Journal of Heuristics, vol. 30, no. 5–6, pp. 325–358, 2024. [Online]. Available: https://doi.org/10.1007/s10732- 024-09530-5

work page doi:10.1007/s10732- 2024
[18]

Srinivas, A

N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger, ‘‘Gaussian process optimization in the bandit setting: No regret and experimental design,’’ in Proceedings of the 27th International Conference on Machine Learning, 2010, pp. 1015–1022

work page 2010
[19]

Gurobi Optimization, ‘‘Gurobi optimizer reference manual,’’ 2026

L. Gurobi Optimization, ‘‘Gurobi optimizer reference manual,’’ 2026. [Online]. Available: https://www.gurobi.com

work page 2026
[20]

Nishimura, Y

K. Nishimura, Y . Sakamoto, T. Shimizu, K. Suzuki, and Y . Y amashiro, ‘‘Openjij,’’ Oct. 2025, version 0.11.6. [Online]. Available: https://github.com/Jij-Inc/OpenJij 10 VOLUME 11, 2023

work page 2025