acceptodds
Under review as a conference paper at ICLR 2027

Single-Layer MeMo as a Randomized Hamming-Kernel Classifier

Abstract

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 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.

Primary area:
learning theory
Keywords:
Associative memory, Kernel methods, Positional Hamming kernel, Randomized sketching, Multiclass classification

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_DGKhOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper provides a theoretical analysis of single-layer MeMo, an associative-memory-based language model architecture. The authors show that its ideal retrieval rule corresponds to a positional Hamming-kernel classifier and derive bounds on the approximation errors introduced by randomized context representations and output decoding. These results lead to a margin-based prediction recovery guarantee. The paper also includes synthetic experiments to validate the theoretical trends and experiments on a restricted WikiText-2 task to evaluate predictive accuracy, memory usage, and inference throughput.

Critical strengths
  1. The paper provides a clear and systematic theoretical characterization of single-layer MeMo, with a useful decomposition of its approximation errors.

  2. The experiments are well aligned with the theoretical analysis and provide empirical support for the predicted trends.

Critical weaknesses
  1. Unclear significance of the theoretical contributions. Although the analysis is clearly presented, I find it difficult to identify the key new insights it provides beyond the expected behavior of randomized representations. In particular, the paper does not sufficiently explain what we learn about MeMo from these results that was not previously understood.

  2. Limited practical implications. The theoretical results are not connected to concrete improvements or design decisions for MeMo. For example, it remains unclear whether the bounds can meaningfully guide the choice of representation dimensions, memory capacity, or coding strategies. This makes it difficult to assess the broader significance of the analysis.

Questions for authors
  1. What are the main new insights provided by the theoretical analysis? Beyond characterizing approximation errors, does the analysis reveal any non-obvious properties or limitations of MeMo? In particular, what would we misunderstand or fail to predict about MeMo without these theoretical results?

  2. Can the theoretical results provide concrete guidance for designing or using MeMo? For example, can they help determine appropriate representation dimensions, memory capacity, or coding strategies? A concrete demonstration of how the analysis informs practical decisions would substantially strengthen the paper.

  3. How informative are the theoretical bounds in practice? Can the authors evaluate their tightness or show how frequently the prediction recovery conditions are satisfied on real data? This would help clarify their practical relevance.

My primary concern is the significance and implications of the theoretical analysis, rather than any specific technical error. I would be willing to reconsider my rating if the authors can provide a convincing explanation of the novel insights and practical value of their theoretical results.

3 comments

Thank you for asking what the theory changes in our understanding and use of MeMo. We have made its architectural consequences explicit and completed experiments connecting them to coding choices, dimension selection and recovery diagnostics.

Q1. Information retained and irrecoverable limitations. Beyond the ideal Hamming interpretation, the finite memory itself satisfies Cr=(WU)NrZ⊤,C_r=(WU)N_rZ^\top, where NrN_r is the token-by-label count matrix at position rr. This follows directly by grouping the outer products in the memory definition. Therefore, two datasets with identical token-position-label counts produce exactly the same memory for every fixed initialization and dimension. For example, the complete two-bit XOR dataset and its label-complement have identical count tables and cannot be distinguished.

This identifies a limitation that increasing dimension cannot fix: joint positional information discarded by these statistics cannot be recovered by a more accurate sketch. The identity holds even with tied codes; the probabilistic recovery theorem remains untied. It provides a concrete distinction between changing the representation's features and increasing its dimension. We present this as an architectural consequence, using standard mathematical tools, without claiming a new general limitation of Hamming kernels.

The analysis also identifies why memory size alone is insufficient to describe fidelity. Duplicating every training example multiplies scores, margins and errors equally, leaving predictions unchanged. Changing the distribution of evidence across labels can instead change interference relative to the margin. In our synthetic control, merging labels preserves Δ=16\Delta=16 while increasing ideal score energy from 37,888 to 150,784. At d=1024d=1024, observed recovery falls from 60.625% to 40.0% over 160 initializations. Thus, margin alone also misses a relevant mechanism; repeated labels do not universally worsen recovery because they can change the margin too.

