"""Lesson 1 check: DeepSeek Sparse Attention on a six-token toy example.

Every number printed here appears in lesson-01-deepseek-sparse-attention.md.
Run:  python3 lesson01_check.py
"""
import torch

torch.set_printoptions(precision=4, sci_mode=False)

TOKENS = ["The", "next", "day", "is", "bright", "and"]

# Hidden states entering the attention layer, shape (6, 4)
H = torch.tensor([
    [ 1., 0., 0., 1.],   # The
    [ 0., 1., 1., 0.],   # next
    [ 2., 1., 0., 0.],   # day
    [-1., 0., 1., 1.],   # is
    [ 1., 2., 1., 0.],   # bright
    [ 1., 1., 0., 1.],   # and
])

# Indexer weights: 2 heads, 2 dimensions per head
W_q = torch.tensor([[1., 0., 0., 0.],
                    [0., 0., 0., 1.],
                    [0., 0., 0., 0.],
                    [0., 0., 0., 0.]])        # (4, 4): 2 heads x 2 dims
W_k = torch.tensor([[1., 0.],
                    [0., 1.],
                    [0., 0.],
                    [0., 0.]])                # (4, 2): one small key per token
W_w = torch.tensor([[0.5, 0.],
                    [0., 0.],
                    [0., 0.],
                    [0., 1.]])                # (4, 2): one weight per head


def lightning_indexer(H, W_q, W_k, W_w, n_heads, k):
    T = H.shape[0]
    d_i = W_k.shape[1]
    q = (H @ W_q).view(T, n_heads, d_i)                        # A
    keys = H @ W_k                                             # B
    w = H @ W_w                                                # C
    dots = torch.einsum("thd,sd->ths", q, keys)                # D
    scores = (w.unsqueeze(-1) * torch.relu(dots)).sum(dim=1)   # E
    causal = torch.triu(torch.ones(T, T), diagonal=1).bool()
    scores = scores.masked_fill(causal, float("-inf"))         # F
    topk = scores.topk(min(k, T), dim=-1).indices              # G
    index_mask = torch.full((T, T), float("-inf"))
    index_mask.scatter_(-1, topk, 0.0)                         # H
    index_mask = index_mask.masked_fill(causal, float("-inf"))
    return q, keys, w, dots, scores, index_mask


q, keys, w, dots, scores, index_mask = lightning_indexer(H, W_q, W_k, W_w, 2, 3)

t = 5  # the query token "and"
print("Indexer keys K_I (6, 2):\n", keys)
print("Query vectors for 'and', one row per head:\n", q[t])
print("Head weights for 'and':", w[t])
print("Dot products for 'and' (2 heads x 6 tokens):\n", dots[t])
print("After ReLU:\n", torch.relu(dots[t]))
print("Index scores for 'and':", scores[t])
print("Index mask for 'and':", index_mask[t])

print("\nSelection pattern for all six rows (1 = kept):")
print((index_mask == 0).int())

# Main attention for "and". The six scores stand for what MLA from chapter 3
# would produce (already scaled). Values have 2 dimensions.
attn_scores = torch.tensor([0.2, 0.5, 2.0, -1.0, 2.4, 1.6])
V = torch.tensor([[1., 0.], [0., 1.], [2., 2.], [1., 1.], [4., 0.], [0., 2.]])

dense_w = torch.softmax(attn_scores, dim=-1)
sparse_w = torch.softmax(attn_scores + index_mask[t], dim=-1)
print("\nexp of each score:", torch.exp(attn_scores), "sum", torch.exp(attn_scores).sum())
print("Dense attention weights: ", dense_w)
print("Sparse attention weights:", sparse_w)
print("Dense weight on the 3 kept tokens:", dense_w[index_mask[t] == 0].sum())
print("Dense context vector: ", dense_w @ V)
print("Sparse context vector:", sparse_w @ V)

# Cost at real scale
L, k = 128_000, 2048
dense_pairs = L * (L + 1) // 2
sparse_pairs = k * (k + 1) // 2 + (L - k) * k
print("\nL =", L, " k =", k)
print("Last token, dense entries:", L, " sparse entries:", k, " ratio:", L / k)
print("Whole sequence, dense pairs: ", f"{dense_pairs:,}")
print("Whole sequence, sparse pairs:", f"{sparse_pairs:,}")
print("Ratio:", round(dense_pairs / sparse_pairs, 2))
