{"id":"66ab4577-7179-4465-b8d2-6018c28079f1","arxiv_id":"2501.03508","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A Bayesian 'knowledge gradient' policy for sequentially choosing which prompts to evaluate finds better language-model prompts within 30 evaluations than evolutionary, bandit, and greedy baselines on instruction-induction tasks.","lead":"This paper presents a method that automatically chooses which prompts to test in a language model, using a Bayesian model to share information between similar prompts and a 'knowledge gradient' rule to pick the next prompt under a tight budget. The paper reports that this approach beats several existing prompt-optimization methods on instruction-induction tasks while using at most 30 test evaluations.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claimed significant outperformance is unsupported: no statistical significance tests are reported, and observed gaps are small relative to reported variability.","rationale":"The reader's weakest_assumption identifies the linear-Gaussian model (Eq. 1) as the most load-bearing concern. I disagree. The linear model, if misspecified, would undermine the theoretical 'optimality' of the KG policy, but the empirical comparison of SOPL-KG against EvoPrompt, TRIPLE, and the SOPL variants does not depend on the model being exactly correct: all three SOPL policies use the same linear model, and the baselines do not use it at all. A failure of the linearity assumption would weaken the interpretability claims and the theoretical grounding, but it would not by itself invalidate the observed rankings if the differences are real and reproducible. In contrast, the abstract's assertion that the method 'significantly outperforms' benchmark strategies is the central claim, and the paper provides no statistical evidence for it. The reported standard deviations are averaged within tasks across replications, which does not account for task-level variability in the improvement; the post hoc selection of 13 'challenging' tasks further complicates any claim of general superiority. The minimal check that would settle this is a paired significance test over tasks (or a replication-level mixed-effects analysis). If such a test does not support significance, the paper's headline finding is not established, and this would affect the verdict more strongly than the linear-model concern. Therefore, I recommend keeping the reader's CONDITIONAL verdict (since the gap is addressable by adding the missing tests) but flagging that the empirical claim is currently unsupported.","tokens_in":12722,"tokens_out":10454,"duration_ms":96822,"concrete_test":"For each of the 13 tasks, compute the mean test score over the 20 replications for SOPL-KG and for each baseline (EvoPrompt, TRIPLE, SOPL-TS, SOPL-Greedy). Then perform paired two-sided t-tests (and, as a robust check, Wilcoxon signed-rank tests) on the 13 paired differences for SOPL-KG versus each baseline, and report 95% confidence intervals for the mean difference. If any comparison fails to reach statistical significance at α=0.05 or has a confidence interval crossing zero, the claim of significant outperformance should be downgraded and the verdict adjusted accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim, repeated in the abstract and introduction, is that SOPL-KG 'significantly outperforms' benchmark strategies on instruction induction tasks, with the headline result of average test score 0.6281 (Table 2). However, the evidence presented consists only of point estimates: the mean test score over 13 tasks and the average within-task standard deviation across 20 replications. These within-task standard deviations (0.067–0.097) are of the same order as the between-method gaps (0.033–0.067), yet no statistical test is reported. Critically, the 13 tasks are selected post hoc as 'challenging' (Section 6), so the comparison lacks even a pre-specified population of tasks. Without a paired significance test across tasks (or across replications when paired by seed) and without confidence intervals, the observed improvements over EvoPrompt, TRIPLE, SOPL-TS, and SOPL-Greedy could plausibly arise from seed noise or a few favorable tasks. The paper does not even report per-task differences, so the reader cannot assess whether the average improvement is consistent or driven by outliers. This is a load-bearing gap because 'significantly outperforms' is precisely the paper's main empirical assertion; if the differences are not statistically significant, the central claim collapses, regardless of the linear-model assumption.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SOPL, a sequential optimal learning framework for automated prompt engineering. Prompts are represented by interpretable categorical features, and a Bayesian linear model links the logit of validation accuracy to one-hot-encoded features. A Knowledge-Gradient policy, computed through mixed-integer conic optimization, selects prompt representations to evaluate under a limited budget. The method is tested on instruction induction tasks using GPT-3.5, with comparisons against EvoPrompt, TRIPLE, Thompson sampling, and a greedy policy. The central claim is that SOPL-KG significantly outperforms these benchmarks within 30 or fewer evaluations, particularly on a set of 13 'challenging' tasks.","tokens_in":12961,"tokens_out":3444,"duration_ms":34369,"significance":"If substantiated, the contribution is useful for automated prompt engineering in cost-sensitive applications: it moves beyond static candidate sets, uses an interpretable feature representation, and applies a forward-looking Bayesian learning policy that exploits correlations among prompts. The paper supplies explicit Bayesian update equations, a benchmark comparison on a public dataset, and several sensitivity analyses. The main value, however, rests on the empirical claim of significant improvement, and the current evidence for that claim is incomplete in ways that a revision can address.","major_comments":[{"comment":"The abstract and Section 6 claim that SOPL-KG 'significantly outperforms' benchmark strategies, but no statistical significance test is reported anywhere in the paper. The absolute gaps between methods (0.033 to 0.067) are of the same order as the average within-task standard deviations (0.067 to 0.097), so the observed differences could plausibly arise from seed noise. In addition, the 13 tasks are selected post hoc as 'challenging' based on validation scores below 80% and large variance, so the comparison is not over a pre-specified task population and may be affected by selection bias. Please provide paired significance tests (ideally paired by seed across replications) or confidence intervals, per-task results with standard errors, and a clear pre-registered or prespecified definition of the task-selection rule.","section":"§6, Table 2"},{"comment":"The paper never reports the prior hyperparameters required by the model: the prior mean θ_0, prior covariance Σ_0, the Gamma shape and rate parameters a and b, the covariance Σ_Θ, or the quantization size J used in equation (16). These quantities directly determine the posterior updates (4)-(7) and the KG selection decisions (17)-(19). Without them the experiments are not reproducible, and the sensitivity of the reported improvements to prior specification is unknown. Please report the exact values used and add a brief sensitivity analysis over reasonable variations.","section":"§3.3 and §5.2"},{"comment":"Equation (1) assumes that the logit of validation accuracy is an exactly linear, homoskedastic function of one-hot-encoded prompt features: η_x = Θ^T x + ε. All Bayesian updates and the KG policy inherit this assumption, yet the paper gives no validation of it. Nonlinear effects and feature interactions are not modeled, and no diagnostics are provided. Please add a robustness check, such as posterior predictive checks on held-out validation scores or a comparison against a model with pairwise feature interactions, to show that the qualitative conclusions do not depend on the linearity and homoskedasticity assumptions.","section":"§3.2, Eq. (1)"}],"minor_comments":[{"comment":"In equation (4), the numerator uses x_t while the rest of the update uses x_n; the index should be made consistent (presumably x_n throughout).","section":"§3.3, Eq. (4)"},{"comment":"The Update call is written as Update(S, logit(x)), but the argument should be the observed score logit(u_x), not the representation x.","section":"Algorithm 1, line 11"},{"comment":"There are typos: 'quanitity' in equation (13), and the expression in equation (16) appears as 'JX_{j=1}' where a summation symbol is intended.","section":"§4, Eqs. (13) and (16)"},{"comment":"The definition of the 13 'challenging' tasks mentions validation scores below 80% and 'relatively large variance', but the exact variance threshold is not stated and the task names are not listed. Please include the task list and threshold in an appendix.","section":"§6"},{"comment":"The row labeled 'Standard deviation' is the average of within-task standard deviations across replications; this does not equal the standard error of the reported mean and is not appropriate for comparing methods. Please report standard errors of the mean or confidence intervals.","section":"Table 2"},{"comment":"The 'Improvement of SOPL-KG per task' row is not defined. State whether it is the mean of per-task relative improvements or the relative improvement of the aggregate mean, and include the formula.","section":"Table 2"}],"recommendation":"major_revision","confidential_remarks":"The paper's heavy reliance on the authors' own prior work [24] for the KG computation is not circular, but the manuscript should more clearly delineate what is new relative to [24] in the prompt-engineering setting. The lack of any significance testing is the most serious empirical gap and should be addressed before publication. No concerns about the citation pattern beyond that."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper wraps a known optimal-learning method around prompt engineering and gets consistent, modest gains on a public benchmark. The framework (SOPL) represents prompts as one-hot feature vectors, models the logit of validation accuracy as a linear Gaussian process, and uses the Knowledge-Gradient policy to decide which prompt to evaluate next under a budget of 30 LLM calls. The genuinely new part is the packaging: a feature-based, constraint-defined prompt space that goes beyond enumerating candidates, plus the demonstration that KG beats heuristics like Greedy and Thompson sampling in this setting. The mathematical machinery, including the mixed-integer SOCP reformulation, is taken directly from Moazeni et al. (2020) and the authors cite it honestly. That is reuse, not circularity.\n\nThe experiments are decent for a first pass: 20 replications per task, comparison against EvoPrompt and TRIPLE, sensitivity checks for N=30/20/10, early stopping, and a feature ablation. The observation that KG's advantage grows with response variability across tasks (correlation with coefficient of variation around 0.89) is genuinely interesting and provides some internal validity.\n\nThe soft spots are statistical and reproducibility-related. The abstract and intro repeatedly say \"significantly outperforms,\" but there are no significance tests, no confidence intervals, and no per-task differences reported. The average gaps over EvoPrompt and TRIPLE are 0.033–0.067, while the average within-task standard deviation is 0.067–0.097, so seed noise could plausibly explain part or all of the headline difference. The post-hoc selection of 13 \"challenging\" tasks from the 24 available further weakens the claim, since the comparison is not over a pre-specified task population. Prior hyperparameters (θ0, Σ0, a, b, ΣΘ, quantization size) are not reported, which makes replication harder. The linear-Gaussian model is assumed without diagnostics, and the intro's claim about \"capturing various interactions among prompt attributes\" is overstated—the model is additive in main effects only.\n\nThese are fixable issues, not fatal flaws. The framework is transparent, the direction of the effect is consistent across tasks, and the paper gives a useful baseline for anyone working on black-box prompt optimization with expensive evaluations. I would send it to peer review and ask for paired significance tests or bootstrap intervals, a table of priors, and a modest rewrite of the \"interactions\" and \"significant\" claims. With those changes, this becomes a solid reference.","headline":"A sensible transfer of Knowledge-Gradient optimal learning to budget-limited prompt search, but the headline claim of 'significant' gains lacks statistical support.","tokens_in":13501,"tokens_out":2780,"would_cite":true,"duration_ms":27640,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A sequential Bayesian policy, the Knowledge-Gradient, finds strong LLM prompts within 30 evaluations and beats evolutionary and bandit baselines on instruction induction tasks.","keywords":["automated prompt engineering","Knowledge-Gradient policy","Bayesian regression","feature-based prompt representation","instruction induction","large language models","sequential optimal learning","limited evaluation budget"],"falsifier":"On the same 13 tasks and 30-evaluation budget, run SOPL-KG with pairwise feature interactions added to the linear model; if the KG advantage over Thompson sampling and greedy shrinks or reverses, the assumed feature-separability in equation (1) was load-bearing. A simpler companion check is to plot residuals of logit validation score against fitted values from equation (1) after the 30 evaluations: curvature or mean-dependent variance would show the linear-Gaussian model is misspecified.","tokens_in":12508,"feed_emoji":"🎯","tokens_out":13705,"duration_ms":110306,"temperature":0.7,"pith_summary":"The paper aims to establish that a forward-looking Bayesian decision policy, the Knowledge-Gradient, can find strong LLM prompts with very few evaluations by treating prompts as combinations of interpretable features and learning which combinations matter. On 13 instruction-induction tasks, with only 30 LLM evaluations, the KG-based workflow reports the highest average held-out score (0.6281) and the best average ranking among EvoPrompt, TRIPLE, greedy, and Thompson-sampling baselines. The authors argue this matters because prompt evaluation is often costly, and existing automated prompt engineering methods typically assume many iterations or require white-box access to the model. The feature-based representation broadens the search space and lets the policy exploit correlations among similar prompts instead of treating candidates independently.","feed_headline":"Forward-looking prompt search beats five baselines in 30 evaluations","feed_subtitle":"A Bayesian Knowledge-Gradient policy finds stronger LLM prompts than evolutionary and bandit methods on instruction tasks.","key_machinery":"The central object is the Knowledge-Gradient quantity, $\\nu_n^x = \\mathbb{E}[\\max_{y\\in\\mathcal{X}}(p_y^n + q_y^n(x)T_{2a_n}) \\mid S_n] - \\max_{y\\in\\mathcal{X}} p_y^n$, which measures how much one more evaluation of prompt $x$ is expected to raise the best predicted prompt score. The inner expectations are approximated by quantizing the Student-$t$ distribution $T_{2a_n}$, and the resulting optimization is solved as a mixed-integer second-order cone program. A normal-gamma Bayesian linear model with update equations (4)-(7) carries the correlations between similar prompts, so learning about one feature combination sharpens beliefs about others.","core_discovery":"The paper's central claim is that automated prompt engineering can be cast as a finite-horizon sequential optimal learning problem, and that the Knowledge-Gradient policy solves it well under a tight evaluation budget. Given a feature-based description of prompts, the paper models the logit of validation accuracy as a Bayesian linear regression, $\\eta_x = \\Theta^\\top x + \\varepsilon$, and at each step chooses the prompt that maximizes the expected improvement in the best predicted score after one more evaluation. On 13 instruction-induction tasks with 30 LLM evaluations, this policy attains the highest average test score (0.6281) and best average ranking (1.85) among EvoPrompt, TRIPLE, Thompson sampling, and greedy, with the largest margins on tasks where prompt performance is most variable. The authors take this as evidence that forward-looking, correlation-aware search can find strong prompts where evaluation is costly and exhaustive search is infeasible.","pith_inferences":["Editorial inference: the same constrained-feature formulation could carry over to other black-box optimization problems with expensive evaluations, such as choosing demonstration sets for retrieval-augmented generation or wording for safety guardrails; the paper does not test these settings.","Editorial inference: the reported correlation between score variability and KG's advantage suggests a practical adaptive policy—estimate the score landscape's variance in a short warm-up and then choose between KG and a cheaper exploitation policy—though the paper stops short of proposing such a rule.","Editorial inference: because the KG decision is computed via mixed-integer conic optimization, it can naturally enforce logical constraints on prompts (for example, mutually exclusive features or content-policy restrictions), which text-editing and embedding-space methods cannot easily express; a direct test would be to impose such constraints in the instruction-induction setup."],"forward_implications":["With a budget of 30 evaluations, the Knowledge-Gradient policy achieves the highest average test score (0.6281) and best average ranking (1.85) across the 13 instruction-induction tasks, compared with EvoPrompt, TRIPLE, Thompson sampling, and greedy.","The KG advantage holds when the budget is cut to 20 or 10 evaluations, and early stopping with a patience of 10 realizes about 17 evaluations with only a modest drop in test score.","On tasks where LLM responses are highly variable across prompt features, KG's relative improvement over Thompson sampling and greedy exceeds 10%, while on flatter, easier tasks a greedy policy is nearly as good.","Searching over multiple prompt features simultaneously—template, demonstration examples, roles, paraphrasing, and description—substantially outperforms searching over demonstration examples alone."],"supporting_citations":[{"why":"Defines the Knowledge-Gradient policy for correlated normal beliefs, the paper's core prompt-selection rule.","marker":"[9]"},{"why":"Establishes consistency of sequential Bayesian sampling policies, justifying the KG policy's convergence properties.","marker":"[10]"},{"why":"Extends KG computation and consistency to constraint-based, non-enumerable search spaces and combinatorial feature selection.","marker":"[14]"},{"why":"Supplies the mixed-integer second-order cone reformulation (Propositions 6 and 7) used to compute the KG decision efficiently.","marker":"[24]"},{"why":"Provides the 24-task instruction induction benchmark, the meta prompt template, and the task-specific metrics.","marker":"[15]"},{"why":"Provides the EvoPrompt evolutionary algorithm baseline that SOPL-KG is compared against.","marker":"[12]"},{"why":"Provides the TRIPLE bandit-based best-arm-identification baseline under a fixed evaluation budget.","marker":"[33]"},{"why":"Source of the instruction-generation meta-prompt procedure and the generation-then-selection baseline.","marker":"[39]"},{"why":"Textbook foundation for optimal learning and the KG policy family used to frame the problem.","marker":"[26]"}],"fun_headline_variants":["Knowledge-Gradient policy beats five prompt baselines","Bayesian prompt search wins with 30 evaluations","Sequential optimal learning for prompt engineering","Forward-looking KG policy excels at prompt search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a prompt's value to the LLM, after a logit transform, is a straight-line sum of its feature indicators plus random noise with constant spread; if real prompt performance has strong interactions or uneven noise, the Bayesian beliefs and the Knowledge-Gradient selections built on them rest on a misspecified model.","fun_headline_variants_meta":{"raw":{"variants":["Knowledge-Gradient policy beats five prompt baselines","Bayesian prompt search wins with 30 evaluations","Sequential optimal learning for prompt engineering","Forward-looking KG policy excels at prompt search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000263,"raw_usage":{"total_tokens":1591,"prompt_tokens":929,"completion_tokens":662,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":545,"completion_tokens_details":{"reasoning_tokens":606}},"tokens_in":545,"tokens_out":662,"duration_ms":6331,"temperature":1.0,"reasoning_tokens":606,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:52:09.556186+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On the same 13 tasks and 30-evaluation budget, run SOPL-KG with pairwise feature interactions added to the linear model; if the KG advantage over Thompson sampling and greedy shrinks or reverses, the assumed feature-separability in equation (1) was load-bearing. A simpler companion check is to plot residuals of logit validation score against fitted values from equation (1) after the 30 evaluations: curvature or mean-dependent variance would show the linear-Gaussian model is misspecified.","supporting_citations":[{"cited_title":"The knowledge-gradient policy for correlated normal be- liefs","cited_arxiv_id":null,"evidence_quote":"Defines the Knowledge-Gradient policy for correlated normal beliefs, the paper's core prompt-selection rule."},{"cited_title":"Consistency of sequential bayesian sampling policies","cited_arxiv_id":null,"evidence_quote":"Establishes consistency of sequential Bayesian sampling policies, justifying the KG policy's convergence properties."},{"cited_title":"Op- timal learning in linear regression with combinatorial feature selection","cited_arxiv_id":null,"evidence_quote":"Extends KG computation and consistency to constraint-based, non-enumerable search spaces and combinatorial feature selection."},{"cited_title":"Sequential learning in designing marketing campaigns for market entry","cited_arxiv_id":null,"evidence_quote":"Supplies the mixed-integer second-order cone reformulation (Propositions 6 and 7) used to compute the KG decision efficiently."},{"cited_title":"Connecting large language models with evolu- tionary algorithms yields powerful prompt optimizers","cited_arxiv_id":null,"evidence_quote":"Provides the EvoPrompt evolutionary algorithm baseline that SOPL-KG is compared against."},{"cited_title":"Large language models are human-level prompt engi- neers","cited_arxiv_id":null,"evidence_quote":"Source of the instruction-generation meta-prompt procedure and the generation-then-selection baseline."},{"cited_title":"Optimal learning, volume 841","cited_arxiv_id":null,"evidence_quote":"Textbook foundation for optimal learning and the KG policy family used to frame the problem."}],"review_version":1}