mirror of
https://github.com/FlashML-org/FreeToken.git
synced 2026-11-23 02:00:02 +08:00
* test(deepseek-v41): add independent text and vision reference * feat(quant): support block-32 and unrounded inference outputs * feat(attention): add csa2 packed cache and sparse backend * feat(deepseek-v41): serve text and images through shared runtime * perf(mhc): tune batch-stable reduction tiles * perf(moe): autotune fp4 decode launch geometry * perf(moe): admit recurring misses against actual lru victims * revert: perf(moe): admit recurring misses against actual lru victims This reverts commit 1652d200f0ebb825379cf44c28baf52971e3a461. * perf(mhc): derive the reduction tile from the width, not a timing * perf(moe): replace the ds_fp4 decode autotune with a fixed two-warp launch * fix(deepseek-v41): fence engram staging against in-flight lookups * fix(moe): return the cpu routed sum in fp32 and round it in python * fix(deepseek-v41): keep the vision tower and aligner unquantized * fix(scheduler): admit bounded-replay hits by the history their resume reads * refactor(deepseek-v41): name the attention family after the model, not csa2 * refactor(kvcache): import the dsv41 pool only for dsv41 models * refactor(deepseek-v41): name the replay switch --swa-decoder-replay * fix(server): keep reasoning_effort a string on the wire * refactor(models): keep the prefill replay hooks off BaseLLMModel * refactor(deepseek-v41): drop the fp32 routed sum and batch-invariant prefill * fix(moe): weight ds_fp4 routes in the down epilogue again * docs(models): anchor the v4.1 replay paragraph on the tech report * refactor(deepseek-v41): run the decoder source's narrowed prefill on Block * refactor(kvcache): let the dsv41 pool own the history a resume keeps live * refactor(deepseek-v41): resume bounded-replay hits by capping the prefix match * refactor(deepseek-v41): describe the attention group as a dsv4 variant and derive its geometry from the args * refactor(deepseek-v41): keep the engram table locator in the model package * refactor(deepseek-v41): drop the fp32 lm head output - return the head's bf16 logits, as DeepSeek-V4 does - revert ParallelLMHead(out_dtype=) and LinearKernel.apply_out_dtype, which only this call used - remove test_head_preserves_fp32_logit_margin - cast test_vision's prefill logits to fp32 before comparing, as the harness does * refactor(quant): carry the w4a8 activation block on MoEConfig - drop ActDesc and QuantScheme.act; the scheme only describes stored tensors - Fp8BlockConfig sets MoEConfig.act_block from weight_block_size for its fp4 experts via a layer_config hook - the ds_fp4 GPU kernel and CPU executor read the block from the layer config and require it * refactor(deepseek-v41): size the kv pool from the args, not a geometry copy - delete kvcache/dsv41_geometry.py; the pool and cost model read dsv41_args by attribute, as the DSV4 pool reads dsv4_args - source / ratio aliasing reads args.roles; the duplicated source and ratio validation is gone - the cost model owns the tier row formats, row bytes and the private window layers - the pool keeps the format and window/ratio checks, and exposes the formats and is_private_window to the attention backend * refactor(kvcache): move the dsv4 pool into kvcache/dsv4 * refactor(kvcache): move the dsv41 pool into kvcache/dsv4 * chore(benchmarks): drop the dsv41 selection and fp8 linear benchmarks * test(deepseek-v41): drop tests that repeat other coverage * test(deepseek-v41): load the tiny model's resident experts as banks * fix(server): parse deepseek-v4.1's space-led dsml tool calls --------- Co-authored-by: andy-yang-1 <andy_yang@berkeley.edu>
263 lines
12 KiB
Python
263 lines
12 KiB
Python
"""Engram conditional memory (reference ``inference/engram.py`` + ``Engram``): n-gram hash lookups
|
|
added into the residual streams before layers 1 and 14.
|
|
|
|
Hashing (host side, ``EngramHash``): token ids are first mapped through a compressed vocabulary
|
|
(tokens that normalize alike collapse together), then each position is hashed with the
|
|
``max_ngram_size - 1`` tokens before it -- a rolling XOR of ``id * multiplier`` over the lookback,
|
|
one bucket range (a distinct prime modulus) per (n-gram order, head). Lookback stops at the sequence
|
|
start (pad id) and never crosses an image span. Addresses depend
|
|
only on the token ids, so the rows can be fetched before the forward starts.
|
|
|
|
Lookup (``EngramTable`` protocol): the 384M-row fp8 tables live on disk; a backend gathers the
|
|
``n_hash_cols`` rows of every token into a device tensor ``[T, n_hash_cols * head_dim]`` in bf16.
|
|
|
|
Gate (``EngramLayer``): ``wkv`` (fp8 linear) turns the gathered rows into one key per residual
|
|
stream plus a shared value; the gate is a normalized dot product of stream and key, signed-sqrt
|
|
then sigmoid; ``stream += gate * value``.
|
|
"""
|
|
|
|
from __future__ import annotations
|
|
|
|
from typing import Protocol
|
|
|
|
import numpy as np
|
|
import torch
|
|
from freetoken.layers import BaseOP, LinearReplicated
|
|
|
|
from .args import DeepseekV41Args
|
|
|
|
|
|
# ----- hashing ---------------------------------------------------------------------------------
|
|
|
|
|
|
def _is_prime(n: int) -> bool:
|
|
"""Deterministic Miller-Rabin for n < 3.3e24 (the bases below are a proven set), matching
|
|
``sympy.isprime`` on every 64-bit input."""
|
|
if n < 2:
|
|
return False
|
|
small = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41)
|
|
for p in small:
|
|
if n % p == 0:
|
|
return n == p
|
|
d, s = n - 1, 0
|
|
while d % 2 == 0:
|
|
d //= 2
|
|
s += 1
|
|
for a in small:
|
|
x = pow(a, d, n)
|
|
if x in (1, n - 1):
|
|
continue
|
|
for _ in range(s - 1):
|
|
x = pow(x, 2, n)
|
|
if x == n - 1:
|
|
break
|
|
else:
|
|
return False
|
|
return True
|
|
|
|
|
|
def find_next_prime(start: int, seen: set[int]) -> int:
|
|
"""The smallest prime above ``start`` not handed out yet (reference ``find_next_prime``)."""
|
|
candidate = start + 1
|
|
while not _is_prime(candidate) or candidate in seen:
|
|
candidate += 1
|
|
return candidate
|
|
|
|
|
|
def bucket_primes(args: DeepseekV41Args) -> list[list[list[int]]]:
|
|
"""``[layer][ngram order - 2][head]`` bucket moduli: distinct primes drawn in order from
|
|
``engram_vocab_size - 1`` upward, never reused across layers / orders / heads."""
|
|
primes: list[list[list[int]]] = []
|
|
seen: set[int] = set()
|
|
for _ in args.engram_layer_ids:
|
|
per_ngram = []
|
|
for _ in range(args.engram_max_ngram_size - 1):
|
|
sizes, current = [], args.engram_vocab_size - 1
|
|
for _ in range(args.engram_n_heads):
|
|
current = find_next_prime(current, seen)
|
|
seen.add(current)
|
|
sizes.append(current)
|
|
per_ngram.append(sizes)
|
|
primes.append(per_ngram)
|
|
return primes
|
|
|
|
|
|
def hash_multipliers(layer_ids: tuple[int, ...], max_ngram_size: int, compressed_vocab_size: int) -> torch.Tensor:
|
|
"""``[n_layers, max_ngram_size]`` odd int64 multipliers from a per-layer RNG (reference
|
|
``compute_hash_multipliers``), bounded so ``id * multiplier`` cannot overflow int64."""
|
|
max_long = np.iinfo(np.int64).max
|
|
bound = max(1, (max_long // compressed_vocab_size) // 2)
|
|
rows = []
|
|
for layer_id in layer_ids:
|
|
gen = np.random.default_rng(10007 * layer_id)
|
|
values = gen.integers(low=0, high=bound, size=(max_ngram_size,), dtype=np.int64)
|
|
rows.append(torch.tensor(values * 2 + 1))
|
|
return torch.stack(rows)
|
|
|
|
|
|
def build_compressed_token_map(tokenizer) -> tuple[list[int], int]:
|
|
"""Token id -> compressed id: tokens that normalize alike (NFKC, accents stripped, lowercased,
|
|
whitespace collapsed) share one id. Reference ``build_compressed_token_map``; the size feeds the
|
|
multipliers, so it is asserted against ``engram_compressed_vocab_size``."""
|
|
from tokenizers import Regex, normalizers
|
|
|
|
sentinel = "\ue000"
|
|
normalizer = normalizers.Sequence([
|
|
normalizers.NFKC(),
|
|
normalizers.NFD(),
|
|
normalizers.StripAccents(),
|
|
normalizers.Lowercase(),
|
|
normalizers.Replace(Regex(r"[ \t\r\n]+"), " "),
|
|
normalizers.Replace(Regex(r"^ $"), sentinel),
|
|
normalizers.Strip(),
|
|
normalizers.Replace(sentinel, " "),
|
|
])
|
|
backend = tokenizer.backend_tokenizer
|
|
key_to_new: dict[str, int] = {}
|
|
lookup = [0] * len(tokenizer)
|
|
for token_id in range(len(tokenizer)):
|
|
text = backend.decode([token_id], skip_special_tokens=False)
|
|
if "\ufffd" in text:
|
|
key = backend.id_to_token(token_id)
|
|
else:
|
|
normalized = normalizer.normalize_str(text)
|
|
key = normalized if normalized else text
|
|
new_id = key_to_new.get(key)
|
|
if new_id is None:
|
|
new_id = len(key_to_new)
|
|
key_to_new[key] = new_id
|
|
lookup[token_id] = new_id
|
|
return lookup, len(key_to_new)
|
|
|
|
|
|
class EngramHash:
|
|
"""Maps token runs to table rows: ``row_ids(tokens) -> [T, n_layers, n_hash_cols]`` int64.
|
|
|
|
``token_map`` is the compressed vocabulary (``build_compressed_token_map``); ``pad_id`` is the
|
|
compressed id of ``engram_pad_id``. Runs on the host (numpy / CPU torch) since the addresses
|
|
are needed before the forward launches.
|
|
"""
|
|
|
|
def __init__(self, args: DeepseekV41Args, token_map: list[int] | torch.Tensor, compressed_vocab_size: int):
|
|
if compressed_vocab_size != args.engram_compressed_vocab_size:
|
|
raise ValueError(
|
|
f"compressed vocab has {compressed_vocab_size} ids, config says {args.engram_compressed_vocab_size}; "
|
|
"the hash multipliers derive from it, so the tokenizer does not match the checkpoint"
|
|
)
|
|
self.args = args
|
|
self.max_ngram = args.engram_max_ngram_size
|
|
self.token_map = torch.as_tensor(token_map, dtype=torch.int64)
|
|
self.pad_id = int(self.token_map[args.engram_pad_id])
|
|
primes = bucket_primes(args)
|
|
flat = [[p for per_ngram in layer for p in per_ngram] for layer in primes]
|
|
self.primes = torch.tensor(primes, dtype=torch.int64) # [L, ngram-1, heads]
|
|
self.offsets = torch.tensor(np.array([np.cumsum([0, *sizes[:-1]]) for sizes in flat]), dtype=torch.int64) # [L, cols]
|
|
self.multipliers = hash_multipliers(args.engram_layer_ids, self.max_ngram, compressed_vocab_size) # [L, ngram]
|
|
self.rows_per_layer = [int(o[-1] + s[-1]) for o, s in zip(self.offsets.tolist(), [[p for pn in layer for p in pn] for layer in primes])]
|
|
|
|
@property
|
|
def n_cols(self) -> int:
|
|
return (self.max_ngram - 1) * self.args.engram_n_heads
|
|
|
|
def row_ids(self, tokens: torch.Tensor, context: torch.Tensor | None = None) -> torch.Tensor:
|
|
"""Rows for ``tokens [T]`` (raw ids, one contiguous run). ``context`` holds the
|
|
``max_ngram_size - 1`` raw ids immediately before the run (fewer -> the run starts a
|
|
sequence and the missing lookback is the pad id). Returns ``[T, n_layers, n_hash_cols]``."""
|
|
tokens = tokens.to(torch.int64).cpu()
|
|
ctx_len = self.max_ngram - 1
|
|
if context is None:
|
|
context = tokens.new_empty(0)
|
|
context = context.to(torch.int64).cpu()[-ctx_len:] if ctx_len else tokens.new_empty(0)
|
|
raw = torch.cat([context, tokens])
|
|
# Content-pad ids identify image spans; n-grams stop at them, including across chunks.
|
|
dead = (raw < 0) | (raw >= self.token_map.numel())
|
|
compressed = self.token_map[raw.clamp(0, self.token_map.numel() - 1)]
|
|
n_ctx = context.numel()
|
|
T = tokens.numel()
|
|
positions = torch.arange(n_ctx, n_ctx + T)
|
|
cols = []
|
|
blocked = torch.zeros(T, dtype=torch.bool)
|
|
for shift in range(self.max_ngram):
|
|
src = positions - shift
|
|
blocked |= (src < 0) | dead[src.clamp_min(0)]
|
|
cols.append(torch.where(blocked, torch.full_like(src, self.pad_id), compressed[src.clamp_min(0)]))
|
|
stack = torch.stack(cols, dim=-1) # [T, max_ngram]; column s is the token s places back
|
|
products = stack.unsqueeze(1) * self.multipliers # [T, L, max_ngram]
|
|
rolling, hashes = products[..., 0], []
|
|
for i in range(1, self.max_ngram):
|
|
rolling = torch.bitwise_xor(rolling, products[..., i])
|
|
hashes.append(rolling.unsqueeze(-1) % self.primes[:, i - 1]) # [T, L, heads]
|
|
return torch.cat(hashes, dim=-1) + self.offsets # [T, L, cols]
|
|
|
|
|
|
# ----- lookup ------------------------------------------------------------------------------------
|
|
|
|
|
|
class EngramTable(Protocol):
|
|
"""Row store of one Engram layer: ``lookup`` returns the dequantized rows of the current
|
|
forward's tokens as ``[T, n_hash_cols * head_dim]`` bf16 (staged by the host before launch)."""
|
|
|
|
def lookup(self, num_tokens: int) -> torch.Tensor: ...
|
|
|
|
|
|
class ZeroEngramTable:
|
|
"""Stand-in when no table is attached (dummy weights / unit tests): every lookup reads zeros."""
|
|
|
|
def __init__(self, width: int, device: torch.device) -> None:
|
|
self.width = width
|
|
self.device = device
|
|
|
|
def lookup(self, num_tokens: int) -> torch.Tensor:
|
|
return torch.zeros(num_tokens, self.width, dtype=torch.bfloat16, device=self.device)
|
|
|
|
|
|
# ----- the layer -----------------------------------------------------------------------------------
|
|
|
|
|
|
class EngramLayer(BaseOP):
|
|
"""``streams [T, hc, dim] += gate * value`` with key / value from the gathered n-gram rows."""
|
|
|
|
def __init__(self, args: DeepseekV41Args, layer_id: int, *, quant_config=None, prefix: str = ""):
|
|
self.layer_id = layer_id
|
|
self.dim = args.dim
|
|
self.hc_mult = args.hc_mult
|
|
self.eps = args.norm_eps
|
|
self.clamp_value = 1e-6
|
|
self.width = args.engram_hash_cols * args.engram_head_dim
|
|
self.wkv = LinearReplicated(self.width, args.dim * (args.hc_mult + 1), has_bias=False, quant_config=quant_config, prefix=f"{prefix}.wkv")
|
|
self.q_weight = torch.empty(args.hc_mult, args.dim, dtype=torch.float32)
|
|
self.k_weight = torch.empty(args.hc_mult, args.dim, dtype=torch.float32)
|
|
self._table: EngramTable | None = None
|
|
|
|
def attach_table(self, table: EngramTable) -> None:
|
|
self._table = table
|
|
|
|
def forward(self, streams: torch.Tensor, rows: torch.Tensor | None = None, *, image_mask: torch.Tensor | None = None) -> torch.Tensor:
|
|
"""``streams [T, hc, dim]``; ``rows`` overrides the table lookup (tests / reference parity)."""
|
|
T = streams.shape[0]
|
|
if rows is None:
|
|
assert self._table is not None, "Engram table was never attached"
|
|
rows = self._table.lookup(T)
|
|
kv = self.wkv.forward(rows.to(streams.dtype))
|
|
key, value = kv.split([self.hc_mult * self.dim, self.dim], dim=-1)
|
|
key = key.float().view(T, self.hc_mult, self.dim)
|
|
weight = self.q_weight * self.k_weight # only ever used as a product
|
|
h = streams.float()
|
|
# normalized per (token, stream) over dim, not jointly over the streams
|
|
rstd = torch.rsqrt(h.square().mean(-1) + self.eps) * torch.rsqrt(key.square().mean(-1) + self.eps)
|
|
dot = (h * weight * key).sum(-1) * rstd * self.dim**-0.5
|
|
gate = torch.sigmoid(torch.copysign(dot.abs().clamp_min(self.clamp_value).sqrt(), dot))
|
|
out = (h + gate.unsqueeze(-1) * value.float().unsqueeze(1)).to(streams.dtype)
|
|
return out if image_mask is None else torch.where(image_mask[:, None, None], streams, out)
|
|
|
|
|
|
__all__ = [
|
|
"EngramHash",
|
|
"EngramLayer",
|
|
"EngramTable",
|
|
"ZeroEngramTable",
|
|
"build_compressed_token_map",
|
|
"bucket_primes",
|
|
"hash_multipliers",
|
|
]
|