Parallelizable Neural Turing Machines

Gabriel Faria; Arnaldo Candido Junior

cs.NEFeb 18, 2026

Parallelizable Neural Turing Machines

Authors: Gabriel Faria, Arnaldo Candido Junior

Organizations: University of São Paulo∗ · ∗Instituto de Ciências Matemáticas e de Computação (ICMC), University of São Paulo. · São Paulo State University

Abstract

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.

Figures & tables

Figure 1: Illustration of the NTM architecture. Adapted from Graves et al. (2014) .

Figure 2: Illustration of the parallel computation of P-NTM.

Task	Example Input	Example Output
Parity Check (PC)	$aaabba$	$01000\underline{1}$
Cycle Navigation (CN)	$siidis$	$01212\underline{2}$
Reverse String (RS)	$aabba$	$\underline{abbaa}$
Duplicate String (DS)	$aabba$	$\underline{aabbaaabba}$
Modular Arithmetic (MA)	$1+2-4$	${+}10{+}21{-}43\underline{4}$
Binary Addition (BA)	$01101+101$	$\underline{11011}$

Table 1: Algorithmic tasks with input and output examples. Final answers are underlined. Detailed descriptions of each task are provided in Appendix A .

Architecture	PC	CN	RS	DS	MA	BA
LSTM	0.09	0.04	0.14	0.09	0.06	0.12
minGRU	0.07	0.04	0.09	0.09	0.08	0.10
Transformer	0.27	0.56	0.21	0.65	0.42	0.22
NTM	$\mathbf{1.00}$	$\mathbf{1.00}$	$\mathbf{1.00}$	$\mathbf{1.00}$	$\mathbf{1.00}$	$\mathbf{1.00}$
P-NTM	$\mathbf{1.00}$	$\mathbf{1.00}$	$\mathbf{1.00}$	$\mathbf{1.00}$	$\mathbf{1.00}$	$\mathbf{1.00}$

Table 2: Maximum exact match accuracy scores across runs for each architecture and task on problems of unseen length (

\ell=41

\ell=120

). Perfect scores are highlighted in bold.

