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

Tianhao Qian; Jiayu Chen; Zhenyu Sun; Lixu Wang

cs.LGApr 15, 2026

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

Authors: Tianhao Qian, Jiayu Chen, Zhenyu Sun, Lixu Wang

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 $(\varepsilon,δ)$ -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 $+4.38$ points at each tested budget; on the natural-termination sensitivity cohort, physical requests decrease by $18.94$ -- $18.95\%$ and end-to-end token usage by $23.57$ -- $23.76\%$ .

Figures & tables

1:	for each task $x\in\mathcal{D}_{\mathrm{cal}}$ do
2:	Run $\Pi_{\mathrm{N}}$ with PAC-CF disabled and record every complete scored frontier $p$ . For every $a\in\mathcal{C}(p)$ , obtain $R$ matched evaluator observations and compute $s_{p}(a)=R^{-1}\sum_{r=1}^{R}Y_{p,a,r}$ .
3:	After the native run terminates, use exact or independent downstream verification available for the domain to label $\mathcal{P}(p)\subseteq\mathcal{C}(p)$ , the candidates whose recorded native subtrees contain a completion accepted by the verifier.
4:	if $\mathcal{E}_{\mathrm{N}}(x)\neq\varnothing$ then set $C_{\mathrm{task}}^{\mathrm{N}}(x)\leftarrow\max_{p\in\mathcal{E}_{\mathrm{N}}(x)}\left[\max_{a\in\mathcal{C}(p)}s_{p}(a)-\max_{a\in\mathcal{P}(p)}s_{p}(a)\right]_{+}$ .
5:	end for
6:	Sort the $n$ nonempty task scores as $C_{(1)}\leq\cdots\leq C_{(n)}$ , set $k_{Q}\leftarrow\lceil(n+1)Q\rceil$ , and freeze $\widehat{\tau}_{Q}\leftarrow C_{(k_{Q})}$ .

Table 1

Stratum / $R$	Mean $C_{\mathrm{path}}$	Mean reference rank	CPER $K=4$	CPER $K=6$	Task survival $K=4$	Task survival $K=6$
Control / 1	16.67	4.64	$54.2\%$	$27.1\%$	–	–
Control / 16	9.50	4.58	$52.1\%$	$24.0\%$	$4/24$	$8/24$
Conflict / 1	20.51	5.11	$57.5\%$	$43.7\%$	–	–
Conflict / 16	12.32	5.11	$64.4\%$	$39.1\%$	$0/24$	$1/24$

Table 1: TSP50 endpoint summary. CPER is the fraction of reference actions removed by top-

K

pruning; task survival is reported at

R=16

. Full

R\times K

results are in Appendix E .

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
Task and search process
$x=(z_{0},\mathcal{A},P,T,\mathcal{V},U)$	Agent task: initial state $z_{0}$ , admissible actions $\mathcal{A}(z)$ , response kernel $P(\cdot\mid z,a)$ , transition $T(z,a,o)$ , verifier $\mathcal{V}(h)$ , and trajectory utility $U(h)$ .
$a,\ o$	Generic action and the resulting reasoning-model, tool, or environment response.
$v,\ v_{t},\ h(v),\ \ell$	Search-tree node, node selected at frontier $t$ , its partial trajectory/history, and trajectory depth. The history symbol $h$ avoids collision with the proof stopping time $\tau$ .
$B$	Per task request budget.
$Q_{\mathrm{MCTS}}(v,a)$	native MCTS action-value statistic; distinct from conformal coverage $Q$ .

Appendix

Table 4: Notation used throughout the paper. Equivalent notation from different views is grouped to avoid duplicate definitions.

Gap regime	Consequence
$\Delta\leq\varepsilon$	Distinguishing the children is unnecessary.
$\varepsilon<\Delta\leq 2L$	PAC identification can be impossible in the worst case.
$\max\{\varepsilon,2L\}<\Delta\leq 4L+\varepsilon$	Identification not ruled out; deletion not certified.
$\Delta>4L+\varepsilon$	Finite reliable elimination is available.

Appendix

Table 5: Theoretical regimes for a two-child true-value gap

\Delta

. The intermediate region is not labeled impossible because the lower bound does not rule out identification there, while the interval certificate does not guarantee deletion.

