# On the Representational Geometry of Dynamic Programs

arXiv: https://arxiv.org/abs/2608.25034 · HTML: https://mlsanity.com/paper/2608.25034/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 12 references that are in the map.
- First posted on arXiv 25 Aug 2026.

## Builds on (most cited first, 4 of 4)

- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms](https://mlsanity.com/paper/2505.17190/) (2025)

## Abstract (arXiv)

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.