# Compositional Generalization Across Distributional Shifts with Sparse Tree Operations

arXiv: https://arxiv.org/abs/2412.14076 · HTML: https://mlsanity.com/paper/2412.14076/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 77 references that are in the map.
- First posted on arXiv 18 Dec 2024.

## Builds on (most cited first, 30 of 42)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [On Layer Normalization in the Transformer Architecture](https://mlsanity.com/paper/2002.04745/) (2020)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [Analysis Methods in Neural Language Processing: A Survey](https://mlsanity.com/paper/1812.08951/) (2018)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Logic Tensor Networks](https://mlsanity.com/paper/2012.13635/) (2020)
- [Neural-Symbolic Learning and Reasoning: A Survey and Interpretation](https://mlsanity.com/paper/1711.03902/) (2017)
- [Language to Logical Form with Neural Attention](https://mlsanity.com/paper/1601.01280/) (2016)
- [Good-Enough Compositional Data Augmentation](https://mlsanity.com/paper/1904.09545/) (2019)
- [Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?](https://mlsanity.com/paper/2010.12725/) (2020)
- [The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers](https://mlsanity.com/paper/2108.12284/) (2021)
- [Randomized Positional Encodings Boost Length Generalization of Transformers](https://mlsanity.com/paper/2305.16843/) (2023)
- [Compositional generalization through meta sequence-to-sequence learning](https://mlsanity.com/paper/1906.05381/) (2019)
- [A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations](https://mlsanity.com/paper/2111.06077/) (2021)
- [Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architectures](https://mlsanity.com/paper/2007.08970/) (2020)
- [Tree-to-tree Neural Networks for Program Translation](https://mlsanity.com/paper/1802.03691/) (2018)
- [NeurASP: Embracing Neural Networks into Answer Set Programming](https://mlsanity.com/paper/2307.07700/) (2023)
- [Compositional Generalization via Neural-Symbolic Stack Machines](https://mlsanity.com/paper/2008.06662/) (2020)
- [Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets](https://mlsanity.com/paper/1503.01007/) (2015)
- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://mlsanity.com/paper/1906.10225/) (2019)
- [Sequence-Level Mixed Sample Data Augmentation](https://mlsanity.com/paper/2011.09039/) (2020)
- [Tree Transformer: Integrating Tree Structures into Self-Attention](https://mlsanity.com/paper/1909.06639/) (2019)
- [Meta-Learning to Compositionally Generalize](https://mlsanity.com/paper/2106.04252/) (2021)
- [DeepStochLog: Neural Stochastic Logic Programming](https://mlsanity.com/paper/2106.12574/) (2021)
- [Compositional generalization in a deep seq2seq model by separating syntax and semantics](https://mlsanity.com/paper/1904.09708/) (2019)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (2015)
- [Characterizing Intrinsic Compositionality in Transformers with Tree Projections](https://mlsanity.com/paper/2211.01288/) (2022)

## Built on by (most cited first, 5 of 5)

- [Behavioural vs. Representational Systematicity in End-to-End Models: An Opinionated Survey](https://mlsanity.com/paper/2506.04461/) (2025)
- [TRA: Better Length Generalisation with Threshold Relative Attention](https://mlsanity.com/paper/2503.23174/) (2025)
- [A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Condition](https://mlsanity.com/paper/2505.02627/) (2025)
- [Hey Pentti, We Did (More of) It!: A Vector-Symbolic Lisp With Residue Arithmetic](https://mlsanity.com/paper/2511.08767/) (2025)
- [Recursive Binding on a Budget: Subspace Carving in Order-p Tensor Memories](https://mlsanity.com/paper/2606.11391/) (2026)

## Abstract (arXiv)

Neural networks continue to struggle with compositional generalization, and this issue is exacerbated by a lack of massive pre-training. One successful approach for developing neural systems which exhibit human-like compositional generalization is textithybrid neurosymbolic techniques. However, these techniques run into the core issues that plague symbolic approaches to AI: scalability and flexibility. The reason for this failure is that at their core, hybrid neurosymbolic models perform symbolic computation and relegate the scalable and flexible neural computation to parameterizing a symbolic system. We investigate a textitunified neurosymbolic system where transformations in the network can be interpreted simultaneously as both symbolic and neural computation. We extend a unified neurosymbolic architecture called the Differentiable Tree Machine in two central ways. First, we significantly increase the model's efficiency through the use of sparse vector representations of symbolic structures. Second, we enable its application beyond the restricted set of tree2tree problems to the more general class of seq2seq problems. The improved model retains its prior generalization capabilities and, since there is a fully neural path through the network, avoids the pitfalls of other neurosymbolic techniques that elevate symbolic computation over neural computation.