Why Attention Replaced Recurrence When It Costs More

Table 1 of the paper is three columns wide and it carries the whole argument for

throwing recurrence away. It is also the most misquoted table in the subject,

because the column that gets quoted is the one that decides nothing.

The table compares three ways of turning a sequence of $n$ vectors into another

sequence of $n$ vectors of the same width $d$. A recurrent layer, a

convolutional layer, and a self-attention layer. Of each it asks three

questions. How much arithmetic does one layer do. How much of that arithmetic

has to happen in a fixed order. How far apart can two positions be and still

reach each other. The answers are published as orders of growth, which is the

honest way to write them down and a poor way to understand them, so the first

job is to put numbers in.

Two sizes are fixed for everything below, both from the paper. The width is

$d = 512$, which section 3.1 gives as the output width of every sub-layer and

embedding in the base model. The length is $n = 1000$ positions, which is longer

than any sentence the paper trained on and is chosen so that the term in $n^2$

and the term in $d^2$ can be compared as real numbers rather than as symbols.

Where a kernel width is wanted it is $k = 3$, and where a restricted

neighbourhood is wanted it is $r = 64$. A multiply-add below means one

multiplication and one addition into a running total, which is what the inner

loop of a matrix product does.

The first column is total arithmetic inside one layer. It is a question about

money and about memory bandwidth, and it is the only column with a cost in it.

The second column is the minimum number of operations that have to be performed

one after another, because each needs the result of the one before. It is a

question about whether a machine with thousands of arithmetic units can be kept

busy. Work that waits cannot be shared out.

The third column is the number of steps a signal takes to get from one position

to another, forwards or backwards. The paper attaches it to the long-term

dependency literature rather than to any timing result, and that is the correct

reading: a long path is where a gradient gets lost, so this column is about what

the network can be taught, not about how long teaching it takes.

A layer can win one column and lose another, and most of the rows do.

Self-attention compares every position with every position. That is

$n \times n = 1{,}000{,}000$ ordered pairs, and each pair costs one dot product

across the width, $512$ multiply-adds, which in the base model is eight separate

dot products of $64$ because the width is split across eight heads. So the score

matrix costs $1{,}000{,}000 \times 512 = 512{,}000{,}000$ multiply-adds, which

is $n^2 d$ written out.

A recurrent layer does something different at every position. The state of width

$512$ is multiplied by a $512 \times 512$ matrix, which is

$512 \times 512 = 262{,}144$ multiply-adds, and that happens once per position,

giving $1000 \times 262{,}144 = 262{,}144{,}000$, which is $n d^2$ written out.

Here is the step that is usually skipped. Both of those counts are half of the

layer. Attention multiplies the weights into the values afterwards, a second

product of exactly the same shape, so the real figure is nearer

$1{,}024{,}000{,}000$. A recurrent layer multiplies the input by a second

$512 \times 512$ matrix as well as the state, so its real figure is nearer

$524{,}288{,}000$. The factor of two appears on both sides and cancels in the

comparison, which is why the orders of growth in the table can drop it. The

ratio survives untouched:

At a thousand positions, attention does nearly twice the arithmetic of the layer

it replaced. The ratio is the length divided by the width, so the two are equal

when $n = d$, which at this width is $512$ positions. Shorter than that and

attention is cheaper; longer and it is dearer, without limit.

The paper states that condition plainly and then says why it held for the work

in front of it: sentence representations in translation, cut into word pieces,

are tens of tokens long and not thousands. Section 5.1 batches about 25,000

source tokens at a time, which at those lengths is hundreds of sentences, not

one. For the problem on the desk in 2017, $n$ was comfortably below $d$ and the

first column favoured attention. That is a fact about machine translation, not

about architecture, and it is the first thing to stop believing when the same

layer is pointed at a document.

Convolution loses this column outright. A kernel of width $k$ does the recurrent

layer's arithmetic $k$ times over, $3 \times 262{,}144{,}000 = 786{,}432{,}000$

at a width of three, and the paper says as much. Restricting attention to a

neighbourhood of $r = 64$ positions costs

$64 \times 1000 \times 512 = 32{,}768{,}000$, which is the cheapest row in the

table by a factor of eight, and the paper proposes it for long sequences as

future work rather than reporting it as a result.

A recurrent state at position $t$ is a function of the state at position

$t-1$. Nothing at position two can start until position one has finished. Over a

thousand positions that is a thousand steps in a fixed order, and each step is

the matrix-vector product above: $262{,}144$ weights read from memory to perform

$262{,}144$ multiply-adds, one arithmetic operation per weight fetched.

Attention has no such chain. The same projection matrix is multiplied into all

thousand positions in one matrix product, so each weight fetched is used a

thousand times before it is thrown away. The score matrix is one product, the

softmax is elementwise, the weighted sum of values is one more product. The

count of steps that must wait for each other does not grow with the sequence at

all.

The mechanism behind the middle column is worth one number of its own, because

it is the number the hardware of 2017 was built around. Ask how much arithmetic

each weight does once it has been read out of memory.

The paper reports what that bought. Eight P100 processors, about $0.4$ seconds

per training step and 100,000 steps for the base model, which is

$100{,}000 \times 0.4 = 40{,}000$ seconds, or $11.1$ hours, given in section 5.2

as twelve hours. Those twelve hours bought 27.3 on the English to German test

set, which is above every earlier system in the results table, the ensembles

included. The 28.4 that gets quoted as the headline figure is a different row:

the big model, trained for 300,000 steps at about $1.0$ second a step, so

$300{,}000 \times 1.0 = 300{,}000$ seconds, which is $83.3$ hours, or $3.47$

days, written in the same section as 3.5 days. The twelve hours and the best

score in the paper are not the same run.

Between position one and position one thousand, a recurrent network has a

thousand edges and an attention layer has one. That is the third column and for

those two rows there is nothing more to say.

Convolution is where the column earns its keep. A layer of width three gives

each output a view of three inputs, and stacking $L$ such layers gives a view of

$L(k-1) + 1$ positions, because every extra layer widens the view by $k-1$. So

the two ends of a thousand-position window are not connected at all until the

stack is deep enough, and the paper's own entry for the contiguous case grows

with the length divided by the kernel width.

The six layers the paper stacks in each half of the model are not there to reach

across the sequence, because one layer already does. They are there for depth in

the ordinary sense, each one working on the representation the one below it

produced.

It does not mention memory. The score matrix for one head at a thousand

positions is $1{,}000{,}000$ numbers, eight million across the heads of one

layer, and all of it has to be kept for the backward pass. That is the cost that

later work on long sequences actually fought, and it is nowhere in the table,

because the table counts arithmetic.

It does not mention parameters, or quality, or anything measured. Every number

in it is a count derived from the shape of the layer, which is why it belongs at

the front of the paper rather than in the results. And the last row is a

proposal the paper explicitly leaves for future work, so it reports nothing at

all.

What the table does say, read with the middle column in front, is this. Attention

is the dearer layer at any length past the width, and it was adopted anyway,

because it was the only one of the three whose work could all be done at once.

The next lesson takes the single equation that does that work and rebuilds it,

including the one constant in it that looks like a tuning parameter and is not.