Parallel Algorithms Align with Neural Execution
This work addresses a fundamental inefficiency in neural algorithmic reasoning, potentially improving training efficiency and performance for AI systems that execute algorithms, though it appears incremental as it adapts existing parallel algorithms to a specific framework.
The paper tackles the inefficiency of teaching sequential algorithms to neural algorithmic reasoners, which are inherently parallel processors, by proposing parallel algorithms that reduce redundant computations and layers. This approach drastically cuts training times and often achieves superior predictive performance, as demonstrated with implementations for searching, sorting, and finding strongly connected components in the CLRS framework.
Neural algorithmic reasoners are parallel processors. Teaching them sequential algorithms contradicts this nature, rendering a significant share of their computations redundant. Parallel algorithms however may exploit their full computational power, therefore requiring fewer layers to be executed. This drastically reduces training times, as we observe when comparing parallel implementations of searching, sorting and finding strongly connected components to their sequential counterparts on the CLRS framework. Additionally, parallel versions achieve (often strongly) superior predictive performance.