6 ms·

Searchformer: Beyond A* – Better planning with transformers via search dynamics

181 points by yeldarb 2y ago

yeldarb 2y ago
> While Transformers have enabled tremendous progress in various application settings, such architectures still lag behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks and present Searchformer, a Transformer model that optimally solves previously unseen Sokoban puzzles 93.7% of the time, while using up to 26.8% fewer search steps than standard A∗ search. Searchformer is an encoder-decoder Transformer model trained to predict the search dynamics of A∗. This model is then fine-tuned via expert iterations to perform fewer search steps than A∗ search while still generating an optimal plan. In our training method, A∗'s search dynamics are expressed as a token sequence outlining when task states are added and removed into the search tree during symbolic planning. In our ablation studies on maze navigation, we find that Searchformer significantly outperforms baselines that predict the optimal plan directly with a 5-10× smaller model size and a 10× smaller training dataset. We also demonstrate how Searchformer scales to larger and more complex decision making tasks like Sokoban with improved percentage of solved tasks and shortened search dynamics. Neat; TIL about Sokoban puzzles. I remember playing Chip's Challenge on Windows 3.1 when I was a kid which had a lot of levels like that.
- smcin 2y ago
  Sokoban puzzles have a discrete set of actions, typically 8 (move U/D/L/R ; drag U/D/L/R), on a discrete grid.
  - airstrike 2y ago
    more like push than drag tbf
- passion__desire 2y ago
  Jonathan Blow is working on "Sokoban"-Inspired Puzzle Game. I am looking forward to its release.
