Transformer Expressiveness

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Numerically 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> exps(x.size());
9
    for (size_t i = 0; i < x.size(); ++i) {
10
        exps[i] = exp(x[i] - m);
11
        sum += exps[i];
12
    }
13
    for (size_t i = 0; i < x.size(); ++i) exps[i] /= max(sum, 1e-300);
14
    return exps;
15
}
16
17
// Sinusoidal positional encoding of dimension d_model for position pos
18
vector<double> sinusoidal_positional_encoding(int pos, int d_model) {
19
    vector<double> pe(d_model, 0.0);
20
    for (int i = 0; i < d_model; i += 2) {
21
        double denom = pow(10000.0, (double)i / d_model);
22
        pe[i] = sin(pos / denom);
23
        if (i + 1 < d_model) pe[i + 1] = cos(pos / denom);
24
    }
25
    return pe;
26
}
27
28
// Simple linear layer: y = x W + b; shapes: x(1xd_in), W(d_in x d_out)
29
vector<double> linear(const vector<double>& x, const vector<vector<double>>& W, const vector<double>& b) {
30
    int d_in = (int)W.size();
31
    int d_out = (int)W[0].size();
32
    vector<double> y(d_out, 0.0);
33
    for (int j = 0; j < d_out; ++j) {
34
        double s = b[j];
35
        for (int i = 0; i < d_in; ++i) s += x[i] * W[i][j];
36
        y[j] = s;
37
    }
38
    return y;
39
}
40
41
// Dot product
42
inline double dot(const vector<double>& a, const vector<double>& b) {
43
    double s = 0.0; for (size_t i = 0; i < a.size(); ++i) s += a[i] * b[i]; return s;
44
}
45
46
// Self-attention forward pass (single head) with optional relative position bias
47
// X: L x d_model token embeddings; returns L x d_v outputs
48
vector<vector<double>> self_attention_single_head(
49
    const vector<vector<double>>& X,
50
    const vector<vector<double>>& Wq,
51
    const vector<vector<double>>& Wk,
52
    const vector<vector<double>>& Wv,
53
    const vector<double>& bq,
54
    const vector<double>& bk,
55
    const vector<double>& bv,
56
    const vector<vector<double>>& rel_bias // L x L positional bias (can be all zeros)
57
) {
58
    int L = (int)X.size();
59
    int d_model = (int)X[0].size();
60
    int d_k = (int)Wq[0].size(); // also Wk[0].size()
61
    int d_v = (int)Wv[0].size();
62
63
    vector<vector<double>> Q(L), K(L), V(L);
64
    for (int i = 0; i < L; ++i) {
65
        Q[i] = linear(X[i], Wq, bq);
66
        K[i] = linear(X[i], Wk, bk);
67
        V[i] = linear(X[i], Wv, bv);
68
    }
69
70
    // Compute attention outputs
71
    vector<vector<double>> Z(L, vector<double>(d_v, 0.0));
72
    double scale = 1.0 / sqrt((double)d_k);
73
    for (int i = 0; i < L; ++i) {
74
        vector<double> logits(L, 0.0);
75
        for (int j = 0; j < L; ++j) {
76
            logits[j] = dot(Q[i], K[j]) * scale + rel_bias[i][j];
77
        }
78
        vector<double> a = softmax(logits); // attention weights over j
79
        for (int j = 0; j < L; ++j) {
80
            for (int c = 0; c < d_v; ++c) Z[i][c] += a[j] * V[j][c];
81
        }
82
    }
83
    return Z;
84
}
85
86
int main() {
87
    // Example: 4 tokens, model dim 6
88
    int L = 4, d_model = 6, d_k = 4, d_v = 4;
89
90
    // Toy token embeddings (could be outputs of an embedding layer)
91
    vector<vector<double>> tokens(L, vector<double>(d_model, 0.0));
92
    // Put simple numeric content in first coordinate, rest zeros; add positional encodings
93
    vector<double> contents = {1.0, 2.0, 3.0, 4.0};
94
    for (int i = 0; i < L; ++i) {
95
        tokens[i][0] = contents[i];
96
        vector<double> pe = sinusoidal_positional_encoding(i, d_model);
97
        for (int k = 0; k < d_model; ++k) tokens[i][k] += 0.1 * pe[k]; // small positional signal
98
    }
99
100
    // Initialize small random weights for Q,K,V (fixed seed for reproducibility)
101
    std::mt19937 gen(42);
102
    std::normal_distribution<double> nd(0.0, 0.2);
103
    auto rand_matrix = [&](int r, int c){
104
        vector<vector<double>> W(r, vector<double>(c));
105
        for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) W[i][j] = nd(gen);
106
        return W;
107
    };
108
    auto rand_bias = [&](int c){ vector<double> b(c, 0.0); return b; };
109
110
    vector<vector<double>> Wq = rand_matrix(d_model, d_k);
