Price-Lifted Nearest-Neighbor Indices for Streaming Optimal Transport

Optimal transport asks for the cheapest way to move one cloud of points onto another. Its cost, the Earth Mover's Distance, serves as a loss, a drift detector and a distribution comparison. Exact solvers look at all $N^2$ pairs of points, so practical systems prune to a sparse graph of "candidate" pairs, usually each point's $k$ nearest neighbors, and solve on that graph. This breaks down in two ways when data streams in. First, the candidate graph is geometric: when the two clouds are shifted relative to each other, the optimal partner of a point is not among its geometric nearest neighbors, and the pruned solution is silently wrong. Second, every insertion or deletion forces the graph to be rebuilt and the problem re-solved.

We propose one fix for both. For squared-Euclidean cost, the question "which excluded pair would most improve the current transport plan?" turns out to be an ordinary nearest-neighbor query in a space with one extra coordinate, where that coordinate encodes each target point's current dual price. Dual prices are the per-point numbers an optimal transport solver maintains to certify optimality. So a dynamic nearest-neighbor index of the kind used in streaming vector databases can serve as an exact pricing oracle. When the prices change, only that extra coordinate needs updating. The result is a sparse transport solver whose candidate graph is kept correct by the index rather than guessed from geometry. It warm-starts from the previous solution after each stream update and can report how far it might be from optimal.

Core Claim

Consider source points $x_i$ and target points $y_j$ in $\mathbb{R}^d$, cost $c_{ij}=\|x_i-y_j\|^2$, and dual potentials $u_i, p_j$. A plan supported on a sparse edge set is globally optimal exactly when no excluded edge has negative reduced cost $c_{ij}-u_i-p_j$. For fixed $i$, the most violated edge is $\arg\min_j \big(\|x_i-y_j\|^2 - p_j\big)$. Choosing any constant $B \ge \max_j p_j$ gives

$$ \|x_i-y_j\|^2 - p_j + B \;=\; \big\|(x_i,\,0) - (y_j,\,\sqrt{B-p_j})\big\|^2 , $$

so the most violated edge is the exact Euclidean nearest neighbor of the lifted query $(x_i,0)$ among the lifted targets $(y_j,\sqrt{B-p_j})$ in $d+1$ dimensions.

Column generation means repeatedly solving on a small edge set and then adding the edges that most violate optimality. Under this identity, column generation for transport becomes a sequence of nearest-neighbor queries against an index whose points drift along one axis as prices change. The claim to test has two parts. Maintaining this lifted index dynamically, with lazy repair when a lifted coordinate moves, should give transport plans that are provably optimal whenever the index returns true neighbors, at a per-update cost close to warm-started sparse solvers. It should also stay accurate in the shifted-distribution regime where geometric $k$-nearest-neighbor pruning fails.

Relation to Prior Work

The method draws on two groups of work. On the sparse transport side, A Computation-Aware Shape Loss Function for Point Cloud Completion (AAIP) prunes point-cloud EMD to an R*-tree $k$-NN graph and warm-starts the auction algorithm with initial prices. Minimum-Cost Network Flow with Dual Predictions shows that warm-starting dual relaxation with predicted potentials $\hat p$ gives running time scaling with $\|\hat p - p^*\|_\infty$. On real road networks with perturbed costs this yields a 12.74x average speedup. Both supply method we reuse: the previous time step's prices become our dual prediction. Neither changes the candidate graph in response to prices. AAIP's graph is fixed per batch, and the flow paper's topology is fixed. Our contribution is to make the candidate graph itself price-aware and dynamic.

On the maintenance side, The DiskANN library introduces FreshVamana. It keeps deleted nodes temporarily as routing points and consolidates them lazily, and it holds >95% recall over 50 churn cycles. We reuse this machinery for a new kind of churn: attribute drift of a single coordinate, driven by an optimizer rather than by data arrival.

Dynamic spanners (A Simple Dynamic Spanner via APSP, A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching) motivate the recourse view. Recourse is the number of structural changes per update. These papers bound it for distance preservation but never maintain a mass-transport plan. We measure recourse of the plan itself.

Two lines constrain the design rather than supply it. Streaming Sliced Optimal Transport handles streams in logarithmic memory but computes a sliced surrogate with no transport plan. Diffusion Earth Mover's Distance shows that tree approximations degrade on curved data but is an offline method. We aim at exact plans, which neither provides.

Research Program

The solver keeps three things across stream updates: a sparse edge set $E$, a primal plan and potentials $(u,p)$ that are optimal on $E$, and a dynamic proximity-graph index over the lifted targets, with a symmetric index over lifted sources for pricing from the other side. Each stream update inserts or deletes points. The solver then carries out five steps. It edits the index. It repairs the plan locally by rerouting the mass of deleted points and giving new points their lifted-nearest candidates. It re-optimizes on $E$ with warm-started auction or $\epsilon$-relaxation. It re-lifts every target whose price moved by more than a threshold $\tau$; each re-lift is a delete-and-reinsert in the index. Finally it runs pricing rounds, querying lifted nearest neighbors for each point, adding violating edges, and dropping long-idle edges, until no violations are returned.

