Experiment: Hadamard-rotierter INT8-KV-Cache (FWHT) vs INT8/KIVI

[geisten]

Experiment: Hadamard-rotierter INT8-KV-Cache (FWHT) vs. INT8 / KIVI

Kontext

llama.cpp PR ggml-org/llama.cpp#21038
(gemerged) rotiert Q/K/V mit einer orthonormalen Hadamard-Matrix vor der
Attention und rotiert den Output zurück. Das glättet Aktivierungs-Ausreißer und
verbessert die Qualität bestehender symmetrischer Low-Bit-Cache-Quants bei
~0 Speicherkosten (QuaRot/TurboQuant-Idee). Headline-Zahlen: Qwen3 0.6B
q4_1-Cache PPL 212 → 22, q5_1 62 → 14; q8_0 unverändert.

geist löst dasselbe Ausreißer-Problem heute mit KIVI (2-bit asymmetrisch,
per-channel-K) und hat einen INT8-Modus, der K, V und Q symmetrisch
per-head quantisiert:

• Q-Quant (INT8-Modus): src/archs/transformer/forward/attention.c:257
• K/V-Quant (INT8-Modus): src/archs/transformer/forward/kv_store.c:69
• KIVI: src/backends/common/kivi.h, .../forward/attention.c:36

Der INT8-Pfad ist der Kandidat: dort sind beide Seiten des Skalarprodukts
symmetrisch quantisiert, also trifft eine Rotation die Ausreißer auf Q- und
K-Seite. KIVI umgeht das strukturell (Q bleibt fp32).

Hypothese

Eine Hadamard-Rotation vor dem INT8-Quant bringt den INT8-Cache nahe an
KIVI-Qualität — bei weniger Code und weniger Laufzeit-Buchhaltung (keine
128er-Gruppen, keine per-channel scales/zeros). Falls ja: simplere Cache-Variante.
Falls nein: wegwerfen, KIVI bleibt.

Umsetzung (minimal, hinter Env-Flag)

GEIST_KV_ROT=1 (analog zum LLAMA_ATTN_ROT_DISABLE des PR), nur im INT8-Modus wirksam.

1. FWHT statt Matmul. Der PR nutzt einen n×n-Matmul nur wegen Backend-Agnostik.
   Auf CPU nimmt geist die Fast Walsh–Hadamard Transform in-place, O(n·log n)
   Butterfly über head_dim (Gemma4: 256/512, sonst 128 — alle Zweierpotenzen).
   Normierung 1/√n → Matrix ist ihr eigenes Inverses (forward = backward).
   Neue Datei src/backends/common/fwht.{h,c}, ~30 Zeilen + Self-Check.
2. Einfügepunkte (nach RoPE, damit Q·K erhalten bleibt — H beidseitig):
   • Q rotieren direkt vor der Quantisierung in attention.c:257.
   • K und V rotieren vor dem Quant-Store in kv_store.c:69.
   • Attention-Output (Σ softmax·V_rot) mit derselben FWHT zurückrotieren, vor o_proj.
3. Keine neuen Typen, kein neuer geist_kv_mode — der Cache bleibt bit-identisch
   INT8, nur der Inhalt ist rotiert. Flag aus = exakt heutiges Verhalten.

Messung

Eval-Harness (PPL + MMLU) auf mind. zwei Modellen, jeweils 3 Konfigurationen:

Modus	Q	K/V	erwartet
INT8 (heute)	int8	int8	Baseline
INT8 + ROT	int8 rotiert	int8 rotiert	Hypothese: ↑ nahe KIVI
KIVI (heute)	fp32	2-bit	Qualitäts-Referenz
FP32	fp32	fp32	oberer Anker

Zusätzlich Prefill/Decode-Kosten der FWHT auf dem A76 (Pi5) messen — die
Butterfly-Pässe liegen im heißen Decode-Pfad und müssen sich im Rauschen bewegen,
sonst kippt der ganze Sinn (CPU-Effizienz). Bench-Protokoll wie üblich:
Pi5 quiesced/mean-of-10, Mac best-of-10.

