Neural Turing Machines

A recurrent neural network carries one vector from step to step, its hidden state. That vector is both the place where the network computes and the only place where it can keep anything. Even the LSTM, whose gates protect information over long spans, still packs everything into a fixed number of units. Ask it to repeat back a sequence twice as long as any it trained on, and there is simply nowhere to put the extra items.

The authors frame the gap in terms borrowed from psychology and linguistics. Humans solve short tasks with working memory, a small store whose contents are manipulated by rules. Critics of neural networks had long argued that they cannot do variable binding: assigning a value to a slot and retrieving it later by name. And although recurrent networks are known to be Turing complete in principle, that is a statement about what they can represent, not about what gradient descent can teach them.

A conventional computer escapes these limits with an addressable memory, separate from the processor. The paper's question is whether a network can be given the same kind of memory without giving up the thing that makes networks trainable: every operation must pass a gradient.

A Neural Turing Machine has two parts. The controller is an ordinary network, either an LSTM or a feedforward net, that receives the input and produces the output at each time step. Beside it sits a memory matrix of N rows, each a vector of M numbers; in every experiment in the paper, N is 128 and M is 20. The controller never touches the memory directly. It talks to it through read and write heads, small output layers that decide where to read or write and what to write.

The name borrows from Turing's machine, a controller moving a head along a tape, but the resemblance stops at the layout. A Turing machine's head sits on exactly one cell. An NTM head produces a weighting over all N rows, a vector of non-negative numbers that sums to one. The authors call the resulting operations "blurry": every read and every write touches every location, some a lot and most almost not at all.

That blurriness is not a weakness to be engineered away. It is what makes the design work, and the next two sections show why.

Reading is the simple half. Given the head's weighting w over the N locations, the read vector is a weighted sum of the memory rows: $r = \sum_i w(i)\, M(i)$. If the weighting is concentrated on one row, the read returns that row almost exactly. If it is spread across three rows, the read returns a blend of them.

Writing takes two steps, and the authors say they were inspired by the input and forget gates of the LSTM. First, each row is partly erased: an erase vector e, with entries between 0 and 1, says which components to clear, and the weighting says how strongly each row is affected. Then an add vector a is written in, scaled by the same weighting. A row with weight 1 and an erase vector of all ones is fully replaced. A row with weight zero is left untouched. Everything in between is a partial blend.

Because erasing and adding are both multiplications and sums, the result is differentiable with respect to the weighting, the erase vector, the add vector and the old memory. When several write heads are active, the order in which their additions are applied does not matter.

It would be simpler to let each head pick one memory row, the way a computer reads one address. That is hard attention, and it breaks training. If the head always reads the single best-matching row, then moving the key slightly usually changes nothing at all, and the gradient with respect to the key is exactly zero. When the choice finally flips to another row, the output jumps. Gradient descent gets no signal on the flat stretches and an undefined one at the jumps.

Soft attention replaces the choice with a smooth weighting. Moving the key slightly now shifts a little weight from one row to its rivals, the read vector changes a little, and every row with non-zero weight receives some gradient. The whole machine, controller and memory together, can then be trained by backpropagation through time, which is the end-to-end training the paper aims for.

The price is that every read and write touches all N locations, so each step costs time proportional to the size of memory. The paper accepts that price in exchange for a memory that can be learned.

So far the weighting has simply been given. Producing it is the paper's main technical contribution, and it starts with content-based addressing. The head emits a key vector k and compares it with every memory row using cosine similarity. A softmax turns those similarities into a weighting, so rows that resemble the key get more weight. This is the idea behind content-addressable memory, and behind the Hopfield network: you find a memory by describing what is in it.

A second number, the key strength β, controls how picky the lookup is. With β near zero the weighting is almost uniform, and every row is a candidate. With a large β it concentrates on the single best match.

