summaryrefslogtreecommitdiff
path: root/ngram.py
diff options
context:
space:
mode:
Diffstat (limited to 'ngram.py')
-rw-r--r--ngram.py414
1 files changed, 414 insertions, 0 deletions
diff --git a/ngram.py b/ngram.py
new file mode 100644
index 0000000..f847d6b
--- /dev/null
+++ b/ngram.py
@@ -0,0 +1,414 @@
+"""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/<name>/ plus any data/<name>_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()}")