Elamur Research⌕
☰
home / papers / 2026 / Examining Algebraic Recombination for Compositional Generalisation

Examining Algebraic Recombination for Compositional Generalisation

Summary

Explicitly compositional semantic parsers such as LeAR generalise well to new combinations of familiar parts. However, their latent syntax is projective, so they cannot represent crossing dependencies. These occur in real language, for example in English long-distance wh-movement or in freer word-order languages. The authors propose DeAR (Dependency Algebraic Recombination), which keeps LeAR's two-stage design: a Composer that induces a latent structure and a Solver that labels its edges with semantic relations, both trained with reinforcement learning. DeAR replaces the binary constituency tree with an unconstrained dependency tree built by repeatedly selecting head–dependent arcs. It is compared with projective baselines on SLOG, an English sentence-to-logical-form benchmark whose generalisation split targets structural recombination. DeAR handles some structurally complex, non-projective cases better. Its overall accuracy drops modestly, particularly on long and deeply nested sentences, because its search space is far larger. The authors interpret this as an expressivity–efficiency trade-off. They argue that linguistically motivated constraints will be needed to build parsers that cope with natural, multilingual data.

Key points

  • DeAR's code is public at github.com/JoaquinCardonaRuiz/thesis-compositionality.
  • SLOG extends COGS with harder structural generalisation, including non-projective dependencies. Its test set is divided into categories, each containing 1000 examples, and targets are Lambda-Calculus-style logical forms.
  • Reference results cited in the paper: LeAR reaches 97.7% accuracy on COGS, and the AM parser scores 70.8% on SLOG (Li et al., 2023).
  • During training, DeAR's structural hypothesis diversity is about 0.8, compared with about 0.2 for LeAR. DeAR converges more slowly, and its higher Composer rewards do not lead to better generalisation.
  • Limitations include a single run per model, no hyper-parameter search, and synthetic English-only data. LeAR and DeAR were trained on CPU.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Linguistics & languages

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.63317/2cuajw7n68ry

