Compositional Reasoning with Transformers, RNNs, and Chain of Thought
This work addresses the fundamental limitations of neural architectures in handling complex reasoning tasks, which is crucial for advancing AI in domains requiring multi-step logic, but it is incremental as it builds on existing complexity theory.
The paper tackles the problem of compositional reasoning in language models by comparing transformers, RNNs, and transformers with chain of thought on Compositional Reasoning Questions, proving that none can solve these problems without hyperparameter growth (e.g., logarithmic depth for transformers) and providing constructions to overcome this hardness.
We study and compare the expressive power of transformers, RNNs, and transformers with chain of thought tokens on a simple and natural class of problems we term Compositional Reasoning Questions (CRQ). This family captures problems like evaluating Boolean formulas and multi-step word problems. Assuming standard hardness assumptions from circuit complexity and communication complexity, we prove that none of these three architectures is capable of solving CRQs unless some hyperparameter (depth, embedding dimension, and number of chain of thought tokens, respectively) grows with the size of the input. We also provide a construction for each architecture that solves CRQs. For transformers, our construction uses depth that is logarithmic in the problem size. For RNNs, logarithmic embedding dimension is necessary and sufficient, so long as the inputs are provided in a certain order. (Otherwise, a linear dimension is necessary). For transformers with chain of thought, our construction uses $n$ CoT tokens. These results show that, while CRQs are inherently hard, there are several different ways for language models to overcome this hardness. Even for a single class of problems, each architecture has strengths and weaknesses, and none is strictly better than the others.