# Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms

arXiv: https://arxiv.org/abs/2505.17190 · HTML: https://mlsanity.com/paper/2505.17190/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 10 of its 77 references that are in the map.
- First posted on arXiv 22 May 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 10 of 10)

- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Mega: Moving Average Equipped Gated Attention](https://mlsanity.com/paper/2209.10655/) (2022)
- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [On the Resurgence of Recurrent Models for Long Sequences -- Survey and Research Opportunities in the Transformer Era](https://mlsanity.com/paper/2402.08132/) (2024)
- [Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms](https://mlsanity.com/paper/1802.06440/) (2018)
- [Transformer with Fourier Integral Attentions](https://mlsanity.com/paper/2206.00206/) (2022)
- [Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution](https://mlsanity.com/paper/2305.01593/) (2023)

## Built on by (most cited first, 12 of 12)

- [AutoSOTA: An End-to-End Automated Research System for State-of-the-Art AI Model Discovery](https://mlsanity.com/paper/2604.05550/) (2026)
- [Quantitative Bounds for Length Generalization in Transformers](https://mlsanity.com/paper/2510.27015/) (2025)
- [Free Energy Mixer](https://mlsanity.com/paper/2602.07160/) (2026)
- [Can Transformers Really Do It All? On the Compatibility of Inductive Biases Across Tasks](https://mlsanity.com/paper/2607.17624/) (2026)
- [KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems](https://mlsanity.com/paper/2509.15239/) (2025)
- [HATSolver: Learning Groebner Bases with Hierarchical Attention Transformers](https://mlsanity.com/paper/2512.14722/) (2025)
- [Geometric Capacity of Transformers: A Tropical Geometry Perspective](https://mlsanity.com/paper/2604.14727/) (2026)
- [Classifiers in High Dimensional Hilbert Metrics](https://mlsanity.com/paper/2601.13410/) (2026)
- [Phylogenetic Tree Inference with Tropical Axial Attention](https://mlsanity.com/paper/2605.13894/) (2026)
- [A Symbolic Neural CPU for Quantization-Simulated Writeback and Interpretable Program Execution](https://mlsanity.com/paper/2607.10021/) (2026)
- [Laguerre Geometry for Interpreting Large Language Models](https://mlsanity.com/paper/2607.10578/) (2026)
- [On the Representational Geometry of Dynamic Programs](https://mlsanity.com/paper/2608.25034/) (2026)

## Abstract (arXiv)

Can algebraic geometry enhance the sharpness, robustness, and interpretability of modern neural reasoning models by equipping them with a mathematically grounded inductive bias? To answer this, we introduce Tropical Attention, an attention mechanism grounded in tropical geometry that lifts the attention kernel into tropical projective space, where reasoning is piecewise-linear and 1-Lipschitz, thus preserving the polyhedral decision structure inherent to combinatorial reasoning. We prove that Multi-Head Tropical Attention (MHTA) stacks universally approximate tropical circuits and realize tropical transitive closure through composition, achieving polynomial resource bounds without invoking recurrent mechanisms. These guarantees explain why the induced polyhedral decision boundaries remain sharp and scale-invariant, rather than smoothed by Softmax. Empirically, we show that Tropical Attention delivers stronger out-of-distribution generalization in both length and value, with high robustness against perturbative noise, and substantially faster inference with fewer parameters compared to Softmax-based and recurrent attention baselines. For the first time, we extend neural algorithmic reasoning beyond PTIME problems to NP-hard and NP-complete problems, paving the way toward sharper and more expressive Large Reasoning Models (LRMs) capable of tackling complex combinatorial challenges in phylogenetics, cryptography, particle physics, and mathematical discovery.