nx_kv_cache.nx

nx_kv_cache.nx -- autoregressive attention KV cache. THE foundation primitive of efficient autoregressive generation (LLM serving, forever-generating world models, autoregressive diffusion). Without it, each new token recomputes attention over every past token: O(n^2) per step. With it: O(n) per step. For n=1000 generation steps that's a 1000x speedup with bit- identical output (algorithmic correctness, not approximation). Per the min-hardware-floor + algo-led cardinal: this brick is what makes a $50 SBC run autoregressive generation that a naive O(n^2) recompute couldn't finish in a year. Composes with: * nx_sparse_tensor -- KV cache rows are mostly zero post-softmax; store sparse, compute sparse * nx_quant_block -- cached K and V can be 4-bit; 10x less memory bandwidth at each new-token step * nx_compute_graph -- KV cache is a typed CONTROL node in the graph; runner persists state across runs of the same graph Storage layout: k_storage[head * max_seq_len * head_dim + pos * head_dim + d] v_storage[head * max_seq_len * head_dim + pos * head_dim + d] Multi-head attention works by treating each head as an independent per-position dot product space. We don't materialise the [Q, K, V] triple as a single tensor here -- the cache OWNS K and V, the caller's Q changes every step. genealogy_id: vaswani_2017_transformer_kv + flashattention_2_kv + pope_2023_efficient_serving + mistral_sliding_window lineage_id: substrate_kv_cache_v1