Chapter 6Data structures

In computer science, a data structure is a specialized format for organizing, storing and accessing data. Mathematically, a data structure forms a so-called algebraic structure: it consists of a set and the functions to operate on that set. In this chapter, we review how to incorporate data structures into differentiable programs, with a focus on lists and dictionaries.

6.1 Lists

A list is an ordered sequence of elements. We restrict ourselves to lists whose elements all belong to the same value space $\cV$. Formally, we denote a list of fixed length $K$ with values in $\cV$ by a $K$-tuple $$\l \coloneqq (\l_1, \dots, \l_K) \in \cL_{K}(\cV)$$ where each $\l_i \in \cV$ and where $$\cL_K(\cV) \coloneqq \cV^K = \underbrace{\cV \times \dots \times \cV}_{K\text{ times}}.$$

6.1.1 Basic operations

Getting values

We first present how to retrieve values from a list $\l \in \cL_K(\cV)$. We define the function $\mathrm{list.get} \colon \cL_K(\cV) \times [K] \to \cV$ as $$\mathrm{list.get}(\l, i) \coloneqq \l_i.$$ The function is continuous and differentiable in $\l \in \cL_K(\cV)$ but not in $i \in [K]$, as it is a discrete variable. In the particular case $\cV = \RR$, $\cL_K(\cV)$ is equivalent to $\RR^K$ and we can therefore write $$\mathrm{list.get}(\l, i) = \langle \l, \e_i \rangle,$$ where $\{\e_1,\dots,\e_K\}$ is the standard basis of $\RR^K$.

Setting values

We now present how to replace values from a list $\l \in \cL_K(\cV)$. We define the function $\mathrm{list.set} \colon \cL_K(\cV) \times [K] \times \cV \to \cL_K(\cV)$ as $$[\mathrm{list.set}(\l, i, \v)]_j \coloneqq \begin{cases} \v &\mbox{ if } i = j \\ \l_j &\mbox{ if } i \neq j \end{cases},$$ for $j \in [K]$. In the functional programming spirit, the function returns the whole new list, even though a single element has been modified. Again, the function is continuous and differentiable in $\l \in \cL_K(\cV)$ and $\v \in \cV$ but not in $i \in [K]$. In the particular case $\cV = \RR$, given a list $\l = (l_1,\dots,l_K)$, we can set the value $v \in \RR$ by $$\mathrm{list.set}(\l, i, v) = \l + (v - l_i) \e_i.$$ That is, we subtract the old value $l_i$ and add the new value $v$ at the location $i \in [K]$ in $\l$.

Implementation

A fixed-length list can be implemented as an array, which enables $O(1)$ random access to individual elements. The hardware counterpart of an array is random access memory (RAM), in which memory can be retrieved by address (location).

6.1.2 Operations on variable-length lists

So far, we focused on lists of fixed length $K$. We now turn our attention to variable-length lists, whose size can decrease or increase over time. In addition to the $\mathrm{list.get}$ and $\mathrm{list.set}$ functions, they support functions that can change the size of a list.

Initializing lists

In order to initialize a list, we define $\mathrm{list.init} \colon \cV \to \cL_1(\cV)$ as $$\mathrm{list.init}(\v) \coloneqq (\v),$$ where we used $(\v)$ to denote a $1$-tuple.

Pushing values

In order to add new values either to the left or to the right, we define $\mathrm{list.pushLeft} \colon \cL_K(\cV) \times \cV \to \cL_{K+1}(\cV)$ as $$\mathrm{list.pushLeft}(\l, \v) \coloneqq (\v, \l_1, \dots, \l_K).$$ and $\mathrm{list.pushRight} \colon \cL_K(\cV) \times \cV \to \cL_{K+1}(\cV)$ as $$\mathrm{list.pushRight}(\l, \v) \coloneqq (\l_1, \dots, \l_K, \v).$$

Popping values

In order to remove values either from the left or from the right, we define $\mathrm{list.popLeft} \colon \cL_K(\cV) \to \cL_{K-1}(\cV) \times \cV$ as $$\mathrm{list.popLeft}(\l) \coloneqq (\l_2, \dots, \l_{K}), \l_1$$ and $\mathrm{list.popRight} \colon \cL_K(\cV) \to \cL_{K-1}(\cV) \times \cV$ as $$\mathrm{list.popRight}(\l) \coloneqq (\l_1, \dots, \l_{K-1}), \l_K.$$ The set $\cL_0(\cV)$ is a singleton which contains the empty list.

