acceptodds
Under review as a conference paper at ICLR 2027

Selective Certification for Safe Upgrade Planning

Abstract

An upgrade planner should spend evaluation on plausible routes, distinguish a rejected candidate from a certified obstruction, and justify any reuse of evidence. We instantiate explore–verify in a known finite graph whose edits share unknown gain signs. The algorithm screens only labels on optimistic candidate routes, then certifies either a useful positive route or a negative blocking set. It stops with finite expected cost on every sign assignment, including infeasible ones, and attains the minimum positive-route information cost on each fixed feasible instance. Its screening cost depends on labels reached by correct optimistic search. A checkpoint contract extends the same procedure to irreversible diagnostic access. A separate packet rule permits adaptive route selection after partially validated sharing, with an explicit combined safety budget. Experiments include 160 random mixed-sign graphs, irrelevant-route and ordering controls, checkpointed deployment, and solver-certified optima on larger graphs. Selective screening removes large all-label overhead, but simpler testing often wins at moderate confidence; an optional rule retains that baseline. A code study that charges all work and matches candidate order reduces executions by 22.1% while taking longer on these cheap programs. These guarantees apply to checked upgrades, not general autonomous self-improvement.

Primary area:
transfer learning, meta learning, and lifelong learning
Keywords:
safe upgrade planning, sequential testing, selective certification, graph search, reusable evidence

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 2 reviews, above 9% of the others.
Reviewer_9BbLOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies safe upgrade planning on a known graph whose edits share unknown gain signs. Its algorithm screens labels on promising routes and then collects fresh evidence to certify either a positive route or a negative blocking set. It gives a route-local exploration cost and an asymptotically optimal leading verification cost on feasible instances, together with finite expected termination on infeasible instances. Checkpoint access and validation packets extend the safety contract. Experiments examine graph search, statistical testing, and controlled code-verification tasks.

Critical strengths
  1. The treatment of infeasibility is useful. A failed cheap screen does not permanently remove a useful route, and a budget interruption is distinguished from a verified obstruction. Theorem 1 and Appendix B connect these algorithmic choices to termination and error control.
  2. The experimental accounting makes the trade-offs inspectable. The random-graph comparisons charge failed attempts, the ordering controls test the constructed advantage, and the code comparison holds returned edits and gain fixed. These choices help identify when selective screening pays for itself.
Critical weaknesses
  1. The additional conceptual contribution is relatively narrow. The explore–verify/restart architecture and the separation between exploration and high-confidence verification already appear in Karnin (2016), as the paper acknowledges in Section 3 and Appendix I. The actual additions here are the route-local screening coefficient, a checked obstruction, and carefully specified access and sharing interfaces.
  2. The practical evidence does not substantially strengthen that contribution case. Cheap rejection uses fewer queries than Selective at all four confidence levels on the feasible random graphs in Table 1. In the checkpoint experiment, Selective also costs more than symmetric testing (110.75 versus 96.68 queries, p. 8). The code fixture saves 22.1% of executions but takes 2.98 ms rather than 2.46 ms (Table 4).
Questions for authors

Can the existing experiments identify an observable property of a graph or upgrade workload that predicts when selective screening will beat cheap rejection?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 9BbL

Thank you for the careful review, and for finding our treatment of infeasibility useful and our experimental accounting inspectable.

W1: the added contribution is narrow. We agree that the explore–verify split, its restarts and the log⁡log⁡(1/δ)\log\log(1/\delta) term come from Karnin (2016), and that our leading-constant optimality is a special case of multiple-answer identification (Degenne & Koolen, 2019). Section 1 now has a paragraph stating what the combination adds (p. 2), and Appendix L.3 compares the designs in a table (p. 44).

  • Testing one label at a time to deployment confidence can have a larger leading constant (queries divided by log⁡(1/δ)\log(1/\delta) as δ\delta goes to zero) than route screening, which first screens a candidate route's labels (Proposition 17). Cheap rejection does this, as in lazy shortest-path search (Dellin & Srinivasa, 2016), so its leading constant is at least the optimal cost Cθ(u)C_\theta(u) plus its excess certification WθW_\theta, the cost of the labels it certifies beyond the cheapest useful route. On our random graphs, WθW_\theta averages 2.6% of Cθ(u)C_\theta(u).
  • An explorer that screens every label also attains the optimal constant but pays a screen on each. With 20 irrelevant alternatives at δ=10−16\delta=10^{-16}, it uses 31.04 queries per unit of log⁡(1/δ)\log(1/\delta), against 4.18 for route screening.
  • Continuation (Proposition 16) limits the lower-order screening cost to labels on routes that the search abandons when every screen is correct. This is an upper bound, and we prove no matching lower bound.

