Research map / Large language models / Agents, code and math
Automating Thought of Search: A Journey Towards Soundness and Completeness (Student Abstract)
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.
Automates Thought of Search by having an LLM generate successor and goal-test code, iteratively repaired using unit tests and soundness/completeness checks instead of a human in the loop, reaching near 100% accuracy on five planning domains.
Problem
Thought of Search required a human expert in the loop to produce a sound successor function and goal test for LLM-based search over natural-language planning problems.
Approach
Replace the human feedback with automatically generated unit tests (goal examples, successor examples, partial soundness checks) and a BFS-based soundness check, feeding failures back to the LLM as targeted repair prompts in a staged pipeline (goal soundness, successor soundness, successor completeness).
Key results
- AutoToS reaches 100% accuracy across all evaluated domains with LLMs of various sizes.
- Average LLM calls per domain are small, e.g., GPT-4o-mini averages 8.8 calls on 24Game and 4.8 on PrOntoQA, comparable to ToS.
- Partial soundness test and completeness step improve accuracy over iterations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the partial soundness test and successor completeness step | AutoToS · evaluated search/planning domains | accuracy | Helped |
Surprising findings
- The smaller GPT-4o-mini performs quite well in terms of accuracy compared with larger models.
- No single model dominates across all domains.
Limitations
- Relies on human-provided unit tests and partial soundness checks, so some human expertise remains.
- Soundness checks are only run on a few example problem instances via BFS, which may not guarantee full soundness.
Experimental setup
Datasets: BlocksWorld PrOntoQA Mini XWord 24Game Sokoban
Benchmarks: BlocksWorld PrOntoQA Mini XWord 24Game Sokoban
Metrics: accuracy average number of LLM calls
Baselines: ToS GPT-4 Thought of Search
Builds on: Thought of Search Tree of Thoughts Reflexion
Closest papers by meaning
- Thought of Search: Planning with Language Models Through The Lens of Efficiency (NeurIPS 2024 · similarity 0.89)
- Planning in Natural Language Improves LLM Search for Code Generation (ICLR 2025 · similarity 0.88)
- Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models (ICML 2024 · similarity 0.87)
- LLMs Improving LLMs: Agentic Discovery for Test-Time Scaling (NeurIPS 2026 · similarity 0.87)
- Learning to Better Search with Language Models via Guided Reinforced Self-Training (NeurIPS 2025 · similarity 0.86)
- Fleet of Agents: Coordinated Problem Solving with Large Language Models (ICML 2025 · similarity 0.86)
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.