---
title: "Investigating More Explainable and Partition-Free"
description: "The authors replace this with a rule-generation perspective. 28 references. Among them: 0."
authors: ["Ziyao Xu", "Cong Wang", "Houfeng Wang"]
year: 2026
venue: "Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)"
source: "https://aclanthology.org/2026.acl-long.409/"
doi: "10.18653/v1/2026.acl-long.409"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/xu-2026-investigating-more-explainable-partition-free/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/xu-2026-investigating-more-explainable-partition-free/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2026](https://md.research.elamur.ai/free/en/papers/2026/page/37/) / Investigating More Explainable and Partition-Free Compositionality Estimation for LLMs: A Rule-Generation Perspective

# Investigating More Explainable and Partition-Free Compositionality Estimation for LLMs: A Rule-Generation Perspective

**Authors:** [Ziyao Xu](https://md.research.elamur.ai/free/en/authors/ziyao-xu/), [Cong Wang](https://md.research.elamur.ai/free/en/authors/cong-wang/) and [Houfeng Wang](https://md.research.elamur.ai/free/en/authors/houfeng-wang/) · **Year:** 2026 · **Venue:** [Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 2026](https://md.research.elamur.ai/free/en/venues/acl/2026/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2026.acl-long.409/) · [PDF](https://aclanthology.org/2026.acl-long.409.pdf) · [DOI 10.18653/v1/2026.acl-long.409](https://doi.org/10.18653/v1/2026.acl-long.409) · [OpenAlex](https://openalex.org/W7166883690)

**Citations:** 0 citations (OpenAlex, 2026-10-14)

## Summary
LLM compositionality is usually measured with compositional generalization tests, which have two weaknesses. First, they only score outputs, so they reveal little about how a model actually interprets the structure of the samples. Second, they rely on train/test splits that keep certain combinations unseen, but that assumption breaks down when massive pre-training corpora may already contain those combinations.

The authors replace this with a rule-generation perspective. The LLM gets a dataset produced by a compositional function that covers every component value. It must then write a program that reproduces all input–output pairs. The program is scored with the complexity-based theory of Elmoznino et al. (2025), which treats compositionality as how much the inputs help compress the outputs, using upper-bound estimates of Kolmogorov complexity.

Applied to reasoning and non-reasoning LLMs on a simple string-to-grid task, the method reveals distinct compositionality profiles and several deficiencies. This matters because the estimates are explainable and need no data partition, and they expose gaps that output-only evaluation can hide.

## Key points
- **Metric:** compositionality of a dataset is defined as K(D_Y) / K(D_Y | D_X), based on Kolmogorov complexity. Because K is uncomputable, upper bounds are used, and generated programs are turned into mapping tables via heuristic rules.
- **Task:** a string-to-grid mapping. One illustrative configuration in the paper uses N = 3, M = 6, U = 2 and d = 8 samples.
- **Result- vs rule-generation:** in the result-generation baseline, models get 8 samples and predict outputs for unseen inputs.
  - This baseline usually yields higher estimates than rule generation.
  - In the Horizontal setting, some models reach perfect accuracy yet produce programs with low C(P).
  - Accuracy (A) and C(P) are not significantly correlated.
- **Limitations:** the approach depends on LLMs' coding ability and on hand-crafted conversion heuristics. Estimating compositionality from rules written in natural language remains an open problem.
- **Resources:** code and constructed datasets are released at github.com/xzy-xzy/RGP.

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

## Institutions

- [Peking University](https://md.research.elamur.ai/free/en/universities/peking-university/) — University, Beijing, China · 315 works · 43,267 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,450 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,296 works

🧭 Topics (1): [🧠 Language models & pretraining](https://md.research.elamur.ai/free/en/topics/language-models/) · 3,894 works

## Cite

Cite as: Ziyao Xu, Cong Wang and Houfeng Wang. 2026. Investigating More Explainable and Partition-Free Compositionality Estimation for LLMs: A Rule-Generation Perspective. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{xu2026investigating,
  title = {{Investigating More Explainable and Partition-Free Compositionality Estimation for LLMs: A Rule-Generation Perspective}},
  author = {Ziyao Xu, Cong Wang and Houfeng Wang},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.409},
  url = {https://doi.org/10.18653/v1/2026.acl-long.409}
}
```

- [← previous Investigating Memorization in Language Models Trained via Knowledge Distillation](https://md.research.elamur.ai/free/en/papers/macking-2026-investigating-memorization-language-models-trained/)
- [next → Investigating Reasoning with Hypotheses: The RIP2 Corpus](https://md.research.elamur.ai/free/en/papers/schad-2026-investigating-reasoning-hypotheses-rip2-corpus/)
- [↑ back to papers of 2026](https://md.research.elamur.ai/free/en/papers/2026/page/37/)

## References

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

1. Anthropic. 2024. Claude 3.5 sonnet model card addendum. [find](https://scholar.google.com/scholar?q=Anthropic%2E+2024%2E+Claude+3%2E5+sonnet+model+card+addendum%2E)
2. Anthropic. 2025. Claude 3.7 sonnet system card. [find](https://scholar.google.com/scholar?q=Anthropic%2E+2025%2E+Claude+3%2E7+sonnet+system+card%2E)
3. Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron C. Courville. 2019. [Systematic generalization: What is required and can it be learned?](https://md.research.elamur.ai/free/en/papers/bahdanau-2018-systematic-generalization-required-learned/) In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenRev…
4. DeepSeek-AI, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang, Bochao Wu, Bei Feng, Chengda Lu, Chengg… — [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://md.research.elamur.ai/free/en/papers/deepseek-ai-2025-deepseek-r1-incentivizing-reasoning-capability/)
5. DeepSeek-AI, Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Daya Guo, Dejian Yang, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, H… [find](https://scholar.google.com/scholar?q=DeepSeek%2DAI%2C+Aixin+Liu%2C+Bei+Feng%2C+Bing+Xue%2C+Bingxuan+Wang%2C+Bochao+Wu%2C+Chengda+Lu%2C+Chenggang+Zhao%2C+Chengqi+Deng%2C+Chenyu+Zhang%2C+Chong+Ruan%2C+Damai+Dai%2C+Daya+Guo%2C+Dejian+Yang%2C+Deli+Chen%2C+Dongjie+Ji%2C+Erhan)
6. Stanislas Dehaene, Fosca Al Roumi, Yair Lakretz, Samuel Planton, and Mathias Sablé-Meyer. 2022. Symbols and mental programs: a hypothesis about human singularity. Trends in Cognitive Sciences, 26(9):751–766. [find](https://scholar.google.com/scholar?q=Stanislas+Dehaene%2C+Fosca+Al+Roumi%2C+Yair+Lakretz%2C+Samuel+Planton%2C+and+Mathias+Sabl%C3%A9%2DMeyer%2E+2022%2E+Symbols+and+mental+programs%3A+a+hypothesis+about+human+singularity%2E+Trends+in+Cognitive+Sciences%2C+26%289%29%3A7)
7. Eric Elmoznino, Thomas Jiralerspong, Yoshua Bengio, and Guillaume Lajoie. 2025. A complexity-based theory of compositionality. Preprint, arXiv:2410.14817. — [arXiv:2410.14817](https://arxiv.org/abs/2410.14817) [find](https://scholar.google.com/scholar?q=Eric+Elmoznino%2C+Thomas+Jiralerspong%2C+Yoshua+Bengio%2C+and+Guillaume+Lajoie%2E+2025%2E+A+complexity%2Dbased+theory+of+compositionality%2E+Preprint%2C+arXiv%3A2410%2E14817%2E+%E2%80%94+%5BarXiv%3A2410%2E14817%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F24)
8. Google. 2024. Introducing gemini 2.0: our new ai model for the agentic era. [find](https://scholar.google.com/scholar?q=Google%2E+2024%2E+Introducing+gemini+2%2E0%3A+our+new+ai+model+for+the+agentic+era%2E)
9. Google. 2025. Gemini 2.5: Our most intelligent ai model. [find](https://scholar.google.com/scholar?q=Google%2E+2025%2E+Gemini+2%2E5%3A+Our+most+intelligent+ai+model%2E)
10. Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. 2020. [Compositionality decomposed: How do neural networks generalise?](https://md.research.elamur.ai/free/en/papers/hupkes-2019-compositionality-decomposed-neural-networks-generalise/) J. Artif. Intell. Res., 67:757–795.
11. Dieuwke Hupkes, Mario Giulianelli, Verna Dankers, Mikel Artetxe, Yanai Elazar, Tiago Pimentel, Christos Christodoulopoulos, Karim Lasri, Naomi Saphra, Arabella Sinclair, Dennis Ulmer, Florian Schottmann, Khuyagbaatar Batsuren, Kaiser Sun, Koustuv Sinha, Leila Khalatbari, Maria Ryskina, Rita Frieske,… [find](https://scholar.google.com/scholar?q=Dieuwke+Hupkes%2C+Mario+Giulianelli%2C+Verna+Dankers%2C+Mikel+Artetxe%2C+Yanai+Elazar%2C+Tiago+Pimentel%2C+Christos+Christodoulopoulos%2C+Karim+Lasri%2C+Naomi+Saphra%2C+Arabella+Sinclair%2C+Dennis+Ulmer%2C+Florian+Schottma)
12. Theo M.V. Janssen and Barbara H. Partee. 1997. Chapter 7 - compositionality. In Johan van Benthem and Alice ter Meulen, editors, Handbook of Logic and Language, pages 417–473. North-Holland, Amsterdam. [find](https://scholar.google.com/scholar?q=Theo+M%2EV%2E+Janssen+and+Barbara+H%2E+Partee%2E+1997%2E+Chapter+7+%2D+compositionality%2E+In+Johan+van+Benthem+and+Alice+ter+Meulen%2C+editors%2C+Handbook+of+Logic+and+Language%2C+pages+417%E2%80%93473%2E+North%2DHolland%2C+Amsterdam)
13. Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, and Olivier Bousquet. 2020. Measuring compositional generalization: A comprehensive method on… [find](https://scholar.google.com/scholar?q=Daniel+Keysers%2C+Nathanael+Sch%C3%A4rli%2C+Nathan+Scales%2C+Hylke+Buisman%2C+Daniel+Furrer%2C+Sergii+Kashubin%2C+Nikola+Momchev%2C+Danila+Sinopalnikov%2C+Lukasz+Stafiniak%2C+Tibor+Tihon%2C+Dmitry+Tsarkov%2C+Xiao+Wang%2C+Marc+van)
14. 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 2020, Online, November 16-20, 2020, pages 9087–9105. Association for Computational Lingu… [find](https://scholar.google.com/scholar?q=Najoung+Kim+and+Tal+Linzen%2E+2020%2E+COGS%3A+A+compositional+generalization+challenge+based+on+semantic+interpretation%2E+In+Proceedings+of+the+2020+Conference+on+Empirical+Methods+in+Natural+Language+Proces)
15. Andrei N Kolmogorov. 1965. Three approaches to the quantitative definition ofinformation’. Problems of information transmission, 1(1):1–7. [find](https://scholar.google.com/scholar?q=Andrei+N+Kolmogorov%2E+1965%2E+Three+approaches+to+the+quantitative+definition+ofinformation%E2%80%99%2E+Problems+of+information+transmission%2C+1%281%29%3A1%E2%80%937%2E)
16. 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, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 o… [find](https://scholar.google.com/scholar?q=Brenden+M%2E+Lake+and+Marco+Baroni%2E+2018%2E+Generalization+without+systematicity%3A+On+the+compositional+skills+of+sequence%2Dto%2Dsequence+recurrent+networks%2E+In+Proceedings+of+the+35th+International+Conferenc)
17. Zhaoyi Li, Gangwei Jiang, Hong Xie, Linqi Song, Defu Lian, and Ying Wei. 2024. Understanding and patching compositional reasoning in llms. In Findings of the Association for Computational Linguistics, ACL 2024, Bangkok, Thailand and virtual meeting, August 11-16, 2024, pages 9668–9688. Association f… [find](https://scholar.google.com/scholar?q=Zhaoyi+Li%2C+Gangwei+Jiang%2C+Hong+Xie%2C+Linqi+Song%2C+Defu+Lian%2C+and+Ying+Wei%2E+2024%2E+Understanding+and+patching+compositional+reasoning+in+llms%2E+In+Findings+of+the+Association+for+Computational+Linguistics%2C)
18. Kate McCurdy, Paul Soulos, Paul Smolensky, Roland Fernandez, and Jianfeng Gao. 2024. Toward compositional behavior in neural models: A survey of current views. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, EMNLP 2024, Miami, FL, USA, November 12-16, 2024,… [find](https://scholar.google.com/scholar?q=Kate+McCurdy%2C+Paul+Soulos%2C+Paul+Smolensky%2C+Roland+Fernandez%2C+and+Jianfeng+Gao%2E+2024%2E+Toward+compositional+behavior+in+neural+models%3A+A+survey+of+current+views%2E+In+Proceedings+of+the+2024+Conference+on)
19. OpenAI, :, Aaron Hurst, Adam Lerer, Adam P. Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Ostrow, Akila Welihinda, Alan Hayes, Alec Radford, Aleksander M adry, Alex Baker-Whitcomb, Alex Beutel, Alex Borzunov, Alex Carney, Alex Chow, Alex Kirillov, Alex Nichol, Alex Paino, Alex Renzin, Alex… — [GPT-4o System Card](https://md.research.elamur.ai/free/en/papers/openai-2024-gpt-4o-system-card/)
20. OpenAI, :, Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, Alex Iftimie, Alex Karpenko, Alex Tachard Passos, Alexander Neitz, Alexander Prokofiev, Alexander Wei, Allison Tam, Ally Bennett, Ananya Kumar, Andre… — [OpenAI o1 System Card](https://md.research.elamur.ai/free/en/papers/openai-2024-openai-o1-system-card/)
21. OpenAI. 2025. Openai o3-mini system card. [find](https://scholar.google.com/scholar?q=OpenAI%2E+2025%2E+Openai+o3%2Dmini+system+card%2E)
22. Peter Pagin and Dag Westerståhl. 2010. Compositionality i: Definitions and variants. Philosophy Compass, 5(3):250–264. [find](https://scholar.google.com/scholar?q=Peter+Pagin+and+Dag+Westerst%C3%A5hl%2E+2010%2E+Compositionality+i%3A+Definitions+and+variants%2E+Philosophy+Compass%2C+5%283%29%3A250%E2%80%93264%2E)
23. Francis Jeffry Pelletier. 1994. The principle of semantic compositionality. Topoi, 13(1):11–24. [find](https://scholar.google.com/scholar?q=Francis+Jeffry+Pelletier%2E+1994%2E+The+principle+of+semantic+compositionality%2E+Topoi%2C+13%281%29%3A11%E2%80%9324%2E)
24. Qwen-Team. 2025. Qwq-32b: Embracing the power of reinforcement learning. [find](https://scholar.google.com/scholar?q=Qwen%2DTeam%2E+2025%2E+Qwq%2D32b%3A+Embracing+the+power+of+reinforcement+learning%2E)
25. Zoltán Gendler Szabó. 2004. Compositionality. In Edward N. Zalta and Uri Nodelman, editors, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. [find](https://scholar.google.com/scholar?q=Zolt%C3%A1n+Gendler+Szab%C3%B3%2E+2004%2E+Compositionality%2E+In+Edward+N%2E+Zalta+and+Uri+Nodelman%2C+editors%2C+The+Stanford+Encyclopedia+of+Philosophy%2E+Metaphysics+Research+Lab%2C+Stanford+University%2E)
26. Thaddäus Wiedemer, Prasanna Mayilvahanan, Matthias Bethge, and Wieland Brendel. 2023. Compositional generalization from first principles. In Advances in Neural Information Processing Systems, volume 36, pages 6941–6960. Curran Associates, Inc. [find](https://scholar.google.com/scholar?q=Thadd%C3%A4us+Wiedemer%2C+Prasanna+Mayilvahanan%2C+Matthias+Bethge%2C+and+Wieland+Brendel%2E+2023%2E+Compositional+generalization+from+first+principles%2E+In+Advances+in+Neural+Information+Processing+Systems%2C+volume+3)
27. Ziyao Xu and Houfeng Wang. 2024. SPOR: A comprehensive and practical evaluation method for compositional generalization in data-to-text generation. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2024, Bangkok, Thailand, August… [find](https://scholar.google.com/scholar?q=Ziyao+Xu+and+Houfeng+Wang%2E+2024%2E+SPOR%3A+A+comprehensive+and+practical+evaluation+method+for+compositional+generalization+in+data%2Dto%2Dtext+generation%2E+In+Proceedings+of+the+62nd+Annual+Meeting+of+the+Ass)
28. An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Le Yu, Mei Li, Mingfeng Xue, Pei… [find](https://scholar.google.com/scholar?q=An+Yang%2C+Baosong+Yang%2C+Beichen+Zhang%2C+Binyuan+Hui%2C+Bo+Zheng%2C+Bowen+Yu%2C+Chengyuan+Li%2C+Dayiheng+Liu%2C+Fei+Huang%2C+Haoran+Wei%2C+Huan+Lin%2C+Jian+Yang%2C+Jianhong+Tu%2C+Jianwei+Zhang%2C+Jianxin+Yang%2C+Jiaxi+Yang%2C+Jin)

*Updated 2 November 2026*