acceptodds
Under review as a conference paper at ICLR 2027

PAC-CF: Calibrating Irreversible Frontier Pruning in LLM-Guided Search

Abstract

LLM-guided search explores multiple candidate trajectories, but at substantial test-time cost. Pruning low-scoring frontier candidates can control this cost, yet it also turns potentially biased evaluator scores into irreversible decisions: systematic ranking errors can persist under repeated scoring and remove useful branches. We propose Probably Approximately Correct Conformal Filtering (PAC-CF). Its fixed-frontier analysis formulates elimination as an -PAC problem under bounded evaluator bias; its operational rule separately calibrates a score-gap threshold on held-out tasks by running the original controller without PAC-CF and using post-search verifier labels to measure the deficit of solution-preserving candidates relative to the frontier leader. Conditional on exchangeable native-controller tasks with nonempty protected exposure, conformal calibration gives finite-sample coverage for retaining at least one verifier-defined valid continuation at every protected frontier on the native trajectory. At deployment, PAC-CF removes only candidates whose gap from the highest frontier score exceeds the frozen threshold. We evaluate PAC-CF across three domains, five controllers, and four request budgets from B100 to B500. In the cross-domain/controller macro averages, the point estimates for all three workload measures are lower at every budget; the paired-bootstrap 95% confidence interval for utility excludes zero at B100 and B200. For pruning-aware ToolTree, the full-test-set cross-domain utility difference is points at each tested budget; on the natural-termination sensitivity cohort, physical requests decrease by – and end-to-end token usage by –.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM-guided search, LLM agents, test-time search, tree search, irreversible pruning, conformal prediction, evaluator bias

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_DBpPOpenReview ↗
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
  1. 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.

  2. The method can be directly plugged into existing controllers without modifying their remaining logic.

Critical weaknesses
  1. 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.

  2. 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.

  3. 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.

  4. 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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

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

The paper presents PAC-CF, a conformally calibrated frontier-pruning method designed to reduce the test-time cost of LLM-guided search while protecting solution-preserving candidates from irreversible elimination. It calibrates a task-level score-gap threshold on held-out trajectories from the native controller using post-search verifier labels, and freezes this threshold for deployment. Across three domains, five controllers, and four request budgets, PAC-CF generally reduces multiple workload measures while preserving or improving task utility/accuracy.

Critical strengths
  1. PAC-CF provides a simple and practical way to reduce unnecessary search by filtering low-scoring candidates (and keeping candidates that have potential to arrive the answer) with a calibrated score-gap threshold.
  2. The method is broadly applicable and can be integrated with multiple search controllers without modifying their underlying search strategies.
  3. The experiments cover several tasks and search methods, demonstrating meaningful efficiency gains while largely preserving task performance.
Critical weaknesses

While the paper presents practical method to achieve better efficiency-utility trade-offs with some solid justification, I have several concerns related to evaluations, presentations, and methodological details:

  1. The paper does not discuss the cost of constructing calibration. Calibration is a one-time cost and the paper acknowledges that offline protection labeling may be costly ("protected labels also depends on domain-specific offline verification and may be costly or incomplete when exact reachability is unavailable"); however, since PAC-CF requires separate calibration for each evaluator-controller-domain combination, analysis of the number of full task executions and the associated compute or token cost would help assess the practical overhead/efficiency of the proposed method.

  2. My understanding is that the proposed filter is applied before each method's native controller (based on the phrase i copied over from the appendix). However, the current evaluation does not seem to isolate the contribution of conformal calibration from the more general effect of adding a pruning rule on top of existing controllers. Additional baselines using basic pruning, e.g. Top-K based or a constant score gap from the best one at each frontier, would need to be considered as baseline to ablate the impact of the proposed 'conformal calibration' method alone (isolated from the general impact of adding rule-based pruning to existing controller). See the phrase:

For UCT-MCTS and LATS the filter is applied to the complete scored child set before native rollout selection; for ToolChain* and LevinTS it is applied before the native priority/Levin ordering

  1. The main results on Table 3 are quite difficult to interpret. It is not immediately clear that the reported values are averaged scores across different controller methods since the explanation is missing from the main text or from the caption of the table, i.e., several details that are critical for evaluating the results and their validity are deferred to the appendix.

  2. The task-level calibration score appears to be defined by taking the maximum score gap across all protected steps in a trajectory, resulting in a single threshold shared across steps. However, score scales and typical gaps may vary across search depths or states, and thus worst-step aggregation could make the threshold overly permissive at other non-worst steps. That is, the max-aggregation may yield suboptimal cost efficiency in certain task domains. An analysis of gap distributions across steps, or a comparison with depth- or step-dependent thresholds, would help clarify this issue.