- Modified3019 2y ago
  It's definitely a fun little puzzle. I was introduced to it ages ago via "Wyvern" (https://web.archive.org/web/20040225005408/http://www.cabochon.com/ https://web.archive.org/web/20040225005408/http://www.caboch...) where I'd basically sit around playing it and chatting. Wyvern was heavily influenced by Crossfire (https://crossfire.real-time.com/ https://crossfire.real-time.com/) which had a not so functional version. Crossfire itself was influenced by nethack, which apparently also has sokoban levels.
a_wild_dandan 2y ago
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.
- jadbox 2y ago
  Remarkable indeed, I've been toying with many smaller, unorthodox use-cases for LLMs and continue to be surprised.
  - smcin 2y ago
    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.
  - jasonjmcghee 2y ago
    Can you say more? Where can I read about some of these alternate use cases?
    - ebri 2y ago
      yes I want to learn about this too! Hadn't thought about it like that.
  - littlestymaar 2y ago
    It uses transformers but it's not an llm though.
- 2y ago
nextaccountic 2y ago
Due to the no free lunch theorem [0], any search algorithm that makes some problems faster will necessarily make other problems slower. How does the worst case for an algorithm like this look like? I think that part of the appeal of A* to me is that I can readily visualize why the algorithm failed at some pathological inputs. [0] https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...
- kevindamm 2y ago
  Well, it's still using A* and state exploration to validate the plans generated. But, it's generating plans nondeterministically so it is possible it could run in O(\inf). Why didn't they give more details about the Sokoban puzzles being solved? The standard benchmark is the 90 puzzles in XSokoban and there's a Large Test Suite that has a few thousand but many of them haven't been solved by any search or planning system. Even the 90 puzzles in XSokoban were only solved a few years ago (2020?) by Festival (using FESS, a feature-space search in addition to domain-space, state-space). Before that it had been about 20 years of only 57 or so levels solved via search. I see that they measure trace lengths but I would have really liked to see # of XSokoban levels and how many states were examined, to line up with existing research.
- reaperman 2y ago
  The "No free lunch" theorem does have some prequisites for it to actually apply. > There is no free lunch in search if and only if the distribution on objective functions is invariant under permutation of the space of candidate solutions.
- IanCal 2y ago
  NFL theorem is frankly silly. It boils down to "you can't predict random numbers". I'm sure it's useful to have formalized but it has no real impact on real world situations because most problems we care about have some kind of structure we can exploit.
  - nextaccountic 2y ago
teleforce 2y ago
Previous post and discussions on HN: Beyond A*: Better Planning with Transformers: https://news.ycombinator.com/item?id=39479478 https://news.ycombinator.com/item?id=39479478

181 points by yeldarb 2y ago

> While Transformers have enabled tremendous progress in various application settings, such architectures still lag behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks and present Searchformer, a Transformer model that optimally solves previously unseen Sokoban puzzles 93.7% of the time, while using up to 26.8% fewer search steps than standard A∗ search. Searchformer is an encoder-decoder Transformer model trained to predict the search dynamics of A∗. This model is then fine-tuned via expert iterations to perform fewer search steps than A∗ search while still generating an optimal plan. In our training method, A∗'s search dynamics are expressed as a token sequence outlining when task states are added and removed into the search tree during symbolic planning. In our ablation studies on maze navigation, we find that Searchformer significantly outperforms baselines that predict the optimal plan directly with a 5-10× smaller model size and a 10× smaller training dataset. We also demonstrate how Searchformer scales to larger and more complex decision making tasks like Sokoban with improved percentage of solved tasks and shortened search dynamics. Neat; TIL about Sokoban puzzles. I remember playing Chip's Challenge on Windows 3.1 when I was a kid which had a lot of levels like that.

smcin 2y ago
Sokoban puzzles have a discrete set of actions, typically 8 (move U/D/L/R ; drag U/D/L/R), on a discrete grid.
- airstrike 2y ago
  more like push than drag tbf
passion__desire 2y ago
Jonathan Blow is working on "Sokoban"-Inspired Puzzle Game. I am looking forward to its release.
Modified3019 2y ago
It's definitely a fun little puzzle. I was introduced to it ages ago via "Wyvern" (https://web.archive.org/web/20040225005408/http://www.cabochon.com/ https://web.archive.org/web/20040225005408/http://www.caboch...) where I'd basically sit around playing it and chatting. Wyvern was heavily influenced by Crossfire (https://crossfire.real-time.com/ https://crossfire.real-time.com/) which had a not so functional version. Crossfire itself was influenced by nethack, which apparently also has sokoban levels.

a_wild_dandan 2y ago

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.

jadbox 2y ago
Remarkable indeed, I've been toying with many smaller, unorthodox use-cases for LLMs and continue to be surprised.
- smcin 2y ago
  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.
- jasonjmcghee 2y ago
  Can you say more? Where can I read about some of these alternate use cases?
  - ebri 2y ago
    yes I want to learn about this too! Hadn't thought about it like that.
- littlestymaar 2y ago
  It uses transformers but it's not an llm though.
2y ago

nextaccountic 2y ago

Due to the no free lunch theorem [0], any search algorithm that makes some problems faster will necessarily make other problems slower. How does the worst case for an algorithm like this look like? I think that part of the appeal of A* to me is that I can readily visualize why the algorithm failed at some pathological inputs. [0] https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...

kevindamm 2y ago
Well, it's still using A* and state exploration to validate the plans generated. But, it's generating plans nondeterministically so it is possible it could run in O(\inf). Why didn't they give more details about the Sokoban puzzles being solved? The standard benchmark is the 90 puzzles in XSokoban and there's a Large Test Suite that has a few thousand but many of them haven't been solved by any search or planning system. Even the 90 puzzles in XSokoban were only solved a few years ago (2020?) by Festival (using FESS, a feature-space search in addition to domain-space, state-space). Before that it had been about 20 years of only 57 or so levels solved via search. I see that they measure trace lengths but I would have really liked to see # of XSokoban levels and how many states were examined, to line up with existing research.
reaperman 2y ago
The "No free lunch" theorem does have some prequisites for it to actually apply. > There is no free lunch in search if and only if the distribution on objective functions is invariant under permutation of the space of candidate solutions.
IanCal 2y ago
NFL theorem is frankly silly. It boils down to "you can't predict random numbers". I'm sure it's useful to have formalized but it has no real impact on real world situations because most problems we care about have some kind of structure we can exploit.
- nextaccountic 2y ago

teleforce 2y ago

Previous post and discussions on HN: Beyond A*: Better Planning with Transformers: https://news.ycombinator.com/item?id=39479478 https://news.ycombinator.com/item?id=39479478