diff options
| author | jdj <jdj@kunix.org> | 2026-11-18 14:47:33 -0800 |
|---|---|---|
| committer | jdj <jdj@kunix.org> | 2026-11-18 14:47:33 -0800 |
| commit | 5d2e4252e695644c34be605b44a14bd80a98a0a6 (patch) | |
| tree | 311a72eda4459af7547b9cd05c0956eafb235f2d /ngram.py | |
| download | boris-2-5d2e4252e695644c34be605b44a14bd80a98a0a6.tar.gz boris-2-5d2e4252e695644c34be605b44a14bd80a98a0a6.zip | |
Boris-2 training code
The code, configuration and data filters used to train Boris-2 (144M,
200B tokens, single V100): model, training loop, data preparation,
n-gram table, V100 kernels, final stages and the exact run configs.
Diffstat (limited to 'ngram.py')
| -rw-r--r-- | ngram.py | 414 |
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()}") |