Q2. Concrete design decisions. The decomposition separates context-sketch error from output-code interference. It motivates storing the same compressed class keys directly, A=∑jϕ(sj)eyj⊤A=\sum_j\phi(s_j)e_{y_j}^{\top}, and predicting with G(q)=A⊤ϕ(q)G(q)=A^\top\phi(q). In the synthetic setting h=8,d=1024,Δ=16h=8,d=1024,\Delta=16, direct scores recover the ideal winner in 160/160 initializations, versus 97/160 for full MeMo. Removing the decoding stage resolves all observed disagreements in this controlled setting.

We also evaluated five paired seeds on restricted WikiText-2: 100,000 training, 2,000 validation and 5,000 test examples, with 64 candidate labels. Agreement excludes ideal ties. At h=8,d=1024h=8,d=1024, direct scores achieve 74.85% ± 0.83% agreement, versus 72.79% ± 4.55% for MeMo (mean ± sample SD). Token accuracy is 21.30% versus 21.50%, so fidelity does not imply improved prediction accuracy. Both direct scores and fused MeMo use 16.499 MiB of deployed numeric state here.

For dimension selection, we extended the h=8h=8 grid through d=4096d=4096 and selected the smallest dimension reaching 80% mean agreement on validation data only. Both methods select d=4096d=4096; held-out agreement is 83.25% ± 0.94% for MeMo and 84.19% ± 0.64% for direct scores. Neither reaches 90% on validation. This is an empirical selection informed by the distinction between fidelity and accuracy, not a theorem-certified dimension. The selected state is about 66 MiB, whereas compact exact counts need 1.986 MiB in this dataset, so increased fidelity does not establish a storage advantage.

Q3. How informative are the bounds? At h=8,d=1024h=8,d=1024, measured MeMo recovery is 72.79%, but the sufficient condition ∥S~−S∥∞<Δ/2\|\widetilde S-S\|_\infty<\Delta/2 holds on only 6.94% of unique-winner queries. Agreement nevertheless rises from 44.31% in the lowest ideal-margin quintile to 98.56% in the highest, supporting the margin's explanatory role.

The explicit output bound at δ=0.05\delta=0.05 covers the measured output error on every tested query/seed; its median bound/error ratio, averaged over seeds, is 4.24. This empirical coverage is descriptive because queries share codebooks. Combining that bound with measured context error satisfies the recovery inequality on only 0.008% of unique-winner queries. This hybrid diagnostic is not the full certificate: the published context bound has unspecified constants and was not numerically evaluated.

The evidence therefore supports a diagnostic role for the theory and demonstrates the limits of its current certification strength. We will clarify these distinctions and include the new ablations and dimension-selection results, without extending the claims to multilayer recovery or general language-model improvements.

Thank you for the thoughtful and detailed rebuttal. I appreciate the additional analyses and experiments, particularly the discussion of the architectural limitations and the direct-scoring ablation. These additions help clarify the theoretical findings and their implications.

However, I remain somewhat unconvinced about the overall significance and practical value of the contributions. While the new results provide further characterization of MeMo, I do not think they yet demonstrate sufficiently meaningful insights or practical benefits beyond analyzing the properties of the existing architecture. In particular, the direct-scoring variant does not show a clear improvement in predictive accuracy, and the theoretical recovery conditions remain quite conservative in practice.

I appreciate the authors' efforts to address my concerns, but the rebuttal does not substantially change my overall assessment. I will therefore maintain my original rating.

Thank you for your careful follow-up and for acknowledging the additional analyses. We understand your remaining concerns about the significance of the contribution. We would briefly clarify that the direct-scoring ablation serves to isolate the contribution of output coding to approximation error (improved predictive accuracy was not its intended purpose). We also agree that the recovery conditions remain conservative. The theoretical insight we aim to establish is the distinction between structural information loss, which increasing dimension cannot resolve, and approximation errors that dimension and coding choices can address. We appreciate our constructive discussion, which has helped us articulate both the contribution and its limitations more precisely.

