Zoology: Measuring and Improving Recall in Efficient Language Models — part 11/14

Cleaned-text code points [154481, 170241). Bibliography omitted here; source.md includes it.
We will start by describing the arithmetic circuit that computes the states 𝒛 n ∈ ℝ d × d \bm{z}^{n}\in\mathbbm{R}^{d\times d} here. Indeed, each state requires exactly two alternative layers with only multiplication gates and only addition gates, respectively. First, we note that for each n ∈ N n\in N , we have 𝒛 n ≡ γ 𝒛 n − 1 + ( 𝐀 [ n , : ] ) ⊤ 𝐕 [ n , : ] . \bm{z}^{n}\equiv\gamma\bm{z}^{n-1}+\left({\bf A}[n,:]\right)^{\top}{\bf V}[n,:]. Since we can compute 𝒛 0 \bm{z}^{0} in 𝒪 ⁡ ( 1 ) \mathcal{O}(1) layers and computing γ ⋅ 𝒛 n − 1 \gamma\cdot\bm{z}^{n-1} needs exactly one layer with each entry from 𝒛 n − 1 \bm{z}^{n-1} serving as an input to a multiplication gate along with γ \gamma , the depth of the circuit is 𝒪 ⁡ ( N ) \mathcal{O}(N) with width d 2 d^{2} . We can thus apply Theorem H.21 to get an ( 𝒪 ⁡ ( N ) , 𝒪 ⁡ ( N  log ⁡ d ) , d 2 , 𝒪 ⁡ ( d 2 ) , 𝒪 ⁡ ( d 2 ) ) − (\mathcal{O}(N),\mathcal{O}(N\log{d}),d^{2},\mathcal{O}(d^{2}),\mathcal{O}(d^{2}))- BaseConv model that can compute 𝒛 n \bm{z}^{n} for each n ∈ N n\in N . ∎

##### The Space Complexity of AR

In the context of the Retnet Model and associative recall, it is worth exploring the space complexity of the associative recall (AR) problem: The AR problem takes key-value pairs { 𝒌 i , 𝒗 i } i = 0 n − 1 \{\bm{k}_{i},\bm{v}_{i}\}_{i=0}^{n-1} along with a query 𝒒 \bm{q} appended at the end as input and the goal is to output 𝒗 i \bm{v}_{i} if 𝒒 = 𝒌 i \bm{q}=\bm{k}_{i} for some i ∈ [ 0 , N − 1 ] i\in[0,N-1] . Indeed, we will first provide a lower-bound for any model that purports to solve AR. To this end, we will require a randomized communication complexity lower bound result for the index problem : The index problem has two agents, Alice and Bob, where Alice has a string 𝒙 ∈ { 0 , 1 } n \bm{x}\in\{0,1\}^{n} and Bob has an index i ∈ [ n ] i\in[n] , and the goal for the players is to output the i i -th entry 𝒙 i \bm{x}_{i} . Moreover, we also require the communication to be one-way : only Alice is allowed to send a single message to Bob and Bob needs to output the answer. We will make use of the following lower-bound result.

###### Theorem H.23 ( [ Jayram et al., 2008 ] ) .

The one-way randomized communication complexity 13 13 13 The randomized communication complexity of function f f is defined as min π ⁡ ‖ π ‖ \min_{\pi}\left\lVert\pi\right\rVert , where π \pi ranges over all randomized protocols that can solve f f with probability of success at least 2 / 3 2/3 . of the index problem for sending an n n -length bit string is Ω ⁡ ( n ) \Omega(n) .

We now use Theorem H.23 to provide a lower bound on the number of bits required by the Retnet model to solve AR.

###### Corollary H.24 .

The RetNet model requires Ω ⁡ ( N ) \Omega(N) -bits to solve AR for d ≤ N d\leq\sqrt{N} .

###### Proof.

