# On Logical Extrapolation for Mazes with Recurrent and Implicit Networks

arXiv: https://arxiv.org/abs/2410.03020 · HTML: https://mlsanity.com/paper/2410.03020/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 66 references that are in the map.
- First posted on arXiv 3 Oct 2024.

## Builds on (most cited first, 30 of 37)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Emergent World Representations: Exploring a Sequence Model Trained on a Synthetic Task](https://mlsanity.com/paper/2210.13382/) (2022)
- [Multiscale Deep Equilibrium Models](https://mlsanity.com/paper/2006.08656/) (2020)
- [Toward Transparent AI: A Survey on Interpreting the Inner Structures of Deep Neural Networks](https://mlsanity.com/paper/2207.13243/) (2022)
- [Deep Equilibrium Architectures for Inverse Problems in Imaging](https://mlsanity.com/paper/2102.07944/) (2021)
- [Goal Misgeneralization: Why Correct Specifications Aren't Enough For Correct Goals](https://mlsanity.com/paper/2210.01790/) (2022)
- [Implicit Deep Learning](https://mlsanity.com/paper/1908.06315/) (2019)
- [Acquisition of Chess Knowledge in AlphaZero](https://mlsanity.com/paper/2111.09259/) (2021)
- [Ripser: efficient computation of Vietoris-Rips persistence barcodes](https://mlsanity.com/paper/1908.02518/) (2019)
- [Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks](https://mlsanity.com/paper/2106.04537/) (2021)
- [Monotone operator equilibrium networks](https://mlsanity.com/paper/2006.08591/) (2020)
- [JFB: Jacobian-Free Backpropagation for Implicit Networks](https://mlsanity.com/paper/2103.12803/) (2021)
- [Is Attention Better Than Matrix Decomposition?](https://mlsanity.com/paper/2109.04553/) (2021)
- [Evaluating Cognitive Maps and Planning in Large Language Models with CogEval](https://mlsanity.com/paper/2309.15129/) (2023)
- [Reviving and Improving Recurrent Back-Propagation](https://mlsanity.com/paper/1803.06396/) (2018)
- [Deep Equilibrium Optical Flow Estimation](https://mlsanity.com/paper/2204.08442/) (2022)
- [Emergent World Models and Latent Variable Estimation in Chess-Playing Language Models](https://mlsanity.com/paper/2403.15498/) (2024)
- [Measuring Robustness in Deep Learning Based Compressive Sensing](https://mlsanity.com/paper/2102.06103/) (2021)
- [A Mechanistic Analysis of a Transformer Trained on a Symbolic Multi-Step Reasoning Task](https://mlsanity.com/paper/2402.11917/) (2024)
- [The troublesome kernel -- On hallucinations, no free lunches and the accuracy-stability trade-off in inverse problems](https://mlsanity.com/paper/2001.01258/) (2020)
- [Path Independent Equilibrium Models Can Better Exploit Test-Time Computation](https://mlsanity.com/paper/2211.09961/) (2022)
- [Evidence of Learned Look-Ahead in a Chess-Playing Neural Network](https://mlsanity.com/paper/2406.00877/) (2024)
- [Representation Matters: Assessing the Importance of Subgroup Allocations in Training Data](https://mlsanity.com/paper/2103.03399/) (2021)
- [A Configurable Library for Generating and Manipulating Maze Datasets](https://mlsanity.com/paper/2309.10498/) (2023)
- [Dictionary Learning Improves Patch-Free Circuit Discovery in Mechanistic Interpretability: A Case Study on Othello-GPT](https://mlsanity.com/paper/2402.12201/) (2024)
- [One-step differentiation of iterative algorithms](https://mlsanity.com/paper/2305.13768/) (2023)
- [SHINE: SHaring the INverse Estimate from the forward pass for bi-level optimization and implicit models](https://mlsanity.com/paper/2106.00553/) (2021)

## Built on by (most cited first, 7 of 7)

- [Think Shallow, Solve Deep: Controlling Recurrent Dynamics for Reliable Test-Time Depth](https://mlsanity.com/paper/2608.18222/) (2026)
- [A Generalization Bound for a Family of Implicit Networks](https://mlsanity.com/paper/2410.07427/) (2024)
- [Path Channels and Plan Extension Kernels: a Mechanistic Description of Planning in a Sokoban RNN](https://mlsanity.com/paper/2506.10138/) (2025)
- [End-to-End Training of High-Dimensional Optimal Control with Implicit Hamiltonians via Jacobian-Free Backpropagation](https://mlsanity.com/paper/2510.00359/) (2025)
- [On the Convergence of Jacobian-Free Backpropagation for Optimal Control Problems with Implicit Hamiltonians](https://mlsanity.com/paper/2602.00921/) (2026)
- [When Recursive Models Finish Computing](https://mlsanity.com/paper/2609.26487/) (2026)
- [End-to-End Learning of Safe Optimal Feedback Control in High Dimensions with Control Barrier Function Layers](https://mlsanity.com/paper/2607.20674/) (2026)

## Abstract (arXiv)

Recent work suggests that certain neural network architectures -- particularly recurrent neural networks (RNNs) and implicit neural networks (INNs) -- are capable of logical extrapolation. When trained on easy instances of a task, these networks (henceforth: logical extrapolators) can generalize to more difficult instances. Previous research has hypothesized that logical extrapolators do so by learning a scalable, iterative algorithm for the given task which converges to the solution. We examine this idea more closely in the context of a single task: maze solving. By varying test data along multiple axes -- not just maze size -- we show that models introduced in prior work fail in a variety of ways, some expected and others less so. It remains uncertain whether any of these models has truly learned an algorithm. However, we provide evidence that a certain RNN has approximately learned a form of `deadend-filling'. We show that training these models on more diverse data addresses some failure modes but, paradoxically, does not improve logical extrapolation. We also analyze convergence behavior, and show that models explicitly trained to converge to a fixed point are likely to do so when extrapolating, while models that are not may exhibit more exotic limiting behavior such as limit cycles, even when they correctly solve the problem. Our results (i) show that logical extrapolation is not immune to the problem of goal misgeneralization, and (ii) suggest that analyzing the dynamics of extrapolation may yield insights into designing better logical extrapolators.