Questions for authors
  1. What motivated the choices of n=60n=60 and Q=0.95Q=0.95? Could you provide either a justification or an ablation showing how sensitive the results are to these choices.
2 comments
AuthorsOpenReview ↗

Response to Reviewer dAQB

Thank you for the specific suggestions. We revised the calibration accounting and table captions, added closed-loop margin sensitivity, and reported the Native-frontier gap distribution.

W1 — Calibration cost. Each evaluator–controller–domain cell requires offline calibration. The primary collection contains 900 Native task runs (400 Game24, 250 Blocksworld, 250 GTA), yielding 744 valid task-level protected-exposure scores (285/250/209); 300 independent validation runs were not used for fitting. At B500, calibration/Native/PAC-CF mean calls per run are 124.6/109.5/102.2 and prompt-plus-completion tokens are 98.9/72.0/65.6K, averaged equally over 15 cells. Calibration calls are logged requests; test calls are reconstructed provider-call equivalents. The margin is subsequently reused across budgets within its configuration. A separate, limited timing sample measures 130 Native initial-frontier verifier calls (80 Game24, 50 Blocksworld), with median latency 6.46/4.46 ms, P95 12.45/40.44 ms, and approximately 0.987 s of cumulative measured runtime (Section 5.5; Appendix O, Table 30). This does not cover the full offline verifier or calibration cost, nor GTA; online admission requires no verifier calls.

W2 — Calibration versus elementary pruning. PAC-CF filters the complete scored frontier before the controller's native selection or ordering. We evaluated the same admission point with fixed score gaps and pure Top-K rules. Section 5.4, Table 4, holds Vanilla UCT-MCTS, B500, the 50 held-out task IDs per domain, four scores per candidate, and the evaluator fixed while varying C95 by ±5. The larger completed grid contains 750 closed-loop task-arm runs; Table 4 and Appendix E, Tables 9–10, report the 450 local runs and paired intervals. The observed C95 point is locally Pareto-nondominated on utility, requests and tokens, with domain-dependent tradeoffs.

We also ran Top-K with K=1/2/5 on Game24 and Blocksworld (300 closed-loop runs). In Blocksworld, success was 44%/62%/58% for those K values, versus 68% with C95; Game24 Top-K5 attained 72% success with fewer requests than C95. An empirical FixedGap baseline chooses a margin to meet 95% observed protected-task retention on calibration traces, without conformal rank correction. Its separate N50 evaluations give Game24 70% success/153.02 requests and Blocksworld 70%/36.36, versus C95's 72%/156.22 and 68%/37.40. These runs provide useful simple-rule comparisons, with distinct execution contracts that preclude a causal ranking of calibration procedures. PAC-CF contributes a task-level, finite-sample Native-trajectory retention property under exchangeability and protected exposure; local utility optimization is a separate question.

W3 — Table 3. We now state the estimands beside Tables 2–3. Each domain–budget result weights its five controllers equally; the macro result then weights the three domains equally. Utility uses all matched tasks. Natural-termination workload restricts to pairs where both arms finish within budget and aggregates cost ratios within controllers before averaging. Table 3 reports hierarchical paired-bootstrap confidence intervals. The underlying results are unchanged.

W4 — Position/depth dependence. The task maximum is the nonconformity score for the simultaneous event that a protected continuation survives every exposed Native frontier. Appendix N, Tables 27–28, now gives the requested distribution analysis. Vanilla gap P90 across frontier-occurrence bins 1–3/4–7/8+ is 10.0/28.5/38.0 for Game24 (83/67/239 frontiers) and 0/0/10.0 for Blocksworld (131/131/790); these bins are occurrence positions, not tree depth. GTA recorded tree depths 0/1/2 give P90 10/24/4 (40/28/27 frontiers). Across five controllers, among tasks with multiple exposures, 428/762 (56.2%), 1,002/2,446 (41.0%) and 51/116 (44.0%) gaps lie below their own task maxima for Game24/Blocksworld/GTA. A pilot/fit offline weighted-threshold comparison is also available; these trace statistics identify potential step-dependent savings without treating them as measured closed-loop speedups.

Q1 — Calibration size and Q. Q95 is the chosen target for retaining a protected continuation along Native trajectories. The 900 calibration runs average 60 per cell, but usable scores vary: Game24 n=30–79, Blocksworld n=50, GTA n=41–43, totaling 744. We compute k=ceil((n+1)Q) from each effective n (at Q95, k=49 for n=50 and k=30 for n=30). Appendix H.1, Tables 18–19, compares Q90/Q95 for the secondary evaluator at selected endpoints; the Blocksworld B500 Q90 result saves 22.33% requests while losing 7.80 utility points. The sample sizes reflect verification resources; test utility plays no role in quantile choice.