W2: the practical evidence. Your three examples were accurate for the submitted algorithm, and much of the gap came from the double payment that continuation removes (General response, item 1).

  • On the 120 graphs of Table 1, which all have a useful route, Sel.-C (our method with continuation) still costs 4.7% more than cheap rejection at δ=0.05\delta=0.05 (95% confidence interval [2.3, 7.7]) and 2.5% more at 10−410^{-4} ([0.7, 4.7]). The two are statistically tied at smaller δ\delta, so your example largely stands for these graphs.
  • In the checkpoint experiment at δ=10−8\delta=10^{-8}, Sel.-C uses 84.81 queries, against 96.68 for symmetric testing and 110.75 for the submitted policy (Section 5.2, Table 14). Symmetric testing still uses fewer queries at δ=0.05\delta=0.05 (33.44 against 34.16) and retains more gain at every δ\delta under a 20-query budget.
  • In the code study, our method is still slower as submitted, because each execution takes under a microsecond. With an added busy-wait of 1 µs per execution, it is 4.5% faster (Section 5.4, Table 15). Proofs get no busy-wait and may cost more, or be unavailable, for expensive real programs, so this run only locates the break-even point.

Q1: an observable property that predicts the winner. In our runs, no per-graph property observable before a run predicted the winner, and Section 5.1 now says so (p. 8). Our cost model predicts each policy's cost from a graph's true signs. With those signs replaced by random draws at the generator's 35% negative rate, its correlation with the observed difference between Sel.-C and cheap rejection on graphs with a useful route is at most 0.21 (Appendix L.4). At the workload level, two quantities matter: δ\delta and the share of instances with no useful route.

  • In the new grid (General response, item 3), the number of such instances per setting rises from 0–1 to 9–14 out of 40 as qq rises from 0.1 to 0.5, and Sel.-C loses narrowly at 10−410^{-4} in the three settings with at most one.
  • In the same grid at 10−810^{-8}, Sel.-C is 22–33% below the best baseline on these instances, though both ends come from settings with only one of them. On instances with a useful route, it stays within 5.1% of cheap rejection at every δ\delta.

The excess certification WθW_\theta explains the per-graph results only after the fact, because it uses the true signs (Table 12). On the 86 of 120 graphs with a useful route and Wθ=0W_\theta=0, Sel.-C was never cheaper than cheap rejection. On the other 34, it was cheaper on 6 at δ=0.05\delta=0.05 and on 21 at 10−1610^{-16}, so a positive WθW_\theta is necessary but not sufficient. About two thirds of WθW_\theta can be read from cheap rejection's logs after a run.

Presentation. We rewrote the abstract and introduction in plainer terms. Section 2 now defines δ\delta, δ\delta-safety, a positive route and screening (p. 2), and Section 3 defines the test notation and epochs before the algorithm (p. 3) and both baselines after it (p. 4). Sections 2–5 open by saying what they show. The caption of Table 1 names every policy, Table 2 uses the same columns, and the caption of Figure 2 states both axes and the leading-constant line. At its first mention in the main text, each new definition, proposition and table names its part of Appendix L.

Reviewer_M6s3OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to choose upgrades in a known graph when several edits share an unknown gain sign. It screens labels on promising routes, then separately verifies either a useful positive route or a set of negative labels that blocks every useful route. The main result gives finite expected stopping even when no useful route exists, while attaining the optimal leading query cost on feasible instances. Experiments test query costs, restricted diagnostic access, planning approximations, and source-based verification.

