Reference. On Logical Extrapolation for Mazes with Recurrent and Implicit Networks

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.

Cite

Cite as @knutson-2024-on (helia, typst) · \cite{knutson-2024-on} (LaTeX)
BibTeX
bibtex · 12 lines
@inproceedings{knutson-2024-on,
  author = {Brandon Knutson and Amandin Chyba Rabeendran and Michael Ivanitskiy and Jordan Pettyjohn and Cecilia Diniz Behn and Samy Wu Fung and Daniel McKenzie},
  title = {On Logical Extrapolation for Mazes with Recurrent and Implicit Networks},
  booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence},
  publisher = {Association for the Advancement of Artificial Intelligence (AAAI)},
  year = {2026},
  month = {3},
  volume = {40},
  number = {27},
  pages = {22635--22643},
  doi = {10.1609/aaai.v40i27.39424}
}
hayagriva YAML (typst)
yaml · 21 lines
knutson-2024-on:
  type: article
  title: On Logical Extrapolation for Mazes with Recurrent and Implicit Networks
  author:
  - Knutson, Brandon
  - Rabeendran, Amandin Chyba
  - Ivanitskiy, Michael
  - Pettyjohn, Jordan
  - Behn, Cecilia Diniz
  - Fung, Samy Wu
  - McKenzie, Daniel
  date: 2026-03
  page-range: 22635-22643
  serial-number:
    doi: 10.1609/aaai.v40i27.39424
  parent:
    type: proceedings
    title: Proceedings of the AAAI Conference on Artificial Intelligence
    publisher: Association for the Advancement of Artificial Intelligence (AAAI)
    issue: 27
    volume: 40
Cited by (1)

maze-dataset: Maze Generation with Algorithmic Variety and Representational Flexibility ivanitskiy-2025-maze

DOI
Cites 43 works (1 here)
With notes (1)

A Configurable Library for Generating and Manipulating Maze Datasets ivanitskiy-2023-a

Understanding how machine learning models respond to distributional shifts is a key research challenge. Mazes serve as an excellent testbed due to varied generation algorithms offering a nuanced platform to simulate both subtle and pronounced distributional shifts. To enable systematic investigations of model behavior on out-of-distribution data, we present 𝚖𝚊𝚣𝚎-𝚍𝚊𝚝𝚊𝚜𝚎𝚝, a comprehensive library for generating, processing, and visualizing datasets consisting of maze-solving tasks. With this library, researchers can easily create datasets, having extensive control over the generation algorithm used, the parameters fed to the algorithm of choice, and the filters that generated mazes must satisfy. Furthermore, it supports multiple output formats, including rasterized and text-based, catering to convolutional neural networks and autoregressive transformer models. These formats, along with tools for visualizing and converting between them, ensure versatility and adaptability in research applications.
arXiv
External (42)
knutson-2024-on reference entries/refs/knutson-2024-on/knutson-2024-on.hel