acceptodds
Under review as a conference paper at ICLR 2027

Expressivity and Limitations of Projection Tying in Self-Attention

Abstract

Self-attention typically uses separate query, key, and value projections, yet the effects of tying these projections on expressivity remain poorly understood. We provide a systematic theoretical comparison of query-key (Q=K) and key-value (K=V) tying. We first prove that, for fixed sequence length and hidden dimension, Transformers with positional encodings remain universal approximators even under full tying (Q=K=V), given sufficient depth. At the level of individual attention heads, however, the two tying schemes impose distinct limitations. Under Q=K, the Gram structure of unmasked attention logits precludes arbitrarily accurate approximation of cyclic-shift attention patterns, regardless of head dimension. With causal masking, Q=K can approximate any causally admissible attention pattern, but previous-token routing requires asymptotically larger projected-feature norms than in the untied case. In contrast, K=V preserves attention-pattern realizability while coupling addressing and content transmission through a shared representation. We prove that the minimum head dimension required for K=V to exactly reproduce a given untied head equals the dimension of the joint span of that head’s effective key and value subspaces, and can possibly be twice as large as in the untied case. Controlled synthetic experiments corroborate these theoretical separations. Together, these results distinguish model-level universality from head-level expressivity and limitations.

Primary area:
learning theory
Keywords:
Theory, Self-attention, Expressive Power

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_FAZ2OpenReview ↗
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 Q=KQ=K, 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 O((LlogL))O(\sqrt(LlogL)). With K=VK=V, 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 Q=KQ=K 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 Q=KQ=K 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-QKQK 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 QQ and KK. These issues make it hard to navigate between parts.

Reference:

  1. Kajitsuka et al. Are transformers with one layer self-attention using low-rank weight matrices universal approximators? ICLR 2024.

  2. Likhosherstov et al. On the expressive power of self-attention matrices. 2021.

Questions for authors

Please see Critical Weaknesses.

7 comments
AuthorsOpenReview ↗

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.

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

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,γ)(k,\gamma)-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 kk 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(Llog⁡L)O(\sqrt{L\log L}) 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.

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.

AuthorsOpenReview ↗

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 WQ=WKW_Q = W_K, the input to the Softmax function is a symmetric and positive semi-definite matrix of the form ZZ⊤ZZ^\top. 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 1/21/2 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 k⊤q=cos⁡(θ)∣∣k∣∣⋅∣q∣∣k^\top q=\cos(\theta)||k||\cdot |q||. 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 ε\varepsilon and the sequence length LL. The required norm can therefore be viewed as a function of both ε\varepsilon and LL, and may increase as ε→0\varepsilon\rightarrow 0 or L→∞L\rightarrow\infty. It is important to note that, in our asymptotic comparison, we treat ε\varepsilon as a constant, since the dependence of the required norm on 1/ε1/\varepsilon through softmax is relatively mild. Our comparison between Theorem 3.2 and Proposition 3.2 is asymptotic in LL, but this does not mean that norm separation cannot occur at finite LL. In fact, a norm separation can be observed at a suitably chosen fixed LL, even when LL 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 LL grows. Norm separation at fixed LL 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 LL = 3, we show that the norm upper bound of untied attention is 23log⁡3\sqrt{2\sqrt{3}\log 3}, while the lower bound of tied attention is 8log⁡3\sqrt{8\log 3}.

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

The authors study projection tying in self-attention, focusing on cases where Q=KQ=K and K=VK=V, in terms of expressivity.

First, they show that for a fixed sequence length and hidden dimension, unmasked Transformers with Q=K=VQ=K=V and sufficient depth are universal approximators. Consequently, universality alone does not characterize the limitations of projection tying on expressivity. However, when they consider the expressivity of an attention head, certain limitations arise:

  • An unmasked attention head without the Q=KQ=K constraint can approximate any matrix characterized by local sparsity. In contrast, the Q=KQ=K constraint forces the attention head to be symmetric, so it cannot approximate certain matrix. When a causal mask is introduced, this symmetry in the attention is no longer present.
  • To explore the role of the K=VK=V constraint, the authors consider a scenario where a student attention reproduces a teacher attention. They find that a student model with K=VK=V constraint requires a larger head dimension to reproduce the teacher model, compared to an unrestricted student.
Critical strengths

The paper shows the benefits of parameterizing Q,K,VQ,K,V independently, in terms of expressivity of an attention head. Here, these benefits cannot be captured by universal approximation arguments alone. The paper is well-structured, and the argument presented is compelling.