Consider an instance ( 𝒙 , i ) (\bm{x},i) of the index problem with 𝒙 ∈ { 0 , 1 } N \bm{x}\in\{0,1\}^{N} . We now describe the corresponding instance of the AR problem: { i , 𝒙 i } i = 0 N − 1 , i . \{i,\bm{x}_{i}\}_{i=0}^{N-1},i. (8) Next, consider the following one-way protocol for solving the index problem using the RetNet model. Alice with their access of 𝒙 ∈ { 0 , 1 } N \bm{x}\in\{0,1\}^{N} generate an input for AR (without the query) as in equation 8 . Alice then runs the RetNet model on { i , 𝒙 i } i = 0 N − 1 \{i,\bm{x}_{i}\}_{i=0}^{N-1} and sends the memory content of running the RetNet model to Bob. This should include the output 𝒛 N − 1 \bm{z}^{N-1} as we can reasonably assume that both have access weight matrices 𝐖 A , 𝐖 C , 𝐖 V {\bf W}_{A},{\bf W}_{C},{\bf W}_{V} and the scalar γ \gamma . Since we assume that this model solves AR, the output 𝙾𝚞𝚝 [ N , : ] = 𝒙 i {\tt Out}[N,:]=\bm{x}_{i} should contain the associated value of i i . Here, Bob can compute 𝙾𝚞𝚝 [ N , : ] {\tt Out}[N,:] by using the memory content sent by Alice along with the term γ  𝒛 N − 1 \gamma\bm{z}^{N-1} : 𝒙 i = 𝙾𝚞𝚝 [ N , : ] = 𝐂 [ N , : ] 𝒛 N = 𝐂 [ N , : ] ( γ 𝒛 N − 1 + ( 𝐀 [ N , : ] ) ⊤ 𝐕 [ N , : ] ) . \bm{x}_{i}={\tt Out}[N,:]={\bf C}[N,:]\bm{z}^{N}={\bf C}[N,:]\left(\gamma\bm{z}^{N-1}+({\bf A}[N,:])^{\top}{\bf V}[N,:]\right). That is, the total number of bits that are communicated in this protocol is O ⁡ ( d 2 ) O(d^{2}) . For d ≤ N d\leq\sqrt{N} , have shown that a one-way communication protocol exists for solving the index problem exists that uses o ⁡ ( N ) o(N) communication complexity. This contradicts Theorem H.23 and hence, we conclude that the ReNet model solving AR also needs Ω ⁡ ( N ) \Omega(N) bits. ∎

### H.7 The Multiple-Query Associative Recall Problem

#### H.7.1 Introduction

In this section, we consider a general version of the associative recall problem [ Ba et al., 2016 ] .

##### Setup.

Next, we will redefine the multiple-query associative recall problem ( Mqar ) from Definition 3.1 to a slightly more general problem: Suppose we are given an input sequence 𝒖 [ 0 ⋯ N − 1 ] ≜ { ( 𝒌 0 , 𝒗 0 , 𝒒 0 ) , … , ( 𝒌 N 3 − 1 , 𝒗 N 3 − 1 , 𝒒 N 3 − 1 ) } \bm{u}[0\cdots N-1]\triangleq\left\{\left(\bm{k}_{0},\bm{v}_{0},\bm{q}_{0}\right),\ldots,\left(\bm{k}_{\frac{N}{3}-1},\bm{v}_{\frac{N}{3}-1},\bm{q}_{\frac{N}{3}-1}\right)\right\} with each 𝒌 i , 𝒗 i , 𝒒 i ∈ C \bm{k}_{i},\bm{v}_{i},\bm{q}_{i}\in C is a token drawn from a vocabulary of size c = | C | c=|C| . Our goal is then to check, for each 1 ≤ i ≤ N 3 − 1 1\leq i\leq\frac{N}{3}-1 , whether there exists 0 ≤ j < i 0\leq j<i such that 𝒒 i ≡ 𝒌 j \bm{q}_{i}\equiv\bm{k}_{j} , and if so, output 𝒗 j \bm{v}_{j} . Here, we note that it suffices to have d ≈ log ⁡ ( c ) d\approx\log(c) so that 𝒌 i , 𝒗 i , 𝒒 i \bm{k}_{i},\bm{v}_{i},\bm{q}_{i} is embedded in { 0 , 1 } d \{0,1\}^{d} . However, we will specify the specific embedding being used for the results below. Here, we construe the tokens 𝒌 i , 𝒒 i \bm{k}_{i},\bm{q}_{i} and 𝒗 i \bm{v}_{i} to be the keys , the queries , and the associated values . Indeed, it might be helpful to think of the input 𝒖 \bm{u} as a streaming sequence of key-value pairs for which we sequentially employ standard associative recall for every key that shows up in the sequence so far.

