Define

This piecewise-linear function is continuous. Set \(f(x)=1-\prod _{i=1}^{\ell }(1-g(x[i]))\). If some \(x[i]\geq b\), then one factor is zero and \(f(x)=1\). If every \(x[i]{\lt}a\), every \(g(x[i])\) is zero and \(f(x)=0\).

Because \(S\) is finite, choose pairwise disjoint open balls centered at the points of \(S\). On the ball around \(s\), use a continuous bump function that is \(1\) at \(s\) and \(0\) on the boundary, multiply it by \(y_s\), and set the function to \(0\) outside the union of the balls. The balls are disjoint, so these local definitions agree on overlaps, and the resulting piecewise function is continuous and has the prescribed values on \(S\).

Since \(t\geq 1\), the sentinel row has last coordinate at least \(2\) and is not a binary row. The valid row set is therefore finite with no conflicting prescriptions. Assign \((x,1)\) to each binary row \(x\) and assign \(\tau _t\) to \(s_t\), then apply Lemma 204.

The set of valid rows is finite: it contains the \(2^\ell -1\) nonzero binary vectors and the one special vector \(s_t\). Since \(t+2{\gt}1\), the sentinel row is not binary, so there is no conflict with the document-row prescriptions. Prescribe the displayed value for each valid row and apply Lemma 204. The document-row prescription uses Euclidean normalization, so the inner product of two prescribed document rows is exactly their cosine similarity.

Put \(\lambda \) on the first \(d_{\rm in}\) diagonal entries of \(Q\) and put \(1\) on the corresponding diagonal entries of \(K\), with all other entries zero. Then the matrix product has diagonal entries \(\lambda \) and off-diagonal entries zero.

The attention score from row \(i\) to row \(j\) is \(-\lambda \left\langle v_i,v_j\right\rangle \), so exponentiating it inside softmax gives \(\exp (-\lambda \left\langle v_i,v_j\right\rangle )\). Definition 40 makes the last row exactly \(0^\ell \), so it contributes score \(0\) and hence denominator contribution \(1\). Multiplication by the all-one value column returns \(\| v_j\| _1\) for document rows and \(0\) for the sentinel row, giving the displayed formula for the first \(n\) rows.

Let \(\left\langle v_{i^*},v_{j^*}\right\rangle =0\). The numerator of row \(i^*\) contains the term \(\exp (0)\| v_{j^*}\| _1\). After the preprocessing used in the proof, zero vectors have already been handled, so \(\| v_{j^*}\| _1\geq 1\). The denominator is at most \(n+1\) because every factor \(\exp (-\lambda \left\langle v_{i^*},v_k\right\rangle )\) is at most \(1\). Therefore the row output is at least \(1/(n+1)\).

In a no instance, every document pair has inner product at least \(1\). Hence every numerator weight is at most \(\exp (-\lambda )\), and every \(\| v_j\| _1\) is at most \(\ell \). The numerator is at most \(n\ell \exp (-\lambda )\), while the denominator is at least \(1\) because of the zero sentinel row. The final displayed implication is exactly the assumed upper bound on \(n\ell \exp (-\lambda )\).

Evaluate the transformer on \(\operatorname {Aug}_{0^\ell }(E)\), whose last row is the fixed zero sentinel and whose first \(n\) rows are exactly the OV instance vectors. Choose \(Q,K\) so that \(QK^\top =-\lambda I_\ell \) for a scale \(\lambda {\gt}0\) satisfying \(n\ell \exp (-\lambda ){\lt}1/(2(n+1))\), and choose \(V\) to be the all-one column. Lemma 208 gives the row outputs. By Lemma 209, yes instances produce an entry at least \(1/(n+1)\); by Lemma 210, no instances produce only entries below \(1/(2(n+1))\). The output MLP from Lemma 203, with \(a=1/(2(n+1))\) and \(b=1/(n+1)\), separates these two ranges and outputs \(1\) or \(0\) accordingly.

Lemma 205 maps each binary document row to \(x_i=(v_i,1)\) and maps the fixed raw sentinel row to \(\tau _t=(0,\ldots ,0,t+1)\). Definition 40 ensures that the sentinel is present as the unique \((n+1)\)st row and is not a candidate pair member.

