Tropical Attention: Neural Algorithmic Reasoning for Combinatorial
  Algorithms
Authors: name: Baran Hashemi, name: Kurt Pasque, name: Chris Teska, name: Ruriko Yoshida

Dynamic programming (DP) algorithms for combinatorial optimization problems
work with taking maximization, minimization, and classical addition in their
recursion algorithms. The associated value functions correspond to 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, a novel attention function that operates natively 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 algorithmic reasoning
tasks, surpassing softmax baselines while remaining stable under adversarial
attacks. We also present adversarial-attack generalization as a third axis for
Neural Algorithmic Reasoning benchmarking. Our results demonstrate that
Tropical attention restores the sharp, scale-invariant reasoning absent from
softmax.