An LLM Teaches a Planner to Get by With Polynomial Memory and Solves 1709 of 1890 Tasks

Classical planners hit the memory wall before the time wall. Heuristic search stores a list of visited states, and that list grows exponentially even when the heuristic is nearly perfect. The authors of a new arXiv paper propose dropping the list altogether. With policies written by a language model, their procedure solved 1709 of 1890 test tasks from the IPC 2023 Learning Track and the Autoscale Agile set. That is more than LAMA, BFWS and Levitron solved, and most tasks finished within a second and 100 MiB.

A policy with registers instead of a list of states

Rather than build a universal search, the authors learn to control the search. For each domain, one specification is written in the form of an "indexical policy". This is a generalized policy with registers that hold objects, plus modes that set the order in which rules are applied. The key addition is the choose rule. It loads an object into a register and sets a backtrack point, and a single suitable candidate is enough. All the other rules must work under any outcome, and they do not require search.

The paper's main result is theoretical. Structural termination rules out infinite executions of the policy. The authors show that it also bounds any execution by a polynomial in the number of objects. It follows that depth-first search finds a plan in polynomial memory, however large the state space is, and no list of visited states is needed. The price is paid in time. Time is exponential only in the choice depth, that is, in the number of genuine choice points along the execution. Therefore any class of tasks that such a policy solves lies in NP, and in P when the choice depth is constant.

Where the language model comes in

The policies are not written by hand. A language model generates them in a loop with counterexamples. In each round, the loop certifies termination, checks the policy on training tasks, and makes sure the choice depth stays small. That last condition matters because the choice depth determines how much time the search will consume. The abstract does not say which model was used.

Figures from the abstract

• 1709 of 1890 test tasks solved (about 90%); 181 tasks remained unsolved.
• Benchmarks: IPC 2023 Learning Track and Autoscale Agile.
• The competitors LAMA, BFWS and Levitron solved fewer.
• Most tasks were solved in under a second and within 100 MiB.
• Memory is polynomial, with no list of visited states.
• Time is exponential only in the choice depth.
• Classes of tasks solvable by such policies lie in NP, and in P when the choice depth is constant.

Where this could be useful

The approach looks strongest where memory is more expensive than CPU time: embedded planners, robots, and systems that solve tasks of the same type on different inputs. There is also a practical insight in the division of labor. The language model writes a verifiable policy program, and the termination certificate gives a guarantee that a plan produced directly by a model does not have. The limitations are also clear. A policy is needed for each domain, training requires a set of training tasks, and the figures come from the authors themselves in a preprint, without independent verification. Even so, this hybrid already delivers a noticeable memory saving on standard planning benchmarks.