AuthorsOpenReview ↗

Discussion Phase Ends in Less Than 24 Hours — We Welcome Reviewer dAQB's Feedback

Dear Reviewer dAQB,

As the author–reviewer discussion period ends in less than 24 hours, we would like to kindly follow up on our detailed responses to your review.

We have carefully addressed your principal concerns through additional calibration-cost measurements, FixedGap and Top-K comparisons, clearer statistical reporting, and an analysis of score-gap distributions across search positions and depths. We have also clarified the rationale behind the calibration sample size and target coverage.

We would greatly appreciate your assessment of whether these additions adequately address the issues raised in your initial review. If any questions remain, we would be very happy to provide further clarification while the discussion period is still open.

Thank you again for your valuable suggestions and consideration.

Best regards,

Authors of Paper 14678

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

LLM-guided search algorithms prune branches permanently, but the evaluator scores they rely on carry persistent ranking bias. Repeated scoring can reduce random noise but cannot necessarily fix systematic bias. In this paper, the authors propose PAC-CF, which treats irreversible pruning as a reliability decision. Its theory separates bounded evaluator bias from reducible sampling noise, deriving an effective separation (Δ − 4L) for safe elimination, and shows that a small observed gap may suffice to rank candidates yet be insufficient for deletion.

Critical strengths

It distinguishes bounded evaluator bias from reducible sampling noise and shows that repeated scoring cannot fix a systematic bias. It derives the effective separation (Δ − 4L) and shows that a gap sufficient to rank candidates may still be insufficient to delete them.

Offline conformal calibration (freezing τ̂_Q from a native, PAC-CF-disabled run) followed by a simple online rule (keep candidates within τ̂_Q + ε of the frontier leader) is easy to implement and interpret.

With probability ≥ Q, at least one verifier-defined valid continuation survives at every protected frontier along the native trajectory, and the guarantee is honestly scoped as path-survival rather than optimality.

Critical weaknesses

Coverage requires protected-set exposure and exchangeability between calibration and future tasks; when these fail, the guarantee may not hold.

It relies on domain-specific offline verification that may be expensive or incomplete, creating a practical barrier to deployment.

Reported workload–utility tradeoffs are tied to the evaluated benchmarks and may not transfer to other settings.

Performance depends on the frozen task-level threshold τ̂_Q and ε, whose robustness and tuning burden are not fully addressed.

Questions for authors

See above

2 comments
AuthorsOpenReview ↗

Response to Reviewer SGFy

We appreciate the emphasis on the assumptions behind the reliability statement and the practicality of offline verification. We have clarified both points in the manuscript and added sensitivity evidence.

W1 — Protected exposure and exchangeability. The statistical unit is an entire task. We take the maximum verifier-defined protected score gap across its exposed Native frontiers, obtaining one task-level nonconformity score; no independence across frontiers is assumed. Under task-level exchangeability and nonempty protected exposure, the split-conformal threshold provides simultaneous retention of at least one protected continuation at every such frontier with probability at least Q. Exposure can occur even when the Native controller ultimately fails to complete a task: the verifier can identify a reachable continuation along its trace. The claim is scoped to Native reference trajectories. Separately, the evaluated closed-loop system retains protected paths at B100 on 461/473 Game24 cases (97.46%) and 494/495 Blocksworld cases (99.80%) (Appendix G.2, Table 14). A distinct B500 audit of PAC-CF-induced trajectories finds no observed protected-continuation loss on 47/50 tasks in each domain (94/100 overall). Seventeen local loss events occur on six affected tasks, of which three were nevertheless solved (Section 5.5; Appendix O, Table 29). The B100 and B500 audits have different units and settings; neither extends the Native-trajectory conformal statement to adaptive deployment.

W2 — Verification and calibration cost. Offline labels use symbolic reachability for Game24, bounded goal-reachability search for Blocksworld, and gold-plan information for GTA, each within its stated scope. The primary collection contains 900 Native calibration runs and 744 usable protected-exposure scores, with 300 independent validation runs excluded from threshold fitting. At B500, calibration averages 124.6 calls and 98.9K tokens per run over the 15 domain–controller cells. The threshold can be reused for subsequent tasks with a matching configuration; deployment only evaluates candidates and applies the frozen score margin. The workload audit distinguishes LLM requests and tokens from offline verifier compute. We additionally timed 130 Native initial-frontier verifier invocations (80 Game24, 50 Blocksworld): median 6.46/4.46 ms, P95 12.45/40.44 ms, and approximately 0.987 s in cumulative measured time (Section 5.5; Appendix O, Table 30). This restricted sample is not a measurement of end-to-end calibration or verification cost and excludes GTA. Recalibration is appropriate when the task or evaluator distribution changes.

