PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Representational Geometry of Dynamic Programs

Richard F. M. Lim, Ruriko Yoshida

arXiv:2608.25034v1cs.LGcs.DMmath.AGmath.CO

TL;DR

Standard neural architectures often fail to generalize dynamic-programming behavior to longer inputs, motivating a geometric study of this length-generalization gap. The paper unifies DAGs, tropical polynomials, and Newton polyhedra through semiring isomorphisms and canonical operations, then proves that native substitutions and standard composition cannot generally recover larger instances. These negative results bound what (min, +) structure alone can achieve and indicate that richer compositional operations are needed.

  • Problem

    Standard neural architectures often degrade beyond training lengths on dynamic-programming targets, despite size-independent DP recurrences and exceptions such as Tropical Attention.

  • Method

    The paper represents finite min-plus DPs simultaneously as shortest-path DAGs, tropical polynomials, and extended Newton polyhedra, linking them with semiring isomorphisms, quotients, and invariant operations.

  • Results

    Semiring-identity substitutions are neither injective nor always DP-closed, while series-parallel and terminal-only operations fail to capture all relevant DAG topologies or DP compositions.

  • Takeaways & Limitations

    The negative results constrain architecture design based only on (min, +) structure and point toward richer compositional operations for length generalization.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies why neural models that perform dynamic programming often fail to generalize from short training lengths to longer inputs. It recasts finite min-plus DPs algebraically and geometrically, then identifies structural barriers to recovering larger instances from smaller ones.

  • Motivation: Dynamic programs use size-independent recurrences, but standard recurrent and attention-based models often degrade sharply beyond their training lengths.Tropical Attention is presented as an exception with strong length OOD generalization on classic DP problems.
  • Three descriptions: Every finite min-plus DP is equivalently a two-terminal shortest-path problem on a DAG and a tropical polynomial.The paper works in the dual (min, +) semiring, equivalent to (max, +) under negation.
  • Research questions: The central questions are which algebraic structures support computation at every length and whether larger instances can be inferred from smaller ones.The learner observes graphs with at most T variables and must predict every graph thereafter.
  • Contributions: Graphs, tropical polynomials, and geometric representations are formalized through a triple semiring isomorphism, with congruence quotients handling representational redundancy.The framework distinguishes formal polynomials from their computed functions and supplies canonical graph normal forms.
  • Negative results: Identity substitutions and composition operations do not suffice to recover longer DPs: substitutions can be non-injective or non-closed, while composition is topologically incomplete.The paper studies setting variables to semiring identities and the limits of series, parallel, and terminal-only operations.

2 The triality: one problem, three languages

This section establishes a triality connecting DAGs, tropical polynomials, and extended Newton polyhedra as equivalent semiring descriptions. The equivalences hold at both formal and function levels through surjective quotient maps.

  • Tropical polynomials: Formal tropical polynomials are finite tropical sums of monomials with coefficients in T, where +∞ denotes an absent term.Their support records exponents with finite coefficients, and vertical-minimum reduction keeps the least coefficient per exponent.
  • Tropical geometry: Normal-form lifted supports form a commutative idempotent semiring under vertical-minimum union and Minkowski addition.Each exponent has at most one lifted point after reduction.
  • Tropical geometry: The extended Newton polyhedron is the upward extension of the convex hull of the lifted support, and equal polyhedra characterize equal computed functions.Convexity provides the second quotient, while the ordinary Newton polytope forgets coefficient heights.
  • DAG algebra: A two-terminal weighted DAG computes the minimum over source-to-sink path weights, yielding a min-plus path polynomial.Series composition adds path polynomials, while parallel composition takes their minimum.
  • Quotients and triality: Different DAG topologies can compute the same function, so graph equivalence relations remove excess structure at formal and function levels.The congruences are compatible with series and parallel composition.
  • Triality theorem: Theorem 1 states that each quotient produces a semiring isomorphic to its associated polynomial and polyhedron, with commuting horizontal isomorphisms and surjective vertical homomorphisms.Thus graph, algebra, and geometry represent the same semiring at each level.

3 A complete calculus of invariant operations on DAG equivalences

The paper gives a complete operational calculus for reducing equivalent two-terminal DAGs to canonical formal and function-level normal forms. These normal forms characterize both graph congruences and their decidability.

  • Canonical forms: The deshared normal form Df(G) replaces a tropical polynomial by a parallel bundle of chains, one chain per monomial.Edges in each chain follow variable order, making the polynomial explicit in graph form.
  • Canonical forms: Mediant deletion removes dominated chains from Df(G), producing the function normal form Dv(G).The four local operations realize semiring properties and connect equivalent graph representations.
  • Reduction: A finite sequence of formal moves carries every graph to Df(G), with one vertex split per path intersection.Mediant deletions then carry Df(G) to Dv(G).
  • Canonicity: Df(G)=Df(G′) exactly characterizes formal equivalence, while Dv(G)=Dv(G′) exactly characterizes function equivalence.The two canonical forms therefore distinguish the two congruence levels.
  • Canonicity: The chains of Dv(G) are precisely the vertices of Γ(fG), and both graph congruences are decidable.This links the function normal form directly to the extended Newton polyhedron.
  • Connectivity: Two graphs are connected by formal moves exactly when they are formally equivalent, and adding mediant deletions yields function equivalence.Both sides reduce to the same canonical normal form.

4 Substitution geometry

The section analyzes semiring-identity substitutions as dimension-reduction operations across graphs, polynomials, polyhedra, and decision boundaries. Both substitutions can lose information and may leave the class of proper-subset DPs.

  • Identity substitutions: The two identity substitutions set x_i to +∞ or 0, corresponding respectively to the min-identity and +-identity.They are denoted Π_i and Q_i and reduce the variable count.
  • Geometric correspondence: Proposition 3 shows that Π_i and Q_i act through corresponding transformations in graph, algebraic, polyhedral, and hypersurface languages.Q_i(fG) ≤ Π_i(fG) pointwise because a face lies inside its shadow.
  • Π_i: Π_i keeps monomials with α_i=0 and restricts the extended Newton polyhedron to a coordinate face.On graphs, it deletes every x_i-edge; on the decision boundary, it retains strategies that ignore position i.
  • Q_i: Q_i projects along coordinate i, reweights every x_i-edge to 0 before merging, and slices the tropical hypersurface at x_i=0.The graph rule is applied on the deshared canonical form because general contraction can alter source-to-sink paths.
  • Identification failure: Neither substitution is injective, and each can fail to remain closed within the DP class.In Figure 1, neither maps the proper-subset instance to a proper-subset instance.

5 A hierarchy beyond series and parallel

Series and parallel composition are insufficient for building all dynamic-program topologies, and terminal-only edge substitutions still miss compositions that identify internal vertices.

  • A hierarchy beyond series and parallel: Series and parallel operations extend time steps or update prior expressions, but they are doubly insufficient for representing DP-instance topologies.These operations correspond to two modifications of Bellman expressions at time t.
  • A hierarchy beyond series and parallel: Figure 1 exhibits two length-3 problems that both identity substitutions map to the same length-2 object, despite differing by the all-ones monomial.The all-ones monomial is redundant under the projection.
  • A hierarchy beyond series and parallel: The Wheatstone edge substitution is not generated by series and parallel composition because the Wheatstone graph is non-series-parallel.This establishes Series-parallel ⊊ terminal-only.
  • A hierarchy beyond series and parallel: Clamped min-subarray exceeds terminal-only composition by gluing internal vertices so subarrays can cross the composition boundary.The construction identifies both terminals and the last internal vertex of A with the first internal vertex of B.

6 Conclusion

The conclusion presents graph, algebra, and polyhedron as exactly transferable descriptions of compositional structure, while negative results bound what min-plus structure alone can achieve for length generalization.

  • 6 Conclusion: The triality transfers compositional structure exactly among graph, algebra, and polyhedron representations.The invariant calculus identifies structural differences that are artifacts of DAG encoding rather than properties of the computed function.
  • 6 Conclusion: Semiring-native substitutions cannot lift polyhedral geometry from length T to length T+1.This is one of the paper’s two structural negatives for length generalization.
  • 6 Conclusion: Series-parallel operations do not generate all DAG topologies, and terminal-only operations do not capture all dynamic-program compositions.Together these are the paper’s doubly incomplete compositional symmetries.
  • 6 Conclusion: The tropical semiring uses min as addition and ordinary addition as multiplication, with identities +∞ and 0 respectively.Its idempotent addition makes it a semiring rather than a ring.

B.3 The geometric dictionary

The geometric dictionary links tropical polynomials to domes, Newton polyhedra, and hypersurfaces, while two-terminal DAGs map to polynomials through path sums and composition.

  • B.3 The geometric dictionary: The dome D(f) is the region below a tropical polynomial’s graph, with one facet per monomial and ridges where the function bends.For the example f = min(4, 2+x, 1+2x, 3+3x), vertices project to tropical zeroes {−2, 1, 2}.
  • B.3 The geometric dictionary: The extended Newton polyhedron is the convex hull of lifted support extended upward, and its lower faces encode polynomial evaluation.Equal extended Newton polyhedra correspond exactly to polynomials computing the same function.
  • B.3 The geometric dictionary: The tropical hypersurface is the locus where at least two monomials tie for the minimum, forming the decision boundary between regions of linearity.For min(0, x, y), it consists of three rays meeting at the origin.
  • B.3 The geometric dictionary: A two-terminal DAG’s path polynomial is the tropical sum of monomials contributed by its source-to-sink paths.Series composition becomes tropical multiplication, while parallel composition becomes tropical addition.