Reviewer_BZWUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper interprets single-layer MeMo as a randomized Hamming-kernel classifier. It analyzes errors from context compression and output encoding, and gives conditions under which MeMo preserves the ideal classifier’s prediction. Synthetic experiments support the predicted trends, while a restricted WikiText-2 task illustrates trade-offs between accuracy, memory, and inference speed.

Critical strengths
  1. The equivalence between single-layer MeMo’s ideal retrieval rule, an unnormalized Hamming-kernel vote, and token-position-label count tables makes the model substantially easier to interpret. It exposes both the role of class frequency and the absence of explicit cross-position interactions. This is a useful conceptual contribution even independently of predictive improvements.
  2. The analysis separates context sketching from output decoding and captures coherent repeated-label interference through the class-score energy. It does not require independence between stored examples. The synthetic experiments are well aligned with this decomposition: the decoder is evaluated with exact ideal scores, and the label-merging experiment preserves the ideal margin while changing interference. The real-data evaluation also carefully separates fidelity, predictive quality, and computational cost.
Critical weaknesses
  1. The paper does not compare MeMo with a model that compresses the inputs but stores class scores directly. Without this comparison, the practical benefit of random output codes remains unclear.
  2. The experiments support the predicted trends, but do not show whether the bounds can guide dimension selection or certify successful recovery at the tested settings.Suggest discussing the consistency and gap between theory and experiment.
Questions for authors
  1. How does MeMo compare with a model that uses the same compressed input representations but stores class scores directly, without random output codes, in terms of accuracy, memory, and speed?

  2. Do the theoretical bounds certify correct recovery at the dimensions used in your experiments, or do they mainly explain qualitative trends?

  3. How much do the results change when the input and output share the same codebook?

2 comments

Thank you for identifying the missing input-only comparison and the need to quantify the gap between the recovery guarantee and observed behavior. We have completed the requested ablation, bound diagnostics, and shared-codebook comparison on restricted WikiText-2: 100,000 training, 2,000 validation and 5,000 test examples, with 64 candidate labels.

Q1. Compressed inputs with direct class scores. We store A=∑jϕ(sj)eyj⊤,G(q)=A⊤ϕ(q),A=\sum_j\phi(s_j)e_{y_j}^{\top},\qquad G(q)=A^{\top}\phi(q), using exactly the same input codebook, projection, training examples, and accumulated class keys as MeMo. This removes output-code interference. We evaluated all 12 original (h,d)(h,d) settings with five paired seeds. Predictive results below are mean ± sample SD across these seeds; agreement is measured only on queries with a unique ideal winner.

At h=8,d=1024h=8,d=1024:

MethodTop-1 accuracy (%)Agreement (%)Inference state (MiB)
Direct scores GG21.296 +- 0.64674.855 +- 0.83516.499
MeMo, fused21.504 +- 0.75572.789 +- 4.55416.499

Direct scores have higher mean agreement in all 12 settings, although not for every seed or in token accuracy. At h=8,d=128h=8,d=128, they also improve accuracy from 16.35% to 17.93% and agreement from 47.22% to 53.97%. Thus, removing one error source does not guarantee monotonic improvement in predictions: errors can cancel, and fidelity is distinct from token accuracy.

The direct matrix AA and fused MeMo matrix CZCZ both have shape d×Kd\times K; both implementations also retain the same projected input codes. Consequently, output coding provides no inference-storage advantage over direct scores in this fixed 64-class setting. Literal two-stage MeMo uses 20.499 MiB at d=1024d=1024. State sizes include numeric arrays and metadata, excluding common token dictionaries, interpreter overhead and temporary buffers.

Matched single-thread PyTorch CPU timing on an Intel Core i7-13700H, with h=8,d=1024h=8,d=1024 and batch size 1024, gives 0.783 million queries/s for direct scores, 0.786 for fused MeMo, and 0.0652 for two-stage MeMo. Timing uses paired seed-17 models, rotating resident query batches, and the median of three trial medians, each with 20 warm-up and 100 measured calls. Gathering, scoring, argmax, and Python overhead are included. Direct and fused paths have identical operation shapes; their small timing difference is not an algorithmic advantage. These are CPU measurements, not new GPU results.

