Why convolution and attention differ

Take a sequence of 1000 items, each a vector of 64 numbers. One self-attention layer compares every item with every other and costs about 64,000,000 multiply-adds. A convolution of width three over the same sequence costs 12,288,000. At 100 items the order reverses, because attention costs 640,000 and the convolution costs 1,228,800.

The two layers encode different assumptions. A convolution assumes that neighbours matter and that the same pattern recurs at every position, and it shares one kernel across the sequence [S:74:222]. Attention assumes nothing about distance, and its cost grows with the square of the sequence length [S:217:6]. The short answer is that attention does not replace convolution: each layer carries a different assumption, and each wins on different data and different lengths. !Operations per layer against sequence length, for vectors of width 64 and a kernel of width three. Attention costs n squared times d and the convolution costs three times n times d squared, so the lines cross at 192 items, where both need 2,359,296 multiply-adds. Below the crossing the convolution is the expensive one, which is the opposite of the usual telling. Status: synthetic.

An assumption built into a structure is an inductive bias. The convolutional bias is strong and cheap when it holds: a local pattern is detected once and reused everywhere. The attention bias is weak and expensive, and it lets the model discover a relation between two positions that no fixed window would put together. !The number of steps information takes between the first item and the eighth. Attention connects the pair in one step, a convolution of width three needs four layers to reach across, and a recurrent layer needs seven. The count is about depth and delay rather than arithmetic, and it is why a long chain leaves a parallel machine idle. Status: schematic.

The two formulas count different objects. Attention builds one score for every ordered pair, and each score is a dot product over the vector width, so the work is the square of the length times the width. A convolution builds one output per position, each from a fixed window of neighbours and every channel, meaning every one of the vector's entries, so the work is the length times the width squared times the kernel width.

The path length is the number of steps information travels between two positions. Attention connects any pair in one layer, and a recurrent layer needs a number of sequential steps that grows with the length [S:217:6]. A convolutional stack does not connect all pairs in one layer: with contiguous kernels, a stack of width-k kernels needs about n/k layers. Each layer therefore adds k − 1 items of reach, and the reach is linear in depth [S:217:7].

Only a dilated stack, whose taps are spaced further apart at every layer, reaches every pair in about log base k of n layers, and that is the row the table reports [S:217:6]. Short paths make long-range dependencies easier to learn, and the transformer replaces recurrence with attention to obtain them [S:217:2].

Worked example. Compare the two cost formulas from the transformer paper, using n for the sequence length, d for the vector width, and a kernel width of 3. Attention costs about n squared times d, and the convolution costs about 3 times n times d squared [S:217:6]. Set them equal:

Dividing both sides by n times d leaves n equal to 3 times d. With d of 64, the crossover is at 192 items.

At exactly 192 items both formulas give 2,359,296 operations, so neither layer has an advantage in the count. Below that length the n squared term is small enough that the convolution's term, 3 times n times d squared, is the larger; above it, the n squared term is the larger. This counts operations, not examples: the convolutional advantage on small image datasets comes from its bias, not from this crossover. The crossover moves with the kernel width and the vector width, so no single number settles the comparison.

Neither layer waits for its neighbours. Attention and convolution both compute every position in parallel, while a recurrent layer must finish one position before it starts the next [S:217:6]. That difference in sequential depth, the number of steps that must run one after another, matters as much as the operation count, because a long chain leaves a parallel machine idle.

A convolution also starts local and grows its view with depth. Without dilation, one kernel of width three sees three items, and a stack of such kernels sees about two more items per layer, so the reach is linear in depth. Attention sees the whole sequence in its first layer, which is either exactly what the task needs or an expensive way to look at neighbours that were already close.

This is why pictures and sentences pulled the field in different directions. An image has strong local structure, because nearby pixels are more alike than distant ones, and a small kernel exploits that structure with few parameters [S:58:287]. A sentence has long-range structure, and a pronoun can depend on a noun twenty words earlier.

Attention did not replace convolution. A vision transformer cuts an image into patches and treats the patches as if they were words [S:229:1]. It works at scale, and its authors state that transformers lack the translation equivariance and locality of convolutional networks, so they do worse on new images when the training set is small [S:229:2]. Convolutions also remain inside many vision models, applied before attention or beside it [S:229:1].