Stratum	$R$	$K=1$	$K=2$	$K=4$	$K=6$	$K=8$
Control	1	$91.7\%$	$76.0\%$	$54.2\%$	$27.1\%$	$0.0\%$
	2	$86.5\%$	$75.0\%$	$52.1\%$	$22.9\%$	$0.0\%$
	4	$87.5\%$	$79.2\%$	$53.1\%$	$22.9\%$	$0.0\%$
	8	$90.6\%$	$81.2\%$	$56.2\%$	$28.1\%$	$0.0\%$
	16	$86.5\%$	$77.1\%$	$52.1\%$	$24.0\%$	$0.0\%$
Local-greedy conflict	1	$86.2\%$	$79.3\%$	$57.5\%$	$43.7\%$	$0.0\%$

Appendix

Table 6: Exact TSP50 catastrophic reference path elimination rate (CPER) on the fixed-cardinality matched cohort. Each row uses the same frontiers for every retained cardinality

K

; ties at the

K

th score are retained. Lower is better.

Stratum	$K=1$	$K=2$	$K=4$	$K=6$	$K=8$
Control	$0/24$	$0/24$	$4/24$ ( $16.7\%$ )	$8/24$ ( $33.3\%$ )	$24/24$
Conflict	$0/24$	$0/24$	$0/24$	$1/24$ ( $4.2\%$ )	$24/24$

Appendix

Table 7: Task-level reference path survival at

R=16

. A task survives when the exact reference continuation is retained at every inspected frontier.

Controller	$\widehat{\tau}_{.95}$	Task coverage	Candidate pruning	Protected-action pruning
UCT-MCTS	30	$97/100$ ( $97.00\%$ )	$13.27\%$	$9.69\%$
ToolChain*	25	$93/97$ ( $95.88\%$ )	$12.88\%$	$12.26\%$
LATS	30	$95/95$ ( $100\%$ ) †	$8.17\%$	$1.52\%$
LevinTS	50	$75/80$ ( $93.75\%$ )	$4.61\%$	$7.27\%$
ToolTree	20	N/A ‡	–	–

Appendix

Table 8: Game24 native-trajectory coverage and pruning aggressiveness at the frozen

Q=.95

operating points. Pruning rates are offline fixed-trajectory diagnostics, not realized end-to-end savings.

Domain	Controller	Exposed	No loss of all protected actions	Survival
Game24	UCT-MCTS	100	97	$97.00\%$
Game24	ToolChain*	97	94	$96.91\%$
Game24	LATS	96	96	$100\%$
Game24	ToolTree	100	99	$99.00\%$
Game24	LevinTS	80	75	$93.75\%$
Game24	pooled	473	461	$97.46\%$

Appendix

Table 9: B100 oracle diagnostic on adaptive trajectories. “Survival” means that no inspected protected frontier loses all actions accepted by the oracle. Game24 ToolTree uses the canonical

C=20

replacement run, not the superseded

C=32.5

run.

Budget	$\Delta$ utility	P-Req. $\downarrow$	Net Graph $\downarrow$	Token $\downarrow$
B100	$+0.265$	$3.88\%$	$8.75\%$	$3.93\%$
B200	$-0.086$	$6.41\%$	$11.86\%$	$6.32\%$
B300	$-0.638$	$6.98\%$	$12.43\%$	$7.25\%$
B500	$-0.855$	$7.54\%$	$12.72\%$	$7.72\%$

Appendix

Table 10: Macro average across the three domains excluding ToolTree. Positive reduction means lower PAC-CF workload.

Figure 1: Macro average utility and workload reduction for Native and PAC-CF. The top row compares utility; the remaining rows plot PAC-CF’s physical request, Net Graph node, and end-to-end token reductions relative to Native. Workload points average controllers with equal weights on the uncensored paired cohort.

$L/\Delta$	$\Delta-4L>0$	Finite Cert.	Pruning	PAC-CF PCS
0.05	Yes	Yes	100.0%	1.00
0.15	Yes	Yes	100.0%	1.00
0.25	Boundary	No	0.0%	1.00
0.40	No	No	0.0%	1.00

Appendix

Table 11: Controlled Gaussian BAI validation around the sufficient separation boundary. Pruning is the fraction of suboptimal candidates eliminated at the predeclared

n=5000

evaluations per candidate.

