SOURCE-LINKED INTELLIGENCE

On the Representational Geometry of Dynamic Programs

arXiv · AI, language, vision and robotics · article · Aug 25, 2026 · UTC

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 lengt

Read original source ↗ Open in workspace

recordType

paper

region

Global