"""The n-gram embedding table: file format, builder, and the module. The idea. A dense transformer has to reconstruct "New York City" or "in accordance with" out of its weights every time it sees one. This table is keyed on the literal last two or three token ids, so the model can retrieve a learned vector for that specific phrase instead. It holds 15M parameters and costs one gather per position -- no matmul, so compute per token barely moves. Explicit top-K, never hashing. A row belongs to one specific (t-1, t) or (t-2, t-1, t); anything outside the top-K falls to a single shared OOV row. Hashed buckets would let two unrelated phrases share a vector, which silently changes what is being measured. Layout is chosen for the gather. Row indices are assigned in descending corpus frequency, so the rows a batch actually touches are clustered at the head of the table: rank 64 in fp32 is 256 bytes, and the top ~24k rows fit in the V100's 6MB L2. Assigning row indices by n-gram id instead would scatter every batch across the full 60MB table, and the gather is bandwidth-bound. The file. `ngram_vocab.bin` maps n-gram to row index as two sorted key arrays with parallel row arrays: header (64 bytes) bigram_keys int64[n_bigram] sorted ascending, key = a*V + b bigram_rows int32[n_bigram] trigram_keys int64[n_trigram] sorted ascending, key = (a*V + b)*V + c trigram_rows int32[n_trigram] Lookup is torch.searchsorted plus an equality check -- exact, no probe loop, and a miss is a miss rather than a collision. Trigram keys peak at V^3 = 3.5e13 for V = 32,768, comfortably inside int64. python ngram.py build --shards data/shards --out data/ngram_vocab.bin """ from __future__ import annotations import argparse import struct import sys import time from dataclasses import dataclass from pathlib import Path import numpy as np import torch import torch.nn as nn MAGIC = b"BNGRAM2\0" HEADER_FMT = "<8sIIQQ" # magic, version, vocab, n_bi, n_tri HEADER_SIZE = 64 VERSION = 2 @dataclass class NGramVocab: vocab_size: int bigram_keys: np.ndarray bigram_rows: np.ndarray trigram_keys: np.ndarray trigram_rows: np.ndarray def save(self, path: Path) -> None: path = Path(path) path.parent.mkdir(parents=True, exist_ok=True) head = struct.pack(HEADER_FMT, MAGIC, VERSION, self.vocab_size, self.bigram_keys.size, self.trigram_keys.size) with open(path, "wb") as f: f.write(head + b"\0" * (HEADER_SIZE - len(head))) for a in (self.bigram_keys.astype(np.int64), self.bigram_rows.astype(np.int32), self.trigram_keys.astype(np.int64), self.trigram_rows.astype(np.int32)): f.write(a.tobytes()) @staticmethod def load(path: Path) -> "NGramVocab": path = Path(path) with open(path, "rb") as f: head = f.read(HEADER_SIZE) magic, ver, vocab, nb, nt = struct.unpack(HEADER_FMT, head[:struct.calcsize(HEADER_FMT)]) if magic != MAGIC: raise ValueError(f"{path}: not an ngram vocab file") if ver != VERSION: raise ValueError(f"{path}: version {ver}, expected {VERSION}") parts = (f.read(nb * 8), f.read(nb * 4), f.read(nt * 8), f.read(nt * 4)) if tuple(map(len, parts)) != (nb * 8, nb * 4, nt * 8, nt * 4): raise ValueError(f"{path}: truncated n-gram vocabulary") if f.read(1): raise ValueError(f"{path}: trailing data after n-gram vocabulary") bk = np.frombuffer(parts[0], dtype=np.int64) br = np.frombuffer(parts[1], dtype=np.int32) tk = np.frombuffer(parts[2], dtype=np.int64) tr = np.frombuffer(parts[3], dtype=np.int32) if ((bk.size > 1 and np.any(bk[1:] <= bk[:-1])) or (tk.size > 1 and np.any(tk[1:] <= tk[:-1]))): raise ValueError(f"{path}: keys are not strictly increasing") return NGramVocab(vocab, bk, br, tk, tr) def fingerprint(self) -> str: import hashlib h = hashlib.sha256() for a in (self.bigram_keys, self.bigram_rows, self.trigram_keys, self.trigram_rows): # The mapping file is only a few MB. Hashing just the first MB let a # changed tail pass the resume guard while assigning learned rows to # different phrases. h.update(np.ascontiguousarray(a).tobytes()) h.update(str(a.size).encode()) return h.hexdigest()[:16] def legacy_fingerprint(self) -> str: """Fingerprint written by checkpoints before the full-file hash fix.""" import hashlib h = hashlib.sha256() for a in (self.bigram_keys, self.bigram_rows, self.trigram_keys, self.trigram_rows): h.update(np.ascontiguousarray(a).tobytes()[:1 << 20]) h.update(str(a.size).encode()) return h.hexdigest()[:16] # --------------------------------------------------------------------------- # # Module # --------------------------------------------------------------------------- # class NGramTable(nn.Module): """Lookup on (t-1, t) and (t-2, t-1, t), projected into the residual stream. Trigram wins where both hit: it is the more specific key. Positions whose history would cross a packed document boundary fall to the OOV row, for the same reason Canon is masked there -- the previous document is not context. """ def __init__(self, cfg, d_model: int): super().__init__() self.cfg = cfg self.d_model = d_model self.table = nn.Parameter(torch.empty(cfg.n_rows, cfg.rank)) self.proj = nn.Parameter(torch.empty(d_model, cfg.rank)) nn.init.normal_(self.table, std=cfg.table_init_std) nn.init.normal_(self.proj, std=cfg.proj_init_std) self.table._boris_role = "ngram_table" # a gather, never Muon self.proj._boris_role = "matmul" if cfg.muon_on_proj else "ngram_table" # Empty until load_vocab(); registered so they move with .to(device) # and are excluded from the checkpoint (they live in ngram_vocab.bin, # whose fingerprint is asserted at resume). self.register_buffer("bigram_keys", torch.zeros(0, dtype=torch.int64), persistent=False) self.register_buffer("bigram_rows", torch.zeros(0, dtype=torch.int64), persistent=False) self.register_buffer("trigram_keys", torch.zeros(0, dtype=torch.int64), persistent=False) self.register_buffer("trigram_rows", torch.zeros(0, dtype=torch.int64), persistent=False) self.vocab_size = 0 self.loaded = False def load_vocab(self, vocab: NGramVocab, device=None) -> None: dev = device or self.table.device self.bigram_keys = torch.from_numpy(vocab.bigram_keys.copy()).to(dev) self.bigram_rows = torch.from_numpy(vocab.bigram_rows.astype(np.int64)).to(dev) self.trigram_keys = torch.from_numpy(vocab.trigram_keys.copy()).to(dev) self.trigram_rows = torch.from_numpy(vocab.trigram_rows.astype(np.int64)).to(dev) self.vocab_size = int(vocab.vocab_size) n = self.cfg.n_rows hi = max(int(self.bigram_rows.max()) if self.bigram_rows.numel() else -1, int(self.trigram_rows.max()) if self.trigram_rows.numel() else -1) assert hi < n, ( f"ngram_vocab.bin holds row index {hi}, the configured table has " f"{n} rows") self.loaded = True @staticmethod def _lookup(keys, rows, query, oov: int): """Exact sorted lookup: searchsorted + equality, one fused kernel.""" if keys.numel() == 0: return torch.full_like(query, oov) i = torch.searchsorted(keys, query.clamp_min(0)) i = i.clamp_max(keys.numel() - 1) hit = keys[i] == query return torch.where(hit, rows[i], torch.full_like(query, oov)) def forward(self, idx, boundary, dtype): if not self.loaded: raise RuntimeError("NGramTable.load_vocab() was never called") B, T = idx.shape V = self.vocab_size oov = self.cfg.oov_row i0 = idx.to(torch.int64) i1 = torch.roll(i0, 1, dims=1) i2 = torch.roll(i0, 2, dims=1) # Same masks Canon uses: t-1 present, and t-2 present. ok1 = ~boundary ok2 = ~(boundary | torch.roll(boundary, 1, dims=1)) ok1[:, 0] = False ok2[:, :2] = False bi_key = torch.where(ok1, i1 * V + i0, torch.full_like(i0, -1)) tri_key = torch.where(ok2, (i2 * V + i1) * V + i0, torch.full_like(i0, -1)) row = self._lookup(self.bigram_keys, self.bigram_rows, bi_key, oov) tri = self._lookup(self.trigram_keys, self.trigram_rows, tri_key, oov) row = torch.where(tri != oov, tri, row) # trigram is more specific vec = torch.nn.functional.embedding(row, self.table) # (B, T, rank) return torch.nn.functional.linear(vec.to(dtype), self.proj.to(dtype)) @torch.no_grad() def hit_rate(self, idx, boundary) -> dict: """Fraction of positions served by a real row -- logged at startup and periodically; a collapse here means the table has stopped earning its parameters.""" B, T = idx.shape V, oov = self.vocab_size, self.cfg.oov_row i0 = idx.to(torch.int64) i1, i2 = torch.roll(i0, 1, 1), torch.roll(i0, 2, 1) ok1 = ~boundary.clone(); ok1[:, 0] = False ok2 = ~(boundary | torch.roll(boundary, 1, 1)); ok2[:, :2] = False bi = self._lookup(self.bigram_keys, self.bigram_rows, torch.where(ok1, i1 * V + i0, torch.full_like(i0, -1)), oov) tri = self._lookup(self.trigram_keys, self.trigram_rows, torch.where(ok2, (i2 * V + i1) * V + i0, torch.full_like(i0, -1)), oov) n = B * T return {"bigram": float((bi != oov).sum()) / n, "trigram": float((tri != oov).sum()) / n, "any": float(((bi != oov) | (tri != oov)).sum()) / n} # --------------------------------------------------------------------------- # # Builder # --------------------------------------------------------------------------- # def _topk_counts(stream, n_keep: int, chunk: int, cap: int, order: int, vocab: int, log=print): """Approximate top-n_keep keys by count over a token stream. Exact counting is not affordable -- a few billion tokens produce hundreds of millions of distinct bigrams. This is lossy counting: accumulate exact counts per chunk, merge, and when the accumulator exceeds `cap` drop the tail below a rising threshold. Frequent n-grams, which are the only ones that get a row, survive every prune; the approximation only ever affects the boundary of the top-K, where the difference between rank 140,624 and 140,626 is noise. """ keys_acc = np.zeros(0, dtype=np.int64) cnt_acc = np.zeros(0, dtype=np.int64) floor = 1 seen = 0 t0 = time.time() for toks in stream: toks = toks.astype(np.int64, copy=False) if toks.size <= order: continue if order == 2: ctx = np.lib.stride_tricks.sliding_window_view(toks, 2) ctx = ctx[np.all(ctx != 0, axis=1)] k = ctx[:, 0] * vocab + ctx[:, 1] else: ctx = np.lib.stride_tricks.sliding_window_view(toks, 3) ctx = ctx[np.all(ctx != 0, axis=1)] k = (ctx[:, 0] * vocab + ctx[:, 1]) * vocab + ctx[:, 2] seen += k.size for a in range(0, k.size, chunk): u, c = np.unique(k[a:a + chunk], return_counts=True) keys_acc = np.concatenate([keys_acc, u]) cnt_acc = np.concatenate([cnt_acc, c.astype(np.int64)]) if keys_acc.size > cap: o = np.argsort(keys_acc, kind="stable") keys_acc, cnt_acc = keys_acc[o], cnt_acc[o] uk, start = np.unique(keys_acc, return_index=True) uc = np.add.reduceat(cnt_acc, start) while uk.size > cap // 2: floor += 1 m = uc >= floor uk, uc = uk[m], uc[m] keys_acc, cnt_acc = uk, uc log(f" merged: {seen/1e9:.2f}B {order}-grams, " f"{uk.size/1e6:.1f}M kept, floor {floor}, " f"{time.time()-t0:.0f}s") o = np.argsort(keys_acc, kind="stable") keys_acc, cnt_acc = keys_acc[o], cnt_acc[o] uk, start = np.unique(keys_acc, return_index=True) uc = np.add.reduceat(cnt_acc, start) if uk.size > n_keep: top = np.argpartition(uc, -n_keep)[-n_keep:] uk, uc = uk[top], uc[top] log(f" {order}-gram: {seen/1e9:.2f}B seen, {uk.size:,} rows kept, " f"min count {int(uc.min()) if uc.size else 0}") return uk, uc def _source_dirs(root: Path, name: str) -> list[Path]: """A source's directories: data// plus any data/_sN/ shards.""" root = Path(root) return [d for d in sorted(root.glob(name)) + sorted(root.glob(f"{name}_s*")) if (d / "tokens.bin").exists() and (d / "tokens.bin").stat().st_size > 0] def _sample_stream(root: Path, cfg, limit_tokens: int, chunk_tokens: int = 25_000_000, seed: int = 0, log=print): """Token chunks sampled to match the training distribution. Two things this must not do. It must not walk the sources in directory order and stop when the budget runs out -- that would build the table's vocabulary out of whichever source sorts first, and with Ultra-FineWeb split across four shard directories the bias is severe. And it must not read only the head of each file: a shard is written in the order documents arrived from the Hub, so its first 3B tokens are one slice of Common Crawl rather than a sample of it. So: budget is split across sources by their stable-phase mixture weight, split again evenly across each source's shards, and drawn from evenly spaced offsets within each shard. Chunks are emitted round-robin so the lossy counter's prune floor sees a representative mix throughout rather than one source at a time. """ from schedule import mixture_at doc_weights = mixture_at( (cfg.schedule.warmup_frac + cfg.schedule.stable_frac) / 2, cfg) # VarlenPacker chooses a source once per document. Convert those draw # probabilities to the token shares the table actually sees; FineMath docs # are 2.4x longer, so a nominal 5% of documents is about 11% of tokens. means = {} for name in doc_weights: dirs = _source_dirs(root, name) nt = nd = 0 for d in dirs: idx = np.memmap(d / "docs.idx", dtype=np.uint64, mode="r") nt += int(idx[-1]); nd += idx.size - 1 means[name] = nt / max(nd, 1) z = sum(doc_weights[n] * means[n] for n in doc_weights) or 1.0 weights = {n: doc_weights[n] * means[n] / z for n in doc_weights} readers = [] for name, share in sorted(weights.items()): if share <= 0: continue dirs = _source_dirs(root, name) if not dirs: log(f" {name}: not prepared, excluded from the n-gram sample") continue per_dir = int(limit_tokens * share) // len(dirs) for d in dirs: a = np.memmap(d / "tokens.bin", dtype=np.uint16, mode="r") n_chunks = max(1, per_dir // chunk_tokens) if a.size <= chunk_tokens: offs = [0] else: offs = np.linspace(0, a.size - chunk_tokens, n_chunks).astype(np.int64) readers.append([d.name, a, list(offs), per_dir]) log(f" {name:<16} {d.name:<20} {per_dir/1e9:5.2f}B from " f"{len(offs)} spans of {a.size/1e9:.2f}B") used = {r[0]: 0 for r in readers} alive = True while alive and sum(used.values()) < limit_tokens: alive = False for name, a, offs, budget in readers: if not offs or used[name] >= budget: continue o = offs.pop(0) b = np.asarray(a[o:o + chunk_tokens]) used[name] += b.size alive = True yield b def build(root: Path, out: Path, cfg, full_cfg, vocab_size: int, sample_tokens: int = 3_000_000_000, cap: int = 120_000_000): print(f" sampling {sample_tokens/1e9:.1f}B tokens, weighted by the " f"stable-phase mixture") if not _source_dirs(root, "*"): raise SystemExit(f"no prepared sources under {root}") bk, bc = _topk_counts(_sample_stream(root, full_cfg, sample_tokens), cfg.bigram_rows, 20_000_000, cap, 2, vocab_size) tk, tc = _topk_counts(_sample_stream(root, full_cfg, sample_tokens, log=lambda *a: None), cfg.trigram_rows, 20_000_000, cap, 3, vocab_size) # Row indices in descending frequency: hot rows contiguous at the head of # each block. Keys are then sorted ascending for searchsorted; the row array # rides along and is deliberately not sorted. def assign(keys, counts, base): rank = np.argsort(-counts, kind="stable") rows = np.empty(keys.size, dtype=np.int64) rows[rank] = base + np.arange(keys.size) o = np.argsort(keys, kind="stable") return keys[o], rows[o] bkey, brow = assign(bk, bc, cfg.bigram_base) tkey, trow = assign(tk, tc, cfg.trigram_base) v = NGramVocab(vocab_size, bkey, brow, tkey, trow) v.save(out) print(f" wrote {out} ({bkey.size:,} bigram + {tkey.size:,} trigram rows, " f"fingerprint {v.fingerprint()})") if __name__ == "__main__": sys.path.insert(0, str(Path(__file__).resolve().parent)) from config import Config ap = argparse.ArgumentParser() ap.add_argument("cmd", choices=["build", "inspect"]) ap.add_argument("--shards", type=Path, default=None, help="prepared-data root (defaults to config.data.root)") ap.add_argument("--out", type=Path, default=None) ap.add_argument("--sample-tokens", type=int, default=3_000_000_000) ap.add_argument("--config", type=Path, default=None) a = ap.parse_args() cfg = Config.from_json(a.config.read_text()) if a.config else Config() shards = a.shards or Path(cfg.data.root) out = a.out or cfg.ngram.vocab_path if a.cmd == "build": build(shards, out, cfg.ngram, cfg, cfg.model.vocab_size, a.sample_tokens) else: v = NGramVocab.load(out) print(f" vocab {v.vocab_size} bigrams {v.bigram_keys.size:,} " f"trigrams {v.trigram_keys.size:,} fingerprint {v.fingerprint()}")