Domain	UCT-MCTS	ToolChain*	LATS	ToolTree	LevinTS
Game24	85.0	85.0	85.0	45.0	75.0
Blocksworld	85.0	90.0	82.5	27.5	90.0
GTA	75.0	77.5	52.5	47.5	30.0

Appendix

Table 12: Frozen secondary model score-gap thresholds

\widehat{\tau}_{.95}

on the common

[0,100]

score scale.

Domain	UCT-MCTS	ToolChain*	LATS	ToolTree	LevinTS
Game24	80/85	80/85	77.5/85	32.5/45	65/75
Blocksworld	70/85	15/90	10/82.5	0/27.5	65/90
GTA	50/75	35/77.5	20/52.5	42.5/47.5	25/30

Appendix

Table 13: Secondary model score-gap thresholds at

Q=.90

and

Q=.95

. Each entry reports

\widehat{\tau}_{.90}/\widehat{\tau}_{.95}

. Smaller margins permit more aggressive pruning.

Domain	Budget	$\Delta U$	P-Req. $\downarrow$	Net Graph $\downarrow$	Token $\downarrow$
Game24	B100	$+3.41$ pp	7.90%	17.36%	8.59%
	B500	$+0.41$ pp	16.10%	22.82%	16.93%
Blocksworld	B100	$+0.00$ pp	16.54%	34.18%	17.37%
	B500	$-7.80$ pp	22.33%	37.14%	23.40%

Appendix

Table 14: Endpoint deployment sensitivity under the more aggressive

Q=.90

calibration. Positive workload values denote reductions relative to Native search.

Domain	Budget	$\Delta U$	P-Req. $\downarrow$	Net Graph $\downarrow$	E2E Token $\downarrow$
Game24	B100	$+0.80$ pp	13.37%	17.84%	14.07%
	B200	$+0.40$ pp	13.63%	16.52%	14.31%
	B300	$-1.00$ pp	15.09%	17.06%	15.77%
	B500	$-0.40$ pp	13.76%	16.72%	15.37%
Blocksworld	B100	$-0.40$ pp	$-0.17\%$	3.81%	0.39%
	B200	$-0.40$ pp	$-0.26\%$	3.18%	0.29%

Appendix

Table 15: Secondary model results at the frozen

Q=.95

operating point across all budgets. Utility changes use the full paired test set; workload reductions use uncensored paired rows.

Item	Frozen setting
Controllers	UCT-MCTS, ToolChain*, LATS, ToolTree, LevinTS
Provider model	deepseek-v4-flash ; seed 42
Budgets	$B\in\{100,200,300,500\}$ , measured in provider call equivalents per task
Main calibration	Direct conformal calibration for each domain–controller pair with $n=60$ tasks with protected exposure per cell, $Q=0.95$ ; deployed $\varepsilon=0$
Frontier scoring	Four evaluator observations per candidate; matched evaluator temperature $0.2$ ; deterministic shuffle set by the seed with paired forward/reverse order
Calibration labels	Exact verifier / solution verification information assigned after search; never exposed to online search

Appendix

Table 16: Frozen implementation and evaluation configuration. These settings are fixed across the matched Native/PAC-CF comparisons unless a row explicitly states otherwise.

Domain	UCT-MCTS	ToolChain*	LATS	ToolTree	LevinTS
Game24	30.0	25.0	30.0	20.0	50.0
Blocksworld	45.0	50.0	62.5	0.0	10.0
GTA	40.0	40.0	40.0	30.0	30.0

Appendix

Table 17: Frozen

Q=.95

score-gap thresholds

\widehat{\tau}_{.95}

. All cells use

n=60

k_{.95}=58

, and the same

4.92\%

rank-based miscoverage bound.

Domain	Controller	B100					B500
		$\Delta U$	$N_{\mathrm{eff}}$	PReq	NetG	Token	$\Delta U$	$N_{\mathrm{eff}}$	PReq	NetG	Token
Game24	UCT-MCTS	+1.00	75	+2.07%	+11.64%	+1.81%	+0.00	88	+2.41%	+15.72%	+2.24%
	ToolChain*	+0.00	57	+4.80%	+16.21%	+2.53%	-2.00	100	+8.69%	+19.73%	+6.38%
	LATS	+0.00	68	+0.00%	+4.49%	+0.00%	+0.00	100	+4.81%	+15.36%	+4.77%
	ToolTree	-3.00	99	+46.91%	-19.13%	+53.11%	-3.00	100	+46.89%	-21.34%	+52.53%
	LevinTS	-3.00	61	-0.12%	+4.95%	-0.38%	-4.00	100	+1.01%	+5.85%	+0.85%

