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
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
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∖{(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 P3 and Q3 , applied to either problem, yield the same length- 2 object (bottom).
Figure 2: (L) The Wheatstone edge substitution ΦW(A1,…,A5) . (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
Figure 3: Series and parallel composition of two-terminal DAGs: series identifies zA with sB , parallel identifies the two sources and the two sinks.
Figure 4: The dome 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} .
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.
Figure 6: The two vertex splits, realizing the distributivity clause of Proposition 17 . Left: an internal vertex w with in-edges e1,e2 and out-edges g1,g2 . Middle: the out-split along O1={g1} , O2={g2} , with each of w1,w2 carrying its own copy of e1 and e2 . Right: the in-split along I1={e1} , I2={e2} , with each of w1,w2 carrying its own copy of g1 and g2 . In both panels every pi→qj path of the original survives exactly once.
Figure 7: Mediant deletion (Lemma 18 ) on the family Gc=0∥(x;x)∥(c;x) , computing min(0,c+x,2x) . Left: the middle chain (weight c≥0 then x ) is deleted for every c≥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
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.
Shivaprasad B. Gowda, Sparsh Mittal
Indian Institute of Information Technology, Nagpur · Indian Institute of Technology, Roorkee
Classical dynamic programming represents optimal sequential decisions through value functions and policies. While this functional representation is natural for computing optimal decisions, it does not directly identify the mathematical object governing policy reconstruction, representation complexity, or oracle-query complexity once an optimal policy is fixed. This paper addresses this question by developing a geometric theory of structured optimal policies in which the decision-boundary geometry induced by the policy becomes the primary object of analysis. We show that, under suitable structural regularity conditions, this geometry provides the minimal representation required for policy reconstruction and determines the statistical and computational complexity of the reconstruction problem. Building upon this representation, we establish structural properties of policy-induced decision geometry, introduce intrinsic notions of boundary and decision complexity, derive information-theoretic measures of decision compression, and obtain statistical guarantees for boundary estimation and policy reconstruction from black-box policy queries. Collectively, these results demonstrate that, for the structured decision problems considered here, the complexity of policy reconstruction is governed by the geometry of the decision boundary rather than by the cardinality of the ambient state space. Controlled numerical experiments examine the principal theoretical predictions and provide empirical evidence consistent with the proposed framework.
Why do neural networks memorize algorithmic training data long before they generalize? We present a geometric case study demonstrating that, on tasks where generalization requires discovering structured low-dimensional circuits, the memorization-generalization delay is driven by radial inflation of hidden representations under cross-entropy optimization. We formalize a radial-angular decomposition of activation-space dynamics and derive three testable propositions: (i) that penalizing radial inflation induces anisotropic, data-dependent weight regularization; (ii) that it suppresses radial gradient energy below the isotropic random baseline, forcing predominantly angular updates; and (iii) that it biases convergence toward flatter minima. To empirically validate these propositions, we study a single-hyperparameter norm penalty that softly constrains activations to a sqrt(d)-radius hypersphere. On modular arithmetic, this penalty accelerates grokking up to 6x across MLPs and Transformers, and halves training steps for a 10M-parameter nanoGPT on 3-digit addition.