ptr/models.py

"""Two small transformer architectures for pointer chasing.

PtrTransformer(S, d_model, n_heads, d_ff, depth):
  - `depth` pre-LN transformer blocks (GPT-2 style, bidirectional attention).
  - forward(f, x, k, n_iters): the SAME `depth` blocks are applied `n_iters`
    times, with a learned per-iteration step embedding added to the hidden
    state before each unroll. n_iters=1 -> conventional fixed-depth model.
    depth=1, n_iters=R -> classic weight-tied recurrent (looped) transformer.

Stability for long unrolls (Li et al. 2604.07822): zero-init the output
projections (attn_out, mlp_out) of every block so each block is the identity
at initialisation and gradients propagate cleanly through all unrolls.

Parameter/FLOP accounting lives in flops.py; the matched-budget logic is:
  per-step training FLOPs  ~  n_iters * depth * (block cost)
  parameter count          ~  depth * block params (+ shared embeddings/head)
"""

import math

import torch
import torch.nn as nn
import torch.nn.functional as F


class Block(nn.Module):
    def __init__(self, d_model, n_heads, d_ff, zero_init=True):
        super().__init__()
        assert d_model % n_heads == 0
        self.n_heads = n_heads
        self.d_model = d_model
        self.head_dim = d_model // n_heads
        self.ln1 = nn.LayerNorm(d_model)
        self.ln2 = nn.LayerNorm(d_model)
        self.qkv = nn.Linear(d_model, 3 * d_model)
        self.attn_out = nn.Linear(d_model, d_model)
        self.mlp_in = nn.Linear(d_model, d_ff)
        self.mlp_out = nn.Linear(d_ff, d_model)
        if zero_init:
            nn.init.zeros_(self.attn_out.weight)
            nn.init.zeros_(self.attn_out.bias)
            nn.init.zeros_(self.mlp_out.weight)
            nn.init.zeros_(self.mlp_out.bias)

    def forward(self, h):
        B, T, _ = h.shape
        q, k, v = self.qkv(self.ln1(h)).chunk(3, dim=-1)
        q = q.view(B, T, self.n_heads, self.head_dim).transpose(1, 2)
        k = k.view(B, T, self.n_heads, self.head_dim).transpose(1, 2)
        v = v.view(B, T, self.n_heads, self.head_dim).transpose(1, 2)
        att = (q @ k.transpose(-2, -1)) / math.sqrt(self.head_dim)
        att = att.softmax(dim=-1)
        o = (att @ v).transpose(1, 2).reshape(B, T, self.d_model)
        h = h + self.attn_out(o)
        h = h + self.mlp_out(F.gelu(self.mlp_in(self.ln2(h))))
        return h


class PtrTransformer(nn.Module):
    """Input sequence: [f(0..S-1), x, k]. Readout at the LAST position.

    f: LongTensor [B, S] of state ids; x: [B]; k: [B] (1-indexed hop count,
    embedded via a dedicated table of size K_MAX+2; k > 8 is OOD by design).
    """

    K_MAX = 64

    def __init__(self, S, d_model, n_heads, d_ff, depth, stem_depth=0,
                 max_len=None, zero_init=True):
        super().__init__()
        self.S = S
        self.depth = depth
        self.stem_depth = stem_depth
        self.d_model = d_model
        max_len = max_len or (S + 2)
        self.state_emb = nn.Embedding(S, d_model)
        self.pos_emb = nn.Embedding(max_len, d_model)
        self.k_emb = nn.Embedding(self.K_MAX + 2, d_model)
        # step embeddings must cover the largest unroll count used anywhere:
        # aligned variants evaluate at R = k + margin, up to 64 + 14
        self.step_emb = nn.Embedding(self.K_MAX + 2 + 14, d_model)
        # untied stem: applied ONCE before the recurrent loop (never unrolled)
        self.stem = nn.ModuleList(
            Block(d_model, n_heads, d_ff, zero_init=False)
            for _ in range(stem_depth)
        )
        self.blocks = nn.ModuleList(
            Block(d_model, n_heads, d_ff, zero_init=zero_init)
            for _ in range(depth)
        )
        self.ln_f = nn.LayerNorm(d_model)
        self.head = nn.Linear(d_model, S, bias=False)

    def forward(self, f, x, k, n_iters=1, return_all=False):
        B, S = f.shape
        T = S + 2
        tok = torch.cat(
            [self.state_emb(f),
             self.state_emb(x)[:, None, :],
             self.k_emb(k)[:, None, :]],
            dim=1,
        )
        pos = torch.arange(T, device=f.device)
        h = tok + self.pos_emb(pos)[None]
        for blk in self.stem:
            h = blk(h)
        outs = []
        for t in range(n_iters):
            step = torch.full((B,), t, device=f.device, dtype=torch.long)
            h = h + self.step_emb(step)[:, None, :]
            for blk in self.blocks:
                h = blk(h)
            if return_all:
                outs.append(self.head(self.ln_f(h[:, -1])))
        logits = self.head(self.ln_f(h[:, -1]))
        if return_all:
            return logits, torch.stack(outs, dim=1)  # [B, n_iters, S]
        return logits


def build_model(arch, S=64, d_model=128, n_heads=4, d_ff=512, depth=4,
                stem_depth=0, zero_init=True, **_):
    """arch 'fixed' -> depth blocks applied once.
    arch 'rec'    -> same blocks applied n_iters times (chosen at call time)."""
    return PtrTransformer(S, d_model, n_heads, d_ff, depth,
                          stem_depth=stem_depth, zero_init=zero_init)