Cost-augmented Schr\"odinger bridges on graphs are exactly solvable: a Feynman-Kac tilt replaces learned control
The paper solves the generalized Schrödinger bridge on finite graphs—transporting probability mass between distributions while charging costs for visited states—by showing that state costs fold into the reference process via a Feynman–Kac tilt. This reduces the problem to solving a plain bridge against the tilted generator $A = Q - \operatorname{diag}(f)$ with sparse matrix-exponential iterations, eliminating the need for learned controls or tuned temporal-difference penalties. The method scales to millions of nodes and extends to congestion costs through a provably convergent damped best-response outer loop.
The tilt identity in Theorem 2.1 is the paper's central result and is derived rigorously: it shows that the generalized bridge objective is equal to $\mathrm{KL}(q\|\widetilde{R}) - \log Z$, making the optimizer exactly the plain bridge against the tilted reference with generator $A = Q - \operatorname{diag}(f)$. Corollary 2.2 preserves the original edge support and gives the optimal controlled rates as $u^\star_t(x,y) = Q_{xy} \varphi_t(y)/\varphi_t(x)$, matching the functional form targeted by prior learned work. The exact solver is validated on assignment, rare-event steering, and routing, meeting endpoint marginals to machine precision and producing roll-outs consistent with the target distribution.
The exact reduction eliminates a fundamental cancellation bug in learned solvers: when the cost is kept outside the reference, it cancels out of the iterative-proportional-fitting objective, forcing prior work to add a tuned temporal-difference penalty that worsens the terminal match. The tilted generator automatically respects graph topology because it changes only the diagonal, so the control consults only out-neighbors. Scaling experiments are strong: on road networks with up to millions of intersections, memory stays near 350 bytes per node and fitting iterations track the singular-value prediction to within a few percent.
Direct benchmarking is limited because the prior learned solver's implementation and full reference rates were not released, so the authors rebuild scenarios and warn that values are only 'comparable in kind.' The continuous-time exactness claim holds for the linear solver, but roll-outs still discretize time geometrically near the horizon to cope with the singular $1/(\tau-t)$ arrival rate. For marginal-dependent congestion costs, the globally guaranteed damping window narrows to $0.0016$ at $\beta\tau=2500$, and the sharper local stability bound requires a Lanczos curvature estimate, so the outer loop is not fully black-box.
The exact solver isolates entropic regularization from learned approximation error. On assignment, it recovers the minimum-cost assignment on every instance inside the prior concentration band, whereas the learned solver achieves only 90% agreement at $K=20$. On the DC road network, roll-outs land within the Monte Carlo sampling-error band of the target. The chignolin evidence is harder to compare: the rebuilt model uses a 0.12 nm folded threshold rather than the prior 0.09 nm, and it rests on only five folding events, making barrier estimates model-sensitive.
The algorithm is deterministic, but no code is released, so an independent replicator must implement the sparse matrix-exponential IPF, chunking renormalization, and Gauss–Legendre quadrature from scratch. The paper does identify public data sources—the Zenodo trajectories for chignolin and the ROAD-FLOW benchmarks for road networks—but omits implementation-level details such as sparse-product tolerances and Lanczos stopping criteria. The inner solves rely on standard scaled Taylor series actions, yet the potential vectors can span tens of orders of magnitude, requiring exact renormalization chunking that is only briefly described.
The generalized Schr\"odinger bridge on a graph moves mass between two distributions while charging a cost for the states visited. It has been approached by learning the rates of a controlled continuous-time Markov chain, with a temporal-difference penalty that restores the cost. A state cost folds into the reference process as a Feynman-Kac tilt. The cost-augmented bridge is then a plain bridge against the tilted reference, and the penalty is unnecessary. The bridge is computed exactly by alternating two endpoint rescalings, each one sparse matrix-exponential application; nothing is discretized in time or learned. The alternation converges at a rate set by the endpoint coupling alone. For a quadratic congestion cost on time-averaged occupancies, damped best response around the exact bridge is gradient descent on a strongly convex function, and its residual bounds its error. On a protein-folding model, a free-energy cost lowers the expected barrier of the folding paths. On the learned approach's road network, roll-outs of the exact bridge match the target within sampling error, and on networks with millions of intersections its memory grows linearly.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.