DOTA: detect and omit weak attentions for scalable transformer acceleration

A chip and a training trick designed together — a tiny learned "detector" predicts which attention connections will matter before they are computed, so the hardware computes only the strong tenth and skips the rest.

Why this problem is worth solving

A Transformer is the neural-network architecture behind modern language, vision and generative models. Its defining ingredient is self-attention: for every token — a word piece, or an image patch — the model asks how relevant every other token is, and then builds the token’s new representation as a weighted mix of all the others.

The paper offers a picture worth keeping: attention is a graph. Each token is a vertex. Each pair of tokens gets a directed edge, weighted by how much one attends to the other. Standard attention builds the complete graph — every vertex connected to every vertex — and then aggregates over it: each token collects the feature vectors of all its incoming neighbors, multiplies each by the edge weight, and sums.

The complete graph is the problem. A sequence of n tokens has n × n edges, so the cost is quadratic: doubling the input length quadruples the attention work. Going from a 2,000-token input to a 16,000-token input — an 8× longer document — multiplies the attention work by 64. The paper measures where the time goes as sequences grow: at 384 tokens attention is a modest share of the model’s floating-point operations, but from about 1,000 tokens upward it becomes the dominant cost, and keeps growing.

There is a second, subtler reason attention is painful for hardware. The other parts of a Transformer multiply activations by learned weight matrices that sit still in memory. Attention multiplies two matrices that are both computed from the input — the paper calls this parameter-free matrix multiplication. There are no fixed weights to preload, cache or prune ahead of time. Every input builds two fresh matrices and multiplies them.

Yet almost all of that work is wasted. The paper takes a trained BERT-large model, computes its full attention graphs on a question-answering benchmark, keeps only the strongest edges in each row, and measures accuracy:

Keeping one edge in ten changes the answer quality by 0.3 points. Nine tenths of the quadratic cost buys almost nothing. The paper calls these unimportant edges weak connections.

What people did before, and where it broke

The catch is circular: the obvious way to find the weak connections is to compute the attention scores and look. But computing the scores is the expensive step. Dropping edges after the fact saves only the cheap aggregation that follows, not the quadratic multiplication that came before. Any real saving requires predicting weakness before paying for the scores. Each prior line of work hits a different wall on the way there.

Fixed sparsity patterns. Some efficient-Transformer designs decide the graph shape in advance: each token attends to a local window, to fixed blocks, or to strided positions. The hardware loves this — the pattern is known at design time. But which connections matter is decided by the content of each input, and a pattern chosen before seeing the input cannot follow it.

Efficient Transformer variants. Another line (clustering and grouping methods) reduces memory during training but spends extra computation to decide the groups — the paper notes they are impractical for fast inference.

Prune after computing. MnnFast skips aggregation work for small attention weights — after all scores and the softmax are computed. The quadratic part survives intact.

Estimate before computing. This is the right shape of solution, and two accelerators tried it. A3 approximates attention weights but needs a sorting-based preprocessing pass done outside the accelerator, which eats the savings. ELSA, the state of the art, estimates the angle between each query and key vector using sign random projections — cheap in hardware, but the estimate is noisy. Noise forces caution: to protect accuracy, ELSA must keep about 20% of connections where a sharper detector could keep 6%. Its estimator is also fixed mathematics — it cannot learn, and the model cannot adapt to it.

Structured pruning. SpAtten removes whole tokens and whole attention heads — entire rows and columns of the matrix. The authors’ experiments show real attention importance is scattered irregularly; cutting by rows and columns is too blunt to follow it.

The gap DOTA fills: a detector that is accurate (because it is trained, not fixed), cheap (because it works in compressed, low-precision form), and supported by hardware that turns skipped connections into actual time and energy saved — including the irregular memory traffic that sparsity creates.

The idea

DOTA has two halves that only work together: an algorithm that makes weakness predictable, and an architecture that makes skipping profitable.

A detector small enough to be free

The detector must answer, for every token pair, “will this connection be strong?” — at a tiny fraction of the cost of computing the connection itself. DOTA makes it cheap in two independent ways.

Shrink the vectors. Instead of comparing the full query and key vectors (dimension d, typically 64 or more per attention head), the detector first projects the input into a much smaller dimension k using a fixed sparse random matrix, then applies its own small learned transformations. The estimated score is the dot product of these shrunken vectors. In the text benchmark, dimension 64 shrinks to 12 — a 5× smaller comparison — with no loss in final accuracy.

Shrink the numbers. The estimated scores are only used to rank connections, never to compute the output. Ranking tolerates coarse numbers, so the detector runs in 4-bit — sometimes even 2-bit — integer arithmetic, against the 16-bit fixed-point used for the real computation. Each halving of precision roughly doubles hardware throughput per unit of silicon.

Connections whose estimated score clears a threshold survive; the threshold comes from a top-k rule, tuned on validation data. The bet underneath: pairs with small true scores also have small estimated scores. Cheap approximations keep the order even when they blur the values.

Making the model easy to predict

A fixed estimator like ELSA’s takes the model as given. DOTA instead trains detector and model together, minimizing the model’s own loss plus an estimation loss — the squared difference between true and estimated scores.

The elegant part is which way the gradients flow. The estimation loss updates the detector to track the model — but it also updates the model, nudging its attention scores to be easier to approximate with few dimensions. Meanwhile the model loss pushes back wherever expressiveness actually matters for accuracy. The two pressures settle where the attention structure is as simple as the task allows, and no simpler. This also makes the design robust to the choice of k: the model meets the detector partway.

