Textual Planning with Explicit Latent Transitions

The idea

Planning needs a transition model that predicts how each action changes the current state. When a large language model plays this role, each next state is generated token by token, with a full forward pass per token, which makes multi-step lookahead and search expensive in latency and cost.

EmbedPlan keeps the semantic encoding in a frozen LLM and learns only the cheap dynamics. It predicts the embedding of the next state with a small network and returns the closest real state, so every prediction is a real state. Because the same head can be trained over any encoder, the framework also serves as a controlled probe of what a frozen text representation supports for learning dynamics.

How it works

• A frozen LLM encoder embeds a natural language description of the state and of the action, for example a Blocksworld state and the action pick-up(C). Each state prompt holds the problem and goal description followed by the facts that hold.
• Learned state and action heads project both embeddings into a 128-dimensional latent space.
• A residual MLP with fewer than 500K parameters predicts the embedding of the next state.
• The nearest state in a candidate pool, by cosine similarity, is returned as the successor. Fed back as the next input, it supports multi-step rollout.
• Two contrastive objectives train the head: state prediction, which identifies the correct next state among candidates, and action disambiguation, which separates the effects of different actions on the same state.

EmbedPlan is a transition component, not a complete planner. Search composes many transitions, and the paper studies the single transition that search queries repeatedly. Training is per domain: a one-time embedding pass plus about 15 minutes of training.

How it was tested

The data are nine classical PDDL domains from ACPBench, with states rendered as natural language: Blocksworld, Depot, Ferry, Floortile, Goldminer, Grid, Logistics, Rovers and Satellite. Together they give 2.97M transitions over 67 problems (259K unique states). A domain fixes the action schemas, and a problem fixes the objects, the initial state, and the goal.

Four frozen encoders are compared: MPNet (all-mpnet-base-v2), BGE-M3, Qwen2.5-7B and Llama-3.3-70B. Results use Llama-3.3-70B unless another encoder is named.

Six protocols form a ladder of exposure, ordered by what the test data share with training:

• Interpolation: held-out transitions of observed problems.
• Plan-Variant: unseen optimal plans of observed problems.
• Extrapolation: unseen problems of an observed domain.
• Multi-Domain: unseen problems, with one model for all nine domains.
• Cross-Domain: an unseen domain, after training on one other domain.
• Leave-One-Out: an unseen domain, after training on the other eight.

Every query is ranked against 128 states, the true successor and 127 distractors. The reference methods keep the head and the pool and vary only the state representation, from no-change floors to lifted STRIPS induction, which serves as an oracle upper bound.

What it finds

Within observed problems, EmbedPlan has the properties search needs. Hit@5 is 99.7% with Llama-3.3-70B. When the candidate pool grows to every observed state of the domain, Hit@5 falls from 100.0% to 86.9% on Ferry (46,205 states) and from 99.9% to 74.9% on Logistics (13,373 states). Snapping each prediction to the nearest real state keeps multi-step rollout within 92–99% of the accuracy obtained with the true state at each step.

Within observed problems, EmbedPlan matches or beats every LLM tested. Given the identical ranking task over the same 128 candidates, GPT-5.4 selects the true successor for 44% of Ferry and 92% of Logistics queries, against 99.0% and 96.3% for EmbedPlan. The comparison is matched in task, not in information: EmbedPlan has observed other transitions of the same problems, whereas the LLM is zero-shot. It ranks successors 101× faster end to end than generation through an LLM API (1.9 s per transition), and takes about 0.17 ms per transition with cached state embeddings.

Accuracy falls with each step down the exposure ladder. On unseen problems of an observed domain, Hit@5 is 54.6%, 14 times chance, and it varies widely by domain (26–76%). Larger encoders extrapolate better, from 26.8% for MPNet to 54.6% for Llama-3.3-70B, but none closes the gap. On unseen domains, Hit@5 is 6.6% (Cross-Domain) and 9.2% (Leave-One-Out), near the 3.9% chance level.

With the head, data and pool fixed, the state representation decides transfer to unseen problems. On Ferry, Logistics and Goldminer, character 3–5 grams of the same text reach 79.4% Hit@5, against 56.8% with Llama-3.3-70B embeddings, and lifted STRIPS induction, given each state's symbolic facts, reaches 99.8%. On these templated states an action edits only a few facts of an otherwise identical text, which sparse and symbolic representations capture directly and a pooled LLM embedding barely registers. The paper names a concrete target for transfer to new problems: an object-aware, order-invariant state encoder.

