A new planning algorithm finds valid plans without storing the states it visits, and it still beats specialized search engines on a standard test suite.
Classical AI planners that search for step-by-step solutions typically keep a running list of every state they have already checked, which is how they avoid repeating work, but that list can balloon exponentially as problems grow. Researchers built a system that instead learns a compact "indexical policy," a small per-domain rulebook with registers that track objects and a single explicit backtracking step called "choose." A language model generates and refines these policies in a loop that checks for infinite loops and verifies correctness against training problems. The result is a depth-first search that needs no memory of past states, just a polynomial amount of space, with runtime cost limited to the number of real decision points along the way.
Memory, not computation, is often the real bottleneck for planning algorithms running at the edge or inside resource-constrained robots and agents. On the IPC 2023 Learning Track and Autoscale Agile benchmark suite, the method solved 1,709 of 1,890 tasks, more than established planners LAMA, BFWS, and Levitron, most in under a second and under 100 MiB. That is a rare case of a method winning on both accuracy and the resource metric planners usually sacrifice.
Learned heuristics have a long history of acing the benchmark they were tuned on and stumbling outside it, so the real test is whether these policies hold up on planning problems nobody wrote a training set for.