Systems that pair a language model with a classical solver have mostly solved the search part of real-world planning. On a travel benchmark, an LLM paired with an integer-programming solver passes 96.6% of test itineraries, against 0.4% for GPT-4o planning on its own. The remaining weak point is the step before the solver, where the language model turns a messy request into a formal constraint list. If the model drops "arrive before 6 PM", the solver still returns a valid-looking plan. It is valid only for the wrong problem, and nothing downstream notices. This proposal treats that translation step as the place to measure and control two known LLM weaknesses. One is distraction by irrelevant context. The other is brittleness to small, meaning-preserving changes in instruction wording.
The core idea is simple. The translator's output is formal, so we can run it several times under deliberately varied but meaning-preserving inputs: reworded instructions, reordered requirements, irrelevant review text added, irrelevant text removed. We then compare the resulting specifications exactly, one atomic constraint at a time. A constraint that appears under every perturbation is probably real. A constraint that appears or disappears depending on wording or noise is flagged. The flagged constraint is then re-translated from only the sentence it came from, or sent back to the user as a clarification question, before the solver ever runs. In free-text tasks one cannot tell exactly which part of an answer changed. In neuro-symbolic planning one can, and that makes sensitivity usable as a per-constraint error detector rather than a whole-answer abstention signal.
Core Claim
We make three linked claims. First, translation errors in LLM-plus-solver planners are concentrated in silent omissions and misreadings, and these errors grow under contextual noise and instruction rewording together. We expect the two to interact: noise makes the model less confident, and low-confidence outputs are the ones that flip under rewording. Second, the agreement of a constraint across a designed family of perturbed translations predicts whether that constraint is wrong. It predicts this better than equal-budget temperature sampling, token probabilities, or solver feedback. Third, repairing only the low-agreement constraints from their localized source text raises end-to-end pass rates on noisy inputs. It should do so at a fraction of the cost of running a reasoning model end to end.
To make "agreement" precise, let $T_1, \dots, T_K$ be the translations produced under $K$ perturbations of the same request. Each translation is canonicalized into a set of atomic constraints (normalized attribute, comparator and value). The stability of a candidate constraint $c$ is
$$s(c) = \frac{1}{K}\sum_{k=1}^{K} \mathbf{1}[c \in T_k],$$
where $\mathbf{1}[\cdot]$ is 1 if the canonical constraint appears in that translation and 0 otherwise. Constraints with $s(c)$ near 1 are passed through. Constraints in a middle band are adjudicated. Constraints with $s(c)$ near 0 that appeared only once are treated as likely hallucinations.
Where This Sits in Prior Work
The motivation comes from neuro-symbolic travel planning. Personal Travel Solver translates requests and noisy user reviews into JSON constraints for a SCIP solver and reaches a 96.6% Final Pass Rate on RealTravel. It runs translation as a single feed-forward pass and never tests rewording or added noise, so an omitted constraint simply flows through. ChinaTravel compiles requests into a Python-like constraint language checked by depth-first search. It names this translation as its chief failure mode, with GPT-4o intent grounding falling from 79% on synthetic queries to 53% on human ones and the neuro-symbolic baseline reaching 37.0% success on human queries. Leveraging Environment Interaction for Automated PDDL Translation shows how unforgiving the formal side is: one missing term in a domain file causes a 14% planning failure rate, and three missing terms cause 30%. That paper repairs domain files by replaying random environment actions against the candidate model. Its signal requires an executable environment and targets the rules of the world. We target the user's constraints, where no environment can reveal an omission.
The perturbation idea builds on work that treats sensitivity as uncertainty. On the Relation between Sensitivity and Accuracy in In-Context Learning introduces SENSEL, which abstains when a classifier's label changes under prompt perturbation. It reports correlations with error up to −0.40 and a +4.1 AUC gain on GPT-J-6B. ProSA ties instability to flat decoding distributions. Rethinking Hallucinations: Correctness, Consistency, and Prompt Multiplicity shows that over 50% of factuality instances get different answers across prompts, and that retrieval can convert systematic errors into prompt-induced randomness. All three work on single labels or short answers. We reuse their insight but apply it inside a structured output, where disagreement can be localized to one constraint and acted on.
From the contextual-noise literature we borrow a constraint rather than a method. Less is More shows that summarizing long programming instructions helps Codex by +8.13% on APPS and +11.88% on CodeContests, but only about 2% on the hardest problems. Improving Zero-shot Reader by Reducing Distractions from Irrelevant Documents shows reader accuracy falling as retrieved documents grow. We use noise injection and noise removal as two of our perturbation axes, not as a fix. Summarization can silently delete the very constraint we care about.
The Mystery Blocksworld results in On the Planning Abilities of Large Language Models and LLMs Still Can't Plan; Can LRMs? appear at first to cut against us. In those papers, GPT-4 drops from about 35% to near zero and o1-preview from 97.8% to 52.8% once names are obfuscated. These results concern a model doing the planning. In our design the model only translates, and obfuscation becomes a further perturbation axis we can test: does renaming predicates reduce or increase translation stability under noise? We treat this as a secondary analysis and do not let it carry the main claim.
Research Program
The first component is a stress-test suite built on existing gold annotations. For ChinaTravel, the human and synthetic splits come with constraint-language annotations that serve as ground truth. For TravelPlanner and RealTravel, the hard constraints (budget, dates, room types, cuisine) are given per query. For PlanBench, the natural-language problem descriptions are compiled from IPC PDDL problem files, so the gold initial state and goal are known exactly. Each request is perturbed along four axes:
- Template rewording: in the style of ProSA's 12 templates.
- Reordering: the stated requirements are reordered.
- Contextual noise: the request is padded with irrelevant review sentences drawn from other RealTravel users, irrelevant venue metadata, or narrative backstory.
- Noise removal: an extractive trim of the request.
Injected distractors are filtered to exclude any mention of schema attributes, and a human spot check on a sample confirms that the gold constraints are unchanged. With this suite we measure per-constraint recall and precision of the translator, separately and jointly across axes. That directly tests whether noise and rewording interact or merely add.
The second component is the agreement-and-repair loop. It translates under $K$ perturbations, canonicalizes, computes $s(c)$, and passes stable constraints through. For each unstable constraint it locates the source sentence by asking the model for a supporting quote, re-translates that sentence alone, and accepts the result if it is consistent with the stable set. Otherwise it emits a clarification question; in offline evaluation, this question is answered from the gold annotation and counted as a human turn. The final specification goes to the existing solver: SCIP for RealTravel, the ChinaTravel search solver, or Fast Downward for PlanBench problem files.
We will run the translators with GPT-4o and an open-weight model, so that cost and token-probability baselines are available.
Baselines
The naive reference is the published pipeline with a single translation call. That means the ChinaTravel neuro-symbolic baseline, which reports 37.0% success on human queries in ChinaTravel, and the PTS translator feeding SCIP, which reports a 96.6% Final Pass Rate on clean RealTravel in Personal Travel Solver. We rerun both on our clean and perturbed inputs with the same translator model. The question is how far each falls under perturbation and how much of that drop our loop recovers. Beating it means a higher pass rate on the perturbed splits without a loss on clean inputs.
The strongest competitor is equal-budget self-consistency: $K$ temperature samples of the translator on the unperturbed input, with per-constraint majority vote and the same repair step for low-agreement constraints. This is the true threat, because it shares everything with our method except the perturbation design. It gets the same number of calls, the same canonicalizer, the same thresholds tuned on the same development split, and the same repair procedure. Beating it means a better risk-coverage curve, measured as per-constraint error detection AUC, and a higher downstream pass rate at matched calls.
A whole-output sensitivity baseline adapts SENSEL from On the Relation between Sensitivity and Accuracy in In-Context Learning. It abstains on or re-asks the entire request whenever any perturbed translation differs, which tests whether per-constraint localization matters. A token-probability baseline flags constraints whose generated tokens have low average probability; this requires only one call.
The summarize-then-translate baseline follows Less is More, with one trimming pass before a single translation. An end-to-end reasoning-model baseline uses o1-class planning without a solver. On PlanBench the file reports o1-preview at 97.8% on standard Blocksworld and 52.8% on Mystery Blocksworld in LLMs Still Can't Plan; Can LRMs?. For ChinaTravel and RealTravel, no reported result was found on Lacuna for o1-class models, so we will run it ourselves on a subsample within a fixed dollar budget.
Ablations remove one perturbation axis at a time. They also replace localized re-translation with plain voting, to isolate whether the gain comes from perturbation diversity, constraint-level comparison, or targeted repair.
Why not just…?
Why not just sample the translator several times at nonzero temperature and vote? This is the most serious alternative. If temperature samples disagree on the same constraints that perturbations do, the perturbation design adds nothing. Our concern is that temperature sampling explores the model's uncertainty given one fixed framing of the input. A distractor-induced omission can be confidently repeated across all samples, because the distractor is present in every one of them. Only removing or varying the noise reveals it. The matched-budget comparison above settles this directly. If self-consistency matches us, we will drop the claim about perturbation design and report constraint-level voting with localized repair as the contribution.
Why not just summarize or filter the input before translating? Less is More shows that summarization helps, but with gains shrinking to about 2% on the hardest problems. In constraint translation a summarizer that drops one requirement reproduces exactly the silent-omission failure; Leveraging Environment Interaction for Automated PDDL Translation shows that one missing term already costs 14%. We include noise removal as one perturbation rather than a gate. The summarize-then-translate baseline measures whether trimming alone closes the gap.
Why not just rely on the solver's feedback, as verifier loops do? Back-prompting with a plan validator lifts GPT-4 to 82% on Blocksworld in On the Planning Abilities of Large Language Models. That works when errors make the problem infeasible or the plan invalid. An omitted user constraint usually makes the problem easier, so the solver returns success. We will report what fraction of translation errors on our suite produce any solver complaint at all. If that fraction is high, solver feedback is a sufficient and cheaper fix, and our method is unnecessary.
Why not just use a reasoning model end to end? Its planning collapses at scale (23.6% on 20–40 step Blocksworld) and costs about a hundred times more per instance ($42.12 vs $0.44 per 100 instances) in LLMs Still Can't Plan; Can LRMs?. We still run it on a subsample, so the comparison is measured rather than assumed.
Decisive Checks
The idea stands or falls on four results.
- Does stability predict error? Per-constraint stability must predict per-constraint translation error on held-out perturbed ChinaTravel and RealTravel queries. An error-detection AUC near 0.5, or no better than token probability, falsifies the main claim.
- Does perturbation design beat sampling? At matched calls, the perturbation-based detector must beat temperature self-consistency. If it does not, the paper becomes a constraint-voting paper.
- Do noise and rewording interact? The joint noise-plus-rewording condition must show more translation error than the sum of the individual conditions. That would confirm that the two weaknesses compound at this boundary. Additivity would weaken the motivation for treating them together, though not the method.
- Do we gain at reasonable cost? End-to-end Final Pass Rate on the perturbed splits must exceed both the single-call pipelines and summarize-then-translate. The total cost per query should stay well below the reasoning-model baseline.
As a secondary probe, rerunning the PlanBench translation suite with Mystery-style renamed predicates will show whether obfuscation stabilizes translation under noise or destabilizes it.
References
- Personal Travel Solver: A Preference-Driven LLM-Solver System for Travel Planning
- ChinaTravel: An Open-Ended Travel Planning Benchmark with Compositional Constraint Validation for Language Agents
- Leveraging Environment Interaction for Automated PDDL Translation and Planning with Large Language Models
- On the Relation between Sensitivity and Accuracy in In-Context Learning
- ProSA: Assessing and Understanding the Prompt Sensitivity of LLMs
- Rethinking Hallucinations: Correctness, Consistency, and Prompt Multiplicity
- Less is More: Summary of Long Instructions is Better for Program Synthesis
- Improving Zero-shot Reader by Reducing Distractions from Irrelevant Documents in Open-Domain Question Answering
- On the Planning Abilities of Large Language Models - A Critical Investigation
- LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBench