HALO: An Attention-Free Language Model: Architecture Built from Compressed Sensing

Abstract

Autoregressive transformers store the entire context uncompressed---the key--value cache \emph{is} the raw signal---and reconstruct a context summary at every decoding step by exhaustive pairwise comparison. Compressed learning teaches that this is unnecessary: when a signal is sparse in a suitable dictionary, inference can be carried out directly on a small number of random linear measurements, and reconstruction can be skipped entirely. We take this principle to its logical conclusion and propose \textbf{HALO} (Holographic Autoregressive Language Operator), a causal language model containing no attention, no softmax over positions, and no KV cache. HALO represents every token as a $k$-sparse code over a wide dictionary, maintains context exclusively as a fixed-size multi-timescale \emph{compressive sketch}---a certified restricted-isometry measurement of the sparse context trajectory---and performs all computation in measurement space: retrieval is matched filtering and holographic unbinding, the only nonlinearity is a Top-$K$ operation that coincides with one step of iterative hard thresholding, and network depth is therefore unrolled sparse inference. All temporal mixing is performed by \emph{fixed} structured-random isometries; only pointwise dictionaries, probes, and readouts are learned. Compressed-sensing theory then supplies what heuristic state-space models lack: a closed-form formula for state size as a function of context horizon and sparsity, and a signal-to-noise guarantee for retrieval. Inference requires $O(1)$ memory per sequence and per-token compute independent of context length. A 1.4M-parameter CPU prototype confirms the theory: sketch retrieval SNR matches the predicted $\sqrt{M/kT}$ law to two decimal places, associative recall---the task attention is presumed necessary for---reaches $94.9\%$ accuracy (chance $12.5\%$), and character-level language modeling trains stably to $0.94$ nats/char against a $2.47$ nats/char bigram baseline - relevant repo is located here: \url{https://github.com/andrew-jeremy/halo---attention-free-CS-vLLM}

Keywords