Limitations

• EmbedPlan is a transition component for discrete, domain-specific settings, not a domain-general planner, and must be trained per domain because cross-domain transfer fails.
• Retrieval assumes a candidate pool that contains the true successor.
• The domains are templated, so the paper has not yet tested the regime the text interface is meant for: states without a clean literal decomposition, where symbolic induction and lexical features would break.
• Pool scaling, multi-step rollout, and LLM ranking are measured within observed problems, and rollouts cover short test trajectories (mean 2.2 steps).
• Extrapolation rests on one or two held-out problems per domain, and the reference comparison covers three domains, without ablating the problem and goal text that every prompt shares.
• Integrating EmbedPlan into beam or tree search over long horizons on held-out problems is the direct next step.

Use it on your data

The code includes EmbedPlan as a scikit-learn style estimator for any domain whose states and actions can be written as text, such as planning problems, game logs, web or UI agent traces, or lab protocols.

• fit learns from (state, action) pairs and their next states, with optional groups such as problem ids.
• predict returns the most likely next state as text, ranked among candidate states, and rollout predicts several steps, each snapped to the nearest real state.
• evaluate follows the paper's protocol, 128 candidates per query, and reports the chance level of the same pools.
• The encoder can be a hashing encoder of word n-grams that needs no download, any sentence-transformers or Hugging Face model name, or your own function from texts to vectors.

Try it with no install in the Colab notebook, or start from the repository. On unseen problems, expect lower accuracy than on seen ones: that is the paper's main finding.

Results by protocol

Hit@5 (%) with the Llama-3.3-70B encoder, mean ± SE across the nine domains. Every query is ranked against 128 candidates, so chance is 3.9%. Rows are ordered by what the test data share with training, and the gain is over chance in percentage points (pp). Plan-Variant faces the hardest distractors. From Table 5 of the paper.

Terms

EmbedPlan

A transition model built on frozen text embeddings: it embeds natural language descriptions of the state and the action with a frozen LLM, predicts the embedding of the next state with a lightweight learned network, and returns the closest real state.

Transition model

A model that predicts how each action changes the current state, which planning requires.

Hit@k

The fraction of queries whose true next state ranks in the top k of a candidate pool. Unless stated otherwise the pool holds 128 states, the true successor and 127 distractors, so chance is 3.9% for Hit@5 and 0.8% for Hit@1.

Head

The learned state and action projection heads and the transition network, together. Only the head is trained, and the LLM encoder stays frozen.

Snapping

In multi-step rollout, each state prediction is replaced by the nearest real state the model retrieves, right or wrong, and that state becomes the next input.

Domain and problem

A domain fixes the action schemas, and a problem fixes the objects, the initial state, and the goal.

Grounded action

An instance of a lifted action schema with its objects filled in, such as pick-up(C) for the schema pick-up(?x).

Interpolation

The protocol that trains on 80% of a domain's transitions and tests on the other 20%, held out at random, so test transitions come from observed problems, with distractors from the whole domain.

Plan-Variant

The protocol that trains on some optimal plans and tests on other optimal plans of the same problems, with distractors from successors along alternative optimal plans, the hardest distractors the paper uses.

Extrapolation

The protocol that trains on about 80% of a domain's problems and tests on the other 20%, so test transitions come from unseen problems, with distractors from the query's own problem.

Multi-Domain

Extrapolation with one model for all nine domains at once.

Cross-Domain

The protocol that trains on one domain and tests on another, with distractors from the target domain.

Leave-One-Out

The protocol that trains on eight domains and tests on the ninth, with distractors from the target domain.

Identity and Offset

Two non-learned floors that need no training. Identity predicts the current state's embedding, and Offset adds the mean training displacement of the ground action or of its schema.

Lifted STRIPS induction

A reference method that infers each action schema's add and delete effects from the symbolic facts of each state. It serves as an oracle upper bound.

Action disambiguation

A training objective that separates the effects of different actions on the same state: the true action must yield a prediction closer to the next state than up to 50 alternative actions applied to the same state.

Questions

Citation

@article{shlomi2026textual,
  title   = {Textual Planning with Explicit Latent Transitions},
  author  = {Shlomi, Eliezer and Levy, Ido and Shapira, Eilam and Katz, Michael and Uziel, Guy and Shlomov, Segev and Mashkif, Nir and Reichart, Roi and Keren, Sarah},
  journal = {arXiv preprint arXiv:2602.04557},
  year    = {2026}
}