To see that the above generalizes Definition 3.1 , considers a sequence of length N 3 \frac{N}{3} : 𝒖 [ 0 ⋯ N − 1 ] := { 𝒙 0 , … , 𝒙 N − 1 } \bm{u}[0\cdots N-1]:=\{\bm{x}_{0},\ldots,\bm{x}_{N-1}\} , where each 𝒙 i ∈ C \bm{x}_{i}\in C . The goal of Definition 3.1 is then to check, for each 1 ≤ i < N − 1 1\leq i<N-1 , whether there exists 0 ≤ j < i 0\leq j<i such that 𝒙 i ≡ 𝒙 j \bm{x}_{i}\equiv\bm{x}_{j} , and if so, output 𝒙 j + 1 \bm{x}_{j+1} , and continue otherwise. We can reduce this problem to the above general formulation by taking the following sequence of tuples as the input { ( 𝒙 i , 𝒙 i + 1 , 𝒙 i ) } \{(\bm{x}_{i},\bm{x}_{i+1},\bm{x}_{i})\} .

###### Remark H.25 .

As noted above, this version is more general than Definition 3.1 . Thus, the results proven in the sequel, which are proven for the above general Mqar can be ported (with constant blowup in parameters) to get the results corresponding results for Definition 3.1 .

#### H.7.2 Mqar Solution via Attention

Before describing how BaseConv solves the multiple-query associative recall problem, we discuss how Attention solves it trivially using pairwise inner-products. To this end, we will specify how the input is presented to attention.

###### Remark H.26 .

