TL;DR
Can neural networks genuinely learn hierarchical, compositional meaning, and what algorithms do they implement internally? By training networks on nested arithmetic expressions, this paper demonstrates that recursive networks implement a clean geometric composition function, while sequential Gated Recurrent Units (GRUs) approximate a "cumulative" running-total strategy rather than an explicit recursive stack. To prove this, the authors introduce diagnostic classifiers—probing internal representations at each step against specific algorithmic hypotheses—pioneering a widely applicable tool for opening neural network black boxes.
What Problem Does This Paper Address?
A defining property of human language is hierarchical compositionality: meanings of larger expressions are systematically composed from their sub-phrases. While recurrent models often perform well on downstream natural language processing tasks, it remains unclear whether they truly encode hierarchical structures or simply exploit shallow statistical shortcuts.
Studying this directly in natural language is tricky due to lexical ambiguities, irregular grammar, and idiomatic exceptions. To isolate structural compositionality, the authors construct an artificial, fully bracketed arithmetic language with unambiguous syntax and exact ground-truth semantics (e.g., ( 5 - ( ( 2 - 3 ) + 7 ) )). They set out to answer:
- Can recursive and recurrent networks learn to compute such hierarchical semantics and generalize to unseen expression lengths?
- How do these networks represent and compute intermediate meanings under the hood?
Methods
The authors compare tree-structured networks against sequential networks:
- TreeRNNs (Recursive): Process syntax trees bottom-up using a learned 2D composition function. The authors analyze this 2D space geometrically via a project-sum-squash decomposition: dissecting how left children, right children, and operators are projected, linearly combined, and squashed by $\tanh$.
- SRNs and GRUs (Recurrent): Process token sequences incrementally, reading one character/token (including brackets) at a time.
- Diagnostic Classifiers: Because high-dimensional GRU states cannot be easily understood via individual cell visualizations, the authors propose training simple linear classifiers on hidden state vectors $h_t$ at every time step to predict the theoretical values of variables from two distinct computational strategies:
- Recursive Strategy: Uses a stack to pause computation and push/pop intermediate subtree results and operators.
- Cumulative Strategy: Maintains a running estimate of the total expression outcome at each token, using an operator stack only to track whether incoming values should be added or subtracted (the mode).
Datasets
- Synthetic Arithmetic Language: Consists of integers from $-10$ to $10$, operators
+and-, and parentheses(and). Expressions are categorized by numeral length $L_k$ ($k$ numbers). - Splits:
- Training set: 3,000 sampled expressions each from $L_1, L_2, L_4, L_5,$ and $L_7$ (15,000 total).
- Test set: Expressions sampled from $L_1$ through $L_9$. Unseen lengths ($L_3, L_6, L_8, L_9$) specifically test length interpolation and extrapolation. Subsets of fully left-branching ($L_{9L}$) and right-branching ($L_{9R}$) expressions are also evaluated.
Key Insights and Ideas
- TreeRNNs discover clean geometric composition: Even constrained to a 2D hidden state, TreeRNNs learn near-perfect arithmetic. Word embeddings project into nearly orthogonal subspaces for left vs. right arguments, and squashing shifts intermediate results onto horizontal/vertical lines depending on the operator, allowing unbounded recursive composition.
- GRUs compute running totals, not recursive stacks: Diagnostic classifiers demonstrate that the GRU does not maintain a stack of intermediate subtree results. Instead, its representations align strongly with a cumulative strategy, updating a global running total while tracking sign flips.
- Internal updates are continuous, not discrete: While theoretical symbolic execution makes sharp, jumpy updates upon closing parentheses, the diagnostic classifier trajectories reveal that the GRU updates its running total smoothly and continuously over time.
- Limitations of single-cell visualization: Visualizing individual gate activations or neuron firing patterns only highlights isolated features. Probing via diagnostic classifiers accounts for distributed representations where concepts span across multiple dimensions.
Key Results
- Task Performance & Generalization:
- TreeRNNs achieve near-perfect performance (0.98–0.99 accuracy on 6 of 8 runs).
- GRUs generalize well to unseen lengths ($L_3, L_6, L_8, L_9$), showing only mild error increases as length grows. Simple recurrent networks (SRNs) largely fail to generalize beyond their training lengths.
- Right-branching expressions ($L_{9R}$) are substantially harder for GRUs than left-branching ones ($L_{9L}$), whereas TreeRNNs are unaffected by branching direction.
- Diagnostic Classifier Alignment:
- Result prediction: On $L_9$ expressions, diagnostic predictions for the cumulative running total yield a Pearson correlation of $r = 0.95$ with true values, compared to only $r = 0.52$ for the recursive intermediate results.
- Operator mode prediction: The GRU encodes the cumulative mode ($+$ vs. $-$) with $0.98\text{--}1.0$ accuracy on lengths up to $L_5$, maintaining $0.93$ accuracy on $L_9$.
Limitations and Future Work
- Toy Language Domain: The task lacks the lexical diversity, ambiguity, and non-deterministic structures present in natural language.
- Right-Branching Discrepancy: The cumulative hypothesis does not fully explain why the GRU struggles significantly with right-branching trees, suggesting the network's internal policy deviates from the symbolic strategy in edge cases.
- Diagnosing Gates: The diagnostic classifiers used linear readouts on hidden states. Extending probes to nonlinear gates without introducing confounding capacity remains an open challenge.
- Scaling Up: The authors highlight extending diagnostic classifiers to state-of-the-art models on real-world NLP tasks (e.g., machine translation and language modeling) as the most critical next step.
Summary updated