New method uses frozen embeddings to speed up AI planning by 1000x

Planning with large language models has a fundamental speed problem: generating each future state requires token-by-token prediction, making it expensive to explore multiple possible futures. A team of researchers now proposes a radically faster alternative that sidesteps this bottleneck.

How EmbedPlan works#

The approach, called EmbedPlan, rethinks the transition model—the component that predicts how an action changes the current state. Rather than querying an LLM repeatedly, EmbedPlan embeds both state descriptions and actions using a frozen (unchanging) language model. A lightweight learned network then predicts the embedding of the resulting next state directly in that embedding space. Finally, the model retrieves the closest real state from its candidate set.

This design offers a secondary benefit: because the network operates on top of any encoder, it provides a controlled way to test how different text representations affect the model's ability to learn transitions.

Performance on training data#

The team evaluated EmbedPlan across nine classical planning domains under increasingly challenging conditions—from holding out just transitions to withholding entire domains. The results on seen problems are strong: the model ranked the true next state in its top five predictions nearly always, and maintained 92–99% single-step accuracy even when predicting several steps into the future using only its own outputs. Most importantly, it processes transitions in roughly 0.17 milliseconds with cached embeddings, compared to the far slower cost of LLM queries.

When given the same candidate states as GPT-5.4, EmbedPlan selected the correct next state more reliably while running hundreds of times faster.

Limits emerge on new problems#

Performance drops noticeably when the model encounters unseen problems, and falls near chance-level accuracy on entirely unseen domains. Diagnostic experiments revealed that this ceiling traces back to the state representation itself rather than limitations in the learned transition mechanism—suggesting that improving the embedding method could unlock further gains.

Why this matters#

The work points toward practical speedups for planning with language models. By replacing repeated LLM calls with a lightweight embedding-based lookup, EmbedPlan opens the door to exploring larger solution spaces without the computational cost that has historically plagued this class of problems.