Searchformer: Beyond a* Better Planning with Transformers via Search Dynamics

Re:Searchformer: Beyond a* Better Planning with Transformers... by a_wild_dandan on Friday April 26, 2024 @09:33PM (#40176289)

Ah, I remember reading this paper! Essentially, they created synthetic data by solving search problems using A*. Trained on this data, transformers unsurprisingly learned to solve these problems. They then improved their synthetic data by repeatedly solving a given problem many times with A*, and keeping only the shortest step solution. Transformers learned to be competitive with this improved search heuristic too!

Pretty remarkable stuff. Given the obsession over chat bots, folk often miss how revolutionary transformer sequence modeling is to...well, any sequence application that isn't a chat bot. Looking solely at speeding up scientific simulations by ~10x, it's a watershed moment for humanity. When you include the vast space of other applications, we're in for one wild ride, y'all.

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by jadbox on Friday April 26, 2024 @10:41PM (#40176665)

Remarkable indeed, I've been toying with many smaller, unorthodox use-cases for LLMs and continue to be surprised.

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by smcin on Friday April 26, 2024 @11:55PM (#40177052)

I want to see an optimal (2P) speedrun with Sonic the Hedgehog and Tails. As a fun proof. There are two players working together; also it has more degrees-of-freedom than a Sokoban.

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by jasonjmcghee on Saturday April 27, 2024 @01:25AM (#40177502)

Can you say more? Where can I read about some of these alternate use cases?

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by ebri on Saturday April 27, 2024 @04:39AM (#40178373)

yes I want to learn about this too! Hadn't thought about it like that.

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by littlestymaar on Saturday April 27, 2024 @01:46PM (#40181934)

It uses transformers but it's not an llm though.

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by unraveller on Friday April 26, 2024 @10:42PM (#40176669)

what are those other applications? so now everyone has SoTA warehouse scheduling in their pockets no one can be expected to do anything or go anywhere inefficiently.

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by electricships on Saturday April 27, 2024 @05:48AM (#40178700)

After AlphaZero, people tried to train various combinatorial solvers

IIRC, they were unable to exceed Sota of SAT solvers (which admittedly are the results of decades of research)

maybe we just needed bigger networks, or transformers, or just more training compute

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by radomir_cernoch on Saturday April 27, 2024 @06:32AM (#40178875)

I'd love to read more. Do you know any sources?

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by algo_trader on Saturday April 27, 2024 @09:24AM (#40179783)

Try Reinforcement Learning for Combinatorial Optimization: A Survey

or a more recent and spirited discussion on reddit..

https://old.reddit.com/r/reinforcementlearning/comments/196i...

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by nickpsecurity on Saturday April 27, 2024 @01:35PM (#40181822)

Link for those who need it:

https://arxiv.org/abs/2003.03600

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by davidguetta on Saturday April 27, 2024 @08:49AM (#40179550)

Mm theres one purely based on position analysis and not tree search that has GM level in chess. From deepmind

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by lou1306 on Saturday April 27, 2024 @10:39AM (#40180297)

SAT appears to be rather impervious to statistical methods because it is very non-linear and non-local (besides, of course, being NP-complete). Flip one single literal anywhere and poof!, your formula mght go from SAT to UNSAT, or vice versa, or you might enable a ton of simplifications, etc. So it might be very hard to train a network on such a riotous state space.

Additionally, in practice SAT solvers are also supposed to provide witnesses (i.e., a satisfying assignment or an unsatisfiability core) to back their verdicts, and that may be an ever taller order for ML.

[ Parent | on HN ]

Re:Searchformer: Beyond a* Better Planning with Transformers... by math_dandy on Saturday April 27, 2024 @01:05PM (#40181574)

Since all of these combinatorial optimization problems are, in full generality, are as difficult as possible in the complexity theoretic sense, there is little prospect of AI/ML helping to solve these problems in general. (?)

But people hope that some subclass of "real-life" instances of one of these optimization problems has enough structure that AI/ML may be able to learn useful heuristics for it. (This is not my field. This is just my take-away from reading some AI/ML-for-CO papers.)

[ Parent | on HN ]