PAC-CF: Calibrating Irreversible Frontier Pruning in LLM-Guided Search
Abstract
LLM-guided search is usually adopted to solve complex tasks by ranking and pruning top-$K$ candidates based on evaluator scores. However, irreducible bias still exists even if popular methods, such as repeated sampling, are applied to reduce variance. Consequently, pruning may remove every continuation that can reach a valid solution. In this paper, we propose Probably Approximately Correct Conformal Filtering (PAC-CF), which formulates tree pruning as a PAC-guaranteed decision problem. Theoretical analysis establishes how irreducible bias reduces the score separation for certified elimination. Native-Trace path calibration derives a conformal margin from the score deficit of verifier-valid continuations on held-out Native traces. During deployment, PAC-CF uses this calibrated margin in a direct score-gap filtering rule. Across diverse domains and state-of-the-art controllers, PAC-CF improves utility at various budgets while reducing all five measured workload metrics. Especially on pruning-aware ToolTree under a 100-request budget, replacing native top-$K$ improves equal-domain utility by 4.38 points while reducing physical requests by $18.95\%$ with a $23.76\%$ token reduction.
![Director of Machine Learning Insights [Part 4]](/uploads/articles/4d4046d553c83e57a3aa9af0665a2d2d482ad7c9.png)