{"id":"arxiv/2608.25034","url":"https://arxiv.org/abs/2608.25034","tags":["cs.LG","cs.DM","math.AG","math.CO"],"score":0,"title":"On the Representational Geometry of Dynamic Programs","domain":"cs.LG","source":"arxiv","authors":["Richard F. M. Lim","Ruriko Yoshida"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-25","reactions":{}}