Q2. Certification and dimension selection. We distinguish three checks. At h=8,d=1024h=8,d=1024, observed MeMo agreement is 72.79%, but the deterministic sufficient condition ∥S~−S∥∞<Δ/2\|\widetilde S-S\|_\infty<\Delta/2, using the measured error, holds on only 6.94% of unique-winner queries. This demonstrates substantial conservativeness even before substituting a concentration bound.

The explicit Theorem 5 output bound, evaluated with δ=0.05\delta=0.05 and 64 candidates, covers the observed output error on every tested query/seed; the mean across seeds of the median bound/error ratio is 4.24 here. This coverage is descriptive: queries share codebooks. The hybrid diagnostic Ectx+Bout<Δ/2E_{\rm ctx}+B_{\rm out}<\Delta/2, using measured context error, holds on only 0.008% of unique-winner queries. It is not a full probabilistic certificate. The published full bound contains unspecified context-bound constants, so we cannot report its numerical certification rate or use it as a calibrated dimension selector.

As an empirical design check, extending h=8h=8 to d=2048,4096d=2048,4096, validation-only selection first reaches 80% mean agreement at d=4096d=4096 for both methods. Held-out agreement is 83.25% ± 0.94% for MeMo and 84.19% ± 0.64% for direct scores. Neither reaches the 90% validation target. These are empirical selections, not theorem-certified dimensions.

Q3. Shared input/output codebook. We paired tied and untied models with identical input codes and projections, selecting each output code from the corresponding input-token column. At h=8,d=128h=8,d=128, tied agreement is 53.94% ± 6.11%, versus 47.22% ± 6.07% untied. At d=512d=512, it is 63.13% ± 6.26% versus 63.46% ± 1.89%; at d=1024d=1024, 72.98% ± 3.46% versus 72.79% ± 4.55%. Tied top-1 accuracy at the latter dimension is 21.37% ± 0.43%. Effects are dimension-dependent; these experiments do not extend the independence-based recovery theorem to tied codes.

Thank you for your detailed response, but considering that the significance of the Q1 experiment is not significant and our concerns still seem to exist, I am considering keeping my score

Reviewer_tfFzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper interprets single-layer MeMo as a randomized approximation to a positional Hamming-kernel classifier. Under independent input and output codebooks, it decomposes the approximation error into context-sketch error and output-code interference, and derives a margin-based guarantee for recovering the ideal classifier’s prediction. Controlled synthetic experiments examine the predicted scaling behavior, while a restricted 64-class WikiText-2 task evaluates prediction agreement, accuracy, memory usage, and throughput.

Critical strengths
  1. The paper provides a clear interpretation of single-layer MeMo. The equivalence to token–position–label count tables makes both the prediction rule and its representational limitations explicit.

  2. Separating context approximation from output decoding is useful. In particular, the analysis of how repeated labels accumulate coherently, with interference governed by the squared class-score norm, is an informative aspect of the paper.

  3. The synthetic experiments isolate the two error sources, and the empirical presentation carefully distinguishes agreement with the ideal classifier from accuracy against the observed token. The authors also acknowledge the restricted task and the limitations of the efficiency results.

Critical weaknesses
  1. The significance of the theoretical advance needs stronger justification. The kernel interpretation follows relatively directly from expanding the encoding, and the recovery argument combines concentration bounds with a standard margin condition. These observations do not invalidate the contribution, but they leave me uncertain about its depth beyond a useful characterization of this particular architecture. The related-work discussion distinguishes token-based context encoding from independent whole-input codes; however, it would help to identify more precisely which resulting conclusions are new and what they reveal beyond existing associative-memory and random-projection analyses.

  2. The experiments establish qualitative trends more clearly than the predictive value of the bounds. Section 5.1 acknowledges that the context bound is pessimistic. Figure 1 supports the expected dimension-dependent decay and the effect of label merging, but does not establish how informative the combined recovery condition is at the tested dimensions. In particular, the synthetic construction keeps the ideal margin fixed. A focused examination of recovery as the margin varies, or an analysis relating observed failures to the error-to-margin ratio, would more directly assess the central recovery argument. I do not expect a sufficient condition to be necessary or tight, but the practical gap deserves characterization.

  3. The real-data results provide limited additional evidence for the contribution’s broader value. At h=8,d=1024h=8,d=1024, agreement with the ideal classifier is 72.79%, despite the relatively small difference in predictive accuracy. This makes it important to understand whether disagreements concentrate on small-margin queries, as the analysis would suggest. The memory comparison is also against a dense exact count table; without a suitable sparse or compressed exact baseline, it remains unclear how much of the observed advantage is specific to the randomized representation. The authors appropriately qualify these results, but they offer limited support beyond the controlled theoretical validation.

