Research map / Learning theory and algorithms / Combinatorial and search optimization
Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Tropical Attention, which replaces softmax dot-product attention with max-plus scoring based on the tropical Hilbert metric, and tests it on combinatorial and NP-hard algorithmic reasoning tasks for OOD length, value, and noise generalization.
Problem
Softmax attention produces dispersed, smooth decision boundaries and fails to generalize out-of-distribution (length, value, noise) on combinatorial and dynamic-programming algorithmic reasoning tasks.
Approach
Lift queries, keys, and values into tropical projective space and compute attention scores with the negative tropical Hilbert projective metric, aggregating with a max-plus matrix-vector product, so the attention is piecewise-linear, 1-Lipschitz, and temperature-free.
Key results
- On Length OOD, Tropical Transformer reaches 97.00 Micro-F1 on ConvexHull versus 42.75 for vanilla and 53.83 for adaptive UT w/ ACT, and wins on all eleven tasks.
- Tropical Transformer is reported as 3x-9x faster at inference and uses about 20% fewer parameters (40,961 vs 50,242) than Universal Transformer baselines.
- On Long Range Arena, the model averages 72.79 across tasks, ranking second overall behind MEGA (86.25).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace softmax attention with Tropical Attention | Transformer · Combinatorial tasks, Length OOD | Micro-F1 / MSE | Helped |
| Replace softmax attention with Tropical Attention | Transformer · Quickselect, Value OOD | Micro-F1: 74.30\std{1.99} -> 71.10\std{3.11} | Hurt |
| Replace softmax attention with Tropical Attention | Transformer · SCC, Value OOD | Micro-F1: 81.38\std{2.62} -> 74.86\std{5.01} | Hurt |
| Replace softmax attention with Tropical Attention | Transformer · BalancedPartition, Value OOD | Micro-F1: 63.40\std{4.29} -> 55.76\std{5.63} | Hurt |
| Replace softmax attention with Tropical Attention | Transformer · 3SUM, Value OOD | Micro-F1: 26.25\std{3.50} -> 22.00\std{2.16} | Hurt |
| Replace softmax attention with Tropical Attention | Transformer · SCC, Perturbative Noise | Micro-F1: 71.33\std{1.96} -> 69.86\std{4.17} | Hurt |
| Replace softmax attention with Tropical Attention | Transformer · LRA average | accuracy: 86.25 -> 72.79 | Mixed |
| Use Tropical Transformer instead of Universal Transformer with ACT | Transformer · All tasks | inference time: 3\times-$9\times faster | Helped |
| Use Tropical Transformer instead of Universal Transformer with ACT | Transformer · All tasks | parameter count: 20\% fewer parameters | Helped |
Surprising findings
- Adaptive softmax attention scores worse than vanilla on several Value OOD tasks, e.g. Knapsack 26.92 vs 38.87.
- On Long Range Arena the tropical model is weaker than MEGA on Text, Retrieval, and Image, though it is best on ListOps and Pathfinder.
Limitations
- Evaluation limited to combinatorial tasks; not demonstrated on generative language modeling.
- Computational and memory overhead of tropical operations and Hilbert metric may add runtime costs.
- Worst-case expressivity results require head width growing with active path monomials.
Experimental setup
Datasets: Floyd-Warshall synthetic graphs QuickSelect synthetic 3SUM synthetic Subset-Sum synthetic Balanced Partition synthetic 0-1 Knapsack synthetic Fractional Knapsack synthetic Convex Hull synthetic SCC synthetic Bin Packing synthetic Minimum Coin Change synthetic Long Range Arena
Benchmarks: eleven custom combinatorial tasks (length OOD, value OOD, perturbative noise) Long Range Arena (ListOps, Text, Retrieval, Image, Pathfinder)
Metrics: Micro-F1 MSE accuracy inference time (ms) parameter count
Baselines: Vanilla softmax Transformer Adaptive softmax attention Universal Transformer with ACT Transformer Longformer Linformer Performer MEGA Fourierformer
Builds on: Universal Transformer adaptive softmax attention Long Range Arena CLRS
Closest papers by meaning
- Learning Linear Attention in Polynomial Time (NeurIPS 2025 · similarity 0.85)
- Topology of Reasoning: Understanding Large Reasoning Models through Reasoning Graph Properties (NeurIPS 2025 · similarity 0.84)
- Efficient Reasoning via Constrained Optimization in Latent Space (NeurIPS 2026 · similarity 0.84)
- MINT-CoT: Enabling Interleaved Visual Tokens in Mathematical Chain-of-Thought Reasoning (NeurIPS 2025 · similarity 0.84)
- Attention Mechanism, Max-Affine Partition, and Universal Approximation (NeurIPS 2025 · similarity 0.84)
- Geometry of Reason: Spectral Signatures of Valid Mathematical Reasoning (ICML 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.