Language models follow one instruction well but many at once poorly. The best measurements show success falling roughly exponentially as rules are added, because each rule fails roughly independently and the failures multiply. That evidence comes almost entirely from writing text and from picking objects in images. Navigation is different. A path is a geometric object, and in the plain grid formats language-model agents usually emit, such as "step north-east, step east…", a single route becomes a long sequence of tokens. Every rule ("stay out of the loading bay," "keep the exit in view," "visit the charger before the shelf") then has to be maintained across all of those steps.
This note proposes that the output format is itself a lever on that load. The format in question is the vocabulary in which a model writes its plan: grid steps, any-angle waypoints, a topological corridor, or a formal spec. Any-angle pathfinding means letting a path turn only at a few obstacle corners and travel in straight lines of arbitrary heading between them, as Theta* does on grids. It shrinks a route to a handful of decisions, and those decisions are exactly where most navigation rules are won or lost. We will build a benchmark with deterministically verifiable spatial constraints on standard game and warehouse maps. On it we will measure how fast constraint adherence decays under each format, and test whether a division of labor beats both end-to-end generation and full translation to a formal solver. In that division, the model picks only the corridor and an any-angle planner fills in the geometry.
Core Claim
The format in which a language model writes a path changes both the rate and the structure of its multi-constraint collapse. We use the three-parameter fit from Large Language Models Can Follow Instructions, But Not Many at Once:
$$P(k) = a\, e^{-\beta k} + c,$$
where $P(k)$ is the fraction of outputs satisfying all $k$ constraints, $\beta$ is the decay rate, and $c$ is the floor sustained by rules that need no active maintenance.
We predict three things. First, 8-connected grid-step outputs will show text-like behavior: a large $\beta$ and approximately independent failures. Second, any-angle corner-waypoint outputs will show a smaller $\beta$ and correlated failures that concentrate on a single "spatial perception" factor, resembling the visual-selection regime in that same paper, where one factor explained 87.9% of failures. Third, and most important, the improvement is not explained by output length alone. A run-length-compressed grid format of equal token count will retain most of the grid format's decay.
If this holds, it settles the open question that paper left about modality versus task structure, at least for spatial planning. It also gives a design rule: language models should commit to topology, and planners should handle metric geometry.
What the Directions Contribute
The instructional-load literature supplies the phenomenon and the measurement method. FollowBench adds constraints one level at a time and finds strong models top out near three. Constraint Saturation Evaluation sweeps $k$ from 1 to 12 with code-based checkers, reports breakdown beyond 5–6 constraints and a floor near 16%, and finds relational rules decaying 2.4 times faster than lexical ones. Why is constrained neural language generation particularly challenging? attributes part of the difficulty to constraints on the output that the model only meets mid-generation, with instruction drift over long spans. We borrow the sweep design and deterministic verification wholesale. What we change is the object being generated.
Any-angle pathfinding supplies both the alternative format and the oracle. Theta* keeps grid memory but lets a node's parent be any visible ancestor, yielding paths typically within 1% of the true shortest length. Lazy Theta* defers the line-of-sight check (whether a straight segment is obstacle-free) until a node is expanded, cutting checks about thirteenfold. We extend that lazy check to evaluate rule predicates as well as obstacles, which makes it the reference solver and the repair step. The work on discrete movement constraints, chiefly Any-Angle Path Planning, supplies the key mechanism. Grid paths are up to about 8% longer in 2D. More importantly, grid search can commit to the wrong side of an obstacle (the wrong homotopy class), and no post-smoothing can undo that choice. Many navigation rules are homotopy rules in disguise: which side of a zone, which room first. Our hypothesis is that grid-format outputs force the model to make these topological commitments implicitly, scattered across dozens of steps. Corner-waypoint outputs make them explicit and few.
Two prior systems constrain the design. Plug in the Safety Chip shows plain language-model agents falling to 0–34% safety at five or more rules. Translating rules to temporal logic and monitoring actions restores 100% safety with 98% task success, though only over discrete landmarks. ChinaTravel shows that a neuro-symbolic pipeline reaches only 37.0% on human queries, because translating language into a formal spec degrades from 79% to 53% grounding accuracy. These results tell us full formalization is a strong baseline but not a free lunch, since its failure point shifts to translation. Neither system touches continuous geometry.
Research Program
We will build a spatial constraint-saturation benchmark on maps from the MovingAI grid benchmark, using empty, random, maze, warehouse, and game maps, with corner-placed vertices. The constraint library will span about 20 types in five groups:
- static zone avoidance, expected to behave as "immune" rules;
- ordered must-visit regions, which are sequential;
- landmark visibility along the route, which is line-of-sight based;
- side-of-obstacle requirements, which are explicit homotopy rules;
- budget rules such as maximum turns or length within a factor $w$ of the constrained optimum, echoing the bounded-suboptimality idea in AA-CCBS.
Every constraint has a code verifier. Every instance with $k$ constraints is certified jointly feasible by a constraint-aware Lazy Theta* oracle, run over the grid crossed with a small automaton for ordering rules and a homotopy signature for side rules. The oracle also gives the optimal constrained length.
Each instance is posed to the language model under five output formats, chosen to separate the candidate explanations. These are 8-connected grid steps, run-length-encoded grid steps ("NE×7, E×3"), and free any-angle waypoint lists, plus two hybrid formats. The first hybrid is a corridor format, where the model outputs only an ordered list of obstacle corners and sides and the planner completes the geometry. The second is a formal-spec format, where the model writes predicates and the oracle plans, in the style of ChinaTravel and the Safety Chip. Rule phrasing, map rendering (ASCII grid plus corner coordinate list), and decoding are held fixed across formats.
The analysis fits $\beta$ and $c$ per format and per constraint group. It tests independence by comparing observed joint success with the product of marginals, and it extracts the first factor of the per-constraint failure matrix. It also separates two causes of failure: violations caused by wrong topology versus wrong local geometry, using the homotopy signature.
Baselines
The naive reference point is constraint-blind Theta*, the shortest any-angle path that ignores every rule. It shows how much success comes free from immune constraints and gives the floor any language-model format must beat. The model-side naive reference is direct prompting in the 8-connected grid format, the representation used throughout embodied instruction-following work. We run it on the same instances, models, and decoding temperature as every other arm, with a chain-of-thought variant at equal token budget.
The strongest existing competitor is full formalization: the model translates rules into predicates and an exact constraint-aware planner solves them. This is the Safety Chip and ChinaTravel recipe, transplanted onto our any-angle oracle so geometry is not a handicap. The Safety Chip reports a 100% safety rate and 98% task success on VirtualHome/Spot, and ChinaTravel reports 37.0% success for its neuro-symbolic pipeline on human queries. Neither number is on spatial any-angle constraints. There is no reported result on Lacuna for multi-constraint any-angle navigation, so all comparisons will be internal. We give the formal-spec arm the same model calls plus one round of verifier feedback, matching the reprompting the Safety Chip uses. The corridor format beats it if it achieves higher strict success at $k \geq 6$ on human-paraphrased instructions with equal calls. A tie with lower translation-error rates would also be informative.
The key ablation is run-length-encoded grid steps. This format matches the any-angle format's token count while keeping grid geometry, so it isolates "fewer tokens" from "decisions placed at obstacle corners." A second ablation runs Theta-style post-repair on grid outputs to test whether the topology the model chose, rather than local jaggedness, causes violations. For path quality we compare against the oracle's constrained optimum and against Theta's reported near-Euclidean lengths.
Why not just…?
Why not just have the model write a formal spec and let a solver do everything? This is the real threat. If the formal-spec arm dominates at every $k$, the practical recommendation is simply "formalize," and our contribution shrinks to the measurement study. ChinaTravel's translation collapse suggests spec-writing has its own $k$-dependent decay. We measure that decay directly by fitting $P(k)$ to translation correctness. We expect the corridor format to win on human-phrased rules because naming corners is closer to the map than writing predicates. The experiment decides it either way.
Why not just compress the grid output? If length alone drives the decay, as instruction drift would suggest, the run-length arm should match the any-angle arm. That would be a clean, useful negative result, and the ablation is designed to show it.
Why not just smooth the model's grid path afterwards? Any-Angle Path Planning shows smoothing cannot change which side of an obstacle a path takes, and Global Tensor Motion Planning reports the same limit for splines. Our topology-versus-geometry split of violations measures how many failures smoothing could fix in principle.
Why not just add chain-of-thought? The constraint-saturation study found that models writing analysis preambles were worse at strict adherence. We include a reasoning arm at matched budget rather than assume that result transfers.
Proposed Experiments
The first experiment is the $k$ sweep from 1 to 12 on about 1,500 certified instances across MovingAI map families, run on several open and closed models. It reports strict success, per-constraint satisfaction, fitted $\beta$ and $c$, the independence gap, and the first-factor share of failures.
The decisive checks follow from the Core Claim. The claim is supported if the any-angle format's $\beta$ is clearly below the grid format's, with confidence intervals from bootstrap over instances. It also requires the run-length arm to sit closer to the grid arm than to the any-angle arm, and the any-angle failures to be markedly more correlated. It is refuted if run-length matches any-angle, or if all formats decay identically.
A second experiment compares the corridor and formal-spec formats at $k \geq 6$ on a held-out set of rules paraphrased by human writers. This probes the grounding drop ChinaTravel observed. A final check on 3D voxel maps from Benchmarks for Pathfinding in 3D Voxel Space asks whether the effect grows where grid inflation is larger (about 13% versus about 8%), as the mechanism predicts.
References
- Large Language Models Can Follow Instructions, But Not Many at Once: Phase Transitions in Compositional Constraint Satisfaction
- FollowBench: A Multi-level Fine-grained Constraints Following Benchmark for Large Language Models
- Why is constrained neural language generation particularly challenging?
- Theta*: Any-Angle Path Planning on Grids
- Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D
- Any-Angle Path Planning
- Plug in the Safety Chip: Enforcing Constraints for LLM-driven Robot Agents
- ChinaTravel: An Open-Ended Travel Planning Benchmark with Compositional Constraint Validation for Language Agents
- Benchmarks for Grid-Based Pathfinding
- Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding
- Global Tensor Motion Planning
- Benchmarks for Pathfinding in 3D Voxel Space