When $\max_j p_j$ exceeds $B$, the gauge is reset. Potentials are only defined up to a shared constant, so we re-center them, but a reset still re-lifts every point. How often resets happen is an outcome we measure, not something we assume away.

The analysis has three parts. The first is a certificate: if the index has recall 1 on the pricing queries, the plan is exactly optimal. Otherwise, the duality gap on edges found by an exact audit of a random sample of rows gives an empirical bound on suboptimality. The second is stale-coordinate error: a threshold $\tau$ lets reduced costs be misestimated by at most $\tau$ per point, which translates into an additive $N\tau$ slack on the certificate. The third is recourse and repair cost as functions of churn rate.

The scope is honest. The lifting identity holds for squared-Euclidean cost and not for the unsquared distance used in some point-cloud EMD losses. For that case the lifted search is only a heuristic candidate generator, and we report it separately.

Baselines

The naive reference is recomputation from scratch at every update. This means an exact network-simplex or auction solve on the full bipartite graph at sizes where that fits in memory, and a freshly built static $k$-NN graph with a cold-start auction above that. It defines ground-truth EMD and the latency we must beat. Beating it means matching its cost to within the certificate slack at lower per-update latency.

The strongest competitor is AAIP-style pruning with warm starts, following A Computation-Aware Shape Loss Function for Point Cloud Completion. At each update the geometric $k$-NN candidate graph is rebuilt incrementally in the same dynamic index, and auction restarts from the previous prices. This is the strongest competitor because it has the same warm start and the same index technology, and differs only in how candidate edges are chosen. On ShapeNet 1024-point clouds, AAIP reports an EMD-estimation mean squared error of 121.79 versus 912.78 for the approximation used in MSN. Their cost convention may differ from our squared cost, so we rerun AAIP under both conventions rather than quoting across them. Fairness is enforced by giving both methods the same $k$, the same index implementation and memory, the same auction code, and the same hyperparameter search budget. Beating it means lower relative EMD error under distribution shift at equal or lower latency, with no loss on aligned distributions.

A warm-started entropic solver (Sinkhorn initialized from the previous potentials) on the same sparse candidate graph is the natural smooth-OT competitor. We tune its regularization over a matched grid.

Stream-SW from Streaming Sliced Optimal Transport is a memory-bound reference rather than a plan-level competitor. It reports MNIST approximation error of 0.0003 versus 0.003 for random subsampling, but it approximates a different distance.

Three ablations isolate the key ingredient. The first swaps price-lifted pricing for geometric pricing, holding everything else fixed. The second replaces lazy re-lifting with full index rebuilds. The third replaces approximate index queries with exact brute-force pricing, which separates index error from algorithmic error.

Why not just…?

Why not just rebuild the geometric k-NN graph and warm-start the prices? This is the real threat. When source and target clouds overlap closely, geometric neighbors already contain the optimal partners, and the lifted index adds cost without adding accuracy. The mechanism predicts the gap appears only under relative shift or deformation, where prices become roughly linear in position and the lifted query points toward $x_i$ plus the shift. The geometric-versus-lifted ablation, run across a controlled sweep of shift magnitude, settles this. If the gains vanish on realistic streams, the contribution reduces to a certificate, and we will say so.

Why not just use warm-started Sinkhorn? Entropic transport produces a blurred, dense plan. It has no reduced-cost certificate on excluded edges, and it inherits whatever candidate graph it is given, so it faces the same pruning failure. The matched-candidate-graph comparison shows whether its speed compensates for its bias against exact EMD.

Why not just use sliced or tree approximations? They compute a different quantity and give no plan. Stream-SW has no plan, and Diffusion Earth Mover's Distance found that tree methods correlate worse with true EMD on the Swiss Roll and Spherical MNIST. They are appropriate only when a scalar drift score is enough. We include Stream-SW to mark the memory frontier, not as an accuracy competitor.

Why not just recompute exactly each step? At a few thousand points this is viable, and our experiments will state that crossover size explicitly. The dynamic-coarsening results in Adapting to Evolving Graphs (10–20x speedups over recomputation) suggest the gap grows with size, but that evidence comes from a different problem and must be re-established here.

Proposed Experiments

Streams are built from four sources. The first uses ShapeNet and ModelNet10 point clouds of 1,024 to 8,192 points, with a fixed fraction replaced per step and a slowly applied rigid or nonrigid deformation. The second is MNIST as a 784-dimensional distribution stream. The third uses windows of the OpenAI-ArXiv-2M and Wikipedia-Cohere-35M embedding corpora, which test high-dimensional drift at scale. The fourth is the COVID-19 single-cell data used by Diffusion EMD, where accessible.

Metrics are relative EMD error against exact solutions, computed where feasible and on sampled sub-streams otherwise; the certified duality gap; the fraction of true violations missed by the index; per-update latency; plan recourse, meaning the fraction of transport edges changed per update; peak memory; and gauge-reset frequency.

Three checks are decisive. The first is the shift sweep: lifted pricing must hold near-zero error as shift grows while geometric $k$-NN error rises. The second is the drift-cost measurement: the fraction of targets re-lifted per update must stay small, since if prices move globally after every insertion, index repair dominates and the approach fails. The third is the certificate audit: the reported gap must upper-bound the true error on every stream where ground truth is available.