Per-Layer Routing over Heterogeneous Experts for Shortest-Path Neural Algorithmic Reasoning

Neural Algorithmic Reasoning (NAR) asks whether a neural processor can carry a classical algorithm beyond its training scale. Shortest-path algorithms differ in how their inner step aggregates and composes path lengths, yet most NAR processors commit to a single aggregation geometry, and an end-to-end selector trained on task loss alone falls short of the best single algebra on four of seven CLRS-30 tasks. We introduce PSAR, a processor that pools three attention algebras (softmax, α-entmax, tropical max-plus) and a triangular multiplicative pair-state update (TMU), and selects one expert per hint step with a hard router trained in stages over frozen, then jointly tuned, experts. Under teacher-forced evaluation on three CLRS-30 shortest-path tasks, no single expert is best on all three. PSAR, trained with the same recipe on each task, matches or exceeds the strongest attention algebra on every task, but falls below standalone TMU on Dijkstra. On Floyd–Warshall, most of the observed gain over attention is already present in the pair-state expert: standalone TMU is 13.0 percentage points above the strongest attention algebra at N=32. On the same task at N=48 and 64, PSAR outperforms a parameter-matched TMU by 7.2 and 8.1 pp, and surpasses its own step schedule retrained as a fixed routing rule by 16.1 and 12.6 pp. However, when PSAR and the parameter-matched TMU are trained and evaluated on their own predictions, the TMU leads on Floyd–Warshall. For shortest-path NAR, these results identify the pair-state update as a primitive worth adding to attention-based processors, and show that the ordering between processors can reverse with the hint contract under which they are trained and compared.