Inserting values

The pushLeft and pushRight functions can only insert values at the beginning and at the end of a list, respectively. We now study the insert function, whose goal is to be able to add a new value at an arbitrary location, shifting all values to the right and increasing the list size by $1$. We define the function $\mathrm{list.insert}: \cL_K(\cV) \times [K+1] \times \cV \rightarrow \cL_{K+1}(\cV)$ as $$[\mathrm{list.insert}(\l, i, \v)]_j \coloneqq \begin{cases} \l_j & \mbox{if} \ j < i \\ \v & \mbox{if} \ j = i \\ \l_{j-1} & \mbox{if} \ j > i \end{cases},$$ for $j \in [K+1]$. As for the $\mathrm{list.set}$ function, $\mathrm{list.insert}$ is readily continuous and differentiable in $\l$ and $\v$, but not in $i$, as it is a discrete variable. As special cases, we naturally recover $$\begin{align*} \mathrm{list.insert}(\l, 1, \v) & = \mathrm{list.pushLeft}(\l, \v), \\ \mathrm{list.insert}(\l, K+1, \v) & = \mathrm{list.pushRight}(\l, \v). \end{align*}$$

Differentiability

The $\mathrm{list.init}$, $\mathrm{list.push}$ and $\mathrm{list.pop}$ functions are readily continuous and differentiable with respect to their arguments (a continuous relaxation is not needed). As for the $\mathrm{list.set}$ function, the $\mathrm{list.insert}$ function is continuous and differentiable in $\l$ and $\v$, but not in $i$.

Implementation

Under the hood, a variable-length list can be implemented as a linked list or as a dynamic array. A linked list gives $O(K)$ random access while a dynamic array allows $O(1)$ random access, at the cost of memory reallocations.

Stacks and queues

The $\mathrm{list.pushRight}$ and $\mathrm{list.popRight}$ functions can be used to implement a stack (last in first out a.k.a. LIFO behavior). The $\mathrm{list.pushLeft}$ and $\mathrm{list.popRight}$ functions can be used to implement a queue (first in first out a.k.a. FIFO behavior).

6.1.3 Continuous relaxations using soft indexing

Getting values

In order to be able to differentiate $\mathrm{list.get}$ w.r.t. indexing, a natural idea is to replace the integer index $i \in [K]$ by a distribution $\piv_i \in \triangle^K$, which we can interpret as a soft index. An integer index $i \in [K]$ is then equivalent to a delta distribution $\piv_i \in \{\e_1, \dots, \e_K\}$. We define the continuous relaxation $\mathrm{list.softGet} \colon \cL_K(\cV) \times \triangle^K \to \conv(\cV)$ as $$\begin{align*} \mathrm{list.softGet}(\l, \piv_i) &\coloneqq \sum_{j=1}^K \pi_{i,j} \l_j \\ &= \mathrm{cond}(\piv_i, \l_1, \dots, \l_K) \\ &= \EE_{I \sim \mathrm{Categorical}(\piv_i)}[\l_I], \end{align*}$$ where $\mathrm{cond}$ is studied in Section 5.7. In the particular case $\cV = \RR$, we obtain $$\mathrm{list.softGet}(\l, i) = \langle \l, \piv_i \rangle.$$ This is illustrated in Fig. 6.1.

The choice of the distribution $\piv_i = (\pi_{i,1}, \dots, \pi_{i,K})$ encodes the importance of the elements $(\l_1,\dots,\l_K)$ w.r.t. $\l_i$. If we consider that the smaller $|i-j|$ is, the more related $\l_i$ and $\l_j$ are, then it makes sense to define a distribution centered around $i$ (i.e., such that the mode of the distribution is achieved at $i$). For example, limiting ourselves to the neighbors $\l_{i-1}$ and $\l_{i+1}$ (i.e., a window of size $1$), we can define the sparse distribution $$\piv_i \coloneqq \frac{1}{4} \cdot \e_{i-1} + \frac{1}{2} \e_i + \frac{1}{4} \cdot \e_{i+1} \in \triangle^K.$$ In this particular case, the continuous relaxation of the $\mathrm{list.get}$ function can then be expressed as a discrete convolution, $$\mathrm{list.softGet}(\l, \piv_i) = \left(\mathrm{list.get}(\l, \cdot) \ast \kappa\right)(i) = \sum_{j=-\infty}^\infty \mathrm{list.get}(\l, i - j) \kappa(j),$$ where $\kappa(-1) \coloneqq \frac{1}{4}$, $\kappa(1) \coloneqq \frac{1}{4}$, $\kappa(0) \coloneqq \frac{1}{2}$, and $\kappa(j) \coloneqq 0$ for $j \not \in \{-1,0,1\}$. Assuming $\cV = \RR^M$, the computational complexity of $\mathrm{list.softGet}$ is $O(M \cdot |\mathrm{supp}(\piv_i)|)$.