One more repair is needed. Omitting connections changes the softmax — the normalization that turns raw scores into weights summing to one. Remove entries, and the survivors’ weights inflate. So the model is fine-tuned with omission switched on, letting the remaining parameters adapt. This restores accuracy to the dense baseline while keeping only 3–10% of connections.

Hardware that turns sparsity into speed

Skipped connections only save time if the hardware stays busy. Three design decisions do the work.

One unified engine, not one per block. Every heavy computation in a Transformer — the projections, the attention, the feed-forward layers — is a matrix multiplication. DOTA abstracts the whole encoder into three sequential matrix-multiplication stages, cuts each into chunks, and maps the chunks onto four identical compute lanes. Each lane produces a chunk of query, key and value vectors and later consumes the same chunk for attention, so intermediate data never crosses between lanes. Prior accelerators built special hardware for the attention block alone; DOTA’s one engine serves the whole model, which is what makes end-to-end acceleration possible.

A matrix unit that changes precision row by row. Detection wants 2- and 4-bit arithmetic; real computation wants 16-bit. Separate circuits for each would waste area, and the right ratio between the two differs per workload. DOTA’s reconfigurable matrix multiplication unit is a 32×16 grid of multiply-accumulate cells in which each row can be switched between 16-bit, 8-bit, 4-bit and 2-bit modes. The trick is that a high-precision multiplier is assembled from four low-precision ones (split each operand into high and low halves, multiply the four combinations, shift and add) — run the same silicon in low-precision mode and it delivers four independent multiplies per cycle instead of one. Throughput scales exactly where the detector needs it.

A dataflow that fights the irregularity sparsity creates. After detection, each token keeps a different, scattered set of partners — the classic sparse workload problem: unbalanced work and irregular memory access. DOTA processes four tokens’ rows in parallel (token-parallel dataflow) so that a key vector needed by several of them is loaded from memory once, not once per row. Balance is restored in software: the detector is constrained to keep the same number of connections in every row, which the accuracy experiments show costs almost nothing. Order is restored in hardware: a small scheduler reorders each row’s connections so that shared keys line up in the same cycle — issuing first the keys shared by all four rows, then by three, and so on. In the paper’s worked example this out-of-order execution cuts memory loads from 11 key vectors to 7. The schedule is computed once and reused for the aggregation pass, and the output still emerges in regular order, because the irregularity lives entirely in the intermediate matrix, which is consumed on the spot.

full vectors:      64 dims, FX16   (used later, only for survivors)
detector vectors:  12 dims, INT4   (used now, for everyone)

Why it works

Because most attention connections barely move the output, a model can afford to lose nine in ten of them — if the right ones are kept. → Because ranking survives coarse arithmetic, strength can be estimated in shrunken dimensions and 4-bit numbers, making the estimate roughly two orders of magnitude cheaper than the real score — cheap enough that its own quadratic cost stays negligible (0.11–0.34% of total energy). → Because the detector is trained jointly with the model, the model’s attention drifts toward being predictable, so the estimates stay accurate at retention ratios where a fixed estimator has already collapsed — 6% where ELSA needs 20%. → Because the equal-count constraint and the reuse-aware reordering restore regularity, the four lanes stay busy and each key vector is fetched close to once — the sparsity shows up as saved time, not as stalls. → Therefore the quadratic term shrinks by more than an order of magnitude in practice, and attention stops being the bottleneck: after DOTA, the ordinary feed-forward layers dominate the remaining cost.

What it costs

• You must retrain the model. The detector’s accuracy comes from joint fine-tuning. A frozen, already-deployed model cannot simply be placed on DOTA at full benefit — and each model-task pair needs its own tuning of the retention ratio, projection size and precision.
• It is custom silicon. The results come from a synthesized 22-nanometer design running at 1 gigahertz — 3 watts and about 4.4 square millimeters. None of this accelerates a Transformer on hardware you already own.
• Amdahl’s law bites. Attention accelerates 152.6×, but the whole model only 9.2×, because the untouched linear layers become the new bottleneck — after DOTA they consume 85–99% of the energy. The authors point to weight pruning and quantization as the natural next step on the same hardware.
• The equal-count constraint is a lie the model must absorb. Forcing every token to keep the same number of partners is there for the hardware’s sake; fine-tuning hides its cost, but it is an approximation nonetheless.
• Generation is a different game. Decoders process tokens one at a time, which is memory-bound; DOTA reduces traffic there but the headline speedups are measured on encoder-style workloads.

The evaluation

Model quality was tested on four long-sequence tasks: question answering (BERT-large on SQuAD, 384 tokens), image classification as a 1,000-token sequence, text classification at 2,000 tokens, document-pair retrieval at 4,000 tokens, and GPT-2 language modeling at 4,000 tokens. Across all of them, DOTA matches or slightly beats the dense baseline while keeping 3–10% of connections, and matches the best published software results on the long-sequence suite.

The hardware was written in register-transfer level and synthesized with a TSMC 22-nanometer library at 1 gigahertz: 2 tera-operations per second, about 3 watts. For the GPU comparison, DOTA’s resources are scaled up to match an NVIDIA V100’s peak throughput (12 versus 14 tera-operations per second), so the comparison measures design, not size. Two operating points are reported: DOTA-C (conservative) allows at most 0.5% accuracy loss; DOTA-A (aggressive) allows 1.5%.

Two design-space results are worth keeping. Detection precision can drop to 4-bit integers on every benchmark — some tolerate 2-bit — with negligible accuracy change, which is what justifies the reconfigurable multiplier. And token parallelism has a sweet spot: four rows. Beyond that, the scheduler’s bookkeeping grows exponentially (its buffer count doubles per added row) while the extra memory reuse fades, because attention locality is real but limited.