LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pendingjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Dense full-attention interaction cost and path length

Statement

Use the standard dense self-attention interaction with $n$ token rows, model width $d$ , and $h$ heads whose total query/key/value width is $d$ (for example, $h$ heads of width $d / h$ when $h$ divides $d$ ). Counting scalar multiply-add operations in the direct matrix implementation, forming all query-key scores and applying the resulting dense weight matrix to all value rows costs $O (n^{2} d)$ per attention sublayer; row softmax adds $O (n^{2})$ . Every query position has a direct value path from every key position, so one unmasked self-attention sublayer gives path length one between any input token value and any output token. A fixed stack of $L$ such layers has a position-to-position path of at most $L$ attention edges, independent of $n$ .

If each query, key, value, and output projection is a dense $d \times d$ linear map and the tokenwise feedforward width is $d_{f f}$ , those operations add $O (n d^{2} + n d d_{f f})$ work per full Transformer layer. Thus the $O (n^{2} d)$ claim concerns the dense all-pairs attention interaction used in the source comparison; it does not assert that projections or the feedforward sublayer have that cost, and it makes no claim about sparse attention, linear attention, training work, memory traffic, or hardware speed.

Statement references

Vaswani et al., Table 1 and §4: self-attention interaction complexity, sequential operations, and maximum path length

Dive into Deep Learning, §11.6.2: scaled-attention matrix multiplications and direct token connections

Facts & Assumptions

Given: Positive integers $n, d$ , the dense multi-head self-attention dimensions in the Statement, and the direct matrix implementation.

[F1]

The forward pass forms scaled query-key scores, applies row softmax, and multiplies the resulting attention weights by values (Transformer encoder-decoder forward pass).

Proof

1.1givenF1algebra

For one head of width $d_{h}$ , the score product has dimensions $(n \times d_{h}) (d_{h} \times n)$ and therefore uses $O (n^{2} d_{h})$ scalar multiply-adds. The value product has dimensions $(n \times n) (n \times d_{h})$ and also uses $O (n^{2} d_{h})$ operations.

1.2F1givenalgebra

For finite real scores, every softmax weight is strictly positive, so each output row uses the value row of every input position. This is one direct attention edge; composing $L$ layers yields at most one such edge per layer, hence at most $L$ attention edges independent of $n$ .

2.1step 1.1algebra

Summing over $h$ heads with total width $\sum_{a = 1}^{h} d_{h}^{(a)} = d$ gives $O (n^{2} d)$ score and value work. Normalizing $n$ rows of $n$ scores costs $O (n^{2})$ , which is at most $O (n^{2} d)$ because $d \geq 1$ .

3.1givenF1algebra∎

A dense projection of an $n \times d$ matrix by a $d \times d$ matrix costs $O (n d^{2})$ , and a two-map positionwise feedforward network of hidden width $d_{f f}$ costs $O (n d d_{f f})$ . Adding these separate terms gives the full-layer operation count stated in the Statement.

Depends on

Transformer encoder-decoder forward pass

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

2 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Vaswani et al., Attention Is All You Need, Table 1 and §4 (standard reference, not scraped)
Dive into Deep Learning, §11.6.2 Comparing CNNs, RNNs, and Self-Attention (standard reference, not scraped)