Elamur Research⌕
☰
home / papers / 2026 / Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks

Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks

Paper · 2026 · Shlok Shelat, Jay Raval, Souvik Roy et al.

Summary

The paper asks whether LLMs that perform well on formal-language problems actually reason symbolically or mostly reproduce constructions they saw during training. To test this, the authors built a benchmark on building deterministic finite automata (DFA) from regular languages, given as regular expressions or natural-language descriptions. It has three parts:

  • factual knowledge questions;
  • construction problems already published online (seen);
  • novel problems (unseen), either hand-crafted with several interacting constraints or generated systematically through Arden's theorem.

GPT-5.1, Gemini-2.5-Flash and Grok-4.1-fast-reasoning were tested with direct, Chain-of-Thought and Tree-of-Thought prompting, plus a three-step hint procedure for self-correction. Outputs were graded only on language equivalence, not on minimality.

All three models answer every knowledge question correctly and solve most seen tasks. On unseen problems their accuracy collapses. Neither the prompting strategy nor the hints repair deeper structural mistakes. The work matters because it separates recall from compositional reasoning in a setting where correctness can be checked mechanically.

Key points

  • Benchmark size: 50 knowledge items (25 multiple-choice, 25 short-answer), 90 seen problems and 180 unseen ones. The unseen set has 60 hand-made "mathematical art" items and 120 Arden's-theorem "mathematical engineering" items.
  • Seen-task accuracy (zero-shot, temperature 0, JSON output): Grok-4.1 reaches 89.5%, Gemini-2.5 85.0% and GPT-5.1 84.2%. Knowledge accuracy is 100% for every model.
  • Unseen-task accuracy: under direct prompting it falls to 20.67–59.12%, a loss of roughly 30–64 points. CoT and ToT, including four construction methods such as Thompson's algorithm, do not remove the errors.
  • Error analysis: over 500 wrong DFAs were analysed, yielding six recurring failure types. Examples are mishandled Kleene-star semantics, constraints lost under concatenation and spurious states.
  • Release and evaluation method: the data, prompts, code and outputs are publicly released, and the new datasets carry a CC BY 4.0 license. Correctness checks use exhaustive enumeration up to a bounded string length plus randomized testing, so they are not a formal proof of equivalence.

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

🎓University of Maryland, Baltimore CountyBaltimore · United States14 works · 915 citations

Also on the byline: Ahmedabad University.

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,320 worksReasoning · 1,426 works

Cite

Cite as Shlok Shelat, Jay Raval, Souvik Roy and Manas Gaur. 2026. Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.1495

@inproceedings{shelat2026beyond,
  title = {{Beyond Memorization: Testing LLM Reasoning on Unseen Theory of Computation Tasks}},
  author = {Shlok Shelat, Jay Raval, Souvik Roy and Manas Gaur},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.1495},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.1495}
}

References

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

  1. Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2006. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley Longman Publishing Co., Inc., USA. find
  2. Zhangir Azerbayev, Bartosz Piotrowski, Hailey Schoelkopf, Edward W. Ayers, Dragomir Radev, and Jeremy Avigad. 2023. Proofnet: Autoformalizing and formally proving undergraduate-level mathematics. Preprint, arXiv:2302.12433.
  3. Matei A. Golesteanu, Garrett B. Vowinkel, and Ryan E. Dougherty. 2024. Can ChatGPT pass a theory of computing course? In Proceedings of the ACM Virtual Global Computing Education Conference, pages 33–38. Association for Computing Machinery. find
  4. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2001. Introduction to Automata Theory, Languages, and Computation, 2 edition. Addison-Wesley. find
  5. Michael Katz, Harsha Kokel, and Sarath Sreedharan. 2025. Seemingly simple planning problems are computationally challenging: The countdown game. Preprint, arXiv:2508.02900. — [arXiv:2508.02900](https://arxiv.org/abs/2508.02900) find
  6. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. Preprint, arXiv:2205.11916.
  7. Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. 2022. Solving quantitative reasoning problems with language models. In Proceedings of…
  8. Michael Sipser. 2013. Introduction to the Theory of Computation, 3 edition. Course Technology. find
  9. Xuezhi Wang and Denny Zhou. 2024. Chain-of-thought reasoning without prompting. Preprint, arXiv:2402.10200. find
  10. Sean Welleck, Jiacheng Liu, Ronan Le Bras, Hannaneh Hajishirzi, Yejin Choi, and Kyunghyun Cho. 2021. Naturalproofs: Mathematical theorem proving in natural language. Preprint, arXiv:2104.01112. find
  11. Yuhuai Wu, Albert Q. Jiang, Wenda Li, Markus N. Rabe, Charles Staats, Mateja Jamnik, and Christian Szegedy. 2022. Autoformalization with large language models. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS).
  12. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. 2023. Tree of thoughts: Deliberate problem solving with large language models. In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS). find
  13. Xiang Yue, Yuansheng Ni, Kai Zhang, Tianyu Zheng, Ruoqi Liu, Ge Zhang, Samuel Stevens, Dongfu Jiang, Weiming Ren, Yuxuan Sun, Cong Wei, Botao Yu, Ruibin Yuan, Renliang Sun, Ming Yin, Boyuan Zheng, Zhenzhu Yang, Yibo Liu, Wenhao Huang, and 3 others. 2024. MMMU: A massive multi-discipline multimodal u…

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/shelat-2026-beyond-memorization-testing-llm-reasoning/