Neural routing solvers are networks trained to build delivery routes directly, without hand-written heuristics. They are now fast and fairly general. One model can handle dozens of vehicle-routing variants and reach within a few percent of the best classical solvers. But you steer them with a fixed numeric switchboard, such as a five-bit "which constraints are on" vector. Dispatchers do not talk in bit vectors. They say "the van has to be back by six," "never let one driver do more than twelve stops," or "serve the northeast cluster before lunch." The LLM systems that do accept such sentences skip the neural solver altogether. They write solver code instead, and the resulting routes are poor. We propose to connect the two, and we treat sensitivity to phrasing as the central design problem rather than an afterthought.
The idea in two sentences: a small multimodal model reads the instruction together with a picture of the instance. It compiles them into a short program of executable constraint clauses, which serves both as the feasibility mask a neural solver uses while it builds a route and as a variable-length set of clause embeddings the solver conditions on. Because clauses are executable, we can test whether two paraphrases mean the same thing by running their programs on the same partial routes and checking agreement. This gives a label-free way to detect misreadings and to pick a consensus interpretation before any route is produced.
Core Claim
Language-steered solvers will inherit the prompt sensitivity documented for LLMs. Training Prompt Matters shows that semantically equivalent training prompts can differ by up to 156% in forgetting and generalization. From Words to Routes finds a 4–5% drop in routing feasibility and optimality when minor details are omitted. Our claim is that in combinatorial optimization this sensitivity is best controlled at a checkable intermediate, not inside the solver's embedding space.
Routing is unusual among instruction-following tasks. Whether a constraint holds can be verified mechanically. Two readings of an instruction are therefore equivalent exactly when they accept and reject the same partial routes, and that can be estimated by sampling. If two compiled programs disagree on a fraction $\epsilon$ of decoding states, then comparing them on $M$ random states misses the difference with probability $(1-\epsilon)^M$. This is the chance that $M$ independent draws all land on agreeing states. The test becomes reliable at modest $M$ for any disagreement large enough to matter.
This differs from the closest work along three axes. The solver-conditioning line uses fixed, predefined constraint encodings with no language. CaDA concatenates a projected five-dimensional multi-hot constraint vector to node embeddings. URS zero-pads a unified feature vector and generates decoder weights from active-constraint indicators. ARC learns compositional intrinsic-plus-contextual embeddings over categorical attribute flags. We borrow ARC's compositional idea, but apply it to clause types with arguments rather than on/off flags.
PromptVRP uses "prompts" that are learned continuous vectors retrieved by spatial statistics. It motivates latent conditioning but has no language. The language-to-optimization line routes around neural solvers. LLMOPT and LLaMoCo produce code for classical solvers or metaheuristics. We share LLMOPT's view that a structured intermediate prevents plausible-but-wrong formulations, but our intermediate is executed as a decoding mask rather than handed to an exact solver that cannot scale. Finally, Promise contracts phrasing variance through two-loop meta-finetuning of prompt embeddings, but only for image classification. We use it as a competing strategy: make the embedding invariant, as opposed to making the interpretation testable.
Research Program
The system has three parts.
The constraint language. This is a small typed set of clause primitives over the solver's decoding state and instance fields. It covers load limits, route-duration limits, time windows, open routes, backhaul ordering, precedence between named customers, same-vehicle and different-vehicle pairs, forbidden edges, maximum stops per vehicle, and priority ordering. Each primitive compiles to a mask predicate, a function saying which next customers are allowed given the partial route. Soft preferences compile to additive penalties on the solver's scores. The five CaDA constraints and the URS variants are all expressible in this language, so our system strictly contains the existing ontologies. The last five primitives are deliberately outside every existing neural solver's encoding.
The compiler. This is a compact vision-language model instruction-tuned on triples of instruction text, a rendered instance, and the target program. The rendered instance is built following the coordinate-to-image construction of GIMF, with node indices overlaid. The image matters only for instructions that refer to geometry ("the northeast cluster," "customers near the depot"), which a text-only parser cannot resolve without an explicit coordinate dump.
Training follows the multi-template recipe of FLAN and T0: many phrasings per program, with instruction and input templates assembled randomly. Paraphrases are generated by an LLM and filtered by the equivalence test itself. A paraphrase whose gold-annotated program behaves differently from the source is either discarded or relabelled as a near-miss contrast example, for instance "at most 50" versus "fewer than 50." This directly addresses the paraphrase-drift failure that the Promise line leaves open.
At inference we sample $k$ programs, from temperature sampling and from self-paraphrases of the user instruction. We compute pairwise behavioral disagreement on $M$ shared partial routes and keep the medoid program. If no program agrees with a majority, the system returns the competing readings to the user instead of silently guessing.
The solver. This is a RouteFinder-style multi-variant transformer (RouteFinder) trained with mixed-batch reinforcement learning. We replace its fixed constraint input with attention over a variable-length set of clause embeddings. Each clause embedding is a learned type vector plus an encoding of its arguments, meaning referenced nodes and thresholds normalized to instance scale. The compiled mask guarantees feasibility under the chosen reading. The clause embeddings let the network plan for constraints rather than merely stumble into masked dead ends.
Solver training uses programs sampled compositionally from the clause grammar, with some clause combinations held out. This lets zero-shot composition be measured the way ARC measures it on unseen attribute combinations.
Baselines
Naive reference. A single-template compiler with single-sample decoding feeding our solver. It measures how much of any gain comes from multi-template training and consensus selection versus the architecture. Below it sits a "no-language" oracle: the same solver given the gold program. This bounds what interpretation errors can cost.
The two-stage pipeline. A strong off-the-shelf LLM extracts the constraint flags and numeric parameters into CaDA's input format, and a retrained CaDA solves the instance (CaDA, whose reported average CVRPLib gap is 3.32% with 32-fold augmentation). This is the most dangerous competitor. Extracting five binary flags is easy for modern LLMs, and CaDA's solver is well tuned. For fairness, CaDA is trained on the same instance distributions and RL budget as our solver. The LLM is given the same instructions, a schema, and few-shot examples, and it receives the same $k$-sample budget with majority voting over its extracted vectors. On in-ontology instructions we expect parity. Beating it means lower gap and higher true-constraint feasibility on out-of-ontology and spatially grounded instructions, with no loss inside the ontology. A URS-based pipeline (URS) is run the same way on the larger-scale tests.
End-to-end text conditioning. The solver attends directly to a frozen sentence encoder's embedding of the instruction, with no program and no mask. It is trained with FLAN-style paraphrase augmentation and, in a second variant, with Promise-style two-loop meta-finetuning over disjoint template sets (Promise). Both variants get our full paraphrase pool and matching compute. Promise reports roughly 18–22% training overhead, and we grant the extra wall-clock. This baseline tests whether invariance in embedding space suffices. Beating it means lower cross-paraphrase variance and far fewer infeasible routes under the true constraints.
LLM-written solver code. GPT-class code generation with self-verification, following From Words to Routes, which reports a 71.5% success rate and an average optimality gap around 38.6% on its 80-problem benchmark. This baseline is included mainly on the small instances where it is viable.
The ablation that isolates our key ingredient. Keep the compiled mask but drop the clause embeddings, so a generic solver only sees masking. A second ablation removes the behavioral-equivalence medoid step and uses a single sampled program.
Why not just…?
Why not just have an LLM fill CaDA's constraint vector? For the five constraints CaDA knows, this probably works about as well as our system, and we will report that honestly. The limit is expressiveness, not parsing accuracy. Precedence pairs, same-vehicle requirements, stop limits, and geometry-referenced rules have no slot in a five-bit vector, and adding them means redesigning and retraining the solver. Parsing is also not free on harder text: even on curated linear-programming word problems, the best named-entity system in NL4Opt reached F1 0.939. The out-of-ontology split settles this question. If a pipeline with an extended flag vector matches us there, then compositional clause conditioning adds nothing and the contribution reduces to the compiler and the equivalence test.
Why not just let an LLM write OR-Tools or Gurobi code? The reported evidence is unfavorable for routing quality. From Words to Routes finds about a 38.6% gap even when self-verification raises feasibility to 71.5%. LLaMoCo reports a 41.6% code error rate for GPT-4 Turbo on optimization code. Exact formulations also stop scaling well before the instance sizes neural solvers handle. We still run it on the small instances to confirm that the ordering holds on our phrasing suite.
Why not just make the solver's text embedding phrasing-invariant, as Promise does for CLIP? Invariance of an embedding does not certify that the right constraint is enforced. A smoothly invariant model can consistently ignore "fewer than" versus "at most." Our near-miss contrast sets are built exactly to expose this. The end-to-end baseline with Promise-style training will show whether embedding invariance also buys constraint fidelity. If it matches us on feasibility and variance, the executable intermediate is unnecessary.
Why not just mask, without clause embeddings? Masking guarantees feasibility, but it may leave the solver planning blind. For example, it may fill a vehicle early and only discover the stop limit at the end. The mask-only ablation measures this directly. If the gap does not widen, we will drop the conditioning claim.
Proposed Experiments
Benchmark construction. No paraphrase-varied natural-language benchmark for neural routing solvers exists; there is no reported result found on Lacuna for language-conditioned neural solvers under phrasing variation. We build one on the synthetic variant suites of CaDA (16 variants), RouteFinder (48), and URS (110 variants, up to thousands of nodes), plus CVRPLib instances. Each instance receives an instruction in many phrasings: handcrafted templates, LLM paraphrases filtered by behavioral equivalence, and near-miss contrast paraphrases with a different gold program. We add an out-of-ontology split using the new primitives, and a grounded split whose instructions refer to spatial regions. Held-out clause combinations test composition. The 80-problem set from From Words to Routes serves as an external small-scale check.
Metrics. Optimality gap to HGS or PyVRP on the gold constraints; feasibility under the gold constraints, not the compiled ones; interpretation accuracy, meaning the behavioral agreement of the chosen program with the gold program; and cross-paraphrase sensitivity, meaning the spread of gap and feasibility across phrasings of the same instance. We also measure contrast-set discrimination: the rate at which near-miss paraphrases are correctly compiled to different programs. Reference numbers from the file include CaDA's 3.32% CVRPLib gap, RouteFinder's 12.3% gap on the CVRPLib X-set, and ARC's 4.078% zero-shot gap on nine unseen combinations. These anchor the solver's quality with gold programs, the oracle setting.
Decisive checks. The first check is whether the oracle-to-language gap stays small, say under one point of optimality gap, across paraphrases while the end-to-end baselines show large feasibility losses. The second is whether the medoid selection reduces cross-paraphrase spread relative to single-sample compilation without collapsing near-miss contrasts. The third is whether the pipeline baseline ties us in-ontology but fails out-of-ontology. The fourth is whether removing the instance image from the compiler hurts only the grounded split, which confirms that the multimodal input earns its place rather than being decoration. The fifth is whether clause embeddings beat mask-only solving on the constraint types that require foresight: stop limits, precedence, and same-vehicle pairs.
A clean negative on the fifth check would narrow the claim to reliable interpretation. A negative on the first or second would mean behavioral equivalence testing does not tame phrasing sensitivity in practice, which would itself be a useful finding for anyone building language front ends to solvers.
References
- Training Prompt Matters: State-Adaptive Optimization for Robust Fine-Tuning
- From Words to Routes: Applying Large Language Models to Vehicle Routing
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
- URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization
- ARC: Leveraging Compositional Representations for Cross-Problem Learning on VRPs
- Prompt Learning for Generalized Vehicle Routing
- LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch
- LLaMoCo: Instruction Tuning of Large Language Models for Optimization Code Generation
- Prompt-Robust Vision-Language Models via Meta-Finetuning
- Neural Multi-Objective Combinatorial Optimization via Graph-Image Multimodal Fusion
- Finetuned Language Models are Zero-Shot Learners
- Multitask Prompted Training Enables Zero-Shot Task Generalization
- RouteFinder: Towards Foundation Models for Vehicle Routing Problems
- NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions