Elamur Research⌕
☰
home / papers / 2026 / Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling

Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling

Paper · 2026 · Ivan Rodkin, Daniil Orel, Konstantin Smirnov et al.

Summary

The paper asks whether multi-step reasoning in neural models reflects real generalization or memorization, and how difficulty grows with the number of required inference steps. The authors build a benchmark from one-dimensional cellular automata (1dCA). A model sees a short trajectory produced by an unknown local Boolean rule and must predict the configuration k steps later. Training and test rules never overlap, so lookup cannot succeed.

LLMs are tested on Handsup, a natural-language game equivalent to the task. Small models (GPT-NeoX, LSTM, Mamba, ARMT) are trained from scratch in Orbit-State and Orbit-Orbit variants. They are then combined with depth-extension techniques: ACT, GRPO and token-level CoT.

The small models infer unseen rules well for a single step. However, accuracy collapses once several hidden steps must be chained. Recurrence, adaptive halting and RL raise this ceiling only moderately, while supervision on intermediate steps goes furthest. The study suggests that effective computational depth, more than scale, limits reasoning. It also argues that reasoning benchmarks should report depth alongside accuracy.

Key points

  • Resources:
    • The dataset is released on Hugging Face as irodkin/1dCA_r2s20T20.
    • Code is available in the GitHub repo associative-recurrent-memory-transformer (ACT branch).
    • Inputs are 10 observed states of width 20, with look-ahead k ∈ {1, 2, 3, 4}.
  • LLM results on Handsup:
    • Only Gemini 2.5 Pro performs notably on the radius-1 version (7 players, 5 rounds of history).
    • In the harder r=2 setting (20 players, 10 rounds), no model exceeds 10%.
    • Accuracy also falls on Wolfram Class 3 and 4 rules.
  • Depth barrier: Fixed-depth 4-layer models solve k=1 but fail for k≥2. ARMT extends this to k=2.
  • Depth-extension methods:
    • ACT adds roughly one effective step without extra parameters, with diminishing gains beyond k≈3.
    • GRPO reaches k=3 without intermediate labels.
    • With stepwise targets (CoT), GPT-NeoX exceeds 90% accuracy for k≤4.
  • Generality and limitations: The same trends also hold on a separate benchmark built around multiplying group elements (Merrill et al., 2024). The authors note that the study covers only small-scale models and a selected set of LLMs.

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

🎓London Institute for Mathematical SciencesLondon · United Kingdom2 works · 8 citations

 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 worksComputer Vision and Pattern Recognition · 2,869 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,426 works

Cite

Cite as Ivan Rodkin, Daniil Orel, Konstantin Smirnov, Arman Bolatov, Bilal Elbouardi, Besher Hassan, Yuri Kuratov, Aydar Bulatov, Preslav Nakov, Timothy Baldwin, Artem Shelmanov and Mikhail Burtsev. 2026. Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling. 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.2103

@inproceedings{rodkin2026beyond,
  title = {{Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling}},
  author = {Ivan Rodkin, Daniil Orel, Konstantin Smirnov, Arman Bolatov, Bilal Elbouardi, Besher Hassan, Yuri Kuratov, Aydar Bulatov, Preslav Nakov, Timothy Baldwin, Artem Shelmanov and Mikhail Burtsev},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.2103},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.2103}
}

