Deep learning: Causal self-attention

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), then output: 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))

Lesson: Attention →