Per-layer complexity — attention vs recurrence

Background

The Vaswani et al. paper compares per-layer cost. For sequence length $n$ and representation dim $d$:

$$\text{self-attention} = O(n^2 d), \qquad \text{recurrent} = O(n\,d^2)$$

So self-attention is cheaper when $n < d$ (typical for sentences); recurrence wins when $n \gg d$ (very long sequences) — the tension that motivates efficient-attention research.

Problem statement

Implement layer_complexity(n, d) returning (self_attention_ops, recurrent_ops, cheaper).

Input

• n — sequence length.
• d — representation dimension.

Output

Returns (self_attention_ops, recurrent_ops, cheaper):

• self_attention_ops = n * n * d,
• recurrent_ops = n * d * d,
• cheaper = "self-attention" if it has strictly fewer ops, else "recurrent".

Examples

Example 1 — short sentence, big model

Input:  n = 10, d = 512
Output: (51200, 2621440, "self-attention")

Example 2 — very long sequence

Input:  n = 1000, d = 64
Output: (64000000, 4096000, "recurrent")

Constraints

• self_attention_ops = n*n*d, recurrent_ops = n*d*d.
• cheaper is "self-attention" only when its op count is strictly less; ties go to "recurrent".
• Return (int, int, str).

Notes

• Self-attention is cheaper exactly when $n < d$. As context length grows past the model width, the $n^2$ term dominates — why long-context efficiency is an active research area.