11 ms·
Beyond A*: Better Planning with Transformers
- teleforce 3y agoTo the authors, please rename this new algorithm from the boring Searchformer to more interesting name for example Optimus Prime.
- anentropic 3y agoalso because googling for "Searchformer" brings up a different paper and model: https://www.sciencedirect.com/science/article/abs/pii/S0172219023000224 https://www.sciencedirect.com/science/article/abs/pii/S01722... "Planformer" seems unused and would reduce confusion (also since "Search" implies RAG etc which is not what this model is about)
- krallistic 3y ago"Search" has been the name for the A* space. So it makes absolute sense. "Planning" means in the symbolic AI space often something quite in the direction of PDDL/STRIPS/ICAPS planning.
- nick12r55t1 3y agoT*former or T-star
- evanmoran 3y agoT* (T-star) is a great name.
- shrubble 3y agoIt is the copyrighted name of a lens coating by Zeiss Optical, however.
- TeMPOraL 3y agoT1* and T2* are common terms in magnetic nuclear resonance imaging, suggesting Tn* for any integer n should be free of bullshit IP protection. May I thus suggest T10*, following the pattern of a11y and i18n?
- deleted 3y ago[deleted]
- teleforce 3y agoFunny that you mention RAG since the RAG authors had expressed their regret of not using a much better name and the name stucked once it becomes very popular. On second thought, in the spirit of A* perhaps they can rename it to O' short for Optimus Prime but this probably will break most of the databases in the world [1],[2]. [1] Exploits of a Mom: https://xkcd.com/327/ https://xkcd.com/327/ [2] Prime (symbol): https://en.m.wikipedia.org/wiki/Prime_(symbol) https://en.m.wikipedia.org/wiki/Prime_(symbol)
- basil-rash 3y agoI can’t think of any database that doesn’t support the ' character in their varchar.
- remexre 3y agoI think the concern was all the buggy apps that connect to databases will accidentally be getting SQL injected.
- basil-rash 3y agoIf they’re susceptible to injections this is the absolute least of their problems. In fact their DB is already dropped.
- rdedev 3y agoAt this point we need a website cataloging all transformer related names.
- leosanchez 3y agoMegatron would be better IMO.
- verticalscaler 3y agoClearly Megatron because LLMs are decepticons.
- leosanchez 3y agoYes that was my reasoning :)
- wiz21c 3y agojust deceptive
- deleted 3y ago[deleted]
- moffkalast 3y agoNvidia: "We'll pretend you didn't say that."
- johndough 3y agohttps://github.com/NVIDIA/Megatron-LM https://github.com/NVIDIA/Megatron-LM > Megatron is a large, powerful transformer [...]
- FooBarWidget 3y agoWouldn't that be a trademark violation?
- nkozyra 3y agoI think Searchformer is kind of catchy. :shrug:
- deleted 3y ago[deleted]
- willcipriano 3y agoSacagawea is my proposed name.
- jan_Sate 3y agoWouldn't that be an overkill to train a model specifically for that? I wish someone could come up with an algorithm that would outperform a trained model. This way we would actually understand how it works.
- jvanderbot 3y agoWell in this case, A* outperforms in terms of funding a solution when it exists. It's just the transformer produces a solution faster, but misses some.
- SnowflakeOnIce 3y agoNote that the paper doesn't measure execution time of the A* or Transformer-based solutions; it compares length of A* algorithm traces with length of traces generated by a model trained on A* execution traces. I suspect that the actual execution time would be far faster with the A* implementation than any of the transformers.
- bamboozled 3y agoWas the pun intended ?
- wongarsu 3y agoShortest path search is a very well understood problem, and for "simple" cases A* is the gold standard. You could probably tweak the heuristic used by A* to the problem to get similarly good results (at much lower compute cost than running what amounts to an LLM with huge context length). But this is a toy problem. The interesting thing about the paper is that you might be able to get good-performing search algorithms for any problem with a cookie-cutter process, instead of spending many man-hours tweaking a hand-written search algorithm. It might also be possible to easily adapt it to much more complex search problems, like cooperatively evading other agents navigating in the same space.
- Moldoteck 3y agodo you want the solution faster or more precise? Depending on the answer you would pick either A* or this model
- jvanderbot 3y agoI am extremely optimistic about using learned heuristics in discrete algorithms like A* or Focal search or the various families of ILP. In most modern discrete optimization libraries, e.g. CPLEX it's the heuristics and tuning that explain the performance. I'm less understanding of using a end to end learning approach to replace a well understood optimal search routine, but that might be pearl clutching. It just seems to me the authors missed that opportunity.
- boesboes 3y agoI think it is just the bubble/hype effect around transformers and AI. I might try to use transformers to solve tic-tac-toe and apply for some VC moneys. In a few years we'll all be writing about how much more efficient actual code is compared to AI perhaps ;)
- losvedir 3y agoEveryone on Transformer News will be talking about the latest web framework for GPT-7 and how to horizontally scale their system to handle dozens of requests a second, and how when you need to scale beyond that it will "be a good problem to have". Meanwhile, you and I will be talking about how our low-level, handwritten Ruby on Rails code is so much faster and more efficient, and closer to the metal so you can understand what's _really_ going on.
- nvrmnd 3y agoI agree, learning admissible heuristics will retain worst case performance, which has always been the measuring stick for these algorithms. It's not at all uncommon to find faster solutions for the average or even p99 cases that cannot provide guarantees on the worst case.
- SnowflakeOnIce 3y agoHow would one go about proving that a learned heuristic (something from an AI model) is in fact admissible?
- eterevsky 3y agoWhile A* could be used to solve Sokoban, wouldn't some sort of Monte-Carlo Tree Search be better at it? I wonder how would it compare to this model.
- espadrine 3y agoThe part of MCTS that matters for solving it is the Bellman equation, which is a component of the Bellman-Ford shortest-path algorithm, so all of those methods are part of a continuum. Which one works best is pretty sensitive to the exploratory decisionmaking algorithm: do I search this cell first, or that one? That heuristic is the differentiator, whether it is put on top of a Dijkstra-style algorithm (A*) or a Bellman-Ford-style algorithm (MCTS).
- abdellah123 3y agowhat's with Cornell University??! They produce constant amazing papers and projects on AI
- losvedir 3y agoWhat makes you say Cornell? Isn't this from Meta?
- tekknolagi 3y agoI think it's either a joke or misunderstanding about arxiv
- bravura 3y agoMachine Translation used to involve complicated grammatical decoding, using search. Now we just use transformers for MT, with much simpler decoding that doesn't really need search. Perhaps we can reach full inception. Let's use our current best-of-breed predictive models to learn heuristics for neural architecture search (NAS) and search for new neural blocks (better than transformer and mamba).
- FeepingCreature 3y ago"Every time I fire a linguist, the performance of the speech recognizer goes up." --Frederick Jelinek
- xg15 3y ago...and finally enter a world where literally no one understands anymore how the technology works, not even the people developing them. Singularity, here we come...
- zwirbl 3y agoWe could then go on to create something akin to the mechanicum, create the position of tech priests and have them pray to the machine god on on our behalf
- amelius 3y agoIs someone keeping a list of classical algorithms or NP complete problems that are now better performed using deep learning?
- scscsc 3y agoFor your convenience, here is the list of NP-complete problems where "AI" works better than the state of the art in the worst case:.
- cs702 3y agoThank you for that. I needed the laugh :-)
- Davidzheng 3y agoProbably soon AI will be able to find improvements to most of them? Like using AI to do search in algorithm space
- thomasahle 3y agoFor all we know, some of the current best (still exponential) algorthms were guided by AI. If a mathematician solves a problem using mathematica, they don't usually write in the paper what tools they used.
- jvanderbot 3y agoAI + classical algorithms is my sweet daydream. Trained heuristics (even better domain specific ones), deployed for classical A*, ILP families, focal search, etc etc. That is going to be really amazing.
- amelius 3y agoEven solving large linear systems would already be amazing. But a SAT solver would be nice too :)
- k2xl 3y agoShameless plug, but if you are interested in Sokoban type games check out https://thinky.gg https://thinky.gg . Features a fun Sokoban variant (called Sokopath) as well as another NP hard variant called Pathology (goal is to get from point A to point B in the shortest amount of steps). Many in the community have tried to create various solvers and things get very hard once the grid gets to be over 5x5. However, some interesting levels with very high maximum step counts have been discovered by the thinky communnity (via simulated annealing)
- nikolay 3y agoThank you! Great games! Super nice execution! I love it!
- paidcompute 3y agoPretty impressive
- light_hue_1 3y ago> 26.8% fewer search steps than standard A∗ search So you're saying I shouldn't read this paper? A* is not particularly good. If all the algorithm can do is mirror it by training on its output what's the point?
- casebash 3y agoYeah, at first I read that as it using 26.8% of the original steps, but reducing the number of steps by 26.8% is not that impressive. I wonder whether it actually reduces total search time as there is added overhead of running the neural network.
- light_hue_1 3y agoThere's absolutely no way it reduces search time. A* is trivial to run per timestep. The time must be thousands to maybe hundreds of thousands of times slower. I publish in this area and this is a common thing for reviewers to bring up when authors don't report wall clock time. And then for papers to be rejected. What's the value in making an algorithm that's drastically slower? Not much.
- ta8645 3y ago> What's the value in making an algorithm that's drastically slower? Perhaps as an important stepping stone? Deferred optimization and all that.
- light_hue_1 3y agoSounds like half baked research that shouldn't have been published then. Papers are supposed to be an actual advance not a tech preview of something that might be useful maybe if someone else figures it out. Some people call the flag planting. You publish something that doesn't work with keywords you suspect will be important in the future. Then hope others will cite you.
- ultra_nick 3y agoIf transformers can plan, then AGI only requires better education...
- throwuwu 3y agoThere’s a lot more pieces, agency being a big one but online learning is required too and many other layers beyond that.
- th0ma5 3y agoThat's probably the foreseeable future, ingesting ever larger amounts of data hoping it prevents hallucinations.
- nyrikki 3y agoApproximating exhaustive search is not logic or causality.
- adamnemecek 3y agoBoth ml and A* are integral transforms.
- Salgat 3y agoWhat do you mean by that?
- adi4213 3y agoFor the auditory learners, here is this paper in a summarized audiobook format : https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30d6f https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30...
- syassami 3y agoThanks for sharing, I've been looking for an app like this for ages.
- adi4213 3y agoThank you so much for your comment! Apologies if my comment came off like an ad - I have mild dyslexia and struggle to keep up with ML papers; I hope others also find this useful! If you have any feedback or issues, feel free to email us at support [at] trurecord.com
- buywiseaccounts 3y ago[flagged]
- softfalcon 3y agoI wonder if they tried the modified J* algorithm (an optimization of A* for games graph/path-finding) before going down this research route. It's in Game AI Pro 2 [0] if anyone is curious. [0] https://www.amazon.ca/Game-AI-Pro-Collected-Professionals/dp/1482254794 https://www.amazon.ca/Game-AI-Pro-Collected-Professionals/dp...
- mysterydip 3y agoI love these books (and nice to see Steve Rabin still doing them), but $120 for an ebook? That's unexpected.
- hlfshell 3y agoIf you consider it like a textbook (very small niche audience for very specialized knowledge) it does kind of match up due to the small expected volume to sell. Authors still gotta eat.
- deleted 3y ago[deleted]
- setr 3y agoWorse yet… the game ai pro books are entirely free for digital copies. You’d basically be paying $120 for it to be stitched together into a single pdf, instead of one per chapter http://www.gameaipro.com/ http://www.gameaipro.com/
- cjaybo 3y agoThat’s one expensive imagemagick command!
- leeoniya 3y agoalso https://github.com/anvaka/ngraph.path https://github.com/anvaka/ngraph.path
- ogogmad 3y ago
- fentedhuff 3y ago[dead]
- tintor 3y ago"26.8% fewer search steps than standard A∗ search" So, slightly better than A* which is far from SOTA on Sokoban (https://festival-solver.site/ https://festival-solver.site/). What is impressive in this paper? Why is this on Hacker News?
- hlfshell 3y agoWhat? Someone somewhere tried to do something and wasn't the most optimal possible solution? We should just ban their account honestly. Comments like these are antithetical to a strong technical sharing community.
- agumonkey 3y agoEspecially considering the amount of trivial mainstream tech articles nowadays. It's cool to see more algorithmic topics.
- pqdbr 3y agoI agree. OP's comment could be quickly rewritten into something useful and just by changing the tone, for example: "26.8% fewer search steps than standard A∗ search" For reference of prior art, it's slightly better than A*, which is far from SOTA on Sokoban (https://festival-solver.site/ https://festival-solver.site/).
- airstrike 3y ago> Why is this on Hacker News? Anything that is on HN is on HN because the community likes it
- mindwok 3y agoSome people find things interesting regardless of if they break records.
- theygotit 3y ago[dead]
- 3y ago
- tulio_ribeiro 3y agoAmazing. Now do that to sorting algorithms.
- gene-h 3y agoThere has been more interesting work on using transformers for robot motion planning[0]. Getting a robot arm from point a to b without hitting stuff is a very difficult problem, the problem is both high dimensional and continuous. Previous planning methods are both computationally intensive and not very good. This is one reason why robot motion appears 'unnatural' and robots generally being bad at many tasks we'd like them to do. This approach appears pretty competitive with other planning methods, planning near optimal paths faster. [0]https://sites.google.com/ucsd.edu/vq-mpt/home https://sites.google.com/ucsd.edu/vq-mpt/home
- gromneer 3y agoInformative comments like this is the reason I go to the comment section before reading the article.
- goggy_googy 3y agoThis paper reminds me of the Neural Network Diffusion paper which was on the front page of HN yesterday in the sense that we are training another model to bypass a number of iterative steps (in the previous paper, those were SGD steps, in this one, it is A* exploration steps). On a different note, they choose such a bad heuristic for the A* for Sokoban. The heuristic they choose is "A∗ first matches every box to the closest dock and then computes the sum of all Manhattan distances between each box and dock pair". I played Sokoban for 20 minutes while reading the paper and I feel like this is a very poor exploration heuristic (you often need to move boxes away from goal state to make progress).
- nyrikki 3y agoI have a hunch they made their decision to train off that particular type of A* traces to avoid an exponential number of embeddings.
- cptroot 3y agoI find it hard to believe that all the heavy-weight data processing and GPU computation really make a constant factor reduction in search steps worth it.
- SnowflakeOnIce 3y agoIt's also not clear to me how one would determine that an ML model-generated plan is indeed optimal, or how far from optimal it is. A*-based approaches give you these things.
- thesz 3y agoCan transformers prove absence of the solution? E.g., did they tried to train them on the unsolvable problems? I once tried my hands on the PCB routing and here's a simple problem of simultaneous multipath search that is unsolvable: A.....b B.....a A and B are starting points and a and b are goal points, respectively for A and for B. It is a 2xN maze, the orders of stating and goal points are reversed. The search algorithm sometimes required to prove absence of the solution. A* can do that, transformers? I do not think so.
- nyrikki 3y agoIn this case, A* is in a finite, bounded 3030 grid. As A is just a type of branch and bound algorithm, which the degenerate form is exhaustive search. Which should be able to 'prove' the absence of a path by simply failing to find one before exhausting all paths. PCB routing is not as simple as this problem for real world problems. Digging into why TSP with a positive integer Euclidean metric is NP-C but with a real valued Euclidean metric is NP-hard may be one way to think about it. But if you choose the right metric and huristic, in what approximates a finite space, A* can run an exhaustive search in practical time. It is probably a good idea to separate search space exhaustion from no-instance proving which in the case of decision problems can cause confusion. If you think of NP as relating to yes-instances, co-NP is the no-instances.
- thesz 3y agoYou are mathematician, am I right? Your answer is correct (sorta, as far as I am concerned) and does not add to the discussion I tried to open. Your answer does not show anything related to the ability of transformers to prove absence of solution, to be precise.
- nyrikki 3y agoNo, just a programmer that has to apply math. Transformers can only do what is called weak negation. if (not (goal X)), then (assert not x) One example I have seen is: "you can cross if you have no information on a train coming” VS: "you can cross if you have evidence that no train is coming" See the difference? As to what 'transformers' can encode is ambiguous and depends on many factors but here is some light reading. https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00493/112604/Saturated-Transformers-are-Constant-Depth https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00493... https://arxiv.org/abs/2204.06618 https://arxiv.org/abs/2204.06618
- tannhaeuser 3y agoPlanning is already well taken care of by established techniques ranging from graph search, SAT-solvers, OR, Prolog, etc. The point usually is optimization over multiple feasible alternatives, which I have a hard time seeing transformers being up to. I see the role of LLM techniques more in translating natural language descriptions to executable programs - but then Prolog is already very close, it being designed for classic NLP after all.
- 3abiton 3y agoIt would be interesting to see the comparison between Prolog and a similar purposes LLM
- tannhaeuser 3y ago> Searchformer [...] solves previously unseen Sokoban puzzles 93.7% of the time, while using up to 26.8% fewer search steps than standard A∗ search ... [and] significantly outperforms baselines that predict the optimal plan directly with a 5-10× smaller model size and a 10× smaller training dataset. So this can be interpreted as a generic statement to say there might be progress during learning iterations (compared to its own arbitrary first iteration baseline). I think it's important to not getting carried away and assume the recent immense progress in generative AI is just easily repeated for any other AI task. There's also quantum computing having been advertised for over a decade now for a break through in planning and optimization efficiency. > 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. Worth mentioning that Sokoban is nowhere near a complex decision making task let alone state of the art in an academic or commercial planning/optimization context. > A∗'s search dynamics are expressed as a token sequence outlining when task states are added and removed [...] during symbolic planning. Go ahead and compare against eg. Quantum Prolog's readily available container planning problem and solutions [1] then to generate exactly that in the browser - a plan with symbolic actions to perform - or alternatively, a classic Graphplan or CLIPS planning competition problem. [1]: https://quantumprolog.sgml.io/\ https://quantumprolog.sgml.io/\*