Setting values

To differentiate w.r.t. indexing, we can define the continuous relaxation $\mathrm{list.softSet} \colon \cL_K(\cV) \times \triangle^K \times \cV \to \cL_K(\conv(\cV))$ as $$\begin{align*} \left[\mathrm{list.softSet}(\l, \piv_i, \v)\right]_j &\coloneqq \EE[\mathrm{list.set}(\l, I, \v)]_j \\ &= \PP(I=j) \v + \PP(I \neq j) \l_j \\ &= \pi_{i,j} \v + (1 - \pi_{i,j}) \l_j, \end{align*}$$ where $j \in [K]$ and $I \sim \mathrm{Categorical}(\piv_i)$. Equivalently, we can write $$\begin{align*} \mathrm{list.softSet}(\l, \piv_i, \v) &= (\pi_{i,1} \v + (1-\pi_{i,1}) \l_1, \dots, \pi_{i,K} \v + (1-\pi_{i,K}) \l_K) \\ &= (\mathrm{ifelse}(\pi_{i,1}, \v, \l_1), \dots, \mathrm{ifelse}(\pi_{i,K}, \v, \l_K)), \end{align*}$$ where $\mathrm{ifelse}$ is studied in Section 5.6. Since $$\mathrm{ifelse}(\pi, \u_1, \u_0) = \EE_{I \sim \mathrm{Bernoulli}(\pi)}[\u_I],$$ this relaxation amounts to using an element-wise expectation. As a result, the list output by $\mathrm{list.softSet}$ takes values in $\conv(\cV)$ instead of $\cV$. Note however that when $\cV = \RR^M$, then $\conv(\cV) = \RR^M$ as well.

Inserting values

To differentiate value insertion w.r.t. indexing, we can define the continuous relaxation $\mathrm{list.softInsert} \colon \cL_K(\cV) \times \triangle^{K+1} \times \cV \to \cL_{K+1}(\conv(\cV))$ as $$\begin{align*} [\mathrm{list.softInsert}(\l, \piv_i, \v)]_j &\coloneqq \EE[\mathrm{list.insert}(\l, I, \v)] \\ & = \PP(I > j) \l_j + \PP(I = j) \v + \PP(I < j) \l_{j-1}, \end{align*}$$ where $I \sim \mathrm{Categorical}(\piv_i)$. The three necessary probabilities can easily be calculated for $j \in [K+1]$ by $$\begin{align*} \PP(I > j) &= \begin{cases} 0 &\mbox{ if } j = K+1 \\ \sum_{k=j+1}^{K+1} \pi_{i, k} &\mbox{ otherwise } \end{cases} \\ \PP(I = j) &= \pi_{i,j} \quad \\ \PP(I < j) &= \begin{cases} 0 &\mbox{ if } j = 1 \\ \sum_{k=1}^{j-1} \pi_{i, k} &\mbox{ otherwise } \end{cases}. \end{align*}$$

Multi-dimensional indexing

In multi-dimensional lists (arrays or tensors), each element $\l_\iv \in \cV$ of a list $\l \in \cL_{K_1,\dots,K_T}(\cV)$ can now be indexed by a multivariate integer $\iv = (i_1, \dots, i_T) \in [K_1] \times \dots \times [K_T]$, where $T \in \NN$ is the number of axes of $\l$. We can always flatten a multi-dimensional list into a uni-dimensional list by replacing the multi-dimensional index $\iv \in [K_1] \times \dots \times [K_T]$ by a flat index $i \in [K_1 \dots K_T]$. The converse operation, converting a flat uni-dimensional array into a multi-dimensional array, is also possible. Therefore, there is a bijection between $[K]$ and $[K_1] \times \dots \times [K_T]$ for $K \coloneqq K_1 \dots K_T$.

