Source-linked AI summary
Neural Random-Access Machines
Karol Kurach, Marcin Andrychowicz, Ilya Sutskever
TL;DR
The paper addresses how neural networks can learn algorithmic tasks requiring explicit pointer manipulation and dereferencing. It introduces NRAM, a differentiable neural controller with variable-size random-access memory, and finds that it solves such tasks and generalizes beyond training lengths, despite unstable optimization.
Problem
The paper investigates how neural networks can learn algorithmic problems requiring explicit pointer manipulation and dereferencing.
Method
NRAM uses a neural controller trained by backpropagation to manipulate probabilistic registers and interact with variable-size external memory.
Results
NRAM learned algorithmic problems involving pointer manipulation, including linked-lists and binary trees, and generalized to inputs longer than those seen during training.
Takeaways & Limitations
For some problems, the learned solutions generalize to inputs of arbitrary length.
Takeaways & Limitations
Training is unstable: with the best hyperparameters, about 11% of random seeds usually converged to error 0, versus about 1% without gradient noise.
Abstract
from arXiv · showhide
In this paper, we propose and investigate a new neural network architecture called Neural Random Access Machine. It can manipulate and dereference pointers to an external variable-size random-access memory. The model is trained from pure input-output examples using backpropagation. We evaluate the new model on a number of simple algorithmic tasks whose solutions require pointer manipulation and dereferencing. Our results show that the proposed model can learn to solve algorithmic tasks of such type and is capable of operating on simple data structures like linked-lists and binary trees. For easier tasks, the learned solutions generalize to sequences of arbitrary length. Moreover, memory access during inference can be done in a constant time under some assumptions.
1 INTRODUCTION
The paper introduces NRAM to make pointer manipulation and dereferencing primitive neural operations, enabling learning of algorithmic tasks that require pointer chasing. It tests this architecture on linked-list and binary-tree problems, while finding optimization challenging for deep nonlinear models.
- NRAM provides primitive operations for manipulating, storing, and dereferencing pointers in working memory.
- Its pointer primitives target problems whose solutions require explicit pointer manipulation and chasing.
- The experiments evaluate NRAM on algorithmic problems involving linked-lists and binary trees.
- Standard optimization algorithms struggle with the extremely deep and nonlinear models used in these tasks.
2 RELATED WORK
Related work established trainable neural architectures for learning algorithms, explicit memory, and algorithmic computation. These models differ in their memory capabilities and demonstrated tasks, ranging from stacks and attention to writable or absent memory.
- Neural Turing Machines introduced training computationally universal neural networks and achieved encouraging results.
- Stack-Augmented RNNs demonstrated generalization from short problem instances to long ones.
- Memory networks explicitly separated memory from computation, while later work combined them with soft attention for less-supervised training.
- Grid-LSTM supported both deep and sequential computation and achieved strong results on synthetic algorithmic and real tasks.
- Pointer Networks solved algorithmic problems without a writable memory, including convex hull and approximate 2D travelling salesman tasks.
- Attention models provided a practical algorithmic architecture with broad applications including translation, speech recognition, and parsing.
3 MODEL
NRAM uses a neural controller to construct differentiable fuzzy circuits over probabilistic registers, then extends this mechanism with variable-size random-access memory. Its READ and WRITE modules support fuzzy pointer dereferencing and memory updates, while a learned stopping rule determines the output timestep.
- The NRAM controller is the only trainable component and may be implemented as a feedforward network or an LSTM.
- Each register stores a probability distribution over integer values, and prespecified modules such as addition and equality operate on registers.
- At each timestep, the controller receives register-derived inputs, updates its state if recurrent, and outputs a fuzzy circuit.
- Register values are overwritten with controller-selected weighted combinations of registers and module outputs.
- The controller selects weighted averages of registers and prior module outputs as module inputs using softmax weights.
- The controller receives only P(r_i = 0) from each register, avoiding parameter dependence on memory size and forcing reliance on modules.
- A variable-size tape provides fuzzy pointers, with READ retrieving the value under a pointer and WRITE storing a value at that address.
- The memory is both input-output storage and an execution workspace, while the controller probabilistically chooses when to finish, with a forced final timestep.
4 EXPERIMENTS
The experiments test differentiable pointer manipulation on algorithmic memory tasks, showing strong performance on easier problems but unstable optimization and weaker discretization on harder ones.
- Training: The NRAM is trained from pure input-output examples with Adam and negative log-likelihood, without supervised memory-access traces.
- Training: Training uses curriculum learning, gradient clipping, gradient noise, and probability-distribution renormalization to stabilize very deep executions.The unfolded computation can exceed hundreds of layers, causing exploding gradients and numerical errors.
- Evaluation: The evaluation writes task outputs to an external memory tape and computes error over the cells that should be modified.Continuous memory states are discretized by selecting the highest-probability value in each cell before comparison.
- Results: The model achieved error 0 on all tasks except Merge and WalkBST, whose errors were ≤1%.The metric is computed after discretizing the model’s continuous memory state.
- Easy tasks: Easy tasks generalized perfectly across longer sequences, different memory sizes, allowed timesteps, and discretized inference; Copy and Increment were verified for arbitrary-length inputs under suitable timesteps.
- Hard tasks: Hard tasks required extensive hyperparameter search: Permutation, ListK, and ListSearch reached error 0, while Merge and WalkBST had training errors of 1% and 0.3%.Permutation, ListK, and WalkBST generalized well to inputs at least twice as long as those used in training.
- Hard tasks: Discretization matched the continuous model for Permutation but produced error rates ≥70% on the other four hard problems.The authors suggest encouraging discretization during training as a possible improvement.
- Limitations: Optimization remained unstable: errors could rise to 70% in one epoch, and about 11% of random seeds typically converged to error 0.Without gradient noise, only about 1% of seeds converged.
5 CONCLUSIONS
The NRAM learns algorithmic problems requiring explicit pointer manipulation and dereferencing, with generalization beyond training inputs. However, standard optimization methods struggle with the resulting deep backpropagation problem.
- NRAM learns to solve problems requiring explicit manipulation and dereferencing of pointers.
- The model solves algorithmic problems and generalizes well to inputs longer than those seen during training.
- For some problems, the learned solutions generalize to inputs of arbitrary length.
- Standard optimization techniques find the backpropagation problem through execution traces very challenging.The authors suggest searching in an easier abstract space may be more effective.
A DETAILED TASKS DESCRIPTIONS
The task suite tests memory transformations, pointer-based array operations, and traversal of linked lists and binary trees. Inputs and outputs are represented directly in variable-size memory, with NULL marking boundaries or missing elements.
- Representation: NULL is represented by 0 and marks the end of arrays or a missing next element in lists and binary trees.
- Array tasks: Access returns A[k] by replacing the first memory cell with the indexed array value.
- Array tasks: Increment adds 1 to every array element, while Copy and Reverse write arrays to a pointer-specified destination.
- Array tasks: Swap exchanges two pointer-indexed array elements, and Permutation rearranges A according to the permutation array P.
- Linked-list tasks: ListK follows linked-list pointers for k hops to return an element, while ListSearch returns a pointer to the first node containing a target value.
- Structured-data tasks: Merge combines two sorted arrays into one sorted output using pointers to both inputs and the destination.
- Structured-data tasks: WalkBST follows a binary-search-tree path from a root pointer through randomly placed node triples to return the reached element.
B DETAILS OF CURRICULUM TRAINING
Training uses curriculum learning: examples are sampled around a progressively increasing difficulty level, while retaining access to all difficulty values. The training procedure also includes task-specific circuit conventions and sampling details.
- Curriculum schedule: Difficulty increases whenever the model’s error falls below a threshold, with successive increases separated by batches.
- Difficulty sampling: Each example first samples a difficulty d from a distribution determined by the current level D.
- Difficulty sampling: Sampling uses probabilities of 10%, 25%, and 65% for broad random, bounded, and level-based difficulty choices.
- Curriculum schedule: The procedure guarantees that every difficulty can be selected regardless of the current curriculum level.
- Circuit generation: For most tasks, timestep 1 uses a distinct initialization circuit, while later timesteps reuse the same main circuit.
C.1 ACCESS
The Access figure presents the circuit generated after initialization, while its memory table indicates that only the first cell is modified.
- The Access circuit shown is the circuit generated at every timestep ≥2.
- The Access memory table indicates that only the first memory cell is modified.
C.2 INCREMENT
The Increment task is documented through its per-timestep generated circuit and corresponding memory table.
- Figure 6 depicts the circuit generated at every timestep for Increment.
- Together, the section records both the generated computation and memory usage for Increment.
- Table 4 reports memory information for the Increment task.
C.3 REVERSE
The Reverse task is documented through a circuit generated from timestep 2 onward and a corresponding memory table.
- Figure 7 depicts the circuit generated at every timestep ≥2 for Reverse.
- Together, the section records Reverse’s generated computation and memory usage.
- Table 5 reports memory information for the Reverse task.
C.4 SWAP
The Swap task uses two different circuits: one at even timesteps and another at odd timesteps from timestep 3 onward, alongside a memory table.
- 2 different circuits are generated for Swap: one for even timesteps and one for odd timesteps.
- Figure 8 depicts the circuit generated at every even timestep for Swap.
- Figure 9 depicts the circuit generated at every odd timestep ≥3 for Swap.
- Table 6 reports memory information for the Swap task.