W3 — Transferability. Evidence spans three domains, five search controllers, four budgets, and an additional evaluator. Across B100–B500, full-pair requests, Net Graph nodes and tokens decline by 6.14–9.47%, 9.03–12.40% and 6.84–10.25%. Utility is domain-dependent: GTA has positive domain-level intervals across the four budgets; Blocksworld has positive intervals at B100/B200; Game24 has negative intervals at B300/B500 (Appendix L). Excluding ToolTree still reduces B500 requests, nodes and tokens by 7.54%, 12.72% and 7.72%. We now state this heterogeneity alongside the aggregate results and limit generalization to the evaluated conditions.

W4 — Margin sensitivity and ε. Primary experiments fix ε=0; it is the theoretical optimality tolerance, with no additional empirical tuning. Increasing nonnegative ε makes admission more conservative under Eq. (7). Q controls the task-level target; Appendix H.1, Tables 18–19 compare Q90/Q95 on the secondary-evaluator setting and selected Game24/Blocksworld endpoints. At Blocksworld B500, Q90 saves 22.33% of requests with a 7.80-point utility decrease, showing the operational consequence of the target. Section 5.4, Table 4, additionally compares C95 to C95±5 using 50 held-out tasks per domain, fixed B500 and four repeated candidate scores. Across Game24, Blocksworld and GTA, C95 is locally Pareto-nondominated on the observed utility/request/token point estimates. Appendix E, Tables 9–10, gives absolute results and task-paired confidence intervals. Thresholds come from separate Native calibration tasks, without test-utility tuning.

AuthorsOpenReview ↗

Discussion Phase Ends in Less Than 24 Hours — We Welcome Reviewer SGFy's Feedback

Dear Reviewer SGFy,

As the author–reviewer discussion period ends in less than 24 hours, we would like to kindly follow up on our detailed rebuttal and revised manuscript.

We have made substantial efforts to address your concerns, particularly by clarifying the assumptions and scope of the conformal guarantee, reporting the cost of offline verification, and adding controlled threshold-sensitivity experiments.

Your feedback would be extremely valuable in helping us understand whether these revisions have adequately addressed your original concerns or whether any important questions remain.

We sincerely appreciate your time and consideration and would be grateful for any further assessment before the discussion period concludes.

Best regards,

Authors of Paper 14678

Comments on the paper

2 comments
AuthorsOpenReview ↗

Global Thanks and Revision Summary — Submission 14678 (PAC-CF)

Dear Reviewers and Area Chair,

We sincerely thank all three reviewers (SGFy, dAQB, and DBpP) and the Area Chair for their careful evaluation, constructive criticism, and valuable suggestions. We appreciate the reviewers' recognition of the motivation behind bias-aware irreversible pruning and the simplicity of the calibrated filtering mechanism. Their feedback has helped us strengthen the theoretical presentation, experimental evaluation, and transparency of our conclusions.

Revision highlights. We have substantially revised the manuscript and expanded the main text to 10 pages. All revisions and newly added material are highlighted in blue in the revised PDF to facilitate inspection. Our detailed point-by-point responses have been posted under the corresponding reviews.

The main improvements address three aspects:

(1) Theoretical clarity and deployment reliability. We clarified the relationship between the bias-aware analysis and conformal calibration, explicitly distinguished the Native-trajectory guarantee from empirical closed-loop behavior, and added an audit of PAC-CF-induced trajectories.

(2) Experimental comparisons and computational overhead. We added calibration-cost accounting, verifier-timing measurements, FixedGap and Top-K baselines, and controlled threshold-sensitivity experiments to clarify both the benefits and limitations of PAC-CF.

(3) Statistical transparency and generality. We clarified the aggregation procedures and confidence intervals, investigated score-gap distributions across frontier positions and depths, and reported controller-independent workload savings alongside domain-dependent utility outcomes.

We hope these revisions and additional experiments address the reviewers' principal concerns. We would greatly appreciate any further feedback and welcome continued discussion.

Thank you again for your time and consideration.

Best regards,

The Authors

AuthorsOpenReview ↗

General Response — Submission 14678 (PAC-CF)

