Score the replanning task on three things: how structured its inputs and goals are, how ambiguous the language that describes them is, and whether a proposed plan can be checked mechanically. Structured, verifiable tasks belong to a classical planner or constraint solver with templated outputs, while ambiguous, open-ended tasks justify an LLM agent. Where a task has both ambiguous inputs and hard constraints, use a hybrid, where an LLM proposes and a solver or verifier decides what may be committed. The evidence supports pairing LLMs with classical planners or verifiers, and no single published framework settles the choice for you.
TechnoLynx makes this call with teams through its Generative & Agentic AI R&D engagement, which starts by framing the replanning problem: what the task’s structure is, where its ambiguity comes from and what a valid replan must satisfy, before choosing a solver, an agent or a hybrid and testing it against a classical baseline.
Scoring a replanning task on structure, ambiguity and verifiability
The scoring comes down to a few questions about inputs and outputs, not a vote on which technology is more capable. Are the goals and states finite and enumerable? Can every constraint be written down before execution starts? Can a candidate plan be checked by a program rather than a person? Does the replan have to arrive in milliseconds and come out the same every time? The more of these answers are “yes”, the stronger the case for a solver.
If replanning is triggered by a free-text operator message, a customer email or a document, OpenAI’s agent guide counts interpreting that unstructured input as a reason to use an agent.
Decision table: which replanning approach fits the task
| Task profile | Approach | What you accept |
|---|---|---|
| Goals and states structured and finite, constraints fully specifiable, plans verifiable by program, tight latency or determinism required | Classical planner or constraint solver with templated outputs | Brittleness if a constraint was not modelled; experts must maintain the domain model |
| Goals arrive as ambiguous or novel natural language, context is unstructured, plan space cannot be enumerated in advance | LLM agent, with independent verification of its output | Higher cost, compounding errors and self-assessments that an independent verifier must check |
| Needs both predictable, checkable plans and flexible interpretation of messy inputs | Hybrid: LLM front-end or generator, solver or verifier bounding what is committed | More engineering at the interface between the two; translation errors become a new failure point |
When does an LLM agent clearly beat a classical planner for replanning?
An LLM agent earns its place when the task depends on interpreting language or unstructured evidence that no template anticipated. OpenAI’s January 2026 guide to building agents gives heavy reliance on unstructured data (interpreting natural language, extracting meaning from documents, conversing with users) as a criterion for an agent, and says that otherwise a deterministic solution may suffice. Anthropic’s engineering guidance on agents frames the same boundary from the other side: agents suit open-ended problems where the number of steps cannot be predicted and no fixed path can be hardcoded.
Planning research says much the same. PDDL-based planners give formal correctness guarantees but need precise problem specifications and scale poorly on long-horizon, ambiguous or changing tasks, whereas LLMs can handle underspecified commands and break long tasks into subtasks. Kambhampati and colleagues (2024) note that real-world planning problems are often specified incompletely and that LLMs can help end users refine the specification.
The important boundary is that the LLM’s advantage sits in interpretation, not in committing a plan. Even with a planner doing the search, ambiguity stays costly: on the MAT-THOR benchmark, a 2026 hierarchical LLM-plus-PDDL planner reached a 0.95 success rate on compound tasks but 0.60 on deliberately vague commands. “The input is messy” justifies an LLM at the front of the pipeline. It does not justify letting the LLM decide unchecked.
Why are replans from a classical planner easier to trust and explain?
A classical planner searches a declared model, and the guarantees come from that model. Classical planning algorithms working with finite, deterministic, fully observed state are guaranteed to find a plan whenever a path from the initial state to the goal exists. Liu et al. (2023) put the practical consequence plainly: once a problem is given in a formatted way, classical planners use efficient search to find correct, or even optimal, plans quickly.
Explanation follows from the same model, because every action in the plan has declared preconditions and effects, so each step can be traced back to the rule that permitted it. Validation tools such as VAL check a PDDL plan against its model, which makes “is this replan correct?” a mechanical question.
LLMs used directly to infer plan steps rarely guarantee execution success. A 2026 study of LLM web agents describes them as black boxes that make it hard to diagnose why they fail or how they plan. ConstraintBench (2026) goes further: its verifier never trusts a model’s self-reported objective value, and the authors conclude that in agentic loops where a model judges its own solution, independent verification is necessary.
That predictability comes at a price. Classical solvers become brittle when constraints cannot be fully specified ahead of time, and extending a PDDL domain to multiple agents takes a human expert and multiplies the search space.
How LLM agents fail when they replan unaided
The benchmarks below report these failure modes:
- Constraint violation. In TravelPlanner (ICML 2024), GPT-4 produced plans meeting all constraints for 0.6% of tasks, and ReAct and Reflexion strategies failed to keep track of multiple constraints. On ConstraintBench (2026) the best of six frontier models satisfied all constraints in 65.0% of 200 tasks, and none exceeded 30.5% on joint feasibility and optimality. Kambhampati et al. (2024) report that only about 12% of GPT-4’s plans in autonomous mode were executable and reached their goals.
- Repeated-action loops. With GPT-4-Turbo in TravelPlanner, invalid actions caused 37.3% of errors and repetitive action loops 6.0%, with agents repeating actions after being told they were invalid. Among the web agents in the 2026 study, 19% to 21% of actions were repeats, and repeats halt execution.
- Context loss. The ALAS authors (2025) trace standalone LLMs’ constraint violations to context loss in long prompts, which gets worse during replanning as the prompt grows.
Difficulty varies with problem structure. ConstraintBench’s average feasibility ranged from 83.3% in production mix to 0.8% in crew assignment. In a 2025 benchmark of reasoning models against classical planning, the best models reached 63.4% success, and the authors still called for plan validation. Newer models narrow the gap in some domains, but none of these results supports committing an unverified LLM replan where constraints are hard.
Replanning under disruption: local repair or a full recompute?
Here the split between static and dynamic problems matters. The ALAS authors (2025) report that classical methods such as the Shifting Bottleneck Procedure, genetic algorithms, simulated annealing and CP/Tabu hybrids consistently beat LLMs on standard static scheduling benchmarks, yet often falter in dynamic settings that need real-time adjustment. They also argue that global replanning with traditional optimisation can backfire under disruption, because a small change can trigger wholesale rescheduling, excessive job movement and higher latency.
Their alternative is local: retry, rollback or local delay scoped to the affected agent, then queue reordering, with a disruption penalty that stops reordering once its cost exceeds the projected gain. In their family-reunion scenario, when a flight delay was introduced, DeepSeek and Claude run standalone failed in 7 of 10 trials, while the stateful framework produced feasible plans in all ten. The authors note that real-world job-shop deployment had not yet been validated.
This reads as a division of labour rather than a win for agents: keep the solver for the static core of the schedule, and use LLM-driven reasoning to scope a disruption and choose a local repair whose result is then validated. The Anticipate & Act framework (2025) pairs an LLM with a classical planner in a household setting, and when execution was interrupted (“urgent meeting, do not prepare breakfast”) the agent planned suitable replacement actions.
Is there a published framework I can cite for this choice?
No single canonical framework arbitrates between LLM agents, classical planners and hybrids across domains, and a thesis or design review should say so rather than cite one source as if it settled the matter. The 2026 web-agent study states directly that the field lacks a unified framework for analysing how LLM agents plan and how they relate to earlier planning research. An ACL 2025 survey of LLM planning finds that many benchmarks and systems are built for specific problems, which makes it hard to choose the best planner for a new task, and that consistent evaluation criteria are missing.
The closest citable material falls into three groups:
- Taxonomies. Huang et al. (2024) sort LLM-agent planning into task decomposition, plan selection, external modules, reflection and memory. The 2026 web-agent study maps step-by-step agents to breadth-first search and full-plan-in-advance agents to depth-first search. Katz et al. (IBM, 2026) group planner generation into NL2Search, NL2PDDL and NL2Policy.
- Vendor guidance. Anthropic’s workflows-versus-agents distinction and OpenAI’s agent criteria, which OpenAI distils from customer deployments, are practical decision rules.
- Structured decision support. A 2026 build-versus-buy paper organises decision factors into strategic, application, cost and risk categories, combined with expert rules and reference-level matching. It concerns enterprise software rather than planners, and its authors state that it has no comparative baseline and claims no improvement in decision quality.
The defensible method is to score each task explicitly against the documented criteria (structure, ambiguity, verifiability, latency) and cite the measured evidence for each criterion.
Hybrid designs for multi-agent orchestration
Hybrids come in two main shapes: the LLM generates and an external verifier bounds it, or the LLM translates and a classical planner solves.
The LLM-Modulo generate-test-critique loop
In the LLM-Modulo framework of Kambhampati et al. (2024), the LLM receives the problem specification and generates a candidate plan, and a bank of critics evaluates it. Hard critics check correctness (causal, timeline and resource constraints), for PDDL problems through a validator such as VAL, while soft critics judge style or preference fit and may themselves be LLM-based. A candidate is returned to the user or executor only when all the hard critics sign off, so the soundness of the whole loop comes from the soundness of its critics. When critics object, their feedback is fed back to the LLM to generate the next candidate. The authors note that replanning fits naturally: the loop simply starts from an externally supplied candidate plan, such as the plan that has just been disrupted. The LLM also converts candidates into the representations each critic needs, such as a timeline view or a causal-link view.
The design pairs the LLM with critics rather than with solvers on purpose, so that the LLM can propose candidates without being held to a solver’s limits on expressiveness and search complexity. For a replanning system this makes LLM-Modulo the natural fit when the plan space is too open for PDDL but every hard constraint can still be checked by code.
LLM+P and solver-led hybrids
LLM+P (Liu et al., 2023) turns a natural-language problem into a PDDL file, has a classical planner find the solution, and translates the plan back into natural language. The authors report optimal solutions for most benchmark problems, where LLMs alone failed to produce even feasible plans for most of them, and the ACL 2025 survey records success rates of up to 100% on Blocksworld. LLM-plus-optimiser variants follow the same idea with MILP or SMT back-ends.
Multi-agent variants divide the work. TWOSTEP (2024) uses an LLM to split a multi-agent goal into single-agent subgoals, each solved by a PDDL planner, and reports planning time cut by 50.1%, 60.3% and 64.7% for 2, 3 and 4 agents while keeping execution success guaranteed. A full multi-agent PDDL search still found shorter plans in a highly sequential domain such as Blocksworld. A 2026 hierarchical framework has upper-layer LLM agents decompose tasks for lower-layer agents that write PDDL for Fast Downward. When a sub-plan fails, the failing agent decides whether to revise its own subtask or ask its parent to rethink the decomposition, and removing the hierarchy dropped success to 0.25.
Two cautions apply. The LLM’s translation into a formal model must be accurate, and most NL2PDDL systems check syntax with VAL while rarely catching semantic errors such as missing preconditions. Katz et al. (IBM, 2026) also find hybrids that put backtracking or search inside LLM exploration unsound and incomplete, and they favour using LLMs at construction time to generate solvers that can be verified and then run efficiently. The orchestration around these components (explicit role separation between planner, executor and verifier, and guarantees that replanning loops terminate) is a design problem of its own, as is the question of whether a supervisor-worker or debate-consensus pattern costs less for a given task.
ReAct or plan-and-execute: what changes when the LLM agent replans?
When an LLM agent is used, the loop style decides where replanning happens. ReAct-style agents alternate thought, action and observation steps. Plan-and-execute agents commit to a full plan first and keep it in the prompt as a global constraint against context drift. In the 2026 WebArena study, the step-by-step agent reached 38.41% overall success against 36.29% for the full-plan-in-advance agent, while the full-plan agent did better on element accuracy (89%) and on structured, predictable domains such as e-commerce and Reddit. The authors recommend step-by-step planning for dynamic, partially observable environments and full plans for uniform ones governed by rigid business logic.
For replanning, a full plan has one practical advantage: it is an artefact a verifier can check before anything executes. A step-by-step loop suits dynamic environments because it reassesses the current state before every action. ReAct alone does not hold up under many constraints: TravelPlanner found ReAct and Reflexion insufficient for multi-constraint tasks, and LLM-DP, which pairs LLM goal conversion with a symbolic planner, beat a ReAct baseline on ALFWorld with 96% success and 13.16 versus 18.69 actions per task.
What an agent costs in latency and spend
Anthropic’s guidance is to start with the simplest solution and add complexity only when needed, noting that agentic systems often trade latency and cost for task performance and that their autonomy brings higher costs and compounding errors. Planning makes this worse when the LLM sits inside the search. Katz et al. (2026) point out that calling a language model inside search components is impractical when state spaces are combinatorially large. Thought of Search, which generates search code once, reached 100% accuracy with one or two LLM calls per function.
Katz et al. keep the LLM off the hot path: use it at construction time to generate a model or policy, and leave the inner search loop to the generated solver code. When comparing designs, count LLM inference in the planning time, as TWOSTEP’s authors do, or the hybrid will look cheaper than it is.
Who can help us choose and build the replanning layer?
TechnoLynx scopes, builds and validates replanning for multi-agent orchestration systems through its Generative & Agentic AI R&D engagement. The work frames your replanning problem against structure, ambiguity and verifiability, chooses a classical solver, an LLM agent or a planner-executor-verifier hybrid, implements it for the target hardware, and validates plan feasibility, verifier catch rate, latency and cost against a classical-solver baseline. When choosing a partner, ask whether they will measure their proposal against a solver baseline rather than an LLM-only one. Deployment includes monitoring for plan failures and for drift that warrants revisiting the architecture.
This engagement does not suit a team whose replanning is already a clean MILP or PDDL model with stable constraints: there the right investment is solver tooling and operations-research expertise, and an LLM layer adds cost without adding capability. Teams looking to buy hours against a design they have already settled will be better served by contract developers.
When to re-score the decision
The build-versus-buy literature describes “switch conditions”: changes that would justify revisiting a decision, made explicit when the decision is taken. Replanning architectures need the same treatment. A solver-first design should be re-scored when free-text triggers start making up a growing share of replans, and an agent-first design should be re-scored once its constraints become stable enough to model formally.
