When is Tree Search Useful for LLM Planning?
Ohio State + OSU analyze multi-step LLM planning as a generator/discriminator/planner system and argue that current LLM discriminators make tree search a poor choice in practice.
Ask this paper
Framework: Decomposes LLM planning into a candidate generator, a discriminator that scores candidates, and a planning algorithm (iterative correction or tree search) that navigates the candidate space.
90% discriminator bar: Tree-search planners only beat simpler re-ranking baselines when the discriminator is at least ~90% accurate - a threshold current LLMs don't reliably clear on text-to-SQL or math.
10-20x slower: Tree search runs 10-20x slower than iterative correction for marginal or zero gains, making it impractical for production LLM pipelines today.
Implication: Investing in stronger discriminators (verifiers, reward models) may unlock more gains than building ever-more-elaborate planners on top of weak scorers.