- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper addresses the pruning problem in LLM-guided tree search, where evaluator scores have systematic biases and pruning is irreversible. The authors propose PAC-CF: first performing a PAC analysis under a bounded-bias assumption, running the original controller on a calibration set to collect trajectories, calculating the "maximum score gap between valid branches and the highest score" using verifier labels, and taking the conformal quantile as the threshold. During deployment, candidates whose score gap from the highest score exceeds the threshold are pruned. Experiments are conducted on Game24, Blocksworld, and GTA, covering five controllers.
Critical strengths
-
It points out that "repeated scoring can reduce noise, but cannot eliminate systematic ranking errors," which is clearly demonstrated by the control experiments on TSP.
-
The method can be directly plugged into existing controllers without modifying their remaining logic.
Critical weaknesses
-
The theory and the method are disconnected. The PAC analysis in Section 4.1 is a standard best-arm identification with a bias term, and the authors themselves state that it "does not directly yield a deployment threshold." The actual method used simply applies split conformal quantiles to a scalar score gap, which is technically straightforward. The theoretical part feels more like packaging rather than supporting the actual algorithm.
-
The guarantee does not cover the system during actual deployment. Coverage only holds on the "trajectories of the original controller." Once PAC-CF pruning is applied, the search trajectory changes, and the guarantee no longer applies—a point acknowledged by the authors. Therefore, the paper's core selling point, "reliable pruning," lacks guarantees during actual execution and can only be evaluated empirically.
-
The gains are small and unstable. Macro-average accuracy improves by only about 1 point. When switching to Ministral as the evaluator, the accuracy change and Workload savings are relatively small. The gain and savings highlighted in the abstract and conclusion come solely from a single controller, ToolTree.
-
Lack of the simplest baseline. Using the same calibration data, one could directly tune a fixed score-gap threshold or tune the K value in top-K. Without this baseline, it is hard to determine what conformal calibration itself actually contributes.
Questions for authors
How do the results of PAC-CF compare to directly tuning a score-gap threshold or K value using the same calibration data (without conformal prediction)?
5 comments
Discussion Phase Ends in Less Than 24 Hours — We Welcome Reviewer DBpP's Feedback
Dear Reviewer DBpP,
As the author–reviewer discussion period ends in less than 24 hours, we would like to kindly remind you of our detailed rebuttal and the additional evidence included in the revised manuscript.
We have specifically addressed your concerns about the theory–algorithm connection, the reliability of pruning during actual deployment, the dependence of improvements on ToolTree, and comparisons with simpler pruning strategies.
In particular, we added an empirical audit of PAC-CF-induced trajectories, reported workload improvements excluding ToolTree, and included FixedGap and Top-K comparisons.
We would sincerely appreciate your feedback on whether these revisions resolve your principal concerns and whether they warrant reconsideration of your original assessment.
Thank you very much for your time and consideration.
Best regards,
Authors of Paper 14678
Thanks for your reply. W1-W3's results are from the paper. From W4, the results of PAC-CF still show limited advantages over the baselines. It doesn't address my main concern, so I will keep my score.
Response to Reviewer DBpP
We appreciate the critique of the theory–algorithm connection and the request for direct pruning controls. The revised paper more clearly links the protected event, calibrated rule, and deployed measurements.
W1 — Theory and method. The decision studied in Section 4.1 is irreversible deletion under persistent evaluator bias. The effective separation Δ−4L shows how bias can survive repeated scoring. In the TSP50 stress test, 16 scores per candidate leave the optimal continuation at mean rank 5.11 on conflict frontiers; fixed Top-4 removes it in 64.4% of those cases. Section 4.2 uses verifier-defined protected continuations to express this risk through observable score gaps. The maximum gap along each Native task trajectory is calibrated with a split-conformal rank to target simultaneous protected-continuation retention across exposed frontiers. This construction links the bias-aware decision problem to a deployable score-based admission rule. The fixed-frontier theorem supplies motivation and analysis; the rank calibration provides the task-level statistical statement.
W2 — Actual deployment. PAC-CF changes later frontiers and search-budget allocation. We explicitly scope the finite-sample result to exchangeable Native reference trajectories with protected exposure. We separately measure the adapted controller's closed-loop behavior. At B100, protected-path survival is 461/473 (97.46%) for Game24 and 494/495 (99.80%) for Blocksworld (Appendix G.2, Table 14). To probe the reviewer’s deployment concern more directly, a separate B500 audit inspects PAC-CF-induced trajectories: 47/50 Game24 tasks and 47/50 Blocksworld tasks (94/100 overall) show no recorded protected-continuation loss, while 17 local loss events are concentrated on six affected tasks, three of which still solve (Section 5.5; Appendix O, Table 29). This is empirical, trajectory-specific protection evidence, not an adaptive-trajectory coverage theorem; the separate B100 and B500 quantities should not be pooled.
W3 — Magnitude and ToolTree dependence. PAC-CF adds a pruning layer to five established search controllers over three domains and four budgets. Paired macro utility changes are +1.09/+0.81 points at B100/B200, with 95% intervals excluding zero. Across B100–B500, full-pair workload reductions are 6.14–9.47% requests, 9.03–12.40% Net Graph nodes and 6.84–10.25% tokens. Removing ToolTree still yields B500 savings of 7.54%, 12.72% and 7.72% on those measures. With Ministral-3-14B as evaluator, uncensored-pair requests/nodes/tokens decline by 6.22–7.86%/10.11–10.94%/6.80–9.20%, while utility changes range from +0.08 to −0.62 points. Domain-level uncertainty is now explicit: GTA has positive intervals across budgets, Blocksworld at B100/B200, and Game24 negative intervals at B300/B500. These results establish broadly observed workload savings with heterogeneous utility effects. FETCH's 0.2–2.9-point matched-cell gains (mean 1.71) and ToolTree's 2.16-point gain over LATS provide context across different protocols, without a cross-paper performance ranking.
W4 / Q1 — FixedGap and Top-K controls. We evaluated a predeclared empirical FixedGap grid with 95% observed protected-task retention on Native calibration traces and Vanilla-MCTS Top-K (K=1/2/5), alongside a frozen C95 margin-sensitivity experiment. On separately collected Game24 N50 runs, FixedGap achieves 70% success/153.02 requests, C95 72%/156.22, and Top-K5 72% with 50.44 requests. On Blocksworld N50, FixedGap gives 70%/36.36, C95 68%/37.40, and Top-K2 62%/39.82. These are genuine computational alternatives; the historic baseline runs and C95 study have differing gate/backend provenance, so their outcomes are descriptive. Section 5.4, Table 4, compares C95±5 under fixed Vanilla UCT-MCTS, B500 and the same 50 test tasks per domain; Appendix E, Tables 9–10, adds absolute values and paired CIs. C95 is locally Pareto-nondominated on point estimates in each domain. Its conformal distinction is a specified finite-sample Native-trajectory retention target under exchangeability and protected exposure, irrespective of whether another rule uses fewer requests on a particular sample.