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

Ivan Rodkin, Daniil Orel, Konstantin Smirnov, Arman Bolatov, Bilal Elbouardi, Besher Hassan, Yuri Kuratov, Aydar Bulatov, Preslav Nakov, Timothy Baldwin, Artem Shelmanov, Mikhail Burtsev · 2025

Read Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling by Ivan Rodkin, Daniil Orel, Konstantin Smirnov, Arman Bolatov, Bilal Elbouardi, Besher Hassan, Yuri Kuratov, Aydar Bulatov, Preslav Nakov, Timothy Baldwin, Artem Shelmanov, Mikhail Burtsev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-16745.txt.

Introduction

Ivan Rodkin and co-authors probe how deep the reasoning of neural models can go in a 2025 paper. They use a simple cellular world where cells update by a hidden local rule. Because test rules never appear in training, the task cannot be solved by memory. A model must infer the rule from a few states and then chain it forward many steps.

Large language models largely failed a word-based version of the task. Models trained from scratch learned the rule inference well for one step ahead. Accuracy fell sharply as more chained steps were required. More depth helped, and adding recurrence, memory, or extra test-time computing helped further, but gains stayed bounded. The study maps a real limit on multi-step reasoning.

Catalog record

CREATORIvan Rodkin, Daniil Orel, Konstantin Smirnov, Arman Bolatov, Bilal Elbouardi, Besher Hassan, Yuri Kuratov, Aydar Bulatov, Preslav Nakov, Timothy Baldwin, Artem Shelmanov, Mikhail Burtsev
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-16745

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling Ivan Rodkin, Daniil Orel, Konstantin Smirnov, Arman Bolatov, Bilal Elbouardi, Besher Hassan, Yuri Kuratov, Aydar Bulatov, Preslav Nakov, Timothy Baldwin, Artem Shelmanov, Mikhail Burtsev Abstract Reasoning is a core capability of large language models, yet understanding how they learn and perform multi-step reasoning remains an open problem. In this study, we explore how different architectures and training methods affect model multi-step reasoning capabilities within a cellular automata framework. By training on state sequences generated with random Boolean functions for random initial conditions to exclude memorization, we demonstrate that most neural architectures learn to abstract the underlying rules. While models achieve high accuracy in next-state prediction, their performance declines sharply if multi-step reasoning is required. We confirm that increasing model depth plays a crucial role for sequential computations. We demonstrate that an extension of the effective model depth with recurrence, memory, and test-time compute scaling substantially enhances reasoning capabilities. The code is available on github . 1 Introduction Large Language Models (LLMs) demonstrate impressive capabilities in problem-solving and reasoning tasks, e.g., OpenAI’s o1 [ 47 ] and DeepSeek R1 [ 28 ] models achieved a top-500 ranking in a qualifier for the USA Math Olympiad (AIME). Also OpenAI system achieved an outstanding result, ranked 6 in International Olympiad in Informatics (IOI 2025) 1 1 1 https://x.com/OpenAI/status/1954969035713687975 . Both Google DeepMind and OpenAI systems achieve gold-medal scores in International Olympiad in Mathematics (IMO 2025) 2 2 2 https://deepmind.google/discover/blog/advanced-version-of-gemini-with-deep-think-officially-achieves-gold-medal-standard-at-the-international-mathematical-olympiad/ . On the other hand, extensive evidence from ongoing research shows that LLMs still face challenges in multi-step reasoning [ 15 , 67 , 34 , 19 , 44 , 59 ] and planning [ 65 ] , particularly when required to infer and apply underlying rules from data. These observations raise the following questions: 1. Is the reasoning exhibited by LLMs the result of genuine generalization, or merely memorization? 2. How does task difficulty scale as the required number of reasoning steps increases? 3. To what extent do a model’s architectural inductive biases, training objectives, and inference procedures limit its reasoning capabilities? Transformers [ 66 ] are universal function approximators and, with unbounded depth and precision, are Turing-complete [ 11 , 35 , 13 , 75 , 5 , 50 , 56 ] . Yet, finite-depth, fixed-width models used in practice cannot process arbitrarily long inputs in a single forward pass, and they provably fail on tasks such as graph connectivity, Boolean formula evaluation, and exact arithmetic beyond a bounded length [ 42 , 40 , 61 , 17 ] . One way to sidestep this depth barrier is to let the model write its own scratch-pad of intermediate tokens. Chain-of-Thought (CoT) prompting, process supervision, and reinforcement learning (RL) encourage models to emit multi-step rationales before producing the final answer [ 69 , 64 , 68 , 73 , 38 ] . Generating and consuming these extra tokens effectively increases the computational depth in proportion to the rationale length, enabling transformers to solve dynamic-programming benchmarks [ 17 ] and to recognize regular languages with linear decoding depth [ 39 ] . Yet, the main drawback is the need for supervision over intermediate steps, which is expensive or might be unavailable. A complementary avenue is to recycle hidden states . Segment-level recurrence in memory-augmented transformers [ 70 , 25 ] enables the re-feeding of hidden states across segments [ 12 , 52 , 8 , 10 , 54 ] , whereas state-space models achieve long-range interactions by leveraging linear dynamical systems [ 27 , 26 ] . Recurrence deepens the network without emitting extra tokens, but the maximum number of recurrent steps is still limited by the input length. Adaptive Computation Time (ACT) [ 24 ] removes this upper bound entirely: the model learns to allocate a variable number of layer updates to each token, halting once further computation is predicted to be unhelpful. In principle, ACT grants transformers unbounded effective depth while preserving parameter efficiency, which is an appealing property for reasoning tasks that require widely varying amounts of computation. In this paper, we investigate rule abstraction capabilities and approaches for increasing the reasoning depth of neural models. We cast multi-step reasoning as a variable-horizon prediction problem on one-dimensional Cellular Automata (1dCA). In our experiments, Boolean local update rules are never reused between training and testing, thus, success requires genuine rule generalization rather than memorization. We use this controlled benchmark to quantify how diverse neural architectures and depth extension strategies cope as the reasoning horizon k increases. Our main contributions are as follows: • 1dCA-Reasoning benchmark. We release a variable-length dataset and four task variants (O-S, O-O, O-RS, RO-S) that disentangle rule inference from state propagation; train/test rule sets are disjoint to preclude memorisation. • Comprehensive architectural study. We evaluate Transformers, LSTMs, state-space models (Mamba), and the Associative Recurrent Memory Transformer (ARMT) under identical conditions. Fixed-depth (4-layer) autoregressive models show a sharp cut-off in reasoning depth—solving k{=}1 but collapsing for k{\geq}2 —while segment-recurrent attention (ARMT) extends generalisation to k{=}2 . We corroborate these findings on a group multiplication benchmark [ 43 ] . • Depth-extension analysis. With four-layer backbones: (i) Adaptive Computation Time (ACT) yields roughly one additional effective step with modest compute overhead; (ii) reinforcement learning with GRPO attains k{=}3 without intermediate supervision; and (iii) token-level Chain-of-Thought training achieves near-perfect accuracy up to k{=}4 . • Ablations and efficiency. We quantify how layer count, model width, and ACT variants trade off computation and accuracy, and we report effective depth alongside accuracy, providing practical design guidelines. 2 Methods 2.1 Modeling Reasoning with One-dimensional Cellular Automata Motivation. Reason is the capacity of consciously applying logic by drawing valid conclusions from new or existing information. 3 3 3 https://en.wikipedia.org/wiki/Reason Reasoning about an unfamiliar process can be decomposed into two subtasks: (i) inferring the hidden law that governs state transitions and (ii) chaining that law to project multiple steps into the future. One-dimensional Cellular Automata embody this structure in its purest form. A single, local Boolean rule — the “micro-physics” of a toy universe — maps each binary state to the next. Given an orbit, a model must first discover this rule from observations and then apply it repeatedly to predict future states, mirroring the two-phase logic of multi-step reasoning. Indeed, reasoning might be simulated by memorization a mapping from each seen input to its correct output, with no grasp of why that mapping holds. In our 1dCA benchmark the update rule is withheld and the train-time and test-time rule sets are disjoint, so rote lookup to train data cannot succeed. To solve a task the model must induce the rule and then reason with it. 1dCA therefore offers a minimal, fully observable sandbox where two essential ingredients — law extraction and multi-step inference — separate genuine reasoning from mere memorization. Background. An One-dimensional Cellular Automaton (1dCA) is a one-dimensional, dynamical system in which space and time are discrete. Let r\in\mathbb{N}:r\geq 1 be the neighborhood radius in the space represented by a regular lattice of W\in\mathbb{N}:W\geq 2r+1 identical, locally-interconnected cells with binary state spaces, \mathbb{S}=\{0,1\} . The 1dCA’s global state , x\in\mathbb{S}^{W} , is a lattice configuration specified by the values of all states

Read the complete text