Content alone is not enough, and the authors say why. Some tasks need a location whose contents are arbitrary but whose position is known: the next slot after the one just written, or the start of a list. For the variables in a computation like x × y, the values can be anything; what the program knows is where it put them. That is the job of the second half of the pipeline.

Location-based addressing takes the content weighting and moves it, in three steps. First, an interpolation gate g between 0 and 1 blends it with the weighting the head used on the previous step. With g = 1 the key decides; with g = 0 the key is ignored and the head starts from wherever it was.

Second, a shift weighting s rotates the result. In the paper's experiments s is a distribution over shifts of −1, 0 and +1, and the rotation is a circular convolution, so the last row wraps around to the first. A soft shift has a side effect the authors point out: weights of 0.1, 0.8 and 0.1 turn a focus on one row into a focus blurred over three. Repeat that on every step and the focus would spread out until it covered everything. The third step, sharpening, prevents this: every weight is raised to a power γ ≥ 1 and the result renormalised, which pushes weight back toward the peak.

Together the stages give three ways of using memory, which the paper lists. The head can jump to a row by content alone. It can find a row by content and then step to its neighbour, which reaches a location next to a known one. Or it can ignore content and keep stepping from its last position, which is exactly a tape head iterating through memory.

The controller can be an LSTM or a feedforward network, and the paper tests both. An LSTM controller has its own internal memory, which the authors compare to the registers of a processor: it can keep earlier read vectors in its state and combine them with new ones. A feedforward controller has no state. It can still act like a recurrent network by reading and writing the same memory location on every step, and its behaviour is easier to interpret, since everything it remembers is visible in memory.

The cost is a bottleneck on the number of heads. With one read head a feedforward controller can combine only one memory vector per step; two heads allow operations on pairs, and so on. The parameter tables show this directly. For copy, repeat copy and N-grams both controllers use a single head. For associative recall the feedforward NTM uses four heads and 256 units against the LSTM version's one head and 100 units. For priority sort it is eight heads and 512 units against five heads and two layers of 100. The authors note that eight parallel heads were needed for the feedforward controller to reach its best result on sorting, which may reflect how hard sorting is with only one-vector-at-a-time operations.

Five tasks probe different uses of memory: copy (store a sequence and repeat it), repeat copy (repeat it a given number of times), associative recall (return the item that followed a query item), dynamic N-grams (predict the next bit of a sequence with shifting statistics) and priority sort (return vectors in order of a priority). Each NTM is compared with a three-layer LSTM baseline. Memory is 128 × 20 in every NTM, and shifts are limited to −1, 0 and +1.

Training uses RMSProp with momentum 0.9, and every gradient component is clipped to the range −10 to 10 (gradient clipping). The NTMs are much smaller than the baselines: 17,162 parameters for the feedforward NTM on copy, against 1,352,969 for the LSTM, and never more than 508,305 on any task.

The key measurement is length generalization. The models are trained on short sequences and then tested on longer ones. A network that has memorised patterns should fail once the sequence length leaves the training range. A network that has learned a procedure should keep working.

In the copy task the network sees a sequence of random 8-bit vectors, followed by a delimiter, and must then output the same sequence. During training the length is between 1 and 20. At test time the authors push it to 30, 50 and 120.

The LSTM copies well inside the training range and falls apart soon after it. Its errors pile up toward the end of the sequence, as if it had run out of room. The NTM keeps copying. At 120, six times the longest training sequence, it makes a few local errors and one global error: a single vector is duplicated, and everything after it comes out one step late. The authors point to the memory size (128 locations) as the limiting factor at that length.

The head weightings show why the NTM generalizes. During the input phase the write head moves forward one location per step; during the output phase the read head retraces the same locations in the same order. The authors write this down as a short program, shown below.

Repeat copy adds a counter. The network receives a sequence and a number, and must output the sequence that many times and then emit an end marker. Both the length and the number of repeats were drawn between 1 and 10 during training. The NTM learns the task much faster than the LSTM, although both solve it in the end.