References

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

  1. Luis M. Antunes. 2021. Cellpylib: A python library for working with cellular automata. Journal of Open Source Software, 6(67):3608. find
  2. Satwik Bhattamishra, Arkil Patel, and Navin Goyal. 2020. On the computational power of transformers and its implications in sequence modeling. arXiv preprint arXiv:2006.09286. find
  3. Sid Black, Stella Biderman, Eric Hallahan, Quentin Anthony, Leo Gao, Laurence Golding, Horace He, Connor Leahy, Kyle McDonell, Jason Phang, Michael Pieler, USVSN Sai Prashanth, Shivanshu Purohit, Laria Reynolds, Jonathan Tow, Ben Wang, and Samuel Weinbach. 2022. Gpt-neox-20b: An open-source autoregr…
  4. Aydar Bulatov, Yury Kuratov, and Mikhail Burtsev. 2022. Recurrent memory transformer. In Advances in Neural Information Processing Systems, volume 35, pages 11079–11091. Curran Associates, Inc. find
  5. Alexis Chevalier, Alexander Wettig, Anirudh Ajith, and Danqi Chen. 2023. Adapting language models to compress contexts. arXiv preprint arXiv:2305.14788.
  6. George Cybenko. 1989. Approximations by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2:183–192. find
  7. Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G Carbonell, Quoc Le, and Ruslan Salakhutdinov. 2019. Transformer-xl: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978–2988. find
  8. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. 2019. Universal transformers. In International Conference on Learning Representations. find
  9. Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. 2023. Neural networks and the chomsky hierarchy. In 11th International Conference on Learning Representations.
  10. Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang (Lorraine) Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. 2023. Faith and fate: Limits of transformers on compositiona…
  11. Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. 2024. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems, 36. find
  12. João Pedro Gandarela, Danilo S Carvalho, and André Freitas. 2024. Inductive learning of logical theories with llms: A complexity-graded analysis. arXiv preprint arXiv:2408.16779. — [arXiv:2408.16779](https://arxiv.org/abs/2408.16779) find
  13. Fabian Gloeckle, Badr Youbi Idrissi, Baptiste Rozière, David Lopez-Paz, and Gabriel Synnaeve. 2024. Better & faster large language models via multi-token prediction. arXiv preprint arXiv:2404.19737. find
  14. Sachin Goyal, Ziwei Ji, Ankit Singh Rawat, Aditya Krishna Menon, Sanjiv Kumar, and Vaishnavh Nagarajan. 2024. Think before you speak: Training language models with pause tokens. In The Twelfth International Conference on Learning Representations. find
  15. Alex Graves. 2016. Adaptive computation time for recurrent neural networks. arXiv preprint arXiv:1603.08983. find
  16. Alex Graves, Greg Wayne, and Ivo Danihelka. 2014. Neural turing machines. arXiv preprint arXiv:1410.5401. find
  17. Albert Gu and Tri Dao. 2023. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752. find
  18. Albert Gu, Karan Goel, and Christopher Re. 2021. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations. find
  19. Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, and 175 others. 2025. Deepseek-r1 incentivizes reasoning in llms through rein… find
  20. Shibo Hao, Sainbayar Sukhbaatar, DiJia Su, Xian Li, Zhiting Hu, Jason Weston, and Yuandong Tian. 2024. Training large language models to reason in a continuous latent space. arXiv preprint arXiv:2412.06769. find
  21. Alex Havrilla, Yuqing Du, Sharath Chandra Raparthy, Christoforos Nalmpantis, Jane Dwivedi-Yu, Maksym Zhuravinskyi, Eric Hambro, Sainbayar Sukhbaatar, and Roberta Raileanu. 2024. Teaching large language models to reason with reinforcement learning. arXiv preprint arXiv:2403.04642. find
  22. David Herel and Tomas Mikolov. 2024. Thinking tokens for language modeling. arXiv preprint arXiv:2405.08644. — [arXiv:2405.08644](https://arxiv.org/abs/2405.08644) find
  23. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735– 1780. find
  24. Wesley H Holliday and Matthew Mandelkern. 2024. Conditional and modal reasoning in large language models. arXiv preprint arXiv:2401.17169. find
  25. Kurt Hornik, Maxwell Stinchcombe, and Halbert White. 1989. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359–366. find
  26. Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. 2010. A model of computation for mapreduce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 938–948. SIAM. find
  27. Aviral Kumar, Vincent Zhuang, Rishabh Agarwal, Yi Su, John D Co-Reyes, Avi Singh, Kate Baumli, Shariq Iqbal, Colton Bishop, Rebecca Roelofs, Lei M Zhang, Kay McKinney, Disha Shrivastava, Cosmin Paduraru, George Tucker, Doina Precup, Feryal Behbahani, and Aleksandra Faust. 2024. Training language mod…
  28. Thang Luong and Edward Lockhart. 2025. Advanced version of gemini with deep think officially achieves gold-medal standard at the international mathematical olympiad. Google DeepMind Blog. find
  29. Jacob Pfau, William Merrill, and Samuel R. Bowman. 2024. Let’s think dot by dot: Hidden computation in transformer language models. In First Conference on Language Modeling. find
  30. William Merrill, Jackson Petty, and Ashish Sabharwal. 2024. The illusion of state in state-space models. In Proceedings of the 41st International Conference on Machine Learning, pages 35492–35506. find
  31. Jack W. Rae, Anna Potapenko, Siddhant M. Jayakumar, and Timothy P. Lillicrap. 2019. Compressive transformers for long-range sequence modelling. Preprint, arXiv:1911.05507.
  32. William Merrill and Ashish Sabharwal. 2023. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531–545. find
  33. Ivan Rodkin, Yurii Kuratov, Aydar Bulatov, and Mikhail Burtsev. 2024. Associative recurrent memory transformer. Preprint, arXiv:2407.04841.
  34. William Merrill and Ashish Sabharwal. 2024. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations. find
  35. William Merrill, Ashish Sabharwal, and Noah A Smith. 2022. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843–856. find
  36. Philipp Mondorf and Barbara Plank. 2024. Liar, liar, logical mire: A benchmark for suppositional reasoning in large language models. arXiv preprint arXiv:2406.12546. find
  37. Franz Nowak, Anej Svete, Alexandra Butoi, and Ryan Cotterell. 2024. On the representational capacity of neural language models with chain-of-thought reasoning. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 12510–12548, Bangk… find
  38. OpenAI. 2024. Learning to reason with llms. https://openai.com/index/ learning-to-reason-with-llms/. Accessed: 2024-09-23. ↗
  39. OpenAI. 2025. We’ve scored highly enough to achieve gold at this year’s ioi online competition with a reasoning system — placing \#6 when ranked with humans and \#1 when ranked with other ais. in just a few weeks: 2nd at atcoder; gold medal-level at imo; gold medal-level at ioi. https://x.com/OpenAI/… ↗
  40. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F Christiano, Jan Leike, and Ryan Lowe. 2022. Tra… — Training language models to follow instructions with human feedback
  41. Jorge Pérez, Pablo Barceló, and Javier Marinkovic. 2021. Attention is turing-complete. Journal of Machine Learning Research, 22(75):1–35. find
  42. Clayton Sanford, Daniel Hsu, and Matus Telgarsky. 2024a. Transformers, parallel computation, and logarithmic depth. In Forty-first International Conference on Machine Learning. find
  43. Clayton Sanford, Daniel J Hsu, and Matus Telgarsky. 2024b. Representational strengths and limitations of transformers. Advances in Neural Information Processing Systems, 36. find
  44. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. find
  45. Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. 2024. Deepseekmath: Pushing the limits of mathematical reasoning in open language models.
  46. Parshin Shojaee, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, and Mehrdad Farajtabar. 2025. The illusion of thinking: Understanding the strengths and limitations of reasoning models via the lens of problem complexity. Preprint, arXiv:2506.06941. find
  47. Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. 2023. Transformers as recognizers of formal languages: A survey on expressivity. arXiv preprint arXiv:2311.00208. find
  48. Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. 2024. What formal languages can transformers express? a survey. Transactions of the Association for Computational Linguistics, 12:543– 561. find
  49. Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. 2022. Solving math word problems with process-and outcome-based feedback. arXiv preprint arXiv:2211.14275.
  50. Karthik Valmeekam, Kaya Stechly, and Subbarao Kambhampati. 2024. Llms still can’t plan; can lrms? a preliminary evaluation of openai’s o1 on planbench. arXiv preprint arXiv:2409.13373. — [arXiv:2409.13373](https://arxiv.org/abs/2409.13373) find
  51. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. In Advances in neural information processing systems, pages 5998–6008.
  52. Yuxuan Wan, Wenxuan Wang, Yiliu Yang, Youliang Yuan, Jen-tse Huang, Pinjia He, Wenxiang Jiao, and Michael Lyu. 2024. LogicAsker: Evaluating and improving the logical reasoning ability of large language models. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing,… find
  53. Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. 2024. Math-shepherd: Verify and reinforce LLMs step-by-step without human annotations. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Paper…
  54. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. 2022. Chain-of-thought prompting elicits reasoning in large language models. 35:24824– 24837.
  55. Jason Weston, Sumit Chopra, and Antoine Bordes. 2015. Memory networks. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. find
  56. Liu Yang, Kangwook Lee, Robert Nowak, and Dimitris Papailiopoulos. 2024. Looped transformers are better at learning learning algorithms. Preprint, arXiv:2311.12424. find
  57. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2024. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36. find
  58. Qifan Yu, Zhenyu He, Sijie Li, Xun Zhou, Jun Zhang, Jingjing Xu, and Di He. 2025. Enhancing autoregressive chain-of-thought through loop-aligned reasoning. Preprint, arXiv:2502.08482. — [arXiv:2502.08482](https://arxiv.org/abs/2502.08482) find
  59. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. 2019. Are transformers universal approximators of sequence-to-sequence functions? arXiv preprint arXiv:1912.10077. find
  60. Xiang Zhang, Muhammad Abdul-Mageed, and Laks VS Lakshmanan. 2024. Autoregressive+ chain of thought= recurrent: Recurrence’s role in language models’ computability and a revisit of recurrent transformer. arXiv preprint arXiv:2409.09239. — [arXiv:2409.09239](https://arxiv.org/abs/2409.09239) find
  61. Rui-Jie Zhu, Zixuan Wang, Kai Hua, Tianyu Zhang, Ziniu Li, Haoran Que, Boyi Wei, Zixin Wen, Fan Yin, He Xing, Lu Li, Jiajun Shi, Kaijing Ma, Shanda Li, Taylor Kergan, Andrew Smith, Xingwei Qu, Mude Hui, Bohong Wu, and 14 others. 2025. Scaling latent reasoning via looped language models. Preprint, ar…

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/rodkin-2026-beyond-memorization-extending-reasoning-depth/