111
    vector<vector<double>> Wk = rand_matrix(d_model, d_k);
112
    vector<vector<double>> Wv = rand_matrix(d_model, d_v);
113
    vector<double> bq = rand_bias(d_k), bk = rand_bias(d_k), bv = rand_bias(d_v);
114
115
    // No relative bias in this basic example
116
    vector<vector<double>> rel_bias(L, vector<double>(L, 0.0));
117
118
    auto Z = self_attention_single_head(tokens, Wq, Wk, Wv, bq, bk, bv, rel_bias);
119
120
    cout << fixed << setprecision(4);
121
    cout << "Self-attention outputs (one head):\n";
122
    for (int i = 0; i < L; ++i) {
123
        cout << "pos " << i << ": ";
124
        for (double v : Z[i]) cout << v << ' ';
125
        cout << '\n';
126
    }
127
    return 0;
128
}
129

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
vector<double> softmax(const vector<double>& x) {
5
    double m = *max_element(x.begin(), x.end());
6
    double sum = 0.0; vector<double> e(x.size());
7
    for (size_t i = 0; i < x.size(); ++i) { e[i] = exp(x[i] - m); sum += e[i]; }
8
    for (double &v : e) v /= max(sum, 1e-300);
9
    return e;
10
}
11
12
// Reverse via attention: set logits to a very large value at j = L-1-i and small elsewhere.
13
// This mimics a Transformer head with a strong relative position bias.
14
int main() {
15
    int L = 6; // sequence length
16
    vector<vector<double>> V(L, vector<double>(1, 0.0)); // values hold the content (scalar per token)
17
    for (int i = 0; i < L; ++i) V[i][0] = (double)(i + 1); // contents: 1,2,3,4,5,6
18
19
    // Build relative bias matrix B where B[i][j] is large if j == L-1-i
20
    double big = 50.0; // large scale -> softmax ~ one-hot
21
    vector<vector<double>> B(L, vector<double>(L, -10.0)); // small baseline elsewhere
22
    for (int i = 0; i < L; ++i) {
23
        int j_star = L - 1 - i;
24
        B[i][j_star] = big;
25
    }
26
27
    // Attention weights for each query position i
28
    vector<vector<double>> A(L, vector<double>(L));
29
    for (int i = 0; i < L; ++i) A[i] = softmax(B[i]);
30
31
    // Output Z = A V (here d_v=1, so it's just a weighted sum of scalars)
32
    vector<double> Z(L, 0.0);
33
    for (int i = 0; i < L; ++i) {
34
        for (int j = 0; j < L; ++j) Z[i] += A[i][j] * V[j][0];
35
    }
36
37
    cout << fixed << setprecision(6);
38
    cout << "Input:  "; for (int i = 0; i < L; ++i) cout << V[i][0] << ' '; cout << '\n';
39
    cout << "Output: "; for (int i = 0; i < L; ++i) cout << Z[i] << ' '; cout << '\n';
40
41
    // Show how close to exact reversal we are by comparing to reversed sequence
42
    cout << "Target: "; for (int i = 0; i < L; ++i) cout << (double)(L - i) << ' '; cout << '\n';
43
44
    double max_err = 0.0;
45
    for (int i = 0; i < L; ++i) max_err = max(max_err, fabs(Z[i] - (double)(L - i)));
46
    cout << "Max abs error: " << max_err << '\n';
47
    return 0;
48
}
49

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute the sum of a sequence via attention: a special query attends uniformly to all tokens.
5
int main() {
6
    int L = 5; // number of tokens
7
    // Values hold 2D features; here we only use the first dim as numbers to sum
8
    vector<vector<double>> V = {{1.0, 0.0}, {2.0, 0.0}, {3.0, 0.0}, {4.0, 0.0}, {5.0, 0.0}};
9
10
    // A single query (CLS) with zero logits to every key -> uniform softmax
11
    vector<double> logits(L, 0.0);
12
    // Numerically stable softmax of zeros is uniform 1/L
13
    vector<double> A(L, 1.0 / L);
14
15
    // Z = sum_j A_j * V_j is the mean; multiply by L to get sum
16
    vector<double> Z(2, 0.0);
17
    for (int j = 0; j < L; ++j) {
18
        Z[0] += A[j] * V[j][0];
19
        Z[1] += A[j] * V[j][1];
20
    }
21
    double mean_first = Z[0];
22
    double sum_first = mean_first * L; // emulate an FFN that scales by L
23
24
    cout << fixed << setprecision(4);
25
    cout << "Numbers:        "; for (int j = 0; j < L; ++j) cout << V[j][0] << ' '; cout << '\n';
26
    cout << "Uniform weights: "; for (int j = 0; j < L; ++j) cout << A[j] << ' '; cout << '\n';
27
    cout << "Mean (first dim): " << mean_first << '\n';
28
    cout << "Sum   (first dim): " << sum_first << '\n';
29
    return 0;
30
}
31