Critical weaknesses

None

Questions for authors

None

1 comment
AuthorsOpenReview ↗

Rebuttal by Authors

We sincerely thank the reviewer for their careful reading of our paper and their positive assessment of our work. We greatly appreciate the time and thought they devoted to the review, as well as their recognition of our contributions. Their encouraging feedback means a great deal to us, and we are grateful for their support!

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

The paper analyses representation capabilities of transformers under often used parameter tying rules (Q=K and K=V). They show that the universal approximation results hold even with Q=K=V, and hence is not sufficient to distinguish the differences between the various parameter tying rules.

In the K=Q setting, the smmetry of the query key circuit forces symmetric attention patterns, but with causal masking can represent any attention pattern if the hidden dimensions are large enough. They also show that for representing sparse attention patterns, the untied setup with much lower head dimension is sufficient. The untied setup also has advantages in terms of parameter norms, over the tied setup, i.e. the parameters need to move less form init in the untied setup to achieve some attention patterns.

In the K=V setting, they show via a linear algebraic/functional dependence argument that to represent an untied single layer transoformer, a K=V transformer requires extra hidden dimension, depending on the overlap between the query-key and output-value circuit's row/column spaes.

Critical strengths

The paper is clearly written , and the representation arguments are easy to follow. The statements look believable (even though I have not checked the proofs in the appendix) and well motivated.

Theorems 3.3 and Proposition 3.2 look elegant and give a potential line to extend representation arguments into optimisation arguments, or initialisation suggestions.

Critical weaknesses

The paper acknowledges almost all of its weaknesses explicitly -- it being a representation story, inly working on single heads etc. However that doesn't make these (rather large) weaknesses go away.

Can Theorem 3.1 and 3.2 be extended to something like : if X has independent rows, for all (k,\gamma)-sparse attention patterns, there exists a W_Q, W_k that achieves said attention pattern? Right now, the theorem on there existing an X for a given W_Q, W_k seems unintuitive. Because it looks like the job of implementing a given attention pattern at a layer n, seems to require all previous layers to function appropriately. Using the universality theorem for this is technically valid, but seems to put the load for layer n implementing an attention pattern on layers 1 to n-1.

I would have very much appreciated some practical recommendations on parameter tying or other memory-saving tricks as a result of this. e.g. some measurable object (at init or even in early training) to predict the cost-vs-benefits of parameter tying for a given dataset. Right now, if I am reading the paper right, it very strongly recommends against parameter tying.

Questions for authors

See weaknesses above.

2 comments
AuthorsOpenReview ↗

Rebuttal by Authors

We sincerely thank the reviewer for the time and these very suggestive comments. Our response to the weaknesses is presented as follows:

W1: Can Theorem 3.1 and 3.2 be extended to something like : if X has independent rows, for all (k,γ)(k,\gamma)-sparse attention patterns, there exists a WQW_Q, WKW_K that achieves said attention pattern? Right now, the theorem on there existing an XX for a given WQW_Q, WKW_K seems unintuitive. Because it looks like the job of implementing a given attention pattern at a layer n, seems to require all previous layers to function appropriately.

This is an insightful observation. In our setting, we fix WQW_Q and WKW_K while allowing the input sequence XX to change with the target attention pattern to be realized. We adopt this setting to reflect real-world models, where all parameters are fixed after training, different inputs lead to different attention patterns, and consequently, different patterns of information flow among tokens. The reviewer kindly asks wether we can consider a different setting, where XX is fixed instead, while WQW_Q and WKW_K can be chosen accordingly. Indeed, this can be readily achieved within our framework if we assume that X∈RL×dhidX\in R^{L\times d_{hid}} is of full row rank, that is, rank⁡(X)=L\operatorname{rank}(X) = L, as the reviewer pointed out. The construction is straightforward: If X∈RL×dhidX\in \mathbb{R}^{L\times d_{hid}} has full row rank, then we can find a matrix X†=X⊤(XX⊤)−1∈Rdhid×LX^\dagger = X^\top (XX^\top)^{-1} \in \mathbb{R}^{d_{hid}\times L} , which is the right inverse of XX such that XX†=ILXX^{\dagger} = I_{L}. For the fixed WQW_Q and WKW_K and non-fixed XX in Theorem 3.1, 3.2, we let Q=XWQQ = XW_Q, K=XWKK=XW_K which safisfies Softmax⁡(QK⊤)\operatorname{Softmax}(QK^\top) approximates the target attention pattern. Then, for any another XX , we can choose WQ,WKW_Q, W_K as WQ=X†QW_Q = X^{\dagger}Q, and WK=X†KW_K = X^{\dagger}K, which depend on the target attention pattern. Then we have Softmax⁡((XWQ)(XWK)⊤)=Softmax⁡(QK⊤)\operatorname{Softmax}((XW_Q)(XW_K)^\top) = \operatorname{Softmax}(QK^\top), which approximates the target attention pattern as well. In this case, XX is fixed beforehand. Our original setting with fixed WQ,WKW_Q, W_K, non-fixed XX together with this extension (fixed XX and non-fixed WQ,WKW_Q,W_K) can be regarded as a novelty beyond [1], as our head dimension only depends on the sparsity. We thank the reviwer again for this constructive comment, which make our work more complete.

