- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper examines what is lost when the query, key, and value projections in self-attention are tied. Its central argument is that the answer differs depending on whether we consider a complete Transformer or an individual attention head. At the model level, the authors show that unmasked Transformers with positional embeddings remain universal approximators even when all three projections are tied, adapting the contextual-mapping construction of Kajitsuka and Sato (2023). At the head level, the two tying schemes impose different constraints. With , the logits form a Gram matrix, which prevents an unmasked head from approximating a cyclic shift arbitrarily well, regardless of head dimension. A causal mask restores the ability to approximate any causal attention pattern, but previous-token routing requires feature norms of at least linear order in sequence length, compared with an untied construction achieving . With , attention-pattern realizability is preserved, but exact reproduction of an untied head requires a dimension equal to the joint span of its effective key and value subspaces. The authors illustrate these results through controlled synthetic experiments. They also probe BERT and LLaMA-2 for the relevant attention patterns and report numerical-rank estimates intended to connect the subspace analysis to pretrained models.
Critical strengths
-
Theorem 4.1 gives a precise and interpretable account of when tying keys and values incurs no dimension penalty and when it doubles the required head dimension.
-
For causal attention, the paper shows that making a pattern realizable does not make it inexpensive to represent. The mask supplies directionality while previous-token routing still requires feature norms of at least linear order in sequence length regardless of head dimension. This is a useful qualification of the idea that either universality or causal masking resolves the expressivity question.
Critical weaknesses
-
My first concern is the relationship to prior constructions. Kajitsuka and Sato construct the query, key, and value projections using a common input direction, and their parameter choices appear to permit all three projections to be identical. Likhosherstov et al. (2021) already study sparse-pattern approximation with fixed projection matrices using random projections. The paper should explain precisely which additional arguments and guarantees distinguish its results from these earlier constructions.
-
The analysis also needs a clearer account of which structural assumptions cause each limitation. Symmetry and positive semidefiniteness play potentially different roles in the cyclic-shift obstruction, while the proof of the causal norm bound compares each token’s score for its predecessor with its score for itself. This suggests that the diagonal and the length of the routing chain are important to the result. It seems unclear how much of the separation remains when self-attention along the diagonal is excluded, as in the shared- attention design used by Reformer, or when the target is a shorter routing chain or an attention-sink pattern.
-
The presentation of the paper has some issues. Many citations appear as plain text without links to the corresponding references. The same issue occurs with references to sections, theorems, and figures. Mathematical notation is also formatted inconsistently; for example, plain-text Q and K are used alongside and . These issues make it hard to navigate between parts.
Reference:
-
Kajitsuka et al. Are transformers with one layer self-attention using low-rank weight matrices universal approximators? ICLR 2024.
-
Likhosherstov et al. On the expressive power of self-attention matrices. 2021.
Questions for authors
Please see Critical Weaknesses.
7 comments
Reference
Reference
[1] Kajitsuka, et al. Are transformers with one layer self-attention using low-rank weight matrices universal approximators?
[2] He, et al. Approximation error upper and lower bounds for Hölder class with transformers.
[3] Bhojanapalli, et al. Low-rank bottleneck in multi-head attention models.
[4] Likhosherstov, et al. On the expressive power of self-attention matrices.
[5] Sanford, et al. Representational strengths and limitations of transformers.
Rebuttal by Authors
W2: The analysis also needs a clearer account of which structural assumptions cause each limitation. Symmetry and positive semidefiniteness play potentially different roles in the cyclic-shift obstruction, while the proof of the causal norm bound compares each token’s score for its predecessor with its score for itself …….
We thank the reviewer for this highly constructive comment, which has prompted us to think more deeply about these questions and from which we have learned a great deal. We have added several theoretical results to the updated PDF, highlighted in blue. This part is core of our rebuttal.
-
Once we let , the input to the Softmax function is a symmetric and positive semi-definite matrix of the form . We clarify here that in Proposition 3.1, both symmetry and semidefiniteness contribute to the tight lower bound of 1. Symmetry alone yields only a lower bound of within our framework. We refer the reviewer to Proposition F.1 for a detailed proof.
-
Once we include the causal mask into consideration, the symmetry-induced limitation no longer applies, and Theorem 3.2 shows that self-attention with tied projections can also approximate arbitrary causal attention patterns. This means that positive semidefiniteness alone does not prevent realization with a causal mask. However, it may introduce other difficulties, such as requiring larger parameter norms to approximate certain attention patterns. These norm constraints arise because each token has identical query and key vectors. In standard attention, we can adjust the norms and directions of queries and keys independently to realize complex operations. With tied QK, however, each token’s query and key have the same direction, and its own self-attention score creates competition for other tokens. For another token to attract more attention than the token itself, its key must have a sufficiently large norm, since . This is precisely the intuition behind the proof of Proposition 3.2. The limitation becomes more severe along a long chain, as the required increases in norm accumulate, leading to a norm requirement that grows linearly with sequence length.
-
What happens if we mask out the diagonal attention weights by modifying the causal mask? Intuitively, this removes the mechanism on which Proposition 3.2 relies. Indeed, we can readily construct self-attention with tied projections that approximates the previous-token pattern. The detailed construction is presented in Proposition F.2. However, this does not mean that the limitations of tied QK disappear. We have added Proposition F.3 to the updated PDF to investigate these limitations further and show that a norm separation still exists. This construction is more involved than that in Proposition 3.2: we need to construct a pattern that exposes the restrictions of tied projections even without competition from each token’s self-attention score.
-
The reviewer also asks whether a norm separation can arise for a target pattern with shorter routing chains. After careful consideration, we think the answer depends on the type of norm separation we seek and what we mean by a long dependency chain. If we regard approximating a target pattern as a task, two relevant factors governing its complexity are the approximation error and the sequence length . The required norm can therefore be viewed as a function of both and , and may increase as or . It is important to note that, in our asymptotic comparison, we treat as a constant, since the dependence of the required norm on through softmax is relatively mild. Our comparison between Theorem 3.2 and Proposition 3.2 is asymptotic in , but this does not mean that norm separation cannot occur at finite . In fact, a norm separation can be observed at a suitably chosen fixed , even when is small. Although the proof of Proposition 3.2 does use a long chain, this is just one way to obtain a clear asymptotic norm separation as grows. Norm separation at fixed can arise in other patterns as well. In particular, attention-sink patterns can also exhibit norm separation. The intuition is that, for the first token to attract most of the attention, untied attention can adjust the directions so that the sink’s key aligns with the other tokens’ queries while keeping the norms small, consistent with observations in real-world LLMs [6]. Tied attention cannot adjust the query and key directions independently and requires larger norms to concentrate attention on the sink token. In Proposition F.4, even if = 3, we show that the norm upper bound of untied attention is , while the lower bound of tied attention is .
Rebuttal by Authors
We sincerely thank the reviewer for the time and care they have devoted to reviewing our work. Their comments have given us much to think about and have helped us improve both the paper and our understanding of the problem. We address the concerns below.
We thank the reviewer for pointing this out. An important aspect of theoretical work is to clarify its relationship to prior literature and clearly identify its advances. In Appendix D, we summarize our proof techniques and novel contributions. We will also include a brief discussion of these points in the main text to improve clarity. Compared with [1], our proof of Theorem 2.1 differs in several respects: (i) In the first step of the construction, we replace the single-layer, very wide FFN used in [1] with an FFN of adjustable depth and width. This configuration is closer to practice, since the hidden width of each FFN in most Transformers is a constant multiple of the model’s hidden dimension. We note that this setting is motivated by [2]. (ii) In the second step of the construction, we construct a self-attention layer with tied Q, K, and V projections to implement the “contextual mapping,” while [1] uses untied projections. As the reviewer pointed out, this follows implicitly from the original construction in [1]. We were aware of this connection when developing our proof and have already acknowledged it in Appendix D. We include this step to make the overall construction complete and do not regard it as a core contribution. (iii) In the third step of the construction, we use a new method to construct the value mapping, employing a deep FFN whose width is a constant multiple of the hidden dimension. As in (i), this gives a more practical configuration compared with [1]. It is important to point out that we use Theorem 2.1 to show that Transformers with tied projections retain substantial expressive power at fixed sequence length, as they remain universal approximators. Thus, Theorem 2.1 serves as a baseline, as stated in the paper, and motivates us to investigate more specific tasks that reveal a separation between attention with and without tied projections.
As for the relationship between our work and [4], our novelty is more evident. We discuss the novel contributions in Section 3 in turn. In Theorem 3.1, we first show that self-attention with untied QK projections can approximate any (k,γ)-sparse attention pattern. While the approximation result itself may not be surprising, the key point is that the head dimension depends on the sparsity level k rather than the sequence length. [4] showed that approximating arbitrary attention patterns, which need not be sparse, requires the head dimension to scale linearly with the sequence length. In Theorem 3.1, we show that, for sparse target attention patterns, the head dimension only needs to scale linearly with the sparsity level. Although the results in [5] also depend on sparsity, they require the nonzero attention weights to be equal. To the best of our knowledge, Proposition 3.1 provides the first result showing that self-attention with tied projections cannot approximate a particular attention pattern, and the lower bound is tight. Theorem 3.2 shows that the causal mask can overcome this limitation, which is also a novel contribution. We then turn our focus to norm separation. Theorem 3.3 shows that self-attention with untied projections requires only an O(LlogL) weight norm to approximate the target pattern. Our result and proof differ from those in [4] in several respects: (i) Although both works use random projection techniques, our construction is more concise because it uses Gaussian random projections; (ii) We control the head dimension and parameter norms simultaneously, which requires a more careful analysis of their scaling. [4] only considers controlling the head dimension; (iii) We provide an approximation error bound in spectral norm, rather than a guarantee expressed in terms of ratios as in [4]. Finally, Proposition 3.2 provides, to the best of our knowledge, the first lower bound of this type.