Neural networks have succeeded in many reasoning tasks. Empirically, these tasks require specialized network structures, e.g., Graph Neural Networks (GNNs) perform well on many such tasks, while less structured networks fail. Theoretically, there is limited understanding of why and when a network structure generalizes better than other equally expressive ones. We develop a framework to characterize which reasoning tasks a network can learn well, by studying how well its structure aligns with the algorithmic structure of the relevant reasoning procedure. We formally define algorithmic alignment and derive a sample complexity bound that decreases with better alignment. This framework explains the empirical success of popular reasoning models and suggests their limitations. We unify seemingly different reasoning tasks, such as intuitive physics, visual question answering, and shortest paths, via the lens of a powerful algorithmic paradigm, dynamic programming (DP). We show that GNNs can learn DP and thus solve these tasks. On several reasoning tasks, our theory aligns with empirical results.
This work seeks theoretical and empirical proof of the reasoning capacity of neural networks. The authors build on a body of research that demonstrates the usefulness of different neural network architectures for different reasoning problems. For example, Deep Sets have been proposed to answer questions about sets (e.g., a summary statistic), and GNNs about graph related problems, such as shortest path.
I anticipate that readers would be very satisfied with the intuition behind the main result: neural networks that “align” with known algorithmic solutions are better able to learn the solutions. Many architectures have been proposed over the years, often with a high-level justification for the architecture’s form. For example, Relation Networks noted the difficulty with learning n^2 relations using an MLP, which is an observation reflected in this work’s explanation of the difficulty with learning a for loop. 
Provided here is a justification for these high-level design decisions. The authors provide some theory and experimental results to demonstrate their proposed notion of alignment, and show that NNs that align with known algorithmic solution do well, while those that do not align do not do well. In particular, I appreciate both the positive and negative evidence, since demonstrating lack of alignment (and poor performance) is a necessary condition to show alongside alignment (and good performance).
I’d like to caution the authors regarding their main conclusion, which is stated a few times in the paper:
“This perspective suggests that whether a neural network can learn a reasoning task depends on whether there exists an algorithmic solution that the network aligns with”.
I think this logic is not precisely correct, and I would modify this to:
“If the structure of a neural network aligns with a known algorithmic solution, then it can more easily learn a reasoning task than a neural network does not align”. 
This is a subtle but important difference. In particular, the original logic does not capture situations where an algorithmic solution is not known, but a neural network can otherwise still learn a solution (consider object classification). I think even the corrected logic as I’ve spelled it out above might not be quite right either, since it does not consider situations where the algorithmic solution exists, but it obtuse. Would a neural network easily learn such a task? 
Overall I think the paper is clearly written, and the experiments are adequate. Unfortunately I am not well-versed in the theoretical literature on this topic, so my assessment of the proofs is limited, and I will need to defer to the other reviewers on these matters. My surface level assessment of them is that the logic seems generally sound, but I cannot make any strong statements placing them in the context of previous work, nor can I properly evaluate the nuances. Nonetheless, as a whole, I think this is a strong contribution and a nicely put together piece of work.