Homotopy Words for Stitched Diffusion Plans

Diffusion planners that stitch short trajectory pieces into long paths now solve mazes that no single model can. The published failure mode is telling, though. When many pieces are chained, the combined path sometimes "passes through walls" (Generative Trajectory Stitching through Diffusion Composition). We argue that this is a topological error with an exact discrete description. In a maze, the free space is a flat region with holes. A classical fact says such a region is aspherical: all of its shape is captured by one group, the group of loops around obstacles, and that group is free. Consequently every path between two points carries a short word recording which way it went around which obstacles. For a stitched plan, this word is simply the product of its pieces' words.

The proposal is to compute that word exactly and cheaply for every generated piece, and to require the pieces' words to multiply to the word of the intended route. The result is a plan whose global correctness is checked by local algebra at each seam, while the continuous geometry inside each piece is left to the diffusion model. The two-sentence version is this. In a maze, what makes a long path globally right or wrong is a discrete word in the loops around obstacles, and that word composes piece by piece. So a stitched diffusion planner can be made globally consistent by agreeing on words at the seams rather than by seeing longer trajectories.

Core Claim

Our claim has a mathematical half, which justifies the design, and an empirical half, which is what is new.

The mathematical half combines two results in the file. Take $Y$ as the free region of the maze, $a$ and $b$ as start and goal, and $P$ as the space of continuous paths from $a$ to $b$ in $Y$. Paths are maps from the interval, which is a countable cell complex, into $Y$, which is a separable complete absolute neighborhood retract (a space that is well behaved locally). The equivalence theorem in Function spaces of CW homotopy type are Hilbert manifolds therefore applies. That theorem proves that local niceness, being a manifold modeled on infinite-dimensional Hilbert space, is equivalent to global niceness, having the homotopy type of a cell complex.

The path space is therefore a Hilbert manifold. Because $Y$ is aspherical, the higher homotopy groups of each connected piece of $P$ equal higher homotopy groups of $Y$, which vanish. Each piece of $P$ is therefore contractible, and a contractible Hilbert manifold is a copy of Hilbert space itself. So

$$P \;\cong\; \bigsqcup_{w \in F_r} \ell^2 ,$$

where $F_r$ is the free group on $r$ generators, $r$ is the number of interior obstacles, and $w$ ranges over the homotopy classes of paths from $a$ to $b$.

The consequence is that within one class, any two valid paths can be continuously deformed into each other with no further obstruction. Global planning therefore reduces exactly to picking and maintaining a word $w$, and everything else is local smoothing.

The empirical half is a hypothesis about how failures grow with the number of stitched pieces, $K$. Unconstrained stitching lets each seam independently risk a class-changing error, so wall crossings and wrong-route plans should grow with $K$. If adjacent pieces instead agree on their words, verifying the global word requires only local cancellation between neighbors. That is a composition with no coordination overhead, in the sense of The composition complexity of majority. That paper separates functions such as Parity, which decompose into local pieces at no extra cost, from functions such as Majority, which pay a logarithmic coordination overhead. We predict that word-constrained stitching keeps its topological error rate roughly flat in $K$.

Research Program

Computing the words. The first component turns a maze into an exact, small algebraic object. We discretize the free space as a cubical cell complex from the occupancy grid. We then apply discrete Morse theory, a systematic way of collapsing cells in pairs without changing the space's shape, to shrink it to a spine: a graph with a single vertex and one loop per obstacle.

This is the same collapsing technique used to reduce the Salvetti complex, a combinatorial model of an Artin group's classifying space, in On the classifying space of Artin monoids. It is also used to shrink infinite complexes to finite ones in Proof of the K(π,1) conjecture for affine Artin groups. Here the target is simpler. A free group is the right-angled Artin group with no commuting relations, and its Salvetti complex is exactly a wedge of circles. Those papers supply the method, and our setting is the easy case where asphericity is already known.

Two exactness checks follow from the algebraic reduction literature. The boundary matrices of a planar cubical complex have all minors in $\{-1,0,1\}$, which is the total-unimodularity condition that Equivariant K-homology for hyperbolic reflection groups uses to rule out torsion. Integer homology can therefore be computed without rounding ambiguity. Free groups are also torsion-free, so the word is a complete invariant rather than an approximation.

In practice, each obstacle gets a "cut", a ray from the obstacle to the outer wall. A path's word is the ordered list of cuts it crosses, with signs, after cancelling adjacent inverse pairs.

Enforcing the words in the planner. The second component modifies CompDiffuser. In CompDiffuser, each chunk is denoised while conditioned on its neighbors' noisy states. The target word comes from a shortest-route search on the spine, weighted by the dataset's reachability, and is split into subwords assigned to chunks.

We use the constraint in two ways. The first is a sampling-time check with local resampling: if a chunk's decoded word disagrees with its assigned subword, only that chunk and its seams are re-denoised. The second is a training-time extra input, where each chunk receives its subword as an embedding. The first way leaves the trained model untouched and isolates the effect of topology.

The composition analysis. The third component formalizes the composition claim, following the computation-graph view of How Compositional is a Model?. That paper models a compositional function as local processors wired by a graph and bounds errors by how far each input's influence spreads.

In our setting, the global word is a composition of $K$ local word maps linked in a chain. We will prove that word agreement at seams yields a chain in which each node depends only on its two neighbors. We will then test the predicted $K$-scaling empirically.

Scope. Everything above assumes a planar maze. For AntMaze and HumanoidMaze, we project the body's position to the plane, whose free space is aspherical. Manipulation tasks are out of scope, because their configuration spaces need not be aspherical and the word would no longer be a complete invariant.

