2604.07822v1

# Loop, Think, & Generalize: Implicit Reasoning in Recurrent-Depth Transformers ## Abstract We study implicit reasoning, i.e. the ability to combine knowledge or rules within a single forward pass. While transformer-based large language models store substantial factual knowledge and rules, they often fail to compose this knowledge for implicit multi-hop reasoning, suggesting a lack of compositional generalization over their parametric knowledge. To address this limitation, we study recurrent-depth transformers, which enables iterative computation over the same transformer layers. We investigate two compositional generalization challenges under the implicit reasoning scenario: systematic generalization, i.e. combining knowledge that is never used for compositions during training, and depth extrapolation, i.e. generalizing from limited reasoning depth (e.g. training on up to 5-hop) to deeper compositions (e.g. 10-hop). Through controlled studies with models trained from scratch, we show that while vanilla transformers struggle with both generalization challenges, recurrent-depth transformers can effectively make such generalization. For systematic generalization, we find that this ability emerges through a three-stage grokking process, transitioning from memorization to in-distribution generalization and finally to systematic generalization, supported by mechanistic analysis. For depth extrapolation, we show that generalization beyond training depth can be unlocked by scaling inference-time recurrence, with more iterations enabling deeper reasoning. We further study how training strategies affect extrapolation, providing guidance on training recurrent-depth transformers, and identify a key limitation, overthinking, where excessive recurrence degrades predictions and limits generalization to very deep compositions. ## 1 Introduction Large language models (LLMs) (Brown et al., 2020) are known to acquire substantial factual knowledge during pretraining, storing it in their parameters (Geva et al., 2023). However, how effectively this knowledge can be composed for reasoning remains less understood (Dziri et al., 2023; Press et al., 2023). In particular, recent work shows that transformer-based LLMs struggle under implicit reasoning, i.e. reasoning within a single forward pass without explicit chain-of-thought (CoT) (Wei et al., 2022). Such failures reveal a fundamental limitation of transformers: despite storing rich knowledge, they are often unable to flexibly combine it to solve novel questions. This limitation has important implications for generalization, as many tasks require composing multiple pieces of seen knowledge in novel ways not observed during training (Lake and Baroni, 2018; Berglund et al., 2023). Why do transformers struggle to combine their parametric knowledge in implicit reasoning? Consider a query such as “The spouse of the performer of Imagine is”. Previous work shows that transformers solve this by chaining two facts: first retrieving that the performer of Imagine is John Lennon in shallow layers, and then that the spouse of John Lennon is Yoko Ono in deeper layers (Biran et al., 2024; Wang et al., 2024a; Yang et al., 2024b). However, since knowledge is distributed across different layers of the transformer, there is no guarantee that the fact required for a particular query can be accessed correctly. For example, if the fact the spouse of John Lennon is Yoko Ono is only stored in shallow layers, deeper layers cannot access it because parameters are not shared across layers. While transformers can be trained to learn to combine such knowledge properly (Wang et al., 2024a; Yao et al., 2025), they fail to compositionally generalize to unfamiliar combinations or deeper recursive combinations. To address this limitation, we introduce depth-recurrence into transformers, allowing the same set of layers to be applied iteratively. The input sequence is processed multiple times by a shared transformer block, where the output of each iteration serves as input to the next. In contrast to vanilla transformers, where knowledge is tied to specific layers, recurrence enables more flexible access to and composition of parametric knowledge within a single forward process. Such models, known as recurrent-depth transformers or looped transformers, have recently gained attention as a promising architecture (Dehghani et al., 2019; Geiping et al., 2025; Zhu et al., 2025). While prior work has shown that recurrent-depth transformers improve length generalization (Bansal et al., 2022; Fan et al., 2025), it remains unclear whether they can overcome compositional generalization limitations when reasoning over parametric knowledge. In this paper, we systematically study whether recurrent-depth transformers can compositionally combine their parametric knowledge implicitly. By constructing synthetic datasets, we train models to learn implicit reasoning from scratch. Unlike LLMs trained on vast, opaque web-scale corpora, this setup provides control over the data and mitigates confounding biases introduced during pretraining. Specifically, we characterize two challenges: systematic generalization (combining knowledge not used in any composition during training) and depth extrapolation (e.g., training on 5-hop reasoning and evaluating on 10-hop). Our main findings are two-fold. First, recurrent-depth transformers exhibit strong systematic generalization, while vanilla transformers fail to do so. We show that this ability emerges through a sharp three-stage grokking process, that transitions from memorization to in-distribution generalization, and finally to systematic generalization. We also support this with evidence from the internal activations of models across different training stages. Second, recurrent-depth transformers enable depth extrapolation, generalizing to reasoning depths beyond those observed during training, as inference-time compute (i.e., recurrent iterations) increases. We further find that the training-time recurrence strategy plays a critical role in extrapolation performance, with dynamic recurrence achieving the strongest generalization. Despite these gains, we identify a key limitation: recurrent-depth transformers suffer from overthinking (Bansal et al., 2022), which degrades performance and limits generalization to extremely deep recursions. <details> <summary>2604.07822v1/x1.png Details</summary>  ### Visual Description ## Neural Network Architecture Diagram ### Overview The image depicts a neural network architecture diagram, specifically for a language model (LM). The diagram illustrates the flow of data through various components of the network, including the embedding layer, recurrent blocks, layer normalization, and the language model head. ### Components/Axes - **Embedder**: Converts input tokens into dense vectors. - **h0**: Initial hidden state. - **h1, h2, ..., hR-1**: Intermediate hidden states. - **hR**: Final hidden state. - **Layer Norm**: Normalizes the output of the recurrent blocks. - **LM Head**: Outputs the final predictions or probabilities. ### Detailed Analysis The diagram shows a sequence of recurrent blocks, each processing the input tokens through a series of transformations. The recurrent blocks are responsible for maintaining a state across the input sequence, which is crucial for tasks like language modeling where understanding the context of the input is important. The layer normalization is applied after each recurrent block to stabilize the learning process and improve the convergence of the network. ### Key Observations - The network architecture is designed to handle sequential data, as indicated by the recurrent blocks. - The use of multiple hidden states (h1, h2, ..., hR-1) suggests that the network can capture complex patterns and dependencies in the input sequence. - The final hidden state (hR) is used by the language model head to generate the output. ### Interpretation The diagram represents a state-of-the-art architecture for language models, which is capable of processing and generating text based on the input sequence. The recurrent blocks allow the network to maintain a context-aware representation of the input, which is essential for tasks like language translation, text summarization, and question answering. The layer normalization helps in stabilizing the training process, making the network more robust and efficient. The language model head generates the final output, which could be a sequence of tokens, a probability distribution over tokens, or a continuous output like a sentence or a paragraph. </details> Figure 1: Recurrent depth model architecture. The transformer block is repeated $R$ times. The embedding layer and language model head (LM Head) have tied weights. In our experiments, we use a simple looped transformer similar to Saunshi et al. (2025) without design elements such as input injection, gated halting, and middle looping. ## 2 Related Work Several small-scale studies pretrain looped or recurrent-depth transformers on synthetic tasks to better understand their behavior in a controlled setting. Our work best aligns with such studies where we are able to cleanly attribute differences in performance and generalization to specific architectural choices and model design decisions. Yang et al. (2024a) demonstrate how ”looping” a transformer block helps to better emulate learning algorithms such as gradient descent for in-context linear regressions, 2-layer neural networks, and decision trees. Fan et al. (2025) show that such looped transformers offer superior length generalization on algorithmic tasks such as parity and binary addition. Saunshi et al. (2025) conduct a larger-scale pretraining with the 250B tokens of the Pile dataset (Gao et al., 2020) and find that looped versions of transformer models of the same effective depth have a greater inductive bias towards reasoning at the cost of memorization and perplexity. Based on these results, they propose a regularization term that encourages certain layers to be closer to each other, thus improving the tradeoff between reasoning and fact recall. Relative to other works, our targeted setting yields unique insights on training dynamics and model behavior. We demonstrate how weight sharing through recurrence can solve systematic composition where vanilla transformers are known to struggle and extrapolation in multi-hop composition is possible with increased recurrence at inference-time. While Fan et al. (2025) propose looped architectures for length generalization, they assume an oracle number of training iterations based on sample complexity. We believe that our setup is closer to real-world scenarios where task complexity cannot be easily estimated through heuristics (such as input length). Without the assumption of task complexity a priori, we face distinct challenges in training our models. We analyze how best to apply methods like recurrent-depth and common pitfalls to avoid, which can help inform more robust implicit reasoning models in the future. We discuss other related work in Appendix D. ## 3 Task Formulation We formally define our implicit reasoning setup using a synthetic multi-hop reasoning task, and categorize three generalization challenges under this formulation: in-distribution generalization, systematic generalization, and depth extrapolation (Figure 2). The latter two can be viewed as out-of-distribution (OOD) generalization. Such tasks have been shown to be difficult for vanilla transformers to learn (Yao et al., 2025), highlighting their limitations in composing parametric knowledge for reasoning (Allen-Zhu and Li, 2023; Yang et al., 2024b). ### 3.1 Task Definition <details> <summary>2604.07822v1/x2.png Details</summary>  ### Visual Description ## Diagram Type: Flowchart ### Overview The image is a flowchart that illustrates the process of training and generalizing a model using atomic facts and inferred facts. The flowchart is divided into three main sections: Training, Systematic Generalization, and Depth Extrapolation. ### Components/Axes - **Training**: This section is divided into three subsections: Atomic facts (1-hop facts), Held-out atomic facts (1-hop facts), and Inferred facts (k-hop facts). - **Systematic Generalization**: This section is composed of held-out atomic facts and shows the process of generalizing from these facts. - **Depth Extrapolation**: This section shows the extrapolation of the model beyond the training hop depth. ### Detailed Analysis - **Training**: - **Atomic facts (1-hop facts)**: These are the initial facts that the model is trained on. The flowchart shows the relationships between these facts (e.g., e1 → e2, e2 → e3). - **Held-out atomic facts (1-hop facts)**: These are the facts that are held out from the training set to test the model's generalization ability. The flowchart shows the relationships between these facts (e.g., e1 → e5, e5 → e6). - **Inferred facts (k-hop facts)**: These are the facts that are inferred from the atomic facts and held-out atomic facts. The flowchart shows the relationships between these facts (e.g., e1 → e2 → e3, e2 → e3 → e4). - **Systematic Generalization**: This section shows the process of generalizing from the held-out atomic facts. The flowchart shows the relationships between the held-out facts and the inferred facts. - **Depth Extrapolation**: This section shows the extrapolation of the model beyond the training hop depth. The flowchart shows the relationships between the inferred facts and the extrapolated facts. ### Key Observations - The flowchart shows that the model is trained on atomic facts and inferred facts, and then generalizes from these facts. - The held-out atomic facts are used to test the model's generalization ability. - The extrapolation of the model beyond the training hop depth is shown in the Depth Extrapolation section. ### Interpretation The flowchart illustrates the process of training and generalizing a model using atomic facts and inferred facts. The model is trained on atomic facts and inferred facts, and then generalizes from these facts. The held-out atomic facts are used to test the model's generalization ability, and the extrapolation of the model beyond the training hop depth is shown. The flowchart demonstrates the importance of training on a diverse set of facts to ensure that the model can generalize well to new data. </details> Figure 2: Illustration of systematic and extrapolation generalization tasks with a sample dataset. Our implicit reasoning task relies on a directed knowledge graph (KG) where nodes represent a set of entities $E=\{e_i\}$ and edges represent a set of relations $R=\{r_j\}$ . The KG is composed of atomic (1-hop) facts, each taking the form of a triplet $(h,r,t)$ , where $h,t∈ E$ and $r∈ R$ (here $h$ and $t$ imply the head and tail entities, respectively). A $k$ -hop inferred fact is defined as a chain of $k$ atomic facts connecting a head entity $h$ to a final tail entity $t$ via a sequence of $k-1$ intermediate entities ( $i_1,\dots,i_k-1$ ): $$ (h,r_1,i_1),(i_1,r_2,i_2),\dots,(i_k-1,r_k,t) $$ Given the head entity $h$ and the sequence of relations $r_1,\dots,r_k$ , we use an auto-regressive decoder-only model to predict the final tail entity $t$ . The input prefix is $<e_h><r_1><r_2>\dots<r_k>$ , and the target is $<e_t>$ . Ideally, the model must implicitly perform the $k$ -hop traversal, successively retrieving each intermediate entity ( $i_1,\dots,i_k-1$ ) until it can resolve the final tail entity $t$ . ### 3.2 Generalization Challenges Given a generated knowledge graph, we first define the complete atomic fact set as $C=\{(h,r,t)\}$ , and the induced set of $k$ -hop inferred facts from $C$ as $$ I_k(C)=\{(h,r_1,\dots,r_k,t) \mid ∃ i_1,\dots,i_k-1, (h,r_1,i_1),\dots,(i_k-1,r_k,t)∈C\}. $$ #### Training set. The training set includes two parts: all possible atomic facts $C$ together with a set of inferred facts $I_train$ up to a maximum depth $k_train$ (e.g. $k$ -hop facts with $k∈[2,k_train]$ ). To characterize different generalization challenges, we partition the atomic fact set into two disjoint subsets $C=C_ID∪C_OOD$ . The training inferred facts $I_train$ can then be defined as $$ I_train=\{(h,r_1,\dots,r_k,t) \mid (h,r_1,\dots,r_k,t)∈I_k(C_ID), k≤ k_train\}. $$ We then define three generalization challenges: #### In-distribution generalization. The model is evaluated on inferred facts $(h,r_1,\dots,r_k,t)∈I_k(C_ID)$ that are not observed during training, equivalent to randomly sample inferred facts from $I_k(C_ID)$ as held-out test set. Despite its simplicity, previous work shows that vanilla transformers can only learn such tasks through extended training (Wang et al., 2024a). #### Systematic generalization. The model is evaluated on inferred facts $(h,r_1,\dots,r_k,t)∈I_k(C_OOD)$ , which are induced from atomic facts that are never used in compositions in the training data. This requires the learner to systematically combine its learned knowledge, without having seen combinations of it in training. This setting simulates scenarios where knowledge appears only as plain text in pretraining data (e.g. long-tail knowledge), but never forms answers to reasoning queries during training. Previous work (Wang et al., 2024a) shows that vanilla transformers completely fail on this generalization challenge. #### Depth extrapolation. The model is evaluated on inferred facts of greater depth than those included in the training dataset, i.e., $(h,r_1,\dots,r_k,t)∈I_k(C_ID)$ with $k$ larger than $k_train$ . Solving this requires the learner to infer the underlying rules of the task and iteratively apply them at depths far beyond those observed during training. This setting simulates scenarios where the complexity (i.e. reasoning depth) of training data is limited due to budget constraints, yet we expect the model to generalize beyond training. Such depth generalization poses challenges for vanilla transformers in symbolic (Kim and Linzen, 2020) and knowledge reasoning (Yao et al., 2025). Although related to length generalization, depth extrapolation is conceptually distinct: it measures the depth to which a model can repeatedly apply learned rules over its parametric knowledge beyond training. ## 4 Recurrent-Depth Transformer #### Model architecture. Across all experiments we use a decoder-only transformer with a recurrent-depth design illustrated in Figure 1. Concretely, we instantiate a GPT-2 style block with $L$ layers and reuse this for $R$ recurrent iterations, yielding an effective rolled-out depth of $D=L× R$ layers. At each recurrent iteration the same stack of layers is applied to the current hidden states. This allows the model to allocate more computation (increasing $R$ ) at inference time without changing the architecture or re-training the parameters. We exploit this property in our inference-time scaling experiments described in Section 6. Formally, let $f_θ$ denote the $L$ transformer layers with shared parameters $θ$ , and let $h^(0)$ be the input sequence after the initial embedding layer. The model computes $$ h^(r+1)=f_θ\big(h^(r);m\big), r=0,\dots,R-1, $$ where $m$ denotes the causal attention and padding masks. The final representation $h^(R)$ is passed through a final layer normalization and a tied output projection to produce logits over the vocabulary at each position. We only supervise the next-token distribution at the final position corresponding to the tail entity $t$ . Each entity and relation is represented by a dedicated token ( $<e_i>$ , $<r_j>$ ), and the query prefix is mapped to token embeddings. We adopt a zero-initialization strategy to stabilize training under repeated application of shared weights. Specifically, we initialize the output projection matrices (c_proj) of both the multi-head attention and feed-forward blocks to zero, so that each recurrent block is an exact identity mapping at initialization. This ensures that the input-output Jacobian remains stable even when the model is unrolled to a large number of recurrent iterations. This design is motivated by the known instability of deep networks with shared parameters (Agarwala and Schoenholz, 2022), which becomes particularly pronounced in recurrent-depth transformers (Saunshi et al., 2025). Following Zhang et al. (2019), this initialization supports stable optimization under unbounded unrolling of the recurrent iterations. #### Stopping strategies of the recurrent iterations. Training the looped transformer requires a stopping strategy to determine the number of recurrent iterations in the forward pass on the input. We consider two stopping strategies: fixed iteration and dynamic iteration. Fixed iteration determines the recurrent iterations to be the same fixed value for all training instances. The dynamic iteration strategy samples the number of recurrent iterations independently for each training batch. Concretely, for the dynamic model we sample $$ R∼clip\big(Poisson(λ),R_\min,R_\max\big), $$ where $R_\min$ and $R_\max$ are hyperparameters. Such strategies have been shown to be effective in realistic pretraining (Geiping et al., 2025; Zhu et al., 2025), and here we adopt a simple Poisson distribution to control the sampling distribution. Importantly, our strategies contrast with prior studies on the generalization ability of looped transformers, where the iteration number is matched to the complexity of each training instance, assuming oracle access to such complexity. Instead, our setup reflects practical scenarios (Geiping et al., 2025), where the complexity is unknown and computation cannot be allocated precisely in advance. ## 5 Systematic Generalization In this section, we study systematic generalization, i.e. whether models can combine parametric knowledge not composed during training for multi-hop tasks. We focus on $2$ -hop, as Wang et al. (2024a) shows that vanilla transformers already struggle with this simple task. ### 5.1 Experiment Setup #### Dataset. We construct the dataset by instantiating a knowledge graph with $|E|=2000$ and $|R|=200$ , where each entity has average out-degree 20. We then include all 40k atomic facts, randomly partitioned with 95% $C_ID$ , and 5% $C_OOD$ , together with 273.6k inferred facts for training. Our in-distribution set includes 3k held-out two-hop inferred facts composed from $C_ID$ , and OOD set includes nearly 2k two-hop inferred facts composed from $C_OOD$ . #### Model. We train our looped transformer with $L=4$ layers, and use fixed training recurrence with $R∈\{1,2,4,8\}$ . The model with $R=1$ is equivalent to a 4-layer vanilla transformer. We evaluate the accuracy of the predicted token against the gold answer. Absolute position embeddings (APE) (Vaswani et al., 2017) are used as positional embeddings in this setup. We do not use dynamic recurrence in this setting, as systematic generalization in the 2-hop task already emerges from weight sharing under fixed recurrence. In the multi-hop setting, however, it improves extrapolation to more complex samples at inference time and helps alleviate latent overthinking, as discussed in Section 6. ### 5.2 Results <details> <summary>2604.07822v1/x3.png Details</summary>  ### Visual Description ## Heatmap: Training Accuracy Over Epochs ### Overview The heatmap illustrates the training accuracy of a model over different numbers of epochs (R=1, R=2, R=4, R=8) and training times (0, 10, 20, 30, 40 hours). The x-axis represents the number of epochs, while the y-axis represents the training time in hours. The colors indicate the accuracy levels, with darker shades representing higher accuracy. ### Components/Axes - **Epochs**: The x-axis is labeled "Epochs" and ranges from 0 to 40. - **Training Time (Hours)**: The y-axis is labeled "Training Time (Hours)" and ranges from 0 to 40 hours. - **Accuracy**: The color scale ranges from 0.00 to 1.00, with darker shades indicating higher accuracy. ### Detailed Analysis - **R=1**: The accuracy is relatively stable and high, especially after 20 epochs. - **R=2**: The accuracy shows a slight increase after 20 epochs and then stabilizes. - **R=4**: The accuracy increases significantly after 20 epochs and then stabilizes. - **R=8**: The accuracy increases the most after 20 epochs and then stabilizes. ### Key Observations - The accuracy is highest for R=4 and R=8, especially after 20 epochs. - The accuracy for R=1 and R=2 is lower but still relatively high. - There is a noticeable increase in accuracy with more epochs for all R values. ### Interpretation The heatmap suggests that the model's accuracy improves with more epochs, especially for R=4 and R=8. The training time also affects the accuracy, with longer training times generally resulting in higher accuracy. The model's performance is consistent across different R values, indicating that the choice of R value does not significantly impact the training accuracy. </details> Figure 3: Accuracy curves for recurrent-depth models across training epochs and wall-clock time. Left: Test OOD accuracy for models trained with $R∈\{1,2,4,8\}$ , plotted against training epochs. Curves are smoothed with a 100-epoch rolling mean, with shading indicating standard deviation. Middle: Test OOD accuracy for the same models, plotted against training wall-clock time (hours). Right: Accuracy of the $R=4$ model on the examples from training, ID, and OOD test splits, plotted against training epochs. #### Recurrent-depth transformers perform systematic generalization, while vanilla transformers do not. On the left of Figure 3, we plot OOD accuracy as a function of training epochs. We find that the vanilla transformer (i.e. $R=1$ ) completely fails when the task requires combining unfamiliar atomic facts, while even the simplest $R=2$ recurrence achieves non-trivial generalization performance. Increasing training iterations further accelerates the convergence, e.g. $R=4$ converges with 2k epoch, while $R=2$ takes 7k. This acceleration is not only in terms of training steps, but also in absolute wall-clock time (Figure 3, middle). #### Systematic generalization emerges through a three-stage grokking dynamic. We further analyze the training dynamics of the $R=4$ model (right panel of Figure 3) to understand how systematic generalization emerges. We observe a three-stage dynamic: In the first stage, the model overfits the training set, with only training accuracy improving. In the second stage, in-distribution generalization emerges after prolonged training beyond memorization, a phenomenon referred to as grokking. In the final stage, systematic generalization arises only after the model achieves near-perfect in-distribution accuracy, occurring at a much later point than training overfitting (e.g., $10^4$ vs. $10^2$ epochs). #### Analyzing model internals with logit lens. We use the logit lens technique (nostalgebraist, 2020) to examine how models represent the bridge entity and the final target during different stages of training. After each layer and recurrent iteration, we project the intermediate hidden states through the final layer norm and language modeling head to obtain logits over the output vocabulary. For 2-hop inputs of the form $(h,r_1,r_2)$ , where $h$ is the head entity and $r_1,r_2$ are the two relations, we measure at each effective depth the accuracy of predicting the bridge entity at the $r_1$ position and the target entity at the $r_2$ position. Figure 4 shows logits lens for an $R=2$ recurrent-depth model on Training, Test ID, and Test OOD splits, across checkpoints corresponding to the three training stages. We compare against an iso-FLOP 8-layer vanilla transformer with matched effective depth. The vanilla model exhibits only two training stages and fails to achieve non-zero systematic generalization regardless of training time, consistent with Wang et al. (2024a). <details> <summary>2604.07822v1/x4.png Details</summary>  ### Visual Description ## Heatmap Analysis ### Overview The image displays two heatmaps comparing the performance of Recurrent Neural Networks (RNNs) with different configurations (L=4, R=2) and Vanilla Neural Networks (L=8, R=1) on a dataset. The heatmaps are divided into three stages: Training, Test ID, and Test OOD, with each stage further divided into two categories: r1 and r2. ### Components/Axes - **Training**: The first row of the heatmaps shows the performance of the RNN with L=4 and R=2 during training. - **Test ID**: The second row shows the performance during test ID, where the model is evaluated on unseen data. - **Test OOD**: The third row shows the performance during test OOD, where the model is evaluated on out-of-distribution data. - **Stage 1, Stage 2, Stage 3**: The heatmaps are segmented into three stages, each representing a different phase of the training process. - **r1, r2**: The heatmaps are further divided into two categories, r1 and r2, which could represent different versions or configurations of the model. ### Detailed Analysis - **Training**: The RNN with L=4 and R=2 shows a higher performance in the training phase compared to the Vanilla Neural Network with L=8 and R=1. - **Test ID**: During test ID, the RNN with L=4 and R=2 maintains a higher performance than the Vanilla Neural Network with L=8 and R=1. - **Test OOD**: In the test OOD phase, the RNN with L=4 and R=2 again shows a higher performance than the Vanilla Neural Network with L=8 and R=1. - **Effective depth**: The bottom right of the image shows a heatmap of effective depth, which is a measure of the model's ability to generalize to unseen data. The RNN with L=4 and R=2 has a higher effective depth compared to the Vanilla Neural Network with L=8 and R=1. ### Key Observations - The RNN with L=4 and R=2 consistently outperforms the Vanilla Neural Network with L=8 and R=1 across all three stages and categories. - The effective depth of the RNN with L=4 and R=2 is higher, indicating better generalization capabilities. ### Interpretation The data suggests that the RNN with L=4 and R=2 is more effective at handling out-of-distribution data compared to the Vanilla Neural Network with L=8 and R=1. This could be due to the RNN's ability to capture long-term dependencies in the data, which is crucial for out-of-distribution scenarios. The higher effective depth of the RNN with L=4 and R=2 also indicates that it is better at generalizing to unseen data, which is a desirable property in machine learning models. </details> Figure 4: Accuracy of predicting bridge and target entities using logit lens at corresponding token positions for the recurrent-depth ( $R=2$ ) and the 8-layer vanilla transformer. #### Grokking marks a transition from memorization to systematic generalization. We first focus on the recurrent-depth model (Figure 4 left panels), which exhibits distinct mechanisms across the three stages. In Stage 1, the model predicts targets without reliably decoding the bridge, indicating memorization. In Stage 2, the bridge becomes decodable, followed by correct target prediction for in-distribution data at deeper effective depths. Only in Stage 3 does the model succeed on OOD inputs, marking a transition from rote learning to systematic composition. In contrast, although vanilla transformers (right panels) can recover the bridge entity on Test OOD inputs, they fail to perform the second-hop reasoning, as they lack incentives to encode OOD facts in deeper layers. ## 6 Depth Extrapolation In this section, we study depth extrapolation, i.e., whether the model can perform deeper recursions when combining its parametric knowledge than those observed during training. <details> <summary>2604.07822v1/x5.png Details</summary>  ### Visual Description ## Heatmap Analysis ### Overview The image displays a heatmap titled "Recurrence (r)" with various hops (k) ranging from 2 to 22. The heatmap is divided into two main sections: "Train recurrence" and "OOD recurrence," with a color gradient indicating the level of recurrence. ### Components/Axes - **X-axis**: Hops (k) ranging from 2 to 22. - **Y-axis**: Recurrence (r) ranging from 0 to 1. - **Legend**: Two color scales, one for "Train recurrence" and one for "OOD recurrence." - **Dashed Green Line**: Represents the ID (In-Distribution) boundary. - **Dashed Purple Line**: Represents the OOD (Out-of-Distribution) boundary. ### Detailed Analysis The heatmap shows a clear trend of increasing recurrence with higher hops. The "Train recurrence" is predominantly in the blue range, indicating lower recurrence, while the "OOD recurrence" is in the red range, indicating higher recurrence. The ID boundary is consistently above the OOD boundary across all hops, suggesting that the model performs better in ID scenarios compared to OOD scenarios. ### Key Observations - **Trend**: There is a general upward trend in recurrence with increasing hops. - **Boundary**: The ID boundary is consistently above the OOD boundary, indicating better performance in ID scenarios. - **Color Gradient**: The color gradient effectively differentiates between train and OOD recurrence, with red indicating higher OOD recurrence. ### Interpretation The data suggests that as the number of hops increases, the model's recurrence also increases, particularly in OOD scenarios. This could indicate that the model becomes more sensitive to out-of-distribution data as the complexity of the model increases. The ID boundary being consistently above the OOD boundary suggests that the model is robust to out-of-distribution data, performing better in ID scenarios. This could be due to the model's ability to generalize better to unseen data or the regularization techniques used in the model. </details> Figure 5: Accuracy of recurrent-depth models on multi-hop composition, trained under various fixed and dynamic recurrence setups. The violet dash-dotted horizontal line indicates the training recurrence (or maximum in the dynamic setting), while the teal dashed vertical line marks the maximum ID generalization achieved by each model. The x-axis shows hop complexity and the y-axis shows inference-time recurrence ( $r^*$ denotes adaptive halting). ### 6.1 Experiment Setup #### Curriculum training. Different from 2-hop scenarios, learning $k$ -hop tasks generally requires training the model with an easy-to-hard curriculum over hop depth ( $k$ ) as suggested in Yao et al. (2025). Specifically, we start with training on atomic and 2-hop facts until an accuracy threshold ( $95\$ ) is reached on a held-out 2-hop test split. Next, 3-hop data is included in the training for the next stage of our curriculum until $95\$ is achieved on the held-out 3-hop test split. This process is repeated for each hop level $k∈\{2,\dots,N_\max\}$ . To prevent forgetting, at each stage we jointly train on all previously introduced facts (e.g., at stage $k=5$ we train on atomic and 2-hop through 5-hop facts). Due to this threshold-based curriculum, training facts beyond the model’s capability are never exposed. That is, if the model fails to achieve above-threshold accuracy on $k$ -hop queries, training terminates and $(k+1)$ -hop data is never introduced. We define the largest such $k$ as the learnable recursion depth of the model. #### Dataset. We construct the dataset by instantiating a knowledge graph with $|E|=200$ entities and $|R|=10$ relations, where each entity has an average out-degree of 10. We additionally impose a permutation constraint on the knowledge graph to avoid learning shortcut solutions, for which we provide details in Appendix B. We pre-generate 2k atomic facts and 15k $k$ -hop inferred facts for each $k∈[2,K_max]$ , with $K_max=40$ . During training, these facts are progressively introduced following the curriculum described above. For each model, we evaluate on 750 held-out $k$ -hop facts. Facts with $k$ up to the model’s learnable recursion depth form the in-distribution test set, while those beyond it constitute the extrapolation test set. This split is model-dependent, reflecting each model’s maximum achievable reasoning depth. #### Model. We follow the model setups in Section 5.1, except that we use $R∈$ {1,2,3,4,5,6,7,8} for fixed iteration. Here we use no positional embeddings (NoPE) (Kazemnejad et al., 2023; Wang et al., 2024b), which shows better generalization in pilot studies. In addition to results with $L=4$ , we present results with varying model size and dynamic train recurrence in Appendix F, and across random seed initializations in Appendix G. ### 6.2 In-Distribution Generalization #### Scaling up training-time iteration increases the learnable recursion depth of looped transformers. Looking at the blue area of Figure 5, we find that increasing training recurrent iterations accordingly improves the ID generalization. This is consistent with previous findings (Wang et al., 2024a; Yao et al., 2025) that the learnable recursion depth of a transformer is bounded by the depth of its layers, and we demonstrate that for looped transformers, scaling up training recurrent iterations can also increase its ”effective depth”, without relying on additional parameters. Training with dynamic iteration further increases the learnable recursion depth over the fixed iteration, suggesting that the fixed iteration is not an optimal design choice. Interestingly, more recurrent iterations do not always translate into larger learnable depth. (e.g., both R=7 and R=8 learns up to 16-hop task). <details> <summary>2604.07822v1/x6.png Details</summary>  ### Visual Description ## Line Graph: Update Steps vs. ID Hops Generalized (k) ### Overview The line graph depicts the relationship between the number of ID hops generalized (k) and the update steps. The x-axis represents the number of ID hops generalized, while the y-axis represents the update steps. The line graph shows a sharp increase in update steps as the number of ID hops generalized increases. ### Components/Axes - **X-axis**: ID Hops Generalized (k) - **Y-axis**: Update Steps - **Legend**: No legend is present in the image. - **Axis Titles**: X-axis is labeled "ID Hops Generalized (k)" and Y-axis is labeled "Update Steps". ### Content Details The line graph shows a sharp increase in update steps as the number of ID hops generalized increases. The update steps start at approximately 500,000 when k is 2, and increase to approximately 2,000,000 when k is 20. The update steps then increase rapidly, reaching approximately 2,500,000 when k is 22. ### Interpretation The data suggests that as the number of ID hops generalized increases, the update steps also increase. This could be due to the fact that more ID hops generalized require more updates to be made. The rapid increase in update steps as the number of ID hops generalized increases could be due to the fact that the system is becoming more complex as the number of ID hops generalized increases. The high level of update steps when k is 22 could be due to the fact that the system is reaching its maximum capacity for handling ID hops generalized. Overall, the data suggests that the system is becoming more complex as the number of ID hops generalized increases, and that the update steps are increasing rapidly as a result. </details> Figure 6: Cumulative gradient updates required to first generalize to each hop complexity. #### Phase transition from prolonged training to rapid learning. We observe that models require a prolonged training phase to acquire low-hop tasks, after which they rapidly generalize to much more complex samples (Figure 6). We illustrate this for the model trained with dynamic recurrence by plotting training steps against the compositional complexity achieved on in-distribution data. This suggests that the main difficulty lies in discovering the underlying compositional rule. Once such a rule is internalized, the model can quickly extend it to samples of much higher complexity. In Figure 6 we observe how the model required over 1.3 million steps for grokking up to 4-hop train samples but was quickly able to learn up to 19-hop samples very few additional steps. Beyond that, for even more complex samples, while each new hop requires additional training steps to cross the 95% threshold, the model still achieves strong generalization (>90%) on hops 20, 21, and 22 within fewer than 8k extra steps per hop which is commensurate with the steps required for each additional hop from 4 through 19. By loading a trained checkpoint (20, say) and continuing training exclusively on 21-hop samples instead of the data mix consisting of samples from all previous stages in our curriculum, generalization over 90% on the new split can be achieved in as little as 50 additional steps of training. ### 6.3 Depth Extrapolation #### Scaling inference-time iterations unlocks depth extrapolation. In Figure 5, we observe that when using the same number of recurrent iterations as in training, all models struggle to generalize to tasks of higher complexity than those seen during training. However, this limitation is immediately alleviated when we increase the number of inference-time iterations, with more iterations enabling generalization to progressively harder tasks. Notably, this scaling effect only emerges for $R>4$ , suggesting that sufficient training-time iterations are a prerequisite for benefiting from increased inference-time computation. #### The effect of training iteration strategy on extrapolation. The above results characterize the maximum reasoning depth each model can achieve under the curriculum setting, but they do not disentangle whether the differences (e.g. $R=6$ generalizing to $17$ -hop vs. $R=8$ to $24$ -hop) are due to more training iterations or exposure to more complex training data (e.g. $R=6$ is trained up to $13$ -hop, while $R=8$ up to $16$ -hop). To isolate the effect of the training iteration strategy, we train all models on the same data (up to $12$ -hop) and evaluate extrapolation on $12$ – $24$ hop tasks. <details> <summary>2604.07822v1/x7.png Details</summary>  ### Visual Description ## Heatmap: Recurrence vs. hops ### Overview The image displays a heatmap with five different scenarios labeled R=5 to R=dynamic. Each scenario represents a different number of hops (k) and a different ID/OOD boundary. The heatmap shows the recurrence of a certain event or pattern across different hops and ID/OOD boundaries. ### Components/Axes - **X-axis**: Hops (k) ranging from 2 to 20 - **Y-axis**: Recurrence (r) ranging from 0 to 1.5 - **Legend**: Two color scales, one for ID/OOD boundary and one for Train recurrence - **ID/OOD boundary**: Represented by a dashed green line - **Train recurrence**: Represented by a dashed purple line ### Detailed Analysis or Content Details - **R=5**: The heatmap shows a high recurrence rate for ID/OOD boundary, especially at lower hops (k=2, 4, 6). The recurrence rate decreases as hops increase. - **R=6**: Similar to R=5, the heatmap shows a high recurrence rate for ID/OOD boundary, but the rate is slightly lower than R=5. The recurrence rate decreases as hops increase. - **R=7**: The heatmap shows a high recurrence rate for ID/OOD boundary, but the rate is slightly lower than R=6. The recurrence rate decreases as hops increase. - **R=8**: The heatmap shows a high recurrence rate for ID/OOD boundary, but the rate is slightly lower than R=7. The recurrence rate decreases as hops increase. - **R=dynamic**: The heatmap shows a high recurrence rate for ID/OOD boundary, but the rate is slightly lower than R=8. The recurrence rate decreases as hops increase. ### Key Observations - The recurrence rate for ID/OOD boundary is consistently high across all scenarios. - The recurrence rate decreases as the number of hops increases. - The recurrence rate is highest at R=5 and R=6, and lowest at R=dynamic. ### Interpretation The data suggests that the recurrence rate for ID/OOD boundary is consistently high across all scenarios. The recurrence rate decreases as the number of hops increases, indicating that the event or pattern is less likely to occur with more hops. The highest recurrence rate is observed at R=5 and R=6, and the lowest recurrence rate is observed at R=dynamic. This could indicate that the event or pattern is more likely to occur with fewer hops and a lower ID/OOD boundary. </details> Figure 7: Accuracy of models trained with fixed recurrence $R∈\{5,6,7,8\}$ and dynamic recurrence on up to 12-hop samples. From Figure 7, we first find that among fixed-iteration models, increasing the number of training-time iterations substantially improves extrapolation when scaling inference-time iterations (e.g. $R=6$ extrapolates up to $14$ -hop, while $R=8$ reaches $19$ -hop). Second, under the same training data, the dynamic iteration strategy achieves comparable extrapolation performance to the $R=8$ model (both reaching $19$ -hop). This contrasts with Figure 5, where the dynamic strategy generalizes to significantly higher complexity than $R=8$ . These results suggest that the maximum number of iterations used during training determines the extrapolation range (i.e. how far beyond the training complexity the model can generalize), while dynamic iteration effectively exploits this range, since it enables a larger learnable recursion depth. Hence, when training data is sufficiently complex, dynamic iteration should be preferred over fixed strategies with the same maximum iteration budget. #### Scaling inference-time iterations is limited by overthinking. Despite strong generalization performance, we observe performance degradation when using excessively large inference-time iterations. For example, increasing iterations beyond 15 for the R=dynamic does not improve OOD performance (Figure 5), a phenomenon known as overthinking (Bansal et al., 2022). We study this along two key axes: (1) inference iterations, i.e. how increasing the inference iterations affects the model’s prediction confidence, and (2) task complexity, i.e. how increasing task complexity impacts this confidence. <details> <summary>2604.07822v1/x8.png Details</summary>  ### Visual Description ## Heatmap: Recurrent Iteration vs. Margin ### Overview The heatmap displays the relationship between recurrent iteration (t) and margin (M) for different hop lengths (2-hop, 5-hop, 10-hop, 13-hop, 16-hop, 30-hop) and a dynamic margin setting. The x-axis represents the recurrent iteration, while the y-axis represents the margin. ### Components/Axes - **X-axis**: Recurrent Iteration (t) - **Y-axis**: Margin (M) - **Legend**: - 2-hop - 5-hop - 10-hop - 13-hop - 16-hop - 30-hop - Avg. first-hit t* - Margin = 0 ### Detailed Analysis or Content Details The heatmap shows that as the recurrent iteration increases, the margin generally decreases for all hop lengths. The 2-hop and 5-hop lines are the most prominent, showing a steep decline in margin as t increases. The 10-hop, 13-hop, 16-hop, and 30-hop lines show a more gradual decline. The dynamic margin line (dashed line) remains relatively flat, indicating that the margin does not significantly change with increasing recurrent iteration. ### Key Observations - The 2-hop and 5-hop lines show the most significant decrease in margin as the recurrent iteration increases. - The dynamic margin line remains relatively flat, indicating minimal change in margin with increasing recurrent iteration. - The 10-hop, 13-hop, 16-hop, and 30-hop lines show a more gradual decline in margin. ### Interpretation The heatmap suggests that as the recurrent iteration increases, the margin decreases for all hop lengths. This could indicate that the system becomes less sensitive to changes in margin as the number of iterations increases. The dynamic margin line remaining relatively flat suggests that the system's margin is not significantly affected by changes in the recurrent iteration. This could be due to the system's ability to adapt to changes in the environment or the system's inherent stability. </details> Figure 8: Average logit margin across recurrent iterations for fixed-recurrence ( $R=6,7,8$ ) and dynamic-recurrence models. Curves show different hop complexities, and dashed vertical lines indicate the average first-hit iteration $t^*$ (when the correct entity is predicted). In Figure 8, we analyze the logit margin, defined as the difference between the logit of the correct entity and that of the strongest competing token, and make two observations. First, across all models and tasks, the margin increases with inference iterations until reaching a peak, and then consistently declines as iterations continue. This suggests that overthinking arises as the iteration number grows, regardless of the task complexity. Notably, the dynamic model exhibits a much slower margin decay compared to fixed-iteration models, indicating that dynamic iteration is more robust to overthinking. Second, the peak margin decreases as task complexity increases across all models. This implies that for more complex tasks, the model’s predictions are inherently less confident and therefore more susceptible to degradation under additional iterations. As a result, the benefit of increasing inference iterations diminishes for highly complex tasks. Note that although previous work mitigates overthinking by injecting inputs information in every iteration (Bansal et al., 2022; Geiping et al., 2025), we find that such methods do not resolve the issue in implicit reasoning. <details> <summary>2604.07822v1/x9.png Details</summary>  ### Visual Description ## Heatmap: Distribution of Average Iterations ### Overview The heatmap shows the distribution of average iterations required for two different methods, "Ours" and "KL-only," as the sample complexity increases. The x-axis represents the sample complexity, and the y-axis represents the average iterations. ### Components/Axes - **x-axis**: Sample Complexity (k) - **y-axis**: Average Iterations - **Legend**: - "Ours" (blue) - "KL-only" (orange) ### Detailed Analysis or Content Details The heatmap illustrates that both methods require an increasing number of iterations as the sample complexity increases. The "Ours" method (blue) generally requires fewer iterations compared to the "KL-only" method (orange). However, the "Ours" method shows a more consistent increase in iterations, while the "KL-only" method experiences a peak before decreasing. The "Ours" method's iterations start lower and reach higher values as the sample complexity increases, indicating a potentially more efficient or robust approach. ### Key Observations - The "Ours" method consistently requires fewer iterations than the "KL-only" method across all sample complexities. - The "KL-only" method shows a peak in iterations at a sample complexity of around 22, after which the iterations decrease. - The "Ours" method's iterations start lower and reach higher values as the sample complexity increases. ### Interpretation The heatmap suggests that the "Ours" method is more efficient in terms of the number of iterations required as the sample complexity increases. This could indicate that the "Ours" method is better at handling larger datasets or is more robust to variations in sample complexity. The "KL-only" method, while requiring fewer iterations overall, has a higher peak in iterations, which might suggest it is more sensitive to changes in sample complexity. The "Ours" method's more consistent increase in iterations could also imply that it is more stable and reliable in its performance. </details> Figure 9: Average recurrent iterations using adaptive halting vs. sample complexity. #### Adaptive halting improves inference efficiency. We flexibly halt recurrence in order to allocate compute proportionate to input complexity. Prior work (Geiping et al., 2025) proposes adaptive halting based on the output distribution $p_t(·\mid x)$ , terminating when the change between successive iterations becomes small, measured by $KL\bigl(p_t,|,p_t-1\bigr)<ε_KL$ . In our setting, we find that this criterion often halts the recurrence prematurely, leading to suboptimal performance. To address this, we additionally incorporate the entropy of the output distribution, $H(p_t)$ , and only stop when both the divergence is small, and the prediction is confident, i.e., $$ KL\bigl(p_t \| p_t-1\bigr)<ε_KL and H(p_t)<H_thresh. $$ In Figure 9, we plot the number of iterations using both methods against the hop count ( $k$ ), demonstrating that ours results in better allocation of inference-time compute in accordance with task complexity. While the output distribution may change very little across iterations, the entropy is still high, indicating that the model remains uncertain despite this apparent convergence. We compare results using the two methods in Figure 10. In our setting, combining KL divergence with entropy therefore provides a more reliable halting signal and yields better overall results. <details> <summary>2604.07822v1/x10.png Details</summary>  ### Visual Description ## Heatmap: R=dynamic (ID 22-hop) ### Overview The heatmap displays the performance of two different halting rules, "Ours" and "KL-only," across various hop counts (k) and ID/OOD (In-Distribution/Out-of-Distribution) boundaries. The color gradient represents the correlation between the two rules, with blue indicating a higher correlation and red indicating a lower correlation. ### Components/Axes - **X-axis (Hop counts, k)**: Ranges from 2 to 38 hops. - **Y-axis (Halting rule)**: Two categories are present: "Ours" and "KL-only." - **Color gradient**: Blue represents high correlation (ID), and red represents low correlation (OOD). - **Legend**: Two colors, blue for ID and red for OOD, with a dashed line indicating the ID/OOD boundary. ### Detailed Analysis or Content Details - **Ours**: The majority of the heatmap is colored blue, indicating a high correlation between the "Ours" rule and the ID boundary. The correlation decreases as the hop count increases. - **KL-only**: The heatmap shows a more varied distribution of colors, with some areas colored blue and others colored red. The correlation with the ID boundary is lower compared to "Ours." - **ID/OOD boundary**: A dashed line runs horizontally across the heatmap, indicating the threshold between ID and OOD data. ### Key Observations - **High correlation with ID boundary**: The "Ours" rule consistently shows high correlation with the ID boundary across all hop counts. - **Variable correlation with OOD boundary**: The "KL-only" rule shows a more variable correlation with the OOD boundary, with some areas showing high correlation and others showing low correlation. - **No clear trend in correlation with hop count**: There is no clear trend in the correlation between the halting rules and hop count, as the correlation varies across different hop counts. ### Interpretation The heatmap suggests that the "Ours" halting rule is more effective in maintaining a high correlation with the ID boundary across different hop counts compared to the "KL-only" rule. This indicates that the "Ours" rule is more robust and reliable in distinguishing between in-distribution and out-of-distribution data. The "KL-only" rule, while showing some correlation with the ID boundary, does not maintain this correlation as consistently as the "Ours" rule. This could imply that the "Ours" rule is more effective in handling out-of-distribution data, which is a common challenge in machine learning. </details> Figure 10: Comparison of adaptive halting based on KL-divergence and entropy (ours) versus KL-divergence alone (Geiping et al., 2025). ## 7 Conclusion We study whether recurrent-depth transformers can compositionally use parametric knowledge for implicit multi-hop reasoning, a task that is challenging for vanilla transformers. Through controlled experiments on models trained from scratch, we show that recurrent-depth transformers successfully address both compositional generalization challenges. Systematic generalization emerges through a three-stage grokking dynamic, as the model transitions from rote memorization to generalizable solutions. Depth extrapolation is enabled by scaling inference-time compute, where additional iterations allow for greater reasoning depth, although latent overthinking limits performance on highly complex tasks. Overall, our results highlight recurrent-depth transformers as a promising architecture for compositional reasoning over parametric knowledge. ## Acknowledgments The authors of this paper express their gratitude to Boshi Wang for valuable discussions on this work, and for motivating the permutation-based task formulation for depth exploration described in Appendix B. We also thank Yupei Du for valuable feedback on this paper. ## References - A. Agarwala and S. S. Schoenholz (2022) Deep equilibrium networks are sensitive to initialization statistics. In International Conference on Machine Learning, pp. 136–160. Cited by: §4. - Z. Allen-Zhu and Y. Li (2023) Physics of language models: part 3.1, knowledge storage and extraction. arXiv preprint arXiv:2309.14316. Cited by: §3. - M. Balesni, T. Korbak, and O. Evans (2024) The two-hop curse: llms trained on $A→ B$ , $B→ C$ fail to learn $A→ C$ . arXiv preprint arXiv:2411.16353. Cited by: Appendix D. - A. Bansal, A. Schwarzschild, E. Borgnia, Z. Emam, F. Huang, M. Goldblum, and T. Goldstein (2022) End-to-end algorithm synthesis with recurrent networks: extrapolation without overthinking. Advances in Neural Information Processing Systems 35, pp. 20232–20242. Cited by: §1, §1, §6.3, §6.3. - L. Berglund, M. Tong, M. Kaufmann, M. Balesni, A. C. Stickland, T. Korbak, and O. Evans (2023) The reversal curse: llms trained on” a is b” fail to learn” b is a”. arXiv preprint arXiv:2309.12288. Cited by: §1. - E. Biran, D. Gottesman, S. Yang, M. Geva, and A. Globerson (2024) Hopping too late: exploring the limitations of large language models on multi-hop queries. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Y. Al-Onaizan, M. Bansal, and Y. Chen (Eds.), Miami, Florida, USA, pp. 14113–14130. External Links: Link, Document Cited by: §1. - T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. (2020) Language models are few-shot learners. Advances in neural information processing systems 33, pp. 1877–1901. Cited by: §1. - M. Dehghani, S. Gouws, O. Vinyals, J. Uszkoreit, and L. Kaiser (2019) Universal transformers. In International Conference on Learning Representations, External Links: Link Cited by: Appendix D, §1. - H. Du, Y. Dong, and X. Ning (2025) Latent thinking optimization: your latent reasoning language model secretly encodes reward signals in its latent thoughts. arXiv preprint arXiv:2509.26314. Cited by: Appendix D. - N. Dziri, X. Lu, M. Sclar, X. L. Li, L. Jiang, B. Y. Lin, P. West, C. Bhagavatula, R. Le Bras, J. D. Hwang, S. Sanyal, S. Welleck, X. Ren, A. Ettinger, Z. Harchaoui, and Y. Choi (2023) Faith and fate: limits of transformers on compositionality. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA. Cited by: Appendix D, §1. - Y. Fan, Y. Du, K. Ramchandran, and K. Lee (2025) Looped transformers for length generalization. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §1, §2, §2. - L. Gao, S. Biderman, S. Black, L. Golding, T. Hoppe, C. Foster, J. Phang, H. He, A. Thite, N. Nabeshima, et al. (2020) The pile: an 800gb dataset of diverse text for language modeling. arXiv preprint arXiv:2101.00027. Cited by: §2. - J. Geiping, S. M. McLeish, N. Jain, J. Kirchenbauer, S. Singh, B. R. Bartoldson, B. Kailkhura, A. Bhatele, and T. Goldstein (2025) Scaling up test-time compute with latent reasoning: a recurrent depth approach. In ES-FoMo III: 3rd Workshop on Efficient Systems for Foundation Models, External Links: Link Cited by: Appendix D, §1, §4, Figure 10, §6.3, §6.3. - M. Geva, J. Bastings, K. Filippova, and A. Globerson (2023) Dissecting recall of factual associations in auto-regressive language models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, H. Bouamor, J. Pino, and K. Bali (Eds.), Singapore, pp. 12216–12235. External Links: Link, Document Cited by: §1. - S. Hao, S. Sukhbaatar, D. Su, X. Li, Z. Hu, J. E. Weston, and Y. Tian (2025) Training large language models to reason in a continuous latent space. In Second Conference on Language Modeling, External Links: Link Cited by: Appendix D. - J. Huang and K. C. Chang (2023) Towards reasoning in large language models: a survey. In Findings of the Association for Computational Linguistics, ACL 2023, pp. 1049–1065. Cited by: Appendix A. - A. Kazemnejad, I. Padhi, K. Natesan Ramamurthy, P. Das, and S. Reddy (2023) The impact of positional encoding on length generalization in transformers. Advances in Neural Information Processing Systems 36, pp. 24892–24928. Cited by: §6.1. - N. Kim and T. 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), B. Webber, T. Cohn, Y. He, and Y. Liu (Eds.), Online, pp. 9087–9105. External Links: Link, Document Cited by: §3.2. - H. Kohli, S. Kumar, and H. Sun (2025) GroundCocoa: a benchmark for evaluating compositional & conditional reasoning in language models. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), L. Chiruzzo, A. Ritter, and L. Wang (Eds.), Albuquerque, New Mexico, pp. 8280–8295. External Links: Link, Document, ISBN 979-8-89176-189-6 Cited by: Appendix D. - B. Lake and M. Baroni (2018) Generalization without systematicity: on the compositional skills of sequence-to-sequence recurrent networks. In International conference on machine learning, pp. 2873–2882. Cited by: §1. - Z. Lan, M. Chen, S. Goodman, K. Gimpel, P. Sharma, and R. Soricut (2020) ALBERT: a lite bert for self-supervised learning of language representations. In International Conference on Learning Representations, External Links: Link Cited by: Appendix D. - [22] I. Loshchilov and F. Hutter Decoupled weight decay regularization. In International Conference on Learning Representations, Cited by: Appendix C. - W. Lu, Y. Yang, K. Lee, Y. Li, and E. Liu (2025) Latent chain-of-thought? decoding the depth-recurrent transformer. arXiv preprint arXiv:2507.02199. Cited by: Appendix D. - nostalgebraist (2020) Interpreting gpt: the logit lens. External Links: Link Cited by: §5.2. - O. Press, M. Zhang, S. Min, L. Schmidt, N. Smith, and M. Lewis (2023) Measuring and narrowing the compositionality gap in language models. In Findings of the Association for Computational Linguistics: EMNLP 2023, H. Bouamor, J. Pino, and K. Bali (Eds.), Singapore, pp. 5687–5711. External Links: Link, Document Cited by: §1. - N. Saunshi, N. Dikkala, Z. Li, S. Kumar, and S. J. Reddi (2025) Reasoning with latent thoughts: on the power of looped transformers. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: Figure 1, §2, §4. - H. A. Simon and A. Newell (1971) Human problem solving: the state of the theory in 1970.. American Psychologist 26, pp. 145–159. External Links: Link Cited by: Appendix D. - A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin (2017) Attention is all you need. In Advances in Neural Information Processing Systems, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30, pp. . External Links: Link Cited by: §5.1. - B. Wang, X. Yue, Y. Su, and H. Sun (2024a) Grokking of implicit reasoning in transformers: a mechanistic journey to the edge of generalization. In Proceedings of the 38th International Conference on Neural Information Processing Systems, NIPS ’24, Red Hook, NY, USA. External Links: ISBN 9798331314385 Cited by: Appendix D, §1, §3.2, §3.2, §5.2, §5, §6.2. - J. Wang, T. Ji, Y. Wu, H. Yan, T. Gui, Q. Zhang, X. Huang, and X. Wang (2024b) Length generalization of causal transformers without position encoding. In Findings of the Association for Computational Linguistics: ACL 2024, pp. 14024–14040. Cited by: §6.1. - J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou, et al. (2022) Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems 35, pp. 24824–24837. Cited by: §1. - L. Yang, K. Lee, R. D. Nowak, and D. Papailiopoulos (2024a) Looped transformers are better at learning learning algorithms. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §2. - S. Yang, E. Gribovskaya, N. Kassner, M. Geva, and S. Riedel (2024b) Do large language models latently perform multi-hop reasoning?. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), L. Ku, A. Martins, and V. Srikumar (Eds.), Bangkok, Thailand, pp. 10210–10229. External Links: Link, Document Cited by: §1, §3. - Y. Yao, Y. Du, D. Zhu, M. Hahn, and A. Koller (2025) Language models can learn implicit multi-hop reasoning, but only if they have lots of training data. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, C. Christodoulopoulos, T. Chakraborty, C. Rose, and V. Peng (Eds.), Suzhou, China, pp. 9695–9713. External Links: Link, ISBN 979-8-89176-332-6 Cited by: Appendix D, §1, §3.2, §3, §6.1, §6.2. - H. Zhang, Y. N. Dauphin, and T. Ma (2019) Residual learning without normalization via better initialization. In International Conference on Learning Representations, External Links: Link Cited by: §4. - R. Zhu, Z. Wang, K. Hua, T. Zhang, Z. Li, H. Que, B. Wei, Z. Wen, F. Yin, H. Xing, et al. (2025) Scaling latent reasoning via looped language models. arXiv preprint arXiv:2510.25741. Cited by: Appendix D, §1, §4. ## Appendix A Limitations Through our paper, we evaluate vanilla and recurrent-depth transformers on a single family of implicit reasoning problems. While we cleanly isolate systematic generalization and depth exploration in compositional reasoning, we do not cover the entire range of reasoning problems relevant to modern language models (Huang and Chang, 2023). In order to maintain a controlled setting and properly study the behavior of recurrent-depth models, our experiments are intentionally small-scale and focused. This potentially limits direct extrapolation of results to modern LLMs whose performance and behavior is shaped by many additional factors like tokenizer choices, heterogeneous internet-scale data, pretraining data, post-training procedures and optimization at a much larger scale. Althought we study somewhat larger models in Appendix F, these are still significantly limited in scale relative to frontier LLMs today. Additionally, our task formulation abstracts away many aspects of real-world language use. Inputs are presented in a highly structured form with dedicated entity and relation tokens with a very limited vocabulary. This removes challenges that might arise from surface-form variation, underspecification, distractor information, and distribution shift in natural language. Therefore, we do not claim complete and immediate transfer of positive results to LLMs trained with recurrent-depth at scale. However, we hope to isolate architectural effects in a controlled setting and use them to inform future designs for more robust implicit reasoning in future LLMs. ## Appendix B Dataset To investigate how our implicit reasoning models scale to deeper $k$ -hop composition tasks, we design a dataset from a permutation-based knowledge graph. In this setup, we found that models can sometimes achieve high accuracy via shortcuts rather than performing the intended multi-step traversal. For large $k$ , the final tail entity $t$ can become nearly determined by a short suffix of the relation sequence. Thus, a model may learn a shallow mapping from the trailing relations to the answer instead of retrieving the intermediate entities. To overcome this, We first construct a set of atomic facts over $|E|=200$ entities and $|R|=10$ relations. For each relation $r∈ R$ , we sample a random permutation $π_r$ over the entity indices and define the atomic facts as $$ ∀ e_i∈ E: (e_i,r,e_π_{r(i)}). $$ Thus, each relation acts as a bijection over the entity set. Since the out-degree is set to $d=|R|=10$ , every entity has exactly one outgoing edge for each relation. This ensures that each relation has full coverage over entities. To generate a $k$ -hop example, we sample a starting atomic fact and then iteratively extend it by following outgoing edges from the current tail entity. At each step, one outgoing relation-edge pair is selected uniformly at random. Intermediate entities are used only during construction and are not included in the final training example. ## Appendix C Training Details & Additional Parameters For most experiments, we use an embedding dimension of 768, 12 attention heads and a recurrent block of 4 transformer layers. However, in Appendix F we experiment with recurrent blocks of greater depth. Similarly, in Section 5.2 we compare with a vanilla transformer of larger depth (8) in our systematicity analysis. AdamW optimizer (Loshchilov and Hutter, ) with a learning rate of $10^-4$ , weight decay of 0.01 and a linear warmup schedule of 2000 steps is used in all of our experiments. We use a batch size of 512 and 128 for the systematicity and extrapolation experiments respectively. In our adaptive halting method, we use fixed thresholds $ε_KL=0.01$ and $H_thresh=3.00$ , and halt recurrence when both $KL\bigl(p_t \| p_t-1\bigr)<ε_KL$ and $H(p_t)<H_thresh$ . ## Appendix D Other Related Work #### Implicit Reasoning LLMs. Weight-sharing in transformers has been used as a strategy for parameter-efficiency starting with Universal Transformers (Dehghani et al., 2019) and ALBERT (Lan et al., 2020). Recent work revisits this idea as a mechanism for implicit reasoning and scaling computation at inference-time. Recurrent-depth models trained at LLM scale such as Huginn (Geiping et al., 2025) and Ouro (Zhu et al., 2025) have shown promise and often exceed the performance of larger, non-recurrent models on popular benchmarks. Another approach to latent reasoning, Coconut (Hao et al., 2025) replaces discrete reasoning tokens with continuous hidden states, enabling reasoning in latent space rather than through explicit text similar to recurrent-depth models. #### Studies on Implicit Reasoning in Recurrent Depth LLMs. There is a growing body of work analyzing the improved performance of models through mechanisms like recurrent-depth architectures that enable reasoning in latent space. At LLM scale, Lu et al. (2025) study the internals of the Huginn-3.5B using logit lens by projecting the intermediate representations through an unembedding matrix or through the models specialized coda layers (coda-lens). They report little evidence of actual latent reasoning and inconsistencies in interpretability across recurrent blocks. Conversely, Du et al. (2025) find that trajectories of hidden states or ”latent thoughts” that lead to correct outcomes are distinguishable from those that lead to incorrect outcomes through certain metrics. The representations of correct trajectories have a higher entropy, anisotropy, and intrinsic dimension but a lower effective rank indicating that correct thinking processes carry richer information with less noise, and generate more expressive latent representations. Both works take a pretrained, generalist LLM (Huginn-3.5B) and focus on probing its latent computations. #### Compositional Generalization. Many recent studies have examined the performance of transformer-based language models in compositional generalization, motivated by the view that such step-by-step reasoning is central to human intelligence (Simon and Newell, 1971) and a proxy for analyzing how models can learn internal mechanisms for combining facts instead of emitting long rationales in the form of CoT. Using 3 representative tasks, Dziri et al. (2023) demonstrate that transformers reduce compositional tasks to linearized subgraph matching that fails with increasing complexity. Wang et al. (2024a) show that transformers learn implicit 2-hop compositional generalization only through ”grokking” and that even then systematicity (OOD generalization) is never observed. Kohli et al. (2025) construct a logically grounded dataset to benchmark on compositional generalization and conditional reasoning, and show that even frontier LLMs struggle on tasks of sufficient compositional complexity. Experiments by Yao et al. (2025) indicate that transformers are capable of multi-hop ID generalization but each hop requires exponentially larger amounts of data and that this issue is partially mitigated through curriculum learning. They also show that intermediate entities are retrieved layerwise and that, in order to achieve $k$ -hop generalization, the numbers of layers needs to grow linearly in $k$ . Balesni et al. (2024) finetune pretrained LLMs on synthetic or semi-synthetic composition tasks and find that the models are only able to achieve composition when the two synthetic facts co-occur in the same finetuning document or test-time prompt or when one of the hops is a natural fact in the pretraining corpus. ## Appendix E Experiments with default initialization <details> <summary>2604.07822v1/x11.png Details</summary>  ### Visual Description ## Heatmap Analysis ### Overview The image displays a series of heatmaps, each representing the recurrence of ID (Internal Data) and OOD (Out-of-Distribution) data across different hop lengths (k). The hop length refers to the number of steps taken in a sequence to determine the recurrence of data. ### Components/Axes - **X-axis**: Represents the hop length (k), ranging from 2 to 20. - **Y-axis**: Represents the recurrence rate (r), ranging from 0.00 to 1.00. - **Legend**: Shows the color gradient indicating the recurrence rate, with darker shades representing higher recurrence rates. - **ID/OOD boundary**: A dashed line indicating the threshold between ID and OOD data. ### Content Details Each heatmap shows a different recurrence rate for ID and OOD data at various hop lengths. The ID data is represented in darker shades, indicating higher recurrence rates, while the OOD data is represented in lighter shades. The ID/OOD boundary line helps to distinguish between the two categories. ### Key Observations - **Hop Length 2**: The recurrence rate for ID data is consistently high, with a slight increase towards the end of the hop length. - **Hop Length 3**: The recurrence rate for ID data remains high, but the increase is less pronounced compared to hop length 2. - **Hop Length 4**: The recurrence rate for ID data shows a slight decrease, but still remains high. - **Hop Length 5**: The recurrence rate for ID data shows a significant decrease, indicating a higher likelihood of OOD data. - **Hop Length 6 to 20**: The recurrence rate for ID data shows a slight increase, but the decrease from hop length 5 is less pronounced. ### Interpretation The data suggests that as the hop length increases, the likelihood of OOD data also increases. This is particularly evident in hop lengths 5 and above, where the recurrence rate for ID data decreases significantly. The ID/OOD boundary line indicates that the threshold between ID and OOD data is relatively high, suggesting that the model is able to distinguish between the two categories with a high degree of accuracy. However, the slight increase in recurrence rate for ID data as the hop length increases indicates that the model may not be able to fully capture the complexity of the data, leading to a slight decrease in accuracy. </details> Figure 11: Results with default initialization for training recurrences $R∈\{1,\dots,7\}$ and dynamic recurrence. Here we report results obtained using the default Gaussian initialization for the c_proj matrices, rather than the zero-initialization described in Section 4. As observed from Figure 11, the results are mixed across training runs, and increasing recurrence does not yield a clear or consistent pattern of improved ID or OOD generalization as well as robustness to latent overthinking. Only the model trained with $R=7$ , hows strong signs of inference-time scaling and robustness to latent overthinking. In the case of the model trained with $R=5$ , there is no OOD generalization with increased recurrence at inference-time. For most of the other runs, we see performance degradation due to latent overthinking. <details> <summary>2604.07822v1/x12.png Details</summary>  ### Visual Description ## Heatmap: Recurrence vs. Hops ### Overview The image displays a heatmap titled "Recurrence vs. Hops" with five subplots, each representing a different seed ID (1 to 5) with varying hop lengths (9-hop, 11-hop). The heatmap shows the recurrence of certain events or patterns across different hop lengths. ### Components/Axes - **X-axis (Hops)**: Represents the number of hops, ranging from 2 to 20. - **Y-axis (Recurrence)**: Represents the recurrence rate, ranging from 0.0 to 1.0. - **Legend**: Located at the bottom right, indicating the color scale for recurrence (0.0 to 1.0) and hop length (2 to 20). - **ID/OOD boundary**: A dashed green line running vertically down the center of the heatmap. - **Train recurrence**: A dashed purple line running horizontally across the heatmap. ### Detailed Analysis Each subplot shows a grid of squares where the color intensity represents the recurrence rate. The darker the color, the higher the recurrence rate. The ID/OOD boundary (dashed green line) and train recurrence (dashed purple line) serve as reference points to compare the recurrence rates across different hop lengths. ### Key Observations - **Seed 1 (9-hop)**: Shows a relatively high recurrence rate across most hop lengths, with a slight decrease towards the higher end of the hop range. - **Seed 2 (9-hop)**: Similar to Seed 1, with a high recurrence rate but slightly lower than Seed 1. - **Seed 3 (11-hop)**: Shows a moderate recurrence rate, with a slight increase towards the higher end of the hop range. - **Seed 4 (11-hop)**: Similar to Seed 3, with a moderate recurrence rate and a slight increase towards the higher end of the hop range. - **Seed 5 (11-hop)**: Shows a high recurrence rate, similar to Seed 1 and Seed 2. ### Interpretation The heatmap suggests that the recurrence rate is generally higher for Seed 1 and Seed 2 across most hop lengths, while Seed 3 and Seed 4 show a moderate recurrence rate with a slight increase towards the higher end of the hop range. Seed 5 shows a high recurrence rate, similar to Seed 1 and Seed 2. The ID/OOD boundary and train recurrence lines help in understanding the distribution of recurrence rates and the impact of hop length on the recurrence of events or patterns. </details> Figure 12: Five random-seed runs for the $R=5$ model with default initialization. To further examine this instability, we train the $r=5$ model with five different random seeds. As shown in Figure 12, the resulting behaviors vary substantially across seeds. Seed 1 is not affected by latent overthinking, but it also shows no evidence of inference-time scaling by solving harder compositional examples with increased recurrence. Seed 2 is likewise stable, but does exhibit scaling with additional recurrence. Seeds 3, 4, and 5 show varying degrees of inference-time scaling, but also experience performance degradation as recurrence increases, consistent with latent overthinking. ## Appendix F Extrapolation with varying model size and dynamic recurrence We carry out additional experiments to study how extrapolation behavior changes with model size and with training recurrence in our dynamic recurrence setting. In addition to our default 4-layer model, we train larger models with 6 and 8 layers. We also vary the maximum recurrence used during dynamic-recurrence training, considering settings with maximum train-time recurrence of 8, 12, and 16. For these, the recurrence at each training iteration is sampled from a Poisson distribution with means 4, 6, and 8 respectively, with a minimum recurrence of 2 in all cases. <details> <summary>2604.07822v1/x13.png Details</summary>  ### Visual Description ## Generalization ratio vs Model Size ### Overview The image displays two line graphs comparing the generalization ratio against model size for different values of L (1, 4, 6, 8) and Max R (8, 12, 16). The x-axis represents the number of ID hops, while the y-axis represents the generalization ratio. ### Components/Axes - **X-axis**: ID hops, ranging from 2 to 22. - **Y-axis**: Generalization ratio, ranging from 1.0 to 1.8. - **Legend**: - Blue line with circles: L=4 - Red line with squares: L=6 - Green line with triangles: L=8 - Blue line with triangles: Max R=8 - Red line with squares: Max R=12 - Green line with triangles: Max R=16 ### Detailed Analysis - **L=4**: The generalization ratio increases with model size, peaking at Max R=16. - **L=6**: The generalization ratio shows a similar trend to L=4 but with slightly lower peaks. - **L=8**: The generalization ratio is consistently higher than L=4 and L=6 across all model sizes. - **Max R=8**: The generalization ratio increases with model size, peaking at L=8. - **Max R=12**: The generalization ratio shows a similar trend to Max R=8 but with slightly lower peaks. - **Max R=16**: The generalization ratio is consistently higher than Max R=8 and Max R=12 across all model sizes. ### Key Observations - The generalization ratio increases with model size for all values of L and Max R. - The highest generalization ratio is observed at Max R=16 for all values of L. - There is a slight decrease in generalization ratio at Max R=12 compared to Max R=16. ### Interpretation The data suggests that larger models tend to have higher generalization ratios, indicating better performance in terms of generalization. The peak at Max R=16 suggests that this is the optimal model size for the given parameters. The slight decrease at Max R=12 could be due to overfitting or other factors that affect model performance. </details> Figure 13: Generalization ratio with changing model size and train recurrence. To summarize extrapolation under these settings, we plot the generalization ratio, defined as the maximum hop complexity to which a model can generalize with at least 60% accuracy with inference-time scaling, divided by the maximum hop complexity that the model has generalized to during training. This can be viewed as the ratio of maximum OOD generalization to maximum ID generalization. A ratio of 1 indicates no extrapolation beyond the level reached during training, while larger values indicate successful extrapolation to more complex compositions at test time. Figure 13 shows that models initially begin with a ratio close to 1. In particular, when models have only generalized to 2-hop composition during training, they do not yet extrapolate to more complex samples. As training progresses and the models have seen more complex compositions through our curriculum learning setup, the ratio increases. However, across both model-size variations and different maximum train-time recurrence settings, we do not observe a clear or consistent trend indicating that either larger models or larger train-time recurrence systematically improves this ratio. ## Appendix G Results with different random seeds We run our fixed-recurrence models on 2 separate random seed initializations (including the run shown in Figure 5) and with to 40 recurrent iterations at inference time. On both runs, we notice the same general trend of increasing ID and OOD generalization with higher train-time recurrence as well as issues due to latent overthinking (with the sole exception being the model trained with $r=8$ in the second run). The results are presented in Figures 14 & 15. <details> <summary>2604.07822v1/x14.png Details</summary>  ### Visual Description ## Heatmap: Fixed Recurrence Seed 1 ### Overview The image displays a heatmap titled "Fixed Recurrence Seed 1," which appears to be a visualization of data related to recurrent neural networks (RNNs). The heatmap is organized into two rows, each containing four subplots, representing different configurations of the RNN with varying numbers of hops (k) and ID (ID) values. ### Components/Axes - **X-axis**: Labeled "ID/OOD boundary," indicating the threshold between in-distribution (ID) and out-of-distribution (OOD) data. - **Y-axis**: Labeled "Hops (k)," representing the number of hops in the RNN. - **Color Gradient**: The heatmap uses a color gradient ranging from blue to red, with blue indicating lower values and red indicating higher values. - **Legend**: The legend on the right side of the image explains the color coding, with blue representing lower values and red representing higher values. ### Content Details - **Subplots**: Each subplot shows a different configuration of the RNN with varying numbers of hops and ID values. - **Data Points**: The data points are represented by the color intensity in each cell of the heatmap. - **Trends**: The heatmap shows a clear trend where the color intensity increases as the number of hops increases, indicating a higher recurrence rate. ### Key Observations - **ID/OOD Boundary**: The ID/OOD boundary is consistently marked by a dashed green line across all subplots. - **Hops (k)**: The number of hops ranges from 2 to 16, with higher values showing a higher recurrence rate. - **Color Intensity**: The color intensity increases from blue to red, indicating a higher recurrence rate. ### Interpretation The heatmap suggests that as the number of hops in the RNN increases, the recurrence rate also increases. This could indicate that the RNN is more likely to return to a previous state or configuration as the number of hops increases. The ID/OOD boundary is consistently marked, suggesting that the RNN is able to distinguish between in-distribution and out-of-distribution data regardless of the number of hops. The color gradient provides a visual representation of the recurrence rate, with red indicating a higher recurrence rate and blue indicating a lower recurrence rate. </details> Figure 14: Results for Seed 1. <details> <summary>2604.07822v1/x15.png Details</summary>  ### Visual Description ## Heatmap: Fixed Recurrence Seed 2 ### Overview The image displays a heatmap titled "Fixed Recurrence Seed 2," which appears to be a visualization of data related to recurrence rates and hops in a certain context. The heatmap is organized into two rows, each with four subplots, representing different values of "R" (recurrence rate) and "ID" (identifier or ID). The x-axis represents "Hops (k)," and the y-axis represents "Recurrence (t)." The color gradient indicates the intensity of the recurrence rate, with darker shades representing higher recurrence rates. ### Components/Axes - **X-Axis**: Labeled "Hops (k)" with values ranging from 2 to 23. - **Y-Axis**: Labeled "Recurrence (t)" with values ranging from 0 to 1. - **Legend**: Located at the bottom right corner, indicating the color gradient for the recurrence rate. - **Subplots**: Each subplot represents a different combination of "R" and "ID," with the color intensity varying across the "Hops (k)" axis. ### Detailed Analysis - **Subplot 1 (R=1, ID=3-hop)**: The heatmap shows a relatively uniform color intensity across the "Hops (k)" axis, indicating a consistent recurrence rate. - **Subplot 2 (R=2, ID=6-hop)**: The color intensity is slightly higher, suggesting a higher recurrence rate compared to Subplot 1. - **Subplot 3 (R=3, ID=9-hop)**: The color intensity is even higher, indicating a significant increase in recurrence rate. - **Subplot 4 (R=4, ID=10-hop)**: The color intensity is the highest, showing the maximum recurrence rate among the subplots. - **Subplot 5 (R=5, ID=12-hop)**: The color intensity is moderate, indicating a moderate recurrence rate. - **Subplot 6 (R=6, ID=13-hop)**: The color intensity is slightly lower than Subplot 5, suggesting a lower recurrence rate. - **Subplot 7 (R=7, ID=14-hop)**: The color intensity is lower, indicating a further decrease in recurrence rate. - **Subplot 8 (R=8, ID=13-hop)**: The color intensity is the lowest, showing the minimum recurrence rate among the subplots. ### Key Observations - **Trend**: As the value of "R" increases, the recurrence rate generally increases. - **Outliers**: There are no significant outliers in the data, as the color intensity varies smoothly across the "Hops (k)" axis. - **Anomalies**: There are no anomalies in the data, as the color intensity does not show any sudden jumps or drops. ### Interpretation The heatmap suggests that the recurrence rate is influenced by the value of "R" and the identifier "ID." As "R" increases, the recurrence rate also increases, indicating a positive correlation between these two variables. The identifier "ID" appears to have a moderating effect, with some subplots showing a higher recurrence rate for certain IDs compared to others. The color gradient provides a visual representation of the recurrence rate, with darker shades indicating higher recurrence rates. This visualization can be useful for identifying patterns and trends in the data, which can inform further analysis and decision-making. </details> Figure 15: Results for Seed 2. We similarly plot the performance of the dynamic recurrence model across three different seeds and observe a generally high ID generalization and OOD extrapolation. Across all seeds, the dynamic recurrence model is robust to the latent overthinking phenomenon and adaptive halting ( $r^*$ ) works reliably to stop recurrence when not necessary. <details> <summary>2604.07822v1/x16.png Details</summary>  ### Visual Description ## Heatmap: Recurrence and Out-of-Distribution (OOD) Boundary ### Overview The image displays a heatmap that visualizes the recurrence of a specific event or pattern across different hops (k) and seeds (ID). The heatmap is divided into three sections, each representing a different seed with varying hop counts. The color gradient indicates the level of recurrence, with darker shades representing higher recurrence and lighter shades indicating lower recurrence. ### Components/Axes - **X-axis (Hops (k))**: Represents the number of hops, ranging from 2 to 38. - **Y-axis (Recurrence (r))**: Represents the recurrence level, ranging from 0 to 1. - **Legend**: Located at the bottom right, it provides color coding for the recurrence levels and OOD boundary. - **ID/OOD boundary**: A dashed green line that separates the in-distribution (ID) and out-of-distribution (OOD) regions. - **Train recurrence**: A dashed purple line that indicates the threshold for train recurrence. ### Detailed Analysis - **Seed 1 (ID: 22-hop)**: The heatmap shows a high recurrence level, especially at the lower end of the hops (2-8). The recurrence level decreases as the hop count increases. - **Seed 2 (ID: 21-hop)**: Similar to Seed 1, Seed 2 also shows a high recurrence level, particularly at the lower end of the hops (2-8). The recurrence level decreases as the hop count increases. - **Seed 3 (ID: 19-hop)**: Seed 3 has a moderate recurrence level, with a slight increase in recurrence as the hop count increases. ### Key Observations - **High Recurrence**: All three seeds show high recurrence levels, especially at the lower end of the hops. - **ID/OOD Boundary**: The ID/OOD boundary is clearly visible, with the ID region being darker and the OOD region being lighter. - **Train Recurrence**: The train recurrence line is consistently above the ID/OOD boundary, indicating that the model is trained to recognize and distinguish between ID and OOD data. ### Interpretation The heatmap suggests that the model is highly effective in recognizing and distinguishing between in-distribution and out-of-distribution data across different seeds and hop counts. The high recurrence levels indicate that the model is consistently able to identify the pattern or event being measured. The ID/OOD boundary is well-defined, which is crucial for the model's ability to generalize and perform well on unseen data. The train recurrence line being consistently above the boundary further confirms that the model is trained to recognize and differentiate between ID and OOD data, which is essential for its performance in real-world applications. </details> Figure 16: Dynamic recurrence with 3 difference random seed initializations. ## Appendix H Illusion of very deep composition through shortcuts Prior to adopting the permutation-based dataset construction described in Appendix B, we observed what appeared to be very deep compositional generalization. As shown in Figure 17, models trained on ID examples up to 40 hops achieved strong OOD performance even at 80 hops for models with $R=4$ , $R=8$ , and dynamic recurrence. This indicates that the model is able to resolve multiple hops or compositions in a single layer. To inspect this closely, we perform a causal activation-patching analysis. We first select a clean 60-hop test example whose relation sequence ends in a particular suffix, and a second random example of the same hop type. We then run both examples through the model and cache their hidden states. Next, for each token position and each recurrent iteration-layer location (as well as the embedding layer), we replace the hidden state in the clean run with the corresponding hidden state from the random run, and measure the resulting change in the logit margin of the correct final answer. Figure 18 visualizes this change relative to the clean run. <details> <summary>2604.07822v1/x17.png Details</summary>  ### Visual Description ## Heatmap Analysis: Recurrence and Hops ### Overview The image displays three heatmaps, each representing different configurations of recurrence (R=4, R=8, R=dynamic) and hops (k=2, k=4, k=6). The heatmaps are used to visualize the recurrence and hops of a model, with the intensity of the color indicating the level of recurrence or hops. ### Components/Axes - **Recurrence (R)**: The x-axis represents the recurrence level, ranging from 2 to 100. - **Hops (k)**: The y-axis represents the number of hops, ranging from 2 to 100. - **ID/OOD boundary**: A dashed green line indicates the boundary between in-distribution (ID) and out-of-distribution (OOD) data. - **Train recurrence**: A dashed purple line represents the recurrence level of the training data. - **Legend**: The legend on the right side of the image provides color coding for the recurrence and hops levels. ### Detailed Analysis - **R=4**: The heatmap shows a moderate level of recurrence, with the majority of the data points falling within the ID/OOD boundary. The recurrence level is relatively stable across different hops. - **R=8**: The heatmap indicates a higher level of recurrence, with a significant portion of the data points falling outside the ID/OOD boundary. The recurrence level increases with the number of hops. - **R=dynamic**: The heatmap shows a highly dynamic recurrence level, with the majority of the data points falling outside the ID/OOD boundary. The recurrence level fluctuates significantly across different hops. ### Key Observations - **ID/OOD boundary**: The ID/OOD boundary is consistently present in all three heatmaps, indicating that the model's performance is evaluated against a standard distribution. - **Train recurrence**: The train recurrence line is present in all three heatmaps, suggesting that the model's recurrence level is based on the training data. - **Hops**: The number of hops affects the recurrence level, with higher hops generally resulting in higher recurrence levels. ### Interpretation The heatmaps suggest that the model's recurrence level is influenced by both the recurrence level and the number of hops. The ID/OOD boundary indicates that the model's performance is evaluated against a standard distribution, and the train recurrence line suggests that the model's recurrence level is based on the training data. The dynamic recurrence level in the R=dynamic heatmap indicates that the model's performance is highly sensitive to the number of hops, with higher hops resulting in higher recurrence levels. This suggests that the model's performance may be affected by the complexity of the data and the number of hops used in the model. </details> Figure 17: Apparent deep compositional generalization in the pre-permutation dataset. This analysis reveals that the model is not solving the full compositional chain. Instead, the strongest causal effects are concentrated on a short suffix of the relation sequence. The final tail entity can often be inferred from trailing relations alone, without explicitly retrieving the intermediate entities. The model learns a shallow mapping from a suffix of the relation sequence to the answer, rather than performing full multi-hop composition. These observations motivate the permutation-based knowledge graph introduced in Appendix B. Under that construction, each relation acts as a permutation over entities, so the correct final entity cannot be recovered from a short suffix alone, and the model must compose the full sequence of relations to solve the task. <details> <summary>2604.07822v1/x18.png Details</summary>  ### Visual Description ## Heatmap: Change in margin vs. clean ### Overview The heatmap displays the change in margin (Δ) between clean and marginated text. The color gradient represents the magnitude of the change, with red indicating a larger increase in margin and blue indicating a smaller increase or a decrease in margin. ### Components/Axes - **X-axis**: Token position, ranging from 0 to 1000. - **Y-axis**: Patched location (dept), ranging from 0 to 100. - **Legend**: Color scale indicating the magnitude of the change in margin (Δ), with red being the highest and blue being the lowest. ### Detailed Analysis The heatmap shows a clear trend where the margin increases as the token position moves from the beginning to the end of the text. The magnitude of the change varies, with some tokens showing a significant increase in margin and others showing a slight decrease or no change. ### Key Observations - There is a noticeable increase in margin as the token position moves from 0 to 1000. - The magnitude of the change is highest at the beginning of the text (token position 0) and decreases as the token position moves towards the end (token position 1000). - There are some tokens that show a slight decrease in margin, but these are relatively rare. ### Interpretation The data suggests that the margin increases as the token position moves from the beginning to the end of the text. This could indicate that the margin is more significant at the beginning of the text and decreases as the text progresses. The slight decrease in margin for some tokens could be due to the context of the text or the specific characteristics of the tokens. Overall, the data demonstrates a trend where the margin increases as the token position moves from the beginning to the end of the text. </details> Figure 18: Activation-patching analysis on a 60-hop example. Each cell shows the change in logit margin for the correct answer, relative to the clean run, after replacing a single hidden state in the clean example with the corresponding hidden state from a random 60-hop example. Large changes are concentrated towards the end of the relation sequence, indicating shortcut-based prediction rather than genuine multi-hop retrieval.