We recently conducted an evaluation of algorithmic reasoning — the inputs are generated by executing an algorithm on a graph, and we ask whether existing neural network models (e.g., graph neural nets, transformers) can memorize or predict the execution outputs. Here are our findings from this evaluation: 1) Depth-first search (DFS) is notably hard to “learn” as compared to breadth-first search (BFS): for input sequences generated on Erdos-Renyi random graph inputs with 16 nodes, existing neural net architectures predict DFS with less than 40% accuracy, whereas for BFS, the accuracy is nearly 100%. This is also consistent with earlier findings from the CLRS benchmark. Our explanation is that, for a model to predict DFS, it must first identify the node IDs; if the IDs are randomly assigned in the input graph, it’s hard to learn this permutation. For BFS, on the other hand, at each step, given a node, the search process pushes to the entire neighborhood of that node. 2) Learning multiple algorithms is as easy as learning a single algorithm: for all twelve algorithms tested in this evaluation, on average, training a shared base encoder with a separate prediction head for each algorithm turned out to perform as well as, or even slightly better than, training a separate model for each algorithm. 3) For text description versions of the same problem, fine-tuning open-source LLMs follows similar patterns as 1) and 2), but the evaluation is a lot more difficult. Link to arXiv paper: (Tables 4 and 5 in particular) Tagging a few co-authors @life_olivers @ZhenshuoZhang @EdgarDobriban who are on this paper. Ideas for this work are also based on prior work with @Wu_Sen.