We note that the input for the multiple-query associative recall problem 𝒖 ∈ { 0 , 1 } N × d \bm{u}\in\{0,1\}^{N\times d} has designated indices for the keys, queries, and values in the sequence. We gather these indices below: 𝒦 \displaystyle\mathcal{K} = { i ∈ { 0 , … , N − 1 } | i ≡ 0 mod 3 } , \displaystyle=\{i\in\{0,\ldots,N-1\}\lvert\ i\equiv 0\mod{3}\}, (9) 𝒱 \displaystyle\mathcal{V} = { i ∈ { 0 , … , N − 1 } | i ≡ 1 mod 3 } , \displaystyle=\{i\in\{0,\ldots,N-1\}\lvert\ i\equiv 1\mod{3}\}, 𝒬 \displaystyle\mathcal{Q} = { i ∈ { 0 , … , N − 1 } | i ≡ 2 mod 3 } , . \displaystyle=\{i\in\{0,\ldots,N-1\}\lvert\ i\equiv 2\mod{3}\},. The input 𝒖 ∈ ℝ N × d \bm{u}\in\mathbbm{R}^{N\times d} to Attention for d = 3  c d=3c is then given by 𝒖 [ i , : ] ≡ { [ 𝒌 i : 𝟎 c : 𝟎 c ] if  i ∈ 𝒦 [ 𝟎 c : 𝒗 i : 𝟎 c ] if  i ∈ 𝒱 [ 𝟎 c : 𝟎 c : 𝒒 i ] if  i ∈ 𝒬 \bm{u}[i,:]\equiv\begin{cases}[\bm{k}_{i}:\bm{0}^{c}:\bm{0}^{c}]&\text{ if }i\in\mathcal{K}\\ [\bm{0}^{c}:\bm{v}_{i}:\bm{0}^{c}]&\text{ if }i\in\mathcal{V}\\ [\bm{0}^{c}:\bm{0}^{c}:\bm{q}_{i}]&\text{ if }i\in\mathcal{Q}\end{cases} Here, each 𝒌 i , 𝒗 i , 𝒒 i \bm{k}_{i},\bm{v}_{i},\bm{q}_{i} is embedded as a one-hot encoding in { 0 , 1 } c \{0,1\}^{c} .

Without softmax, the output for an attention layer 𝐎 ∈ ℝ N × d {\bf O}\in\mathbbm{R}^{N\times d} is given by 𝐎 ≡ ( 𝐐𝐊 ⊤ )  𝐕 , {\bf O}\equiv\left({\bf Q}{\bf K}^{\top}\right){\bf V}, (10) where 𝐐 , 𝐊 , 𝐕 ∈ ℝ N × d {\bf Q},{\bf K},{\bf V}\in\mathbbm{R}^{N\times d} are defined as 𝒖  𝐖 Q , 𝒖  𝐖 K , 𝒖  𝐖 V \bm{u}{\bf W}_{Q},\bm{u}{\bf W}_{K},\bm{u}{\bf W}_{V} for 𝒖 ∈ ℝ N × d \bm{u}\in\mathbbm{R}^{N\times d} . Instead of position embeddings, we use ALiBi, a popular technique that biases the attention scores 𝐐𝐊 ⊤ {\bf Q}{\bf K}^{\top} with a lower-triangular Toeplitz matrix 𝐁 ∈ ℝ N × N {\bf B}\in\mathbb{R}^{N\times N} [ Press et al., 2021 ] . The values in this matrix are controlled by a fixed hyperparameter so they do not count towards the number of parameters in the model.

###### Proposition H.27 .

Given an input 𝐮 ∈ { 0 , 1 } N × d \bm{u}\in\{0,1\}^{N\times d} (encoded as in Remark H.26 ) where d = 3  c d=3c , Attention with linear biases (even without using soft-max) solves Mqar for 𝐮 \bm{u} using 𝒪 ⁡ ( c 2 ) {\mathcal{O}}(c^{2}) parameters, 𝒪 ⁡ ( N  c 2 + N 2  c ) {\mathcal{O}}(Nc^{2}+N^{2}c) time complexity and 𝒪 ⁡ ( 1 ) {\mathcal{O}}(1) layers.

###### Proof.

We use two layers of attention. We will start by specifying the projection matrices for the first layer 𝐖 Q 1 , 𝐖 K 1 , 𝐖 V 1 ∈ ℝ d × d {\bf W}_{Q}^{1},{\bf W}^{1}_{K},{\bf W}^{1}_{V}\in\mathbbm{R}^{d\times d} as: 𝐖 K 1 ≡ 𝐖 Q 1 ≡ 𝟎 , 𝐖 V 1 ≡ ( 𝟎 𝟎 𝟎 𝟎 𝐈 𝐜 × 𝐜 𝟎 𝟎 𝟎 𝟎 ) {\bf W}^{1}_{K}\equiv{\bf W}^{1}_{Q}\equiv{\bf 0},\quad{\bf W}_{V}^{1}\equiv\begin{pmatrix}{\bf 0}&{\bf 0}&{\bf 0}\\ {\bf 0}&{\bf I_{c\times c}}&{\bf 0}\\ {\bf 0}&{\bf 0}&{\bf 0}\end{pmatrix}

Above, 𝐖 𝐕 𝟏 {\bf W_{V}^{1}} is meant to isolate the 𝒗 i \bm{v}_{i} embeddings. For the first layer, we then have 𝐐 1 ≡ 𝐊 1 ≡ 𝟎 {\bf Q}^{1}\equiv{\bf K}^{1}\equiv{\bf 0} , and 𝐕 1 [ i , : ] := 𝒖 1 [ i , : ] 𝐖 V 1 ≡ { [ 𝟎 c : 𝒗 i : 𝟎 c ] if  i ∈ 𝒱 , 𝟎 d otherwise , {\bf V}^{1}[i,:]:=\bm{u}^{1}[i,:]{\bf W}_{V}^{1}\equiv\begin{cases}[\bm{0}^{c}:\bm{v}_{i}:\bm{0}^{c}]&\text{if }i\in\mathcal{V},\\ {\bf 0}^{d}&\text{otherwise}\end{cases}, where 𝒦 , 𝒬 , 𝒱 \mathcal{K},\mathcal{Q},\mathcal{V} are defined as in equation 9 . The output for the first layer is given by the following: 𝐎 1 [ i , : ] \displaystyle{\bf O}^{1}[i,:] = ( ( 𝐐𝐊 ⊤ + 𝐁 1 ) 𝐕 ) [ i , : ] \displaystyle=\left(\left({\bf Q}{\bf K}^{\top}+{\bf B}^{1}\right){\bf V}\right)[i,:] = 𝐁 1 𝐕 [ i , : ] \displaystyle={\bf B}^{1}{\bf V}[i,:] = { [ 𝟎 c : 𝒗 i : 𝟎 c ] if  i ∈ 𝒦 𝟎 d otherwise , \displaystyle=\begin{cases}[\bm{0}^{c}:\bm{v}_{i}:\bm{0}^{c}]&\text{if }i\in\mathcal{K}\\ \bm{0}^{d}&\text{otherwise}\end{cases}, The 𝐐𝐊 𝐓 {\bf QK^{T}} is ignored ( ≡ 𝟎 \equiv{\bf 0} ) and we isolate the shifted sequence by setting the bias matrix 𝐁 {\bf B} appropriately. In particular, the last equality follows from the fact that 𝐁 1 {\bf B}^{1} is an up-shift matrix that shifts each row of 𝐕 {\bf V} by 1. We apply the residual connection at the end of the standard Transformer block to insert the 𝒌 i \bm{k}_{i} adjacent to the 𝒗 i \bm{v}_{i} . For the second layer, the input 𝒖 2 ∈ ℝ N × d \bm{u}^{2}\in\mathbbm{R}^{N\times d} is given by 𝒖 2 [ i , : ] ≡ { [ 𝒌 i : 𝒗 i : 𝟎 c ] if  i ∈ 𝒦 [ 𝟎 c : 𝒗 i : 𝟎 c ] if  i ∈ 𝒱 [ 𝟎 c : 𝟎 c : 𝒒 i ] if  i ∈ 𝒬 , \bm{u}^{2}[i,:]\equiv\begin{cases}[\bm{k}_{i}:\bm{v}_{i}:\bm{0}^{c}]&\text{if }i\in\mathcal{K}\\ [\bm{0}^{c}:\bm{v}_{i}:\bm{0}^{c}]&\text{if }i\in\mathcal{V}\\ [\bm{0}^{c}:\bm{0}^{c}:\bm{q}_{i}]&\text{if }i\in\mathcal{Q}\end{cases}, Further, we take the following projection matrices: 𝐖 K 2 ≡ ( 𝐈 c × c 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 ) , 𝐖 Q 2 ≡ ( 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝐈 c × c 𝟎 𝟎 ) , 𝐖 V 2 ≡ ( 𝟎 𝟎 𝟎 𝐈 c × c 𝟎 𝟎 𝟎 𝟎 𝟎 ) {\bf W}^{2}_{K}\equiv\begin{pmatrix}{\bf I}_{c\times c}&{\bf 0}&{\bf 0}\\ {\bf 0}&{\bf 0}&{\bf 0}\\ {\bf 0}&{\bf 0}&{\bf 0}\end{pmatrix},{\bf W}^{2}_{Q}\equiv\begin{pmatrix}{\bf 0}&{\bf 0}&{\bf 0}\\ {\bf 0}&{\bf 0}&{\bf 0}\\ {\bf I}_{c\times c}&{\bf 0}&{\bf 0}\end{pmatrix},{\bf W}^{2}_{V}\equiv\begin{pmatrix}{\bf 0}&{\bf 0}&{\bf 0}\\ {\bf I}_{c\times c}&{\bf 0}&{\bf 0}\\ {\bf 0}&{\bf 0}&{\bf 0}\end{pmatrix} We then have the following matrices as input to attention after applying projection: 𝐐 2 [ i , : ] \displaystyle{\bf Q}^{2}[i,:] : = 𝒖 2 [ i , : ] 𝐖 2 K ≡ { [ 𝒒 i : 𝟎 2  c ] if  i ∈ 𝒬 , 𝟎 d otherwise , \displaystyle:=\bm{u}^{2}[i,:]{\bf W}^{2}_{K}\equiv\begin{cases}[\bm{q}_{i}:\bm{0}^{2c}]&\text{if }i\in\mathcal{Q},\\ {\bf 0}^{d}&\text{otherwise}\end{cases}, (11) 𝐊 2 [ i , : ] \displaystyle{\bf K}^{2}[i,:] : = 𝒖 2 [ i , : ] 𝐖 2 Q ≡ { [ 𝒌 i : 𝟎 2  c ] if  i ∈ 𝒦 , 𝟎 d otherwise , \displaystyle:=\bm{u}^{2}[i,:]{\bf W}^{2}_{Q}\equiv\begin{cases}[\bm{k}_{i}:\bm{0}^{2c}]&\text{if }i\in\mathcal{K},\\ {\bf 0}^{d}&\text{otherwise}\end{cases}, 𝐕 2 [ i , : ] \displaystyle{\bf V}^{2}[i,:] : = 𝒖 2 [ i , : ] 𝐖 2 V ≡ { [ 𝒗 i : 𝟎 2  c ] if  i ∈ 𝒦 ∪ 𝒱 , 𝟎 d otherwise . \displaystyle:=\bm{u}^{2}[i,:]{\bf W}^{2}_{V}\equiv\begin{cases}[\bm{v}_{i}:\bm{0}^{2c}]&\text{if }i\in\mathcal{K}\cup\mathcal{V},\\ {\bf 0}^{d}&\text{otherwise}\end{cases}. Here, note that the values have been shifted to the corresponding key position. Next, we compute the term in the parenthesis for the second layer as ( 𝐐 2  𝐊 2 ⊤ )  [ i , j ] = ( 𝐐 2  𝐊 2 ⊤ )  [ i , j ] \displaystyle\left({\bf Q}^{2}{\bf K}^{2\top}\right)[i,j]=\left({\bf Q}^{2}{\bf K}^{2\top}\right)[i,j] = ⟨ 𝐐 2 [ i , : ] , 𝐊 2 ⊤ [ : , j ] ⟩ \displaystyle=\langle{\bf Q}^{2}[i,:],{\bf K}^{2\top}[:,j]\rangle = ⟨ 𝐐 2 [ i , : ] , 𝐊 2 [ j , : ] ⟩ \displaystyle=\langle{\bf Q}^{2}[i,:],{\bf K}^{2}[j,:]\rangle = { ⟨ 𝒒 i , 𝒌 j ⟩ if  i ∈ 𝒬 , j ∈ 𝒦 0 otherwise \displaystyle=\begin{cases}\langle\bm{q}_{i},\bm{k}_{j}\rangle&\text{if }i\in\mathcal{Q},j\in\mathcal{K}\\ 0&\text{otherwise}\end{cases} = { 1 if  i ∈ 𝒬 , j ∈ 𝒦 , 𝒒 i ≡ 𝒌 j ≡ 𝒆 k  for some k 0 otherwise . \displaystyle=\begin{cases}1&\text{if }i\in\mathcal{Q},j\in\mathcal{K},\bm{q}_{i}\equiv\bm{k}_{j}\equiv\bm{e}_{k}\text{ for some $k$}\\ 0&\text{otherwise}.\end{cases} Finally, we compute the output as follows: 𝐎 2 [ i , : ] \displaystyle{\bf O}^{2}[i,:] = ( ( 𝐐 2 𝐊 2 ⊤ + 𝐁 2 ) 𝐕 2 ) [ i , : ] \displaystyle=\left(\left({\bf Q}^{2}{\bf K}^{2\top}+{{\bf B}^{2}}\right){\bf V}^{2}\right)[i,:] = ( ( 𝐐 2 𝐊 2 ⊤ + 𝟎 ) 𝐕 2 ) [ i , : ] \displaystyle=\left(\left({\bf Q}^{2}{\bf K}^{2\top}+{{\bf 0}}\right){\bf V}^{2}\right)[i,:] = ( 𝐐 2 𝐊 2 ⊤ ) [ i , : ] ⋅ 𝐕 2 \displaystyle=\left({\bf Q}^{2}{\bf K}^{2\top}\right)[i,:]\cdot{\bf V}^{2} = ∑ j = 0 N − 1 ( 𝐐 2 𝐊 2 ⊤ ) [ i , j ] ⋅ 𝐕 2 [ j , : ] \displaystyle=\sum_{j=0}^{N-1}\left({\bf Q}^{2}{\bf K}^{2\top}\right)[i,j]\cdot{\bf V}^{2}[j,:] = ∑ j ∈ 𝒦 ( 𝐐 2 𝐊 2 ⊤ ) [ i , j ] ⋅ [ 𝒗 j : 𝟎 2  c ] \displaystyle=\sum_{j\in\mathcal{K}}\left({\bf Q}^{2}{\bf K}^{2\top}\right)[i,j]\cdot[\bm{v}_{j}:\bm{0}^{2c}] = { [ 𝒗 j : 𝟎 2  c ] if  j ∈ 𝒦 , i ∈ 𝒬 , 𝒒 i ≡ 𝒌 j 𝟎 d otherwise , \displaystyle=\begin{cases}[\bm{v}_{j}:\bm{0}^{2c}]&\text{if }j\in\mathcal{K},i\in\mathcal{Q},\bm{q}_{i}\equiv\bm{k}_{j}\\ \bm{0}^{d}&\text{otherwise}\end{cases}, where we use the fact that for each index j ∈ 𝒦 j\in\mathcal{K} , the matrix 𝐕 2 {\bf V}^{2} contains the associated value from equation 11 . Thus, for each query 𝒒 i \bm{q}_{i} , we solve the associated value problem yielding a match for the j j th key.