# ========================================
# TRANSFORMER ALGORITHM (Decoder-Only)
# ========================================
def transformer_forward(input_ids, past_kv=None):
    """
    DSA: Arrays, Hashing, Graphs, DP (KV Cache)
    """
    # 1. Token → Embedding (O(V) → O(d) via Hash Map)
    x = embedding_lookup(input_ids) * sqrt(d_model)

    # 2. Add Positional Encoding (Deterministic Hash: pos → vector)
    x = x + positional_encoding(seq_len)

    # 3. For each layer: Attention + FFN
    new_kv_cache = []
    for layer in transformer_layers:
        # === SELF-ATTENTION (Graph Algorithm) ===
        Q, K, V = linear_project(x)           # O(n * d)
        scores = matmul(Q, K.T) / sqrt(d_k)    # O(n²) → Adjacency Matrix
        mask = causal_triangle_mask()         # Lower triangular
        probs = softmax(scores + mask)
        context = matmul(probs, V)            # Weighted sum

        x = residual_add(x, context)
        x = layer_norm(x)

        # === FEEDFORWARD (Dense Array Ops) ===
        x = residual_add(x, ffn(x))
        x = layer_norm(x)

        # Cache K, V for next token (DP Memoization)
        new_kv_cache.append((K, V))

    # 4. Final LM Head
    logits = linear(x, vocab_size)
    return logits, new_kv_cache

# Task: Implement matmul from scratch
def matmul(A, B):
    return [[sum(a*b for a,b in zip(row, col)) 
             for col in zip(*B)] for row in A]

def scaled_dot_product_attention(Q, K, V, mask=None):
    d_k = Q.size(-1)
    scores = Q @ K.transpose(-2,-1) / sqrt(d_k)  # Graph weights
    if mask: scores = scores.masked_fill(mask == 0, -inf)
    probs = softmax(scores)
    return probs @ V

# DSA: Parallel Processing (like MapReduce)
heads = [attention_head_i(x) for i in range(h)]
output = concat(heads) @ W_o

# Hash Function: position → unique vector
pe[pos, 2i]   = sin(pos / 10000^{2i/d})
pe[pos, 2i+1] = cos(pos / 10000^{2i/d})

class MiniGPT(nn.Module):
    def __init__(self, vocab=1000, d_model=64, n_layer=4):
        self.token_emb = nn.Embedding(vocab, d_model)
        self.pos_emb = nn.Parameter(torch.zeros(1, 128, d_model))
        self.blocks = nn.ModuleList([Block() for _ in range(n_layer)])
        self.ln_f = nn.LayerNorm(d_model)
        self.head = nn.Linear(d_model, vocab)

# Before: O(n²) per token
# After: O(n) per token → 100x faster!
if past_kv is not None:
    past_k, past_v = past_kv
    K = torch.cat([past_k, K], dim=1)
    V = torch.cat([past_v, V], dim=1)

import heapq
heap = []  # (score, sequence)
heapq.heappush(heap, (-prob, [token]))
best = heapq.nsmallest(k, heap)

def get_stats(ids):
    counts = {}
    for pair in zip(ids, ids[1:]):
        counts[pair] = counts.get(pair, 0) + 1
    return counts  # Hash Map

TRANSFORMER = Embedding
            + Positional Encoding
            + N × (MultiHeadAttention + FFN + Residual + LayerNorm)
            + LM Head

ATTENTION(Q,K,V) = softmax(QK^T / √d_k) × V

GENERATION:
  while not EOS:
      logits, kv_cache = model(token, kv_cache)
      token = sample(logits)

DSA MAP:
  Token → Hash Map
  Position → Sinusoid Hash
  Attention → Graph
  KV Cache → DP Memo
  Beam → Min-Heap
  BPE → Trie + Greedy