{"id":"ae191848-f462-4da7-a1a2-149f960b0e61","arxiv_id":"2412.07820","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"HbBoPs combines a structural-aware deep kernel Gaussian process with Hyperband to select LLM prompts, improving sample and query efficiency over prior methods.","lead":"This paper presents HbBoPs, a method that selects the best prompt for a large language model by combining a learned Gaussian-process surrogate with Hyperband's multi-fidelity scheduling. It reports lower error and fewer API calls than existing prompt-selection methods across ten benchmarks and three LLMs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Concern: caching lower-fidelity outputs under temperature=0.5 makes the claimed query-efficiency factor of eta optimistic, but the main efficiency advantage over TRIPLE holds even without caching.","rationale":"The reader's weakest_assumption identifies caching under stochastic LLM outputs as the soft spot, and I agree that this is where the efficiency claim is most exposed. The strongest claim in Section 5.1 is about outperforming all methods on anytime performance; at full budget, the test-error advantage over TRIPLE-SH and TRIPLE-GSE is not statistically significant (z=1.49, p=1.000 and z=1.34, p=1.000), which the reader correctly notes. So the anytime performance at 0.25-0.50 budget carries the load, and that is exactly the regime where HB's multi-fidelity scheduling and the caching/superset design is most impactful. The concern is not that the method is unsound; the ablation shows the design choices work empirically, and HbBoPs has genuine strengths: a structural-aware deep kernel that demonstrably aligns latent space with task performance (Appendix A), robust significance testing, repeated runs, and an encoder sensitivity check. But the cost accounting is the place where a skeptic should probe: temperature=0.5 and caching are in tension, the paper itself acknowledges the assumption, and no code is released to verify the caching implementation. I do not see grounds to reject the paper or demand changes beyond what the reader already proposed; the appropriate disposition is conditional acceptance with a request for either code release, a re-run under non-cached accounting, or a clear statement of how caching handles stochasticity. Therefore I keep the verdict UNCHANGED relative to the reader's CONDITIONAL, since the reader has already captured the concern and the remedy.","tokens_in":36367,"tokens_out":2075,"duration_ms":19299,"concrete_test":"Re-run a subset of the benchmark scenarios (e.g., GSM8K and second word letter on LLAMA3 and Claude 3 Haiku, 30 seeds) comparing three cost accounting variants for HbBoPs: (a) current caching with reuse of cached outputs across stages, (b) caching disabled (all samples redrawn each stage, cost counted as raw calls), and (c) re-sampling with a fixed seed per prompt-instance pair to emulate deterministic outputs while counting raw calls. If variant (b) or (c) moves the anytime curves at fraction 0.25 and 0.50 by more than the standard error ribbons in Figure 1, or overturns the 24% improvement over TRIPLE-SH at 0.25 budget, the query-efficiency claim depends on the caching assumption.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central efficiency claim is that HbBoPs achieves the reported performance with fewer LLM calls by extending lower-fidelity evaluations to higher stages and caching outputs, roughly reducing calls by a factor of eta (Appendix C). This is explicitly justified by assuming 'reasonably deterministic outcomes.' But the experimental protocol uses temperature=0.5 (Section D.2) for all three LLMs, and Section 2 acknowledges f is only observable with noise. Under stochastic sampling, a cached output from a lower fidelity can be a lucky or unlucky realization, and reusing it biases the paired halving comparisons: a prompt that got lucky on early instances is more likely to survive to higher fidelities, and the cost metric understates the number of unique LLM calls needed to obtain an unbiased estimate at the higher fidelity. This is the same weakness the paper itself flags in Appendix C, and the ablation in Appendix E.4 tests supersets versus no supersets within the stochastic protocol, finding supersets significantly better, which is consistent with the caching assumption mattering. If caching is invalid, the anytime performance curves shift right (real cost is higher than reported), and the discrepancy between validation and test improvements at full budget (Table 2, test medians near zero) could be explained by noisy cached decisions. The concern is load-bearing because the query-efficiency advantage over full-fidelity methods is the stated contribution, and the advantage over multi-fidelity TRIPLE-SH at full budget is not statistically significant (p=0.236 validation, p=1.000 test, Appendix E.1), so the anytime comparison is the remaining evidence for the efficiency claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes HbBoPs, a black-box prompt selection method that combines a structural-aware deep kernel Gaussian Process (GP) with Hyperband multi-fidelity scheduling. Prompts are composed of an instruction and a few-shot exemplar; the GP is trained on separate BERT embeddings of the two components and proposes candidates via expected improvement, while Hyperband controls the number of validation instances per evaluation. The authors evaluate HbBoPs against random search, four full-fidelity baselines (vanilla BO, HDBO, BOPCA, EASE, MIPROv2) and two multi-fidelity state-of-the-art methods (TRIPLE-SH, TRIPLE-GSE) on ten tasks and three LLMs, with 30 repeats per scenario, reporting normalized validation/test errors versus total LLM-call budget. They report that HbBoPs achieves lower average errors than all competitors, especially in the anytime regime, and they support this with mixed-effects models, Tukey post-hoc tests, component ablations, and an encoder robustness study.","tokens_in":36635,"tokens_out":8869,"duration_ms":76935,"significance":"The contribution is potentially valuable: to my knowledge it is the first method in static black-box prompt selection to combine a surrogate model with a multi-fidelity scheduler, and the empirical design is unusually thorough (10 tasks x 3 LLMs x 30 runs, with linear mixed-effects models and corrected post-hoc tests, plus ablations of the deep kernel, structural-awareness, and Hyperband design choices). The statistical analysis is a strength: the authors report exact test statistics and p-values rather than only mean curves. However, the headline claim of 'outperforms state-of-the-art methods in both performance and efficiency' is only partially supported: at full budget, the advantage over TRIPLE-SH and TRIPLE-GSE is not statistically significant, and the efficiency claim relies on a caching assumption that is not validated under temperature=0.5. The anytime improvements and component ablations are credible and are the paper's main contribution.","major_comments":[{"comment":"The claim that HbBoPs outperforms all methods at full budget is not supported by the paper's own statistical tests. In Appendix E.1, the Tukey post-hoc tests at fraction 1.00 report non-significant differences versus TRIPLE-SH for validation (z=1.87, p=0.236) and test error (z=1.49, p=1.000), and versus TRIPLE-GSE for test error (z=1.34, p=1.000). Table 2 also shows median test improvements over TRIPLE-SH at full budget of -0.006 (Claude 3 Haiku), 0.000 (LLAMA3 8B), and -0.001 (Mistral 7B). The abstract and Section 5.1 should either restrict the 'outperforms' claim to the anytime regime or provide additional evidence (e.g., more repetitions, a different aggregation, or a focused analysis) that HbBoPs also improves final test performance.","section":"Section 5.1; Appendix E.1"},{"comment":"The query-efficiency advantage is partly built on caching lower-fidelity outputs and reusing them in higher stages. Appendix C justifies this by assuming 'reasonably deterministic outcomes,' but the experimental protocol sets temperature=0.5 for all three LLMs (Section D.2), and Section 2 states that the validation error is observed with noise. Under stochastic sampling, a cached output is one realization; reusing it at higher fidelity biases the paired halving comparisons and understates the number of LLM calls that would be needed to obtain an unbiased estimate at the higher fidelity. The paper should either validate the determinism assumption (e.g., with temperature=0 or fixed seeds) or quantify the sensitivity of the anytime performance curves and the claimed factor-of-eta call reduction to stochasticity, for example by comparing the cached implementation with an implementation that re-queries at each fidelity.","section":"Appendix C; Section 3.3; Section D.2"},{"comment":"The text states that 'HbBoPs consistently outperforms TRIPLE-SH in terms of both anytime validation and test error,' but Table 2 shows the opposite at full budget for test error: the median relative improvements are negative or zero for all three LLMs. This overstatement should be corrected, e.g., by limiting the consistency claim to the anytime fractions (0.25 and 0.50) and noting that the full-budget test differences are within noise.","section":"Section 5.2; Table 2"}],"minor_comments":[{"comment":"The legend entry 'TRIPLE-SH (Shi et al. 2014)' should read '(Shi et al., 2024)' to match the reference list.","section":"Figure 1 caption"},{"comment":"The passage 'roughly by a factor of eta), In HbBoPs we cache the output...' contains a stray closing parenthesis and a missing sentence break; please revise for clarity.","section":"Appendix C"},{"comment":"The threshold 'at least four observations' used for training the deep-kernel GP is defined only in the experimental setup; it would be helpful to state it in the method description in Section 3.4 alongside the definition of 'enough' observations.","section":"Section 4.2"},{"comment":"The expression for n in the for-loop header is typeset with an ambiguous 'l' and 'm'; please use explicit floor/ceiling notation so that the bracket schedule is unambiguous.","section":"Algorithm 1"},{"comment":"The normalization of errors 'by the performance of the worst and best prompt' should specify whether the 'best prompt' is the global optimum over the candidate set P or the best prompt found by any method; otherwise the normalized errors are not uniquely defined.","section":"Section 5"},{"comment":"No link to the code is provided; given the complexity of the method and the many design choices, releasing the implementation would substantially aid reproducibility.","section":"Section 6 / Reproducibility"}],"recommendation":"major_revision","confidential_remarks":"This is a solid empirical paper with a potentially useful method, but the authors' framing is stronger than the evidence. The full-budget performance advantage over TRIPLE-SH/TRIPLE-GSE is not statistically significant, and the efficiency gain depends on a caching assumption that conflicts with the temperature=0.5 protocol. I recommend major revision rather than reject because the anytime results and ablations are reproducible and valuable, and the issues can be addressed by revised claims and additional analysis."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a clean, honest piece of applied ML. HbBoPs is a sensible combination: a structural-aware deep kernel GP (separate embeddings for instructions and exemplars) inside Hyperband for static prompt selection. The components are known, but the specific combination and the modular treatment of prompt structure are new and give real gains in the low-budget regime. The experimental work is the strongest part: ten tasks, three LLMs, 30 runs each, linear mixed-effects models, Tukey post-hoc tests, ablations, even an encoder sensitivity analysis. The authors also flag their own limitation about caching in Appendix C, which is refreshingly candid. No code is released, which is a real drawback for a benchmark-heavy paper, though the method is simple enough to reimplement.\n\nThe soft spots are real but not disqualifying. The biggest one is the query-efficiency claim. The factor-of-eta reduction assumes caching lower-fidelity LLM outputs is valid, but the protocol runs all models at temperature=0.5. A lucky cached output can bias the halving decisions, and the anytime curves understate true cost. The stress-test concern is fair: the advantage over full-fidelity baselines at full budget is driven by the anytime comparison, and the full-budget test-error edge over TRIPLE-SH and TRIPLE-GSE is not statistically significant. However, the ablation in E.4 shows supersets materially help even within the stochastic protocol, so the method still works in practice; it just costs more than reported. The right fix is to either run at a deterministic temperature (or with greedy decoding) or report costs without the caching bonus.\n\nThe smaller issue is overclaiming in the abstract: “outperforms state-of-the-art in both performance and efficiency” glosses over the non-significant full-budget test results. That is a wording problem, not a scientific one.\n\nWho is this for? Practitioners doing API-based prompt selection on a fixed candidate pool, and people working on multi-fidelity BO generally. The method is likely to be useful even with the efficiency caveat. I would accept this for peer review without hesitation, with a request to address the stochastic-caching mismatch and tone down the abstract. My own verdict would be conditional accept, not reject.","headline":"A solid, well-tested engineering contribution to black-box prompt selection, with an honest but load-bearing efficiency claim that needs a small fix before the abstract can stand.","tokens_in":37238,"tokens_out":711,"would_cite":true,"duration_ms":9640,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A new method, HbBoPs, selects better LLM prompts with fewer API calls by combining a structural-aware Gaussian Process with Hyperband scheduling.","keywords":["prompt selection","black-box optimization","Bayesian optimization","multi-fidelity","Hyperband","deep kernel Gaussian Process","large language models","few-shot learning"],"falsifier":"Re-run the HbBoPs experiments with high sampling temperature (e.g., temperature=1.0) or with seed-dependent variability in LLM outputs, and compare the number of true LLM calls needed to reach the same test error as reported; if the cached lower-fidelity evaluations produce inconsistent rankings, HbBoPs's edge over TRIPLE-SH would shrink or vanish.","tokens_in":36155,"feed_emoji":"🧠","tokens_out":1400,"duration_ms":15073,"temperature":0.7,"pith_summary":"This paper introduces HbBoPs, a method for static black-box prompt selection that jointly chooses instructions and few-shot exemplars from a finite candidate pool. The method pairs a structural-aware deep kernel Gaussian Process with Hyperband as a multi-fidelity scheduler to balance sample-efficiency (fewer prompt evaluations) and query-efficiency (fewer total LLM calls). The central claim, supported by experiments across ten benchmarks and three LLMs, is that HbBoPs outperforms existing full-fidelity and multi-fidelity methods—especially in anytime performance under a limited budget. If true, it means practitioners can identify better-performing prompts for black-box LLMs while spending fewer API calls.","feed_headline":"Smarter prompt picking with fewer LLM calls","feed_subtitle":"HbBoPs pairs a structural Gaussian Process with Hyperband to find strong prompts on a tight budget.","key_machinery":"The central machinery is the structural-aware deep kernel Gaussian Process: a GP whose kernel is a learned feature extractor that processes instruction embeddings and exemplar embeddings through separate feed-forward networks, concatenates them, and projects to a low-dimensional latent space aligned with downstream performance. This surrogate is trained online and used with Expected Improvement to propose candidate prompts within Hyperband brackets, where the number of validation instances serves as the fidelity parameter.","core_discovery":"The paper claims that combining a structural-aware deep kernel Gaussian Process (which learns a low-dimensional latent representation from separate embeddings of instructions and few-shot exemplars) with Hyperband (which adaptively allocates validation instances across fidelity levels) yields a prompt selection method that is both sample-efficient and query-efficient. In experiments, HbBoPs achieves the lowest average normalized test error at full budget (0.150) compared to all baselines and competitors, and shows the largest improvements in the low-budget regime, e.g., roughly 35% lower error than the best full-fidelity method (HDBO) and 24% lower than the best multi-fidelity method (TRIPLE-SH) at 0.25 budget. The paper also demonstrates through ablation that each component (deep kernel, structural-awareness, Hyperband, and BO proposal) contributes significantly to the overall performance.","pith_inferences":["The efficiency gains reported are partially contingent on caching lower-fidelity LLM outputs and assuming near-deterministic outputs; with temperature=0.5, stochasticity could undermine this assumption, potentially inflating the reported query-efficiency advantage over methods that do not cache.","The paper's focus on exact-match loss on ten benchmarks may not capture settings with more nuanced or open-ended outputs, where the surrogate's learned embeddings may transfer differently.","A direct extension would be to test HbBoPs on larger candidate pools (e.g., hundreds or thousands of prompts) to see whether the deep kernel's capacity and Hyperband's bracket structure scale gracefully.","The multi-objective extension mentioned in the paper (balancing prompt performance against inference latency) is a natural next step, but is not explored here."],"forward_implications":["HbBoPs can identify well-performing prompts with substantially fewer LLM calls than full-fidelity Bayesian optimization or bandit methods, making black-box prompt selection more practical under API budget constraints.","In the low-budget regime (e.g., 0.25 of total calls), the method's gains are largest, suggesting it is especially effective when evaluation budgets are severely limited.","The structural-aware deep kernel generalizes across encoder models, indicating the approach is robust to the choice of embedding backbone.","The paper's design choices—caching lower-fidelity evaluations, using supersets for higher stages, and selecting the incumbent from full-fidelity evaluations—make Hyperband viable for prompt selection.","The method can be extended to evolving candidate pools, enabling integration with mutation-based or iterative prompt optimizers."],"supporting_citations":[{"why":"Provides the Hyperband algorithm, which is the multi-fidelity scheduler at the core of HbBoPs.","marker":"Li et al. (2018)"},{"why":"Introduces TRIPLE, the main multi-fidelity baseline, and the idea of using number of validation instances as a fidelity parameter.","marker":"Shi et al. (2024)"},{"why":"Provides the deep kernel learning framework used for the structural-aware GP.","marker":"Wilson et al. (2016)"},{"why":"Supplies the Automatic Prompt Engineering method used to generate instruction candidates and the BBII benchmarks.","marker":"Zhou et al. (2023)"},{"why":"BOHB, the hyperparameter optimization method that combines BO with Hyperband, which HbBoPs adapts to prompt selection.","marker":"Falkner et al. (2018)"},{"why":"Defines the Expected Improvement acquisition function used for BO proposals.","marker":"Kushner (1964)"},{"why":"Provides the Successive Halving algorithm, which Hyperband relies on within each bracket.","marker":"Karnin et al. (2013)"}],"fun_headline_variants":["Better prompts with fewer LLM calls","Hyperband accelerates black-box prompt search","Efficient prompt selection via multi-fidelity BO","Cut prompt evaluation cost with HbBoPs","GP and Hyperband team up for cheaper prompts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method's query-efficiency gains assume that LLM outputs are reasonably deterministic, so that cached lower-fidelity evaluations remain valid at higher fidelities; the paper uses temperature=0.5, making this assumption fragile.","fun_headline_variants_meta":{"raw":{"variants":["Better prompts with fewer LLM calls","Hyperband accelerates black-box prompt search","Efficient prompt selection via multi-fidelity BO","Cut prompt evaluation cost with HbBoPs","GP and Hyperband team up for cheaper prompts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0002,"raw_usage":{"total_tokens":1340,"prompt_tokens":873,"completion_tokens":467,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":489,"completion_tokens_details":{"reasoning_tokens":401}},"tokens_in":489,"tokens_out":467,"duration_ms":4965,"temperature":1.0,"reasoning_tokens":401,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:43:04.065256+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the HbBoPs experiments with high sampling temperature (e.g., temperature=1.0) or with seed-dependent variability in LLM outputs, and compare the number of true LLM calls needed to reach the same test error as reported; if the cached lower-fidelity evaluations produce inconsistent rankings, HbBoPs's edge over TRIPLE-SH would shrink or vanish.","supporting_citations":[{"cited_title":"(2018) for each proposal with a probability of ρ= 0.1","cited_arxiv_id":null,"evidence_quote":"BOHB, the hyperparameter optimization method that combines BO with Hyperband, which HbBoPs adapts to prompt selection."}],"review_version":1}