This means that the previous discussion on soft indexing in the uni-dimensional setting readily applies to the multi-dimensional setting. All it takes is the ability to define a probability distribution $\piv_\iv \in \triangle^{K_1 \times \dots \times K_T}$. For example, when working with images, we can define a probability distribution putting probability mass only on the neighboring pixels of pixel $\iv$, a standard approach in image processing. Another simple approach is to use a product of axis-wise probability distributions.

6.2 Dictionaries

A dictionary (a.k.a. associative array or map) is an unordered list of key-value pairs, such that each possible key appears at most once in the list. We denote the set of keys by $\cK$ and the set of values by $\cV$ (both being potentially infinite). We can then define the set of dictionaries of size $L$ from $\cK$ to $\cV$ by $$\cD_L(\cK,\cV) \coloneqq \cL_L(\cK \times \cV) = (\cK \times \cV)^L$$ and one such dictionary by $$\d \coloneqq ((\kv_1,\v_1), \dots, (\kv_L,\v_L)) \in \cD_L(\cK,\cV).$$

6.2.1 Basic operations

Getting values

The goal of the $\mathrm{dict.get}$ function is to retrieve the value associated with a key, assuming that the dictionary contains this key. Formally, we define the $\mathrm{dict.get} \colon \cD_L(\cK,\cV) \times \cK \to \cV \cup \{\infty\}$ function as $$\mathrm{dict.get}(\d, \kv) \coloneqq \begin{cases} \v_i &\mbox{ if } \exists i \in [L] \text{ s.t. } \kv = \kv_i \\ \infty & \mbox{ if } \kv \not \in \{\kv_1,\dots,\kv_L\} \end{cases}.$$ The function is continuous and differentiable in the dictionary $\d$, but not in the key $\kv$. Equivalently, we can write the function as $$\begin{align*} \mathrm{dict.get}(\d, \kv) \coloneqq \frac{\sum_{i=1}^L \eq(\kv, \kv_i) \v_i} {\sum_{i=1}^L \eq(\kv, \kv_i)}. \end{align*}$$ The denominator encodes the fact that the function is undefined if no key in the dictionary $\d$ matches the key $\kv$. Assuming $\kv \in \{\kv_1,\dots,\kv_L\}$ and $\cV = \RR^M$, we can also write $$\mathrm{dict.get}(\d, \kv) = \v_i \quad \text{where} \quad i = \argmax_{j \in [L]} \|\kv - \kv_j\|_2,$$ which shows that we can see $\mathrm{dict.get}$ as a nearest neighbor search.

Setting values

The goal of the $\mathrm{dict.set}$ function is to replace the value associated with an existing key. Formally, we define the $\mathrm{dict.set}: \cD_L(\cK, \cV) \times \cK \times \cV \rightarrow \cD_L(\cK, \cV)$ function as $$(\mathrm{dict.set}(\d, \kv, \v))_i \coloneqq \begin{cases} (\kv_i, \v) & \mbox{if} \ \kv_i = \kv \\ (\kv_i, \v_i) & \mbox{if} \ \kv_i \neq \kv \end{cases}.$$ The function leaves the dictionary unchanged if no key in the dictionary matches the input key $\kv$. The function is continuous and differentiable in $\d$ and $\v$, but not in $\kv$.

Implementation

While we view dictionaries as lists of key-value pairs, in practice, a dictionary (a.k.a. associative array) is often implemented using a hash table or search trees. The hardware counterpart of a dictionary is called content-addressable memory (CAM), a.k.a. associative memory.

6.2.2 Continuous relaxation using kernel regression

