Planning with LLMs and classical solvers: LLM proposes, solver disposes

LLMs are bad at long-horizon planning. Not occasionally wrong: in the LLM+P evaluation, LLMs failed to produce even feasible plans on most benchmark problems, while a classical planner found optimal plans once the same problems were written in PDDL. The bottleneck was never search. It was translation, getting the problem out of natural language and into a form a solver can see.

That is the neurosymbolic division of labor I keep coming back to. LLMs handle the parts of planning that are ill-posed, ambiguous, or preference-laden. Solvers handle the parts that are well-posed and combinatorial. LLM proposes, solver disposes.

The field map: where the search lives

Three lines of work converge on this territory, and they differ in where the search happens.

• Search as prompting. Tree of Thoughts and Language Agent Tree Search put search structure inside the LLM loop, using the model as both generator and value function.
• LLM as translator. LLM+P keeps the LLM at the edges of a classical planner: parse, solve, translate back.
• Modeling as the bottleneck. DCP-Bench-Open and CP-Agent are the constraint-programming line: LLMs write executable models for real solvers such as Google OR-Tools CP-SAT, and the open question is how close the model is on the first try.

The first line searches inside the model's token stream. The second searches in a solver's state space, with optimality guarantees. The third is where they meet: the LLM still proposes, but proposing means writing a model, and the solver's verdict is executable feedback. I laid out the surrounding agent design space in the agent taxonomy overview.

Close read: LLM+P, the translator pattern

LLM+P (Liu et al., 2023) is the cleanest statement of the translator pattern. A natural-language description of a planning problem goes in. The LLM rewrites it as PDDL. A classical planner finds a solution. The LLM translates the solution back into natural language.

The results are stark: optimal plans for most problems through the pipeline, versus LLMs failing to give even feasible plans on their own for most problems. The benchmark covered common scenarios like logistics and block worlds, where the structure is simple enough to formalize and search is easy once modeled.

LLM+P gets the division of labor right. The LLM never tries to search. It does the two things it is actually good at: reading an underspecified problem statement, and writing fluent prose about a plan it did not find. Everything in between belongs to a planner that can prove optimality.

Its limits are equally instructive. PDDL assumes the world can be fully specified up front. Real planning runs against a changing world, with costs and constraints that resist formalization and preferences that are never stated once.

Close read: ToT and LATS, search as prompting

Tree of Thoughts (Yao et al., 2023) generalized chain-of-thought into explicit search: the model generates multiple candidate thoughts, self-evaluates them, and backtracks when a branch is dead. On Game of 24, GPT-4 with chain-of-thought solved 4 percent of tasks; ToT reached 74 percent. The lesson was that deliberate exploration beats greedy decoding when initial decisions matter.

LATS (Zhou et al., 2023) extended that to agents by wrapping the LLM in Monte Carlo Tree Search, with LM-powered value functions, self-reflections, and environment feedback. Reported results include 92.7 percent pass@1 on HumanEval with GPT-4 and strong WebShop performance with GPT-3.5.

LATS matters for two reasons: search structure pays off even inside the model, and the loop is grounded by the environment rather than pure self-evaluation. The gap I care about is that LATS searches over actions. For scheduling and resource allocation, the action space is huge and the constraints are the hard part. Token-level search is a weak way to respect constraints; that is what constraint solvers exist for.

Close read: the constraint-modeling line

This is the line closest to what I build. DCP-Bench-Open (Michailidis, Tsouros, and Guns, 2025) gathers discrete combinatorial problems from the CP and OR communities and asks LLMs to write executable models in three frameworks at different abstraction levels. Findings: a high-level Python-based framework performs best, and prompt-based plus inference-time compute techniques raise accuracy up to 91 percent. Modeling, not solving, is where LLMs lose points.

CP-Agent (Szeider, 2025) closes the loop. A ReAct-style Python coding agent with a persistent IPython kernel and a project prompt under 50 lines writes a model, executes it, reads the solver's feedback, and refines. After cleaning up systematic ambiguities in the CP-Bench specs, it reached perfect accuracy on all 101 problems. Two findings stand out: minimal guidance beat detailed procedural scaffolding, and explicit task-management tooling had mixed effects.

CP-Agent makes the division of labor literal: the solver is not a consumer of the LLM's answer, it is a critic inside the loop. Every failed solve is a signal to rewrite the model.

My position: propose with language, dispose with a solver

The pattern I keep returning to:

LLM:    parse, model, propose        (ill-posed part)
solver: search, optimize, prove      (well-posed part)
LLM:    repair, explain, negotiate   (feedback part)

If there is one mistake in most agentic planning work, it is reaching for a bigger model or a longer chain-of-thought when the problem is already well-posed. That is a solver's job. The LLM's job is upstream of the solve: extracting constraints that were never written down, making modeling choices, and translating results back into decisions a human can review.

The open problem is the middle: modeling. LLM+P showed translation works when the formalization is trivial. DCP-Bench-Open shows modeling accuracy is where LLMs still lose points, and CP-Agent shows solver feedback closes most of that gap. So the practical recipe is an agentic loop around a deterministic core: LLM writes the model, CP-SAT solves it, and the diff between what was asked and what was solved feeds the next proposal.

The counterpoint, because the recipe has a failure mode: sometimes the solve is not worth its modeling cost. On small or degenerate instances, writing and debugging a CP model costs more than the search saves. A twelve-task schedule with loose deadlines is mostly precedence structure, and longest-path math over the graph answers it in milliseconds; a solver adds nothing except a new place for the model to be wrong. My rule for whether a re-plan earns a solve: if the instance has real resource contention or coupling constraints the graph algorithms cannot express, it goes to the solver. If it is mostly precedence with slack, the graph answer is the answer, and the model's effort belongs on the ill-posed parts.

I would also keep the search-as-prompting tools, but in a narrower role: exploring the ill-posed frontier of a plan (what if demand doubles, what if a resource dies) rather than searching for the plan itself. That keeps token-level search where it has leverage and gives the hard combinatorial core to a real solver.

Where this lands in my own work

This is the design lens I am applying at PiPlan.ai. Goals become typed graphs, so the modeling step is explicit instead of buried in a prompt. Adaptive re-planning re-derives the critical path as reality changes, and I want to be precise about what that is today: graph algorithms, a NetworkX critical-path computation over the typed graph, not a constraint solver. The translator-plus-solver framing does not stretch over a CPM update. There is no search to dispose of; the re-plan is longest-path math, deterministic and cheap. CP-SAT is the candidate solver for the cases that outgrow that, and whether it earns a place in the re-planner is what the benchmark below is for. The agent harness runs proposal-first review: proposals come first, a review layer disposes, and only the survivors move forward. That ordering is the whole argument of this post.

I also have a benchmark in progress comparing learned scheduling against CP-SAT. The question I want answered is where each side wins: learned scheduling on hidden structure, CP-SAT on crisp constraints, and what the boundary between them looks like. No numbers yet, that is for a later post.

Sources linked in this post were fetched and verified.