{"id":"e3915fca-b484-4da2-9a2e-1832805df246","arxiv_id":"2603.01470","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Randomized kriging believer parallelizes any base Bayesian optimization acquisition function and attains Bayesian cumulative and simple regret bounds, the latter independent of batch size.","lead":"This paper introduces 'randomized kriging believer' (RKB), a cheap and simple way to run Bayesian optimization in parallel by injecting random 'fake' observations for evaluations still in progress. It comes with Bayesian regret bounds, including a simple-regret bound that does not get worse as more parallel workers are added.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma B.1's proof contains an invalid equality (Eq. 11f) that all main theorems rely on; the BSR bound is not rigorously established as written.","rationale":"I read the paper as a serious attempt to give a greedy, diversity-encouraging PBO method with theoretical guarantees. The central claim is Theorem 4.3: BSR_T ≤ B_T/T with B_T = O~(√(Tγ_T)), independent of the number of parallel workers Q. For this claim to hold, Lemma B.1 must be valid, since it bounds E[Σ(g*_t − g_t(x_t))] and appears in the proof of every main theorem. I found a concrete flaw in the proof of Lemma B.1: Eq. (11f) asserts an equality between posterior variances under D^RKB and D_{t-1} that is not true pointwise. Distributional equivalence of these datasets does not permit replacing only the variance term inside an expectation that also depends on u_t and x_t; the proper argument is to replace the whole expectation via the coupling, then invoke Lemma A.1. The result likely survives this repair, but as written the proof is incomplete. This is more load-bearing than the BSR definitional mismatch highlighted by the reader, which is a practical presentation issue (the algorithm should state that the final recommendation uses D_T after waiting for pending evaluations). Both concerns justify a conditional verdict: the authors must fix the proof gap and clarify the stopping rule. I remain optimistic that the theorem is true, but it is not yet rigorously established.","tokens_in":24887,"tokens_out":23252,"duration_ms":208818,"concrete_test":"Analytically re-derive Lemma B.1 from Appendix B without using Eq. (11f): replace the inequality with E[Σ u_t(D^RKB_{t-1}) σ(x_t;D^RKB_{t-1})] = E[Σ u_t(D_{t-1}) σ(A(D_{t-1});D_{t-1})] by the distributional equality of D^RKB and D_{t-1}, then apply Lemma A.1 to the D_{t-1} sequence. If this yields B_T, the proof is repairable; if it yields a different (e.g., Q-dependent) bound, the BSR independence claim fails.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma B.1, used by Theorems 4.1–4.3, is not proved correctly. In Appendix B, the transition from Eq. (11e) to Eq. (11f) replaces σ(x_t; D^RKB_{t-1}) with σ(x_t; D_{t-1}) inside an expectation while keeping u_t(D^RKB_{t-1}) and x_t = A(D^RKB_{t-1}). The paper justifies this by 'σ(x_t; D^RKB_{t-1}) = σ(x_t; D_{t-1})', which is pointwise false: D^RKB contains posterior-sample fantasized pending observations, whereas D_{t-1} contains the real (unobserved at time t) pending observations. Distributional equality of D^RKB and D_{t-1} does not allow replacing only the variance factor; it would require changing the whole expectation to the D_{t-1} process. A rigorous proof can likely be obtained by noting E[Σ u_t(D^RKB) σ(x_t;D^RKB)] = E[Σ u_t(D_{t-1}) σ(A(D_{t-1});D_{t-1})] and applying Lemma A.1, but as written the key step is invalid. Since Lemma B.1 underpins the BSR bound (Theorem 4.3) and the BCR bounds, the central claim is not rigorously established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes randomized kriging believer (RKB), a parallel Bayesian optimization wrapper that imputes each pending evaluation by a single posterior draw plus observation noise. It inherits the low computational cost, simplicity, and asynchronous applicability of the standard KB heuristic. Under a conditional regret condition (Condition 4.1) on the base acquisition function, the paper proves Bayesian cumulative regret bounds for finite and continuous input domains (Theorems 4.1 and 4.2) and a Bayesian simple regret bound (Theorem 4.3) that is independent of the number of parallel workers Q. The method is evaluated on synthetic functions, standard benchmarks, and real-data emulators.","tokens_in":25218,"tokens_out":26489,"duration_ms":244457,"significance":"The contribution is significant if the theorems hold: RKB is a simple, greedy parallelization wrapper that achieves the same Q-independent Bayesian simple regret rate as PTS and DPP-TS, while avoiding their computational overhead. The proof strategy is transparent and largely sound: the distributional equivalence between D^RKB and D_{t-1} is used cleanly, and Condition 4.1 is verified for a reasonable family of base algorithms by reference to published proofs. I specifically considered the stress-test objection to Lemma B.1 and find that it does not land: Eq. (11f) is valid because GP posterior variance depends on the data only through the input locations, and D^RKB and D_{t-1} share the same input locations. The remaining issue is a local formal inconsistency in the proof of Theorem 4.3, which is readily repairable and does not undermine the central claim.","major_comments":[{"comment":"The proof writes BSR_t = E[f* - f(A(D_{t-1})) + f(A(D_{t-1})) - f(hat x_t)] and then bounds the first term. But under the theorem's hypothesis x_t = A(D^RKB_{t-1}), not A(D_{t-1}); these are different processes, so the displayed equality is not the RKB process. The chain can be repaired by replacing A(D_{t-1}) with A(D^RKB_{t-1}) in lines 2-5 of Eq. (43), and then using the joint distributional identity (f, D^RKB_{t-1}) = (g_t, D^RKB_{t-1}) conditional on D_{N_{t-1}} and the query history, which is exactly what lines 7-8 already invoke. Please correct the proof and add a brief justification for that replacement; this is a load-bearing proof step and should not be left in the present form.","section":"Appendix D, proof of Theorem 4.3, Eq. (43)"}],"minor_comments":[{"comment":"The BSR guarantee is stated for hat x_T = argmax_x mu(x; D_T), i.e., after all T evaluations are available. In an asynchronous run, at the moment the T-th query is dispatched only D_{N_T} is available. The theorem is correct, but the paper should explicitly state the stopping protocol: stop querying, wait for pending evaluations to complete, and then make the final recommendation. Without this sentence, the Q-independent BSR statement can be misread.","section":"Section 2.5 / Theorem 4.3"},{"comment":"The equality sigma(x_t; D^RKB) = sigma(x_t; D_{t-1}) is true, but the proof's one-line justification is terse. The reason is that GP posterior variance is independent of the observed y-values and depends only on the input locations, which are identical in D^RKB and D_{t-1}. Please state this explicitly to avoid the impression that distributional equality alone justifies the replacement.","section":"Appendix B, Lemma B.1, Eq. (11f)"},{"comment":"The claim that the worst-case variance ratio is achieved when all Q pending points coincide with x is asserted rather than proved. Since the lemma is cited from prior work, please add an explicit reference or a short argument for this step.","section":"Appendix B, Lemma B.2"},{"comment":"Typographical errors: 'theretical' should be 'theoretical' in Section 5.1; 'Acknowkedgements' should be 'Acknowledgements' in Section 6.","section":"Sections 5.1 and 6"}],"recommendation":"minor_revision","confidential_remarks":"To the editor: the stress-test concern about Lemma B.1 is unfounded; the claimed invalid step is actually valid once one notes that posterior variance is y-independent. The only substantive issue I found is a formal inconsistency in the proof of Theorem 4.3, but it is local and clearly repairable. I see no scope or disclosure concerns; Condition 4.1 relies in part on the authors' previous results, but those are published and independently checkable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper earns its keep. RKB—hallucinate a single posterior sample at the pending points instead of KB's mean—is a small algorithmic change that makes the old kriging believer heuristic analyzable. The main theorems give Bayesian cumulative regret bounds with a mild Q penalty and a Bayesian simple regret bound that is independent of Q, which is the first time a greedy, diversity-promoting PBO method gets that rate. The distributional equivalence (fantasy data and real pending data share the same law) is the load-bearing trick, and it is used honestly.\n\nThe proofs are mostly in good shape. Condition 4.1 is a fair black-box condition on the base algorithm, and the paper verifies it for UCB, randomized UCB, PIMS, EIMS, and TS by pointing to existing analyses. The variance-decay lemma and the discretization argument for continuous domains are standard and correctly applied. The experiments are broad (synthetic GP, four benchmarks, nine Olympus emulators) and the results are honestly presented: RKB is competitive with KB and LP, and beats PTS on several problems. The paper does not oversell itself.\n\nI disagree with the stress-test's cited gap in Lemma B.1. The step from (11e) to (11f) replaces σ(x_t;D^RKB) with σ(x_t;D_{t-1}). The note says this is false because the datasets differ in the pending values. But GP posterior variance does not depend on observed values at all—only on the input locations. D^RKB and D_{t-1} share exactly the same input set, so the variance functions are pointwise identical. The step is correct, and no distributional substitution is needed. Whoever wrote that note skipped over the basic fact that the predictive variance is y-free.\n\nThe real caveat is one the reviewer (and reader) flagged: Theorem 4.3's final recommendation is argmax of the posterior mean given D_T, i.e., it assumes all T evaluations are completed. In an asynchronous run with Q pending jobs, you need to wait for the last batch before you can compute that point. That is a reasonable convention—nobody recommends before the budget returns—but the paper should say so in the theorem statement. As written, it invites the misinterpretation that the bound applies at the stopping instant. The authors should also release code; the method's main selling point is how easy it is to implement, and a reference implementation would close the deal.\n\nBottom line: worth a serious referee. I'd accept it into the review process without hesitation, ask for the BSR clarification and code, and let it through.","headline":"Simple, well-analyzed parallel BO wrapper; the alleged Lemma B.1 gap is not a gap (posterior variance is y-independent), but the BSR theorem's timing convention needs a footnote.","tokens_in":25658,"tokens_out":12989,"would_cite":true,"duration_ms":118628,"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":"The paper proposes randomized kriging believer (RKB), a parallel Bayesian optimization method that imputes one posterior sample at each pending evaluation, and proves Bayesian cumulative and simple regret bounds—including a simple regret bo","keywords":["parallel Bayesian optimization","kriging believer","posterior sampling","regret bounds","Gaussian processes","batch optimization","hallucinated observations","simple regret"],"falsifier":"Run RKB with Q=7 workers on a GP sample from the paper's setup, record the simple regret of the recommendation computed at iteration T using only the observed data D_{N_T} (i.e., exclude the ongoing evaluations), and compare it with the claimed B_T/T bound. If for a range of T the observed-data recommendation's regret consistently violates the bound while the full-data recommendation satisfies it, the Q-independent guarantee does not apply to the practical output of the algorithm.","tokens_in":24747,"feed_emoji":"🎯","tokens_out":6367,"duration_ms":58247,"temperature":0.7,"pith_summary":"Parallel Bayesian optimization usually trades a theoretical guarantee against simple implementation: heuristic batch methods like kriging believer work well but lack regret bounds, while principled batch methods are complex or over-explore. This paper tries to get both by randomizing the kriging believer heuristic: instead of filling in pending evaluations with posterior means, it fills them with one draw from the posterior predictive distribution. Because a posterior draw is exactly what the true function would look like given the observed data, the algorithm's distributional structure matches that of sequential Bayesian optimization, which lets the authors prove Bayesian expected regret bounds for any base acquisition function satisfying a mild one-step condition. The headline result is that the Bayesian simple regret bound does not depend on the number of parallel workers, matching the guarantee of far more complex sampling-based batch methods. If correct, this gives a cheap, general-purpose parallelization wrapper with a solid theoretical grounding.","feed_headline":"Parallel BO method gets batch-size-free simple regret","feed_subtitle":"Switching the fantasized value from posterior mean to posterior sample removes the batch-size penalty from simple regret.","key_machinery":"The distributional identity between a full dataset and the fantasized dataset. RKB constructs D^{RKB}_{t-1} by using a posterior sample g_t ~ p(f|D_{N_{t-1}}) plus Gaussian noise in place of the pending observations. Conditioned on the observed data, this fantasized dataset has exactly the same conditional distribution as a real dataset would have, which allows the regret analysis to transfer bounds from the sequential setting. The proof decomposes the cumulative regret into A1 (regret on the sampled path, bounded like sequential BO) and A2 (discrepancy between the sample path and the true objective, bounded via the ratio of posterior variances and a maximum-of-Gaussian argument). For simple","core_discovery":"The central claim is that randomized kriging believer (RKB) achieves Bayesian expected regret guarantees with a bound on simple regret that is independent of the parallel batch size Q. The key move is replacing the deterministic posterior-mean imputation of classic kriging believer with a single posterior sample plus noise at each as-yet-unobserved point. Conditioned on the observed data, the fantasized dataset has the same distribution as a real full dataset, so the regret of the parallel algorithm can be decomposed into a sequential-regret term (bounded by existing theory) and a cross-term measuring the gap between the sample path and the true function. For cumulative regret the bound carr","pith_inferences":["The Q-independent simple regret bound relies on a definition of the final recommendation that uses the full dataset including pending evaluations; a practically computable recommendation at time T would only use observed data, and the proof does not obviously transfer to that output. A separate analysis—or a different stopping rule—would be needed to guarantee the same rate for the algorithm a use","The decomposition that powers the proof suggests a general recipe: any sequential Bayesian optimization method whose one-step regret can be bounded by posterior standard deviation plus a small bias term can be parallelized by posterior-sample imputation. This may extend beyond the listed base algorithms to other acquisition functions or to non-Gaussian surrogate models.","The experimental protocol compares against KB and LP on equal footing; a sharper test would be to compare the practically achievable simple regret (using only observed data) against the theoretical BSR_T bound, and to measure the gap as Q grows.","Because RKB uses a single posterior sample per pending point, its batch diversity is controlled by the posterior spread; one can imagine a tunable version that draws samples with a tempered posterior to adjust the exploration-exploitation balance, which the current analysis does not cover."],"forward_implications":["If RKB's bound holds, users can run a generic Bayesian optimization loop with up to Q pending evaluations and retain the same asymptotic simple regret as sequential BO, without special-purpose batch acquisition functions.","Since RKB only changes how pending points are filled in, it can wrap any acquisition function that satisfies Condition 4.1 — including UCB, randomized UCB, PIMS, and EIMS — and works in asynchronous settings with no extra cost.","The guaranteed rate B_T/T for simple regret matches the best existing parallel methods (PTS and DPP-TS) at far lower computational complexity, making theoretically justified parallelization practical at moderate batch sizes.","The Q-independent simple-regret bound suggests that wall-clock speedup from parallelism need not be bought with statistical efficiency, at least asymptotically."],"fun_headline_variants":["Randomized imputation removes batch-size penalty in parallel BO","Batch-size-free regret achieved by sampling in kriging believer","Sample-based fantasy beats mean in parallel Bayesian optimization","Parallel BO regret bound now independent of batch size","Kriging believer with posterior samples yields tighter regret"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The simple regret guarantee applies to a recommendation chosen with the full dataset including evaluations that are still pending; in a real parallel run the user only has the observed subset at time T, and the paper's proof does not bound the regret of that practically available recommendation.","fun_headline_variants_meta":{"raw":{"variants":["Randomized imputation removes batch-size penalty in parallel BO","Batch-size-free regret achieved by sampling in kriging believer","Sample-based fantasy beats mean in parallel Bayesian optimization","Parallel BO regret bound now independent of batch size","Kriging believer with posterior samples yields tighter regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000526,"raw_usage":{"total_tokens":2334,"prompt_tokens":660,"completion_tokens":1674,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":404,"completion_tokens_details":{"reasoning_tokens":1597}},"tokens_in":404,"tokens_out":1674,"duration_ms":10744,"temperature":1.0,"reasoning_tokens":1597,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T19:36:46.989522+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run RKB with Q=7 workers on a GP sample from the paper's setup, record the simple regret of the recommendation computed at iteration T using only the observed data D_{N_T} (i.e., exclude the ongoing evaluations), and compare it with the claimed B_T/T bound. If for a range of T the observed-data recommendation's regret consistently violates the bound while the full-data recommendation satisfies it, the Q-independent guarantee does not apply to the practical output of the algorithm.","supporting_citations":[],"review_version":1}