mLattice / src /mulattice /autoscan.py
Ex0bit's picture
μLattice: live demo — your own facts, store at scale
20a3a74 verified
Raw History Blame Contribute Delete
4.28 kB
"""
Adaptive scan: run whichever of the two verified-identical scans is cheaper.
`sparse_scan.SparseLatticeScan` walks the sequence token by token (T rounds).
`fastscan.CellParallelScan` walks it cell by cell (max_writes_per_cell rounds).
They are the same function -- forward and gradients agree to 1e-13 over
configurations from clustered to fully spread addresses (tests/test_kernel.py) --
so which one runs is purely a throughput decision.
Measured on MPS at the MQAR shape (B=64, T=136, d=32):
clustered lattice (~20k cells): token loop 1065 ms, cell-parallel 432 ms @ 17 rounds
-> crossover near 19 rounds = 0.14*T
spread lattice (~76k cells): token loop 3038 ms, cell-parallel 226 ms @ 4 rounds
-> crossover near 54 rounds = 0.40*T
so the crossover is regime-dependent. A single constant must pick the conservative
end of that range, otherwise it chooses the *slower* path in the middle band: at
48 rounds with 0.40*T the cell-parallel path is selected at 2358 ms against a
1065 ms token loop. 0.15*T is correct in both measured regimes.
Rounds come from the keys (a sort over B*T*9 int64), a small fraction of either
scan, and when the cell-parallel path is chosen its setup is reused.
"""
from __future__ import annotations
import torch
from .fastscan import CellParallelScan
from .sparse_scan import SparseLatticeScan, compact_ids
from .kernel import MAX_CELLS_PER_TOKEN, phi_2d
CROSSOVER = 0.15 # rounds < CROSSOVER * T -> cell-parallel (fast path).
# VERIFIED (tests/test_kernel.py, same-inputs comparison): both scans have
# IDENTICAL forward (0.0) and gradients (4e-16); the reads are deterministic
# (unique (row, cell) index_put) and the write is functional (out-of-place).
# An earlier "gradient bug" was a test bug comparing the scans at different
# random inputs. Note: training runs differ at the 1e-3 level (different
# summation order), which the bootstrap phase transition AMPLIFIES into
# different transition timing -- use the token-loop for warmup/bootstrap
# stages (small T, stability matters) and the cell-parallel for long
# sequences (its speedup grows with T).
class AdaptiveScan(torch.nn.Module):
def __init__(self, d_k: int, d_v: int, n_heads: int, crossover: float = CROSSOVER):
super().__init__()
self.d_k, self.d_v, self.n_heads = d_k, d_v, n_heads
self.crossover = crossover
self.slow = SparseLatticeScan(d_k, d_v, n_heads)
self.fast = CellParallelScan(d_k, d_v, n_heads)
self.last_n_cells = 0
self.last_rounds = 0
self.last_path = None
def rounds_estimate(self, q_addr: torch.Tensor, k_addr: torch.Tensor, n_seq: int) -> int:
"""max writes per (sequence, cell) -- the number of rounds the fast path needs."""
from .fastscan import _encode
B = k_addr.shape[0]
T = k_addr.shape[1]
_, zk = phi_2d(k_addr.reshape(-1, 2))
keys = _encode(zk.reshape(B, T, MAX_CELLS_PER_TOKEN, 2), B).reshape(-1)
order = torch.argsort(keys)
ks = keys[order]
first = torch.ones_like(ks, dtype=torch.bool)
if ks.numel() > 1:
first[1:] = ks[1:] != ks[:-1]
ar = torch.arange(ks.numel(), device=ks.device)
run_start = torch.cummax(torch.where(first, ar, torch.zeros_like(ar)), 0).values
return int((ar - run_start).max()) + 1 if ks.numel() else 0
def forward(self, q_addr, k_addr, q2, kappa, v, alpha, beta, read_mode="all"):
T = kappa.shape[1]
rounds = self.rounds_estimate(q_addr, k_addr, kappa.shape[0])
if rounds < self.crossover * T:
out, n = self.fast(q_addr, k_addr, q2, kappa, v, alpha, beta, read_mode=read_mode)
self.last_rounds = self.fast.last_rounds
self.last_path = "cell-parallel"
else:
out, n = self.slow(q_addr, k_addr, q2, kappa, v, alpha, beta, read_mode=read_mode)
self.last_rounds = rounds
self.last_path = "token-loop"
self.last_n_cells = n
return out, n