⚙️AlgorithmIntermediate

Efficient Attention Mechanisms

Key Points

•
Standard softmax attention costs O(n²) in sequence length because every token compares with every other token.
•
Linear attention replaces softmax with a kernel feature map so we can reorder computations and reduce cost to O(n · r), where r is the feature dimension.
•
By pre-aggregating keys and values into small summaries, each query can be answered with only dot products against these summaries.
•
Causal (autoregressive) linear attention can be computed online using prefix sums, enabling streaming with constant memory per step.
•
Choosing the right feature map balances accuracy and speed: ELU+1 is simple and fast; random Fourier features approximate softmax better but cost more.
•
Numerical stability requires nonnegative feature maps and normalization to avoid exploding activations.
•
Linear attention is exact for the chosen kernel, but only approximates softmax unless you use special random features (e.g., Performer/FAVOR+).
•
In C++, careful memory layout and loop ordering are key to achieving the advertised O(n · r) runtime and O(r · $d_{v}$ ) memory.

Prerequisites

→Matrix multiplication and associativity — Linear attention relies on reordering matrix products to avoid building n×n intermediates.
→Softmax attention (Transformer basics) — Understanding standard attention clarifies what linear attention replaces and why it is faster.
→Kernel methods and feature maps — Linear attention uses a kernel trick: approximate a kernel by an inner product in feature space.
→Numerical stability and normalization — Stable denominators and nonnegative features are critical to avoid exploding or vanishing outputs.
→Prefix sums / streaming algorithms — Causal linear attention uses cumulative updates to support online inference.

Detailed Explanation

Tap terms for definitions

01Overview

Efficient attention mechanisms aim to keep the expressive power of attention while avoiding the quadratic O(n^2) cost that appears when every token interacts with every other token. The classic Transformer computes attention as softmax(QK^T)V, which forms an n×n matrix of pairwise scores. This becomes the bottleneck for long sequences in language modeling, audio, or DNA analysis. Linear attention bypasses that bottleneck by replacing the softmax with a kernel feature map that makes attention associative. Instead of materializing the full n×n score matrix, we first compress information from keys and values into a small set of running summaries and then answer each query using only these summaries. As a result, time and memory scale linearly with sequence length n and linearly with a feature dimension r (often r ≪ n). Some variants, like Performer, choose random feature maps that approximate the softmax kernel closely; others, like the ELU+1 map, trade some accuracy for simplicity and speed. Importantly, linear attention can be computed in streaming (causal) fashion, enabling online inference with constant memory per step. The main ideas are algebraic reordering, kernel tricks, and careful normalization for stability.

02Intuition & Analogies

Hook: Imagine you are hosting a party with n guests. Classic attention means every guest talks to every other guest to reach a group consensus—O(n^2) conversations. That quickly becomes unmanageable as the party grows. Concept: Linear attention appoints a few note-takers (feature summaries). Instead of having every pair talk, each guest whispers to the note-takers, who keep compact summaries of all conversations so far. When someone needs information (a query), they just consult the note-takers rather than pinging everyone else. Example: Suppose each guest (a token) hands the note-takers two items: a short tag describing themselves (a transformed key) and their message (the value). The note-takers maintain two running tallies: (1) a sum of tags, and (2) a sum of outer products between tags and messages. When a new guest asks a question (a query), we quickly combine their question with those two tallies to generate an answer—no need to revisit every past guest individually. This reduces work dramatically: we do a constant amount of work per guest to update the tallies, and a small amount per query to read them, giving us linear time overall. The twist is that the way we convert guests into tags uses a specific 'feature map' so that consulting the tallies is equivalent to a specific kind of attention. If we choose the feature map cleverly, this approximates the familiar softmax attention quite well; if we choose it for simplicity (like ELU+1), it is very fast and stable but not an exact softmax replacement.

03Formal Definition

Given queries Q ∈

R^{n \times d_{k}}

, keys K ∈

R^{n \times d_{k}}

, and values V ∈

R^{n \times d_{v}}

