NLP: Self-attention over a sentence

Compute scaled dot-product self-attention, with or without a causal mask.

What to build

A program that prints each token's attention weights and output vector.

Requirements

  • Each token's vector serves as its query, key and value. For token i, score every visible token j as (xᵢ · xⱼ) ÷ √d, where d is the vector length, and turn the visible scores into weights with softmax. Masked tokens get weight 0.
  • In full mode every token is visible; in causal mode only tokens 0 to i are.
  • The output of token i is the sum over j of weight(i, j) × xⱼ. Print token: weights w0 w1 ... -> out o1 o2 ..., all numbers to three decimal places, with a weight for every position.

Input

Line 1: n and the mode (full or causal). Then n lines: a token and its d numbers.

Output

n lines.

Constraints

n ≤ 50; d ≤ 64.

Example

Input:

3 full
the 1 0
cat 0 1
sat 1 1

Output:

the: weights 0.401 0.198 0.401 -> out 0.802 0.599
cat: weights 0.198 0.401 0.401 -> out 0.599 0.802
sat: weights 0.248 0.248 0.503 -> out 0.752 0.752

Why it works

Softmax over the scaled similarities gives each token a probability distribution over the tokens it may see, so its output is a weighted average that leans towards the most similar tokens, and the mask simply removes later tokens from that average.

Examples

Example 1 · Input
3 full
the 1 0
cat 0 1
sat 1 1
Expected output
the: weights 0.401 0.198 0.401 -> out 0.802 0.599
cat: weights 0.198 0.401 0.401 -> out 0.599 0.802
sat: weights 0.248 0.248 0.503 -> out 0.752 0.752
Example 2 · Input
3 causal
the 1 0
cat 0 1
sat 1 1
Expected output
the: weights 1.000 0.000 0.000 -> out 1.000 0.000
cat: weights 0.330 0.670 0.000 -> out 0.330 0.670
sat: weights 0.248 0.248 0.503 -> out 0.752 0.752

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For token i, the visible positions are all positions in `full` mode and 0 to i in `causal` mode.

Hint 2

Score = dot product ÷ `math.sqrt(d)`; softmax the visible scores (subtracting the maximum), give masked positions weight 0, then average the vectors with the weights.

Solution

Show one correct solution (try it yourself first)
import math

n, mode = input().split()
rows = [input().split() for _ in range(int(n))]
tokens = [r[0] for r in rows]
x = [[float(v) for v in r[1:]] for r in rows]
d = len(x[0])
for i, q in enumerate(x):
    visible = range(i + 1) if mode == "causal" else range(len(x))
    scores = [sum(a * b for a, b in zip(q, x[j])) / math.sqrt(d) for j in visible]
    top = max(scores)
    e = [math.exp(s - top) for s in scores]
    total = sum(e)
    weights = [v / total for v in e] + [0.0] * (len(x) - len(e))
    out = [sum(weights[j] * x[j][c] for j in range(len(x))) for c in range(d)]
    print(f"{tokens[i]}: weights {' '.join(f'{w:.3f}' for w in weights)} -> out {' '.join(f'{o:.3f}' for o in out)}")

Lesson: Attention, transformers and LLMs in practice →