Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

The Hardware Lottery: Why the Dense Version Won

6 minute read

Published:

TL;DR: The previous chapter established that Transformers and GNNs compute the same thing on different graphs. This one asks why one of them took over. Attention compares every pair — asymptotically more work than sparse message passing — but expresses that work as dense matrix multiplication, which modern accelerators are built for. Sparse message passing needs gather and scatter over a neighbour index, which they are not. The winner was decided by hardware, not by mathematics.

The dense formulation

Self-attention over a whole input is three matrix multiplications and a softmax:

\[ \tilde{H}^{\ell} = \operatorname{softmax}\Bigl( H^{\ell} W_Q^{\ell} \bigl( H^{\ell} W_K^{\ell} \bigr)^{\top} \Bigr) \bigl( H^{\ell} W_V^{\ell} \bigr). \]

No loops, no indices, no per-node branching. Multi-head parallelises the same way: do one projection for all heads at once, then reshape queries, keys and values to \(n \times k \times d/k\). Everything after attention is token-wise and therefore trivially parallel.

Sparse message passing cannot be written like that. You maintain an index of neighbours, gather the source features for every edge, apply the message function, then scatter-add the results back to destination nodes. The access pattern is irregular by construction, memory-bound rather than compute-bound, and hostile to the wide, regular pipelines a GPU or TPU is built around.

The asymptotics say the opposite

Here is the tension, made concrete. Attention compares \(n^2\) pairs. Message passing on a graph of average degree \(k\) handles \(nk\) directed messages.

nodes \(n\)attention pairs \(n^2\)messages at \(k = 10\)ratio
10010,0001,00010×
1,0001,000,00010,000100×
10,000100,000,000100,0001,000×
1,000,000\(10^{12}\)\(10^{7}\)100,000×

Sparse message passing does dramatically less arithmetic, and the gap widens without bound. On operation count it is not close.

And yet the dense one is faster to train at the scales people actually use. That is the whole phenomenon. Let \(C\) be how many times more throughput a dense matmul achieves per arithmetic operation than gather-scatter. Dense wins while \(n^2 < C \cdot nk\), i.e. while
\[ n \;<\; C \, k . \]
The crossover is linear in both the hardware constant and the graph's density. For a sparse graph with \(k\) around 10 and a large \(C\), that threshold sits in the thousands of nodes — which is above most sequence lengths and most molecular graphs, and far below a billion-node social network. I am not giving a number for \(C\): it depends on hardware, kernel and precision, and the source paper reports none. The shape of the trade-off is the point.

This explains the exception the argument always carries: for very sparse or billion-scale graphs, message passing remains the only option. There, \(n \gg Ck\) and no constant factor rescues \(n^2\).

The hardware lottery

Sara Hooker’s term for this: a research idea wins partly on merit and partly because it happens to fit the hardware available when it arrives. Ideas that need hardware nobody built lose, whatever their intrinsic quality — and the loss looks like the idea being wrong rather than being early.

Transformers are the clean case. Attention was not selected because it does less work — it does more. It was selected because its work is shaped like the operation accelerators execute best, and because that shape kept paying off as models and datasets grew.

This connects to Sutton’s bitter lesson: methods that scale with compute tend to beat methods that encode human insight about the problem. A GNN’s sparse graph is encoded insight — a claim that these entities interact and those do not. A Transformer declines to make that claim and learns which pairs matter. When compute is scarce the encoded insight is valuable; when compute is abundant, learning it beats asserting it.

Two things this argument does not establish. First, that structure is worthless. There is empirical evidence Transformers can learn the inductive biases GNNs hard-code — locality especially — when trained at sufficient scale and given positional encodings as hints. "Can learn given enough data and compute" is not "is better to learn"; on small scientific datasets the encoded prior is often still the better trade. Second, that the lottery is permanent. It is a statement about current accelerators. Hardware with better sparse support, or graphs large enough to make \(n^2\) impossible, changes the arithmetic — and the equivalence from the previous chapter means the model need not change at all, only which implementation of the same operator you run.

What to take from it

Practically: if your graph is small or dense, run attention with a mask and get the fast kernel for free. If it is large and sparse, message passing is not a legacy choice, it is the only feasible one. The equivalence means this is an implementation decision, not an architectural commitment.

Conceptually, this is the honest ending to the geometric deep learning story. The blueprint tells you which architectures respect your data’s symmetry. It is silent on which will run fast, and that silence turned out to determine what the field actually adopted. Both facts are worth holding at once: the mathematics unified these architectures, and the hardware picked a winner among them anyway.

✅ Key Takeaways

  • Attention is three dense matmuls and a softmax — no indices, no branching, and multi-head parallelises by reshaping to \(n \times k \times d/k\).
  • Sparse message passing needs gather and scatter over a neighbour index: irregular, memory-bound, and poorly matched to current accelerators.
  • Attention does asymptotically more arithmetic — \(n^2\) pairs against \(nk\) messages, a 1,000× gap at \(n = 10^4, k = 10\) — and is still faster to train at typical scales.
  • Dense wins while \(n < Ck\), linear in the hardware constant and the graph's density. Above that, sparsity is the only option.
  • The hardware lottery: architectures win partly because they fit the hardware of their moment. Attention's advantage is the shape of its computation, not the amount.
  • None of this shows structure is worthless, or that the outcome is permanent — and by the equivalence, changing implementation does not require changing the model.

References

You May Also Enjoy

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test framework’s smaller cousin, and a JSON-safe date library already installed — most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually — but ‘eventually’ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first — which is faster, shorter, and free of race conditions.