Questions for authors
  1. What is the strongest new conclusion relative to prior associative-memory theory? In particular, which part of the repeated-label or two-stage interference analysis cannot be obtained by a straightforward specialization of existing results?

  2. How informative is the recovery condition in the reported experiments? Can the authors characterize its conservativeness, or use the existing queries to show how prediction agreement varies with the ideal margin and observed approximation error?

  3. How sensitive is the reported memory advantage to the representation of the exact count-table baseline? A discussion of its sparsity and feasible storage alternatives would help contextualize Table 2.

My initial recommendation is Weak Reject. I appreciate the clarity of the formulation and the careful separation of approximation fidelity from predictive accuracy. My main reservations concern the significance of the theoretical advance and the limited evidence that the bounds provide useful predictions beyond qualitative scaling trends. Large-scale language-model experiments are not necessary for the paper’s stated theoretical objective; a more precise account of the new insight and a closer connection between the theory and the existing experiments would be more valuable. I intend to engage actively and constructively with the authors during the discussion period. This recommendation is provisional, and I am open to revising my score, including toward acceptance, if the response clarifies the theoretical advance and strengthens the evidence for its explanatory value.

2 comments

Thank you for the specific suggestions. We have completed additional margin, error, and exact-storage analyses and clarified which conclusions are specific to MeMo.

1. Theoretical contribution and prior work. We use standard concentration and margin arguments. The original MeMo paper, Sec 3.1 already describes partial matching. Cabannes et al., Theorem 1 already allow repeated labels, but assume independent embeddings for distinct inputs. MeMo instead shares token codes and a projection across contexts, inducing structured Hamming similarities; that theorem does not apply directly.

Conditional on the intermediate scores GG, output decoding S~=Z⊤ZG\widetilde S=Z^\top ZG is a standard random-code calculation. Our contribution connects this calculation to the actual context representation, its count-based target, and prediction recovery.

A concrete consequence of Eqs. (3)-(4) is that each memory block satisfies Cr=(WU)NrZ⊤C_r=(WU)N_rZ^\top, with NrN_r the token-by-label count matrix at position rr. Thus, identical token-position-label counts imply identical memories for every fixed initialization and dimension, including tied codes. The complete two-bit XOR dataset and its label-complement are indistinguishable. Increasing dimension cannot recover the joint positional information discarded by this architecture. This structural limitation and the finite-dimensional recovery analysis distinguish representational failure from sketching error; we do not claim a new general phenomenon of repeated-label interference.

2. Margin dependence and conservativeness. We varied the synthetic ideal margin over {2,4,8,16,24,32}\{2,4,8,16,24,32\} and dimension over {128,256,512,1024,2048,4096}\{128,256,512,1024,2048,4096\}, using 160 random initializations per setting. At d=1024d=1024, recovery for margins 8, 16, 24 and 32 is 16.25%, 60.625%, 91.875% and 99.375%. Sample count, label balance and context length are fixed; score energy varies by 6.66% across the full margin sweep, rather than being exactly constant.

On WikiText-2, we used 100,000 training, 2,000 validation and 5,000 test examples, 64 candidate labels, and five paired seeds. At h=8,d=1024h=8,d=1024, agreement with the exact classifier increases across ideal-margin quintiles from 44.31%, 57.35%, 72.83%, 90.71% to 98.56%. Approximately 72% of observed disagreements lie in the two lowest quintiles. Agreement excludes ideal ties.