, standard (scaled) dot-product attention is A = softmax(Q

K^{T}

d_{k}

)V. Linear attention replaces the softmax kernel with a feature map ϕ:

R^{d_{k}}

→

R^{r}

such that a kernel k(q,k) ≈ ϕ(q)^T ϕ(k). Define Q' = ϕ(Q) ∈

R^{n \times r}

and K' = ϕ(K) ∈

R^{n \times r}

. Then we can write unnormalized attention as Ã = Q'(K'^T V). Because matrix multiplication is associative, compute

S = K^{' T}

V ∈

R^{r \times d_{v}}

once, then Ã = Q' S without building the n×n matrix. For normalized attention that mimics probability normalization, maintain

z = K^{' T}

1_n ∈

R^{r}

(sum of key features) and output for each query q: y(q) = (ϕ(q)^T S) / (ϕ(q)^T z). In causal settings, replace sums with prefix sums over positions

i \leq t

to ensure tokens only attend to the past. If ϕ yields nonnegative outputs, denominators are positive and normalization is stable. When ϕ is chosen as random features approximating the exponential kernel, this procedure approximates softmax attention; when ϕ is deterministic (e.g., ELU+1), it computes attention under a different kernel but preserves linear complexity.

04When to Use

Long sequences: When n is large (thousands to millions), O(n^2) memory and time are prohibitive. Linear attention reduces both to O(n · r), enabling practical training and inference.
Streaming/online inference: In autoregressive models, you can maintain running summaries S_t and z_t and answer each next-token query in O(r · d_v) time with O(r · d_v) memory.
Edge and realtime applications: Limited memory and latency budgets benefit from linear-time updates and small working sets.
Retrieval-like patterns: If your model benefits from global context but exact pairwise interactions are not necessary, linear attention provides a strong approximation.
Softmax approximation needs: Use random feature maps (e.g., FAVOR+) when you want behavior close to softmax with tunable accuracy via feature rank r.
When interpretability of exact attention weights is critical, or when short sequences dominate and overheads matter less, standard attention may be preferable.

⚠️Common Mistakes

Assuming equivalence to softmax: Linear attention is exact only for its kernel. Unless you use appropriate random features, it does not reproduce softmax. Be explicit about the kernel and its implications.
Ignoring normalization: Without a denominator term (ϕ(q)^T z), outputs can explode with sequence length. Always include normalization, especially with nonnegative ϕ.
Choosing too small r: An overly small feature dimension harms accuracy. Tune r and monitor validation metrics.
Numerical instability: Using feature maps that produce negative values can cause cancellations in denominators. Prefer nonnegative maps (e.g., ELU+1 shifted) or use stabilized implementations (e.g., Performer’s positive random features with re-centering).
Materializing large intermediates: If you build K'^T explicitly per step or re-scan the sequence for each query, you lose linear complexity. Precompute S and z once (non-causal) or maintain prefix updates (causal).
Poor loop ordering in C++: Inefficient memory access can dominate runtime. Iterate with contiguous memory strides, accumulate into small r×d_v buffers, and avoid repeated allocations.

Key Formulas

Softmax Attention

A = softmax (\frac{Q K ^{⊤}}{d _{k}}) V

Explanation: Standard attention forms all pairwise query–key scores, normalizes each row with softmax, and applies the weights to V. This incurs O( $n^{2}$ ) time and memory for sequence length n.

Kernel Feature Map

k (q, k) \approx ϕ (q)^{⊤} ϕ (k)

Explanation: A kernel similarity can be approximated as an inner product in a transformed space. Choosing $ϕ$ makes attention associative and enables linear-time computation.

Unnormalized Linear Attention

\tilde{A} = ϕ (Q) (ϕ (K)^{⊤} V)

Explanation: Reorders matrix multiplications so we never build the n×n score matrix. First compress keys/values into S = $ϕ$ (K)^{ $⊤$ }V, then multiply by $ϕ$ (Q).

Sufficient Statistics

S = i = 1 \sum n ϕ (k_{i}) v_{i}^{⊤} \in R^{r \times d_{v}}, z = i = 1 \sum n ϕ (k_{i}) \in R^{r}

Explanation: All keys and values can be summarized by an r× $d_{v}$ matrix S and an r-vector z. These summaries allow answering any query without revisiting the entire sequence.

Normalized Output

y (q) = \frac{ϕ ( q ) ^{⊤} S}{ϕ ( q ) ^{⊤} z}

Explanation: Dividing by $ϕ$ (q)^{ $⊤$ } z mimics row-wise normalization (like softmax rows summing to 1). This keeps outputs well scaled as sequence length grows.

Causal Prefix Updates

S_{t} = S_{t - 1} + ϕ (k_{t}) v_{t}^{⊤}, z_{t} = z_{t - 1} + ϕ (k_{t})

Explanation: For autoregressive models, maintain running statistics so each new token can be processed in O(r· $d_{v}$ ) time without revisiting the past.

Complexity Comparison

Softmax cost: O (n^{2} d_{k} + n^{2}) vs. Linear cost: O (n r d_{v} + n r)

Explanation: Softmax attention scales quadratically with sequence length n, while linear attention scales linearly with n and with the feature rank r. This is the core efficiency benefit.

Random Feature Approximation

E [ϕ_{ω} (q)^{⊤} ϕ_{ω} (k)] = exp (\frac{q ^{⊤} k}{d _{k}}) (approx.)

Explanation: With a suitable distribution over random features, the expected inner product recovers the exponential (softmax) kernel. Finite r introduces variance that decays with r.

Complexity Analysis

Let n be sequence length,

d_{k}

the query/key dimension,

d_{v}

the value dimension, and r the feature-map dimension. Standard softmax attention forms Q

K^{T}

(O(

n^{2}

d_{k}

)), applies softmax (O(

n^{2}

)), and multiplies by V (O(

n^{2}

d_{v}

)), totaling O(

n^{2}

(

d_{k}

d_{v}

)) time and O(

n^{2}

) memory to store the score matrix. In contrast, linear attention first computes K' =

φ (K)

and Q' =

φ (Q)

in O(n

d_{k}

r) if φ is a learned linear map plus elementwise nonlinearity (or O(n r

d_{k}

) for random projections). The key-value summary

S = K^{' T}

V costs O(n r

d_{v}

), and

z = K^{' T}

1 costs O(n r). Each query output requires O(r

d_{v}

) to compute

φ (q)^{T}

S and O(r) for the denominator. For a batch of n queries, this is O(n r

d_{v}

+ n r). Total time is therefore O(n

d_{k}

r + n r

d_{v}

), linear in n. Memory drops from O(

n^{2}

) to O(n r + r

d_{v}

) if we store Q', K' and S, or to O(r

d_{v}

) in causal/streaming mode where we discard past tokens after updating S and z. For multi-head attention with h heads, costs multiply by h but remain linear in n. Accuracy–efficiency trade-offs concentrate in r: larger r reduces kernel approximation error but increases compute. If r ≪ n and

d_{v}

is moderate, the asymptotic savings are substantial. Numerically, using nonnegative φ ensures denominators are positive; normalization keeps outputs bounded as n grows.

Code Examples

Reference: Naive Softmax Attention (O(n²))

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Utility: stable softmax over a vector
5 vector<double> softmax(const vector<double>& x) {
6     double m = *max_element(x.begin(), x.end());
7     double sum = 0.0;
8     vector<double> ex(x.size());
9     for (size_t i = 0; i < x.size(); ++i) {
10         ex[i] = exp(x[i] - m);
11         sum += ex[i];
12     }
13     for (double &v : ex) v /= (sum + 1e-12);
14     return ex;
15 }
16 
17 // Compute Y = softmax(QK^T / sqrt(dk)) V
18 // Shapes: Q[n][dk], K[n][dk], V[n][dv] -> Y[n][dv]
19 int main() {
20     ios::sync_with_stdio(false);
21     cin.tie(nullptr);
22 
23     int n = 4, dk = 3, dv = 2; // small demo sizes
24     vector<vector<double>> Q(n, vector<double>(dk));
25     vector<vector<double>> K(n, vector<double>(dk));
26     vector<vector<double>> V(n, vector<double>(dv));
27 
28     // Initialize with deterministic values for reproducibility
29     for (int i = 0; i < n; ++i) {
30         for (int j = 0; j < dk; ++j) {
31             Q[i][j] = (i + 1) * 0.1 + j * 0.01;
32             K[i][j] = (i + 2) * 0.05 + j * 0.02;
33         }
34         for (int j = 0; j < dv; ++j) {
35             V[i][j] = (i + 1) * 0.2 + j * 0.03;
36         }
37     }
38 
39     vector<vector<double>> Y(n, vector<double>(dv, 0.0));
40     double scale = 1.0 / sqrt((double)dk);
41 
42     // For each query, compute attention weights over all keys (O(n^2))
43     for (int i = 0; i < n; ++i) {
44         vector<double> scores(n, 0.0);
45         for (int j = 0; j < n; ++j) {
46             double dot = 0.0;
47             for (int t = 0; t < dk; ++t) dot += Q[i][t] * K[j][t];
48             scores[j] = dot * scale;
49         }
50         vector<double> w = softmax(scores);
51         for (int j = 0; j < n; ++j) {
52             for (int t = 0; t < dv; ++t) Y[i][t] += w[j] * V[j][t];
53         }
54     }
55 
56     // Print output
57     cout << fixed << setprecision(6);
58     for (int i = 0; i < n; ++i) {
59         for (int t = 0; t < dv; ++t) cout << Y[i][t] << (t+1==dv?'\n':' ');
60     }
61     return 0;
62 }
63

This baseline forms all n×n attention scores, applies a row-wise softmax to get weights, and multiplies by V. It is simple and exact for softmax attention but costs O(n²) in time and memory.

Time: O(n²(d_k + d_v))Space: O(n² + n(d_k + d_v))

Non-causal Linear Attention with ELU+1 Feature Map (O(n · r))

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Elementwise ELU(x) + 1 to ensure nonnegativity
5 inline double elu1(double x) {
6     return (x >= 0.0) ? (x + 1.0) : (exp(x) - 1.0 + 1.0);
7 }
8 
9 // Compute ϕ(X) = elu(WX + b) + 1 where W is (dk x r)
10 void feature_map(const vector<vector<double>>& X, // n x dk
11                  const vector<vector<double>>& W, // dk x r
12                  const vector<double>& b,         // r
13                  vector<vector<double>>& Xp) {    // n x r
14     int n = (int)X.size();
15     int dk = (int)X[0].size();
16     int r = (int)W[0].size();
17     Xp.assign(n, vector<double>(r, 0.0));
18     for (int i = 0; i < n; ++i) {
19         for (int j = 0; j < r; ++j) {
20             double s = b[j];
21             for (int t = 0; t < dk; ++t) s += X[i][t] * W[t][j];
22             Xp[i][j] = elu1(s);
23         }
24     }
25 }
26 
27 // Linear attention: Y = normalize( ϕ(Q) (ϕ(K)^T V) ) with denom per row ϕ(q)^T z
28 int main() {
29     ios::sync_with_stdio(false);
30     cin.tie(nullptr);
31 
32     int n = 5, dk = 4, dv = 3, r = 6; // demo sizes; choose r << n for big problems
33 
34     // Random-ish but deterministic parameters
35     vector<vector<double>> Q(n, vector<double>(dk)), K(n, vector<double>(dk)), V(n, vector<double>(dv));
36     for (int i = 0; i < n; ++i) {
37         for (int j = 0; j < dk; ++j) {
38             Q[i][j] = sin(0.1 * (i+1) * (j+1));
39             K[i][j] = cos(0.07 * (i+2) * (j+3));
40         }
41         for (int j = 0; j < dv; ++j) V[i][j] = 0.1 * (i+1) + 0.05 * j;
42     }
43 
44     // Feature map parameters Wq, Wk, bq, bk
45     vector<vector<double>> Wq(dk, vector<double>(r)), Wk(dk, vector<double>(r));
46     vector<double> bq(r), bk(r);
47     for (int i = 0; i < dk; ++i) {
48         for (int j = 0; j < r; ++j) {
49             Wq[i][j] = 0.2 * cos(0.3 * (i+1) * (j+1));
50             Wk[i][j] = 0.2 * sin(0.4 * (i+1) * (j+2));
51         }
52     }
53     for (int j = 0; j < r; ++j) { bq[j] = 0.01 * j; bk[j] = -0.02 * j; }
54 
55     // Compute transformed features ϕ(Q), ϕ(K)
56     vector<vector<double>> Qp, Kp;
57     feature_map(Q, Wq, bq, Qp); // n x r
58     feature_map(K, Wk, bk, Kp); // n x r
59 
60     // Compute S = ϕ(K)^T V  (r x dv) and z = ϕ(K)^T 1  (r)
61     vector<vector<double>> S(r, vector<double>(dv, 0.0));
62     vector<double> z(r, 0.0);
63     for (int i = 0; i < n; ++i) {
64         for (int a = 0; a < r; ++a) {
65             double kia = Kp[i][a];
66             z[a] += kia;
67             for (int b = 0; b < dv; ++b) S[a][b] += kia * V[i][b];
68         }
69     }
70 
71     // Output Y = row-wise (Qp * S) normalized by denom = Qp * z
72     vector<vector<double>> Y(n, vector<double>(dv, 0.0));
73     for (int i = 0; i < n; ++i) {
74         // denom = ϕ(q_i)^T z
75         double denom = 1e-12; // avoid divide-by-zero
76         for (int a = 0; a < r; ++a) denom += Qp[i][a] * z[a];
77         for (int b = 0; b < dv; ++b) {
78             double num = 0.0;
79             for (int a = 0; a < r; ++a) num += Qp[i][a] * S[a][b];
80             Y[i][b] = num / denom;
81         }
82     }
83 
84     cout << fixed << setprecision(6);
85     for (int i = 0; i < n; ++i) {
86         for (int b = 0; b < dv; ++b) cout << Y[i][b] << (b+1==dv?'\n':' ');
87     }
88     return 0;
89 }
90

This program implements non-causal linear attention using an ELU+1 feature map to ensure nonnegativity. It first computes key/value summaries S and z, then answers all queries without forming any n×n matrices. The result is exact for the chosen kernel defined by ϕ, not for softmax.

Time: O(n d_k r + n r d_v)Space: O(n r + r d_v)

Causal (Streaming) Linear Attention via Prefix Sums

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 inline double elu1(double x) { return (x >= 0.0) ? (x + 1.0) : (exp(x) - 1.0 + 1.0); }
5 
6 void feature_map_one(const vector<double>& x, const vector<vector<double>>& W, const vector<double>& b, vector<double>& out) {
7     int dk = (int)x.size();
8     int r = (int)W[0].size();
9     out.assign(r, 0.0);
10     for (int j = 0; j < r; ++j) {
11         double s = b[j];
12         for (int t = 0; t < dk; ++t) s += x[t] * W[t][j];
13         out[j] = elu1(s);
14     }
15 }
16 
17 int main() {
18     ios::sync_with_stdio(false);
19     cin.tie(nullptr);
20 
21     int n = 6, dk = 4, dv = 3, r = 5;
22     vector<vector<double>> K(n, vector<double>(dk));
23     vector<vector<double>> Q(n, vector<double>(dk));
24     vector<vector<double>> V(n, vector<double>(dv));
25 
26     for (int i = 0; i < n; ++i) {
27         for (int j = 0; j < dk; ++j) {
28             K[i][j] = 0.1 * cos(0.2 * (i+1) * (j+1));
29             Q[i][j] = 0.1 * sin(0.3 * (i+1) * (j+2));
30         }
31         for (int j = 0; j < dv; ++j) V[i][j] = 0.05 * (i+1 + j);
32     }
33 
34     vector<vector<double>> Wq(dk, vector<double>(r)), Wk(dk, vector<double>(r));
35     vector<double> bq(r), bk(r);
36     for (int i = 0; i < dk; ++i) for (int j = 0; j < r; ++j) {
37         Wq[i][j] = 0.15 * sin(0.1 * (i+1) * (j+1));
38         Wk[i][j] = 0.12 * cos(0.13 * (i+1) * (j+2));
39     }
40     for (int j = 0; j < r; ++j) { bq[j] = 0.0; bk[j] = 0.0; }
41 
42     // Running summaries for causal attention
43     vector<vector<double>> S(r, vector<double>(dv, 0.0)); // r x dv
44     vector<double> z(r, 0.0);                              // r
45 
46     vector<vector<double>> Y(n, vector<double>(dv, 0.0));
47     vector<double> qphi, kphi;
48 
49     for (int t = 0; t < n; ++t) {
50         // 1) Update summaries with current key/value (causal prefix)
51         feature_map_one(K[t], Wk, bk, kphi); // r
52         for (int a = 0; a < r; ++a) {
53             z[a] += kphi[a];
54             for (int b = 0; b < dv; ++b) S[a][b] += kphi[a] * V[t][b];
55         }
56         // 2) Answer query at t using current summaries
57         feature_map_one(Q[t], Wq, bq, qphi); // r
58         double denom = 1e-12;
59         for (int a = 0; a < r; ++a) denom += qphi[a] * z[a];
60         for (int b = 0; b < dv; ++b) {
61             double num = 0.0;
62             for (int a = 0; a < r; ++a) num += qphi[a] * S[a][b];
63             Y[t][b] = num / denom;
64         }
65     }
66 
67     cout << fixed << setprecision(6);
68     for (int i = 0; i < n; ++i) {
69         for (int b = 0; b < dv; ++b) cout << Y[i][b] << (b+1==dv?'\n':' ');
70     }
71     return 0;
72 }
73

This demonstrates causal linear attention. We process the sequence left-to-right, maintaining prefix summaries S_t and z_t. Each step updates summaries with the current key and value, then answers the current query using only O(r · d_v) work and O(r · d_v) memory, suitable for streaming inference.

Time: O(n d_k r + n r d_v) overall; O(d_k r + r d_v) per stepSpace: O(r d_v + r)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Utility: stable softmax over a vector
5	vector<double> softmax(const vector<double>& x) {
6	double m = *max_element(x.begin(), x.end());
7	double sum = 0.0;
8	vector<double> ex(x.size());
9	for (size_t i = 0; i < x.size(); ++i) {
10	ex[i] = exp(x[i] - m);
11	sum += ex[i];
12	}
13	for (double &v : ex) v /= (sum + 1e-12);
14	return ex;
15	}
16
17	// Compute Y = softmax(QK^T / sqrt(dk)) V
18	// Shapes: Q[n][dk], K[n][dk], V[n][dv] -> Y[n][dv]
19	int main() {
20	ios::sync_with_stdio(false);
21	cin.tie(nullptr);
22
23	int n = 4, dk = 3, dv = 2; // small demo sizes
24	vector<vector<double>> Q(n, vector<double>(dk));
25	vector<vector<double>> K(n, vector<double>(dk));
26	vector<vector<double>> V(n, vector<double>(dv));
27
28	// Initialize with deterministic values for reproducibility
29	for (int i = 0; i < n; ++i) {
30	for (int j = 0; j < dk; ++j) {
31	Q[i][j] = (i + 1) * 0.1 + j * 0.01;
32	K[i][j] = (i + 2) * 0.05 + j * 0.02;
33	}
34	for (int j = 0; j < dv; ++j) {
35	V[i][j] = (i + 1) * 0.2 + j * 0.03;
36	}
37	}
38
39	vector<vector<double>> Y(n, vector<double>(dv, 0.0));
40	double scale = 1.0 / sqrt((double)dk);
41
42	// For each query, compute attention weights over all keys (O(n^2))
43	for (int i = 0; i < n; ++i) {
44	vector<double> scores(n, 0.0);
45	for (int j = 0; j < n; ++j) {
46	double dot = 0.0;
47	for (int t = 0; t < dk; ++t) dot += Q[i][t] * K[j][t];
48	scores[j] = dot * scale;
49	}
50	vector<double> w = softmax(scores);
51	for (int j = 0; j < n; ++j) {
52	for (int t = 0; t < dv; ++t) Y[i][t] += w[j] * V[j][t];
53	}
54	}
55
56	// Print output
57	cout << fixed << setprecision(6);
58	for (int i = 0; i < n; ++i) {
59	for (int t = 0; t < dv; ++t) cout << Y[i][t] << (t+1==dv?'\n':' ');
60	}
61	return 0;
62	}
63

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Elementwise ELU(x) + 1 to ensure nonnegativity
5	inline double elu1(double x) {
6	return (x >= 0.0) ? (x + 1.0) : (exp(x) - 1.0 + 1.0);
7	}
8
9	// Compute ϕ(X) = elu(WX + b) + 1 where W is (dk x r)
10	void feature_map(const vector<vector<double>>& X, // n x dk
11	const vector<vector<double>>& W, // dk x r
12	const vector<double>& b, // r
13	vector<vector<double>>& Xp) { // n x r
14	int n = (int)X.size();
15	int dk = (int)X[0].size();
16	int r = (int)W[0].size();
17	Xp.assign(n, vector<double>(r, 0.0));
18	for (int i = 0; i < n; ++i) {
19	for (int j = 0; j < r; ++j) {
20	double s = b[j];
21	for (int t = 0; t < dk; ++t) s += X[i][t] * W[t][j];
22	Xp[i][j] = elu1(s);
23	}
24	}
25	}
26
27	// Linear attention: Y = normalize( ϕ(Q) (ϕ(K)^T V) ) with denom per row ϕ(q)^T z
28	int main() {
29	ios::sync_with_stdio(false);
30	cin.tie(nullptr);
31
32	int n = 5, dk = 4, dv = 3, r = 6; // demo sizes; choose r << n for big problems
33
34	// Random-ish but deterministic parameters
35	vector<vector<double>> Q(n, vector<double>(dk)), K(n, vector<double>(dk)), V(n, vector<double>(dv));
36	for (int i = 0; i < n; ++i) {
37	for (int j = 0; j < dk; ++j) {
38	Q[i][j] = sin(0.1 * (i+1) * (j+1));
39	K[i][j] = cos(0.07 * (i+2) * (j+3));
40	}
41	for (int j = 0; j < dv; ++j) V[i][j] = 0.1 * (i+1) + 0.05 * j;
42	}
43
44	// Feature map parameters Wq, Wk, bq, bk
45	vector<vector<double>> Wq(dk, vector<double>(r)), Wk(dk, vector<double>(r));
46	vector<double> bq(r), bk(r);
47	for (int i = 0; i < dk; ++i) {
48	for (int j = 0; j < r; ++j) {
49	Wq[i][j] = 0.2 * cos(0.3 * (i+1) * (j+1));
50	Wk[i][j] = 0.2 * sin(0.4 * (i+1) * (j+2));
51	}
52	}
53	for (int j = 0; j < r; ++j) { bq[j] = 0.01 * j; bk[j] = -0.02 * j; }
54
55	// Compute transformed features ϕ(Q), ϕ(K)
56	vector<vector<double>> Qp, Kp;
57	feature_map(Q, Wq, bq, Qp); // n x r
58	feature_map(K, Wk, bk, Kp); // n x r
59
60	// Compute S = ϕ(K)^T V (r x dv) and z = ϕ(K)^T 1 (r)
61	vector<vector<double>> S(r, vector<double>(dv, 0.0));
62	vector<double> z(r, 0.0);
63	for (int i = 0; i < n; ++i) {
64	for (int a = 0; a < r; ++a) {
65	double kia = Kp[i][a];
66	z[a] += kia;
67	for (int b = 0; b < dv; ++b) S[a][b] += kia * V[i][b];
68	}
69	}
70
71	// Output Y = row-wise (Qp * S) normalized by denom = Qp * z
72	vector<vector<double>> Y(n, vector<double>(dv, 0.0));
73	for (int i = 0; i < n; ++i) {
74	// denom = ϕ(q_i)^T z
75	double denom = 1e-12; // avoid divide-by-zero
76	for (int a = 0; a < r; ++a) denom += Qp[i][a] * z[a];
77	for (int b = 0; b < dv; ++b) {
78	double num = 0.0;
79	for (int a = 0; a < r; ++a) num += Qp[i][a] * S[a][b];
80	Y[i][b] = num / denom;
81	}
82	}
83
84	cout << fixed << setprecision(6);
85	for (int i = 0; i < n; ++i) {
86	for (int b = 0; b < dv; ++b) cout << Y[i][b] << (b+1==dv?'\n':' ');
87	}
88	return 0;
89	}
90

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	inline double elu1(double x) { return (x >= 0.0) ? (x + 1.0) : (exp(x) - 1.0 + 1.0); }
5
6	void feature_map_one(const vector<double>& x, const vector<vector<double>>& W, const vector<double>& b, vector<double>& out) {
7	int dk = (int)x.size();
8	int r = (int)W[0].size();
9	out.assign(r, 0.0);
10	for (int j = 0; j < r; ++j) {
11	double s = b[j];
12	for (int t = 0; t < dk; ++t) s += x[t] * W[t][j];
13	out[j] = elu1(s);
14	}
15	}
16
17	int main() {
18	ios::sync_with_stdio(false);
19	cin.tie(nullptr);
20
21	int n = 6, dk = 4, dv = 3, r = 5;
22	vector<vector<double>> K(n, vector<double>(dk));
23	vector<vector<double>> Q(n, vector<double>(dk));
24	vector<vector<double>> V(n, vector<double>(dv));
25
26	for (int i = 0; i < n; ++i) {
27	for (int j = 0; j < dk; ++j) {
28	K[i][j] = 0.1 * cos(0.2 * (i+1) * (j+1));
29	Q[i][j] = 0.1 * sin(0.3 * (i+1) * (j+2));
30	}
31	for (int j = 0; j < dv; ++j) V[i][j] = 0.05 * (i+1 + j);
32	}
33
34	vector<vector<double>> Wq(dk, vector<double>(r)), Wk(dk, vector<double>(r));
35	vector<double> bq(r), bk(r);
36	for (int i = 0; i < dk; ++i) for (int j = 0; j < r; ++j) {
37	Wq[i][j] = 0.15 * sin(0.1 * (i+1) * (j+1));
38	Wk[i][j] = 0.12 * cos(0.13 * (i+1) * (j+2));
39	}
40	for (int j = 0; j < r; ++j) { bq[j] = 0.0; bk[j] = 0.0; }
41
42	// Running summaries for causal attention
43	vector<vector<double>> S(r, vector<double>(dv, 0.0)); // r x dv
44	vector<double> z(r, 0.0); // r
45
46	vector<vector<double>> Y(n, vector<double>(dv, 0.0));
47	vector<double> qphi, kphi;
48
49	for (int t = 0; t < n; ++t) {
50	// 1) Update summaries with current key/value (causal prefix)
51	feature_map_one(K[t], Wk, bk, kphi); // r
52	for (int a = 0; a < r; ++a) {
53	z[a] += kphi[a];
54	for (int b = 0; b < dv; ++b) S[a][b] += kphi[a] * V[t][b];
55	}
56	// 2) Answer query at t using current summaries
57	feature_map_one(Q[t], Wq, bq, qphi); // r
58	double denom = 1e-12;
59	for (int a = 0; a < r; ++a) denom += qphi[a] * z[a];
60	for (int b = 0; b < dv; ++b) {
61	double num = 0.0;
62	for (int a = 0; a < r; ++a) num += qphi[a] * S[a][b];
63	Y[t][b] = num / denom;
64	}
65	}
66
67	cout << fixed << setprecision(6);
68	for (int i = 0; i < n; ++i) {
69	for (int b = 0; b < dv; ++b) cout << Y[i][b] << (b+1==dv?'\n':' ');
70	}
71	return 0;
72	}
73