Baselines

Published CompDiffuser (the do-nothing reference). The naive reference point is CompDiffuser exactly as published, with the same checkpoints or retrained on the same stitching datasets. It is the strongest existing method on this question. On OGBench PointMaze Giant, where training paths span 4 maze blocks and test paths span up to 30, it reports a 68% success rate with replanning (Generative Trajectory Stitching through Diffusion Composition). The same paper reports 97% on AntMaze Medium, 66% on AntMaze Large, and 81% on AntMaze Medium with low-quality Explore data.

We rerun it under our own evaluation harness so that success, wall-crossing rate, and class correctness are measured identically. Our method uses the same denoiser, the same number of denoising steps, and the same replanning budget. Local resampling counts against an equal total number of chunk evaluations, so it does not receive extra compute. Beating the baseline means higher success on PointMaze Giant and AntMaze Large at matched compute. It also requires a wall-crossing rate that stops growing with $K$ where CompDiffuser's grows.

Weaker published references. The same paper reports 29% for Generative Skill Chaining and 0% for monolithic Decision Diffusers on PointMaze Giant. We cite these numbers rather than rerunning them, except for one Decision Diffuser sanity run.

Collision guidance from a distance field. The strongest simple competitor is guidance from a signed distance field, which pushes each sample's states away from walls with a gradient on the distance to the nearest obstacle. It uses the same maze map our method uses. That makes it the fair test of whether the topological information, as opposed to mere wall knowledge, matters. It receives the same guidance-strength tuning budget as our method.

Waypoint conditioning. This is the strongest structural competitor. A graph search over dataset states yields intermediate waypoints, and each chunk is conditioned to pass through its waypoint. Waypoints implicitly fix a homotopy class, so this baseline is a direct threat.

Ablations of the invariant. The key ingredient is the non-abelian word, so the central ablation replaces it with coarser invariants. The first coarser invariant is the abelianized signature, a vector of winding counts around each obstacle. This is the first homology group, which forgets the order of crossings. The second is winding parity modulo 2.

This ladder mirrors the composition-complexity distinction. The parity signature composes like Parity. The count signature needs Majority-style counting. Only the full word distinguishes routes that circle obstacles in different orders. If the abelian signature matches the full word on these mazes, the claim that non-abelian structure matters is false for them, and we will report that.

Why not just…?

Why not just reject and resample plans that hit walls? Rejection with replanning is essentially what already produces CompDiffuser's 68%. Rejection only tests validity. A path that avoids walls but loops the wrong way around an obstacle passes the check while wasting horizon, so rejection cannot distinguish two valid but different routes. Rejection also resamples the whole plan, whereas the word check localizes the faulty chunk. Matched-compute comparisons of whole-plan rejection against chunk-local resampling will show whether localization is worth anything.

Why not just add a collision penalty from a distance field? A distance gradient resolves wall penetration locally, but it can push a penetrating segment out on either side of an obstacle. Each side is a different homotopy class, so the penalty can silently change the route. We expect this baseline to lower wall crossings while leaving wrong-class plans common. The class-correctness metric measures exactly this. If distance-field guidance matches us on both metrics, the topological machinery is unnecessary for these tasks.

Why not just condition on waypoints from a graph planner? This is the real threat, because waypoints do pin down a homotopy class. The difference is that waypoints also dictate where in the free space the path passes. Words dictate only the order in which obstacles are circled, leaving the diffusion model free within each contractible class. The decomposition result above says that this freedom is exactly the part that local smoothing can handle.

We therefore predict that words match waypoints on success and beat them on path quality (length and smoothness), especially on the low-quality Explore data, where dataset states make poor waypoints. If waypoints win outright, the contribution shrinks to a diagnostic: the word metric still explains when and why stitching fails.

Why not just train a bigger monolithic model or use more data? Monolithic Decision Diffusers score 0% on PointMaze Giant (Generative Trajectory Stitching through Diffusion Composition). All OGBench baselines score 0% on HumanoidMaze giant (OGBench: Benchmarking Offline Goal-Conditioned RL). Scaling training data 41-fold still leaves an error floor under compositional shift in *-CFQ. We do not rerun this alternative beyond one sanity check.

Proposed Experiments

Environments and metrics. Experiments use OGBench PointMaze (medium, large, giant) stitching datasets, AntMaze Medium and Large (including Explore data), and HumanoidMaze giant, all from OGBench. We report three metrics:

  • Success rate, as the benchmark defines it.
  • Wall-crossing rate, the fraction of plans with any state in an obstacle before execution.
  • Class correctness, the fraction of valid plans whose word equals the target word.

First decisive check: error growth with $K$. Holding total horizon fixed, we sweep the number of chunks $K$ from 2 to 16 on PointMaze Giant and plot wall-crossing and wrong-class rates. The composition claim predicts roughly linear growth for CompDiffuser and distance-field guidance, and a flat curve for word-constrained stitching. A flat curve for CompDiffuser itself would refute the premise that seam errors compound.

Second decisive check: the invariant ladder. We compare parity, winding counts, and full words on mazes deliberately built so that routes differ only in the order of obstacle circling. Only the full word should succeed there.

Third check: the cost of exactness. We time the Morse-collapse pipeline on OGBench maps and confirm that its integer homology matches the obstacle count. Unimodularity guarantees this, so any mismatch indicates a discretization bug rather than a mathematical surprise.

Stretch test: HumanoidMaze giant. HumanoidMaze giant has no reported nonzero success. We do not claim we will solve it. The test is whether word constraints raise class correctness even when low-level control fails, which would localize the remaining difficulty to locomotion rather than routing.