Critical strengths

I like that the method does not treat a cheap negative screen as proof of infeasibility. The separate obstruction check gives the algorithm a justified way to stop when no useful route exists.

I also appreciate the experiments honesty. The authors show that screening often loses to simpler testing and that fewer program executions do not necessarily mean lower runtime.

Critical weaknesses

My main concern is the paper's significance, given that they acknowledge that explore-verify and multiple-answer optimality come from earlier work. Optimistic path-based evaluation also has close precedents. I can see the additional route-local accounting, but I am not yet convinced that the resulting advance is substantial enough for acceptance. I would like a more precise explanation of what cannot already be obtained by specializing those existing methods.

Cheap rejection wins on every displayed random feasible condition, and the code experiment is slower overall. This would not be a reason to reject a strong theory paper on its own. Here, however, the theoretical advance is specialized, and the practical benefit remains conditional. Taken together, these leave me leaning toward rejection.

Questions for authors

Q1: What is the strongest result here that does not follow from an existing explore–verify method combined with a lazy, label-aware path planner? A precise comparison would help more than a broader related-work discussion.

Q2: What safety and completion requirements define the policies against which the optimality claim is made?

Q3: Do the existing results contain a non-contrived setting where selective screening beats cheap rejection after planning and validation costs are included? If so, please make that comparison explicit. I am not asking for a new large-scale agent benchmark.

4 comments
AuthorsOpenReview ↗

Response to Reviewer M6s3 (1/2): what does not follow from prior methods, and the policy class

Thank you for the review, and for valuing the separate obstruction check and the candor of our experiments.

Q1 and W1: the strongest result that does not follow. It is Proposition 17. A lazy planner that certifies one label at a time (depth-first), such as our cheap-rejection baseline, pays an extra leading cost of at least WθℓW_\theta\ell, where ℓ=log⁡(1/δ)\ell=\log(1/\delta) and WθW_\theta is the cost of the labels it certifies beyond the cheapest useful route. A second result is Proposition 16: continuing the statistic of our cheap, low-confidence screen into the deployment test removes the deployed route's labels from the lower-order term of our cost bound. Section 1 now states both (p. 2). Our leading-order optimality follows from prior work, and we do not claim it as new.

An explore–verify method combined with a lazy planner has two readings.

  • The first reading is Karnin's Algorithm 1 with our lazy route screening as the explorer, which is the submitted algorithm. Karnin's analysis verifies on new samples, so it charges a screen to every screened label, and continuation removes that charge for the deployed route.
  • The second reading is a lazy planner that tests its current route's labels one at a time to deployment confidence. This is lazy shortest-path search (Dellin & Srinivasa, 2016) with noisy edges, which our cheap-rejection baseline implements. With noisy repeated queries, each label certified beyond the cheapest useful route costs order ℓ\ell queries instead of one exact evaluation, which gives the WθℓW_\theta\ell term. Relative to the optimal cost Cθ(u)C_\theta(u), WθW_\theta is unbounded over constructed instances and averages 2.6% on our random graphs. A test order based on costs or a prior (Choudhury et al., 2018) could shrink WθW_\theta, but we did not run one.

Appendix L.3 now gives this comparison as a table (p. 44). The leading constant is the number of queries divided by ℓ\ell as δ\delta goes to zero.

DesignLeading constantScreening termNo useful route
Depth-first lazy testing (cheap rejection)at least Cθ(u)+WθC_\theta(u)+W_\thetanoneneeds a separate check
Explore–verify with an explorer that screens all labelsCθ(u)C_\theta(u)every labelanswer assumed to exist
Karnin's scheme with route screening (submitted algorithm)Cθ(u)C_\theta(u)screened labels, including the deployed routechecked blocking set, finite stopping
Route screening with continuation (Sel.-C)Cθ(u)C_\theta(u)labels on abandoned routes onlychecked blocking set, finite stopping

