Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.14345 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909029211570176 |
|---|---|
| author | Qian, Tianhao |
| author_facet | Qian, Tianhao |
| contents | As search depth increases in autonomous reasoning and embodied planning, candidate action spaces expand exponentially, often exhausting computational budgets. While heuristic pruning is a critical countermeasure, existing approaches lack formal safety guarantees when guided by surrogate evaluators such as Large Language Models (LLMs), which exhibit systematic biases. We formulate node expansion as a localized Best-Arm Identification (BAI) problem under bounded bias $L$ and derive a sample complexity upper bound of $\mathcal{O}((Δ-4L)^{-2})$, identifying $Δ> 4L$ as the regime where safe elimination is feasible. We further establish an information-theoretic lower bound of $Ω((Δ-2L)^{-2})$ that characterizes the structural limits of biased exploration. Motivated by these results, we propose PAC-MCTS, a bias-aware pruning framework that dynamically adapts confidence bounds during search. Experiments on Blocksworld and ALFWorld demonstrate that PAC-MCTS consistently improves robustness and search efficiency over strong pruning baselines, achieving up to 78\% fewer API evaluations and over 3$\times$ higher sample efficiency under strict compute budgets. Ablation studies further validate the predicted degradation behavior as evaluator bias increases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_14345 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | PAC-MCTS: Bias-Aware Pruning for Robust LLM-Guided Search and Planning Qian, Tianhao Machine Learning Artificial Intelligence 68T05, 90C40 As search depth increases in autonomous reasoning and embodied planning, candidate action spaces expand exponentially, often exhausting computational budgets. While heuristic pruning is a critical countermeasure, existing approaches lack formal safety guarantees when guided by surrogate evaluators such as Large Language Models (LLMs), which exhibit systematic biases. We formulate node expansion as a localized Best-Arm Identification (BAI) problem under bounded bias $L$ and derive a sample complexity upper bound of $\mathcal{O}((Δ-4L)^{-2})$, identifying $Δ> 4L$ as the regime where safe elimination is feasible. We further establish an information-theoretic lower bound of $Ω((Δ-2L)^{-2})$ that characterizes the structural limits of biased exploration. Motivated by these results, we propose PAC-MCTS, a bias-aware pruning framework that dynamically adapts confidence bounds during search. Experiments on Blocksworld and ALFWorld demonstrate that PAC-MCTS consistently improves robustness and search efficiency over strong pruning baselines, achieving up to 78\% fewer API evaluations and over 3$\times$ higher sample efficiency under strict compute budgets. Ablation studies further validate the predicted degradation behavior as evaluator bias increases. |
| title | PAC-MCTS: Bias-Aware Pruning for Robust LLM-Guided Search and Planning |
| topic | Machine Learning Artificial Intelligence 68T05, 90C40 |
| url | https://arxiv.org/abs/2604.14345 |