On the Representational Geometry of Dynamic Programs

Richard F. M. Lim; Ruriko Yoshida

cs.LGAug 25, 2026

On the Representational Geometry of Dynamic Programs

Authors: Richard F. M. Lim, Ruriko Yoshida

Organizations: Departments of Mathematics and Computer Science, Bowdoin College, Brunswick, Maine · Department of Operations Research, Naval Postgraduate School, Monterey, California · Department of Mathematical Sciences, Aalborg University, Denmark

Abstract

Standard neural architectures often fail to generalize to longer inputs for dynamic programming (DP) targets. We investigate what makes this hard geometrically. Every finite min-plus DP is a shortest path on a DAG, which is equivalently a tropical polynomial whose extended Newton polyhedron encodes the decision boundary of which path wins. We prove these three descriptions (graph, polynomial, polyhedron) form isomorphic semirings at two levels --- formal polynomials and their computed functions --- connected by operations that characterize all structural redundancies. We then address the length-generalization question geometrically: does the decision boundary at length $T$ decide the boundary at $T+1$ ? We present two structural negatives. The semiring's two native ways to reduce dimension (setting a variable to each identity) are neither injective nor always closed within the DP. Series and parallel composition fail to construct all DAG topologies from smaller sub-DAGs, and even all terminal-only operations do not capture all DP compositions.

Figures & tables

Panel of Figure 1 — Figure 1: Two length- $3$ problems that no substitution distinguishes. (L) min-subset-sum, support $\{0,1\}^{3}$ ; (R) the same over proper subsets, support $\{0,1\}^{3}\setminus\{(1,1,1)\}$ . Middle panels show the decision boundaries (positive half-axes behind, dotted). The all-ones monomial is off the coordinate face and redundant under the projection, so both $P_{3}$ and $Q_{3}$ , applied to either problem, yield the same length- $2$ object (bottom).

Panel of Figure 2 — Figure 2: (L) The Wheatstone edge substitution $\Phi_{W}(A_{1},\dots,A_{5})$ . (R) Merging two instances of clamped min-subarray: the two sources, the two sinks, and the last internal vertex of $A$ with the first internal vertex of $B$ .

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Series and parallel composition of two-terminal DAGs: series identifies $z_{A}$ with $s_{B}$ , parallel identifies the two sources and the two sinks.

Panel of Figure 4 — Figure 4: The dome $\mathcal{D}(f)$ of $f=\min(4,\;2{+}x,\;1{+}2x,\;3{+}3x)$ from Example 5 . Each facet is a monomial’s locus of dominance; the three vertices of the dome project to the tropical zeroes $\{-2,1,2\}$ .

Panel of Figure 5 — Figure 5: The tropical line of Example 6 : the hypersurface of $f=\min(0,x,y)$ is three rays meeting at the origin, separating the three regions on which a single monomial attains the minimum.

Panel of Figure 6 — Figure 6: The two vertex splits, realizing the distributivity clause of Proposition 17 . Left: an internal vertex $w$ with in-edges $e_{1},e_{2}$ and out-edges $g_{1},g_{2}$ . Middle: the out-split along $O_{1}=\{g_{1}\}$ , $O_{2}=\{g_{2}\}$ , with each of $w_{1},w_{2}$ carrying its own copy of $e_{1}$ and $e_{2}$ . Right: the in-split along $I_{1}=\{e_{1}\}$ , $I_{2}=\{e_{2}\}$ , with each of $w_{1},w_{2}$ carrying its own copy of $g_{1}$ and $g_{2}$ . In both panels every $p_{i}\to q_{j}$ path of the original survives exactly once.

Panel of Figure 7 — Figure 7: Mediant deletion (Lemma 18 ) on the family $G_{c}=0\,\|\,(x;x)\,\|\,(c;x)$ , computing $\min(0,\,c+x,\,2x)$ . Left: the middle chain (weight $c\geq 0$ then $x$ ) is deleted for every $c\geq 0$ , leaving $\min(0,2x)$ . Right: the lifted points and extended Newton polyhedron.

graph operation	tropical semiring property
series-run reweighting : redistribute weights along an unbranched run, sum preserved	$+$ associative, commutative
parallel-bundle bookkeeping : permute or delete/adjoin a dominated branch	$\min$ assoc., comm., idempotent
$+\infty$ -edge adjunction : add/remove $+\infty$ -weighted edges (preserving 2-terminality)	$\min(a,{+}\infty)=a$ , $a+\infty=+\infty$
vertex splitting / merging : split edges at an internal vertex into two copies, or merge	distributivity of $+$ over $\min$
mediant deletion : delete a path whose monomial lies weakly above the lower hull of the others	redundant monomials may be deleted by convexity

Appendix

Table 1: The calculus of invariant operations on DAGs derived from tropical semiring properties.

Dynamic Programming

Dynamic programming decomposes sequential optimization into smaller state-based subproblems, enabling planning, control, and combinatorial search.

See all 31 papers

Representations Have Trajectories: Characterizing Temporal Representation Dynamics in Neural Networks
Oct 17, 2026Shivaprasad B. Gowda, Sparsh MittalLow-Rank Representation Learning Neural Representation Geometry
Indian Institute of Information Technology, Nagpur · Indian Institute of Technology, Roorkee
A Geometric Theory of Decision Boundaries in Structured Markov Decision Processes
Sep 16, 2026Fredy PokouMarkov Decision Processes Decision-Making under Uncertainty
MRE, INOCS
Radial Suppression Accelerates Algorithmic Generalization: A Geometric Analysis of Delayed Generalization
Jun 30, 2026Srijan Tiwari, Aditya Chauhan, Manjot SinghNeural Network Generalization Neural Representation Geometry
Indian Institute of Technology Roorkee

Oct 17, 2026J/K move · Enter open · S save

Representations Have Trajectories: Characterizing Temporal Representation Dynamics in Neural Networks

Shivaprasad B. Gowda, Sparsh Mittal

Indian Institute of Information Technology, Nagpur · Indian Institute of Technology, Roorkee

Low-Rank Representation Learning Neural Representation Geometry Neural Network Training Dynamics Representation Learning Neural Network Optimization Representation Collapse

Open paper AskPDF arXiv

Recent work has shown that deep neural networks exhibit an implicit low-rank simplicity bias. In this paper, we investigate the questions that naturally arise from this observation. What are the temporal consequences of low-rank simplicity bias during optimization? How does representation geometry evolve throughout optimization rather than only at convergence? Do different neural architectures exhibit distinct geometric optimization behaviors? To answer these questions, we conduct a large-scale empirical study tracking representational geometry throughout training. We find that neural networks follow three recurring geometric trajectories: persistent high-rank, collapse-and-recovery, and persistent low-rank. We further identify Destructive Representation Collapse (DRC) as a pathological regime in which representations collapse to rank-one and fail to recover, leading to a sustained loss of representational capacity. While collapse-and-recovery is consistently associated with successful optimization in controlled settings, experiments on real-world models show that the relationship between geometric trajectories and optimization outcomes is configuration dependent. Overall, our findings suggest that representation geometry evolves dynamically during training and provide a new perspective on how deep neural networks learn.

Abstract

Dynamic Programming

Explore similar work

Representations Have Trajectories: Characterizing Temporal Representation Dynamics in Neural Networks

A Geometric Theory of Decision Boundaries in Structured Markov Decision Processes

Radial Suppression Accelerates Algorithmic Generalization: A Geometric Analysis of Delayed Generalization