Beyond A*: Better Planning with Transformers

Original Article ↗ Hacker News Discussion ↗

Researchers are exploring whether transformer models can outperform classic path-planning algorithms like A* by learning from their execution traces, for example on maze-solving and Sokoban puzzles. Commenters find the approach intellectually interesting, especially as a way to learn heuristics or guide traditional search methods, but note that the reported 26.8% reduction in search steps likely comes with far higher computational cost and weaker optimality guarantees than A*. The exchange highlights broader questions about when it makes sense to replace well-understood symbolic algorithms with heavy neural models, and whether such work advances practical performance or mainly illustrates the flexibility of transformers.

Model naming and terminology

  • Several commenters dislike the name “Searchformer”; suggest alternatives (e.g., planning-themed names, “T*”), and note naming collisions with prior work.
  • Some argue “Search” is appropriate due to A* heritage; others say “Planning” would better match symbolic-planning terminology and avoid confusion with information-retrieval “search.”
  • Jokes about naming, trademarks, and the proliferation of transformer-themed names.

Performance vs A* and classical search

  • Paper claims fewer A* search steps on Sokoban and maze tasks; commenters note this doesn’t necessarily mean faster wall-clock time.
  • Multiple participants assert A* per-step cost is trivial compared to running a transformer; some doubt any speed gain, especially since wall-clock times are not reported.
  • There is discussion of A* being optimal under its assumptions, and that domain-specific methods (e.g., Jump Point Search) can outperform it by exploiting structure.

Learned heuristics and hybrid approaches

  • Strong interest in using learned models to provide heuristics or tie-breakers for A*, branch-and-bound, ILP, SAT, and other discrete optimizers.
  • Preference from several commenters for hybrid systems: keep provable algorithms, augment them with ML-learned heuristics rather than fully replacing them.
  • Some see this paper as a step toward a generic, data-driven way to tune search strategies instead of hand-crafting heuristics.

Sokoban, benchmarks, and scientific value

  • Critics note that Sokoban SOTA solvers far outperform plain A*, so beating vanilla A* is a modest result.
  • Questions raised about the paper’s scientific contribution if it largely mirrors A* traces and improves them by a constant factor.
  • Others counter that research need not be SOTA to be valuable; it can illustrate a new framing (transformers over execution traces) and inspire follow-up work.

Optimality, unsolvability, and limitations

  • Concerns that transformer-based planners don’t naturally prove optimality or absence of solutions, whereas A* can in finite spaces.
  • Discussion of transformers’ difficulties with strong forms of logical negation and guarantees.
  • Some see the work as evidence of transformers’ surprising generality; others warn against overgeneralizing generative-AI success to all planning/optimization problems.