Triangle-Inequality Pruning for Dense Quasimetric Planning

Robots, and agents more generally, often live in worlds where distance is one-way. Climbing a slope costs more than descending it, and a dropped object cannot be un-dropped. A family of learned "quasimetric" distances respects this. These distances obey the triangle inequality but drop the requirement that the distance from A to B equal the distance from B to A. They have become the strongest tool for goal-reaching from offline data. The best planners built on them, however, hit a compute wall. Planning over $V$ candidate waypoints needs all pairwise distances, $O(V^2)$, and shortest-path search, up to $O(V^3)$. So today's systems shrink their maps to roughly 150 waypoints.

This note proposes a way around that wall that uses only the geometry the distance already has. The triangle inequality, which these models build in exactly, also gives cheap, provably correct lower bounds on distances that were never computed. Those bounds let a planner skip most waypoint pairs while returning the same answer as brute force. We then use this as an attention operator: each waypoint "attends" to the others through a soft minimum over learned one-way distances. The operator becomes one differentiable relaxation step of shortest-path search, and its cost grows sub-quadratically on the low-dimensional state manifolds typical of navigation. Multi-scale dilated convolutions play a supporting role. They are the visual encoder that maps camera images to waypoint embeddings, where local obstacle detail and wide arena layout must both survive.

Core Claim

Let $d(x,y)\ge 0$ be a learned quasimetric between state embeddings, such as the Interval Quasimetric Embedding of Tongzhou Wang et al. or the Metric Residual Network of Bo Liu et al.. Both satisfy the triangle inequality by construction. Pick a small set of pivot states $c$ and precompute $d(i,c)$ and $d(c,i)$ for every waypoint $i$. Applying the triangle inequality in both directions then gives, for any pair $(i,j)$,

$$d(i,j)\;\ge\;\max_c \max\big(d(i,c)-d(j,c),\; d(c,j)-d(c,i)\big),$$

which costs a handful of subtractions per pair rather than a forward pass. The same bound holds blockwise when waypoints are grouped around pivots: subtracting a block's radius gives a valid lower bound for every member. Planning needs a relaxation of the form

$$\hat d(s,g)=\operatorname{softmin}_{\tau}\big\{\,d(s,w)+d(w,g)\,\big\}_{w\in W},$$

where $W$ is the waypoint bank, $\tau$ a temperature, and the soft minimum is a softmax-weighted average of the candidate path lengths. Hard top-$k$ or thresholded versions of this operator can therefore discard waypoint blocks whose lower bound already exceeds the current best path. The result is identical to evaluating all of $W$.

The central bet is that waypoints in navigation and manipulation lie near a low-dimensional manifold, such as maze position plus body pose. If so, the bounds are tight, the fraction of evaluated pairs falls as $V$ grows, and planning over thousands of waypoints becomes practical. The planning gain itself is a separate empirical claim: denser waypoint banks should improve long-horizon success where sparse maps lose stitching options.

No paper in the file does this. SMYRF speeds up attention by hashing queries and keys with different transformations, but its scores are ordinary dot products with no triangle inequality, so it offers no correctness guarantee. Efficient vision transformers such as SG-Former and LookupViT keep symmetric dot-product affinities and save compute by merging or bottlenecking tokens heuristically. Adaptive Quasimetric Mapping (AQM) uses the same learned distances we do but escapes its $O(V^3)$ search by keeping about 150 keypoints. We keep the dense waypoint set and remove the cost exactly instead.

Research Program

The first component is the distance model. We reuse the training recipes that currently set the bar on OGBench and add nothing to them. These are multistep waypoint sampling with an MRN head from MQE, and the contrastive initialization with Bregman-divergence consistency updates from TMD. This isolates the planner: any gain comes from search, not from a better learned distance. We implement the bound for both IQE and MRN. IQE also admits a cheaper per-component bound, because the length of an interval union is at least the largest single stretch $\max_j (v_j-u_j)^+$. This allows a two-tier filter before the full distance is computed.

The second component is the pruned operator. Pivots are chosen by farthest-point sampling under $d$, and waypoints are bucketed by pivot. A GPU kernel computes block lower bounds and evaluates exact distances only for surviving blocks. We use it in two ways. The first is exact single-source search: Dijkstra-style expansion where neighbor discovery is pruned rather than brute-forced. The second is a stack of $L$ soft-min attention layers over the bank, which acts as $L$ steps of differentiable path relaxation. The second form can be fine-tuned end to end against the offline consistency loss. Exactness is checked against brute force on every run.

