Commercial language models served through text-only interfaces have two weaknesses that compound in long planning tasks. They cannot reliably check their own work: self-critique drives GPT-4 from 16% to 2% on graph coloring. They also expose no token probabilities, so no internal confidence signal is available to tell a plausible answer from a broken one. This proposal replaces the missing confidence signal with an exact external one. The language model translates a user's request into formal constraints. A knowledge compiler turns those constraints, grounded in the available options, into a circuit that can answer counting questions instantly. The number of valid plans that remain, and which choices every valid plan is forced to make, is then returned to the model in plain language. A zero count says the model's reading of the request contradicts the available data. An enormous count says it probably dropped a constraint. Once the count is sensible, the model's only remaining job is to choose among options that are already known to be valid. It never judges validity, which is the step at which self-correction fails.
Knowledge compilation here means converting a logical formula, in an expensive offline step, into a restricted circuit called a d-DNNF. In a d-DNNF, AND gates join sub-circuits that share no variables, and OR gates join alternatives that cannot both hold. With that structure, counting solutions, counting under a partial assignment, and sampling uniformly all take time linear in the circuit size. The proposal makes three linked claims. First, these counts work as a calibrated substitute for logits when checking an LLM's formalization. Second, the counts and forced choices give actionable feedback that stops the "dead loops" seen in tool-using agents. Third, the circuit's own independent sub-circuits indicate where a task can be split across separate agents and where agents must coordinate.
Core Claim
Existing hard-critic designs check one candidate at a time and answer yes or no. Position: LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks back-prompts a black-box generator with a plan validator. On the self-verification limitations of large language models on reasoning and planning tasks pairs independent sampling with a sound verifier. Both motivate this work, because they establish that external verification is necessary. Both also leave the generator guessing blindly inside a space it cannot see.
On the compilation side, Counting and Reasoning with Plans supplies the method. It compiles bounded classical planning tasks to d-DNNF for counting, finding "facets" (choices that appear in some but not all valid plans), and uniform sampling. It assumes a hand-written formal specification and has no language component. A Balanced Neuro-Symbolic Approach for Commonsense Abductive Logic is the closest neuro-symbolic precedent. It feeds SAT-solver backbones (facts every model must satisfy) to a black-box LLM. However, it answers single true/false validity questions and does not use the size or shape of the solution space.
The claim that differs from this prior work is about the formalization step. The obvious combination, which uses compiled sampling to seed the LLM generator, is not worth doing in the classical-planning setting where it was proposed. If the domain is already formalized, the circuit alone solves Mystery Blocksworld, and the LLM adds nothing. The LLM is indispensable only where the specification itself comes from natural language. That step is exactly where black-box models currently get no confidence signal. The model count conditioned on the LLM's extracted constraints is a property of the formalization, not of any single plan. We hypothesize that it detects mistranslations far better than asking the LLM to review its own constraints.
Research Program
The test bed is TravelPlanner (TravelPlanner: A Benchmark for Real-World Planning with Language Agents). Each query asks for a 3- to 7-day itinerary over a 4-million-record sandbox and carries hard constraints: budget, room type and house rules, cuisine, and transport mode. Agents there reach a 0.6% final pass rate and fall into repeated identical calls when a tool returns nothing.
The system has three agent roles around one compiled oracle. A Translator agent reads the query and writes constraints in a small typed language. The language covers equality, exclusion, cardinality, and budget sums over option variables. An Options agent fills in the candidate flights, hotels, restaurants, and attractions per city from the sandbox tools, and these ground the variables. The compiler (Dsharp-style d-DNNF compilation, following WAPS: Weighted and Projected Sampling) builds the circuit per query.
The oracle then reports three kinds of feedback to the Translator in plain language: the total count, the backbone (the forced choices), and, if the count is zero, a small conflicting subset of constraints found by dropping constraints one at a time and recounting. If the count is implausibly large relative to the candidate pool, the oracle reports which facets remain free, which prompts the Translator to re-read the query for missed requirements. When a tool returns an empty result, the Options agent passes that result to the oracle as a new fact. The oracle then reports either the revised count or that no valid plan survives, so a dead loop becomes a single deterministic recount.
Once the count is accepted, Selector agents commit choices. They are assigned one per independent sub-circuit under a top-level decomposable AND, for example per-city dining when budget couples only transport and lodging. Each commitment is a conditioning query, so a Selector only ever sees options with at least one valid completion, ranked by remaining count. Selectors use commonsense and stated preferences to choose among these options. They are never asked whether anything is valid.
Budget sums are the main compilation risk. Pseudo-Boolean constraints can blow up d-DNNF size, and WAPS: Weighted and Projected Sampling documents compilation timeouts on dense constraints. We will measure compile time and circuit size per query, and use projected compilation over decision variables with discretized cost buckets. The bucket rounding error is reported as a soundness gap and checked by the official evaluator.
Baselines
The naive reference point is the published single-agent ReAct agent. On TravelPlanner, GPT-4-Turbo with ReAct reaches a 0.6% final pass rate in two-stage mode, and GPT-4 reaches 4.4% on the hardest sole-planning tasks (TravelPlanner: A Benchmark for Real-World Planning with Language Agents). We rerun both with the same current model used by our system.
The strongest existing method is LLM-Modulo back-prompting (Position: LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks). The paper reports roughly a 6x improvement on travel planning and a standard GPT-3.5-Turbo success rate of 0.7%. No absolute LLM-Modulo pass rate for TravelPlanner was found on Lacuna. To keep the comparison fair, we implement it with hard critics built from the same Translator-extracted constraints our oracle uses, so the only difference is point-wise rejection versus counting feedback. It receives the same iteration cap and the same dollar budget of API tokens.
The sampling baseline follows On the self-verification limitations of large language models on reasoning and planning tasks: independent generation with a sound checker, up to k=25, matched on API cost. That paper reports 72% on Blocksworld and 14% on Mystery Blocksworld with this setup. A multi-agent baseline in the style of Self-collaboration Code Generation via ChatGPT, with Analyst, Planner, and LLM Tester roles, tests whether role splitting without sound verification is enough.
The key ablations isolate counting. The first replaces the oracle's counts with a SAT solver's single-bit "a completion exists" answer and its unsatisfiable core, while keeping everything else fixed. The second removes the count-plausibility check on the Translator's constraints. The third collapses all Selectors into one agent, to measure what circuit-guided decomposition contributes.
A gold-formalization solver-only run, which uses hand-written constraints and uniform sampling, is reported as an upper bound rather than a competitor. Beating the strongest baseline means a higher final pass rate than cost-matched LLM-Modulo, with non-overlapping bootstrap intervals over the 1,225 queries, at equal or lower API cost.
Why not just…?
Why not just let the solver produce the whole plan? With a correct formalization it would, and our gold-formalization upper bound will show this. That is why the proposal does not claim the LLM generates plans better. The open problem is that real requests arrive in natural language. The relevant comparison is therefore solver-only on LLM-extracted constraints with no count feedback, which is our second ablation. If that ablation matches the full system, the Selector agents contribute nothing to pass rate, and the contribution reduces to count-checked formalization. That would be a narrower result, and we would report it as such.
Why not just call a SAT solver for feasibility at each step? This is the most serious threat. A Balanced Neuro-Symbolic Approach for Commonsense Abductive Logic shows that SAT backbones already help black-box LLMs. A satisfiability check catches zero-count formalizations but cannot flag under-constrained ones, because a missed constraint still leaves a satisfiable formula. It also cannot rank options by how much flexibility they preserve. The binary-feasibility ablation settles the question directly. If it matches the full system on both pass rate and mistranslation detection, counting is unnecessary, and we would recommend the cheaper solver.
Why not just sample more? Sampling with a sound checker works when valid plans are dense, reaching 44% on graph coloring at k=25 (On the self-verification limitations of large language models on reasoning and planning tasks). It degrades to 14% on Mystery Blocksworld and to near zero on TravelPlanner, where few plans satisfy all constraints at once. The cost-matched sampling baseline measures this gap on our exact queries.
Why not just ask the LLM to double-check its constraint extraction? The self-verification evidence predicts this fails, with a 97.09% false-negative rate on Mystery Blocksworld plans. We test it directly by comparing self-review against count plausibility as detectors of seeded mistranslations.
Proposed Experiments
The first decisive check measures detection quality. We seed 300 TravelPlanner queries with controlled formalization errors (dropped, flipped, and over-tightened constraints) and compare two detectors: count plausibility and LLM self-review. The metric is the area under the ROC curve for flagging the corrupted formalization. The hypothesis fails if counts do not beat self-review by a clear margin.
The second check reports the end-to-end TravelPlanner final pass rate, hard-constraint and commonsense pass rates, API cost, and dead-loop rate against all baselines and ablations above. Dead-loop rate is defined as three or more identical consecutive tool calls.
The third check records compile time and circuit size per query, and the fraction of queries that time out. If budget constraints make compilation impractical on more than a small minority of queries, we will report that as a limit on the approach.
As a sanity check, we run PlanBench Blocksworld and Mystery Blocksworld (PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change), where the domain arrives already formalized. There we expect the circuit alone to dominate every LLM-in-the-loop method. That result would confirm that the LLM's value lies in formalization, not in generating plans.
References
- Position: LLMs Can’t Plan, But Can Help Planning in LLM-Modulo Frameworks
- On the self-verification limitations of large language models on reasoning and planning tasks
- Counting and Reasoning with Plans
- A Balanced Neuro-Symbolic Approach for Commonsense Abductive Logic
- TravelPlanner: A Benchmark for Real-World Planning with Language Agents
- WAPS: Weighted and Projected Sampling
- Self-Collaboration Code Generation via ChatGPT
- PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change