File size: 5,079 Bytes
c0045c8 90b2784 c0045c8 90b2784 c0045c8 9fbe83d 90b2784 c0045c8 90b2784 c0045c8 90b2784 c0045c8 90b2784 c0045c8 90b2784 c0045c8 90b2784 c0045c8 90b2784 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 | """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) |