The third component is the encoder for visual tasks. OGBench's 64×64 visual mazes require a single embedding to capture both a nearby wall and the agent's place in the arena. We replace the standard convolutional encoder used by MQE and TMD with poly-scale dilated convolution, as in PSConv. PSConv cycles dilation rates across channels inside one layer, adding no parameters. It reported a drop in ImageNet top-1 error from 22.8% to 21.1% for ResNet-50. This component is deliberately secondary. It matters only if encoder quality limits how tight the bounds are, which we test directly.

The analysis plan tracks three quantities as functions of bank size $V\in\{150, 1\text{k}, 4\text{k}, 16\text{k}\}$: the fraction of pairs actually evaluated, wall-clock planning time, and task success. We also report how pruning efficiency varies with the estimated intrinsic dimension of the embedded waypoints. This is where the method can fail, since triangle-inequality pruning is known to degrade in high-dimensional, uniformly spread data.

Baselines

The naive reference point is the trained quasimetric with no planner. The agent acts greedily on $d(s,g)$, as MQE does. MQE is the "do nothing" control for search and also the strongest direct method. The file reports it as the only method with non-zero success on AntMaze-Colossal and a tenfold gain on humanoidmaze-giant-stitch, but no absolute success numbers for these tasks were found on Lacuna. We rerun it on our hardware, with seeds and tuning budgets matched to the original configuration. Beating it means higher success on the giant and colossal mazes at matched training compute, with planning latency kept within an interactive per-step budget that we fix in advance.

The strongest existing planner is AQM. It reports 88% success on antmaze-giant-navigate using 158 nodes, while GAS fell to 64% when restricted to fewer than 300 nodes (AQM). We run AQM's wavefront keypoint extraction on the same learned distance as our method, so only map construction and search differ. Beating it means exceeding 88% on antmaze-giant-navigate, or matching it while also improving the stitch and explore datasets, where we expect sparse maps to lose connectivity.

Two ablations isolate the key ingredient. The first is a brute-force dense planner: the same bank, the same distance, every pair evaluated. It must return identical plans, which verifies exactness, and it measures the speedup we claim. The second replaces the quasimetric with a symmetric Euclidean embedding trained by the same recipe and pruned with the same bounds. Classical metric-tree pruning applies here too, so this ablation tests whether asymmetry, not pruning alone, drives success. Anders Jonsson et al. predict that symmetric distances blur uphill and downhill costs. The encoder ablation swaps PSConv for the standard encoder at identical parameter count.

Why not just…?

Why not just keep a sparse map of ~150 nodes, as AQM does? This is the real threat. AQM's 88% with 158 nodes suggests sparse maps may already suffice on navigate datasets. The sweep over $V$ settles it. If success plateaus at a few hundred nodes on every dataset type, the case for dense planning collapses to the speed result alone, and we will report it that way. Our hypothesis is narrower: stitch and explore data, where OGBench shows coverage dominates outcomes, need waypoints that sparse extraction discards.

Why not just use an off-the-shelf approximate nearest-neighbor index or linear attention? These assume symmetric similarity and give no guarantee. A missed waypoint can silently remove the only connecting path. Top-$K$ selection must also score every pair before choosing, so it saves nothing on the expensive step. The symmetric-embedding ablation and the exactness check against brute force address this directly.

Why not just trust the learned distance, since the architecture already enforces the triangle inequality? Enforcing the inequality guarantees consistency, not accuracy. Learned distances still err over thousands of steps. The greedy-MQE baseline measures exactly how much explicit search corrects. If greedy matches planning on colossal mazes, search is unnecessary there, and the result is still informative.

Why not just use an unconstrained network to score asymmetric distances? Without the triangle inequality, no lower bound exists and pruning is impossible. MRN also reports that such networks generalize worse over long horizons.

Decisive Checks

We run state-based and 64×64 visual versions of OGBench antmaze-giant, humanoidmaze-giant and AntMaze-Colossal, across navigate, stitch and explore datasets, with eight seeds each. The decisive outcomes are three. First, the fraction of evaluated pairs must fall below 10% at $V=4\text{k}$ while plans exactly match brute force. Second, dense planning must beat AQM's 88% on antmaze-giant-navigate and beat greedy MQE on the stitch datasets. Third, the symmetric ablation must lose to the quasimetric at equal pruning. As a qualitative transfer check, we test whether the pruned planner preserves AQM's zero-shot rerouting in AmazeVille when gates close, by invalidating blocks whose observed traversal cost exceeds its bound. If pruning efficiency collapses on the visual tasks but recovers with the PSConv encoder, that would support the multi-scale component. If it does not recover, the encoder claim is dropped.