SERA: 列長に非依存な O(1)/token 実行、正値ランダム特徴に基づく十分統計化、比率推定の非漸近保証
タイトル
SERA: Self-Normalized Random-Feature Attention for O(1)/Token Streaming
— positive RF + ratio bounds + exponential decay
カジュアルに：
SERA = PRFでsoftmaxを正に線形化し、A(q),B(q)を十分統計(Z,z)に“永続化”して比率推定で出す。
softmax注意の指数核を正値ランダム特徴で展開し、列長に依存せず O(1)/token で問い合わせできる仕組み。キー列から十分統計 Z=∑φ(k)v^T と z=∑φ(k) だけを持ち、クエリは ŷ(q)=(φ(q)^T Z)/(φ(q)^T z+λ)。重いKV-cache不要で常駐は r×d_v+r の定数、p99レイテンシが伸びない。精度は r^{-1/2} で効率よく上がり、時間一様・集合一様の非漸近保証あり。ストリーミングは指数減衰 γ で古い情報を自然にフェード。数値は Kahan・拡張精度・指数クリップで堅牢。用途は長尺対話/実況/オンデバイス/エッジ/RAGの“注意メモリ化”。近傍は厳密softmax、遠距離はSERAのハイブリッドも簡単。実運用は τ=√d, λ≈分母中央値の1–5%, r≒128–512 目安。Z,z は共有・合成しやすく、DP/TEEでの安全化とも相性良し。要は“注意の十分統計”で長文と低遅延を両取りする発想。
新規点は (i) 自己正規化（λ付き）比率の“時間一様”非漸近界を明示、(ii) 実運用で効く数値規範（Kahan/拡張精度/クリップ/校正λ）を体系化、(iii) 指数減衰γとβ下界で条件数制御を“ anytime-valid ”に運用可能な設計へ落とした点。
既存：Linear Transformersはφで前方累積（S,z）する形でO(1)/token化、PerformerはPRF（FAVOR+）でsoftmaxを線形化。SERAはその2本を“比率推定＋監査運用”の枠でまとめ上げた。
“指数核を非負ランダム特徴で厳密に線形化”という時点で既存のPerformer系（FAVOR+）と似てるようで、実は SERA は softmax kernel = exp(q·k/τ) に対して、E[φ(q)^Tφ(k)] = exp(q·k/τ) を符号なしで再現する設計。
→ 多くの線形Attention（ReLU系やTruncated）は符号を落とせず、“非負＋自己正規化”を両立できていない。非負かつ期待一致のφを導く部分は、解析的にかなりレア。
次に、比率推定(ŷ = A_r/B_r)を非漸近で誤差解析している点。多くの研究が「分母もランダム量」であることを無視してるが、SERAは 比率不等式補題＋Freedman時間一様化で
sup_{t,q} ||ŷ−y|| ≤ O(r^{-1/2}) + O(log T/r) を導出。
→ これは「attentionを比率推定として扱う」発想。
何ができるの？：
① ロング・ストリームの“実時間読解”。SERAは列長に依存しない O(1)/token なので、会議/配信/取引ログのような無限時系列でも p99 レイテンシが増えない。指数減衰 γ で古い情報を自然に忘れつつ直近文脈は鋭く保持。ライブ要約、即時引用、異常検知を同一パイプで回し、Z,z を跨セッション継続して“記憶”として使える。
② エッジ/ブラウザで賢く。保持するのは十分統計 Z(r×d_v) と z(r) だけ（数MB級）。KV-cache不要でバッテリ/帯域に優しい。更新が線形和だから TEE や DP ノイズの付加で個人寄与を秘匿化しやすい。seed固定で再現・監査もしやすく、機微データを外に出さずに高品質応答を提供できるオンデバイスAIが現実的に。
③ RAGの前段を“注意メモリ”化。文書・会議・チャンネルごとに (Z_m, z_m) を保持し、クエリ時に重み付け合成すれば、索引→注意→回答が一呼吸。近傍は厳密softmax、遠距離はSERAでスケール。長文検索・社内FAQ・監視ダッシュボードを低遅延で回し、混合係数はBM25や埋め込みで軽量に推定可能。
④ 低コスト運用とハイブリッド最適化。r を128–512でスイープし λ とクリップ c を自動校正、誤差は理論どおり r^{-1/2} で減少。層ごとに r を変える、値側を低ランク化（LUM）する、失敗時に局所だけ厳密softmaxへフォールバック等のハックで、品質・遅延・メモリの Pareto を押し上げる。
問題は？
→色々動くけど実験中、実装負荷が高い(というより微妙な最適化が面倒くさい)
→長期記憶が弱いから色々モジュール積まないと駄目。
→個人的にリソースが足りなすぎる(文献リファレンスが弱い)
→転移学習してみないと分からないことが多い(そこまで体力が持たない)
要は？
→実装すれば、勿論、動くけど”魔法”が必要なタイプのアルゴリズム。
texで書けよ
→それはそう。時間が無かった。
→アカデミック対策用の研究メモだからね。
何でOSSで出さないの？
→証跡と引用性を残したかったから。実装が詰まっているのと、査読準備とか。
色々と”大人の事情”がね。各組織のプロ勢が実験すれば多分、再現性高く実装できる筈。
どんなAI使っているの？
→守秘義務あるから言えないが、割とクローズドなやつ。
以下、本文。
要旨
SERA は、指数核 w(q,k)=exp(q·k/τ)（τ>0）に対する分離可能構造を正値ランダム特徴で実現し、注意の分子 A(q)=∑j w(q,k_j)v_j、分母 B(q)=∑j w(q,k_j) を有限次元の十分統計で近似・再利用することにより、列長 n に依存しない O(1)/token の問い合わせ実行を達成する。具体的には、独立なガウス乱数 w_i∼N(0,I_d) を用い、非負特徴 φ_i(x)=r^{-1/2}·exp(w_i^T x/√τ − ||x||^2/(2τ))（i=1..r）を構成し、Z:=∑j φ(k_j)v_j^T∈R^{r×d_v}、z:=∑j φ(k_j)∈R^{r} を保持する。クエリ q に対する推定は ŷ(q)=(φ(q)^T Z)/(φ(q)^T z + λ)（λ>0）で与えられる。本稿は、(i) 期待一致 E[φ(q)^Tφ(k)]=w(q,k) の厳密導出、(ii) φ に起因する有限 r のサブ指数集中に基づく点ごと・時間一様・集合一様の非漸近誤差上界、(iii) 正則化 λ と分母下界の役割、(iv) クリッピング・浮動小数点・累積誤差の数値解析、(v) ストリーミング指数減衰 γ∈(0,1] での有効窓長と Freedman 型集中、(vi) minimax 下界 Ω(r^{-1/2}) の提示を含む。いずれの境界も列長 n に依存せず、列長nに関して定数（固定r,d_v,ヘッド数Hのもと）。主項は r^{-1/2} と数値・設計定数で明示される。実装規範（正則化・自動校正・Kahan 加算・指数クリップ・拡張精度）と再現的評価プロトコルを併記する。
キーワード
softmax kernel, positive random features, ratio estimator, nonasymptotic bounds, streaming with exponential decay, numerical stability
貢献
- 指数核に対する正値ランダム特徴の期待一致と十分統計の厳密導出（非負性とスカラー比率の自己正規化）。
- ランダム特徴のサブ指数集中に基づく r^{-1/2} 主項の非漸近誤差界（点ごと・時間一様・集合一様）。
- 正則化 λ による分母下界の確保とバイアスの明示境界、指数クリップの偏り評価。
- ストリーミング指数減衰 γ の下での有効窓長 μ_eff と Freedman 一様化。
- 数値実装規範（Kahan、拡張精度、Cholesky 逆、クリップ設計、量子化方針）。
- 情報論的下界とオーダ最適性の整合。
-
記法・設定
入力次元 d、値次元 d_v。キー列 K={k_j}⊂R^d、値列 V={v_j}⊂R^{d_v}、クエリ q∈R^d。温度 τ>0、通常は τ=√d で scaled dot-product に一致。ランダム特徴数 r。φ(x)∈R_+^{r} は非負。分母安定化のため λ>0。ノルムは ||·||（2-ノルム）、||·||_F（Frobenius）、||·||_op（作用素）。確率言明の高確率とは確率≥1−δ（δ∈(0,1)）。 -
指数核と正値ランダム特徴
1.1 核と目標
softmax 注意の核は w(q,k)=exp(q·k/τ)。我々の目標は、w の分子 A(q)=∑j w(q,k_j)v_j と分母 B(q)=∑j w(q,k_j) を有限次元の十分統計で代替し、問い合わせを O(1) で行うことである。
1.2 正値ランダム特徴の構成
w_i∼N(0,I_d) を独立に i=1..r 生成し、
φ_i(x)=r^{-1/2}·exp(w_i^T x/√τ − ||x||^2/(2τ))。
このとき E[φ_i(q)φ_i(k)]=r^{-1}·E[exp(w_i^T(q+k)/√τ)]·exp(−(||q||^2+||k||^2)/(2τ))
= r^{-1}·exp(||q+k||^2/(2τ))·exp(−(||q||^2+||k||^2)/(2τ))
= r^{-1}·exp(q·k/τ)。
よって E[φ(q)^Tφ(k)]=∑i E[φ_i(q)φ_i(k)]=exp(q·k/τ)=w(q,k)。特徴は非負で数値実装に適する。
- 十分統計と推定子
2.1 構築
Z=∑j φ(k_j)v_j^T ∈R^{r×d_v}、z=∑j φ(k_j)∈R^r を保持する。問い合わせでは φ(q) を計算し、
num(q)=φ(q)^T Z ∈R^{d_v}、den(q)=φ(q)^T z ∈R。
推定子は ŷ(q)=num(q)/(den(q)+λ)。
2.2 厳密再現条件
理想化条件（r→∞ または w の有限正確表現、λ=0）では ŷ(q)=A(q)/B(q) に一致する。有限 r ではランダム特徴の平均化誤差が残る。
- ストリーミング指数減衰
3.1 更新式
時刻 t で (k_t,v_t) を受けたとき、γ∈(0,1] に対し
Z_t←γ Z_{t−1}+φ(k_t)v_t^T、z_t←γ z_{t−1}+φ(k_t)。
問い合わせは ŷ_t(q)=(φ(q)^T Z_t)/(φ(q)^T z_t + λ)。
3.2 有効窓長
分母の期待値 E[B_t(q)] は m(q)/(1−γ)（m(q)=E[w(q,k_t)]）に比例し、μ_eff:=inf_q m(q)/(1−γ) が分母スケールの下限を与える。λ と組み合わせ β:=μ_eff+λ を比率の条件数制御に用いる。
-
誤差分解
真値 y(q)=A(q)/B(q)、推定 ŷ(q)=A_r(q)/B_r(q) with A_r(q)=φ(q)^T Z、B_r(q)=φ(q)^T z。
誤差は E_total(q)=||ŷ(q)−y(q)|| ≤ E_num(q)+E_den(q)+E_reg(q)+E_clip(q)。
E_num, E_den はランダム特徴に起因する分子・分母の偏差。E_reg は λ に伴う収縮バイアス、E_clip は指数クリップや丸めの系統誤差。 -
比率誤差補題
a/b と a0/b0（b,b0≥β>0）に対し
||a/b−a0/b0|| ≤ ||a−a0||/β + ||a0||·|b−b0|/β^2。
ここで β を高確率での分母下界として μ_eff+λ で設計する。 -
点ごとの非漸近境界
6.1 サブ指数集中
固定の q,k_j,v_j に対し、X_i:=φ_i(q)∑j φ_i(k_j)v_j は非負の log-normal の線形結合。ψ_1 ノルムが有限であり、Bernstein 型集中により
||A_r(q)−E A_r(q)|| ≤ C_A·S_A·√((d_v+log(1/δ))/r) + C_A’·(d_v+log(1/δ))/r、
|B_r(q)−E B_r(q)| ≤ C_B·S_B·√(log(1/δ)/r) + C_B’·log(1/δ)/r。
S_A、S_B はスケール（窓内重みの合計や値ノルム B_v）で具体化できる。
6.2 主定理（点ごと）
高確率（≥1−δ）に
||ŷ(q)−y(q)|| ≤ C1·√((d_v+log(1/δ))/r)/(μ_eff+λ) + C2·||A(q)||·√(log(1/δ)/r)/(μ_eff+λ)^2 + C3·(log(1/δ))/r + E_clip(q) + E_round。
主項は r^{-1/2}。E_clip(q) は指数クリップによる期待差分、E_round は丸め誤差（実装節で境界化）。
-
時間一様境界（ストリーミング）
A_r,t(q) と B_r,t(q) の増分は適切なフィルトレーション下で martingale 差列を構成し、Freedman により sup_{t≤T} の同時制御ができる。結果として定理 6.2 の r 依存は不変、log T の加算のみを要する。 -
集合一様境界（q∈X）
φ の q-Lipschitz 定数 L_φ と状態ノルム ||Z||_op, ||z|| から勾配界
||∇_q ŷ(q)|| ≤ (L_φ·||Z||_op)/λ + (L_φ·||φ(q)||·||Z||op·||z||)/λ^2。
半径 R の被覆数 log N(X,ε) を用い、一様化
sup{q∈X} ||ŷ(q)−y(q)|| ≤ C·√((d_v+log N(X,ε)+log(1/δ))/r)/(μ_eff+λ) + 2L_y ε + 低次項。 -
正則化バイアスと設計
9.1 収縮係数
shr(q):=B_r(q)/(B_r(q)+λ)∈(0,1)。理想化で num≈A、den≈B のとき
||ŷ(q)−A/B|| ≈ ||A/B − A/(B+λ)|| = ||A||·λ/(B(B+λ)) ≤ ||A||·λ/β^2。
したがって λ は β に対し小さくとる。実務では校正セット Q_calib に対し med_q B_r(q) の 1–5% を初期値に採用する。
9.2 クリップによる偏り
exp の上限クリップ c>0 を用いると、E[exp(U)·1{|U|>c}] の寄与が偏りとなる。U∼N(0,σ^2) なら上尾確率で exp(−(c−σ^2/2)^2/(2σ^2)) で抑えられる。c を log 精度に応じて 30–50 程度へ設定し、残項を r^{-1/2} と同程度以下に調整する。
-
情報論的下界
正値特徴の平均化により w を推定する最良の不偏推定でも、二点法により minimax 率は Ω(r^{-1/2}) を下回らない。したがって SERA の r^{-1/2} 主項は最良オーダである。 -
計算量・記憶
前処理（列の蓄積）: Z と z の更新は rank-1 外積・ベクトル加算で O(r·d_v)+O(r)。問い合わせ: φ(q) 計算 O(r·d)、num=φ(q)^T Z（O(r·d_v)）、den=φ(q)^T z（O(r)）、最終比率 O(d_v)。r,d_v を固定すれば O(1)/token。常駐記憶は r·d_v + r（定数）。 -
数値実装規範
12.1 精度
倍精度を既定とし、分母累積は拡張精度（80bit 等）で保持して最後に縮約。Z と z の加算は Kahan あるいは二重補償和で行う。
12.2 クリップ
指数は ±c（例 40）でクリップ。入力の L2 正規化で ||x||^2/(2τ) のスケールを安定化する。
12.3 逆行列不要
SERA 本体は逆行列を要しない（単純な内積と除算）。
12.4 量子化
Z の行ごとにスケールを持つ per-row 量子化を採用し、round-to-nearest-ties-to-even を既定とする。分母は可能なら非量子化で保持。
12.5 並列化と融合
φ 計算と GER（外積）/GEMV をカーネル融合。問い合わせは φ(q) 計算→二つの内積→除算→出力合成を単一カーネルに。p99 レイテンシはバッチ化で平滑化。 -
パラメータ設計
13.1 r（特徴数）
目標相対誤差 ε と信頼度 1−δ に対し r ≈ C·(d_v+log(1/δ))/ε^2。
13.2 τ（温度）
scaled dot-product に合わせ τ=√d。入力を L2 正規化（または α スケーリング）し、log-normal の分散を制御。
13.3 λ（正則化）
校正集合で den の中央値 med を測り λ≈(0.01–0.05)·med。shr の中央値が 0.95–0.99 の帯に入るよう微調整。
13.4 γ（指数減衰）
有効窓長 L_eff=(1−γ)^{-1} を設計ターゲットから逆算。オンライン用途では γ∈{0.95,0.99,0.995,0.999} を推奨。 -
失敗様式と回復
14.1 分母希薄化
B_r(q) が小さい場合、比率が不安定。λ を自動増分、γ を増やして μ_eff を厚くする。
14.2 分布シフト
入力スケールが変動すると log-normal 分散が増大。入力を再正規化、クリップ c を引き上げ、r を一時的に増やす。
14.3 量子化飽和
クリッピング率を監視しスケールを再推定。Z の再構築を許容するなら一時的に非量子化へ退避。
14.4 数値アンダーフロー
−||x||^2/(2τ) が大きいと下振れ。入力の L2 スケールを抑え、c を上げ、double/long double を選択。 -
評価プロトコル
データ: 長文テキスト（言語）、対話ログ、連続時系列。
指標: 真値 softmax と比較した L2/L∞、相対 RMSE、p50/p99 レイテンシ、常駐メモリ。
スイープ: r∈{16,32,64,128,256,512}、γ∈{1.0,0.99,0.995,0.999}、λ∈{0.5%,1%,2%,5% of med den}、クリップ c∈{30,40,50}、入力スケール α∈{0.25,0.5,1.0}。
アブレーション: クリップ有無、Kahan 有無、拡張精度有無、ストリーミング有無。
可視化: 誤差 vs r（log–log、スロープ ≈ −1/2）、レイテンシ vs n（SERA がフラット）、shr の分布、クリップ率。 -
理論補遺
16.1 期待一致の導出
E[exp(w^T(q+k)/√τ)]=exp(||q+k||^2/(2τ))。補正因子 exp(−(||q||^2+||k||^2)/(2τ)) を掛け合わせることで exp(q·k/τ) が得られる。
16.2 サブ指数ノルムの上界
U=w^T x/√τ は N(0,||x||^2/τ)。exp(U−||x||^2/(2τ)) は平均 1 の log-normal。積 φ_i(q)φ_i(k) は log-normal の積で依然サブ指数、ψ_1 ノルムは ||q||,||k||,τ の多項式・指数関数で上界化される。入力正規化で上界定数が制御可能。
16.3 Freedman 一様化
増分 Δ_t=φ_i(q)φ_i(k_t)v_t − E[·|F_{t−1}] に対し条件つき分散過程と最大増分を評価し、時間一様境界に log T を追加。
16.4 クリップ偏り
P(|U|>c) の上界（ガウス尾）と exp(U) の尾の合成から、E[exp(U)1{|U|>c}] ≤ exp(−(c−σ^2/2)^2/(2σ^2))·多項式(σ,c)。c を 40 前後に設定すれば r^{-1/2} 主項以下に抑制可能。 -
他手法との関係（抽象）
SERA は「非負・分離可能・有限次元」特徴の典型例であり、SLUM など値側低ランク圧縮と直交的に統合できる。SERA が分子・分母を十分統計化し、SLUM が値側を圧縮することで、問い合わせ・更新ともに O(1)/token を満たす合成系を構成できる。 -
限界と適用範囲
指数核の分離可能性と非負性を前提とする。負重み・非分離核では追加設計が要る。入力スケールが過大な領域では log-normal の分散が増え r が必要。r を極小にすると r^{-1/2} ノイズが支配的になる。 -
まとめ
SERA は、指数核 softmax 注意の分子・分母を正値ランダム特徴で十分統計化し、列長から独立した O(1)/token の問い合わせ実行を実現する。理論的には r^{-1/2} 主項の非漸近界、時間・集合一様化、正則化・クリップ・数値誤差まで含めた設計則を提示した。実装は逆行列不要・内積と除算のみという単純さと非負性により堅牢で、国防・産業スケールのストリーミング処理に適する。今後は非分離核の学習的特徴（小規模 NN による feature map 学習）と DP/TEE 併用の安全化解析が課題である。
付録 A（比率誤差補題の証明）
a/b−a0/b0=[(a−a0)b0+a0(b0−b)]/(bb0)。b,b0≥β>0 より |a/b−a0/b0| ≤ |a−a0|/β + |a0||b−b0|/β^2。ベクトル版は各成分評価後にノルムで包絡。
付録 B（Bernstein 型集中の適用）
X_i=φ_i(q)∑j φ_i(k_j)v_j の各座標は非負サブ指数。ψ_1 ノルム K と分散 proxy ν^2 に対し、平均 1/r∑i X_i が E[X_i] から逸脱する確率は exp(−c·min{t^2 r/ν^2, t r/K}) で抑制。座標数 d_v に対し union bound で log d_v を追加。
付録 C（Freedman による時間一様化）
martingale 差列 {M_t} に対し、可換変数の二次変動と最大増分で制御。SERA の指数減衰により増分の有界性と二次変動の累積が抑制され、log T の係数のみ追加。
付録 D（数値誤差の境界）
Kahan 補償和により n 回加算しても丸め誤差は O(u·∑|x_i|)+O(u^2 n)（u は機械イプシロン）。分母は拡張精度で保持し最終縮約時の誤差を O(u’) に限定。指数クリップは偏り項として別建てで界に加算。
付録 E（設計レシピの短縮版）
r: 目標誤差 ε に対し r≈C·(d_v+log(1/δ))/ε^2。
τ: √d。入力は L2 正規化（あるいは α<1 を掛ける）。
λ: den の中央値の 1–5%。
γ: L_eff=(1−γ)^{-1} から逆算。
c: 30–50。
実装: 倍精度＋拡張精度分母、Kahan、GER/GEMV 融合、per-row 量子化（必要時）。
補記.1 — 校正プロトコル（r, τ, λ, クリップ c）
r は目標相対誤差 ε と信頼 1−δ から r≈C·(d_v+log(1/δ))/ε^2 を初期化し、p99 誤差が帯域を外れたら 2 倍刻みで調整する。τ は入力を L2 正規化した上で τ=√d を既定、勾配爆発や過小感度が見られる場合は τ を 0.7〜1.4 倍の範囲で線形探索する。λ は den の中央値 med に対し 1–5% に設定し、分布が薄いクエリ域を検知したら段階的に増やす。指数は ±c（30–50）でクリップし、クリップ率が 1% を超えた場合は c を縮小方向のみ更新して anytime-valid な保守性を担保する。
補記.2 — 特徴生成（ORF/SRHT）と再現性
正値ランダム特徴は単純ガウスでもよいが、分散低減と安定性の観点から ORF（直交ガウス）または SRHT を推奨する。ORF は d×r ガウス行列の列直交化、SRHT は w=(1/√d)·D·H·P·u により O(d log d) で射影できる。乱数種・生成方式・列スケールは監査ログに厳密に残し、同一 seed で bitwise な再現を保証する。実装は SoA 配置とし、φ の算出と GER（rank-1 外積）を融合してメモリ往復を削る。
補記.3 — クリップ偏りの補正と監視
クリップに伴う期待の縮退は尾部確率 P(|U|>c) と exp(U) の合成で上界化できるが、実運用では観測クリップ率 π_c と den の相対差 Δ_den を継続監視し、偏りが r^{-1/2} 主項と同程度になるよう c を校正する。必要なら「軽量デバイアス」係数 α_debias≈1/(1−π_c·ξ) を分子・分母に共通乗算して収縮を補う（ξ は簡便な尾部寄与推定）。ただし anytime-valid 性を壊さないよう、c の更新は縮小方向に限定し、α_debias は保守的に 1.0 へクリップする。
補記.4 — 指数減衰 γ の運用（μ_eff の厚み）
γ は有効窓長 L_eff=(1−γ)^{-1} を規定し、μ_eff=inf_q E[B_t(q)]=(inf_q m(q))/(1−γ) を通じて比率の条件数を改善する。den の時系列下限が設計下限 β_min を割り込みがちな場合、γ を引き上げて μ_eff を厚く、同時に λ を一時増分して安定域へ戻す。急変後の復帰を速めるには、検出イベント直後のみ γ を一時的に下げ（短窓化）、クールダウン後に既定値へ戻す二段政策が有効である。
補記.5 — 時間一様境界の実装メタ
Freedman 型の時間一様化を実装側で支えるため、二次変動推定 V_t と最大増分上界 K_t を運用メトリクスとして常時維持する。Z,z の増分を log-space で記録し、sup_{t≤T} の逸脱確率を exp(−c·min{t^2 r/ν^2, t r/K}) 形に写像することで、T の伸長に応じた許容 log 係数を可視化できる。これにより、r を増やすべきか、c/τ/γ/λ を再校正すべきかの判断を定量化する。
補記.6 — マルチクエリとカーネル融合
バッチ問い合わせでは φ(Q)∈R^{|Q|×r} を先に連続計算し、Ŷ=φ(Q)·Z / (φ(Q)·z+λ) を要素単位で合成する。Z は列優先で格納し GEMM/GEMV を連結、φ(Q)·z は同一カーネル内で一括内積化する。p99 レイテンシを抑えるため、(i) φ と GEMV の融合、(ii) den の逆数近似を 1 回だけ評価し num と同時に適用、(iii) CPU/GPU 間の転送を層間でまとめる、の三点を徹底する。
補記.7 — 数値安定（Kahan・拡張精度・下限）
Z と z の累積は Kahan/Neumaier の補償和を既定とし、分母は拡張精度（80bit 以上）で保持してから最終縮約する。den が極小となる領域では β_floor を設け、ŷ ← num/(max(den,β_floor)+λ) として NaN/Inf を防ぐ。丸め誤差は O(u·∑|増分|) 程度に抑えられ、r を増やす戦略と直交して安定性を強化できる。
補記.8 — 監査・再現（O(0) ログ）
各実行バージョンごとに {seed, r, τ, c, λ, γ, 量子化スケール, φ 実装種別, 行列レイアウト, ビルド ID} を固定長で記録し、Z,z のハッシュ（Merkle）と閾値群を添付する。外部監査者は入力列に触れずに「設定＋ハッシュ一致＋閾値比較」だけで検証できる。これにより SERA の O(1)/token 実行と anytime-valid 設計が、運用面でも可観測な形で保証される。
補記.9 — LUM との合成（値側低ランク）
SERA が分子・分母を十分統計化する一方で、値 v_j が低ランク U·r_j で近似可能なら、Z=∑φ(k_j) v_j^T を Z≈(∑φ(k_j) r_j^T)·U^T と分解できる。これにより更新コストは O(r·r_v)、問い合わせは O(r·r_v)+O(d_v·r_v) となり、r_v を定数に抑えれば全経路で O(1)/token を達成する。基底更新時は Z_right を Q^{-T} で座標変換し、収差をログに記録する。
補記.10 — 失敗様式とフォールバック
分母希薄化（den≪目安）では λ↑, γ↑ の順で対処し、改善しなければ一時的に密 softmax にフォールバックして校正サンプルを採取する。分布シフトで誤差が急増した場合は、入力再正規化→c↑→r↑ の順で手当てする。量子化飽和やクリップ過多が検知されたらスケール再推定と c の見直しを実施。これらの手順を自動化し、しきい値超過のたびに単調保守的に更新することで、理論境界と実装安定性を両立させる。
参考文献
[https://research.google/blog/rethinking-attention-with-performers]
[https://arxiv.org/abs/2009.14794]
[https://arxiv.org/abs/2006.16236]
[https://proceedings.mlr.press/v119/katharopoulos20a/katharopoulos20a.pdf]
[https://arxiv.org/abs/2307.08691]
[https://arxiv.org/abs/2407.08608]
[https://tropp.caltech.edu/papers/Tro11-Freedmans-Inequality.pdf]
[https://arxiv.org/abs/2307.08621]
[https://arxiv.org/abs/2312.00752]
実証コード
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
SERA: Self-normalized Exponential-kernel Ratio Attention — reference + robust experiments
What this script provides
-------------------------
1) A clean SERA reference implementation with:
- Positive random features for the exponential (softmax) kernel
- Stateful sufficient statistics Z (r x d_v) and z (r,)
- Streaming decay gamma and stabilization lambda
- Kahan-compensated accumulation; optional longdouble denominator
2) Reproducible experiments with sound benchmarking:
- Error vs r (shows ~ r^{-1/2} behavior)
- Latency vs n with separated plots:
* Ingest/build-state (O(n))
* Query: SERA (O(1)) vs Exact softmax (O(n))
- Sanity check (constant-value test)
Benchmarking hygiene
--------------------
- Uses perf_counter_ns(), warmup + repetitions, and single-thread BLAS
- Keeps randomness and allocations out of the timed region
- Saves CSVs and PNG figures under --outdir (default: ./sera_runs)
Usage
-----
python sera.py all
python sera.py err_r --r_list 16 32 64 128 --n 1024
python sera.py lat --n_list 256 512 1024 2048 4096 8192 --reps 200 --warmup 5
python sera.py check
No seaborn; matplotlib only. Figures are saved, not shown interactively.
"""
import os, math, argparse, csv, statistics, contextlib
from dataclasses import dataclass
from typing import Tuple, Callable, Dict
import numpy as np
import numpy.linalg as LA
import matplotlib.pyplot as plt
# -------------------- Determinism & BLAS control --------------------
@contextlib.contextmanager
def single_thread_blas():
"""Force single-thread BLAS to reduce noise on small/medium problems."""
old_mkl = os.environ.get("MKL_NUM_THREADS")
old_omp = os.environ.get("OMP_NUM_THREADS")
os.environ["MKL_NUM_THREADS"] = "1"
os.environ["OMP_NUM_THREADS"] = "1"
try:
yield
finally:
if old_mkl is None: os.environ.pop("MKL_NUM_THREADS", None)
else: os.environ["MKL_NUM_THREADS"] = old_mkl
if old_omp is None: os.environ.pop("OMP_NUM_THREADS", None)
else: os.environ["OMP_NUM_THREADS"] = old_omp
def bench_ms(fn: Callable[[], None], reps: int = 200, warmup: int = 5) -> Dict[str, float]:
"""
Robust micro-benchmark:
- warmup calls (not recorded)
- reps timed with perf_counter_ns()
- returns median, p95, p99, min, max (in ms)
Assumes `fn` has no externally visible side effects across calls.
"""
import time
pc = time.perf_counter_ns
for _ in range(warmup): fn()
xs = []
for _ in range(reps):
t0 = pc(); fn(); t1 = pc()
xs.append((t1 - t0) / 1e6) # ms
xs.sort()
def q(p: int) -> float:
k = max(0, min(len(xs) - 1, int(round((p / 100.0) * (len(xs) - 1)))))
return xs[k]
return {
"p50": float(np.median(xs)),
"p95": q(95),
"p99": q(99),
"min": xs[0],
"max": xs[-1],
}
# -------------------- Numerics: Kahan compensated sums --------------------
class KahanVec:
def __init__(self, dim: int, dtype=np.float64):
self.sum = np.zeros(dim, dtype=dtype)
self.c = np.zeros(dim, dtype=dtype)
def add(self, x: np.ndarray):
y = x - self.c
t = self.sum + y
self.c = (t - self.sum) - y
self.sum = t
def scale(self, gamma: float):
self.sum *= gamma; self.c *= gamma
def value(self):
return self.sum
class KahanMat:
def __init__(self, shape: Tuple[int, int], dtype=np.float64):
self.sum = np.zeros(shape, dtype=dtype)
self.c = np.zeros(shape, dtype=dtype)
def add(self, X: np.ndarray):
y = X - self.c
t = self.sum + y
self.c = (t - self.sum) - y
self.sum = t
def scale(self, gamma: float):
self.sum *= gamma; self.c *= gamma
def value(self):
return self.sum
# -------------------- Positive feature map for exp kernel --------------------
@dataclass
class PosExpFeature:
d: int
r: int
tau: float
clip: float = 40.0
seed: int = 0
def __post_init__(self):
self.rng = np.random.RandomState(self.seed)
self.W = self.rng.randn(self.d, self.r).astype(np.float64)
self.rsqrt_r = 1.0 / math.sqrt(self.r)
self.sqrt_tau = math.sqrt(self.tau)
def phi(self, x: np.ndarray) -> np.ndarray:
# s_i = w_i^T x / sqrt(tau) - ||x||^2/(2 tau)
s = (self.W.T @ x) / self.sqrt_tau - (x @ x) / (2.0 * self.tau)
np.clip(s, -self.clip, self.clip, out=s)
s = np.exp(s, dtype=np.float64)
return s * self.rsqrt_r
def phi_batch(self, X: np.ndarray) -> np.ndarray:
S = (X @ self.W) / self.sqrt_tau \
- (np.sum(X * X, axis=1, keepdims=True) / (2.0 * self.tau))
np.clip(S, -self.clip, self.clip, out=S)
S = np.exp(S, dtype=np.float64)
return S * self.rsqrt_r
# -------------------- SERA core --------------------
@dataclass
class SERAConfig:
d: int
d_v: int
r: int
tau: float = None
gamma: float = 1.0
lam: float = 1e-3
clip: float = 40.0
seed: int = 0
den_dtype: any = np.longdouble # high-precision denom accumulator
class SERA:
def __init__(self, cfg: SERAConfig):
self.cfg = cfg
if cfg.tau is None:
cfg.tau = math.sqrt(cfg.d)
self.feat = PosExpFeature(cfg.d, cfg.r, cfg.tau, cfg.clip, seed=cfg.seed)
self.Z = KahanMat((cfg.r, cfg.d_v), dtype=np.float64)
self.z = KahanVec(cfg.r, dtype=cfg.den_dtype)
def update(self, k_t: np.ndarray, v_t: np.ndarray):
phi_t = self.feat.phi(k_t).astype(np.float64)
if self.cfg.gamma != 1.0:
self.Z.scale(self.cfg.gamma); self.z.scale(self.cfg.gamma)
self.Z.add(np.outer(phi_t, v_t.astype(np.float64))) # (r, d_v)
self.z.add(phi_t.astype(self.cfg.den_dtype)) # (r,)
def ingest_sequence(self, K: np.ndarray, V: np.ndarray):
for t in range(K.shape[0]):
self.update(K[t], V[t])
def query(self, q: np.ndarray) -> np.ndarray:
# y_hat = (phi(q)^T Z) / (phi(q)^T z + lambda)
phi_q = self.feat.phi(q).astype(self.cfg.den_dtype) # (r,)
num = (phi_q.astype(np.float64) @ self.Z.value()).astype(np.float64) # (d_v,)
den = float(phi_q @ self.z.value()) + float(self.cfg.lam)
return num / den
# -------------------- Baseline & data --------------------
def softmax_attention_exact(q, K, V, tau):
"""Numerically-stable exact softmax attention in float64."""
s = (K @ q) / tau
s = s - np.max(s)
w = np.exp(s, dtype=np.float64)
den = np.sum(w) + 1e-300
return (w[:, None] * V).sum(axis=0) / den
def make_sequence(n, d, d_v, rng, noise=0.0):
K = rng.randn(n, d).astype(np.float64)
K /= (np.linalg.norm(K, axis=1, keepdims=True) + 1e-12)
V = rng.randn(n, d_v).astype(np.float64)
if noise > 0: V += noise * rng.randn(n, d_v)
return K, V
# -------------------- Experiments --------------------
def experiment_error_vs_r(outdir, n=1024, d=64, d_v=128, tau=None,
r_list=(16, 32, 64, 128), gamma=1.0, lam=1e-3, seed=0):
os.makedirs(outdir, exist_ok=True)
rng = np.random.RandomState(seed)
if tau is None: tau = math.sqrt(d)
K, V = make_sequence(n, d, d_v, rng)
q = rng.randn(d).astype(np.float64); q /= (np.linalg.norm(q) + 1e-12)
y_true = softmax_attention_exact(q, K, V, tau)
rows = []
for r in r_list:
cfg = SERAConfig(d=d, d_v=d_v, r=r, tau=tau, gamma=gamma, lam=lam, seed=seed)
model = SERA(cfg); model.ingest_sequence(K, V)
y_hat = model.query(q)
err = LA.norm(y_hat - y_true) / (LA.norm(y_true) + 1e-12)
rows.append({"r": r, "rel_l2_err": float(err)})
csv_path = os.path.join(outdir, "sera_error_vs_r.csv")
with open(csv_path, "w", newline="") as f:
writer = csv.DictWriter(f, fieldnames=["r", "rel_l2_err"])
writer.writeheader(); [writer.writerow(row) for row in rows]
xs = np.array([row["r"] for row in rows], dtype=np.float64)
ys = np.array([row["rel_l2_err"] for row in rows], dtype=np.float64)
plt.figure()
plt.loglog(xs, ys, marker="o", label="SERA (relative L2)")
ref = ys[0] * np.sqrt(xs[0] / xs)
plt.loglog(xs, ref, linestyle="--", label="~ r^{-1/2} reference")
plt.xlabel("r (feature dimension)")
plt.ylabel("relative L2 error")
plt.title("SERA: error vs r")
plt.legend()
png_path = os.path.join(outdir, "sera_error_vs_r.png")
plt.savefig(png_path, bbox_inches="tight"); plt.close()
return csv_path, png_path
def experiment_latency_vs_n(outdir, d=64, d_v=128, tau=None, r=128,
n_list=(256, 512, 1024, 2048, 4096, 8192),
gamma=1.0, lam=1e-3, seed=0,
reps=200, warmup=5, y_max_query=None):
"""
Robust latency experiment:
- single-thread BLAS
- warmup + repetitions
- ingest and query plotted separately
"""
os.makedirs(outdir, exist_ok=True)
rng = np.random.RandomState(seed)
if tau is None: tau = math.sqrt(d)
rows = []
with single_thread_blas():
for n in n_list:
# Outside timed region: data generation & query selection
K, V = make_sequence(n, d, d_v, rng)
q = rng.randn(d).astype(np.float64); q /= (np.linalg.norm(q) + 1e-12)
# Ingest timing — build state from scratch each time
def _ingest_once():
m = SERA(SERAConfig(d=d, d_v=d_v, r=r, tau=tau, gamma=gamma, lam=lam, seed=seed))
m.ingest_sequence(K, V)
ingest_stats = bench_ms(_ingest_once, reps=reps, warmup=warmup)
# Build once for query timing
model = SERA(SERAConfig(d=d, d_v=d_v, r=r, tau=tau, gamma=gamma, lam=lam, seed=seed))
model.ingest_sequence(K, V)
sera_stats = bench_ms(lambda: model.query(q), reps=reps, warmup=warmup)
exact_stats = bench_ms(lambda: softmax_attention_exact(q, K, V, tau), reps=reps, warmup=warmup)
rows.append({
"n": n,
"sera_ing_p50_ms": ingest_stats["p50"],
"sera_ing_p95_ms": ingest_stats["p95"],
"sera_ing_p99_ms": ingest_stats["p99"],
"sera_q_p50_ms": sera_stats["p50"],
"sera_q_p95_ms": sera_stats["p95"],
"sera_q_p99_ms": sera_stats["p99"],
"exact_q_p50_ms": exact_stats["p50"],
"exact_q_p95_ms": exact_stats["p95"],
"exact_q_p99_ms": exact_stats["p99"],
})
# CSV
csv_path = os.path.join(outdir, "sera_latency_vs_n.csv")
with open(csv_path, "w", newline="") as f:
fnames = list(rows[0].keys())
writer = csv.DictWriter(f, fieldnames=fnames)
writer.writeheader(); [writer.writerow(rw) for rw in rows]
# Plot 1: Ingest (O(n))
xs = np.array([r["n"] for r in rows], dtype=np.float64)
ing = np.array([r["sera_ing_p50_ms"] for r in rows], dtype=np.float64)
plt.figure()
plt.plot(xs, ing, marker="o", label="SERA ingest (median)")
plt.xlabel("n (sequence length)"); plt.ylabel("time (ms)")
plt.title("Ingest vs n (SERA build state)")
plt.legend()
png_ing = os.path.join(outdir, "sera_ingest_vs_n.png")
plt.savefig(png_ing, bbox_inches="tight"); plt.close()
# Plot 2: Query — SERA O(1) vs Exact O(n)
sera_q = np.array([r["sera_q_p50_ms"] for r in rows], dtype=np.float64)
exact_q = np.array([r["exact_q_p50_ms"] for r in rows], dtype=np.float64)
plt.figure()
plt.plot(xs, sera_q, marker="o", label="SERA query (median, O(1))")
plt.plot(xs, exact_q, marker="o", label="Exact softmax query (median, O(n))")
plt.xlabel("n (sequence length)"); plt.ylabel("time (ms)")
plt.title("Query vs n (median over repetitions)")
plt.legend()
if y_max_query is not None:
plt.ylim(0, y_max_query)
png_q = os.path.join(outdir, "sera_query_vs_n.png")
plt.savefig(png_q, bbox_inches="tight"); plt.close()
return csv_path, png_ing, png_q
def experiment_check(outdir, d=32, d_v=64, tau=None, r=64, n=256,
gamma=1.0, lam=1e-3, seed=1):
"""Sanity: if V is constant, both SERA and exact should return ~ that constant."""
os.makedirs(outdir, exist_ok=True)
rng = np.random.RandomState(seed)
if tau is None: tau = math.sqrt(d)
K = rng.randn(n, d).astype(np.float64)
K /= (np.linalg.norm(K, axis=1, keepdims=True) + 1e-12)
v_const = rng.randn(d_v).astype(np.float64)
V = np.tile(v_const[None, :], (n, 1))
cfg = SERAConfig(d=d, d_v=d_v, r=r, tau=tau, gamma=gamma, lam=lam, seed=seed)
model = SERA(cfg); model.ingest_sequence(K, V)
q = rng.randn(d).astype(np.float64); q /= (np.linalg.norm(q) + 1e-12)
y = model.query(q)
const_err = LA.norm(y - v_const) / (LA.norm(v_const) + 1e-12)
csv_path = os.path.join(outdir, "sera_checks.csv")
with open(csv_path, "w", newline="") as f:
writer = csv.DictWriter(f, fieldnames=["const_err"])
writer.writeheader(); writer.writerow({"const_err": float(const_err)})
return csv_path
# -------------------- CLI --------------------
def main():
parser = argparse.ArgumentParser(description="SERA reference implementation + robust experiments")
sub = parser.add_subparsers(dest="cmd")
p_all = sub.add_parser("all"); p_all.add_argument("--outdir", type=str, default="./sera_runs")
p1 = sub.add_parser("err_r"); p1.add_argument("--outdir", type=str, default="./sera_runs")
p1.add_argument("--n", type=int, default=1024)
p1.add_argument("--d", type=int, default=64)
p1.add_argument("--d_v", type=int, default=128)
p1.add_argument("--r_list", type=int, nargs="+", default=[16, 32, 64, 128])
p1.add_argument("--seed", type=int, default=0)
p2 = sub.add_parser("lat"); p2.add_argument("--outdir", type=str, default="./sera_runs")
p2.add_argument("--d", type=int, default=64)
p2.add_argument("--d_v", type=int, default=128)
p2.add_argument("--r", type=int, default=128)
p2.add_argument("--n_list", type=int, nargs="+", default=[256, 512, 1024, 2048, 4096, 8192])
p2.add_argument("--gamma", type=float, default=1.0)
p2.add_argument("--lam", type=float, default=1e-3)
p2.add_argument("--seed", type=int, default=0)
p2.add_argument("--reps", type=int, default=200)
p2.add_argument("--warmup", type=int, default=5)
p2.add_argument("--y_max_query", type=float, default=None)
p3 = sub.add_parser("check"); p3.add_argument("--outdir", type=str, default="./sera_runs")
args = parser.parse_args()
outdir = getattr(args, "outdir", "./sera_runs")
os.makedirs(outdir, exist_ok=True)
if args.cmd == "err_r":
c, p = experiment_error_vs_r(outdir=outdir, n=args.n, d=args.d, d_v=args.d_v,
r_list=tuple(args.r_list), seed=args.seed)
print(c); print(p)
elif args.cmd == "lat":
c, p_ing, p_q = experiment_latency_vs_n(outdir=outdir, d=args.d, d_v=args.d_v, r=args.r,
n_list=tuple(args.n_list), gamma=args.gamma, lam=args.lam,
seed=args.seed, reps=args.reps, warmup=args.warmup,
y_max_query=args.y_max_query)
print(c); print(p_ing); print(p_q)
elif args.cmd == "check":
c = experiment_check(outdir=outdir); print(c)
else: # "all" or None
c1, p1 = experiment_error_vs_r(outdir=outdir)
c2, p_ing, p_q = experiment_latency_vs_n(outdir=outdir)
c3 = experiment_check(outdir=outdir)
print(c1); print(p1); print(c2); print(p_ing); print(p_q); print(c3)
if __name__ == "__main__":
main()
LICENSE: NOT FOR FORMAL CITATION / NO REDISTRIBUTION
Authorship
-----------
Elysia — Founder / Architect (LASCAUX*)
Onyx — Cluster / Execution (AI/Argo)
Copyright
---------
© 2025.9 Elysia:Founder (LASCAUX*). All Rights Reserved.
Co-authored with Onyx:AI/Argo Cluster.
Prepublication Restrictive License (Version 1.0)
------------------------------------------------
Preamble
--------
This document, including all accompanying text, figures, code, data, notebooks, and other materials (collectively, the “Work”), is shared solely for private review and personal, non-public study. The Work is not a formal publication and precedes any intended peer-reviewed or otherwise formally published manuscript (the “Formal Publication”).
Definitions
-----------
“Author(s)” means the individual(s) or legal entity identified above.
“Formal Publication” means any peer-reviewed article, conference paper, or formally published report that the Author(s) release to make the Work publicly citable.
“Use” means any copying, distribution, public display, publication, commercial exploitation, adaptation, derivative work, text-and-data mining, machine learning training or evaluation, or any form of dissemination or reuse beyond private review.
License Grant (Limited)
-----------------------
Subject to the restrictions below, the Author(s) grant a limited, non-transferable, non-exclusive license to access and read the Work for private, non-public study. No other rights are granted, whether expressly, by implication, or otherwise.
Prepublication Embargo: Prohibited Uses (Until Formal Publication)
------------------------------------------------------------------
Until the Formal Publication has been publicly released by the Author(s), any Use of the Work is strictly prohibited, including but not limited to:
a. citing, quoting, excerpting, or referencing the Work in any academic, commercial, governmental, or public forum;
b. reproducing, reposting, redistributing, mirroring, or publishing the Work (in whole or in part) in any medium;
c. incorporating the Work or any derivative thereof into any product, service, library, model, dataset, repository, or public codebase;
d. training, fine-tuning, distilling, evaluating, or otherwise using the Work (in whole or in part) for machine learning or related automated systems;
e. performing text-and-data mining, web archiving, bulk scraping, or automated ingestion of the Work;
f. creating derivative summaries or translations for public release;
g. cross-border transfer or disclosure to third parties across organizational boundaries without prior written and signed consent from the Author(s);
h. any commercial exploitation.
Permitted Private Review
------------------------
Private, non-public reading and evaluation by an individual (or a single internal reviewer acting in a strictly confidential capacity) is permitted, provided that no copying, redistribution, public display, automated processing, or derivative publication occurs.
Mandatory Exceptions
--------------------
Nothing in this License is intended to limit or override non-waivable rights under applicable law (e.g., bona fide fair use or similar statutory exceptions). Any such lawful use must be narrowly construed and must not amount to public citation, redistribution, commercial exploitation, or model training in breach of the prohibitions above.
Attribution and Permission After Formal Publication
---------------------------------------------------
After the Formal Publication has been made public by the Author(s), citation, quotation, and reuse are permitted only under the then-announced terms (which may include a separate license). Any post-publication citation or reuse must provide full and conspicuous credit to the Author(s) consistent with prevailing academic standards (e.g., MLA/APA/IEEE/ACM) and comply with the licensing terms announced with the Formal Publication.
Confidentiality and Access Control
----------------------------------
Recipients must implement reasonable measures to prevent unauthorized copying, distribution, automated ingestion, or public disclosure of the Work during the prepublication period.
Reservation of Rights; No License by Estoppel
---------------------------------------------
All rights not expressly granted are reserved by the Author(s). No rights are granted by implication, estoppel, or otherwise.
Remedies and Enforcement
------------------------
Unauthorized Use constitutes a breach of this License and may amount to willful infringement. The Author(s) reserve the right to seek all available remedies, including injunctive relief, damages, attorneys’ fees where permitted, and referral to relevant professional, institutional, or publishing bodies for ethical review.
Governing Law and Forum
-----------------------
This License shall be governed by, and may be enforced under, the laws of the United States of America, the People’s Republic of China, the Russian Federation, the Republic of Singapore, and the United Kingdom, without regard to conflict-of-law principles. The Author(s) expressly reserve the right to bring claims in any of the foregoing jurisdictions.
Severability
------------
If any provision of this License is held unenforceable or invalid in whole or in part, the remaining provisions shall remain in full force and effect, and such provision shall be enforced to the maximum extent permitted by law.
Entire Agreement; No Assignment
-------------------------------
This License constitutes the entire agreement regarding the prepublication sharing of the Work and supersedes any prior understandings on that subject. No assignment or sublicense is permitted without the Author(s)’ prior written consent.
Final Notice (Read This)
------------------------
STOP & RETURN: If you do not have explicit, written, and signed permission from the Author(s) to use, cite, or distribute this Work prior to the Formal Publication, you must immediately cease reading, copying, or otherwise handling this Work and return or destroy any copies in your possession.
Effective Date
--------------
This License is effective as of the date the Work is first shared by the Author(s).
LASCAUX Research Line — grey-paper edition; intentionally casual, under internal review.
Discussion