We compare lower-order terms only through upper bounds. Degenne and Koolen's answer sets can include "no", so a specialization of their method could be cheaper than our blocking-set check on instances with no useful route.

Q2: the policy class. The class contains every policy that is uniformly δ\delta-safe and δ\delta-complete on the true sign assignment θ\theta. Definition 15 now states it (Appendix L.1, p. 40), and Section 2 summarizes it (p. 2). A policy is uniformly δ\delta-safe if, under every sign assignment, it deploys a negative-gain edge with probability at most δ\delta. It is δ\delta-complete on θ\theta if, with probability at least 1−δ1-\delta under θ\theta, it deploys a route that ends in a terminal node and whose gain with all signs positive is at least uu. Every such policy satisfies EθN≥(1−2δ)Cθ(u)ℓ−(log⁡2)∑jcj\mathbb E_\theta N\ge(1-2\delta)C_\theta(u)\ell-(\log 2)\sum_j c_j, where NN is the number of queries and certifying label jj takes about cjℓc_j\ell queries. The proof uses safety only at θ\theta and at the assignments that flip one positive label of θ\theta, and completion only at θ\theta, so it also covers policies that never stop on infeasible inputs. Our algorithm meets a stronger requirement: under every sign assignment, it stops in finite expected time and, with probability at least 1−δ1-\delta, returns a correct route or a valid blocking set. Under local access, the same definitions give the access-constrained lower bound (9) of Appendix D.

AuthorsOpenReview ↗

Response to Reviewer M6s3 (2/2): practical benefit, and a comparison with all costs included

W2: cheap rejection wins, and the code study is slower. Both observations were correct for the submitted algorithm. On the random graphs, the main cause was the double payment that continuation removes (General response, item 1). On random graphs with a useful route, Sel.-C (our method with continuation) still costs 4.7% more than cheap rejection at δ=0.05\delta=0.05 and 2.5% more at 10−410^{-4}, and the two are statistically tied at 10−810^{-8} and 10−1610^{-16}. The code study is slower for a different reason: each execution takes under a microsecond. With an added busy-wait of 1 µs per execution, our method is 4.5% faster (Section 5.4).

Q3: a non-contrived setting with planning and validation costs included. With continuation, the full random suite gives one. Over all 160 graphs at δ≤10−4\delta\le10^{-4}, Sel.-C is cheaper in total than every baseline, planning included, once a query costs more than 0.08 ms, and Section 5.1 now states this comparison (p. 7). In the submitted results, the only such setting was the 40 graphs with no useful route, and no policy can tell in advance whether a graph is one of them. There, the submitted policy beat cheap rejection at every δ\delta, for example with 102.19 against 140.29 queries at 10−1610^{-16} (Table 2), but over all 160 graphs it cost more than cheap rejection at every δ\delta. Every query count includes screening, failed attempts, verification and checks that no useful route exists.

Most of the gain comes from instances with no useful route. In the new grid at 10−810^{-8}, Sel.-C is 22–33% below the best baseline on those instances, though both ends come from settings with only one of them. On instances with a useful route, it stays within 5.1% of cheap rejection at every δ\delta. For instances with no useful route, our theory guarantees finite stopping but claims no optimal constant. We have not measured how often real upgrade problems have no useful route, and in our generator this share is set by the negative-label share qq and the gain target.

Planning cost. Because our queries are simulated and free, measured wall-clock time is planning time. At 1 ms per query and δ=10−8\delta=10^{-8}, the total time per run over all 160 graphs is 47.46 ms for Sel.-C, 55.28 ms for cheap rejection and 56.33 ms for symmetric testing (Appendix L.4). On graphs with a useful route at δ≥10−8\delta\ge10^{-8}, though, Sel.-C never wins in total, whatever a query costs.

Thank you for the response and the additions in Appendix L. Definition 15 resolves my question on the policy class (Q2), and the comparison table in Appendix L.3 makes clear what is inherited from prior work versus newly shown here.