The practical answer is usually a hybrid. Use the convolutional bias where the data has local structure and the dataset is small. Use attention where the relations are long-range, the data is plentiful, and the quadratic table is affordable. Attention is often applied together with a convolutional network rather than instead of one [S:229:1].

The count is operations per layer, not seconds. It ignores memory traffic and how well a machine runs each kind of operation, and it changes with the number of heads and the kernel width. A model can also be wrong about which assumption its data satisfies, and paying for that mistake means collecting more data, not doing more arithmetic.

The formal statement. For one layer over $n$ items of width $d$, the transformer paper's Table 1 gives three costs [S:217:6]:

$$\text{attention}:n^{2}d,\text{convolution}:kn{d}^2,\text{recurrence}:n{d}^2.$$

The line says attention pays for every ordered pair and one dot product each, while a convolution pays for every position, every channel pair and every kernel tap. The hypotheses are: one layer, a kernel of width $k$, the same width $d$ on both sides, constant factors dropped, and a count of arithmetic operations rather than time.

The derivation. Set the first two costs equal and divide. Both sides carry a factor $nd$, and both factors are positive. What remains is

$$n=kd.$$

The crossover is a length. It grows with the kernel width and with the vector width, and the core's 320 is that product at $k=5$ and $d=64$. Below the crossover the width-squared term of the convolution dominates. Above it the pair term does.

The edge case. The table lists $O({\log }_{k}n)$ as the convolutional path length, and that row is the dilated stack. The paper's text says a contiguous stack needs $O(n/k)$ layers, while dilated convolutions need $O({\log }_{k}n)$ [S:217:7]. The core now conditions its sentence on dilation: a stack of width-three kernels with no dilation adds two items of reach per layer, which is linear growth, while a dilated stack spaces its taps further apart at every layer, so the reach multiplies and the depth becomes logarithmic. Read the table's row as the dilated case.

The second edge case. The crossover counts operations, and memory traffic can move it. The arithmetic intensity of the projections carries a term in the ratio of length to width, which the CS336 notes call difficult to reduce [S:100:172]. A layer that is memory-bound spends its time moving values rather than multiplying them, so the length at which each layer becomes the slower one depends on the batch and the machine.

What the core hid. It compared two layers at one width. In a real model the convolutional width and the attention width are separate choices, so the comparison at equal width is a decision, not a fact. A real block also pays for the projections and the output map, which are linear in the length and are counted separately in the Megatron-LM appendix [S:640:39].

Where the picture breaks. The core said two layers of three-tap kernels see five values. The reach is right and the reading is not. With a nonlinearity between the layers, the pair is not one five-tap kernel, because no single weighted sum reproduces the composition. Reach grows; a wider kernel does not appear.

Original sources. Table 1 gives the per-layer complexity, the minimum number of sequential operations and the maximum path length for self-attention, recurrence and convolution [S:217:6]. The surrounding text states the purpose of the comparison: fewer sequential operations and shorter paths make long-range dependencies easier to learn. The next page gives the two convolutional stacks, contiguous and dilated, and the cost of a separable convolution [S:217:7].

An open question. Does a hybrid beat both pure forms at long context, and at what length? The Titans paper frames attention as a short-term memory with accurate dependencies, and a compressed recurrent state as a long-term memory that is cheap and lossy [S:396:1]. It reports a hybrid that scales past two million tokens [S:396:1]. The unsettled part is the crossover. No result in this corpus compares a pure attention model, a pure compressed-state model and a hybrid at matched parameters and matched training compute, over a sweep of context lengths. Evidence that would settle it: one such sweep on a recall task with a known target position, reporting accuracy against context length for all three models.

A frontier result. The vision transformer keeps the comparison honest. It replaces convolutions with attention over patches and works at scale, and its authors state the cost plainly. Without enough data the model generalises worse than a convolutional network, because it lacks translation equivariance and locality [S:229:2]. The quadratic layer did not make the convolutional assumption obsolete. It made that assumption optional, at a price in data.

What to read next. Read Table 1 and §4 of the transformer paper together, because the table's convolutional row is the dilated case [S:217:6][S:217:7]. Read the first two pages of the vision transformer for the data-scale result [S:229:2]. Read Titans §1 and §2 for the memory taxonomy the hybrid argument rests on [S:396:1][S:396:3]. The CS336 notes give the memory-traffic side of the cost that the operation count leaves out [S:100:172].