Length-OOD Generalization and Transfer Learning Limits on Dynamic Programming Problems
Advisor: Ruriko Yoshida, Ph.D.
Work done at the Naval Postgraduate School. Length generalization is a notoriously hard problem for neural networks. However, Tropical Attention, based in the tropical (max/min-plus) semiring, is a conspicuous exception, achieving strong length generalization on dynamic programming (DP) tasks. We ask what is required for length generalization on DPs. We demonstrate that embedding DPs as a tropical polynomial is lossy and does not respect the DP’s graph topology. Finally, we prove two negative results. 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.