Appendix

Table 18: Results by controller at the frozen

Q=.95

operating point for B100 and B500. Utility deltas use the full test set;

N_{\mathrm{eff}}

and workload reductions use uncensored paired rows.

Domain	Controller	$N_{\mathrm{eff}}$	Physical Nodes $\downarrow$	Net Graph $\downarrow$	Matched roots
Game24	UCT-MCTS	88	15.79%	15.72%	99.66%
	ToolChain*	100	21.61%	19.73%	98.96%
	LATS	100	15.34%	15.36%	100.00%
	ToolTree	100	11.42%	$-21.34\%$	81.44%
	LevinTS	100	7.60%	5.85%	95.51%
	Macro	–	14.35%	7.06%	95.11%

Appendix

Table 19: B500 matched pruning and realized graph reduction on the uncensored paired cohort. Physical Nodes is gross matched native subtree suppression; Net Graph is realized end-to-end reduction after adaptive reallocation. “Matched roots” is the fraction of PAC-CF pruning roots whose Native ancestry is recoverable. GTA is omitted because complete node ancestry was not recorded.

Domain	Budget	$\Delta$ utility [95% CI]	PReq [95% CI]	NetG [95% CI]	Token [95% CI]
Game24	B100	$-1.00$ [-2.60,0.60]	$+10.73\%$ [8.92,12.34]	$+3.63\%$ [0.40,6.50]	$+11.41\%$ [9.66,12.95]
Game24	B200	$-1.00$ [-2.60,0.40]	$+12.31\%$ [10.58,13.90]	$+6.78\%$ [3.26,9.87]	$+12.76\%$ [11.08,14.27]
Game24	B300	$-1.60$ [-3.00,-0.40]	$+12.56\%$ [10.98,14.01]	$+7.01\%$ [3.71,9.91]	$+13.08\%$ [11.50,14.50]
Game24	B500	$-1.80$ [-3.20,-0.60]	$+12.76\%$ [11.19,14.22]	$+7.06\%$ [3.80,9.95]	$+13.35\%$ [11.76,14.81]
Blocksworld	B100	$+3.03$ [1.41,4.85]	$+1.69\%$ [-0.73,4.11]	$+11.22\%$ [9.06,13.46]	$+2.38\%$ [0.07,4.70]
Blocksworld	B200	$+2.22$ [0.81,3.64]	$+5.04\%$ [2.06,7.97]	$+14.17\%$ [11.58,16.70]	$+5.62\%$ [2.72,8.45]

Appendix

Table 20: Paired bootstrap averages by domain. Utility intervals use the full paired test set; workload intervals use uncensored paired rows. Positive reduction means lower PAC-CF workload.

Budget	$\Delta$ utility [95% CI]	PReq [95% CI]	NetG [95% CI]	Token [95% CI]
B100	$+4.38$ [1.43,7.41]	$+18.95\%$ [14.81,22.96]	$+12.90\%$ [7.54,17.77]	$+23.76\%$ [19.56,27.85]
B200	$+4.38$ [1.43,7.41]	$+18.94\%$ [14.84,22.93]	$+12.16\%$ [6.62,17.20]	$+23.57\%$ [19.39,27.65]
B300	$+4.38$ [1.43,7.40]	$+18.94\%$ [14.84,22.93]	$+12.16\%$ [6.67,17.19]	$+23.57\%$ [19.39,27.65]
B500	$+4.38$ [1.44,7.41]	$+18.94\%$ [14.83,22.94]	$+12.16\%$ [6.66,17.20]	$+23.57\%$ [19.40,27.65]

Appendix

Table 21: Independent summary across the three domains for the already pruning-aware ToolTree controller. Utility uses the full test set; workload intervals use uncensored paired rows.

Explore similar work

Jul 29, 2026cs.LG

Budget-Aware LLM Discovery via Cost-Calibrated Frontier Utility