Erfolgskriterium

INT8+ROT schließt ≥ ~70 % der PPL/MMLU-Lücke zwischen INT8 und KIVI und
FWHT-Overhead < ~2 % Decode auf A76 → lohnt als simplere Alternative, KIVI ggf.
ablösen/optional machen. Sonst: Ergebnis dokumentieren, Branch schließen.

Nicht-Ziele

• Kein neues Cache-Format, keine randomisierten Hadamard-Matrizen (PR-Follow-up),
  kein MLA, keine Fusion in Attention-Gewichte (QuaRot-Stufe 2). Erst messen, ob
  sich der Ansatz überhaupt trägt.

[geisten]

Erste Messung: Rotation bewegt bei 8-Bit-KV nichts (erwartungsgemäß)

bench_kv_quality misst jetzt alle Modi in einem Lauf (top-1 next-token accuracy, cpu_neon, 317 eval-Positionen).

kv_mode	Gemma4-e2b Q4_K	BitNet-2b4t i2_s
FP32	0.1987	0.4263
INT8	0.2019	0.4295
INT8+ROT	0.2019	0.4295
KIVI (2-bit)	0.2050	0.3846

Deutung

• INT8 ist bereits verlustfrei (INT8 ≥ FP32, im Rauschen) → es gibt bei 8 Bit keine Ausreißer-Lücke, die eine Rotation schließen könnte. Deckt sich 1:1 mit der q8_0-Zeile in llama.cpp#21038, die ebenfalls unverändert blieb; die großen Gewinne dort kamen ausschließlich bei q4/q5.
• Die reale Quant-Lücke sitzt im Low-Bit-Pfad: bei BitNet verliert 2-bit-KIVI 4.5% (0.4295 → 0.3846). Dort würde Ausreißer-Glättung etwas bringen.

Konsequenz

Das ursprüngliche Erfolgskriterium (INT8→KIVI-Lücke via INT8+ROT schließen) ist nicht erreichbar, weil INT8 keine Lücke hat. Der PR-Nutzen entsteht erst < 5 Bit.

→ Weiter mit Option A: Rotation dorthin bringen, wo Quant-Rauschen beißt — ein rotierter symmetrischer INT4-KV-Cache. Nächster Schritt: INT4-Quant-Grid (zunächst als Quality-Sim in den INT8-Containern, ohne neue Buffer/Kernel) messen, ob ROT den INT4→INT8-Abstand schließt. Trägt es, folgt echtes gepacktes INT4 für den Speichergewinn.

Implementierung/Bench liegen auf feat/rot-kv-cache-fwht-61 (FWHT self-inverse + dot-preserving, Unit-Test grün).

[geisten]

KLD-Messung: Rotation wirkt bei Low-Bit — aber schlägt KIVI nicht

top-1-Accuracy war zu grob (sättigt, Sub-1%-Rauschen). bench_kv_quality misst jetzt zusätzlich mittlere KL(P_fp32 ‖ P_mode) in nats — token-weise teacher-forced im Lockstep gegen eine FP32-Referenzsession (public session API: prefill_tokens + peek_logits). Modell lädt einmal, jeder Modus ist eine Session; KL über den gemeinsamen finiten Support (BitNets nicht-finite Dead-Vocab-Slots vergiften sonst).

Ergebnis (mean KL, niedriger = näher an FP32)

kv_mode	Gemma4-e2b¹	BitNet-2b4t
FP32	0.00000	0.00000
INT8	0.833	0.00197
INT8+ROT	0.481	0.00199
INT4	3.591	0.01275
INT4+ROT	1.828	0.00861
INT2	18.51	1.635
INT2+ROT	14.86	0.915
KIVI (asym 2-bit)	2.516	0.262

¹ Gemmas Absolutwerte sind durch den nicht angewendeten final_logit_softcapping aufgebläht (ich softmaxe rohe Logits) — die Ordnung stimmt, die Skala nicht. BitNet (kein Softcap) liefert die vertrauenswürdigen Absolutwerte.