A dictionary can be seen as a (potentially non-injective) function that associates a value $\v$ to each key $\kv$. To obtain a continuous relaxation of the operations associated to a dictionary, we can adopt a probabilistic perspective of the mapping from keys to values. We can view keys and values as two continuous random variables $K$ and $V$. We can express the conditional PDF $f(\v|\kv )$ of $V|K$ in terms of the joint PDF $f(\kv, \v)$ of $(K,V)$ and the marginal PDF $f(\kv)$ of $K$ as $$f(\v|\kv) = \frac{f(\kv, \v)}{f(\kv)}.$$ Integrating, we obtain the conditional expectation $$\begin{align*} \EE[V | K=\kv] = \int_{\cV} f(\v|\kv) \v d\v = \int_{\cV} \frac{f(\kv, \v)}{f(\kv)} \v d\v. \end{align*}$$ This is the Bayes predictor, in the sense that $\EE[V|K]$ is the minimizer of $\EE[(h(K) - V)^2]$ over the space of measurable functions $h \colon \cK \to \cV$. Using a sample of $L$ input-output pairs $(\kv_i, \v_i)$, corresponding to key-value pairs in our case, Nadaraya–Watson kernel regression estimates the joint PDF and the marginal PDF using kernel density estimation (KDE). Using a product of isotropic kernels $\kappa_\sigma$ and $\rho_\sigma$ for key-value pairs, we can define $$\widehat{f}_\sigma(\kv, \v) \coloneqq \frac{1}{L} \sum_{i=1}^L \kappa_\sigma(\kv - \kv_i) \rho_\sigma(\v - \v_i).$$ The corresponding marginal distribution on the keys is then given as $$\begin{align*} \widehat{f}_\sigma(\kv) &\coloneqq \int_{\cV} \widehat{f}_\sigma(\kv, \v)d\v\\ &= \frac{1}{L} \sum_{i=1}^L \kappa_\sigma(\kv - \kv_i) \int_{\cV} \rho_\sigma(\v - \v_i) d\v\\ &=\frac{1}{L} \sum_{i=1}^L \kappa_\sigma(\kv - \kv_i). \end{align*}$$ Replacing $f$ with $\widehat{f}_\sigma$, we obtain the following estimator of the conditional expectation $$\begin{align*} \widehat{\EE}[V|K=\kv] &\coloneqq \int_{\cV} \frac{\widehat{f}_\sigma(\kv, \v)}{\widehat{f}_\sigma(\kv)} \v d\v \\ &= \int_{\cV} \frac{\frac{1}{L} \sum_{i=1}^L \kappa_\sigma(\kv - \kv_i) \rho_\sigma(\v - \v_i)}{\frac{1}{L} \sum_{i=1}^L \kappa_\sigma(\kv - \kv_i)} \v d\v \\ &= \frac{\sum_{i=1}^L \kappa_\sigma(\kv - \kv_i) \int_{\cV} \rho_\sigma(\v - \v_i) \v d\v}{\sum_{i=1}^L \kappa_\sigma(\kv - \kv_i)} \\ &= \frac{\sum_{i=1}^L \kappa_\sigma(\kv - \kv_i) \v_i}{\sum_{i=1}^L \kappa_\sigma(\kv - \kv_i)}. \end{align*}$$ In the above, we assumed that $\rho_\sigma(\v - \v_i) = p_{\v_i,\sigma}(\v)$, where $p_{\v_i,\sigma}(\v)$ is the PDF of a distribution whose mean is $\v_i$, so that $$\int_{\cV} \rho_\sigma(\v - \v_i)\v d\v = \EE_{V \sim p_{\v_i,\sigma}}[V] = \v_i.$$ Given a dictionary $\d = ((\kv_1,\v_1),\dots,(\kv_L,\v_L))$, we can therefore define the $\mathrm{dict.softGet} \colon \cD_L(\cK, \cV) \times \cK \to \conv(\cV)$ function as $$\mathrm{dict.softGet}(\d, \kv) \coloneqq \frac{\sum_{i=1}^L \kappa_\sigma(\kv - \kv_i) \v_i}{ \sum_{i=1}^L \kappa_\sigma(\kv - \kv_i)}.$$ This kernel regression perspective on dictionaries was previously pointed out by Zhang et al. (2021). It is illustrated in Fig. 6.2 with $\cK = \cV = \RR$.

6.2.3 Discrete probability distribution perspective

