Linear Memory, Reconstruction and Recall
What SVD tells us about a learned matrix as memory
In Towards a Testable Theory of Emergence, I interpreted matrix multiplication as a key–value memory computation through its singular value decomposition. k-NN as a Binding Algorithm extends that interpretation across learning methods. The purpose here is to strengthen it with a quantitative account of storage and recall.
Alex Wang’s You could have invented transformers from memory asks how many memories a store can hold before interference becomes comparable to the desired signal. We use that question to develop the earlier SVD viewpoint: with keys in \(\mathbb R^d\), how accurately can a matrix return the intended values as the number \(M\) of stored pairs grows?
SVD gives a memory representation of any linear map. To quantify recall, we then specify the pairs to be stored and how the matrix is fitted. These constructions provide an analysable model of the memory interpretation; their capacity estimates apply under the assumptions stated below. Here recall means reconstructing the intended output vector, rather than identifying an item from a list of candidates.
Vectors are columns, and \(A^\top\) denotes transpose. Appendix A defines the notation and dimensions; the subsequent appendices give the derivations.
A matrix as a key–value store
Let \(W\in\mathbb R^{p\times d}\) have rank \(r_W\) and compact singular value decomposition (SVD)
\[ W=U\Sigma Z^\top =\sum_{\ell=1}^{r_W}\sigma_\ell u_\ell z_\ell^\top. \]
For a query \(q\),
\[ Wq=\sum_{\ell=1}^{r_W} \underbrace{\sigma_\ell u_\ell}_{\text{value}} \underbrace{z_\ell^\top q}_{\text{query–key comparison}}. \]
The right singular vectors \(z_\ell\) are orthonormal keys; \(\sigma_\ell u_\ell\) are their associated values. Querying with \(z_j\) returns its value exactly. Components of a query orthogonal to these keys lie in the null space \(\ker(W)=\{q:Wq=0\}\) and contribute zero.
These SVD-derived pairs describe the action of the learned map; they do not identify its original training pairs. To develop the memory interpretation quantitatively, we now supply a collection of intended key–value pairs and examine two rules for constructing a matrix that reproduces them. Rank counts independent directions, not independently specified memories: one linear rule can generate arbitrarily many consistent input–output pairs.
Two ways to construct the memory matrix
Suppose we want to store \(M\) key–value pairs \((k_i,v_i)\). Each pair specifies one requirement: querying with \(k_i\) should return \(v_i\). Thus \(M\) counts supplied pairs, with one intended value per key; it does not count SVD components. Put the keys and values into columns:
\[ K=[k_1,\ldots,k_M]\in\mathbb R^{d\times M}, \qquad V=[v_1,\ldots,v_M]\in\mathbb R^{p\times M}. \]
Assume \(\|k_i\|=1\). We want a single matrix \(W\) that returns \(v_i\) when multiplied by \(k_i\). We examine two ways to construct it. The word “store” describes the role of the resulting matrix; it is not a separate statistical estimator.
First, construct one matrix per key–value pair and add them. For each pair \((k_i,v_i)\), find a matrix \(A_i\) using only that pair. Choose the smallest Frobenius norm, \(\|A\|_F=(\sum_{ab}A_{ab}^2)^{1/2}\), among matrices that return \(v_i\) exactly:
\[ A_i=\underset{A}{\operatorname{arg\,min}}\ \frac12\|A\|_F^2 \quad\text{subject to}\quad Ak_i=v_i. \]
For a unit key, the solution is \(A_i=v_i k_i^\top\). This is an outer product: a column vector multiplied by a row vector. Summing the matrices gives
\[ W_{\mathrm{OP}}=\sum_i v_i k_i^\top=VK^\top. \]
We call the sum the outer-product store, abbreviated OP. Each \(A_i\) is constructed using only its own key–value pair. This construction requires no assumption that the pairs are statistically independent. The sum generally does not minimize total recall error because each matrix also acts on other keys. Appendix B derives the single-pair solution.
Second, fit one matrix using all key–value pairs together. Choose \(W\) to minimize the sum of squared output errors, equivalently the squared Frobenius norm of the residual matrix:
\[ \min_W\ \frac12\sum_{i=1}^{M}\|Wk_i-v_i\|^2 =\min_W\ \frac12\|WK-V\|_F^2. \]
This is ordinary multivariate linear least squares without an intercept. We call its fitted matrix the least-squares store, abbreviated LS. If several matrices minimize the error, choose the one with smallest Frobenius norm:
\[ W_{\mathrm{LS}}=VK^\dagger. \]
The symbol \(K^\dagger\) denotes the Moore–Penrose pseudoinverse, defined through the SVD below. The minimum-norm choice is a tie-break among least-squares solutions, not a ridge penalty. Appendix C proves the formula.
Now take the compact SVD of the key matrix:
\[ K=U_K\Sigma_K Z_K^\top, \qquad r_K=\operatorname{rank}(K). \]
The columns of \(U_K\) are orthonormal directions in the input-key subspace in \(\mathbb R^d\). The columns of \(Z_K\) are orthonormal directions in the space of coefficients over the \(M\) stored pairs, \(\mathbb R^M\). Each \(z_{K,\ell}\) specifies how to combine the columns of \(K\); applying those same coefficients to \(V\) gives the combination of values \(Vz_{K,\ell}\). The diagonal entries of \(\Sigma_K\) are singular values: they describe the scaling of these directions, not the intended values \(v_i\). The key rank \(r_K\) need not equal the store rank \(r_W\).
The two stores become
\[ W_{\mathrm{OP}}=VZ_K\Sigma_K U_K^\top, \qquad W_{\mathrm{LS}}=VZ_K\Sigma_K^{-1}U_K^\top. \]
They use the same input directions with different gains. Least squares compensates for the nonzero singular gains of the key matrix. Written one direction at a time,
\[ W_{\mathrm{LS}}=\sum_{\ell=1}^{r_K} \underbrace{\frac{Vz_{K,\ell}}{\sigma_{K,\ell}}}_{\text{effective value}} \underbrace{u_{K,\ell}^{\top}}_{\text{effective key}}. \]
This connects the supplied pairs to the memory interpretation: the fitted matrix uses orthonormal keys \(u_{K,\ell}\) and associated values \(Vz_{K,\ell}/\sigma_{K,\ell}\). Each effective value combines the supplied values using coefficients determined by the supplied keys. Querying with \(u_{K,\ell}\) returns that effective value exactly. This expansion comes from the SVD of \(K\); it need not be the SVD of \(W\), because the effective values need not be orthogonal.
At the supplied keys,
\[ W_{\mathrm{LS}}K=VZ_KZ_K^\top=VP, \qquad P=K^\dagger K. \]
Write \(\operatorname{col}(B)\) for the column space of \(B\), the span of its columns. Here \(P=Z_KZ_K^\top\) is an orthogonal projector: \(P^\top=P\) and \(P^2=P\). It projects coefficients over the stored pairs in \(\mathbb R^M\) onto \(\operatorname{col}(Z_K)\), the row space of \(K\). It differs from \(Q=KK^\dagger=U_KU_K^\top\), which projects inputs in \(\mathbb R^d\) onto \(\operatorname{col}(K)\). Appendix C derives both projectors.
Measure the strength of recall
The identity \(W_{\mathrm{LS}}K=VP\) tells us what the fitted matrix returns. To assess it as memory, we must ask how much of each response comes from the requested value and how much comes from other stored values. Comparing these contributions lets us quantify how recall changes as we increase the number of stored pairs.
We use power signal-to-noise ratio (SNR) to compare the intended contribution with cross-talk from other key–value pairs:
\[ \mathrm{SNR}=\frac{\text{power of the intended contribution}}{\text{expected power of cross-talk}}. \]
Here cross-talk is generated by the other stored key–value pairs; it is not measurement noise added to the query. SNR measures their relative strength. We also calculate squared reconstruction error because a response can have little cross-talk and still return the intended value at the wrong magnitude.
For the calculation, assume that the values are independent, zero-mean random unit vectors, independent of the keys. Expectations below are over these values, conditional on \(K\). These assumptions let us measure interference when the values have no systematic relation to one another. They also make the cross terms vanish in the expected noise power. This is a baseline for unrelated outputs. In a learned representation, keys and values may instead be dependent or learned together. We later examine a shared linear rule to show how such structure changes what can be stored.
Let \(h_j=P_{jj}=\|Z_K^\top e_j\|^2\), the leverage score of key \(j\), where \(e_j\) is the coordinate vector with a one in position \(j\). It measures how much of the coordinate direction for pair \(j\) survives projection by \(P\). Recall decomposes into
\[ W_{\mathrm{LS}}k_j =\underbrace{h_jv_j}_{\text{signal}} +\underbrace{\sum_{i\ne j}P_{ij}v_i}_{n_j:\ \text{cross-talk noise}}. \]
Since \(P^2=P\) and independent zero-mean values eliminate cross terms,
\[ \text{signal power}=h_j^2, \qquad \mathbb E_V\|n_j\|^2 =\sum_{i\ne j}P_{ij}^2=h_j-h_j^2. \]
Thus, for \(0<h_j<1\),
\[ \boxed{\mathrm{SNR}_j=\frac{h_j}{1-h_j}.} \]
With unit signal power, SNR is the reciprocal of total zero-mean noise variance. Here the signal is attenuated by \(h_j\). Dividing the recalled output by \(h_j\) restores unit signal power and gives
\[ \mathbb E_V\left\|\frac{n_j}{h_j}\right\|^2 =\frac{1-h_j}{h_j} =\frac1{\mathrm{SNR}_j}. \]
For vector noise, total variance means \(\operatorname{tr}\operatorname{Cov}(n)\). SNR is a ratio of powers, not the expectation of a random ratio. Wang expresses interference relative to signal amplitude. Using root-mean-square interference gives the equivalent power convention
\[ \mathrm{SNR}=\left(\frac{\text{RMS interference amplitude}}{\text{signal amplitude}}\right)^{-2}. \]
Both conventions therefore give the same threshold when interference and signal have equal strength.
Reconstruction error compares the unnormalized output with \(v_j\), so it includes attenuation as well as noise:
\[ \mathbb E_V\|W_{\mathrm{LS}}k_j-v_j\|^2 =(1-h_j)^2+(h_j-h_j^2) =1-h_j. \]
Because \(\sum_jh_j=\operatorname{tr}(P)=r_K\),
\[ \boxed{\frac1M\mathbb E_V\|W_{\mathrm{LS}}K-V\|_F^2 =1-\frac{r_K}{M}.} \]
Appendix D shows each expectation and explains the boundary cases.
Recover Wang’s capacity estimate
If the supplied keys are linearly independent, least squares fits every supplied value exactly. There can be at most \(d\) such keys. Beyond this, arbitrary prescribed values cannot in general all be fitted exactly: they must respect the linear dependencies among the keys. The capacity calculation below concerns approximate recall of independent random values, not exact storage of \(2d\) arbitrary pairs.
We can now connect recall quality to memory count. The exact SNR depends on each key through \(h_j\). To obtain an estimate using only \(M\) and \(d\), suppose \(M>d\), the keys have full row rank, and leverage scores are approximately uniform. Then
\[ h_j\approx\frac dM \quad\Longrightarrow\quad \mathrm{SNR}_j\approx\frac{d}{M-d}. \]
A numerical capacity requires a chosen recall criterion. For a required power SNR of at least \(\gamma>0\), the approximation gives
\[ \frac{d}{M-d}\gtrsim\gamma \quad\Longrightarrow\quad M\lesssim d\left(1+\frac1\gamma\right). \]
Wang’s criterion takes equal signal and cross-talk strength as the threshold. Setting \(\gamma=1\) therefore gives
\[ \boxed{M\approx2d.} \]
Does fitting all key–value pairs together improve this threshold over simply adding their individual matrices? To make that comparison, the outer-product store gives
\[ W_{\mathrm{OP}}k_j=v_j+\sum_{i\ne j}(k_i^\top k_j)v_i. \]
For this comparison, average the cross-talk power over independent uniform spherical keys as well as the random values. Then
\[ \mathbb E\|W_{\mathrm{OP}}k_j-v_j\|^2=\frac{M-1}{d}, \qquad \mathrm{SNR}_{\mathrm{OP}}=\frac{d}{M-1}. \]
Its signal already has unit power, so SNR is directly reciprocal noise variance. Unit SNR occurs at \(M=d+1\), approximately \(d\) for large dimension. This compares an averaged-power result for the outer-product construction with the approximately uniform-leverage result for least squares; it is not a per-dataset guarantee of twice the capacity. Joint fitting accounts for relationships among the keys. Appendix E derives the spherical-key moments and distinguishes exact identities from the uniform-leverage approximation.
What the dimension-only estimate leaves out
The count \(M\) and dimension \(d\) give an approximate operating point. To assess a particular learned matrix, we also need to know whether recall is uneven across keys, whether it tolerates perturbed queries, and whether the values share structure.
Unequal recall across keys. Uniform leverage is an assumption, not a consequence of unit norms. Consider
\[ K=[e_1,e_1,e_1,e_2],\qquad d=2,\quad M=4=2d. \]
Here \(e_1=(1,0)^\top\) and \(e_2=(0,1)^\top\). The same input \(e_1\) is asked to return three independently specified values. Least squares returns their average, while it can fit the value at \(e_2\) exactly. The leverage scores are \((1/3,1/3,1/3,1)\); Appendix F gives the full projector. The first three key–value pairs have SNR \(1/2\); the fourth is recalled exactly. No key–value pair has SNR one, although the average expected squared error is \(1/2\).
Random spherical keys have zero expected pairwise inner products and squared inner products of expectation \(1/d\). Their distances concentrate near equality in high dimension. Exchangeability gives \(\mathbb E[h_j]=d/M\) at full row rank, but using \(h_j\approx d/M\) for individual keys additionally requires concentration. The exact SNR formula retains the key geometry through \(h_j\).
Sensitivity to query perturbations. Recall at an exact stored key does not establish that nearby queries return accurate values. To test this, let \(q=k_j+\eta\), with zero-mean noise independent of the keys and values and covariance \(\tau^2I_d\). Here \(I_d\) is the \(d\times d\) identity and \(\tau^2\) is noise variance per input coordinate. For a fixed store,
\[ \mathbb E_\eta\|Wq-v_j\|^2 =\|Wk_j-v_j\|^2+\tau^2\|W\|_F^2. \]
Under the same random-value assumptions, the key SVD yields
\[ \boxed{ \mathbb E_{V,\eta}\|W_{\mathrm{LS}}(k_j+\eta)-v_j\|^2 =1-h_j+\tau^2\sum_{\ell=1}^{r_K}\sigma_{K,\ell}^{-2}. } \]
This assumes additive noise without subsequent query normalization. The first term measures reconstruction error at the stored key. The second measures noise amplification. Small singular values can make recall unstable even when fitting is exact. Appendix G derives the formula step by step.
Shared structure permits more exact pairs. A learned matrix may represent a shared rule across many examples. We therefore need to distinguish recalling unrelated values from reproducing values that follow that rule. The capacity calculation assumes independent random values. If instead \(V=AK\) for a fixed linear map \(A\in\mathbb R^{p\times d}\), then
\[ W_{\mathrm{LS}}=AKK^\dagger=A P_{\operatorname{col}(K)}. \]
Every query in the key span has its intended output recovered exactly. There can be more than \(d\) such key–value pairs because their values respect the dependencies among keys. The capacity estimate for independent random values does not limit how many consistent pairs a linear rule can represent. Here \(P_{\operatorname{col}(K)}=Q=KK^\dagger\) is the input-space projector. Appendix H proves exact recall on this span and gives the general consistency condition.
What to assess in a learned store
The storage calculation gives quantitative content to the earlier interpretation of matrix multiplication as memory. SVD describes the map in terms of keys and values; specifying intended pairs and a fitting rule lets us assess how well that memory works. Does the store reproduce its intended key–value pairs? Are errors concentrated on particular keys? Does recall remain accurate when queries are perturbed?
For the least-squares model analysed here, leverage scores determine expected reconstruction error and SNR at stored keys. The key singular spectrum determines additional sensitivity to isotropic query noise. Wang’s \(M=2d\) estimate follows when these results are reduced to approximately uniform leverage and a unit-SNR threshold.
For a particular learned matrix, measure the residuals \(\|Wk_j-v_j\|^2\) directly. The formula \(1-h_j\) is an expectation under the least-squares random-value model, not the measured error for arbitrary fixed values. For independent isotropic additive query noise, the additional expected error is \(\tau^2\|W\|_F^2\); expressing it through the singular values of \(K\) additionally uses that model.
Appendix A: notation and assumptions
All spaces are real and finite-dimensional. Vectors are columns. Unless an expectation includes the keys explicitly, \(K\) is held fixed.
| Symbol | Meaning and dimensions |
|---|---|
| \(M,d,p\) | Number of key–value pairs, input dimension, and output dimension. |
| \(k_i\in\mathbb R^d\), \(v_i\in\mathbb R^p\) | Key and intended value of key–value pair \(i\). |
| \(K\in\mathbb R^{d\times M}\), \(V\in\mathbb R^{p\times M}\) | Matrices whose columns are the keys and values. |
| \(W\in\mathbb R^{p\times d}\) | Linear memory map; its response to \(q\in\mathbb R^d\) is \(Wq\). |
| \(r_W,r_K\) | Ranks of \(W\) and \(K\), which need not be equal. |
| \(U,\Sigma,Z\) | Compact SVD factors of \(W\): dimensions \(p\times r_W\), \(r_W\times r_W\), \(d\times r_W\). |
| \(U_K,\Sigma_K,Z_K\) | Compact SVD factors of \(K\): dimensions \(d\times r_K\), \(r_K\times r_K\), \(M\times r_K\). |
| \(K^\dagger\in\mathbb R^{M\times d}\) | Pseudoinverse \(Z_K\Sigma_K^{-1}U_K^\top\). Only positive singular values occur in \(\Sigma_K\). |
| \(P\in\mathbb R^{M\times M}\) | Projector on the coefficient space of stored pairs \(K^\dagger K=Z_KZ_K^\top\). |
| \(Q\in\mathbb R^{d\times d}\) | Input-space projector \(KK^\dagger=U_KU_K^\top\). |
| \(h_j\) | Diagonal entry \(P_{jj}\), the leverage score of key–value pair \(j\). |
| \(e_j\), \(I_n\) | Coordinate vector of the indicated space; identity matrix of size \(n\). |
| \(\eta\), \(\tau^2\) | Additive input noise and its variance per coordinate when \(\operatorname{Cov}(\eta)=\tau^2I_d\). |
For a matrix \(A\in\mathbb R^{a\times b}\),
\[ \operatorname{col}(A)=\{Ax:x\in\mathbb R^b\}\subseteq\mathbb R^a, \qquad \ker(A)=\{x\in\mathbb R^b:Ax=0\}. \]
The row space is \(\operatorname{row}(A)=\operatorname{col}(A^\top)\subseteq\mathbb R^b\). The span of vectors is the set of their linear combinations. For a subspace \(\mathcal S\), its orthogonal complement is \(\mathcal S^\perp=\{x:x^\top s=0\text{ for every }s\in\mathcal S\}\). In particular,
\[ \ker(A)=\operatorname{row}(A)^\perp. \]
An orthogonal projector onto \(\mathcal S\) maps each vector to its component in \(\mathcal S\); its matrix is symmetric and idempotent. If \(B\) has orthonormal columns spanning \(\mathcal S\), that matrix is \(BB^\top\).
The vector inner product is \(x^\top y\). The Frobenius inner product is \(\langle A,B\rangle_F=\operatorname{tr}(A^\top B)\), with \(\|A\|_F^2=\langle A,A\rangle_F\). The trace \(\operatorname{tr}(A)\) is the sum of a square matrix’s diagonal entries. We use \(\operatorname{tr}(AB)=\operatorname{tr}(BA)\) whenever both products are defined. The notation \(\operatorname{arg\,min}\) denotes a minimizing argument, or the set of minimizers if it is not unique.
For a random vector \(x\), its covariance is
\[ \operatorname{Cov}(x)=\mathbb E[(x-\mathbb Ex)(x-\mathbb Ex)^\top]. \]
Thus \(\mathbb E\|x\|^2=\operatorname{tr}\operatorname{Cov}(x)\) when \(\mathbb Ex=0\). For the recall calculations we assume mutually independent values with \(\mathbb Ev_i=0\) and \(\|v_i\|=1\) almost surely, independent of \(K\). Their directions need not be uniformly distributed. These conditions imply
\[ \mathbb E_V[v_i^\top v_j]=\begin{cases}1&i=j,\\0&i\ne j,\end{cases} \qquad \mathbb E_V[V^\top V]=I_M. \]
Keys have unit norm. Only the spherical-key calculation additionally assumes that they are independent and uniform on the unit sphere.
Appendix B: the matrix for a single key–value pair and its sum
For a unit key \(k\), the matrix \(A_0=vk^\top\) is feasible because \(A_0k=v(k^\top k)=v\). Any other feasible \(A\) can be written \(A=A_0+B\), where \(Bk=0\). Their Frobenius inner product is
\[ \langle A_0,B\rangle_F =\operatorname{tr}(kv^\top B) =v^\top Bk=0. \]
Consequently,
\[ \|A\|_F^2=\|A_0\|_F^2+\|B\|_F^2\geq\|A_0\|_F^2, \]
with equality only at \(B=0\). Hence \(A_0\) is the unique minimum-norm solution. For a nonunit, nonzero key, the corresponding solution is \(vk^\top/\|k\|^2\); the unit-key assumption removes this denominator.
Adding the single-pair solutions yields
\[ W_{\mathrm{OP}}=\sum_i v_i k_i^\top=VK^\top. \]
For key \(k_j\),
\[ W_{\mathrm{OP}}k_j =\sum_i v_i(k_i^\top k_j) =v_j+\sum_{i\ne j}v_i(k_i^\top k_j). \]
Orthogonal keys make the extra terms zero. For general keys, the summation rule contains no joint correction for them.
Appendix C: least squares, the pseudoinverse and the two projectors
Write \(K=U_K\Sigma_KZ_K^\top\) with positive diagonal singular values and orthonormal columns in \(U_K\) and \(Z_K\). Define
\[ P=Z_KZ_K^\top,\qquad Q=U_KU_K^\top. \]
Decompose the residual as
\[ WK-V=(WU_K\Sigma_K-VZ_K)Z_K^\top-V(I_M-P). \]
The first term has each row in \(\operatorname{col}(Z_K)\); the second has each row in its orthogonal complement. Therefore their Frobenius inner product is zero. Orthonormality of \(Z_K\) gives
\[ \|WK-V\|_F^2 =\|WU_K\Sigma_K-VZ_K\|_F^2 +\|V(I_M-P)\|_F^2. \]
The second term cannot be changed by choosing \(W\). The first can be made zero, so every minimizer satisfies
\[ WU_K=VZ_K\Sigma_K^{-1}. \]
The action of \(W\) on the orthogonal complement of \(\operatorname{col}(K)\) is unconstrained. All minimizers have the form
\[ W=VZ_K\Sigma_K^{-1}U_K^\top+B(I_d-Q), \]
where \(B\in\mathbb R^{p\times d}\) is arbitrary. The two terms act on orthogonal input subspaces, so
\[ \|W\|_F^2 =\|VZ_K\Sigma_K^{-1}U_K^\top\|_F^2 +\|B(I_d-Q)\|_F^2. \]
The unique minimum-norm fitted matrix sets the unconstrained action to zero:
\[ W_{\mathrm{LS}}=VZ_K\Sigma_K^{-1}U_K^\top=VK^\dagger. \]
Multiplication verifies
\[ K^\dagger K=P,\qquad KK^\dagger=Q,\qquad W_{\mathrm{LS}}K=VP. \]
Both \(P\) and \(Q\) are symmetric and idempotent, but act in different spaces. The SVD of the store itself has the analogous decomposition: \(\operatorname{row}(W)=\operatorname{col}(Z)\) and \(\ker(W)=\operatorname{col}(Z)^\perp\). Thus \(Wq=WZZ^\top q\) for every query, proving the full-SVD recall identity in the main text.
Appendix D: leverage, cross-talk variance and reconstruction error
Since \(P=P^\top=P^2\),
\[ h_j=e_j^\top Pe_j=\|Pe_j\|^2 =\|Z_K^\top e_j\|^2,\qquad 0\leq h_j\leq1. \]
Also,
\[ \sum_iP_{ij}^2=(P^\top P)_{jj}=P_{jj}=h_j, \qquad \sum_{i\ne j}P_{ij}^2=h_j-h_j^2. \]
Column \(j\) of \(W_{\mathrm{LS}}K=VP\) gives
\[ W_{\mathrm{LS}}k_j=h_jv_j+n_j, \qquad n_j=\sum_{i\ne j}P_{ij}v_i. \]
The coefficients are fixed conditional on \(K\). Independence and zero means yield \(\mathbb E_Vn_j=0\) and
\[ \begin{aligned} \mathbb E_V\|n_j\|^2 &=\sum_{i\ne j}\sum_{\ell\ne j} P_{ij}P_{\ell j}\,\mathbb E_V[v_i^\top v_\ell]\\ &=\sum_{i\ne j}P_{ij}^2=h_j-h_j^2. \end{aligned} \]
Desired signal power is \(\|h_jv_j\|^2=h_j^2\). Its ratio to expected cross-talk power is \(h_j/(1-h_j)\) when \(0<h_j<1\). Dividing the output by \(h_j\) gives unit desired signal power and noise variance \((1-h_j)/h_j\), the reciprocal SNR.
For reconstruction error, the desired value is \(v_j\), not \(h_jv_j\). Because \(v_j\) is independent of \(n_j\) and both have zero mean,
\[ \begin{aligned} \mathbb E_V\|W_{\mathrm{LS}}k_j-v_j\|^2 &=\mathbb E_V\|(h_j-1)v_j+n_j\|^2\\ &=(h_j-1)^2+\mathbb E_V\|n_j\|^2\\ &=(h_j-1)^2+h_j-h_j^2=1-h_j. \end{aligned} \]
Finally,
\[ \sum_jh_j=\operatorname{tr}(Z_KZ_K^\top) =\operatorname{tr}(Z_K^\top Z_K)=r_K, \]
so averaging the preceding error gives \(1-r_K/M\). At \(h_j=1\), the off-diagonal coefficients in column \(j\) vanish and recall is exact, with zero noise. A leverage score of zero would imply \(Pe_j=0\) and hence \(k_j=KPe_j=0\); unit keys exclude this case. If all keys are linearly independent, \(r_K=M\) and \(P=I_M\).
Appendix E: random keys and the dimension-only estimates
For a uniformly distributed unit vector \(k\in\mathbb R^d\), sign symmetry gives \(\mathbb Ek=0\). Rotational symmetry implies \(\mathbb E[kk^\top]=cI_d\). Taking traces gives \(1=cd\), hence
\[ \mathbb E[kk^\top]=\frac1dI_d. \]
For two independent spherical keys, conditional on the unit vector \(k_j\),
\[ \mathbb E[k_i^\top k_j\mid k_j]=0, \qquad \mathbb E[(k_i^\top k_j)^2\mid k_j] =k_j^\top\frac{I_d}{d}k_j=\frac1d. \]
For any fixed pair, Chebyshev’s inequality therefore gives
\[ \Pr(|k_i^\top k_j|\geq t)\leq\frac{1}{dt^2},\qquad t>0. \]
This establishes pairwise concentration near orthogonality as dimension grows. Since \(\|k_i-k_j\|^2=2-2k_i^\top k_j\), squared distances concentrate near two. Uniform control over a growing collection of pairs requires accounting for their number.
For outer-product recall, the same value calculation as in Appendix D gives, conditional on \(K\),
\[ \mathbb E_V\|W_{\mathrm{OP}}k_j-v_j\|^2 =\sum_{i\ne j}(k_i^\top k_j)^2. \]
Averaging over spherical keys yields \((M-1)/d\). Unit signal power divided by this expected noise power gives \(d/(M-1)\). This is not the expectation over keys of the conditional SNR, which involves a reciprocal inside the expectation.
For least squares, the exact conditional formula remains \(h_j/(1-h_j)\). Exchangeable keys make the leverage scores identically distributed. If their rank is fixed at \(r_K\), the trace identity implies
\[ M\mathbb E[h_j]=\mathbb E\sum_i h_i=r_K. \]
This establishes \(\mathbb E[h_j]=r_K/M\), not that every \(h_j\) equals its mean, nor that \(\mathbb E[h_j/(1-h_j)]\) equals the ratio evaluated at that mean. The dimension-only estimate additionally assumes approximately uniform leverage. For \(r_K=d<M\),
\[ \frac{h_j}{1-h_j}\approx\frac{d/M}{1-d/M} =\frac{d}{M-d}. \]
Equating this approximation to one gives \(M\approx2d\). At precisely \(M=2d\), the average expected reconstruction error is nevertheless exactly \(1/2\) whenever rank is \(d\), irrespective of leverage uniformity. A chosen SNR threshold is an operating criterion, not a theorem about successful item identification.
Appendix F: a nonuniform-key counterexample
For \(K=[e_1,e_1,e_1,e_2]\in\mathbb R^{2\times4}\),
\[ KK^\top=\begin{pmatrix}3&0\\0&1\end{pmatrix}, \qquad P=K^\top(KK^\top)^{-1}K =\begin{pmatrix} 1/3&1/3&1/3&0\\ 1/3&1/3&1/3&0\\ 1/3&1/3&1/3&0\\ 0&0&0&1 \end{pmatrix}. \]
The leverage scores are its diagonal entries. For the first three key–value pairs, signal power is \(1/9\) and expected cross-talk power is \(2/9\), so SNR is \(1/2\). For the fourth, signal power is one and cross-talk is zero. The expected errors are \((2/3,2/3,2/3,0)\), whose mean is \(1/2\). This verifies that the average error can obey the dimension-only identity while individual SNRs differ substantially.
Appendix G: recall with additive query noise
Fix \(K,V,W\) and let \(a_j=Wk_j-v_j\). Assume \(\eta\) is independent, has zero mean and covariance \(\tau^2I_d\). Expanding the squared error gives
\[ \mathbb E_\eta\|a_j+W\eta\|^2 =\|a_j\|^2+2a_j^\top W\mathbb E\eta +\mathbb E_\eta[\eta^\top W^\top W\eta]. \]
The middle term is zero. Using the trace identity,
\[ \mathbb E_\eta[\eta^\top W^\top W\eta] =\operatorname{tr}(W^\top W\,\mathbb E[\eta\eta^\top]) =\tau^2\|W\|_F^2. \]
For \(W=VK^\dagger\), conditional on \(K\), the random-value assumptions give
\[ \begin{aligned} \mathbb E_V\|VK^\dagger\|_F^2 &=\operatorname{tr}\bigl((K^\dagger)^\top\mathbb E_V[V^\top V]K^\dagger\bigr)\\ &=\|K^\dagger\|_F^2 =\sum_{\ell=1}^{r_K}\sigma_{K,\ell}^{-2}. \end{aligned} \]
Adding the stored-key reconstruction error from Appendix D establishes
\[ \mathbb E_{V,\eta}\|W_{\mathrm{LS}}(k_j+\eta)-v_j\|^2 =1-h_j+\tau^2\sum_{\ell=1}^{r_K}\sigma_{K,\ell}^{-2}. \]
No Gaussian assumption is needed for \(\eta\); its independence and stated first two moments suffice. The intended value remains \(v_j\) for the noisy query. A model in which the intended output also changes with the query is a different task. Renormalizing \(k_j+\eta\) would also change the calculation.
Appendix H: consistent values and exact recall on the key span
Suppose \(V=AK\) for a fixed linear map \(A\). Then
\[ W_{\mathrm{LS}}=AKK^\dagger=AQ. \]
For any query \(q\in\operatorname{col}(K)\), \(Qq=q\), so \(W_{\mathrm{LS}}q=Aq\). For a general query,
\[ Aq-W_{\mathrm{LS}}q=A(I_d-Q)q. \]
The component \((I_d-Q)q\) lies in \(\ker(K^\top)\), the orthogonal complement of the input-key span. It need not lie in \(\ker(A)\). This distinguishes an input direction unobserved by the keys from a direction that the intended map itself annihilates.
More generally, exact fitting of supplied values is possible if and only if
\[ \ker(K)\subseteq\ker(V), \quad\text{equivalently}\quad Kc=0\Longrightarrow Vc=0. \]
Necessity follows because \(WK=V\) implies \(Vc=WKc=0\) whenever \(Kc=0\). For sufficiency, \(\operatorname{col}(I_M-P)=\ker(K)\), so the condition gives \(V(I_M-P)=0\). Thus \(V=VP=W_{\mathrm{LS}}K\), proving exact fitting.
Here \(\ker(K)\subseteq\mathbb R^M\) describes dependencies among key–value pairs, while \(\ker(K^\top)\subseteq\mathbb R^d\) describes input directions outside the key span. These spaces have different roles and must not be interchanged.