After reading the revised analysis and experiments, my main reservation about overall significance remains. Proposition 17 separates against fixed- and random-order depth-first baselines rather than general cost- or prior-aware edge-selection rules, and on the feasible random graphs Wθ=0W_\theta = 0 in 86/12086/120 cases (averaging 2.6%2.6\% of Cθ(u)C_\theta(u)). Proposition 16 cleanly removes the deployed route from the lower-order screening term via within-epoch continuation, though as an upper-bound refinement without a matching second-order lower bound. Empirically, even with continuation (Sel.-C), the method still slightly trails or ties cheap rejection on feasible random instances; the aggregate cost crossover at δ≤10−4\delta \le 10^{-4} relies primarily on infeasible instances under imputed per-query costs (>0.08 ms> 0.08\,\mathrm{ms}), and the code-study speedup requires an added synthetic delay (1 μs1\,\mu\mathrm{s}). While the revision improves clarity and soundness, the theoretical and practical advance still feels specialized, so I am keeping my score at 2.

AuthorsOpenReview ↗

Response to Reviewer M6s3 (follow-up)

Thank you for the close reading and for confirming that Definition 15 settles Q2.

We agree with the scope you describe. Proposition 17 compares only against depth-first testers with a fixed or random test order, and Appendix L.3 notes that a cost- or prior-aware order could reduce WθW_\theta. Our claim is that route screening reaches the optimal leading constant without such an order, because in Theorem 1 the order affects only the lower-order term. Proposition 16 is an upper bound, and Appendix L.2 states that we prove no matching second-order lower bound.

We also agree that the continuation variant (Sel.-C) ties or trails cheap rejection on feasible random graphs, and that Wθ=0W_\theta = 0 on 86 of these 120 graphs, where Proposition 17 gives no separation. The gains come from instances with Wθ>0W_\theta > 0 or with no useful route, and how common these are depends on the workload. Our extra planning pays for itself over all 160 graphs once a query costs more than 0.08 ms. Since a query stands for a trusted evaluation of an upgrade, we expect most real checks to cost more, although we have not measured this. Likewise, the 1 µs delay in the code study marks the break-even point for programs that run in under a microsecond.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response: what the revision changes

We thank both reviewers and the Area Chair for the additional review. All three asked what is new beyond explore–verify and correctly noted that simpler testing often wins in our tables. New material in the revised PDF is in Appendix L, and the changes to the main text are noted in each reply below.

1. Continuation removes a double payment. The submitted algorithm verified the chosen route on new observations, so each deployed label was paid for twice, once in a screen (our cheap, low-confidence test) and once in a full-confidence test. By Ville's maximal inequality, the full test can instead continue the screen's statistic within the same error budget. Theorem 1's guarantees still hold, and the lower-order screening cost no longer includes the deployed route's labels (Section 3, p. 4; Proposition 16 in Appendix L.2). Our reruns of this variant, Sel.-C, reuse the submitted seeds and observations but are post hoc, since we designed it after seeing the results.

2. Results. Over all 160 random graphs, Sel.-C is the cheapest policy at every error level δ≤10−4\delta\le10^{-4} (Table 11, mean queries per run). Cheap rejection needs full confidence only to accept a label, symmetric testing needs it both ways, and Cheap-C is cheap rejection with continuation.

δ\deltaSel.-CCheap rejectionCheap-CSymmetric testing
10−410^{-4}30.6335.3431.8633.22
10−810^{-8}46.3054.1650.3455.36
10−1610^{-16}77.4891.5587.5599.96

Most of the gain comes from the 40 graphs with no useful route. At δ=0.05\delta=0.05, symmetric testing is cheapest (18.12 queries against 19.24 for Sel.-C), and on graphs with a useful route, cheap rejection remains cheaper at moderate δ\delta.

3. New seeds. A new grid of eight settings with fresh seeds varies the share qq of negative labels and the graph depth (Table 13). At δ≤10−8\delta\le10^{-8}, Sel.-C beats the best baseline in all eight settings, by under 3% at q=0.1q=0.1 and by 10–15% at q=0.5q=0.5, while at 10−410^{-4} it loses by at most 0.9% in three settings.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.