2FFS Beats BAI-MCTS by Mixing Cheap and Costly AI Planning Evaluations
2FFS is a new tree-search algorithm that slashes the cost of finding the best move by smartly mixing cheap heuristic evaluations with expensive accurate rollouts
- New algorithm: 2FFS is the first tree-search algorithm to formally combine cheap biased evaluations with expensive accurate ones inside a minimax tree.
- Core problem solved: Modern AI planning (especially with LLMs) faces a cost tradeoff -- heuristics are fast but wrong, full rollouts are accurate but prohibitively expensive.
- How it works: Uses cheap oracles to quickly rank children, then calls the expensive oracle only at competitive nodes via a "local certification" mechanism.
- Proven guarantees: Fixed-confidence correctness, finite stopping, and polynomial-depth cost bounds -- all formally proved.
- Results: Substantially fewer samples and compute operations vs. the BAI-MCTS baseline across synthetic stochastic tree experiments.
- Limitation: No public code yet; experiments are on synthetic trees, not real-world game benchmarks.
Finding the best move in a game tree sounds like a solved problem -- chess engines have been doing it for decades. But modern AI planning, especially when language models are involved in the reasoning loop, has reopened the question in a painful way: accurate evaluations are expensive, and cheap heuristics are biased. A new paper from Peter Chen and Xi Chen introduces 2FFS (Two-Fidelity Fixed-confidence Search), an algorithm that navigates this tradeoff by intelligently mixing two types of evaluations inside a minimax tree.
The core tension in modern AI planning
Minimax trees are the backbone of adversarial planning. A MAX player picks moves to maximize a score; a MIN player picks moves to minimize it. The tree alternates between these two roles, and the goal is to identify the best action at the root. This problem is increasingly relevant in modern AI planning, where deep minimax search and MCTS with language model long rollouts face a fundamental tradeoff: heuristic evaluations are cheap but biased, while accurate rollouts are reliable but prohibitively expensive.
This is not a hypothetical concern. In many settings, there are two complementary information sources: an expensive, high-fidelity oracle (such as a high-accuracy simulation) that provides accurate but costly feedback, and a cheap, low-fidelity prediction (such as a machine learning model or analytical approximation) that gives fast but potentially biased estimates. When you are running an LLM to evaluate a game position or a planning state, the cost difference between a quick heuristic and a full rollout can be orders of magnitude.
Prior work on Best-Action Identification (BAI) in game trees -- the formal problem of finding the optimal root action with a guaranteed confidence level -- assumed you only had one type of evaluation. The goal is to quickly identify the action at the root of a game tree whose value is the largest by querying noisy samples of the leaves' values of that tree. But in practice, you almost always have both a fast-and-dirty option and a slow-and-reliable one. 2FFS is the first algorithm to exploit both simultaneously inside a tree.
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