C Polynomials, configurations, and polyhedra

Normal-form configurations, extended Newton polyhedra, and quotient congruences organize formal polynomials and computed functions into compatible semiring descriptions.

  • C Polynomials, configurations, and polyhedra: Normal-form lifted configurations form a commutative idempotent semiring under vertical-minimum union and Minkowski addition.The isomorphism maps normal-form formal tropical polynomials onto these configurations.
  • C Polynomials, configurations, and polyhedra: The extended Newton polyhedron is obtained by convexifying lifted support and adding the upward ray, making convexity the second quotient.Its lower hull determines the polyhedron and corresponds bijectively to tropical polynomial functions.
  • C Polynomials, configurations, and polyhedra: Congruence quotients preserve semiring structure when the underlying isomorphism relates equivalent elements.The induced map on quotient classes is well-defined, injective, surjective, and a homomorphism.
  • C Polynomials, configurations, and polyhedra: For two-terminal DAGs, series maps to polynomial addition and parallel maps to minimum, so the associated graph equivalences are compatible with both compositions.Normal form commutes with these operations.

D Proof of the triality (Theorem 1)

The triality identifies graph, formal-polynomial, and geometric representations through semiring isomorphisms, then descends these correspondences to computed-function equivalence classes.

  • Function-row descent: The quotient relations are congruences, so the operations remain well-defined after identifying representations with the same formal object or computed function.The descent lemma applies because the matched relations are congruences.
  • Formal-row isomorphism: Surjectivity is constructive: a normal-form polynomial becomes a parallel bundle containing one chain for each support monomial.Each chain contains variable-labelled edges followed by one coefficient edge.
  • Formal-row isomorphism: The graph-to-polynomial map is an isomorphism onto formal tropical polynomials, and support configurations provide the next representation.The identities map to the empty configuration and the single zero configuration.
  • Function-row descent: Two graphs are function-equivalent exactly when their path polynomials evaluate equally, while polynomial-function equivalence matches equality of extended Newton polyhedra.The congruences correspond under the formal-row isomorphisms, allowing the construction to descend to function rows.

E Invariance: normal form and completeness

The section constructs canonical graph normal forms and proves that local invariant operations capture precisely the structural redundancies of two-terminal DAG representations.

  • Normal forms: Desharing produces one canonical chain per support monomial, while mediant deletion removes chains whose lifted points are not vertices of the extended Newton polyhedron.The deshared form represents the polynomial; the second pass represents the computed function.
  • Normal forms: Π(G)=Σ_v(P(v)−1) counts the exact number of vertex splits needed to transform a two-terminal DAG into deshared form.Π(G)=0 characterizes deshared graphs, and each available split reduces the count by one.
  • Invariant operations: Series reweighting, parallel bookkeeping, tropical-zero adjunction, and vertex splitting preserve the path-polynomial class.Vertex splitting preserves every source-to-sink path exactly once, with merging as its inverse.
  • Mediant deletion: A chain can be deleted exactly when its lifted point lies weakly above the others’ lower hull, equivalently when it is never the unique minimizer.At most d+1 chains suffice for a deletion certificate by Carathéodory’s theorem.
  • Completeness: The reduction is complete and canonical: graphs with the same computed function reduce to the same normal form and are connected by invertible invariant moves.The mediant pass preserves exactly the vertices of the extended Newton polyhedron.

F Geometry of the two substitutions

The two identity substitutions have distinct geometric actions across graphs, polynomials, polyhedra, and hypersurfaces, and their relationship exposes non-injectivity and composition limits.

  • P_i substitution: Setting x_i=+∞ deletes every monomial containing x_i and corresponds graphically to removing paths that use an x_i-edge.Geometrically, it selects the α_i=0 supporting face of the extended Newton polyhedron.
  • Q_i substitution: The hypersurface of Q_i is obtained from the coordinate-stable cells of the original hypersurface after projecting away coordinate i, with a correction for merged monomials.Monomials sharing a projected exponent can create full-dimensional cells that must be removed.
  • Q_i substitution: Setting x_i=0 reweights every x_i-edge to zero, projects lifted supports while retaining coefficients, and keeps the least coefficient when exponents collide.This operation is reweighting rather than contraction, because contraction can change source-to-sink paths.
  • Comparison: Pointwise, Q_i(f_G)≤P_i(f_G): the coordinate face of the polyhedron lies inside its coordinate shadow.This is the geometric relation between the two identity substitutions.
  • Composition boundary: Series and parallel composition cannot generate every two-terminal DAG, because substituting single edges into the Wheatstone graph yields a non-series-parallel graph.The Wheatstone graph is the smallest non-series-parallel two-terminal example described here.
Loading 2608.25034v1…