We appreciate the reviewers’ close reading of PAC-CF. The revised manuscript clarifies the relationship between the bias-aware theory, the calibrated admission rule, and the closed-loop evidence. It also adds calibration-cost accounting, local threshold sensitivity, Native-frontier gap distributions, an empirical protection audit on PAC-CF-induced trajectories, and a scoped Native-verifier timing audit, with more explicit statistical estimands in Tables 2–3.

[G1] Reliability and theory. The TSP50 stress test illustrates why averaging cannot eliminate persistent ranking bias: with 16 scores per candidate, the optimal continuation has mean rank 5.11 on conflict frontiers and is removed by Top-4 at 64.4% of those frontiers. Section 4.1 identifies the effective separation Δ−4L. Section 4.2 constructs a task-level score from the maximum verifier-defined protected gap along a Native trajectory. Split-conformal calibration then yields a simultaneous protected-continuation retention statement at target Q for exchangeable tasks with protected exposure. This statement concerns Native reference trajectories. Closed-loop deployment is separately measured: at B100, protected-path survival is 461/473 (97.46%) on Game24 and 494/495 (99.80%) on Blocksworld (Appendix G.2, Table 14). In a separate B500 audit on PAC-CF-induced trajectories, 47/50 Game24 and 47/50 Blocksworld tasks (94/100 overall) show no observed protected-continuation loss. The audit records 17 local loss events on the six affected tasks, three of which were nevertheless solved (Section 5.5; Appendix O, Table 29). This empirical observation is not a conformal guarantee for the adapted trajectory.

[G2] Calibration and cost. The primary-evaluator study collected 900 Native calibration runs, providing 744 usable task-level scores; 300 independent validation runs were excluded from fitting. Calibration is specific to an evaluator–controller–domain configuration, and thresholds are reused across test budgets. At B500, the 15-cell macro means are 124.6/109.5/102.2 calls and 98.9/72.0/65.6K tokens per run for calibration/Native/PAC-CF. Calibration counts logged request attempts; test calls are provider-call equivalents. Verification occurs offline, with domain-specific reachability or gold-plan labels. Online filtering uses scored candidates and a frozen margin. These figures quantify LLM workload, not the full cost of offline verification. A separate timing audit covers 130 Native initial-frontier verifier invocations (80 Game24; 50 Blocksworld), with respective median latencies of 6.46/4.46 ms and P95 latencies of 12.45/40.44 ms; the measured invocations total approximately 0.987 s (Section 5.5; Appendix O, Table 30). These timings do not estimate the full offline calibration or verification workload, and GTA was not measured.

[G3] Threshold sensitivity and simple baselines. Section 5.4, Table 4, studies frozen C95 and its ±5 neighbors on the same 50 held-out tasks per domain, using Vanilla UCT-MCTS at B500. All other control settings and four repeated candidate scores are fixed. The six margin contrasts (utility points; request/token changes) are: Game24, −5: 0/+4.0%/+3.6%; +5: −4/+7.9%/+5.9%; Blocksworld, −5: +2/+0.4%/+1.2%; +5: −2/+13.3%/+9.4%; GTA derived Avg3, −5: −0.52/−11.8%/−17.4%; +5: +3.09/+4.4%/+6.7%. C95 is locally Pareto-nondominated on these point estimates. Appendix E, Tables 9–10, reports absolute means and paired bootstrap intervals (e.g., Game24 +5 utility CI [−12,+4] points, Blocksworld +5 requests CI [+2.28,+7.92]/task, GTA +5 Avg3 CI [+0.16,+6.60] points). The intervals are exploratory and unadjusted for multiple comparisons. Additional FixedGap and Top-K runs inform the distinction between pruning efficiency and conformal threshold selection. The latter supplies a finite-sample Native-trajectory retention property under its assumptions.

[G4] Main effects and interpretation. PAC-CF augments five established controllers across Game24, Blocksworld and GTA at B100/200/300/500. Macro utility changes at B100/B200 are +1.09/+0.81 percentage points, with paired 95% intervals excluding zero. Across budgets, full-pair requests, Net Graph nodes and end-to-end tokens fall by 6.14–9.47%, 9.03–12.40% and 6.84–10.25%, respectively. The paper now explains equal weighting across five controllers and three domains, the full-pair utility estimand, natural-termination workload cohorts, and hierarchical paired-bootstrap intervals. Utility varies by domain; workload savings also persist in the ToolTree-excluded analysis and under Ministral on uncensored pairs. We have kept the scope of each finding tied to its evaluator, protocol and measured outcome.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.