Was KL zeigt (und top-1 verdeckte)

1. Rotation senkt die KL bei jeder Low-Bit-Stufe — BitNet: INT4 −33%, INT2 −44%; bei INT8 praktisch nichts (0.00197→0.00199). Deckt sich mit der q8_0-Zeile aus llama.cpp#21038.
2. INT4+ROT ist quasi verlustfrei (BitNet KL 0.0086, ~1.5× INT8) — und ~30× näher an FP32 als KIVI (0.262). Anderer Betriebspunkt: 4 Bit statt 2, dafür ohne per-channel/Gruppen-Buchhaltung.
3. Symmetrisches INT2+ROT schlägt KIVI nicht (0.915 vs 0.262). KIVIs asymmetrisches per-channel-K bleibt beim 2-Bit-Budget klar vorn → die „lazier KIVI"-Hypothese ist bei 2 Bit widerlegt.

Fazit für #61

Der verwertbare Gewinn ist ein gepackter symmetrischer INT4-KV-Cache mit Rotation: near-lossless bei halbem INT8-Speicher, deutlich simpler als KIVI. Bei 2 Bit bleibt KIVI die richtige Wahl.

Nächste Schritte (in dieser Reihenfolge):

1. A76-Kosten der FWHT im Decode-Hotpath messen (Pi5) — bevor irgendetwas gebaut wird; kann den Speichergewinn auffressen.
2. Trägt es kostenseitig → gepacktes INT4 (2 Werte/Byte + INT4-Attention-Kernel) für den echten Speichergewinn.

Bisher ist INT4/INT2 nur ein Quality-Sim in INT8-Containern (kein Speichergewinn) — bewusst, um erst die Qualitätsfrage zu klären. Alles auf feat/rot-kv-cache-fwht-61.

[geisten]

A76-Kosten der FWHT-Rotation (Raspberry Pi 5)

Decode-Overhead von GEIST_KV_ROT=1 gegenüber reinem INT8, gemessen mit bench_session_throughput auf einem dedizierten, quiesced Pi5 (Cortex-A76 @ 2.4 GHz, 4 Threads, OMP_WAIT_POLICY=active, load 0.00). 128 Decode-Tokens, mean-of-5, Varianz < 1%.

Modell	head_dim	INT8 decode	INT8+ROT decode	Overhead
gemma4-e2b Q4_K	256	136.5 ms/tok (7.33 tok/s)	140.9 ms/tok (7.10 tok/s)	+3.3% (+4.4 ms/tok)
bitnet-2b4t i2_s	128	65.0 ms/tok (15.39 tok/s)	65.6 ms/tok (15.23 tok/s)	+1.0% (+0.7 ms/tok)

Die konsistente, reproduzierbare Differenz ist zugleich der Nachweis, dass die Rotation aktiv ist (wäre sie ein No-op, wären die Zeiten identisch).

Deutung

• Der Overhead skaliert mit head_dim (mehr Butterfly-Pässe + längere Zeilen) und Head-Zahl. Für das Pi-Flaggschiff BitNet (head_dim 128) nur ~1%; für Gemmas head_dim 256 ~3.3%.
• Beides ist moderat und liegt in der Größenordnung, die der ursprüngliche Kostenrahmen erwartet hat (≤~2% Ziel; BitNet darunter, Gemma knapp darüber wegen größerem head_dim).
• Die FWHT läuft auf den fp32-Aktivierungen vor der Quantisierung — die Kosten sind daher unabhängig vom Quant-Grid. Ein echtes gepacktes INT4 würde dieselben Zeilen rotieren, also gilt dieser Overhead auch dort.

Gesamtbild für #61

Achse	Befund
Qualität (KLD)	INT4+ROT near-lossless, ~30× näher an FP32 als KIVI (bei 4 statt 2 Bit)
Kosten (A76)	+1% (BitNet) … +3.3% (Gemma) Decode
Speicher	gepacktes INT4 = halber INT8-KV-Cache
Komplexität	keine per-channel/Gruppen-Buchhaltung wie KIVI

