mlsanityData to 14 Oct 2026

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

arXiv 2508.16745 ↗First posted 22 Aug 2025cs.LG cs.AIcited by 4

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

Reasoning is a core capability of large language models, yet how multi-step reasoning is learned and executed remains unclear. We study this question in a controlled cellular-automata (1dCA) framework that excludes memorisation by using disjoint training and test rules. Given a short state sequence, the model is required to infer the hidden local rule and then chain it to predict multiple future steps. Our evaluation shows that LLMs largely fail to reliably solve a natural-language proxy of the proposed task. We find that most neural architectures trained from scratch can learn rule inference and achieve high next-step accuracy, but performance drops sharply as the required number of intermediate reasoning steps increases. Experiments show that increasing model depth is crucial, and extending effective depth via recurrence, memory, or test-time compute improves results but remains bounded. The code is available on github: https://github.com/RodkinIvan/associative-recurrent-memory-transformer/tree/ACT

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 59 of its 89 references that are in the map. First posted on arXiv 22 Aug 2025.

Builds on

59 of 89 references.

Closest ancestors · 4

Same direction, newest first

  1. 2025The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity7 Jun
  2. 2024Training Language Models to Self-Correct via Reinforcement Learning19 Sep
  3. 2023Think before you speak: Training Language Models With Pause Tokens3 Oct
  4. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Models17 May

Other references · 55

  1. 2017Attention Is All You Needcited by 60,361
  2. 2022Training language models to follow instructions with human feedbackcited by 15,971
  3. 2017Proximal Policy Optimization Algorithmscited by 15,215
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  5. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  6. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,718
  7. 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,465
  8. 2019Transformer-XL: Attentive Language Models Beyond a Fixed-Length Contextcited by 1,850
  9. 2023Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotationscited by 928
  10. 2022Solving math word problems with process- and outcome-based feedbackcited by 901
  11. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Modelscited by 886
  12. 2024Training Large Language Models to Reason in a Continuous Latent Spacecited by 797
38 more
  1. 2019Compressive Transformers for Long-Range Sequence Modellingcited by 726
  2. 2022GPT-NeoX-20B: An Open-Source Autoregressive Language Modelcited by 713
  3. 2018Universal Transformerscited by 647
  4. 2014Neural Turing Machinescited by 644
  5. 2016Adaptive Computation Time for Recurrent Neural Networkscited by 506
  6. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 503
  7. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  8. 2014Memory Networkscited by 363
  9. 2024Better & Faster Large Language Models via Multi-token Predictioncited by 360
  10. 2023Adapting Language Models to Compress Contextscited by 356
  11. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  12. 2022Neural Networks and the Chomsky Hierarchycited by 217
  13. 2022Recurrent Memory Transformercited by 203
  14. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  15. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Modelscited by 191
  16. 2024The Illusion of State in State-Space Modelscited by 187
  17. 2024Teaching Large Language Models to Reason with Reinforcement Learningcited by 160
  18. 2023Looped Transformers are Better at Learning Learning Algorithmscited by 149
  19. 2025RWKV-7 "Goose" with Expressive Dynamic State Evolutioncited by 141
  20. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  21. 2023Representational Strengths and Limitations of Transformerscited by 133
  22. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  23. 2024LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBenchcited by 94
  24. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  25. 2024Transformers, parallel computation, and logarithmic depthcited by 79
  26. 2018Cellular automata as convolutional neural networkscited by 45
  27. 2021Learning Graph Cellular Automatacited by 33
  28. 2022Attention-based Neural Cellular Automatacited by 26
  29. 2024On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoningcited by 26
  30. 2024Thinking Tokens for Language Modelingcited by 24
  31. 2025Enhancing Auto-regressive Chain-of-Thought through Loop-Aligned Reasoningcited by 19
  32. 2024Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformercited by 16
  33. 2020It's Hard for Neural Networks To Learn the Game of Lifecited by 13
  34. 2023E(n)-equivariant Graph Neural Cellular Automatacited by 9
  35. 2024Conditional and Modal Reasoning in Large Language Modelscited by 9
  36. 2024Liar, Liar, Logical Mire: A Benchmark for Suppositional Reasoning in Large Language Modelscited by 9
  37. 2023Learning spatio-temporal patterns with Neural Cellular Automatacited by 8
  38. 2024LifeGPT: Topology-Agnostic Generative Pretrained Transformer Model for Cellular Automatacited by 8

50 most cited of 55 All 55 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2026Are Latent Reasoning Models Easily Interpretable?cited by 9
  2. 2026The Topological Trouble With Transformerscited by 3
  3. 2025Catch Your Breath: Adaptive Computation for Self-Paced Sequence Productioncited by 2
  4. 2026Attention Routing Stabilizes Early: Working-Set Inference for Recurrent Language Modelscited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2025Scaling up Test-Time Compute with Latent Reasoning: A Recurrent Depth Approach
  2. 2026Unlocking the Working Memory of Large Language Models for Latent Reasoning
  3. 2025ReProbe: Efficient Test-Time Scaling of Multi-Step Reasoning by Probing Internal States of Large Language Models
  4. 2026Not Too Hard, Not Too Easy: Learning from Intermediate States for LLM Structured Reasoning
  5. 2026MILES: Modular Instruction Memory with Learnable Selection for Self-Improving LLM Reasoning
  6. 2026Thinking Deeper, Not Longer: Memory-Efficient Test-Time Reasoning with Depth-Recurrent Transformers for Compositional Generalization
  7. 2026CosmicFish-HRM: Adaptive Reasoning via Hierarchical Recurrent Mechanisms in Compact Language Models
  8. 2025Rethinking Reasoning in LLMs: Neuro-Symbolic Local RetoMaton Beyond ICL and CoT