Canonical Tropical Segment State

Implement a compact tropical segment state containing a support tensor of pairs (alpha, c), with alpha in R^d and c in R. A token or local graph edge emits a small state, such as one to four affine pieces from an MLP. For each new sequence position, perform series composition by forming pairwise sums: alpha_new[p,q] = alpha_old[p] + alpha_token[q] and c_new[p,q] = c_old[p] + c_token[q]. For branching alternatives, concatenate supports from the branches, which implements parallel composition. Canonicalize after every composition: merge duplicate alpha vectors by retaining the smallest c, then remove candidates failing the lower-hull feasibility test from the first idea. Evaluate the state on features x as output = min_p(c_p + dot(alpha_p,x)). During early training, optionally replace min with softmin at temperature tau and anneal tau toward zero; use subgradients or a straight-through rule at ties. The paper determines the composition laws and canonical geometric representation; support-size thresholds, LP tolerances, and temperature schedules are empirical. First test on subset-sum and DAG shortest-path tasks, training on lengths 8-16 and evaluating at lengths 32-64. Compare an LSTM, Transformer, ordinary min-plus recurrence, and the proposed state at equal parameter budgets. Track extrapolation accuracy, decision-boundary disagreement on sampled x, support size, and runtime. The target signal is slower error growth when sequence length doubles, with bounded support size and improved length-64 accuracy.