Compute the masked self-attention used by text-generating models.
What to build
A program that applies causal self-attention to a sequence of vectors.
Requirements
- Use the input rows as queries, keys and values. Position i attends to positions 0 … i with weights softmax(xᵢ · xⱼ / √d); later positions get weight 0.
- Print
weights:and n rows of n weights (masked entries as 0.0000), thenoutput:and n output rows, all with four decimal places.
Input
Line 1: n and d. Then n rows of d numbers.
Output
weights:, n rows, output:, n rows.
Constraints
n ≤ 50; d ≤ 20.
Example
Input:
3 2
1 0
0 1
1 1
Output:
weights:
1.0000 0.0000 0.0000
0.3302 0.6698 0.0000
0.2483 0.2483 0.5035
output:
1.0000 0.0000
0.3302 0.6698
0.7517 0.7517
Why it works
A model that predicts the next token must not use tokens it has not produced yet, so each position only mixes in itself and what came before it.
Examples
Example 1 · Input
3 2 1 0 0 1 1 1
Expected output
weights: 1.0000 0.0000 0.0000 0.3302 0.6698 0.0000 0.2483 0.2483 0.5035 output: 1.0000 0.0000 0.3302 0.6698 0.7517 0.7517
Example 2 · Input
1 2 5 5
Expected output
weights: 1.0000 output: 5.0000 5.0000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For position i, compute scores only against positions 0 … i; the later positions get weight 0.
Hint 2
Queries, keys and values are all the input rows themselves in this exercise.
Solution
Show one correct solution (try it yourself first)
import math
n, d = map(int, input().split())
X = [list(map(float, input().split())) for _ in range(n)]
weights_rows, outputs = [], []
for i in range(n):
scores = [sum(a * b for a, b in zip(X[i], X[j])) / math.sqrt(d) for j in range(i + 1)]
top = max(scores)
e = [math.exp(s - top) for s in scores]
w = [v / sum(e) for v in e]
weights_rows.append(w + [0.0] * (n - i - 1))
outputs.append([sum(w[j] * X[j][c] for j in range(i + 1)) for c in range(d)])
print("weights:")
for row in weights_rows:
print(" ".join(f"{v:.4f}" for v in row))
print("output:")
for row in outputs:
print(" ".join(f"{v + 0.0:.4f}" for v in row))