The deterministic condition ∥S~−S∥∞<Δ/2\|\widetilde S-S\|_\infty<\Delta/2, evaluated using measured errors, holds on only 6.94% of unique-winner queries, versus 72.79% agreement. In the synthetic setting Δ=16,d=4096\Delta=16,d=4096, recovery is 98.75%, while this condition holds in only 0.625% of trials. Conservativeness therefore arises even before replacing errors with concentration bounds.

For the explicit output bound at δ=0.05\delta=0.05, the real-data mean across seeds of the median bound/error ratio is 4.24. The hybrid check using measured context error plus this bound holds on only 0.008% of unique-winner queries. This is not the full probabilistic certificate: the context bound has unspecified universal constants, so its numerical certification rate is not established.

3. Sparse exact storage and scaling. Your concern changes the memory interpretation. At h=8h=8, the exact table has 339,094 nonzeros (1.99% density). Dense int32 storage uses 65.00 MiB, standard CSR 3.60 MiB, and compact CSR 1.986 MiB, preserving every score on all 5,000 test queries, including ties. Compact CSR uses uint16 counts, uint8 class indices and uint32 row pointers. Fused MeMo uses 2.062 MiB at d=128d=128 and 16.499 MiB at d=1024d=1024. These figures include deployed numeric state and metadata, excluding shared token dictionaries, interpreter overhead and temporary buffers.

We also enlarged training to all 793,614 eligible examples, keeping vocabulary, classes and test queries fixed. Compact exact storage rises to 5.334 MiB; fused MeMo at d=256d=256 remains 4.125 MiB, but achieves only 55.44% mean agreement with that training set's exact classifier. Direct scores have the same deployed state size as fused MeMo. Thus, a storage crossover can occur, but it is a memory-fidelity trade-off shared with the input-only baseline, not a universal advantage of output coding. We will revise the efficiency claim and include the sparse exact baseline.

I will maintain my borderline score.

Reviewer_fVrwOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper provides theoretical insight into a memory-based method called MeMo. It starts by defining an ideal position-wise context-matching classifier based on the positional Hamming kernel. Then it introduces MeMo’s mechanism, which uses independent random input and output codebooks and a random projection of the codes. Finally, it bounds the context-sketch error and output-code interference and provides controlled synthetic results and results on a restricted next-token task.

Critical strengths
  • The interpretation of single-layer MeMo as a randomized approximation to a Hamming-kernel classifier is clear.
  • The separation of context-sketch error and output-code interference is clean and provides a guarantee for recovering the ideal classifier’s output under untied sketching.
  • Controlled experiments qualitatively align with the error-bound analysis.
Critical weaknesses
  • The theory is limited to a single-layer model with untied sketching. The authors note that their analysis does not directly extend to tied sketching. Further analysis of tied sketching and multi-layer MeMo would be valuable.
  • While the work gives good theoretical insight into MeMo’s associative-memory mechanism, it does not connect this insight to other memory mechanisms, such as SSMs, dictionary-based methods, or sliding-window attention. The experiments primarily validate the theory, however, using the insight to improve the memory mechanism for downstream performance would make a stronger empirical case.

Remark: Line 213 contains a typo. It should be tilde S.

Questions for authors

No specific question apart from the concerns mentioned in the weaknesses.

4 comments

Thank you for recognizing the Hamming-kernel interpretation and the separation of context and output errors. We agree that the relationship to other memories, the implications for design, and the scope of the untied analysis need clearer treatment. Our contribution concerns the information retained by single-layer retrieval and the conditions under which its randomized implementation preserves the corresponding classifier.

