acceptodds
Under review as a conference paper at ICLR 2027

Latest Exact Match Attention

Abstract

We introduce latest exact match attention (LEMA), an attention variant for transformers where queries and keys are binarized and each query attends only to the latest exactly matching key. We prove that LEMA transformers with chain of thought can simulate word-RAMs, as was recently shown for the less restrictive rightmost hard attention. In contrast to prior hard attention variants, the restriction to exact matches enables an efficient converse direction: word-RAMs can simulate LEMA transformers at a cost per token independent of the context length. Together, these results yield a close correspondence between the two computational models in terms of both compute and memory. Beyond the theory, we propose a training method for LEMA transformers that handles their non-differentiable operations with a straight-through estimator for the binarization and a soft attention surrogate annealed towards LEMA. On a synthetic associative recall task, LEMA models trained this way use their growing state to store and recall a large number of associations, outperforming gated DeltaNet (GDN) with its fixed state size. As a first scaling test, we train LEMA language models with up to 834 million parameters. They match softmax transformers of around half their size in loss and, on repeated rare phrases and a needle-retrieval task, remain behind softmax transformers but recall across longer distances than GDN models of comparable size. Finally, we implement dictionary-based inference for LEMA transformers and show constant generation speed comparable to GDN despite their growing state, with the dictionaries residing in main memory rather than VRAM.

Primary area:
learning theory
Keywords:
attention, transformer, hard attention, expressivity, word-RAM, chain of thought, efficient inference

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 3 reviews, above 27% of the others.
Reviewer_DN9aOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

LEMA binarizes query and key vectors and retrieves the value at the latest exactly matching key, allowing dictionary-based lookup. On the theory side, LEMA uses a more restrictive construction than prior recency-based hard attention and shows simulations in both directions: word-RAMs can simulate LEMA transformers and LEMA transformers can simulate word-RAMs. On the empirical side, experiments with models of up to 834M parameters show positive results on the reported benchmarks and in inference performance. However, LEMA’s broader advantage is less convincing. More details are provided below.

Critical strengths
  • Extends the prior word-RAM connection for recency-based hard attention to the more restrictive LEMA rule and establishes simulations in both directions.
  • Shows competitive long-range recall against GDN on selected tasks with competitive compute.
  • Demonstrates strong length extrapolation on the synthetic associative-recall task.
Critical weaknesses
  • The word-RAM results do not explain how the choice of backward surrogate affects learning. The paper studies the effect of capping the backward sharpening parameter, but a small ablation across different surrogate derivatives, like sigmoid, would help establish whether the training result depends on the particular choice of backward pass function.
  • The comparisons omit several relevant attention baselines, including stick-breaking attention beyond the limited ablation, path attention (https://arxiv.org/pdf/2505.16381), which also reports targeted recall experiments, and other related improved mechanisms like GDN-2 (https://arxiv.org/pdf/2605.22791).
  • The empirical case relies heavily on selected recall tasks. The harder multi-key retrieval results in the appendix are less favorable to LEMA and deserve more discussion; standard downstream language-modeling benchmarks, like TinyBenchmark, would also help assess the quality cost of exact-match attention.
Questions for authors

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

Reviewer_QByAOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes an attention variant that binarizes key and queries and, given a binary query, retrieves the value corresponding to the most recent matching key. Strictly speaking, this can be interpreted as a constant-size state since there are at most 2dkey2^{d_{key}} values that have to be maintained at any point. They propose a differentiable training method for this based on stick breaking attention. They perform synthetic NIAH experiments where LEMA performs very well, and they perform language modeling experiments where LEMA significantly trails GDN/Transformer.

Critical strengths

The paper proposes a clear idea and is easy to follow.

Critical weaknesses

The language modeling results are very poor. A LEMA model performs worse on next token prediction than a transformer/gdn with half the parameter count and half the pretraining data (Figure 3 left). The better NIAH results compared to GDN (Figure 3 right) are most likely a result of much bigger state size, which is to be expected. It is also much less efficient than other linear models (Figure 4), and not more efficient (or lower state) than softmax attention at common context lengths like 2k (this is not entirely clear from the figure since x-axis shows super-long context only). It is also not well motivated why doing latest exact match attention would be good in practice (beyond the connection to word-RAMs). Synthetic associative recall depends mostly on state size, so LEMA performing well there (Figure 2) is not more than a sanity check. Overall, there is no evidence that LEMA (or the particular proposed method to train LEMA) is actually useful in practice. Meanwhile, very similar approaches like stick breaking attention [1] perform well in practice.

The theoretical part takes a minor part in the main paper, consists of two theorems, where Theorem 1 is very similar to [2] and Theorem 2 is straight forward. This is not a weakness, but also not significant enough to be a main contribution on its own.

[1] Shawn Tan, Songlin Yang, Aaron Courville, Rameswar Panda, and Yikang Shen. Scaling Stick-Breaking Attention: An Efficient Implementation and In-depth Study

[2] Yanhong Li, Anej Svete, Ashish Sabharwal, and William Merrill. Efficiently representing algorithms with chain-of-thought transformers

Questions for authors

No questions. I think the experimental results are significantly too poor to recommend acceptance.

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

The paper proposes a new attention mechanism where query and keys are converted into binary format and each head retrieves the last token which has the same key as the query. This means each head at most selects a single token (or none if none of the previous keys match the query). Theoretically, it is proven that this mechanism has the same representation power as word-rams. For training, straight through estimators are used: tanh for converting to binary and stick-breaking attention for the single token selection. Experimental results show that loss lags behind standard softmax attention and Gated DeltaNet. The ability to solve tasks like needle in a haystack is improved over Gated DeltaNet but still is worse than softmax attention.

Critical strengths

This paper builds on the intuition that small gates in stick-breaking attention cause problems and proposes a training mechanism to avoid these issues by hard-selecting a token. Various ablations and analysis are done to provide additional insights on how LEMA works.

Critical weaknesses

The performance of LEMA in terms of perplexity remains significantly behind GDN and standard softmax attention. While there are benefits in needle in a haystack tasks, other tasks (e.g. reasoning, knowledge, etc.) might be significantly suffering. Intuitively, LEMA has less representation power than softmax attention since it can't mix tokens and can only retrieve them. There is no solution or alternative investigated to address this limitation.

The training mechanism involves manually changing the backward graph in several places. This is concerning as it can make the training unstable. It is also not very clear how much the model is sensitive to the exact chosen constants. For example, for hardening, why do we need to use 2 for backward instead of 10? Would 5 also work? How about 1?

Generally I also find the paper a bit hard to follow. For example the discussion around word-rams is not directly relevant to the rest of experiments and can be moved to Appendix. Also, some terms like "hardening" (which refers to alpha increasing towards end of training) are not properly introduced. As another example, reading the below sentence made me think stick breaking attention is only used during backward pass but it seems it is also used during the forward pass throughout the training.

Just as the sign function is approximated by tanh as a differentiable surrogate, we approximate the latest exact match operation with a smooth surrogate.

Questions for authors
  1. In the paper, LEMA does not use RoPE. This might be necessary given the binarization. However, I wonder if some form of position encoding was tried or not?

  2. Given the manual changes in the backward graph, did you observe instabilities such as loss spikes during training?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.