Research map / Architectures and efficiency / Attention and transformers
Compositional Reasoning with Transformers, RNNs, and Chain of Thought
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Compares transformers, RNNs, and chain-of-thought transformers on Compositional Reasoning Questions (tree-structured evaluation like Boolean formulas), proving each needs a size-growing resource (depth, hidden dimension, or CoT tokens) and giving matching constructions.
Problem
Which neural architectures (deep transformers, RNNs, transformers with chain of thought) can solve compositional reasoning over tree structures such as Boolean formula evaluation, and what resources each needs as input size grows.
Approach
Defines Compositional Reasoning Questions (CRQs) as tree-structured argmax-of-inner-product evaluation, proves NC1-hardness, and shows a trade-off: transformers need depth logarithmic in tree depth, RNNs need logarithmic hidden dimension under a memory-rank (post-order, stack-friendly) input ordering, and CoT transformers need n CoT tokens with constant depth.
Key results
- Constant-depth transformers cannot solve CRQs unless TC0 = NC1; depth-logarithmic transformers suffice.
- RNNs need Omega(n) hidden size under adversarial ordering but O(log n) hidden dimension with memory-rank ordering; memory rank is a tight lower bound.
- A 2-layer transformer with n chain-of-thought tokens solves all CRQs of size n, with O(log n) bit precision.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase transformer depth to match the CRQ tree depth | Transformer · CRQs with at most n nodes and depth at most L | solvability: depth L-1 | Helped |
| Keep transformer depth constant | Transformer · CRQs of size n | solvability: depth L | Hurt |
| Order RNN inputs by memory-rank sort | RNN · CRQs with binary trees | hidden dimension: O(n) -> O(d\log(n)) | Helped |
| Use the bad ordering of nodes | RNN · CRQs on a balanced binary tree of size n | hidden state size: \Omega(n) bits | Hurt |
| Add n chain-of-thought tokens in reverse BFS order | Transformer · CRQs with n nodes | solvability: n | Helped |
| Limit chain-of-thought tokens to O(log(n)) | Constant-depth transformer · CRQs of size n | solvability: O(\log(n)) | Hurt |
| Use logarithmic hidden dimension rather than constant hidden dimension | RNN · CRQs with a suitable input ordering | solvability: O(\log n) | Helped |
Surprising findings
- No single architecture is strictly best on CRQs: each minimizes one resource at the cost of others.
- RNN hardness depends heavily on input ordering: adversarial order forces Omega(n) hidden size.
Experimental setup
Baselines: Feng et al. arithmetic chain-of-thought
Builds on: chain of thought NC1-completeness of Boolean formula evaluation TC0 characterization of transformers
Closest papers by meaning
- Transformers Provably Solve Parity Efficiently with Chain of Thought (ICLR 2025 · similarity 0.88)
- Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization (NeurIPS 2025 · similarity 0.87)
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · similarity 0.87)
- Are Transformers Able to Reason by Connecting Separated Knowledge in Training Data? (ICLR 2025 · similarity 0.87)
- When can transformers reason with abstract symbols? (ICLR 2024 · similarity 0.86)
- Attention as a Hypernetwork (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.