The structural characterization extends beyond the probabilistic assumptions. Let NrN_r be the token-by-label count matrix at position rr. The corresponding memory block satisfies exactly Cr=(WU)NrZ⊤.C_r=(WU)N_rZ^\top. Consequently, datasets with identical token–position–label counts produce identical memories for every fixed initialization and dimension. For example, the complete two-bit XOR dataset and its label-complement have identical count tables. Increasing dimension cannot restore the joint positional information discarded by this representation. This identity also holds with tied codes. It distinguishes a limitation requiring different features or storage from approximation errors that larger representations can reduce. It does not establish that a particular multilayer extension resolves that limitation.

The probabilistic guarantees remain restricted to untied codes: sharing input and output embeddings introduces dependencies that invalidate the conditioning used in the decoding proof. This matters because the original MeMo construction, Section 3.1, shares embeddings. We have therefore added a paired empirical comparison, without treating it as an extension of the theorem. The restricted WikiText-2 task uses 100,000 training, 2,000 validation and 5,000 test examples, 64 output classes, and five codebook seeds. Methods share input sketches and examples; here h=8h=8 and dh=d/hd_h=d/h. “Agreement” means matching the exact Hamming classifier on the 4,987 test queries with a unique ideal winner; accuracy refers to the observed next token.

At d=128d=128, tied agreement is 53.94% +- 6.11%, versus 47.22% +- 6.07% untied; at d=1024d=1024, it is 72.98% +- 3.46%, versus 72.79% +- 4.55% (mean +- sample SD over seeds). At the latter dimension, token accuracy is 21.372% tied and 21.504% untied. These results demonstrate dimension-dependent empirical sensitivity, not a universal benefit or a theoretical guarantee for tied MeMo. Multilayer recovery remains outside the present analysis.

The count characterization also provides precise connections to other memory mechanisms. A dictionary storing counts for entire context–label pairs retains joint configurations and can distinguish the XOR datasets above; MeMo's positional aggregation cannot. The outer-product update and bilinear readout correspond algebraically to the numerator of linear attention (Katharopoulos et al. 2020). This correspondence does not identify their features, normalization, or learning procedures. Our additive limitation follows from MeMo's particular concatenated context map. Similarly, a sliding window restricts accessible positions without necessarily discarding their joint information. Comparing SSMs requires specifying their state updates and readouts; our results establish neither equivalence nor an expressivity ordering across these families.

The decomposition motivates a concrete design ablation: retain the same input sketch but store class scores directly, A=∑jϕ(sj)eyj⊤A=\sum_j\phi(s_j)e_{y_j}^{\top}, predicting from G(q)=A⊤ϕ(q)G(q)=A^\top\phi(q). This removes output-code interference. In the same WikiText-2 setup, at d=128d=128, mean agreement increases from 47.22% to 53.97% and token accuracy from 16.352% to 17.928%. At d=1024d=1024, agreement increases from 72.79% to 74.85%, while accuracy changes from 21.504% to 21.296%. Thus, improved fidelity is not automatically improved downstream prediction. Direct scores and fused MeMo both store a d×64d\times64 final matrix here, with identical deployed numeric state sizes. This controlled result supports evaluating whether output coding is useful in a given regime; it does not establish broader language-model gains.

We will clarify these connections and the scope of each claim in the manuscript, keeping the structural conclusions, untied guarantees, and empirical observations explicitly separate.

Thank you for the response. I appreciate the tied vs untied empirical study and the direct-score ablation. However, the concern about limited scope of MeMo stays. While the theory appears accurate and the empirical evidence support it, the scale is small and results are limited to draw any conclusion for practical classification tasks and broader benefits. This is why I asked about multi-layer MeMo, using the insight to improve the memory mechanism, and comparisons with other memory-based mechanisms. I will therefore maintain a weak reject.

Thank you for considering our response and for your constructive feedback. Our intended contribution is a first theoretical step toward understanding MeMo, providing a foundation for studying the more complex and general mult-layers variant. Demonstrating immediate benefits on broader practical tasks was somewhat beyond the scope of this study, and we appreciate your suggestions for future work. We also noticed a small discrepancy: your initial rating was clear reject, whereas your latest message refers to weak reject. We simply wanted to flag this for clarity. Thank you again for the time and attention devoted to our work.

Hello, thank you for pointing out the discrepancy. I raise the rating to weak reject.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.