The generalization test shows exactly what was learned. With longer sequences and more than ten repeats, the NTM keeps reproducing the sequence fairly accurately, so the copying loop generalized. It does not keep count. It emits the end marker after every repetition beyond the eleventh. The authors suggest this is probably because the network represents the number of repetitions numerically, and such a representation does not easily extend beyond a fixed range. The copying generalized; the counting did not.

Associative recall tests a pointer-like use of memory. The network sees a list of items, each made of three 6-bit vectors, then one of those items again as a query, and must output the item that came after it. Training used between 2 and 6 items.

The feedforward NTM learns this fastest of all, faster even than the NTM with an LSTM controller. It is nearly perfect up to 12 items, twice the training maximum, and still averages less than one wrong bit per sequence at 15. The LSTM had not reached zero cost at the end of its training. The authors' analysis of the heads shows the strategy: the NTM writes a compressed representation of each item to consecutive locations. When the query arrives, it finds the query's location with a content lookup, then shifts forward by one and reads the next item. This is associative memory built from the two addressing modes working together.

Dynamic N-grams test whether memory can hold statistics rather than items. Each training sequence is 200 bits long, generated by a 6-gram model: the probability that the next bit is 1 depends on the five bits before it. For each new sequence, all 32 probabilities are drawn afresh from a Beta distribution with parameters ½ and ½, so the network cannot memorise them. It has to estimate them on the fly from the bits it has seen.

For this setup the optimal Bayesian predictor has a closed form, shown below, which gives a benchmark no model can beat. The NTM beats the LSTM by a small but significant margin, yet it never quite reaches the optimum. Close to optimal, but not at it, is the accurate summary. Looking at the heads, the authors observe that the controller uses memory to count how many ones and zeros it has seen after each context, which is exactly what the optimal formula needs.

Priority sort tests whether memory can be used as a data structure. The input is 20 random binary vectors, each tagged with a scalar priority drawn uniformly between −1 and 1. The target is the 16 vectors with the highest priorities, in sorted order. The size of 16 was chosen deliberately: the authors wanted to see whether the NTM would discover a binary heap sort of depth 4.

It found something different. Looking at the write weightings, the authors hypothesise that the network uses the priority to decide the relative location of each write, placing vectors in memory roughly in priority order, and then reads the locations back in sequence. Both NTMs clearly outperform the LSTM on this task. The mechanism, though, is the authors' reading of the head weightings, not something the paper proves.

The tasks are small and synthetic. Each tests one algorithmic skill with short random binary vectors, and nothing in the paper shows an NTM on natural language, images or a real-world problem. The results show that the mechanism can learn simple procedures, not that it scales to practical ones.

Memory is fixed and has no bookkeeping. There are always 128 locations. There is no way to mark a location as free, reuse it safely, or remember the order in which locations were written, apart from the head simply moving forward. The copy task at length 120 shows where this bites: the authors name memory size as the limiting factor. Every read and write also touches every location, so the cost of each step grows with the size of memory.

Generalization is also partial. Repeat copy extends the loop but not the counter, and dynamic N-grams approach the Bayesian optimum without reaching it. The paper does not report on how reliable training is across random seeds. Later reimplementations found NTMs hard to train, with sensitivity to how memory is initialised, but that finding comes from later work, not from this paper.

The NTM appeared alongside two closely related ideas. Attention for machine translation, published the same year, let a decoder read a soft weighting over the encoder's states; the NTM cites it as related work, and the two share the same core operation (see attention). Memory Networks, posted a few days earlier, also paired a network with an explicit memory, and their end-to-end version in 2015 replaced hard lookups with soft ones.

The NTM's direct successor, the Differentiable Neural Computer (2016), kept the controller and the soft heads and addressed the bookkeeping limits above. It added a mechanism for allocating free memory and a record of the order in which locations were written, so the heads could follow that order forwards or backwards. The general idea of memory-augmented networks, and the habit of reading from a large store by a softmax over similarities to a key, carried forward into the attention layers of Transformers.