Source-linked AI summary
Single-Layer MeMo as a Randomized Hamming-Kernel Classifier
Alessandro Straziota
TL;DR
The paper asks what classifier single-layer MeMo implements and how its randomized representation affects prediction. It identifies a positional Hamming-kernel classifier and analyzes the sketching and decoding errors. On a restricted WikiText-2 task, fused MeMo trades accuracy against throughput and memory relative to the exact classifier.
Problem
MeMo’s single-layer retrieval had been described as an approximate counter, leaving its precise learning problem and partial-match geometry unspecified.
Source: §1 · p. 1Method
The paper identifies the ideal retrieval rule as a positional Hamming-kernel classifier and analyzes context-sketching and output-decoding errors under independent input and output codebooks.
Source: §1 · pp. 1–2, §4 · p. 4Results
At batch size 1024, fused MeMo with d = 256 processes 40.00 million queries per second versus 33.33 million for the exact sum prototype, uses 4.12 MiB versus 65.00 MiB, and has 18.76% versus 22.30% mean top-1 accuracy.
Source: §6.2 · p. 12Takeaways & Limitations
On the restricted WikiText-2 task, MeMo offers a trade-off among predictive accuracy, memory, and throughput, with matrix-operation parallelization particularly useful on a GPU.
Source: §1 · p. 2, §6.2 · p. 12The unbiased-score result relies on independent input and output codebooks; tied codes can produce bias when output tokens recur in contexts.
Source: §4 · p. 4
Abstract
from arXiv · showhide
MeMo (Zanzotto et al., 2025) is a recent language-model architecture that stores associations between token contexts and next tokens in a correlation matrix memory. In this work, we study its single-layer form and show that its ideal retrieval rule is a multiclass classifier based on the positional Hamming kernel. The MeMo architecture represents both the sequence features and the output labels with Gaussian random codes. Its score is therefore a doubly randomized sketch of the ideal classifier. Under independent input and output codebooks, we bound the errors introduced by context sketching and output decoding, characterize their dependence on model and data parameters, and give a margin-based guarantee for recovering the ideal prediction. Controlled simulations support the trends predicted by the analysis. On a restricted WikiText-2 next-token task, we compare single-layer MeMo with classical baselines and show that it can offer a useful trade-off among predictive accuracy, memory, and throughput, particularly on a GPU, where its matrix operations can be parallelized.
1 INTRODUCTION
The introduction frames explicit memory as a way to store token-context associations, then identifies single-layer MeMo with a positional Hamming-kernel classifier. It presents the analysis of randomized retrieval and its empirical evaluation as the paper’s contributions.
1 INTRODUCTION
- Explicit-memory architectures make stored associations more directly accessible for inspection or editing than associations encoded in transformer parameters.The introduction motivates this direction with prior work on explicit memory (Berges et al., 2025; Behrouz et al., 2025).Source: §1 · p. 1
- Single-layer MeMo implements a positional Hamming-kernel classifier: each candidate label accumulates similarity from stored contexts with that label.The kernel counts matching token positions, and the prediction is the label with the largest accumulated similarity.Source: §1 · pp. 1–2
- MeMo uses random codes for context features and output labels, so its classifier is only an approximate implementation.The paper analyzes context-sketching and output-decoding errors and combines the bounds with the ideal classifier’s margin to guarantee exact recovery under stated conditions.Source: §1 · p. 2
- The evaluation combines controlled simulations with a restricted WikiText-2 next-token comparison of fidelity, accuracy, memory use, and inference throughput.The introduction describes the task as an assessment against classical baselines, not a full language-model benchmark.Source: §1 · p. 2
- The paper distinguishes its analysis from prior associative-memory scaling work by studying MeMo’s token-based context encoding and recovery of the positional Hamming-kernel classifier.Related work includes correlation matrix memories, MeMo, and whole-input random-code analyses (Cabannes et al., 2024).Source: §1 · p. 2
2 PRELIMINARIES
The preliminaries define fixed-length token contexts and a data multiset, then introduce independent Gaussian codebooks and a random projection for representing them. The positional feature map keeps token positions separate and induces the positional Hamming kernel.
2 PRELIMINARIES
- A context is a length-h sequence over a finite vocabulary, and the dataset is a multiset of context–next-token pairs whose repetitions retain their multiplicity.Unless stated otherwise, the dataset is fixed and probabilities are over random representation initialization.Source: §2 · p. 2
- Independent Gaussian input and output codebooks represent context tokens and next-token labels, respectively.In the tied construction, the output codebook is set equal to the input codebook; independence matters for expectation calculations.Source: §2 · p. 2
- The random projection is normalized so the expected squared norm of a projected token code is 1/h times its original squared norm.The scaled projection is a Gaussian Johnson–Lindenstrauss map, with dimension governing simultaneous distance preservation.Source: §2 · p. 2
- The positional feature map records each token separately by position, so its inner product gives the positional Hamming kernel without joint features across positions.The feature map has dimension h n and concatenates one-hot token features for each position.Source: §2 · p. 3
3 PROBLEM FORMULATION
The problem is to predict a next token by summing positional Hamming similarities over stored contexts for each candidate label. This defines a count-weighted kernel vote and an equivalent linear classifier with unnormalized class prototypes.
3 PROBLEM FORMULATION
- For each candidate token, the classifier sums query-to-context positional Hamming similarity over training examples carrying that label, retaining repeated examples.The prediction is the candidate with the largest score; ties may be broken arbitrarily.Source: §3 · p. 3
- The same rule is a kernel vote or a linear classifier whose class prototype is the unnormalized sum of training features for that class.The feature-map inner product equals the positional Hamming kernel.Source: §3 · p. 3
- The prototypes retain occurrence counts; dividing by class size would instead yield an average-similarity classifier and a different prediction rule.Token–position–label count tables completely determine the ideal classifier.Source: §3 · p. 3
4 SINGLE-LAYER MEMO
Single-layer MeMo encodes contexts as position-preserving randomized features, stores context–label associations as outer products, and retrieves candidate scores by decoding against output codes. Under independent codebooks, the score is unbiased for the ideal classifier’s score; tied codes can introduce bias.
4 SINGLE-LAYER MEMO
- The randomized context map preserves position by placing each token’s projected code in a separate block, and its expected inner product equals the positional Hamming kernel.Its approximation error depends jointly on input-codebook coherence and projection distortion.Source: §4 · pp. 3–4
- MeMo stores each context–label association as an outer product of its randomized context key and output code, which can be added or subtracted to update memory.The memory has p d scalar parameters and is square when the projection dimension is d/h.Source: §4 · p. 4
- Retrieval decodes the output vector against candidate label codes; context similarity and label-code inner products form two distinct sketches of the ideal score.With independent input and output codebooks, the decoded score is an unbiased estimator of the ideal score.Source: §4 · p. 4
- Tying input and output codebooks makes the two inner products dependent, so repeated output tokens within contexts can produce bias terms.The independent-codebook expectation result therefore cannot be invoked directly for the tied construction.Source: §4 · p. 4
- Prediction recovery depends on the ideal classifier’s margin as well as the random sketch’s retrieval error.The analysis separates intrinsic ambiguity in the ideal classification problem from approximation error and cross-talk introduced by randomized representations.Source: §4 · pp. 4–5
5 ANALYSIS
The analysis separates MeMo’s randomized score error into context-sketch and output-code interference components. It combines bounds on these errors with the ideal classifier’s margin to give conditions for recovering its prediction.
5 ANALYSIS
- An error smaller than half the ideal score gap preserves the winner; a small gap reflects classifier ambiguity, while large score error reflects randomized-representation limits.The analysis bounds context sketching and output decoding separately before combining them.Source: §5 · p. 5
5.1 CONTEXT-SKETCH APPROXIMATION
- For square memory, a dimension on the order of h log(n/δ)/ε² suffices to bound context-sketch error by εMmax.The uniform bound scales linearly with Mmax; duplicated contexts can accumulate the same kernel error coherently, and the proof may be pessimistic when errors cancel.Source: §5.1 · p. 7
5.3 FULL PREDICTION GUARANTEE
- When the combined context and output error is below half the ideal margin, single-layer MeMo recovers the ideal prediction with probability at least 1−δ.The guarantee assumes a fixed dataset and query with a unique ideal winner.Source: §5.3 · p. 8
5.2 OUTPUT-CODE INTERFERENCE
- Output-code interference depends on the squared norm of the pre-decoding score vector, so repeated same-label evidence can accumulate coherently and increase collision energy.When k contexts with similarity ρ share a label, their aggregated score is kρ and the corresponding cross-talk variance scales as k²ρ²/d.Source: §5.2 · p. 7, §5.3 · p. 8
6 EXPERIMENTAL EVALUATION
The experiments test synthetic error and recovery trends, then evaluate single-layer MEMO’s fidelity, accuracy, memory, and throughput on a restricted WikiText-2 task. Results show a dimension-dependent fidelity trade-off and a favorable—but not uniformly superior—accuracy, memory, and throughput balance.
6.1 SYNTHETIC VALIDATION
- Synthetic results follow the predicted d^-1/2 context-sketch error decay in the well-resolved regime, while merging labels increases collision energy and typical output error.The merged h = 8 instance recovers more slowly despite the same ideal margin; the experiment tests agreement with the ideal classifier, not external ground-truth accuracy.Source: Figure 1 · p. 10, §6.1 · p. 10
6.2 REAL-DATA EVALUATION
- The WikiText-2 experiment is a controlled 64-class next-token task covering 44.79% of eligible test positions, not a full language-model benchmark.It uses fixed sampled positions with no context crossing line boundaries; all methods receive the same examples.Source: §6.2 · p. 11
- The sum prototype is the exact classifier, while the SVM and suffix model achieve higher top-1 accuracy by learning discriminative rules or preserving token conjunctions.The poor mean-prototype accuracy indicates that class frequency matters to the exact sum-prototype prediction on this task.Source: §6.2 · p. 11
- At h = 8, MEMO agreement with the exact classifier rises from 47.22% at d = 128 to 72.79% at d = 1024; top-1 accuracy reaches 21.50%, 0.80 points below the exact sum prototype.At d = 1024, the deployed two-stage MEMO state occupies 20.50 MiB versus 65.00 MiB for the exact count table; at d = 512 it uses 9.25 MiB for 20.18% accuracy and 63.46% agreement.Source: §6.2 · p. 11, Table 1 · p. 11, Figure 2 · p. 12
- Fused MEMO combines its two retrieval matrix products before inference, preserving the two-stage scores up to floating-point rounding while leaving output-code interference intact.The GPU measurements include score computation and label selection but exclude training, data transfers, and Python overhead.Source: §6.2 · p. 12
- At batch size 1024, fused MEMO with d = 256 processes 40.00 million queries per second versus 33.33 million for the exact sum prototype, using 4.12 MiB versus 65.00 MiB.Its mean top-1 accuracy is 18.76% versus 22.30%; the linear SVM has the highest predictive accuracy at 34.28%. The overall trade-off is not universal superiority.Source: Table 2 · p. 12, §6.2 · pp. 12–13