For Max-IP, choose \(QK^\top =\lambda I\) and value vector \((1,\ldots ,1,0)\). If some document pair has inner product at least \(t\), then the shifted score \(\left\langle x_i,x_j\right\rangle \) is at least \(t+1\), matching or exceeding the sentinel score \(\left\langle x_i,\tau _t\right\rangle =t+1\). The best document contribution in that row therefore carries at least a \(1/(n+1)\) softmax fraction and has value at least \(1\). If all document pairs have inner product at most \(t-1\), every document score is lower than the sentinel by at least one, hence by a factor \(\exp (\lambda )\) after exponentiation. The total document value is at most \(n\ell \exp (-\lambda )\), which is below \(1/(2(n+1))\) by the chosen scale.

For Min-IP, choose \(QK^\top =-\lambda I\) and use the same positive target sentinel row \(\tau _t\). A yes witness with \(\left\langle v_i,v_j\right\rangle \leq t\) has shifted score at most \(t+1\), so after negation its exponent is at least the sentinel exponent; a no instance has all shifted document scores at least \(t+2\), so every document exponent is smaller than the sentinel exponent by a factor \(\exp (\lambda )\). The same numerator bound gives the stated gap.

Lemma 212 constructs attention parameters and input MLPs that separate yes and no instances by the numerical gap \(1/(2(n+1)){\lt}1/(n+1)\). Applying the continuous threshold OR of Lemma 203 to the attention outputs gives the required decision value.

There are only finitely many nonzero binary vectors of length \(\ell \), hence only finitely many pairwise cosine-similarity values. If no value lies on the accepting side of the threshold, the finite set of distances from the remaining values to \(t\) has a positive minimum. This minimum is the desired \(\Delta \) for the corresponding maximization or minimization decision.

Expanding the concatenated inner product gives \(\left\langle v/\| v\| ,w/\| w\| \right\rangle +1\), which is \(\left\langle v,w\right\rangle /(\| v\| \| w\| )+1\). The target sentinel has zeros in the document coordinates and last coordinate \(t+1\), while \(x_v\) has last coordinate \(1\), so their inner product is \(t+1\).

Lemma 206 gives exactly the displayed row images, and Definition 40 places the raw sentinel as the unique last row. In a yes instance choose a row \(i\) with some witness row \(j\) whose cosine similarity is at least \(t\), and then choose a document row \(j'\) maximizing the attention score against row \(i\). Its score is at least the sentinel score \(t+1\) by Lemma 215. The value of a nonzero normalized binary row under \((1,\ldots ,1,0)\) is positive and at least \(1\). Since the chosen document row has maximal score among the \(n+1\) rows up to ties with the sentinel, its softmax mass is at least \(1/(n+1)\), so the output is at least \(1/(n+1)\).

In a no instance Lemma 214 gives \(\Delta {\gt}0\) such that every document score is at most \(t+1-\Delta \), whereas the target sentinel score is \(t+1\). The numerator is at most \(n\sqrt{\ell }\exp (\lambda (t+1-\Delta ))\), and the denominator is at least \(\exp (\lambda (t+1))\). Choosing \(\lambda \) so that \(n\sqrt{\ell }\exp (-\lambda \Delta ){\lt}1/(2(n+1))\) gives the claimed no-case bound.

Multiplication by \(-\lambda I_{\ell +1}\) reverses the score order. In a yes instance a witness pair has cosine similarity at most \(t\), so its negated document score is at least the negated target-sentinel score. Choosing the best such document score in the row gives softmax mass at least \(1/(n+1)\) and value at least \(1\), as in Lemma 216.

In a no instance every cosine similarity is at least \(t+\Delta \) for the positive gap from Lemma 214. Thus every negated document score is at most the negated target-sentinel score minus \(\lambda \Delta \). Taking \(\lambda \) large enough makes the total document contribution smaller than \(1/(2(n+1))\), exactly as in the MSD no-case.

For \(t=0\), MSD is trivial on instances with at least two nonzero document rows, so the output MLP may constantly output \(1\). For all other MSD cases, Lemma 216 constructs attention parameters whose outputs have a gap between yes and no instances. For LSD, including the endpoint \(t=0\), Lemma 217 gives the analogous gap with the sign of \(QK^\top \) reversed. Applying the continuous threshold OR of Lemma 203 to the resulting attention-output vector gives the scalar decision value.

The OV part is Theorem 211. The MSD and LSD decision parts are Theorem 218. These constructions use one attention unit plus simple continuous MLPs, with the fixed sentinel row supplied by the input encoding rather than counted as a problem-instance document row.