Reference

[1] Bhojanapalli, et al. Low-rank bottleneck in multi-head attention models.

AuthorsOpenReview ↗

Rebuttal by Authors

W2: I would have very much appreciated some practical recommendations on parameter tying or other memory-saving tricks as a result of this. e.g. some measurable object (at init or even in early training) to predict the cost-vs-benefits of parameter tying for a given dataset. Right now, if I am reading the paper right, it very strongly recommends against parameter tying.

We agree that it is important for a theoretical paper to provide guidance or theoretical guarantees for practical applications. Indeed, our work provides several such insights, although they are discussed in different parts of the paper. For example, we first proved in Theorem 2.1 that Transformers with tied projection are sequence-to-sequence universal approximator with a parameter-count upper bound matching the state of the art. This result provides a theoretical perspective on the empirical observation in [2] that tied projections have little effect on model performance in tasks with fixed sequence lengths, such as vision and set processing. SInce there is no free lunch, this success comes from the possibility that these tasks may not rely heavily on flexible attention patterns to control information flow. Later, we show in Section 3 and 4 that tied projection may face several limitations compared with standard attention. Tied QK primarily restricts the realization of attention patterns, especially those capture long chains of dependence. To connect this with reality, many works studied the importance of sparse attention patterns in language tasks [3,4,5]. We also plot typical patterns in Figure 4 and 5 which are proved hard to be realized by tied QK attention or need more resource. This suggests caution when using tied projections in tasks such as language generation. In fact, the experimental results in [2] show that these Transformer present higher PPL and lower accuracy on downstream tasks. Importantly, the limitation we establish for tied QK become more severe as sequence length increases (Proposition 3.2), while the limitation of tied KV is independent of sequence length (Theorem 4.1). One takeaway is that tied QK may be less suitable for language generation as the sequence grows , while tied KV may be worth considering as an alternative.

Regarding a measurable quantity to assess the cost–benefit trade-off of parameter tying on a given dataset, one possible approach is to monitor the similarity between query and key, or between key and value during early training. For K=V tying, our Theorem 4.1 provides a concrete motivation: greater overlap between the effective key and value subspaces reduces the dimension needed to preserve both addressing and content information in a shared representation. Figure 6 illustrates this analysis across layers by comparing the individual numerical ranks of these subspaces with their joint numerical rank. The same quantities could be monitored at early training checkpoints to identify layers where sharing may incur a smaller representational cost. Principal angles between subspaces and cosine similarities between appropriately aligned projected features could provide complementary diagnostics. Such measurements could help guide selective tying across layers or heads under a given memory budget. For Q=K tying, representation similarity may also be informative, although it does not fully capture the directional-routing constraints identified in Section 3.

We therefore believe that our work is best understood as explicitly and quantitatively characterizing the limitations of tied projections, while also establishing their expressive power and thereby affirming their possible feasibility. Since any form of parameter sharing will restrict the expressive power of a neural network architecture, its success depends on whether these restrictions affect properties required by the task. Our work shows that tied QK, KV retain the universal approximation capabilities of their untied counterparts at fixed sequence length, while identifying limitations that may be relevant to tasks such as language generation. In particular, the limitation we establish for tied QK becomes more pronounced with longer sequences, whereas the corresponding bound for tied KV does not grow with sequence length (we prove in Corollary F.1 that tied KV does not affect the realization of any attention pattern in a more strict setting). We thank the reviewer again for encouraging us to rethink how our work may inform practice.

Reference

[2] Kayyam, et al. Do Transformers Need Three Projections? Systematic Study of QKV Variants.

[3] Clark, et al. What does bert look at? an analysis of bert’s attention.

[4] Voita, et al. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned.

[5] Olsson, et al. In-context learning and induction heads.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.