Research map / Learning theory and algorithms / Combinatorial and search optimization
SeeA*: Efficient Exploration-Enhanced A* Search by Selective Sampling
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 SeeA*, which replaces A*'s best-first node selection with selective sampling of a candidate subset of OPEN (uniform, clustering, or UCT-like), and shows improved search efficiency on retrosynthesis, logic synthesis, and Sokoban.
Problem
A* search has limited exploration and gets trapped in suboptimal branches when the learned heuristic is inaccurate, which hurts efficiency on real-world combinatorial problems.
Approach
Select the expansion node as the best-f node within a dynamically sampled candidate subset D of the OPEN list (via uniform, competitive-clustering, or UCT-like sampling), instead of the global best, so exploration of other promising branches occurs; a theoretical analysis under a prediction-error distribution assumption shows efficiency gains when heuristic error is large.
Key results
- On USPTO retrosynthesis, SeeA*(UCT) reaches 98.95% solved with average length 6.36 versus 91.05% and 8.74 for Retro*+.
- On MCNC logic synthesis, SeeA*(Cluster) achieves 23.5% mean ADP reduction versus 20.9% for ABC-RL.
- SeeA* solves all 1000 Sokoban test problems from Boxoban, with shorter solutions than A*, WA*, LevinTS, PHS and DeepCubeA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SeeA* (UCT) instead of A* search | Retrosynthesis planning · USPTO | Solved (%): 88.42 -> 98.95 | Helped |
| Use SeeA* (UCT) instead of A* search | Retrosynthesis planning · USPTO | Length: 9.27 -> 6.36 | Helped |
| Use SeeA* (Cluster) instead of A* search | Logic synthesis · MCNC test circuits | Mean ADP reduction (%): 19.5 -> 23.5 | Helped |
| Use SeeA* (Cluster) instead of LevinTS | Retrosynthesis planning · Seven retrosynthesis datasets | Mean success accuracy (%): 61.01 -> 63.56 | Helped |
| Vary the candidate-set size K; K=1 leaves selection to sampling, while K=∞ is equivalent to A* (ablation) | SeeA* · USPTO | Solved rate | Mixed |
| Vary the number of clusters Nc in clustering sampling (ablation) | SeeA* (Cluster) · USPTO | Search performance | No clear effect |
| Vary cb in UCT-like sampling (ablation) | SeeA* (UCT) · USPTO | Search efficiency | Mixed |
Surprising findings
- Pure epsilon-greedy exploration on USPTO yields a very long average solution length (43.78) despite a 92.11% success rate.
- SeeA* with K=1 (pure sampling) performs worst, indicating that some heuristic guidance is necessary alongside exploration.
Limitations
- Theoretical analysis relies on a specific prediction-error distribution assumption (uniform or Gaussian) and does not cover all practical settings.
- Sampling strategies are limited to three simple variants; the authors note more effective sampling is future work.
- Clustering and UCT-like variants add hyperparameters (K, Nc, cb) whose best values depend on the domain.
Experimental setup
Datasets: USPTO benchmark (190 molecules) eMolecules building blocks logP logS Toxicity LD50 Ames BBBP ClinTox MCNC Boxoban
Benchmarks: USPTO logP logS Toxicity LD50 Ames BBBP ClinTox MCNC Boxoban
Metrics: solved rate (%) solution length node expansions wall-clock time ADP reduction rate (%)
Baselines: Retro* Retro*+ MCTS A* search WA* LevinTS PHS epsilon-Greedy ABC-RL DeepCubeA
Builds on: A* search Retro*+ LevinTS PHS ABC-RL
Closest papers by meaning
- Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration (NeurIPS 2026 · similarity 0.86)
- Intelligent Go-Explore: Standing on the Shoulders of Giant Foundation Models (ICLR 2025 · similarity 0.86)
- Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstraction (ICML 2024 · similarity 0.86)
- Monte Carlo Tree Search in the Presence of Transition Uncertainty (AAAI 2024 · similarity 0.86)
- Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts (NeurIPS 2026 · similarity 0.86)
- ExACT: Teaching AI Agents to Explore with Reflective-MCTS and Exploratory Learning (ICLR 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.