On Logical Extrapolation for Mazes with Recurrent and Implicit Networks

## Abstract

Abstract Recent work has suggested that certain neural network architectures—particularly recurrent neural networks (RNNs) and implicit neural networks (INNs)— are capable of logical extrapolation . That is, one may train such a network on easy instances of a specific task and then apply it successfully to more difficult instances of the same task.
In this paper, we revisit this idea and show that
(i) The capacity for extrapolation is less robust than previously suggested. Specifically, in the context of a maze-solving task, we show that while INNs (and some RNNs) are capable of generalizing to larger maze instances, they fail to generalize along axes of difficulty other than maze size.
(ii) Models that are explicitly trained to converge to a fixed point (e.g. the INN we test) are likely to do so when extrapolating, while models that are not (e.g. the RNN we test) may exhibit more exotic limiting behaviour such as limit cycles, even when they correctly solve the problem. Our results suggest that (i) further study into why such networks extrapolate easily along certain axes of difficulty yet struggle with others is necessary, and (ii) analyzing the dynamics of extrapolation may yield insights into designing more efficient and interpretable logical extrapolators.

## 1 Introduction

Figure: Figure 1: Three extrapolation dimensions: maze size, percolation, and deadend start. Each shown maze is generated using the indicated parameters. The origin (i.e., maze size $9\times 9$, percolation $p=0$, and deadend_start = True) represents the training distribution. Moving away from the origin corresponds to an out-of-distribution shift. Green denotes the start position.
Refer to caption: x1.png

A hallmark of human learning is the ability to generalize from easy problem instances to harder ones by merely thinking for longer.
In (Schwarzschild et al., ) it is demonstrated that recurrent neural networks (RNNs) are also capable of such logical extrapolation. That is, RNNs that are trained on ‘easy’ instances of a task such as solving small mazes can, in some cases, successfully solve ‘harder’ tasks of the same kind, such as larger mazes.

A pre-requisite for logical extrapolation is the ability of the network to adjust its computational budget to fit the difficulty of the problem at hand. Concretely, this means that the network should be able to vary its number of layers (or iterations). Two classes of network naturally fit this description: weight-tied RNNs and Implicit Neural Networks (INNs), also known as Deep Equilibrium Networks (DEQs) (Bai et al., ; El Ghaoui et al., ; Wu Fung et al., ). Both INNs and RNNs, described further in Section 2, have been considered for logical extrapolation problems (Schwarzschild et al., ; ; Bansal et al., ; Anil et al., ) .

In this work we revisit prior results on logical extrapolation with both RNNs and INNs in the context of a single task: maze-solving (Bansal et al., ; Anil et al., ). While previous studies on logical extrapolation in maze-solving have characterized difficulty as simply a function of maze size, we introduce two new ways in which to vary the difficulty: (i) a binary variable $\texttt{deadend_start}\in\{\texttt{True},\texttt{False}\}$ which, when set to True, constrains the start point to have exactly degree 1, (ii) a percolation constant $p\in[0,1]$ which relates to the likelihood of a maze containing loops. Only for $p=0$ are mazes are guaranteed to be acyclic and thus have unique solutions. We note that in both prior works examining logical extrapolation in maze-solving, $\texttt{deadend_start}=\texttt{True}$ and $p=0$. We show that the models introduced in prior work (Bansal et al., ; Anil et al., ) do not generalize when deadend_start and $p$ are varied, even though they generalize well as maze size is varied. More detail on the maze solving task and the modifications we make is given in Section 3.2.

As our second major contribution, we investigate how RNNs and INNs generalize.
Initially, it was observed that with proper training RNNs converge to a fixed point, even for more difficult task instances such as larger maze sizes (Bansal et al., ).
However, Anil et al. () hints at more complex behaviour, as they find evidence of periodicity in the dynamics of INNs when applied to larger mazes. We quantify this phenomenon using tools from Topological Data Analysis (TDA)(De Silva et al., ; Perea & Harer, ; Tralie & Perea, ). We find that, while the INN we consider (Anil et al., ) consistently converges to a fixed point, regardless of maze size, the RNN we consider (Bansal et al., ) exhibits more complex limiting behaviour. Specifically, for most larger mazes, this RNN converges to either a two-point cycle or two-loop cycle. In order to streamline TDA on INN/RNN architectures, this work also contributes a PyTorch-based (Paszke et al., ) wrapper to Ripser (Bauer, ; Tralie et al., ), a fast Python library for TDA (see Subsection 2.3 and Appendix D for more details). Our code can be found at [https://github.com/mines-opt-ml/maze-extrapolation](https://github.com/mines-opt-ml/maze-extrapolation).

Our results suggest that a network’s ability to extrapolate may depend on the axis along which difficulty is increased; thus, greater caution is needed when using neural networks for extrapolation. We conclude by discussing how the tools introduced for studying periodicity may also be useful in other deep learning contexts.

## 2 Background and Prior Work

### 2.1 Recurrent Neural Networks

A special class of RNNs, namely, weight-tied input-injected networks (or simply weight-tied RNNs), are used in logical extrapolation (Schwarzschild et al., ; Bansal et al., ). For a $K$-layer weight-tied RNN $\mathcal{N}_{\Theta}$, the output is given by

$$ $\mathcal{N}_{\Theta}(d)=P_{\Theta_{2}}(u_{K})\ \text{ where }\ u_{j}=T_{\Theta _{1}}(u_{j-1},d)\ \text{ for $j=1,\ldots,K$.}$ (1) $$

Here, $\Theta_{1}$ and $\Theta_{2}$ are the parameters of the networks $T_{\Theta_{1}}$ and $P_{\Theta_{2}}$ respectively, and $\Theta:=\{\Theta_{1},\Theta_{2}\}$, while $d$ denotes the input features. These networks represent a unique class of architectures that leverage weight sharing across layers to reduce the number of parameters.
The input injection at each layer ensures the network does not ‘forget’ the initial data (Bansal et al., ). In (Bansal et al., ), it is empirically observed that a certain weight-tied RNN extrapolates to larger mazes when applying more iterations. The authors speculate that the reason for this success is that the model has learned to converge to fixed points within its latent space (Section 5, Bansal et al. ()).

### 2.2 Implicit Networks

Drawing motivation from (Bansal et al., ),  (Anil et al., ) propose to use implicit neural networks (INNs) for logical extrapolation tasks.
INNs are a broad class of architectures whose outputs are the fixed points of an operator parameterized by a neural network. That is,

$$ $\mathcal{N}_{\Theta}(d)=P_{\Theta_{2}}(u_{\star})\quad\text{ where }\quad u_{ \star}=T_{\Theta_{1}}(u_{\star},d).$ (2) $$

Here again $\Theta=\{\Theta_{1},\Theta_{2}\}$ refers collectively to the parameters of the networks $T_{\Theta_{1}}$ and $P_{\Theta_{2}}$ and $d$ is the input feature, while $u_{\star}$ represents a fixed point of $T_{\Theta}$. These networks can be interpreted as infinite-depth weight-tied input-injected neural networks (El Ghaoui et al., ; Bai et al., ; Winston & Kolter, ).

Unlike traditional networks, INN outputs are not defined by a fixed number of computations but rather by an implicit condition. INNs have been applied to domains as diverse as image classification (Bai et al., ), inverse problems (Gilton et al., ; Yin et al., ; Liu et al., ; Heaton et al., ; Heaton & Wu Fung, ), optical flow estimation (Bai et al., ), game theory (McKenzie et al., ), and decision-focused learning (McKenzie et al., ). In principle, INNs are naturally suited for logical extrapolation, as they are not defined via an explicit cascade of layers, but rather by an implicit, fixed-point, condition.
This condition can be viewed as specifying when the problem is considered solved. Key to logical extrapolation is that this characterization of “solving a problem” is always the same, regardless of the difficulty of the problem at hand.

### 2.3 Topological Data Analysis in the Latent Space

For both RNNs and INNs, we call $\{u_{j}\}_{j=1}^{K}\subset\mathbb{R}^{n}$ the latent iterates, and $n$ the latent dimension. Note that $n$ can be, and often is, larger than the dimension of the input feature $d$ or network output $\mathcal{N}_{\Theta}(d)$. To characterize the limiting behaviour of the sequence of latent iterates we study its shape. Intuitively, if this sequence exhibits periodic behaviour, it should trace out a loop. More precisely, the sequence should appear as though it was sampled from the topological equivalent of a circle embedded in $\mathbb{R}^{n}$. Topological data analysis (TDA) provides a set of tools for analysing the shape of point clouds, and has been previously applied in other contexts to study periodicity (De Silva et al., ; Perea & Harer, ; Tralie & Perea, ).

As stated in Section 1, we construct a PyTorch wrapper to Ripser (Bauer, ; Tralie et al., ), a fast Python library for TDA (see Appendix D for further details). Ripser computes (persistent) homology groups to identify the most significant topological features of the point cloud. The relevant quantities are the zeroth and first (persistent) Betti numbers, which we denote as $B_{0}$ and $B_{1}$ respectively. These are the “dimensions”(^1^11More formally: these count classes in the zeroth and first homology groups of the Rips complex that persist for large ranges of the length scale.) of the zeroth and first homology groups, and count the respective number of connected components and loops in the data. We identify and interpret three common values of the tuple $[B_{0},B_{1}]$.

- 1.
Convergence to a point ($[B_{0},B_{1}]=[1,0]$). The sequence is clustered around a single point. No loops are present.
- 2.
Two-point cycle ($[B_{0},B_{1}]=[2,0]$) The sequence is clustered around two points, and alternates between them. No loops are present.
- 3.
Two-loop cycle ($[B_{0},B_{1}]=[2,2]$) The sequence lies along two well-separated, thickened loops, and alternates between them.

We emphasize that, while 1. represents the expected convergent behaviour (see Sections 2.1, 2.2) 2. and 3. represent novel, previously undetected limiting behaviour. A more precise overview of TDA is presented in Appendix B.

## 3 Experiments

We study two trained maze-solving models from previous works. The first model is an RNN from Bansal et al. () which we call DT-Net, and the second is an INN from Anil et al. () which we call PI-Net(^2^22This stands for ‘Path-Independent’ net, as path independence is a feature identified in Anil et al. () as being strongly correlated with generalization.). We emphasize that while both works propose multiple models, we focus on the most performant model from each work.

DT-Net uses a progressive loss function to encourage improvements at each RNN layer. In this approach, the recurrent module is run for a random number of iterations, and the resulting output is used as the initial input for the RNN, while gradients from the initial iterations are discarded. The model is then trained to produce the solution after another random number of iterations. We refer the reader to (Bansal et al., , Section 3.2) for additional details. For PI-Net, path-independence (i.e., contractivity) is encouraged in two ways: (i) by using random initialization for half of the batch and zero initialization for the other half, and (ii) by varying the compute budgets/depths of the forward solver during training.

### 3.1 The maze-solving task

In this and previous work (Schwarzschild et al., ; ; Bansal et al., ; Anil et al., ), maze solving problems are encoded as raster images ( Figure 2). Given this RGB input image, the task is to return a black and white image representing the unique path from start (indicated by a green tile) to end (indicated by a red tile). In this work, we consider “accuracy” on a single maze to be $1$ if the solution is exactly correct and 0 0 otherwise. However, instead of using the original “easy to hard” dataset (Schwarzschild et al., ), we use the maze-dataset Python package (Ivanitskiy et al., ). maze-dataset can provide maze-solution pairs in the same format and from the same distribution, but allows modifications to the distribution if desired. The original “easy to hard” dataset only contains acyclic (i.e. percolation parameter $p=0$, any path between two nodes is unique) mazes generated via randomized depth-first search (RDFS) and with start positions having exactly degree 1 (i.e., deadend_start=True). We remove these restrictions to investigate the behavior of the selected models on out-of-distribution mazes in Subsection 3.2. More details on our usage of maze-dataset are given in Appendix A.

Figure: Figure 2: Maze input-solution pairs of size $9\times 9$ (left) and $49\times 49$ (right). Start positions are in green and end positions are in red. Mazes problems/inputs are RGB raster images and solutions are black and white images highlighting the solution path in white.
Refer to caption: x2.png

Figure: Figure 3: Example of maze with a start position that has multiple neighbors (left); example of a percolated maze ($p=0.2$) with loops (right).
Refer to caption: x4.png

### 3.2 Extrapolation

Usage of the maze-dataset package allows us to explore the behavior of DT-Net and PI-Net outside of the training distribution in a direction other than simply maze size. Specifically, in addition to being able to create mazes of any size (Figure 2), we investigate mazes whose start is not restricted to nodes of degree 1 (Figure 3). Furthermore, by setting the percolation parameter $p$ to values $>0$, we can create mazes that may contain cycles, which means that the uniqueness of valid paths or even shortest-path solutions is no longer guaranteed (Figure 3). More detail on maze-dataset and our usage of it is given in Appendix A of the appendix and Subsection 3.1.

Increased Maze Size. We first verify the extrapolation performance of DT-Net and PI-Net with increasing maze size (Bansal et al., ; Anil et al., ). For each maze size $n\times n$, where $n\in\{9,19,29,\ldots,99\}$, we tested each model on 100 mazes. As expected, with sufficient iterations, both models achieve strong performance. See the plots labeled deadend_start=True in Figure 4. Both models achieve perfect accuracy on the $9\times 9$ mazes of the training distribution. Furthermore, with 3,000 iterations, DT-Net achieves perfect accuracy and correctly solved all test mazes. PI-Net achieved near perfect accuracy on smaller mazes, but performance noticeably diminished for mazes larger than $59\times 59$(^3^33Note this does not contradict the experiments in Anil et al. ()) . Importantly, running more iterations usually helps and never harms accuracy. Note that for PI-Net the performance of the model after 1,000 iterations is identical to performance after 3,000 iterations at all tested maze sizes; this indicates that convergence occurred by 1,000 iterations.

Figure: Figure 4: Left: DT-Net extrapolation accuracy (see Subsection 3.1) on a sample of 100 mazes at various maze sizes, with deadend_start=True and deadend_start=False. Right: Analogous results for PI-Net. Both models extrapolate very well to larger maze sizes with sufficient iterations. However, performance diminishes when the start position is allowed to have neighbors, regardless of the number of iterations. See Subsection C.3 for examples of these failures. Note that deadend_start=False does not guarantee that the degree of the start position is $>1$, and mazes still satisfying this condition contribute to some of the performance seen. See Figure 5 for a breakdown of accuracy by start position.
Refer to caption: x6.png

Deadend Start. Allowing the start position to have multiple neighbors, rather than starting at a deadend, represents a different out-of-distribution shift from the training dataset. This shift corresponds to changing deadend_start from True to False, and diminishes the performance of both models. See the plots labeled deadend_start=False in Figure 4. With this shift, accuracy on $9\times 9$ mazes drops from 1.00 to 0.72 for DT-Net and from 1.00 to 0.94 for PI-Net. Interestingly, the fraction of failed predictions remains relatively stable as maze size is increased. There is no clear qualitative difference between mazes that were correctly and incorrectly solved by the models. However, we do observe that accuracy decreases monotonically from 1.0 as the number of start position neighbors increases from 1, a deadend, to 4, the maximum neighbors possible (see Figure 5). See Appendix C.3 for examples of mazes the models fail to solve.

Figure: Figure 5: DT-Net and PI-Net predictions for deadend_start=False maze predictions split by maze size and the number of start position neighbors (from 1, a deadend, to 4, the maximum possible). For both models, accuracy diminishes on mazes with more start position neighbors.
Refer to caption: x11.png

Percolation.
The final out-of-distribution shift we consider is increasing percolation from 0 in the training dataset, to a nonzero value which potentially introduces cycles into the mazes. We reiterate that when percolation equals 0, all mazes are acyclic and hence any path between two nodes is unique. This shift significantly reduces accuracy, as shown in Figure 6, and it highlights the ill-posed nature of solving percolated mazes. The presence of loops creates multiple paths to the goal. Notably, increasing the number of iterations in this setting *does not improve model performance*.
We also observe that the loops introduced by percolation persist during inference with DT-Net, indicating behavior similar to that of the dead-end-filling algorithm (Hendrawan, ).

Figure: Figure 6: Left: Accuracy rapidly diminishes for both models when percolation increases above 0. Both models were iterated 30 times, and the resulting outputs do not change with additional iterations. Right: Both models fail on any maze with a loop, as they always include loops in the prediction.
Refer to caption: x13.png

### 3.3 Latent Dynamics

For both DT-net and PI-net the latent space dimension $n$ is significantly larger than the output space dimension. Consequently, $P_{\Theta_{2}}$ is a projection operator with large-dimensional fibers(^4^44By fiber we are referring to the preimage of any point in the output space under $P_{\Theta_{2}}$.). While prior works emphasize the importance of training a model to reduce loss, i.e. the discrepancy between $\mathcal{N}_{\Theta}(d)$ and the true solution $x^{\star}$, at every iteration (Bansal et al., ; Anil et al., ), there is no incentive for the iterative part of the network $T_{\Theta_{1}}(\cdot,d)$ to prefer one element of the fiber $P^{-1}_{\Theta_{2}}(x^{\star}):=\{u\in\mathbb{R}^{n}:P_{\Theta_{2}}(u)=x^{
\star}\}$ over another. Thus, $T_{\Theta_{1}}(\cdot,d)$ may exhibit more complex dynamics than convergence-to-a-point, while $\mathcal{N}_{\Theta}(d)$ still yields the correct solution.

This possibility is considered for the first time in Anil et al. (), where it is proposed that, in order to solve a particular instance, $T_{\Theta_{1}}(\cdot,d)$ need not have a unique fixed point, but rather need only possess a global attractor. In other words, no matter which initialization $u_{0}$ is selected, the latent iterates exhibit the same asymptotic behaviour. They dub this property “path independence”. In (Anil et al., , App. F, App. G) evidence of instances $d$ where the latent iterates induced by $T_{\Theta_{1}}(\cdot,d)$ form a limit cycle, yet $\mathcal{N}_{\Theta}(d)$ is correct, is provided.

It is therefore both interesting and important to understand the latent dynamics of DT-Net and PI-Net. Building upon Anil et al. (), we introduce several tools for doing so. Most importantly, we use TDA 2.3 to quantitatively study the statistics of the limiting behaviours induced by a pretrained $T_{\Theta_{1}}(\cdot,d)$ as $d$ varies. In our experiments, for both models, we consider 100 mazes at maze sizes $9\times 9$, $19\times 19,\ldots,69\times 69$. We select a “burn-in” parameter $\tilde{K}<K$ and then consider latent iterates $\{u_{j}\}_{j=\tilde{K}}^{K}$ in order to study stable long-term latent behavior. We set $\tilde{K}=3,001$ and $K=3,400$.

Residuals.
(Anil et al., ) considers the residuals $r_{j}:=\|u_{j+1}-u_{j}\|_{2}$, i.e. the distances between consecutive iterates. The one-dimensional sequence of residuals offers a window into the high-dimensional dynamics of the latent iterates. In particular, if $r_{j}=0$ for all sufficiently large $j$ then the $u_{j}$ have converged to a fixed point. (Anil et al., ) finds instances $d$ such that the residual sequence $\{r_{j}\}_{j=\tilde{K}}^{K}$ induced by a variant(^5^55Although not the variant we consider, see Appendix C.1 for further discussion.) of PI-net is visually periodic. We replicate this finding for DT-net (see Figure 7, third panel) and discover a novel asymptotic behaviour of $\{r_{j}\}_{j=\tilde{K}}^{K}$: convergence to a nonzero value (see Figure 7, first panel). To understand the underlying latent dynamics more deeply, a different method is required.

PCA.
Projecting the high-dimensional latent iterates onto their first three principal components reveals the underlying geometry of $\{u_{j}\}_{j=\tilde{K}}^{K}$ responsible for the observed residual sequences $\{r_{j}\}_{j=\tilde{K}}^{K}$. Specifically, the first sequence of latent iterates oscillates between two points (see Figure 7, panel 2), yielding constant values of $r_{j}$ equal to the distance between these points. We call such limiting behaviour a two-point cycle. The second sequence of latent iterates oscillates between two loops (see Figure 7, panel 4), yielding values of $r_{j}$ that oscillate around the distance between these loops. We call such limiting behaviour a two-loop cycle. To the best of our knowledge, neither of these limiting behaviours has been observed previously in the latent dynamics of an RNN or INN.

TDA. Using TDA tools as discussed in Section 2.3, we analyze the frequency with which the aforementioned limiting behaviours occur. This is possible because these limiting behaviours are distinguishable using the persistent Betti numbers (see Section 2.3 and Appendix B) of $\{u_{j}\}_{j=\tilde{K}}^{K}$. Specifically, convergence to a point has $[B_{0},B_{1}]=[1,0]$, a two-point cycle has ($[B_{0},B_{1}]=[2,0]$), and a two-loop cycle ($[B_{0},B_{1}]=[2,2]$).

Table 1 summarizes the TDA results. For PI-Net, every latent sequence converges to a fixed-point. For DT-Net at every maze size the majority of latent sequences approach a two-point cycle, a minority approach a two-loop cycle, and a few approach some other geometry. Interestingly, DT-Net exhibits fixed-point convergence in latent sequences of 17 in-distribution mazes at maze size $9\times 9$.

Figure: Figure 7: Residual plots and corresponding PCA projections for two sequences of DT-Net latent iterates. The left two plots indicate oscillation between two points corresponding to $[B_{0},B_{1}]=[2,0]$ for a $19\times 19$ maze. The right two plots indicate oscillation between two loops corresponding to $[B_{0},B_{1}]=[2,2]$ for a $69\times 69$ maze. Both mazes were solved correctly.
Refer to caption: x16.png

## 4 Discussion

The results of Subsection 3.2 suggest two points warranting further discussion. First, we highlight that seemingly mild distribution shifts (e.g. that induced by toggling deadend_start) can have a large negative effect on model performance, while performance can be unchanged under a seemingly larger distribution shift (e.g. increasing maze size). Secondly, other distribution shifts (e.g. using a nonzero percolation parameter and thus allowing for maze cycles) may make the task, as framed by the training data given to the model, ill-posed. More specifically, both DT-net and PI-net are trained to find the unique path from start to end, but when the maze has even a single loop, there is no longer a unique path. When presented with a maze that does not have a unique solution path, both models fail (see Figure 6 and Appendix Subsection C.3), whereas a human might reasonably reinterpret the task (e.g. “find the shortest path”, or even “find a path”) and solve it.

The results of Subsection 3.3 suggest that the dynamics of RNNs are richer than previously thought, particularly when the latent space is high-dimensional. While Table 1 clearly shows that models trained with path independence (Bansal et al., )
converge to fixed points more frequently, it is unclear how this correlates with (i) overall model accuracy and (ii) robustness towards distributional shifts. If allowing more exotic limiting behaviour (e.g. limit cycles, not just fixed points) is benign, or even desirable, various theoretical results on the convergence and backpropagation of RNNs and INNs (Liao et al., ; Wu Fung et al., ; Ramzi et al., ; ; Bolte et al., ) need to be revisited and adjusted to allow such behaviour. If exotic limiting behaviour is in fact undesirable, further research on interventions promoting path independence Winston & Kolter (); Bansal et al. (), and the ensuing tradeoffs, should be conducted.

**Table 1: Betti number frequencies for DT-Net and PI-Net. PI-Net always exhibits fixed-point convergence ($[B_{0},B_{1}]=[1,0]$) whereas DT-Net usually approach a two-point cycle ($[B_{0},B_{1}]=[2,0]$) or sometimes a two-loop cycle ($[B_{0},B_{1}]=[2,2]$). ^∗ When all latent iterates are contained in a ball of radius $0.01$, we set $[B_{0},B_{1}]=[1,0]$. See Appendix D for further discussion.**
|  |  | $n$ for $n\times n$ maze |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| MODEL | $\mathbf{[B_{0},B_{1}]}$ | $\mathbf{9}$ | $\mathbf{19}$ | $\mathbf{29}$ | $\mathbf{39}$ | $\mathbf{49}$ | $\mathbf{59}$ | $\mathbf{69}$ |
| DT-Net | $[1,0]^{*}$ | 17 | 0 | 0 | 0 | 0 | 0 | 0 |
|  | $[2,0]$ | 75 | 80 | 79 | 74 | 73 | 77 | 86 |
|  | $[2,2]$ | 4 | 18 | 17 | 22 | 25 | 21 | 14 |
|  | Other | 4 | 2 | 4 | 4 | 2 | 2 | 0 |
| PI-Net | $[1,0]^{*}$ | 100 | 100 | 100 | 100 | 100 | 100 | 100 |

The exploration of neural networks’ internal representations in maze-solving scenarios has emerged as a compelling area of study (Mini et al., ; Ivanitskiy et al., ). This research aligns closely with the rapidly expanding field of AI interpretability (Räuker et al., ), which has become increasingly crucial as neural architectures grow in sophistication. Investigations into networks trained on spatial tasks—spanning chess (Karvonen, ; Jenner et al., ; McGrath et al., ), othello (Li et al., ; Nanda, ; He et al., ), graph traversal (Brinkmann et al., ; Momennejad et al., ), and mazes (Mini et al., ; Ivanitskiy et al., )—have provided significant insights into their decision-making processes. Our study of the DT-Net model, with its foundation in chess puzzle training (Bansal et al., ; Schwarzschild et al., ), contributes another valuable perspective to this complex landscape of spatial reasoning research.

Our topological tools could be used to explore how distribution shifts affect the latent dynamics, complementing prior work Liang et al. () which considers this from a non-topological perspective. It would be useful to determine if topological information can be used to detect out-of-distribution examples, analogous to how Sastry & Oore () flags examples with abnormal latent representations using Gram matrices. Finally, we note that the tools developed in this work could be applied to study latent dynamics in other settings, for example data assimilation (Williams et al., ).

##### Limitations.

While this work focuses on the two most performant models from Bansal et al. () and Anil et al. (), considering other models proposed in these works may yield additional insights. Moreover, it would be of interest to consider different dimensions of extrapolation for other tasks considered in the aforementioned works, for example the prefix sum problem or solving chess puzzles Schwarzschild et al. (). We did not do so as it is less clear (to us) how to define, and interpret, such dimensions.

## 5 Conclusion

Using a maze-solving task with out-of-distribution test datasets constructed along different axes (maze size, deadend start, and percolation), we demonstrate that the ability of RNNs or INNs to extrapolate can depend on the type of out-of-distribution shift considered. Specifically, we find that a trained RNN and INN (DT-Net and PI-Net, respectively), can successfully extrapolate maze-solving to larger mazes but are less successful in extrapolating maze-solving to mazes with start positions with multiple neighbors and mazes with loops.

#### Acknowledgments

We thank Ashwini Pokle for providing trained model weights from (Anil et al., ). Samy Wu Fung and Brandon Knutson were supported by National Science Foundation Award DMS-2309810. Michael Ivanitskiy was supported by National Science Foundation Award DMS-2110745.

## Appendix A Additional Maze Dataset Details

Both DT-Net and PI-Net were trained on the same maze dataset (Schwarzschild et al., ) containing $50,000$ mazes of size $9\times 9$, meaning the mazes are subgraphs of the $5\times 5$ lattice. Training mazes were generated via RDFS without percolation, and with the start position being constrained to being at a dead end (exactly $1$ neighbor). We mimic this training distribution and add out-of-distribution shifts using the maze-dataset Python package (Ivanitskiy et al., ).

We first note that for controlling maze size, [maze-dataset.MazeDatasetConfig](https://understanding-search.github.io/maze-dataset/maze_dataset.html#MazeDatasetConfig) takes a parameter [grid_n](https://understanding-search.github.io/maze-dataset/maze_dataset.html#MazeDatasetConfig) which denotes the size of the lattice which the maze is a subgraph of. By contrast, the ‘‘easy to hard’’ (Schwarzschild et al., ) dataset considers an $n\times n$ mean that many blocks in its raster representation. To convert between these two notions of maze size, $n=2\cdot(\texttt{grid_n})-1$.

We can modify the start position constraint in maze-dataset by setting deadend_start=False in [endpoint_kwargs](https://understanding-search.github.io/maze-dataset/maze_dataset.html#MazeDatasetConfig.endpoint_kwargs). When False, the start position is sampled uniformly at random from all valid nodes, while when True the start position is samples uniformly at random from all valid nodes with degree one. Valid nodes are, by default, those not directly matching the end position or directly adjacent to it.

Randomized depth-first search (RDFS) is a standard algorithm for generating mazes, and produces mazes which are spanning trees of the underlying lattice, and thus do not contain cycles. For any acyclic graph with a spanning connected component, there is a unique (non-backtracking) path between any pair of points, and thus solutions are guaranteed to be unique. In our work, we select [LatticeMazeGenerators.gen_dfs_percolation](https://understanding-search.github.io/maze-dataset/maze_dataset.html#LatticeMazeGenerators.gen_dfs_percolation) as the [maze_ctor](https://understanding-search.github.io/maze-dataset/maze_dataset.html#MazeDatasetConfig.maze_ctor) parameter. This function takes an additional variable p in maze_ctor_kwargs, which controls the percolation parameter. This percolation parameter, denoted $p$ in our work, means that the final maze is the result of a logical OR operation on the presence of all possible edges in the maze between an initial maze generated via RDFS and a maze generated via percolation, where each edge is set to exist with probability $p$. This is equivalent to first generating a maze with RDFS and then setting each wall to an edge with proability $p$. Since the initial RDFS maze is a spanning tree, adding any edge will cause the creation of a cycle, thus giving our desired out-of-distribution mazes.

## Appendix B Topological Data Analysis

Topological Data Analysis, or TDA, attempts to produce informative summaries of high dimensional data, typically thought of as point clouds(^6^66By using the term “point cloud” we are implying that the ordering of points does not matter.) $\mathcal{U}=\{u_{1},\ldots,u_{K}\}\subset\mathbb{R}^{n}$, by adapting tools from algebraic topology.

### B.1 Simplicial Complexes

We are interested in TDA tools based on the idea of homology groups (Hatcher, , Chapter 2). Homology groups can be computed algorithmically from a geometric object known as a simplicial complex, which we define below.

###### Definition 1 .

We collect definitions of several relevant concepts related to simplices.

- 1.
A $k$-simplex is the convex hull of any $k+1$ points in $\mathbb{R}^{k}$,
$\displaystyle\sigma$
$\displaystyle:=\mathrm{Conv}\left\{u_{1},\ldots,u_{k+1}\right\}$
(3)
$\displaystyle=\left\{\sum_{i=1}^{k+1}\alpha_{i}u_{i}:\ \alpha_{i}\geq 0\text{
and }\sum_{i=1}^{k+1}\alpha_{i}=1\right\}$
- 2.
A face of a $k$-simplex $\sigma$ is a piece of the boundary of $\sigma$ which is itself a simplex. That is, $\tau$ is a face of $\sigma$ defined in equation 3 if
$\tau=\mathrm{Conv}\left\{u_{i_{1}},\ldots,u_{i_{\ell+1}}\right\}$
- 3.
A simplicial complex $\mathcal{S}$ is a set of simplices, of multiple dimensions, satisfying the following properties
(a)
For all $\sigma\in\mathcal{S}$, all faces of $\sigma$ are also in $\mathcal{S}$.
(b)
If any two $\sigma_{1},\sigma_{2}\in\mathcal{S}$ have non-empty intersection, then $\sigma_{1}\cap\sigma_{2}$ is a face of both $\sigma_{1}$ and $\sigma_{2}$, and consequently $\sigma_{1}\cap\sigma_{2}\in\mathcal{S}$

The process of computing homology groups from a simplicial complex is beyond the scope of this paper. We refer the reader to (Hatcher, , Chapter 2) for further details. It is also possible to define homology groups for abstract simplicial complexes, $\mathcal{R}$, for which a $k$-simplex $\sigma\in\mathcal{R}$ is not literally a convex hull, but merely a list of points:

$$ $\sigma=\{u_{1},\ldots,u_{k+1}\}.$ (4) $$

In this case, a face is just a subset of $\sigma$:

$$ $\tau=\left\{u_{i_{1}},\ldots,u_{i_{\ell+1}}\right\}.$ (5) $$

Note that condition 3 (b) of Definition 1 is now vacuously true.

###### Definition 1 .

### B.2 Homology Groups

Although we have not stated exactly how homology groups are defined, in this section we discuss a few of their properties. Fix a (possibly abstract) simplicial complex $\mathcal{S}$. We shall work with homology groups with coefficients in the field $\mathbb{Z}_{2}:=\mathbb{Z}/2\mathbb{Z}$, hence all homology groups will be vector spaces over $\mathbb{Z}_{2}$. We will focus on the zeroth and first homology groups, denoted $H_{0}(\mathcal{S})$ and $H_{1}(\mathcal{S})$ respectively. Elements in $H_{0}(\mathcal{S})$ are equivalence classes of points, where two points are equivalent if they are in the same path component of $\mathcal{S}$. Elements in $H_{1}(\mathcal{S})$ are equivalence classes of closed loops, where two loops are equivalent if they ‘‘encircle the same hole’’ (Munch, ). Consequently, the dimension of $H_{0}(\mathcal{S})$ (the zeroth Betti number, $B_{0}(\mathcal{S}$) counts the number of path connected components of $\mathcal{S}$, while the the dimension of $H_{1}(\mathcal{S})$ (the first Betti number, $B_{1}(\mathcal{S}$) counts the number of distinct holes in $\mathcal{S}$.

### B.3 The Rips Complex

Given the above, in order to associate Betti numbers to a point cloud we first need to define an appropriate simplicial complex.

###### Definition 2 (The Vietoris-Rips complex) .

Fix a point cloud $\mathcal{U}=\{u_{1},\ldots,u_{K}\}\subset\mathbb{R}^{n}$, and for simplicity assume that $K<n$. Select a distance parameter $\epsilon\geq 0$. We define the simplicial complex $\mathcal{S}_{\epsilon}$, known as the Vietoris-Rips, or simply Rips, complex to contain all simplices

$$ $\sigma=\mathrm{Conv}\left\{u_{i_{1}},\ldots,u_{i_{\ell+1}}\right\},$ (6) $$

satisfying the condition:

$$ $\max_{1\leq m<n\leq\ell+1}\|u_{i_{m}}-u_{i_{n}}\|_{2}\leq\epsilon.$ (7) $$

In words, $\mathcal{S}_{\epsilon}$ contains all simplices on $\mathcal{U}$ with a diameter less than $\epsilon$. We note that $\mathcal{S}_{0}=\mathcal{U}$ and hence $B_{0}(\mathcal{S}_{0})=|\mathcal{U}|$, as every point in $\mathcal{U}$ is its own connected component., while $B_{1}(\mathcal{S}_{0})=0$. On the other end of the scale, when $\epsilon>\mathrm{diam}(\mathcal{U})$, where

$$ $\mathrm{diam}(\mathcal{U})=\max_{1\leq i<j\leq N}\|u_{i}-u_{j}\|_{2},$ (8) $$

the full-dimensional simplex

$$ $\sigma=\mathrm{Conv}\left\{u_{1},\ldots,u_{K}\right\}$ (9) $$

is contained in $\mathcal{S}_{\epsilon}$, and thus $\mathcal{S}_{\epsilon}$ has one connected component and no loops: $B_{0}(\mathcal{S}_{\epsilon})=1$, $B_{1}(\mathcal{S}_{\epsilon})=0$. Consequently, the important topological features of $\mathcal{U}$ are detected by the Rips complex for $\epsilon$ values in $(0,\mathrm{diam}(\mathcal{U}))$.

The condition $K<n$ in 2 may be removed, in which case $\mathcal{S}_{\epsilon}$ is defined as an abstract simplicial complex. This distinction is not relevant for our work.

###### Definition 2 (The Vietoris-Rips complex) .

### B.4 Persistent Betti Numbers

Which value of $\epsilon$ should one choose? As discussed in Munch (), the trick is not to select a particular value of $\epsilon$ but rather focus on features (concretely: equivalence classes in $H_{0}(\mathcal{S}_{\epsilon})$ and $H_{1}(\mathcal{S}_{\epsilon})$) which persist for large ranges of $\epsilon$. More specifically, we define $\epsilon_{b}$, the birth time, to be the value of $\epsilon$ at which a particular equivalence class is first detected in $\mathcal{S}_{\epsilon}$. The death time, $\epsilon_{d}$, is the largest value of $\epsilon$ for which a particular equivalence class is detected in $\mathcal{S}_{\epsilon}$. Fixing a threshold thresh, we say an equivalence class is persistent if $\epsilon_{d}-\epsilon_{b}>\text{\tt thresh}$. We define the persistent zeroth (respectively first) Betti number $B_{0}$ (respectively $B_{1}$) to be the number of distinct equivalence classes appearing in $H_{0}(\mathcal{S}_{\epsilon})$ (respectively $H_{1}(\mathcal{S}_{\epsilon})$) which satisfy $\epsilon_{d}-\epsilon_{b}>\text{\tt thresh}$.

### B.5 Sliding Window Embedding

Finally, we note that Perea & Harer (); Tralie & Perea () propose a more sophisticated method for detecting periodicity using the sliding window embedding, also known as the delay embedding:

$$ $\left\{u_{j}\right\}_{j=1}^{K}\mapsto\left\{SW_{d,\tau}(u_{j}):=\begin{bmatrix }u_{j}\\ u_{j+\tau}\\ \vdots\\ u_{j+d\tau}\end{bmatrix}\right\}_{j=1}^{K-d\tau},$ (10) $$

where $\tau$ (the delay) and $d$ (the window size) are user-specified parameters. Then, persistent Betti numbers are computed for $\{SW_{d,\tau}(u_{j})\}_{j=1}^{K-d\tau}$ instead. This construction is motivated by Taken’s theorem Takens () which, informally speaking, states that the dynamics of $\left\{u_{j}\right\}_{j=1}^{K}$ can be recovered completely from its sliding window embedding, for sufficiently large $d$. Note this comes at a price: the increase in dimension means an increase in computational cost.

In preliminary experiments we found that the persistent Betti numbers for $\{SW_{d,\tau}(u_{j})\}_{j=1}^{K-d\tau}$ did not reveal anything that could not already be inferred from the persistent Betti numbers of $\{u_{j}\}_{j=1}^{K}$. Thus, we chose not to work with the sliding window embedding.

## Appendix C Additional Experimental Details

### C.1 Additional Details on PI-net

During our experiments we determined that there was another model parameter, beyond the number of iterations, that had a strong impact on the accuracy of PI-Net. Specifically, there is a threshold parameter within the forward solver, Broyden’s method, that controls the maximum rank of the inverse Jacobian approximation. Based on code included in the supplementary material for Anil et al. (), it appears the threshold parameter was originally set at 40. However, with this setting PI-Net performed very poorly; it failed on all mazes of size $49\times 49$. Increasing threshold increased the accuracy of PI-Net, but also increases memory costs because it requires storing a number of high-dimensional latent iterates equal to threshold. For our experiments, we used threshold = 1,000 in order to achieve strong accuracy without unreasonable memory requirements.

### C.2 Computational Resources

The experiments in this study were performed on a high-performance workstation with the following specifications:

- •
CPU: AMD Ryzen Threadripper PRO 3955WX (16 cores, 32 threads)
- •
GPU: NVIDIA RTX A6000 (48 GiB VRAM)
–
CUDA Version: 12.5, Driver Version: 555.42.06
- •
Memory: 251 GiB RAM
- •
Operating System: Ubuntu 20.04.6 LTS (x86_64 architecture)

### C.3 Failed Model Predictions

Figure: Figure 8: Examples of $9\times 9$ mazes with deadend_start=False predictions from DT-Net (left) and PI-Net (right), some of which they fail to solve. Note that mistakes are often in the start position cell or cells immediately adjacent to it.
Refer to caption: x20.png

## Appendix D The Ripser Wrapper

In order to apply TDA to the latent iterates $\{u_{j}\}_{j=\tilde{K}}^{K}$ we refactored the code of DT-net and PI-net to add functionality for storing arbitrary contiguous sequences of latent iterates. A number of optimizations were applied to reduce the memory and compute time of computing $B_{0}$ and $B_{1}$:

- 1.
Instead of passing the point cloud $\{u_{j}\}_{j=\tilde{K}}^{K}$ directly to ripser, we project onto the first $K-\tilde{K}$ singular vectors to obtain $\{\tilde{u}_{j}\}_{j=\tilde{K}}^{K}$, as suggested by (Tralie & Perea, ). We then compute the distance matrix $D_{ij}=\|\tilde{u}_{i}-\tilde{u}_{j}\|$ using the package scipy.spatial.distance and pass this to ripser.
- 2.
The SVD computation mentioned above is performed in PyTorch to leverage GPU acceleration.
- 3.
We added the option to use a diagonal convolution trick, also from Tralie & Perea (), to avoid redundant computations when constructing the distance matrix for the sliding window embedding. However, this was not used in our final TDA experiments, as we dropped the sliding window embedding.
- 4.
We use a custom class (see Analysis in utils/tda.py) to handle applying the workflow of 1--3 above to batches of mazes.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: * Have the authors tried reframing the problem to classification instead of segmentation? Say, the authors were to generate a maze classification dataset where the stimuli were either mazes with a solution and mazes without a solution (where the green and red dots are disconnected), would generalization still be hurt in the other dimensions evaluated? Since the authors are only basing their conclusions in one dataset (Maze solving), the presented results may be more compelling when discussed with converging evidence on both settings of the problem.
soundness: 3
strengths: * Logical extrapolation is a key ability of human vision. The authors show that prior work in this area need more exploration and highlight that scaling difficulty in dimensions other than model size hurts the out-of-distribution performance of RNNs and INNs, both of which have been the kind of networks which have shown logical extrapolation. This is a really interesting contribution and warrants the need to further explore this unsolved problem.
* This work includes source code for generating the various difficulty levels of mazes (deadend_start and percolation), this is great and promotes tackling a more holistic solution to logical extrapolation by the community.
* The writing, figures and accompanying captions have sufficient detail and the paper is quite a straightforward read.
summary: In this paper, the authors question the ability of recurrent and implicit neural networks in logical extrapolation. The authors demonstrate that prior approaches to logical extrapolation using RNNs and INNs on maze solving fail when the difficulty scales along dimensions other than maze size (degree of the start of mazes, presence of loops in the maze). Additionally, the authors also present an analysis of the RNN/INN latent dynamics where they highlight key signatures of either model's trajectory in the hidden dimension space.
weaknesses: * **Loose connection between the TDA analysis and lack of logical extrapolation**: It felt to me that the TDA analysis of RNN/INN latent dynamics is disconnected from the issue of logical extrapolation in RNNs and INNs. My biggest feedback to improve this paper further would be to strengthen the connection between these two explorations in the paper's writing as I believe this would greatly help in gleaning the contributions clearly. 
* **Overall framing of the story**: The current writing sounds quite critical of RNN/INNs ability to perform logical extrapolation. These are currently the main class of models from prior art that show (any) extrapolation to greater difficulty settings, and I felt that the writing was potentially overly critical of these model architectures. This is a minor weakness in my opinion, yet I still find it concerning since we don't have another architecture class of neural networks that do a better job at extrapolating to out of distribution settings in solving mazes.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 3
questions: In appendix C.3, it looks like predictions sometimes fail due to lack of exact match between prediction and solution by a few pixels, but not by a whole maze “square”. Does this failure mode occur often in the training data, and how much does this explain additional failures in test?
soundness: 3
strengths: 1. The use of topological data analysis is to study sequences of RNN latents is novel, to my best knowledge.
2. The description of the experimental setup is clear and the main points in the paper are conveyed in a way that is easy to understand.
summary: This paper analyzes the behavior of maze-solving RNNs and INNs. They take models from prior work and evaluate their generalization performance on a dataset that consists of maze problems that are harder than these models’ original training data. Unlike the training data, the test data contains mazes of larger sizes, mazes where the start node is not a dead end, and mazes with cycles. They find that the models studied generalize to larger mazes but not in the latter categories. They also use topological data analysis to study the behavior of the latent data after more RNN/INN iterations.
weaknesses: I believe that the depth of analysis does not meet the bar of an ICLR acceptance. 

This paper can be seen as a paper about generalization or interpretability. When evaluated as a paper about generalization:

1. The paper observes a lack of generalization but does not provide much surprising insight or propose new techniques to improve generalization. I believe the Bansal work already covers the claim about their model generalizing to increased maze size, so the new claims are about deadend-starts and cycles. The explanation for this lack of generalization is simple:

“Both DT-net and PI-net are trained to find the unique path from start to end, but when the maze has even a single loop, there  is no longer a unique path. When presented with a maze that does not have a unique solution path, both models fail (see Figure 3.2 and Appendix Subsection C.3), whereas a human might reasonably reinterpret the task (e.g. “find the shortest path”, or even “find a path”) and solve it.”

The problem setup changes so certain invariants are no longer respected and the problem may no longer be well-defined. That models can fail to generalize under these conditions seems like an intuitive and well-known fact, e.g. https://arxiv.org/abs/2210.01790, https://arxiv.org/abs/2105.14111.

2. The lack of generalization seems specific to the models studied. The authors do not explore whether we can easily correct for this, for instance by training on a small sample of hard data. 

3. The maze dataset itself is not new, so the extent of the analysis is to run previously trained models on an open source dataset.

4. Failure modes are not sufficiently explored.

When evaluated as a paper about interpretability, the analysis is observational, mostly making statements about what the latents look like and doesn’t try to explain why the dynamics occur or what the mechanism is for the model to arrive at periodic latents. It’s well known that latents may only be spuriously correlated with model mechanisms and may not have much meaning on their own, which is why most interpretability work includes causal evidence. For example, it’s possible that the latents are periodic in a direction that isn’t read by the final projection matrix, in which case this finding isn’t very interesting. TDA seems like an intriguing direction but needs to be supplemented with further analysis to see whether it relates to the models’ lack of generalization (though it seems somewhat unrelated, given that the PI-net always converges to a fixed point yet still fails to generalize).

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: More comparison of the model success in different extrapolation directions would be useful. Consider discussing the models in terms of the features the base models have vs what features the different extrapolation directions require. Perhaps:
- Increasing maze size is “more of the same” with the model able to reuse existing features.
- Deadend start = false increases the search space size, eliminating a few initial “forced” moves. A deeper/longer solution path, increases the compute required. Figure 5 reflects this.
- Base models were trained with percolation = 0, and so learnt to find the unique solution. They were not trained to select one path out of several valid paths. So Figure 6 results seem unsurprising. To pick one out of several valid paths (e.g. the shortest) the model would need a feature that distinguishes between valid paths (e.g. measure path length, and prefer minimum path length). To learn this feature likely requires more model training.
soundness: 3
strengths: This is an interesting paper.

Good analysis of two models in 3 extrapolation dimensions. 

Good mathematical analysis of the latents of the models.

Content is well presented.
summary: The authors explores whether a recurrent neural networks (RNN) and a implicit neural networks (INN) exhibits logical extrapolation, finding they do with extrapolate well respect to maze size, but extrapolate less well with respect to dead-end-start and percolation (loop paths). PCA analysis of latents shows 3 distinct modes. Topological Data Analysis (TDA) supports this finding
weaknesses: The paper would benefit from going deeper in a few areas. Refer Questions section

The PCA/TDA finding of one point, two point, two circles is very interesting. Understanding how these modes relate to model performance, algorithm or similar would extend this finding. Without some implications of this finding, it’s hard to say how important this finding is.

Erata:
- Page 5. Text “mazes still satisfying this condition contribute” is ambiguous. Consider using “mazes with a start position degree of 1 contribute” if this is the meaning
- Page 5. “See Figure 3.2 for a breakdown of accuracy by start position” seems incorrect. There are multiple references to this figure that seem incorrect.
- Inconsistent capitalization of DT-Net as DT-net. Ditto PI-Net.
- Page 7. “Table 4” links to Table 1. Check all links.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: What is the significance that the models tested cannot extrapolate well along the new axes of dead-end start and percolation? Can we apply this to other extrapolative tasks?

What is the significance of the convergence dynamics results on this task? Do similar patterns apply to other extrapolative tasks?

Can the authors show theoretical results on the extrapolative abilities of models on this maze task?
soundness: 4
strengths: **Originality**

While the paper considers a task and architecture found in prior works, they conduct new analyses which reveal additional information about the inner mechanics of the model.

**Quality**

Overall, the experiments are thorough and well-conducted. The authors consider a number of ways to both extrapolate the task and analyze the latent dynamics.

**Clarity**

Overall, the paper is well-written and the figures are well-illustrated.

**Significance**

This paper will likely have some significance to researchers studying extrapolation on the specific maze task studied.
summary: This paper studies RNNs and INNs on extrapolative maze-solving tasks. The authors show empirically that prior results on networks do not generalize when the task is made more difficult on a new axis. The authors also study the dynamics of the RNNs and INNs and show that the dynamics either converge to a fixed point or a cycle.
weaknesses: Overall, the paper seems quite similar to prior work on the maze extrapolation task, and the new analyses do not seem very significant. Certainly, the authors show new results, but the broader significance to extrapolative tasks is not clear. I would encourage the authors to consider at least one other extrapolative task. Another way to improve the significance of the paper is to include theoretical results.

Clarity-wise, some text in figures is too small (namely, 2, 3, 4, 5, 6, 7). I encourage the authors to increase figure font size throughout.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 2
questions: The paper would benefit from addressing the identified experimental issues with a proposed solution and performance evaluation, which would enhance the impact of the work. Additionally, careful correction of referencing errors throughout would improve the paper's overall presentation.
soundness: 3
strengths: 1. This work provides evidence that challenges the claims of previous research by setting up new tests where prior work fell short, underscoring the importance of establishing limitations on earlier findings.

2. The paper is well-structured across its five sections, presented with direct and concise wording, making it easy to read and follow.
summary: This paper investigates "logical extrapolation" in previously published neural network models, specifically focusing on Recurrent Neural Networks (RNNs) and Implicit Neural Networks (INNs). Prior authors defined "logical extrapolation" as the model's capacity to add shared-weight layers during testing, enabling it to address more complex problems than those encountered during training. In this work, the authors tackle the challenge of connecting a start and end node within maze-solving tasks. Unlike previous studies that succeeded on extrapolating maze size, this paper demonstrates that top-performing models from prior research struggle to extrapolate when additional complexity arises across different dimensions. For example, slight distribution shifts—such as allowing multiple neighbors for start nodes, or introducing cycles into previously cycle-free mazes—impede the model's ability to extrapolate.

The authors conduct a straightforward yet insightful topological analysis of the network's latent space dynamics, illuminating the underlying behaviors and convergence patterns of these networks. Findings reveal that DT-NET, the highest-performing RNN model, does not converge to a single latent point, whereas PI_NET, the top-performing INN model, does. This dynamic is explored through principal component analysis, residual analysis, and homology grouping, uncovering a complex and partially unexplored latent behavior in DT-NET. Examining network dynamics may lead to more interpretable and robust extrapolation strategies utilizing recurrence.

The paper concludes that the extrapolation capabilities of DT_NET and PI_NET are significantly influenced by the specific axis of complexity introduced. These findings challenge previous assertions about general logical extrapolation and suggest further research into why certain extrapolation dimensions are more manageable for neural networks.
weaknesses: 1. The primary reason for rejection is that the paper does not solve or propose any new solutions; it merely highlights where previous work falls short, without suggesting a new model or method to address the identified issues. In my view, experiments without any novel proposals are insufficient for a conference of this caliber.

2. Testing on only 100 mazes (line 237) appears limited, especially given that prior work typically evaluates on a much larger sample size, often 1,000 to 10,000 mazes. I recommend that the authors consider increasing the test set size to provide more robust insights into model accuracy or provide a justification for why 100 mazes would be adequate for reliable performance assessment in comparison to these larger sample sizes.

3. Figure 7's legends are very small, making them difficult to read. I suggest increasing the font size of the legends to match or be close to the main font size of the paper for improved readability. Additionally, Figures 5 and 6 are not referenced in the text, and Figure 3.2 is misreferenced twice (lines 253 and 258), where Figures 5 and 6 should be referenced instead, please double check all figure references in the text.

4. Figure 5 suggests that only a few mazes were tested with four start neighbors, leading to an imbalanced distribution. I recommend testing more mazes with four start neighbors for a more balanced analysis or explaining why this case is less common or important. Additionally, the y-axis label “probability” is misleading, as it actually represents counts of correct and incorrect instances. A more accurate label, such as “Count” or “Number of Instances,” would improve clarity.

5. Line 355 references Table 4, although it should refer to Table 1, as this is the only table in the paper, please double check all references in the text.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. Generalizability Beyond Maze-Solving: The study currently focuses on maze-solving as a test bed for logical extrapolation. How do the authors view the transferability of their findings to other logical reasoning or extrapolation tasks? Would they consider additional experiments or theoretical discussions on the applicability of their results beyond maze-solving?

2. Choice of TDA for Latent Dynamics Analysis: The use of Topological Data Analysis (TDA) provides unique insights, but could the authors clarify why TDA was chosen over other possible analysis techniques (e.g., standard trajectory or spectral analysis)? Additionally, have the authors considered other types of topological structures that may emerge in the latent space besides fixed points and cycles?

3. Relation Between Latent Dynamics and Model Performance: The paper presents different latent dynamics (e.g., fixed points, cycles), but the connection to model performance remains somewhat abstract. Could the authors elaborate on how these dynamics influence logical extrapolation? For example, are certain behaviors (e.g., two-loop cycles) generally associated with better or worse generalization?

4. Handling of Out-of-Distribution Shifts: The experiments show that both RNNs and INNs struggle with out-of-distribution shifts, such as deadend starts and percolation. Have the authors explored any methods (e.g., fine-tuning, architectural changes) to improve robustness to these shifts? Insights on potential adjustments would be valuable.

5. Explanation of TDA in the Main Text: TDA is an advanced method that may be unfamiliar to some readers. Would the authors consider adding a high-level explanation of TDA, perhaps with intuitive examples, to make the analysis more accessible? This could help readers better understand the significance of Betti numbers and their relation to latent dynamics.

6. Evaluation with Additional Network Architectures: The paper evaluates RNNs and INNs but does not compare them to simpler architectures. Could the authors include results for models like CNNs or MLPs on the same maze tasks? This would clarify how unique RNNs and INNs are in their extrapolation abilities and whether these findings are specific to recurrent or implicit architectures.
soundness: 2
strengths: 1. Originality: The paper introduces new difficulty dimensions for maze-solving (e.g., deadend starts and maze percolation) beyond simple maze size, providing fresh insights into neural network generalization. The use of Topological Data Analysis (TDA) to explore latent space dynamics is also novel in this context and adds an interesting layer to understanding neural networks’ internal behaviors.

2. Quality: The experiments are well-structured, covering a variety of maze configurations. The analysis of latent dynamics using TDA methods, such as Betti numbers, is thorough and demonstrates different behaviors (e.g., fixed points, cycles), adding depth to the results.

3. Clarity: The paper is clear and well-organized, with effective visual aids that support understanding of key results. The explanation of TDA concepts is accessible, which is helpful for readers unfamiliar with this method.

4. Significance: This study highlights the limits of RNNs and INNs in extrapolating maze-solving tasks under varied conditions, offering valuable insights into neural network robustness and generalization. The methods and findings could inspire further research into network behaviors in complex problem-solving tasks.
summary: This paper explores the logical extrapolation capabilities of recurrent neural networks (RNNs) and implicit neural networks (INNs) in the context of maze-solving tasks. The authors investigate whether these network architectures, when trained on simpler instances of a task (e.g., small mazes), can generalize to more complex instances (e.g., larger or differently structured mazes). Their main contributions include:

1. Demonstrating that while both RNNs and INNs can extrapolate to larger mazes, their generalization is less effective when maze complexity increases through factors other than size, such as changes in the starting point configuration or the introduction of cycles.

2. Introducing new difficulty axes, such as a deadend start and percolation parameters, which significantly impact model performance, revealing limits to previous assumptions about logical extrapolation.

3. Providing insights into the latent dynamics of RNNs and INNs through topological data analysis (TDA). The authors observe various limiting behaviors, such as convergence to fixed points or periodic cycles, and suggest these dynamics are essential for understanding the generalization potential of such networks.

Overall, the study underscores the need for careful consideration of difficulty dimensions in neural extrapolation tasks and suggests that topological tools may help improve understanding and robustness of extrapolative models.
weaknesses: 1. Limited Applicability: The study focuses solely on maze-solving tasks, which may limit the generalizability of its findings. To strengthen the paper’s relevance, it would be beneficial to test RNNs and INNs on other logical extrapolation tasks or provide more justification for why maze-solving is a suitable proxy for broader reasoning abilities.

2. Complexity of TDA Analysis: The use of Topological Data Analysis (TDA) adds depth but may be challenging for readers not familiar with these tools. Including a simplified explanation or visual summary in the main text, or moving detailed technical aspects to an appendix, could improve accessibility and help readers better grasp the significance of TDA results.

3. Out-of-Distribution Performance: Although the study introduces new dimensions of difficulty (e.g., deadend starts, percolation), the models show limited ability to generalize effectively in these out-of-distribution scenarios. This indicates that the models may require further improvements or modifications. Exploring architectural adjustments or fine-tuning strategies to enhance generalization across these dimensions could improve the paper’s impact.

4. Interpretation of Latent Dynamics: While the paper presents examples of limiting behaviors (e.g., fixed points, cycles) in latent space, the connection between these dynamics and the models' generalization performance is somewhat limited. Providing a clearer theoretical analysis or practical insights on how these dynamics relate to extrapolation ability would make the findings more actionable and valuable.

5. Evaluation Depth: The evaluation could benefit from more in-depth comparisons with other types of neural networks beyond RNNs and INNs. Testing simpler architectures, such as CNNs or MLPs, on the same maze tasks would help contextualize the benefits and limitations of RNNs and INNs, strengthening claims about their suitability for logical extrapolation.