Figure 3: Exact match accuracy scores across runs for different architectures and tasks on problems of unseen length (

\ell=41

\ell=120

Figure 4: Speedup of P-NTM sequential and parallel execution relative to the standard NTM execution across input batches of varying sequence lengths.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: High-level structure shared by all evaluated models. An encoder maps input tokens to embeddings, a sequence-processing module transforms them, and a decoder produces vocabulary logits.

Figure 6: Residual block structure used by the minGRU, Transformer, and P-NTM models. Each block applies a sequence-wise sublayer (self-attention, minGRU, or P-NTM layer) over the full sequence, followed by a position-wise feedforward network. Both sublayers use pre-normalization and residual connections. LSTM and NTM architectures do not adopt this structure.

Architecture	Hidden Size	Depth	Heads	Cell Size	Parameters
LSTM	192	—	—	—	$\sim$ 298 K
minGRU	64	5	—	—	$\sim$ 289 K
Transformer (NoPE)	64	5	8	—	$\sim$ 248 K
Transformer (ALiBi)	64	5	8	—	$\sim$ 248 K
Transformer (RoPE)	64	5	8	—	$\sim$ 248 K
Transformer (FIRE)	64	5	8	—	$\sim$ 249 K

Appendix

Table 3: Hyperparameters and parameter counts for all evaluated models. Dashes (—) indicate the hyperparameter is not applicable to that specific architecture.

Pos. Encoding	PC	CN	RS	DS	MA	BA
NoPE	0.16	0.19	0.18	0.24	0.19	0.22
RoPE	0.06	0.07	0.05	0.05	0.04	0.06
ALiBi	0.27	0.56	0.21	0.65	0.38	0.20
FIRE	0.23	0.44	0.19	0.28	0.42	0.19

Appendix

Table 4: Maximum exact match accuracy scores across runs for each task and Transformer positional encoding scheme. Best results boldfaced.

Figure 7: Exact match accuracy across varying input lengths for NTM and P-NTM. Each curve represents a separate run on a specific task, with the shaded area indicating the training distribution (

\ell=1

\ell=40

). While NTM generally maintains non-zero accuracy at extended lengths, P-NTM exhibits a sharp performance degradation, frequently dropping to zero accuracy for longer inputs.

Input Length	NTM	P-NTM (Sequential)	P-NTM (Parallel)
$2^{3}=8$	$0.0011\pm 0.0000$	$0.0007\pm 0.0000$	$0.0003\pm 0.0000$
$2^{4}=16$	$0.0019\pm 0.0001$	$0.0012\pm 0.0000$	$0.0004\pm 0.0000$
$2^{5}=32$	$0.0035\pm 0.0000$	$0.0023\pm 0.0000$	$0.0005\pm 0.0000$
$2^{6}=64$	$0.0068\pm 0.0001$	$0.0043\pm 0.0000$	$0.0006\pm 0.0000$
$2^{7}=128$	$0.0128\pm 0.0000$	$0.0083\pm 0.0000$	$0.0011\pm 0.0001$
$2^{8}=256$	$0.0209\pm 0.0003$	$0.0164\pm 0.0000$	$0.0017\pm 0.0002$

Appendix

Table 5: Mean execution time (

\pm

standard deviation), measured in seconds, across batches of input sequences of varying lengths for NTM and P-NTM. The P-NTM results include both sequential and parallel execution.

Figure 8: Memory interaction patterns of the heads of a trained P-NTM on a parity check sequence. The top row displays write heads , and the bottom row displays read heads . For each head, the upper panel visualizes addressing weights across memory locations over time, while the lower strip shows the read or write vector at each timestep (normalized per head). Write Head 4 and Read Head 4 exhibit the sharpest addressing weights.

Neural Algorithmic Reasoning

Neural algorithmic reasoning studies how neural networks can learn, execute, and generalize algorithmic procedures.

See all 45 papers

Parallel Recursive LSTM
May 16, 2026Tristan Gaudreault, Yongyi MaoRecurrent Neural Networks Language Modeling
School of Electrical Engineering and Computer Science University of Ottawa Ottawa, ON
A PyTorch Library of Turing-Complete Neural Networks
May 3, 2026Jonathan BatesNeural Network Expressivity
Phasor Memory Networks: Stable Backpropagation Through Time for Scalable Explicit Memory
May 13, 2026Sungwoo Goo, Hwi-yeol Yun, Sangkeun JungMemory-Augmented Neural Networks Memory-Augmented Language Models
College of Pharmacy Chungnam National University Daejeon, South Korea · Department of Computer Science & Engineering Chungnam National University Daejeon, South Korea

May 16, 2026J/K move · Enter open · S save

Parallel Recursive LSTM

Tristan Gaudreault, Yongyi Mao

School of Electrical Engineering and Computer Science University of Ottawa Ottawa, ON

Recurrent Neural Networks Language Modeling Long Short-Term Memory Networks

Open paper AskPDF arXiv

Transformers have become the dominant architecture for sequence modeling by using self-attention to enable expressive and highly parallel processing. However, the resulting quadratic time and memory costs limit efficiency in long-context settings. Recurrent models such as LSTMs provide explicit nonlinear state updates and strong state-tracking capabilities, yet their strictly sequential computation limits parallelism. We introduce the Parallel Recursive LSTM (PR-LSTM), a hierarchical recurrent architecture that replaces left-to-right recurrence with recursive nonlinear state composition over a balanced computation tree. Tokens are first mapped independently to latent states, which are then recursively merged by a learned gated composition block. This structure uses the reduction pattern underlying parallel scans as a fixed execution schedule, rather than assuming an associative recurrence. As a result, PR-LSTM retains nonlinear gated state representations while reducing recurrent parallel depth from linear to logarithmic. Empirically, PR-LSTM achieves strong sequence-length generalization on formal-language benchmarks, solving more tasks than standard RNN, LSTM, and Transformer baselines, while avoiding the quadratic scaling of attention. These results suggest that recurrent computation can be reorganized hierarchically to expose parallelism without restricting the transition dynamics to linear or associative forms.

Abstract

Neural Algorithmic Reasoning

Explore similar work

Parallel Recursive LSTM

A PyTorch Library of Turing-Complete Neural Networks

Phasor Memory Networks: Stable Backpropagation Through Time for Scalable Explicit Memory