- 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
- 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.
- 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
- 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.
- 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?
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 loglog(1/δ) 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).
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).
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: δ and the share of instances with no useful route.
The excess certification Wθ 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θ=0, Sel.-C was never cheaper than cheap rejection. On the other 34, it was cheaper on 6 at δ=0.05 and on 21 at 10−16, so a positive Wθ is necessary but not sufficient. About two thirds of Wθ 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 δ, δ-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.