Parallelizable Neural Turing Machines

We introduce a parallelizable simplification of Neural Turing Machine (NTM), referred to as P-NTM, which redesigns the core operations of the original architecture to enable efficient scan-based parallel execution. We evaluate the proposed architecture on a synthetic benchmark of algorithmic problems involving state tracking, memorization, and basic arithmetic, solved via autoregressive decoding. We compare it against a revisited stable implementation of the standard NTM, as well as conventional recurrent and attention-based architectures. Results show that, despite its simplifications, the proposed model attains length generalization performance comparable to the original, learning to solve all problems, including unseen sequence lengths, with perfect accuracy. It also improves training efficiency, with parallel execution of P-NTM being up to an order of magnitude faster than the standard NTM. Ultimately, this work contributes toward the development of efficient neural architectures capable of expressing a broad class of algorithms.

• Publication year

  2026

• Venue

  Unknown venue

• Publication date

  2026-02-18

• Fields of study

  Computer Science

• Identifiers
  arXiv 2602.18508
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products

  2025cited by this paper
• Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers

  2025cited by this paper
• Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization

  2025cited by this paper
• Softmax Transformers are Turing-Complete

  2025cited by this paper
• Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues

  2024cited by this paper
• Autoregressive Large Language Models are Computationally Universal

  2024cited by this paper
• Were RNNs All We Needed?

  2024influential reference
• Parallelizing Linear Transformers with the Delta Rule over Sequence Length

  2024cited by this paper
• Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality

  2024cited by this paper
• The Expressive Capacity of State Space Models: A Formal Language Perspective

  2024cited by this paper
• DAPE: Data-Adaptive Positional Encoding for Length Extrapolation

  2024cited by this paper
• The Illusion of State in State-Space Models

  2024cited by this paper
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems

  2024cited by this paper
• Functional Interpolation for Relative Positions Improves Long Context Transformers

  2024cited by this paper
• Titans: Learning to Memorize at Test Time

  2024cited by this paper
• Gated Delta Networks: Improving Mamba2 with Delta Rule

  2024cited by this paper
• Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective

  2023cited by this paper
• A provably stable neural network Turing Machine with finite precision and time

  2023cited by this paper
• Efficient Parallelization of a Ubiquitous Sequential Computation

  2023cited by this paper
• Resurrecting Recurrent Neural Networks for Long Sequences

  2023cited by this paper
• On the Parameterization and Initialization of Diagonal State Space Models

  2022cited by this paper
• Simplified State Space Layers for Sequence Modeling

  2022cited by this paper
• The Parallelism Tradeoff: Limitations of Log-Precision Transformers

  2022cited by this paper
• Neural Networks and the Chomsky Hierarchy

  2022cited by this paper
• Efficiently Modeling Long Sequences with Structured State Spaces

  2021cited by this paper
• RoFormer: Enhanced Transformer with Rotary Position Embedding

  2021cited by this paper
• Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation

  2021cited by this paper
• Example

  2020cited by this paper
• HiPPO: Recurrent Memory with Optimal Polynomial Projections

  2020cited by this paper
• Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages

  2019cited by this paper
• Implementing Neural Turing Machines

  2018cited by this paper
• On the Practical Computational Power of Finite Precision RNNs for Language Recognition

  2018cited by this paper
• Parallelizing Linear Recurrent Neural Nets Over Sequence Length

  2017cited by this paper
• Attention is All you Need

  2017cited by this paper
• Simple Recurrent Units for Highly Parallelizable Recurrence

  2017cited by this paper
• Quasi-Recurrent Neural Networks

  2016cited by this paper
• Hybrid computing using a neural network with dynamic external memory

  2016cited by this paper
• Dynamic Neural Turing Machine with Soft and Hard Addressing Schemes

  2016cited by this paper
• Neural GPUs Learn Algorithms

  2015cited by this paper
• Learning to Transduce with Unbounded Memory

  2015cited by this paper
• Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets

  2015cited by this paper
• Neural Turing Machines

  2014influential reference
• On the Properties of Neural Machine Translation: Encoder–Decoder Approaches

  2014influential reference
• Adam: A Method for Stochastic Optimization

  2014cited by this paper
• Discrete Time Signal Processing

  2004cited by this paper
• Long Short-Term Memory

  1997influential reference
• RECURRENT NEURAL NETWORKS AND FINITE AUTOMATA

  1996cited by this paper
• Bounds on the complexity of recurrent neural network implementations of finite state machines

  1993cited by this paper
• Learning Context-free Grammars: Capabilities and Limitations of a Recurrent Neural Network with an External Stack Memory (cid:3)

  1992cited by this paper
• Prefix sums and their applications

  1990cited by this paper

• No citing papers are available for this paper.