On the Representational Geometry of Dynamic Programs

arXiv:2608.25034v1 Announce Type: new 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.

Related

• Embedding Linear Equality Constraints in Probabilistic Neural Networks for Dynamic Modelling
• Warm-starting active-set solvers using graph neural networks
• Stimulus symmetries can confound representational similarity analyses
• What Cosine Similarity of Label Representations Can and Cannot Tell us

Source: arXiv cs.LG | 2026-08-27