@inproceedings{ruiz2026examining,
  title = {{Examining Algebraic Recombination for Compositional Generalisation}},
  author = {Ruiz, Joaquin Cardona and Fokkens, Antske and Donatelli, Lucia},
  booktitle = {Proceedings of the 15th Workshop on Cognitive Modeling and Computational Linguistics},
  year = {2026},
  doi = {10.63317/2cuajw7n68ry},
  url = {https://doi.org/10.63317/2cuajw7n68ry}
}

References

41 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Jacob Andreas. 2020. Good-Enough Compositional Data Augmentation. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7556–7566, Online. Association for Computational Linguistics (ACL). find our card
  2. Noam Chomsky. 1965. Aspects of the Theory of Syntax, 50th edition. The MIT Press, Cambridge, MA. find
  3. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. 2019a. Measuring Compositional Generalization: A Comprehensive Method on Realistic Data. In International Conference on Learning Representations. find
  4. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. 2019b. Universal transformers. In International Conference on Learning Representations. find
  5. Dan Flickinger, Emily M. Bender, and Stephan Oepen. 2014. Towards an Encyclopedia of Compositional Semantics: Documenting the Interface of the English Resource Grammar. In Proceedings of the 9th International Conference on Language Resources and Evaluation (LREC’14), pages 875–881, Reykjavik, Icelan… find
  6. Jerry A. Fodor and Zenon W. Pylyshyn. 1998. Connectionism and cognitive architecture: A critical analysis. Cognition, 28(1):3–71. find
  7. Jonas Groschwitz, Matthias Lindemann, Meaghan Fowlie, Mark Johnson, and Alexander Koller. 2018. AMR dependency parsing with a typed semantic algebra. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1831–1841, Melbourne, Austra… find
  8. Carlos Gómez-Rodríguez. 2016. Restricted non-projectivity: Coverage vs. efficiency. Computational Linguistics, 42(4):809–817. find
  9. Jiří Havelka. 2007. Beyond projectivity: Multilingual evaluation of constraints and measures on non-projective structures. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 608–615, Prague, Czech Republic. Association for Computational Linguistics (ACL)… find
  10. David G. Hays. 1964. Dependency theory: A formalism and some observations. Language, 40(4):511–525. find
  11. Jonathan Herzig and Jonathan Berant. 2021. Span-based semantic parsing for compositional generalization. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), page… find
  12. Kristen Howell and Olga Zamaraeva. 2018. Clausal modifiers in the grammar matrix. In Proceedings of the 27th International Conference on Computational Linguistics, pages 2939–2952, Santa Fe, NM, USA. Association for Computational Linguistics (ACL). find
  13. Theo Janssen. 2012. Compositionality: Its Historic Context. In The Oxford Handbook of Compositionality. Oxford University Press, Oxford. find
  14. Daniel Jurafsky and James H. Martin. 2026. Speech and Language Processing, 3rd edition. Draft of January 6, 2026. https://web.stanford.edu/~jurafsky/slp3/. ↗
  15. Sylvain Kahane, Alexis Nasr, and Owen Rambow. 1998. Pseudo-projectivity: A polynomially parsable non-projective dependency grammar. In COLING 1998 Volume 1: The 17th International Conference on Computational Linguistics. find
  16. Najoung Kim and Tal Linzen. 2020. COGS: A Compositional Generalization Challenge Based on Semantic Interpretation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 9087– 9105, Online. Association for Computational Linguistics (ACL). find
  17. Najoung Kim, Tal Linzen, and Paul Smolensky. 2022. Uncontrolled Lexical Exposure Leads to Overestimation of Compositional Generalization in Pretrained Models. arXiv:2212.10769. — [arXiv:2212.10769](https://arxiv.org/abs/2212.10769) find
  18. Yoon Kim. 2021. Sequence-to-sequence learning with latent neural grammars. In Proceedings of the 35th International Conference on Neural Information Processing Systems, pages 26302– 26317, Red Hook, NY, USA. Curran Associates Inc. find
  19. Marco Kuhlmann. 2013. Mildly non-projective dependency grammar. Computational Linguistics, 39(2):355–387. find
  20. Brenden M. Lake and Marco Baroni. 2018. Generalization without systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks. In Proceedings of the 35th International Conference on Machine Learning (ICML 2018), pages 4487–4499, Stockholm, Sweden. Proceedings of Machine Learni… find
  21. Brenden M. Lake, Ruslan Salakhutdinov, and Joshua B. Tenenbaum. 2015. Human-level concept learning through probabilistic program induction. Science, 350(6266):1332–1338. find
  22. Bingzhi Li, Lucia Donatelli, Alexander Koller, Tal Linzen, Yuekun Yao, and Najoung Kim. 2023. SLOG: A Structural Generalization Benchmark for Semantic Parsing. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 3213–3232, Singapore. Association for Compu… find
  23. Chenyao Liu, Shengnan An, Zeqi Lin, Qian Liu, Bei Chen, Jian-Guang Lou, Lijie Wen, Nanning Zheng, and Dongmei Zhang. 2021. Learning Algebraic Recombination for Compositional Generalization. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 1129–1144, Online. Associ… find
  24. Qian Liu, Shengnan An, Jian-Guang Lou, Bei Chen, Zeqi Lin, Yan Gao, Bin Zhou, Nanning Zheng, and Dongmei Zhang. 2020. Compositional generalization by learning analytical expressions. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 11416–11427, Red… find
  25. João Loula, Marco Baroni, and Brenden Lake. 2018. Rearranging the familiar: Testing compositional generalization in recurrent networks. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 108–114, Brussels, Belgium. Association for Computa… find
  26. Igor A. Melčuk. 1988. Dependency Syntax: Theory and Practice. State University of New York Press, Albany, NY. find
  27. Joakim Nivre. 2006. Constraints on non-projective dependency parsing. In 11th Conference of the European Chapter of the Association for Computational Linguistics, pages 73–80, Trento, Italy. Association for Computational Linguistics (ACL). find
  28. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34(4):513–553. find our card
  29. Inbar Oren, Jonathan Herzig, Nitish Gupta, Matt Gardner, and Jonathan Berant. 2020. Improving Compositional Generalization in Semantic Parsing. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 2482– 2495, Online. Association for Computational Linguistics (ACL). find
  30. Barbara Partee. 2004. Compositionality. In Compositionality in Formal Semantics: Selected Papers by Barbara H. Partee. Blackwell Publishing, Malden. find
  31. Linlu Qiu, Peter Shaw, Panupong Pasupat, Pawel Nowak, Tal Linzen, Fei Sha, and Kristina Toutanova. 2022. Improving Compositional Generalization with Latent Structure and Data Augmentation. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Lingui… find
  32. Peter Shaw, Ming-Wei Chang, Panupong Pasupat, and Kristina Toutanova. 2021. Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both? In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International… find
  33. Kai Sheng Tai, Richard Socher, and Christopher D. Manning. 2015. Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural La… find
  34. Pia Weißenhorn. 2022. Investigations on what makes compositional generalization challenging. Master’s thesis, Saarland University. find
  35. Yuekun Yao and Alexander Koller. 2022. Structural generalization is hard for sequence-to-sequence models. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 5048–5062, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics (ACL). find
  36. Yang Yu. 2018. Towards Sample Efficient Reinforcement Learning. In Proceedings of the 27th International Joint Conference on Artificial Intelligence Early Career, pages 5739–5743. International Joint Conferences on Artificial Intelligence Organization (IJCAI). find
  37. Hao Zheng and Mirella Lapata. 2022. Disentangled Sequence to Sequence Learning for Compositional Generalization. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 4256–4268, Dublin, Ireland. Association for Computational Linguis… find
  38. Wang Zhu, Peter Shaw, Tal Linzen, and Fei Sha. 2021. Learning to generalize compositionally by transferring across semantic parsing tasks. arXiv:2111.05013. — [arXiv:2111.05013](https://arxiv.org/abs/2111.05013) find
  39. Shawn Tan, Yikang Shen, Zhenfang Chen, Aaron Courville, and Chuang Gan. 2023. Sparse universal transformer. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 169–179, Singapore. Association for Computational Linguistics (ACL). find
  40. Stephen Tratz and Eduard Hovy. 2011. A fast, accurate, non-projective, semantically-enriched parser. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1257–1268, Edinburgh, Scotland, UK. Association for Computational Linguistics (ACL). find
  41. Antoine Venant and Alexander Koller. 2019. Semantic expressive capacity with bounded mem- find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/ruiz-2026-examining-algebraic-recombination-compositional-generalisation/