Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms
Baran Hashemi, Kurt Pasque, Chris Teska, Ruriko Yoshida
Dynamic programming (DP) algorithms for combinatorial optimization problems work with taking max, min, and classical addition in their recursion algorithms and their value functions are associated with convex polyhedra in the max‑plus semiring. Existing Neural Algorithmic Reasoning models, however, rely on softmax‑normalized dot‑product attention where the smooth exponential weighting blurs these sharp polyhedral structures and collapses when evaluated on out‑of‑distribution (OOD) settings. We introduce Tropical attention, an attention function that operates originally in the max-plus semiring of tropical geometry. We prove that Tropical attention can approximate tropical circuits of DP-type combinatorial algorithms. We then propose that using Tropical transformers enhances empirical OOD performance in both length generalization and value generalization, on canonical algorithmic reasoning tasks, surpassing softmax baselines while remaining stable under adversarial perturbations. Our results demonstrate that Tropical attention restores the sharp, scale‑invariant reasoning absent from softmax.