Improving the Compositionality of Triplet-Based Neural Algorithmic Reasoners

Neural algorithmic reasoning (NAR) aims to train neural networks that emulate classical algorithms. Despite substantial progress on most of CLRS-30, Floyd-Warshall remains one of the hardest tasks. This is surprising given that standard NAR architectures already emphasize triplet reasoning aligned with that algorithm. In this work, we identify an information bottleneck in how the standard CLRS-30 encoder and decoder represent edge-pointer probes. We remove this bottleneck by introducing higher-order information flow, improving the performance of the baseline NAR model on Floyd-Warshall from 46\% to 95\% and on Matrix Chain Order from 91\% to 98\%. Our results suggest that proper compositionality matters: the hardest failures in NAR can lie in interfaces and encodings, not only in the capacity or inductive bias of the processor itself.