While the set of possible keys $\cK$ is potentially infinite, the set of keys $\{\kv_1,\dots,\kv_L\} \subset \cK$ associated with a particular dictionary $\d = ((\kv_1,\v_1),\dots,(\kv_L,\v_L))$ is finite. To a particular key $\kv$, we can therefore associate a discrete probability distribution $\piv_\kv = (\pi_{\kv,1},\dots,\pi_{\kv,L}) \in \triangle^L$ over the keys $(\kv_1,\dots,\kv_L)$ of $\d$, defined by $$\pi_{\kv,i} \coloneqq \frac{\kappa_\sigma(\kv - \kv_i)}{\sum_{j=1}^L \kappa_\sigma(\kv - \kv_j)} \quad \forall i \in [L].$$ This distribution captures the affinity between the input key $\kv$ and the keys $(\kv_1,\dots,\kv_L)$ of dictionary $\d$. As illustrated in Fig. 6.3, we obtain $$\begin{align*} \mathrm{dict.softGet}(\d, \kv) &= \EE_{i \sim \mathrm{Categorical}(\piv_\kv)}[\v_i] \\ &= \sum_{i=1}^L \pi_{\kv,i} \v_i. \end{align*}$$ In the limit $\sigma \to 0$, we recover $$\mathrm{dict.get}(\d, \kv) = \frac{\sum_{i=1}^L \mathrm{eq}(\kv,\kv_i) \v_i}{\sum_{i=1}^L \mathrm{eq}(\kv,\kv_i)}.$$

While the $\mathrm{dict.get}$ function is using a mapping from keys $\kv \in \{\kv_1,\dots,\kv_L\}$ to integer indices $[L]$, the $\mathrm{dict.softGet}$ function is using a mapping from keys $\kv \in \{\kv_1,\dots,\kv_L\}$ to distributions $\piv_{\kv} \in \triangle^L$. This perspective allows us to reuse the soft functions we developed for lists in Section 6.1. For example, we can softly replace the value associated with key $\kv$ by performing $$\mathrm{list.softSet}(\d, \piv_\kv, (\kv, \v)).$$ Unlike $\mathrm{dict.set}$, the function is differentiable w.r.t.  the distribution $\piv_\kv$.

6.2.4 Link with attention in Transformers

In the case when $\kappa_\sigma$ is the Gaussian kernel, assuming that the keys are normalized to have unit norm (which is often the case in practical implementations (Dehghani et al., 2023; Schlag et al., 2021)), we obtain $$\begin{align*} \kappa_\sigma(\kv - \kv_i) &= \exp(-\|\kv - \kv_i\|^2_2 / (2\sigma^2)) \\ &= \exp(-(\|\kv\|^2_2 + \|\kv_i\|^2_2) / (2\sigma^2)) \exp(\langle \kv, \kv_i \rangle / \sigma^2) \\ &= \exp(-1/\sigma^2) \exp(\langle \kv, \kv_i \rangle / \sigma^2) \end{align*}$$ so that $$\begin{align*} \pi_{\kv,i} &= \frac{\kappa_\sigma(\kv - \kv_i)}{\sum_{j=1}^L \kappa_\sigma(\kv - \kv_j)}\\ &= \frac{\exp(\langle \kv, \kv_i \rangle / \sigma^2)}{ \sum_{j=1}^L \exp(\langle \kv, \kv_j \rangle / \sigma^2)}. \end{align*}$$ We recognize the softargmax operator. Given a dictionary
$\d = ((\kv_1,\v_1), \dots, (\kv_L,\v_L))$, we thus recover attention from Transformers (Vaswani et al., 2017) as $$\begin{align*} \mathrm{dict.softGet}(\d, \kv) &= \sum_{i=1}^L \pi_{\kv,i} \v_i \\ &= \sum_{i=1}^L \frac{\exp(\langle \kv, \kv_i \rangle / \sigma^2) \v_i}{ \sum_{j=1}^L \exp(\langle \kv, \kv_j \rangle / \sigma^2)}. \end{align*}$$ Transformers can therefore be interpreted as relying on a differentiable dictionary mechanism. Besides Transformers, content-based memory addressing is also used in neural Turing machines (Graves et al., 2014).

6.3 Summary

• Operations on lists are continuous and differentiable w.r.t. the list, but not w.r.t. the integer index. Similarly, operations on dictionaries are continuous and differentiable w.r.t. the dictionary, but not w.r.t. the input key.

• Similarly to the way we handled the predicate in conditionals, we can replace the integer index (respectively the key) with a probability distribution over the indices (respectively the keys).

• This allows us to obtain a probabilistic relaxation of operations on lists. In particular, the relaxation for $\mathrm{list.get}$ amounts to performing a convolution. The relaxation for $\mathrm{dict.get}$ amounts to computing a conditional expectation using kernel regression.

• When using a Gaussian kernel with keys normalized to unit norm, we recover softargmax attention from Transformers.