Large language models increasingly support scientific and algorithmic discovery through inference-time search over evaluated candidates. Existing adaptive discovery controllers assign credit based only on score progress, even though prompt length, retries, and guidance calls cause search actions to incur different token costs. We prove that cost-blind credit can forfeit all but a vanishing fraction of attainable quality as frontiers multiply and costs diverge. Under a fixed search-side token budget, the controller must decide which frontier is improving and whether its gain justifies the realized cost before the budget is exhausted. We introduce \textbf{CostAda}, a cost-calibrated adaptive controller built around \emph{cost-calibrated frontier utility}. The utility values frontier progress relative to realized action cost and conditions that credit on the remaining budget. CostAda uses this signal to control local exploration intensity, frontier allocation, and budgeted tactic intervention. Cost and remaining budget therefore shape the search rather than serving only as accounting variables or a stopping rule. CostAda reaches the strongest baseline's full-budget quality with at most half the budget on twelve of sixteen benchmark--backbone pairs while achieving the strongest mean final quality on all eight benchmarks under GLM-5 and GPT-5.4.

Yansen Zhang, Yilu Liu, Tianyu Liu +6

International Digital Economy Academy (IDEA) · City University of Hong Kong · Mohamed bin Zayed University of Artificial Intelligence (MBZUAI)

Cost-Aware Frontiers Pareto Frontier Discovery Step-Level Credit

Ask PDF

Jun 7, 2026cs.LG

Agentic Search for Counterfactual Recourse under Fixed LLM Budgets

Counterfactual recourse aims to provide actionable feature changes that would alter an unfavorable decision made by a predictive model. In practice, affected individuals often benefit from multiple feasible alternatives rather than a single optimal explanation. A natural way to produce such alternatives is to prompt large language models (LLMs). However, prompting incurs a practical constraint: the number of LLM calls is often the dominant computational and economic cost. Together, the need for multiple alternatives and this cost constraint shift the problem from finding a single high-quality counterfactual to efficiently generating a set of oracle-validated counterfactuals under a fixed LLM-call budget. In this work, we study counterfactual recourse generation in the LLM-agentic setting as a fixed-budget search problem and propose Recourse Monte Carlo Tree Search (ReCo-MCTS), an agentic tree-search framework that aims to increase the yield of unique, oracle-validated counterfactuals under this budget while accounting for the extent of the required changes. ReCo-MCTS combines LLM-based multi-candidate generation, constraint checking, black-box oracle evaluation, and UCT-guided tree search to accumulate valid counterfactuals under a fixed LLM-call budget. On four real-world tabular datasets, ReCo-MCTS returns more counterfactuals than the evaluated baselines in our main comparison under the specified resource limits, with trade-offs in the extent of the required changes.

Yasuo Tabei

RIKEN Center for Advanced Intelligence Project Tokyo, Japan

Agentic Search Token Budget Allocation Candidate

Ask PDF

Jul 27, 2026cs.LG

Conformal Cascade: Distribution-Free Accuracy Guarantees for Multi-Tier LLM Inference

Large language model (LLM) cascades reduce inference cost by routing easy queries to a small model and deferring hard queries to a larger one. Production cascades govern this deferral through a confidence threshold, but LLM confidence scores are miscalibrated, the threshold must be tuned per model pair and per domain, and no setting yields a formal bound on cascade accuracy. We introduce \textbf{Conformal Cascade} (CC), a multi-tier inference framework that uses conformal prediction set size as the deferral rule: accept when the calibrated set collapses to a single answer, defer otherwise. The procedure delivers a distribution-free, finite-sample accuracy guarantee. By a per-tier union bound, the prediction set at the accepting tier covers the correct answer with probability at least

1 - Kα

for any user-specified

α

; under a selection-preservation condition (consistent with, but not strictly implied by, our marginal coverage results), the bound tightens to

1 - α

. We further characterise expected cascade cost as an explicit function of

α

and the calibration-set acceptance rate. Across 18 multiple-choice benchmarks spanning science, medicine, commonsense, and standardized exams, evaluated on two-tier cascades drawn from four open-weight model families, CC strictly improves over the strongest calibration-tuned heuristic cascade on the majority of family--benchmark pairs, with the largest gains on reasoning-heavy benchmarks where majority vote is unreliable; on easier benchmarks the cascade commits the vast majority of queries to the small model at no accuracy cost. Extension to open-ended generation requires an answer-clustering step that we leave for future work. The method requires no model training and only black-box API access.

Yifan Dou, Shikan Lian, Shibo Li

Department of Computer Science, Florida State University

LLM Inference Optimization Conformal Selection Online Conformal Prediction

Ask PDF