→ Ein gepackter symmetrischer INT4-KV-Cache mit Rotation ist auf dem Pi ein guter Trade: ~halber KV-Speicher, near-lossless, für ~1–3% Decode. Auf dem 4-GB-Pi ist Speicher knapp → attraktiv. Bei 2 Bit bleibt KIVI.

Nächster (echter) Schritt

Gepacktes INT4 bauen: 2 Werte/Byte im K/V-Cache + INT4-Attention-Kernel (dequant-on-read). Das ist der erste Baustein mit echtem Speichergewinn — bisher ist INT4 nur ein Quality-Sim in INT8-Containern. Größerer Baustein (neue Buffer + Kernel + exec_plan-Sizing), daher als eigener Schritt.

Messungen auf Branch feat/rot-kv-cache-fwht-61.

[geisten]

Gepacktes INT4 gebaut (GEIST_KV_INT4=1) — der echte Speichergewinn

Neuer öffentlicher KV-Modus GEIST_KV_INT4: zwei 4-Bit-Werte pro Byte, halber INT8-Datenspeicher für K/V, per-token per-head Skala, optionale Rotation (GEIST_KV_ROT). Reitet auf dem INT8-Pfad (gleiche Buffer-Slots, halb alloziert; gleiche Skalen + ctx-Verdrahtung) mit gepacktem Append-Zweig und Unpack-Kernel attention_int4_via_buffers.

Korrektheit

• KL bit-identisch zum früheren INT8-Container-Sim (BitNet INT4 0.01275, +ROT 0.00861) → Pack/Unpack korrekt.
• int4_kv.h Pack/Unpack hat einen Unit-Test (Sign-Extension der Nibbles ist die fehleranfällige Stelle).
• INT8 + KIVI unverändert (Regression geprüft). Kohärente Generierung mit INT4 und INT4+ROT.

A76-Decode-Kosten (Pi5, BitNet-2b4t, 128 Tokens, mean-of-5, quiesced)

Modus	ms/tok	vs INT8
INT8	64.1	—
INT4 packed	64.8	+1.1%
INT4+ROT	65.7	+2.5%

Der Unpack hebt die halbierte KV-Bandbreite bei kurzem Kontext fast auf → Decode nur ~1% teurer. Der Wert ist Speicherkapazität, nicht Tempo: bei langem Kontext (großer KV-Cache) wächst sowohl die Speicherersparnis als auch der BW-Vorteil.

Gesamtbild

Achse	INT4+ROT
Qualität	near-lossless (KL 0.0086, ~30× näher an FP32 als KIVI bei 4 statt 2 Bit)
Speicher	halber INT8-KV-Datenspeicher
Decode-Kosten (A76)	+2.5% vs INT8
Komplexität	keine per-channel/Gruppen-Buchhaltung

Modus-Auswahl: INT4 nicht automatisch gegen KIVI arbitrieren

INT4+ROT (4-Bit, near-lossless, halber Speicher) und KIVI (2-Bit, aggressiver, viertel Speicher, Qualitätsabfall) sind verschiedene Betriebspunkte. Die Wahl ist ein Qualität/Speicher-Tradeoff des Aufrufers, nicht der Plattform — eine „pick-best-per-env"-Heuristik würde diesen Tradeoff für den Nutzer raten. Daher: expliziter Modus (GEIST_KV_INT4 / opts.kv_mode), INT8 bleibt Default. Guidance dokumentieren, Aufrufer wählt.

Offene Punkte / Follow-ups

• Gepacktes INT4 spart nur den Datenteil, Skalen bleiben fp32 per-token-per-head — bei kurzem head_dim nicht vernachlässigbar; ok für den Zweck.
• Kein GPU/Metal-Pfad (CPU-Experiment).
• Bei langem Kontext neu benchen — dort sollte INT4 den BW-Vorteil zeigen (evtl. schneller als INT8).

Alles auf feat/rot-kv-cache-fwht-61. Aus meiner Sicht ist #61 damit vollständig beantwortet und bereit für einen PR.