Research map / Large language models / Agents, code and math
PlanU: Large Language Model Reasoning through Planning under Uncertainty
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PlanU, an LLM-based MCTS planner that models node returns as quantile distributions and adds a curiosity-based UCC exploration score to handle both LLM and environmental uncertainty in stochastic decision-making tasks.
Problem
LLM-based decision-making and planning degrade in stochastic environments because existing LLM-MCTS methods ignore environmental uncertainty and average returns, while LLM sampling adds further uncertainty.
Approach
Model each MCTS action node's return as a quantile distribution (QR-DQN style) instead of a mean, select actions with an Upper Confidence Bound with Curiosity score that adds an RND-style novelty bonus computed on text embeddings to reduce LLM-generation noise.
Key results
- On Blocksworld with Mistral-7B, PlanU reaches 0.559 success on 6-step tasks versus 0.338 for the best baseline RAP-E.
- On TravelPlanner, PlanU achieves task completion 0.378 and constraint satisfaction 0.222, versus 0.234 and 0.089 for LATS.
- On WebShop, PlanU obtains success rate 0.5 and average reward 0.73, compared with 0.3 and 0.57 for LATS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PlanU instead of LATS | TravelPlanner planning · TravelPlanner | Task Completion Rate: 0.234 ± 0.039 -> 0.378 ± 0.020 | Helped |
| Use PlanU instead of LATS | TravelPlanner planning · TravelPlanner | Constraint Satisfaction Rate: 0.089 ± 0.017 -> 0.222 ± 0.015 | Helped |
| Use PlanU instead of LATS | WebShop agent · WebShop | Average Reward: 0.57 ± 0.07 -> 0.73 ± 0.07 | Helped |
| Use PlanU instead of LATS | WebShop agent · WebShop | Success Rate: 0.3 -> 0.5 | Helped |
| Use PlanU instead of the strongest reported baseline | Blocksworld with Mistral-7B · Blocksworld 4-step | Success Rate: 0.632 ± 0.05 -> 0.803 ± 0.04 | Helped |
| Use PlanU instead of the strongest reported baseline | Blocksworld with Llama3.1-8B · Blocksworld 6-step | Success Rate: 0.428 ± 0.05 -> 0.524 ± 0.04 | Helped |
| Replace mean-value selection with quantile-distribution modeling (ablation) | PlanU · Overcooked Tomato Lettuce Salad | optimal-path identification | Hurt |
| Replace UCC novelty reward with the UCT exploration term (ablation) | PlanU · Overcooked Tomato Lettuce Salad | optimal-path identification | Hurt |
| Replace mean-value selection with quantile-distribution modeling (ablation) | PlanU · VirtualHome Entertainment | learning speed | Hurt |
| Replace UCC novelty reward with the UCT exploration term (ablation) | PlanU · VirtualHome Entertainment | learning speed | Hurt |
| Shuffle policy and world-model prompt sentences (ablation) | PlanU · VirtualHome Entertainment | convergence speed | No clear effect |
| Inject task-irrelevant environment-related prompt information (ablation) | PlanU · VirtualHome Entertainment | convergence speed | No clear effect |
Surprising findings
- Naive integration of uncertainty prompting into CoT and RAP (CoT+U, RAP+U) performs poorly even on a simple stock investment task.
- DeLLMa's success rate drops sharply with more steps on Blocksworld (0.041 at 6 steps), since it does not use environment feedback.
Limitations
- Environmental uncertainty is simulated by injected failure rates rather than naturally stochastic environments.
- Results on TravelPlanner and WebShop use only 45 and 10 tasks respectively, giving limited statistical power.
- Experiments are on a few text-based benchmarks; generalization beyond them is untested.
Experimental setup
Datasets: Blocksworld Overcooked VirtualHome TravelPlanner WebShop
Benchmarks: Blocksworld Overcooked VirtualHome TravelPlanner WebShop
Metrics: success rate return task completion rate constraint satisfaction rate average reward
Baselines: CoT ToT Reflexion DeLLMa RAP RAP-D RAP-E LATS QR-DQN
Builds on: RAP QR-DQN IQN Random Network Distillation UCT
Closest papers by meaning
- Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI Planning (AAAI 2024 · similarity 0.90)
- Non-myopic Generation of Language Models for Reasoning and Planning (ICLR 2025 · similarity 0.90)
- DeLLMa: Decision Making Under Uncertainty with Large Language Models (ICLR 2025 · similarity 0.90)
- Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code (NeurIPS 2025 · similarity 0.88)
- Policy Guided Tree Search for Enhanced LLM Reasoning (ICML 2025 · similarity 0.88)
- LexiCon: a Benchmark for Planning under Temporal Constraints in Natural Language (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.