outer product

An outer product

$$\begin{array}{rl}{\mathbb{R}}^{n\times 1}\times {\mathbb{R}}^{1\times n}& \to {\mathbb{R}}^{n\times n}\\ a_i{b}_j& \mapsto C_{ij}\end{array}$$

results in a matrix where the $n^{\text{th}}$ row is the $n^{\text{th}}$ row of the first vector multiplied by the $n^{\text{th}}$ element of the second vector:

torch.einsum("i, j -> ij", [torch.arange(4), torch.arange(4)])
tensor([[0, 0, 0, 0],
		[0, 1, 2, 3],
		[0, 2, 4, 6],
		[0, 3, 6, 9]])

→ an outer product produces a rank-1 matrix

Outer-product memory

The rank-1 matrix produced by an outer product can be interpreted as storing an association from pattern $x$ (key) to pattern $y$ (value).
$W=y{x}^T\in {\mathbb{R}}^{m\times n}$ is a linear map ${\mathbb{R}}^n\to {\mathbb{R}}^n$ that takes a query $q\in {\mathbb{R}}^n$ which, if similar to $x\in {\mathbb{R}}^n$, returns something similar to $y\in {\mathbb{R}}^m$:

$$\begin{array}{rl}Wq& =y{x}^{T}q\\ & =y(x\cdot q)\end{array}$$

If the keys are unit norm, $Wq$ is exactly $y$ scaled by the cosine similarity of $x$ and $q$.

→ outer product stores association from key to value
→ inner product measures similarity of query to key
→ Together, they implement content-based addressing, aka associative memory.

For many pairs, we stack keys $K=[x^{(1)}\dots x^{(P)}]\in {\mathbb{R}}^{n\times P}$ and values $V=[y^{(1)}\dots y^{(P)}]\in {\mathbb{R}}^{m\times P}$ and build a weight matrix that stores all associations $W=V{K}^{\top }\in {\mathbb{R}}^{m\times n}$. Then

$$Wq=V(K^{\top }q)$$

So $K^{\top }q\in {\mathbb{R}}^P$ computes the similarity of the query to all keys, and $V(K^{\top }q)$ returns a similarity-weighted sum of all values.
If the keys are orthonormal, this exactly returns the value corresponding to the most similar key.
Too many non-orthogonal keys clutter recall.
Mitigations incude:

• normalization, scaling (e.g. NTM, SDP, layer normalization, RMS norm, qk-norm)
• applying a hard/soft threshold after reading, letting the correct item win even if noisy (Hopfield Network, SDP)
• increasing the the memory capacity, i.e. the dimensionality of keys/queries $n$ (for each ${\mathbb{R}}^n$ key, each nonmatching $x^{T}q$ adds ~$\mathcal{O}\left(\frac{1}{\sqrt{n}}\right)$ noise to the readout → std of noise is $\mathcal{O}\left(\frac{\mathcal{P}}{\sqrt{n}}\right)$ for $P$ items)
• using sparse keys/queries (e.g. locality-sensitive hashing, sparse attention, …)

Link to original