Proof sketch. Set \(v(x, y) = (y, 1)\), \(k(x, y) = \psi(x)\), \(q(x_t) = \phi(x_t)\), and choose \(\phi, \psi\) so that \(q(x_t)^\top k(x_i, y_i) \approx \log K(x_t, x_i)\). Then the attention weights recover the normalized kernel weights, and a linear decoder extracts the kernel smoother. The full construction and universal approximation argument appear in Appendix 12. ◻

Proof sketch. The GP posterior weight \(w_i = [k(x_t, X_C) \mathbf{K}^{-1}]_i\) depends on the full Gram matrix, coupling all context points. ANP attention weights factor as \(\alpha_i \propto f(x_t, x_i, y_i)\), depending only on query-point pairs independently. The simplest counterexample has \(n=2\): the GP weight on \(y_1\) is \[w_1 = \frac{k(x_t, x_1) k(x_2, x_2) - k(x_t, x_2) k(x_1, x_2)}{k(x_1, x_1) k(x_2, x_2) - k(x_1, x_2)^2},\] which depends on the inter-context kernel value \(k(x_1, x_2)\). No ANP attention weight \(\alpha_1 \propto \exp(q(x_t)^\top k(x_1, y_1))\) can capture this coupling. See Appendix 12 for the general argument. ◻

Proof. By induction: \(H^{(L)} = (\mathbf{I}+ \alpha_L \tilde{\mathbf{K}}) H^{(L-1)} = \prod_{\ell=1}^{L} (\mathbf{I}+ \alpha_\ell \tilde{\mathbf{K}}) H^{(0)}\). ◻

Proof sketch. The argument proceeds in four stages:

(1) Linearization. By Taylor expansion (Lemma 4 in Appendix 14), \(\varepsilon\)-approximation of the linear target implies the Jacobian \(M(X) = \partial F / \partial y_C|_{y_C=0}\) satisfies \(\|M(X) - \mathbf{K}^{-1}\| \leq O(\varepsilon)\).

(2) Polynomial structure. Differentiating through \(L\) self-attention layers shows \(M(X)\) is a matrix polynomial of degree at most \(2L\) in the attention matrix \(\tilde{\mathbf{K}}|_{y_C=0}\) (Appendix 14, Corollary 5).

(3) Univariate reduction. We construct a family of kernel matrices \(\{\mathbf{K}_t\}\) (Lemma 7) where all eigenvalues except the minimum are equal to 1, with condition number \(\kappa\). On this family, the quadratic form \(v_1^\top M(\mathbf{K}_t) v_1\) reduces to a univariate polynomial in the minimum eigenvalue \(\mu_1(t)\).

(4) Chebyshev barrier. The target \(v_1^\top \mathbf{K}_t^{-1} v_1 = 1/\mu_1(t)\) must be approximated by a degree-\(2L\) polynomial on \([1/\kappa, 1]\). The classical Chebyshev lower bound gives error at least \(\Omega(\rho^{2L})\) where \(\rho = (\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)\). Solving for \(L\) yields the stated bound. ◻

Proof of Theorem 1 (CNP Characterization). \((\Rightarrow)\) If \(F \in \mathcal{F}_{\mathrm{moment}}^{(d)}\), then \(F(C, x_t) = \phi(\frac{1}{n}\sum_i \psi(x_i, y_i), x_t)\). Setting \(h = \psi\) and \(g = \phi\) gives exact representation.

\((\Leftarrow)\) If \(F\) is \(d\)-representable, then \(F(C, x_t) = g(\bar{h}_C, x_t)\) for some \(h, g\). This is exactly the form of \(\mathcal{F}_{\mathrm{moment}}^{(d)}\) with \(\psi = h\) and \(\phi = g\). ◻

Proof of Proposition [prop:collisions] (Existence of Collisions). Consider the map \(\Phi: (\mathcal{X}\times \mathcal{Y})^n \to \mathbb{R}^d\) defined by \(\Phi(C) = \frac{1}{n} \sum_{i=1}^n h(x_i, y_i)\). The domain has dimension \(n(d_x + d_y)\); the codomain has dimension \(d\). When \(n(d_x + d_y) > d\), the map cannot be injective, so distinct context sets can have identical representations.

More explicitly, for fixed \(h\)-images \((h_1, \ldots, h_n) \in (\mathbb{R}^d)^n\), perturbations \((\delta_1, \ldots, \delta_n)\) satisfying \(\sum_i \delta_i = 0\) form a subspace of dimension \((n-1)d\). Since \(h\) is continuous and maps from a higher-dimensional space when \(n(d_x + d_y) > d\), generic perturbations in \((\mathcal{X}\times \mathcal{Y})^n\) induce such mean-preserving perturbations in the representation space. ◻

Proof of Theorem 2 (GP Posterior is Not Finitely Representable). The GP posterior mean depends on the inverse Gram matrix \(\mathbf{K}^{-1}\), which couples all context points. The weight on \(y_i\) in the posterior mean depends on all pairwise kernel values \(k(x_i, x_j)\) for \(j \neq i\).

By [prop:collisions], for any encoder \(h\), there exist distinct context sets \(C, C'\) with \(\bar{h}_C = \bar{h}_{C'}\). We construct \(C, C'\) with identical mean encodings but different x-configurations, hence different Gram matrices \(\mathbf{K}(X_C, X_C) \neq \mathbf{K}(X_{C'}, X_{C'})\).

Specifically, with \(n = d+1\) context points, let \(C\) have points \(\{x_1, \ldots, x_{d+1}\}\) in general position and \(C'\) have points \(\{x_1', \ldots, x_{d+1}'\}\) arranged so that \(\bar{h}_C = \bar{h}_{C'}\) (possible by the null space argument) but the pairwise distances differ.

For the same target \(x_t\) and y-values, the GP posterior means differ: \[\mu(x_t | C) = k(x_t, X_C) \mathbf{K}(X_C, X_C)^{-1} y_C \neq k(x_t, X_{C'}) \mathbf{K}(X_{C'}, X_{C'})^{-1} y_C = \mu(x_t | C').\] Thus no CNP with representation dimension \(d\) can exactly represent the GP posterior on contexts of size \(n > d\). ◻

Proof of Theorem 3 (CNP Approximation Lower Bound). We proceed in four steps.

Step 1: Reduction to linear encoders. Since the target \(\mu(x_t | C) = k(x_t, X_C) \mathbf{K}^{-1} y_C\) is linear in \(y_C\) and \(y_C\) is Gaussian, the optimal encoder is linear. This follows from a standard result in Gaussian rate-distortion theory: for jointly Gaussian \((y_C, T(y_C))\) with \(T\) linear, the minimum MSE estimator of \(T(y_C)\) given any function \(\phi(y_C)\) compressed to \(d\) dimensions is achieved by a linear \(\phi\) (see [22] for example).

For fixed context locations, a CNP encoder \(h: \mathcal{X}\times \mathcal{Y}\to \mathbb{R}^d\) reduces to \(\bar{h}_C = \frac{1}{n} \sum_{i=1}^n \phi_i(y_i)\) for functions \(\phi_i: \mathbb{R}\to \mathbb{R}^d\). Linearity gives \(\phi_i(y_i) = a_i y_i\) for some \(a_i \in \mathbb{R}^d\), so \(\bar{h}_C = A y_C\) for a matrix \(A \in \mathbb{R}^{d \times n}\).

Step 2: Whitening. Let \(z = \mathbf{K}^{-1/2} y_C \sim \mathcal{N}(0, \mathbf{I}_n)\). Define: \[\begin{align} \tilde{w}_{x_t} &= \mathbf{K}^{-1/2} k(x_t, X_C) \in \mathbb{R}^n \\ \tilde{A} &= A \mathbf{K}^{1/2} \in \mathbb{R}^{d \times n} \end{align}\] Then \(\mu(x_t | C) = \tilde{w}_{x_t}^\top z\) and \(\bar{h}_C = \tilde{A} z\).

Step 3: Optimal reconstruction. For Gaussian \(z\), the optimal predictor of \(\tilde{w}_{x_t}^\top z\) given \(\tilde{A} z\) is: \[\mathbb{E}[\tilde{w}_{x_t}^\top z | \tilde{A} z] = \tilde{w}_{x_t}^\top P_{\tilde{A}} z\] where \(P_{\tilde{A}} = \tilde{A}^\top (\tilde{A} \tilde{A}^\top)^{-1} \tilde{A}\) is the orthogonal projection onto the \(d\)-dimensional row space of \(\tilde{A}\). The MSE at target \(x_t\) is: \[\mathbb{E}[|\tilde{w}_{x_t}^\top z - \tilde{w}_{x_t}^\top P_{\tilde{A}} z|^2] = \|(\mathbf{I}- P_{\tilde{A}}) \tilde{w}_{x_t}\|^2.\]

Step 4: Integrated error. Define the whitened weight matrix \(\tilde{W} \in \mathbb{R}^{n \times m}\) with columns \(\tilde{w}_{x_1^*}, \ldots, \tilde{w}_{x_m^*}\) for target points \(x_1^*, \ldots, x_m^* \sim \nu\). The total MSE is: \[\sum_{j=1}^m \|(\mathbf{I}- P_{\tilde{A}}) \tilde{w}_{x_j^*}\|^2 = \|(\mathbf{I}- P_{\tilde{A}}) \tilde{W}\|_F^2.\] This is minimized when \(P_{\tilde{A}}\) projects onto the top \(d\) left singular vectors of \(\tilde{W}\). If \(\tilde{W}\) has singular values \(\sigma_1 \geq \cdots \geq \sigma_n\) (with \(\sigma_i = 0\) for \(i > \mathop{\mathrm{rank}}(\tilde{W})\)), the minimum error is \(\sum_{i=d+1}^n \sigma_i^2\) and the total variance is \(\sum_{i=1}^n \sigma_i^2\).

Under the isotropic second moment assumption: \[\frac{1}{m} \tilde{W} \tilde{W}^\top = \frac{1}{m} \sum_{j=1}^m \tilde{w}_{x_j^*} \tilde{w}_{x_j^*}^\top \to \mathbb{E}_{x_t \sim \nu}[\tilde{w}_{x_t} \tilde{w}_{x_t}^\top] = \alpha \mathbf{I}_n\] for some \(\alpha > 0\). Thus the singular values of \(\tilde{W}\) satisfy \(\sigma_i^2 \approx \alpha m / n\) for all \(i \leq n\), giving: \[\frac{\sum_{i=d+1}^n \sigma_i^2}{\sum_{i=1}^n \sigma_i^2} = \frac{n - d}{n} = 1 - \frac{d}{n}. \qedhere\] ◻

Proof. (a) The OLS solution is \(\beta(C) = (\sum_i \psi(x_i)\psi(x_i)^\top)^{-1} (\sum_i y_i \psi(x_i))\). Define the encoder: \[h(x, y) = (\mathop{\mathrm{vech}}(\psi(x)\psi(x)^\top), y \cdot \psi(x)) \in \mathbb{R}^{k(k+1)/2 + k},\] Then \(\bar{h}_C = (\frac{1}{n}\mathrm{vec}(\sum_i \psi(x_i)\psi(x_i)^\top), \frac{1}{n}\sum_i y_i \psi(x_i))\). The decoder can recover \(\beta(C)\) by inverting the (rescaled) Gram matrix and multiplying.

(b) The Gram matrix \(\sum_i \psi(x_i)\psi(x_i)^\top\) has \(k(k+1)/2\) degrees of freedom (symmetric). Different Gram matrices generically yield different predictors. Thus \(d \geq k(k+1)/2 = \Omega(k^2)\). ◻

Proof of Theorem 4 (ANPs Represent Kernel Smoothers). Set:

• Value: \(v(x, y) = (y, 1) \in \mathbb{R}^{d_y + 1}\)

• Key: \(k(x, y) = \psi(x)\) (independent of \(y\))

• Query: \(q(x_t) = \phi(x_t)\)

Choose \(\phi, \psi\) such that \(q(x_t)^\top k(x_i, y_i) = \log K(x_t, x_i)\). If \(\log K\) admits a finite inner product decomposition, this is achieved exactly. For general continuous \(K\) on a compact domain, universal approximation [23] gives networks \(\phi, \psi\) with \(|q(x_t)^\top k(x_i, y_i) - \log K(x_t, x_i)| \leq \delta\) for any \(\delta > 0\), yielding \(\varepsilon(\delta)\)-approximation of the kernel smoother with \(\varepsilon(\delta) \to 0\) as \(\delta \to 0\).

In the exact case, the attention weights are: \[\alpha_i(x_t; C) = \frac{\exp(\log K(x_t, x_i))}{\sum_j \exp(\log K(x_t, x_j))} = \frac{K(x_t, x_i)}{\sum_j K(x_t, x_j)}.\]

The representation is: \[r_C(x_t) = \sum_i \alpha_i(x_t; C) \, (y_i, 1) = \left( \frac{\sum_i K(x_t, x_i) y_i}{\sum_i K(x_t, x_i)}, 1 \right).\]

A linear decoder extracts the first component, which is exactly the kernel smoother. ◻

Proof of Theorem 5 (ANP Characterization). \((\Rightarrow)\) If \(F\) is ANP-representable, the attention mechanism gives exactly this form with \(s(x_t, x, y) = q(x_t)^\top k(x, y) / \tau\).

\((\Leftarrow)\) Any such \(F\) can be implemented by setting \(q(x_t)^\top k(x, y) = s(x_t, x, y) \cdot \tau\) and using an appropriate decoder \(G\). ◻

Proof of Theorem 6 (GP Posterior Requires Context-Context Coupling). The GP posterior mean is: \[\mu(x_t | C) = k(x_t, X_C) \, \mathbf{K}(X_C, X_C)^{-1} \, y_C = \sum_{i=1}^n w_i(x_t; C) \, y_i\] where \(w_i(x_t; C) = [k(x_t, X_C) \mathbf{K}^{-1}]_i\).

The weight \(w_i\) depends on \(\mathbf{K}^{-1}\), which couples all context points. Specifically, \(w_i\) depends on \(k(x_j, x_m)\) for \(j, m \neq i\).

ANP attention weights factor as: \[\alpha_i(x_t; C) = \frac{f(x_t, x_i, y_i)}{\sum_j f(x_t, x_j, y_j)}\] for some function \(f\) depending on query-key pairs independently. The weight on point \(i\) depends only on \((x_t, x_i, y_i)\) and the normalizing constant, not on the relationships between other context points.

Explicit counterexample: Consider \(n = 2\) context points. The GP weight on point 1 is: \[w_1 = \frac{k(x_t, x_1) k(x_2, x_2) - k(x_t, x_2) k(x_1, x_2)}{k(x_1, x_1) k(x_2, x_2) - k(x_1, x_2)^2}.\] This depends on \(k(x_1, x_2)\), the kernel value between the two context points. No ANP attention weight can capture this, as \(\alpha_1 \propto \exp(q(x_t)^\top k(x_1, y_1))\) involves only the query-point-1 relationship. ◻

Proof. Direct computation: \[\beta_{ij} = \frac{\exp(q_s(x_i)^\top k_s(x_j)/\tau)}{\sum_m \exp(q_s(x_i)^\top k_s(x_m)/\tau)} = \frac{\exp(\log K(x_i, x_j) + c)}{\sum_m \exp(\log K(x_i, x_m) + c)} = \frac{K(x_i, x_j)}{\sum_m K(x_i, x_m)}.\] The representation update follows from the definition. ◻

Proof. Set \(W_v^{(1)} = \mathbf{I}\). Then \(h_i^{(1)} = h_i^{(0)} + \sum_j \beta_{ij} h_j^{(0)} = (e_i, y_i) + \sum_j \beta_{ij} (e_j, y_j) = (e_i + \tilde{\mathbf{K}}_{i\cdot}, y_i + \sum_j \beta_{ij} y_j)\). ◻

Proof of Theorem 7 (Polynomial Representation). By induction. For \(L = 1\): \(H^{(1)} = (\mathbf{I}+ \alpha_1 \tilde{\mathbf{K}}) H^{(0)}\). Assuming the result for \(L-1\): \[H^{(L)} = (\mathbf{I}+ \alpha_L \tilde{\mathbf{K}}) H^{(L-1)} = (\mathbf{I}+ \alpha_L \tilde{\mathbf{K}}) \prod_{\ell=1}^{L-1} (\mathbf{I}+ \alpha_\ell \tilde{\mathbf{K}}) H^{(0)} = \prod_{\ell=1}^{L} (\mathbf{I}+ \alpha_\ell \tilde{\mathbf{K}}) H^{(0)}.\] Expanding the product, the coefficient of \(\tilde{\mathbf{K}}^m\) is the sum over all ways to choose \(m\) factors to contribute \(\alpha_\ell \tilde{\mathbf{K}}\) (and the remaining \(L-m\) factors to contribute \(\mathbf{I}\)), which is exactly \(e_m(\alpha_1, \ldots, \alpha_L)\). ◻

Proof. The map \(\alpha \mapsto (e_0(\alpha), \ldots, e_L(\alpha))\) has image determined by Newton’s identities relating elementary symmetric polynomials to power sums. Since \(e_0 = 1\) always, the image lies in the hyperplane \(\{c_0 = 1\}\). Within this hyperplane, the image is the set of coefficient vectors of constant term 1 polynomials with real roots (since \(\prod_\ell(1 + \alpha_\ell z) = \sum_m e_m z^m\) has roots \(-1/\alpha_\ell\)). This is a proper subset of \(\mathbb{R}^L\). ◻

Proof. Standard result from matrix analysis [15]. The truncation error is \(\|(\mathbf{I}- A)^{-1} A^L\| = \|(\mathbf{I}- A)^{-1}\| \|A^L\| \leq \frac{1}{1-\rho(A)} \rho(A)^L\). ◻

Proof. (a) If \(\mathbf{K}v = \lambda v\), then \(Av = (1 - \lambda/\lambda_{\max})v\). Since \(\lambda \in [\lambda_{\min}, \lambda_{\max}]\), the eigenvalues of \(A\) lie in \([0, 1 - \lambda_{\min}/\lambda_{\max}] = [0, 1 - 1/\kappa]\).

(b) \(\mathbf{K}= \lambda_{\max}(\mathbf{I}- A)\), so \(\mathbf{K}^{-1} = \frac{1}{\lambda_{\max}}(\mathbf{I}- A)^{-1}\).

(c) By Lemma 3: \(\|(\mathbf{I}- A)^{-1} - \sum_{m=0}^{L-1} A^m\| \leq \frac{\rho^L}{1 - \rho} = \frac{\rho^L}{1/\kappa} = \kappa \rho^L\). Dividing by \(\lambda_{\max}\): \(\|\mathbf{K}^{-1} - \frac{1}{\lambda_{\max}}\sum_{m=0}^{L-1} A^m\| \leq \frac{\kappa \rho^L}{\lambda_{\max}} = \frac{\rho^L}{\lambda_{\min}}\). ◻

Proof. By Proposition [app:prop:neumann-inverse], the truncated Neumann series \(\hat{\mathbf{K}}^{-1} = \frac{1}{\lambda_{\max}} \sum_{m=0}^{L-1} (\mathbf{I}- \mathbf{K}/\lambda_{\max})^m\) satisfies \(\|\mathbf{K}^{-1} - \hat{\mathbf{K}}^{-1}\| \leq \rho^L / \lambda_{\min}\).

The approximation error in the posterior mean is: \[|\mu_{\mathrm{TNP}} - \mu| = |k(x_t, X_C)(\hat{\mathbf{K}}^{-1} - \mathbf{K}^{-1}) y_C| \leq \|k(x_t, X_C)\| \cdot \|\hat{\mathbf{K}}^{-1} - \mathbf{K}^{-1}\| \cdot \|y_C\|. \qedhere\] ◻

Proof of Proposition [prop:chebyshev-upper] (Chebyshev Upper Bound). Set \[\alpha_\ell = -\frac{2}{\lambda_{\max} + \lambda_{\min} + (\lambda_{\max} - \lambda_{\min})\cos\theta_\ell}, \quad \theta_\ell = \frac{(2\ell-1)\pi}{2L}.\] These are the optimal Chebyshev iteration parameters for inverting a matrix with spectrum in \([\lambda_{\min}, \lambda_{\max}]\). Each \(\alpha_\ell\) is real and negative with \(\alpha_\ell \in (-2/\lambda_{\min}, -2/\lambda_{\max})\), so the polynomial \(p_L(\lambda) = \prod_\ell(1 + \alpha_\ell \lambda)\) satisfies \(p_L(0) = 1\) and has all roots \(-1/\alpha_\ell\) in \([\lambda_{\min}, \lambda_{\max}]\).

The residual polynomial \(r_L(\lambda) = 1 - \lambda \cdot p_L(\lambda)\) is the degree-\(L\) polynomial vanishing at \(0\) that deviates least from \(1\) on \([\lambda_{\min}, \lambda_{\max}]\) in the sup-norm. Standard Chebyshev theory [14] gives \(\|r_L\|_\infty \leq 2\rho^L\) where \(\rho = (\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)\). The stated bound follows from \(\|p_L(\mathbf{K}) - \mathbf{K}^{-1}\| = \|\mathbf{K}^{-1}\| \cdot \|r_L(\mathbf{K})\| \leq \lambda_{\min}^{-1} \cdot 2\rho^L\). ◻

Proof. Let \(M = \frac{\partial F}{\partial y_C}\big|_{y_C = 0}\) and \(T = k(x_t, X_C) \mathbf{K}^{-1}\). For any unit vector \(u\), Taylor expansion gives: \[F(\delta u) = F(0) + \delta \cdot Mu + R(\delta)\] where \(|R(\delta)| \leq \frac{L_2}{2} \delta^2\) by the smoothness assumption.

The target satisfies \(T(\delta u) := k(x_t, X_C) \mathbf{K}^{-1} (\delta u) = \delta \cdot Tu\) (exactly linear).

By the approximation hypothesis: \[|F(\delta u) - \delta \cdot Tu| \leq \varepsilon \quad \text{for all } |\delta| \leq 1.\]

Evaluating at \(\delta = 0\): \(|F(0)| \leq \varepsilon\).

For \(\delta \neq 0\): \[|F(0) + \delta \cdot Mu + R(\delta) - \delta \cdot Tu| \leq \varepsilon\] \[|\delta| \cdot |Mu - Tu| \leq \varepsilon + |F(0)| + |R(\delta)| \leq 2\varepsilon + \frac{L_2}{2}\delta^2.\]

Setting \(\delta = 1\): \[|Mu - Tu| \leq 2\varepsilon + \frac{L_2}{2}.\]

Since \(u\) was an arbitrary unit vector, \(\|M - T\| \leq 2\varepsilon + \frac{L_2}{2}\). ◻

Proof. Differentiating the layer update with respect to \(y_m\) and evaluating at \(y_C = 0\): \[\frac{\partial h_i^{(\ell)}}{\partial y_m} = \frac{\partial h_i^{(\ell-1)}}{\partial y_m} + \sum_j \frac{\partial \beta_{ij}^{(\ell)}}{\partial y_m} W_v h_j^{(\ell-1)} + \sum_j \beta_{ij}^{(\ell)} W_v \frac{\partial h_j^{(\ell-1)}}{\partial y_m}.\]

At \(y_C = 0\), the third term becomes \(\sum_j \tilde{\mathbf{K}}_{ij} W_v B^{(\ell-1)}_{jm}\).

For the attention gradient term, we use the softmax derivative: \[\frac{\partial \beta_{ij}}{\partial y_m} = \beta_{ij} \left( \frac{\partial s_{ij}}{\partial y_m} - \sum_k \beta_{ik} \frac{\partial s_{ik}}{\partial y_m} \right)\] where \(s_{ij} = q(h_i)^\top k(h_j) / \tau\).

The score gradient is: \[\frac{\partial s_{ij}}{\partial y_m} = \frac{1}{\tau} \left[ (\nabla_h q|_{h_i})^\top \frac{\partial h_i}{\partial y_m} \cdot k(h_j) + q(h_i) \cdot (\nabla_h k|_{h_j})^\top \frac{\partial h_j}{\partial y_m} \right].\]

At \(y_C = 0\), \(\frac{\partial h_i^{(0)}}{\partial y_m} = \delta_{im} b(x_i)\), so \(\frac{\partial s_{ij}}{\partial y_m}\big|_{y_C=0}\) is nonzero only when \(m \in \{i, j\}\).

Collecting terms, the attention gradient contribution has the form \(\Gamma^{(\ell)} B^{(\ell-1)}\) where \(\Gamma^{(\ell)}\) depends on \(\tilde{\mathbf{K}}\), query/key gradients, and initial representations—all functions of \(X\) alone. ◻

Proof. By induction on \(L\). The base case \(L = 0\) gives \(B^{(0)} = C_0\) where \([C_0]_{im} = \delta_{im} b(x_i)\) is diagonal.

For the inductive step, Theorem 14 gives: \[B^{(\ell)} = (\mathbf{I}+ \Gamma^{(\ell)}) B^{(\ell-1)} + \tilde{\mathbf{K}} W_v B^{(\ell-1)}\] where \(\Gamma^{(\ell)}\) depends only on \(X\). If \(B^{(\ell-1)}\) is a degree-\((\ell-1)\) polynomial in \(\tilde{\mathbf{K}}\), then \(B^{(\ell)}\) is degree at most \(\ell\). ◻

Proof. Write \(\tilde{\mathbf{K}} = \sum_{k} \mu_k v_k v_k^\top\). Then \(\tilde{\mathbf{K}}^m = \sum_k \mu_k^m v_k v_k^\top\), so: \[u^\top \tilde{\mathbf{K}}^m u = \sum_k \mu_k^m (u^\top v_k)^2.\] For the full polynomial: \[u^\top M u = \sum_{m=0}^{L} u^\top C_m \tilde{\mathbf{K}}^m u = \sum_{m=0}^{L} \sum_{k} \mu_k^m \cdot u^\top C_m v_k \cdot v_k^\top u.\] Expanding \(C_m v_k = \sum_j (v_j^\top C_m v_k) v_j\): \[u^\top M u = \sum_{m=0}^{L} \sum_{j,k} \mu_k^m (v_j^\top C_m v_k)(u^\top v_j)(u^\top v_k).\] Setting \(Q_{jk}(\mu) = \sum_{m=0}^{L} (v_j^\top C_m v_k) \mu_k^m\) gives the result. Each \(Q_{jk}\) has degree at most \(L\) in \(\mu_k\), hence total degree at most \(L\). ◻

Proof. Let \(\{v_1, \ldots, v_{n-1}\}\) be any orthonormal set in \(\mathbf{1}^\perp\), and set \(v_n = \mathbf{1}/\sqrt{n}\). Define: \[K_0 = \frac{1}{\kappa} v_1 v_1^\top + \sum_{j=2}^{n} v_j v_j^\top = I + \left(\frac{1}{\kappa} - 1\right) v_1 v_1^\top.\] Then \(K_0\) is positive definite with eigenvalue \(1/\kappa\) for \(v_1\) and eigenvalue \(1\) for \(v_2, \ldots, v_n\).

Row sums: \(K_0 \mathbf{1} = \mathbf{1} + (1/\kappa - 1) v_1 (v_1^\top \mathbf{1}) = \mathbf{1}\) since \(v_1 \perp \mathbf{1}\).

For \(t \in [0, 1 - 1/\kappa]\), set \(K_t = K_0 + t \cdot v_1 v_1^\top\). Then:

• \(K_t \mathbf{1} = K_0 \mathbf{1} + t \cdot v_1 (v_1^\top \mathbf{1}) = \mathbf{1}\)

• \(K_t v_1 = (1/\kappa + t) v_1\)

• \(K_t v_j = v_j\) for \(j \geq 2\)

The minimum eigenvalue \(1/\kappa + t\) remains below \(1\) for \(t \leq 1 - 1/\kappa\), so \(v_1\) remains the minimum eigenvector throughout. ◻

Proof. By Corollary 5, \(M\) is a sum of terms of the form \(C_0 \tilde{\mathbf{K}}^{m_1} C_1 \cdots C_k\) with \(\sum m_i \leq L\), where each \(C_i\) depends on \(X\) but not on \(y_C\).

For the family \(\mathbf{K}_t\) from Lemma 7, we have \(\tilde{\mathbf{K}}_t = \mathbf{K}_t\) (since \(D_t = I\)) with eigenvalues \(\mu_1(t) = 1/\kappa + t\) and \(\mu_j = 1\) for \(j \geq 2\). The eigenvector \(v_1\) is fixed across the family.

Consider any term \(C_0 \tilde{\mathbf{K}}_t^{m_1} C_1 \tilde{\mathbf{K}}_t^{m_2} \cdots C_k\). Expanding in the eigenbasis \(\{v_1, \ldots, v_n\}\): \[v_1^\top C_0 \tilde{\mathbf{K}}_t^{m_1} C_1 \cdots C_k v_1 = \sum_{j_0, \ldots, j_k} (v_1^\top C_0 v_{j_0})(v_{j_0}^\top \tilde{\mathbf{K}}_t^{m_1} v_{j_1}) \cdots (v_{j_{k-1}}^\top C_k v_1).\] Since \(\tilde{\mathbf{K}}_t^{m} v_j = \mu_j^m v_j\), each factor \(v_{j_{i-1}}^\top \tilde{\mathbf{K}}_t^{m_i} v_{j_i} = \mu_{j_i}^{m_i} \delta_{j_{i-1}, j_i}\). The sum collapses to paths through eigenvector indices.

For indices \(j \geq 2\), we have \(\mu_j = 1\), contributing constant factors. Only paths passing through \(j = 1\) contribute powers of \(\mu_1(t)\). Therefore: \[v_1^\top M(\mathbf{K}_t) v_1 = \sum_{m=0}^{L} c_m \mu_1(t)^m = q(\mu_1(t))\] where the coefficients \(c_m\) depend on the matrices \(C_i\) (hence on network parameters) but not on \(t\). The degree is at most \(2L\) since each of the \(L\) layers contributes at most degree \(2\) due to the quadratic attention gradient terms. ◻

Proof. This is a classical result from approximation theory. The optimal degree-\(L\) polynomial approximation to \(1/\mu\) on \([a,b]\) is achieved by appropriately shifted and scaled Chebyshev polynomials, with the stated error bound. See [14]. ◻

Proof. The matrix \(\tilde{\mathbf{K}} = D^{-1}\mathbf{K}\) is similar to \(\hat{\mathbf{K}} = D^{-1/2} \mathbf{K}D^{-1/2}\): \[D^{1/2} \tilde{\mathbf{K}} D^{-1/2} = D^{-1/2} \mathbf{K}D^{-1/2} = \hat{\mathbf{K}}.\] Thus \(\tilde{\mathbf{K}}\) and \(\hat{\mathbf{K}}\) share eigenvalues, and we analyze the latter via Rayleigh quotients.

Upper bound on \(\kappa(\tilde{\mathbf{K}})\): For any unit vector \(w\), setting \(u = D^{-1/2}w\) gives: \[\frac{w^\top \hat{\mathbf{K}} w}{w^\top w} = \frac{u^\top \mathbf{K}u}{u^\top D u} \in \left[ \frac{\lambda_{\min}(\mathbf{K})}{d_{\max}}, \frac{\lambda_{\max}(\mathbf{K})}{d_{\min}} \right]\] where the bounds follow from \(d_{\min} \|u\|^2 \leq u^\top D u \leq d_{\max} \|u\|^2\). Therefore: \[\kappa(\tilde{\mathbf{K}}) \leq \frac{\lambda_{\max}(\mathbf{K})/d_{\min}}{\lambda_{\min}(\mathbf{K})/d_{\max}} = \gamma \cdot \kappa(\mathbf{K}).\]

Lower bound on \(\kappa(\tilde{\mathbf{K}})\): Let \(v_{\max}\) be the unit eigenvector of \(\mathbf{K}\) with eigenvalue \(\lambda_{\max}(\mathbf{K})\). Evaluating at \(w = D^{1/2}v_{\max}\): \[\lambda_{\max}(\tilde{\mathbf{K}}) \geq \frac{v_{\max}^\top \mathbf{K}v_{\max}}{v_{\max}^\top D v_{\max}} = \frac{\lambda_{\max}(\mathbf{K})}{v_{\max}^\top D v_{\max}} \geq \frac{\lambda_{\max}(\mathbf{K})}{d_{\max}}.\]

Let \(v_{\min}\) be the unit eigenvector of \(\mathbf{K}\) with eigenvalue \(\lambda_{\min}(\mathbf{K})\). Evaluating at \(w = D^{1/2}v_{\min}\): \[\lambda_{\min}(\tilde{\mathbf{K}}) \leq \frac{v_{\min}^\top \mathbf{K}v_{\min}}{v_{\min}^\top D v_{\min}} = \frac{\lambda_{\min}(\mathbf{K})}{v_{\min}^\top D v_{\min}} \leq \frac{\lambda_{\min}(\mathbf{K})}{d_{\min}}.\]

Combining: \[\kappa(\tilde{\mathbf{K}}) = \frac{\lambda_{\max}(\tilde{\mathbf{K}})}{\lambda_{\min}(\tilde{\mathbf{K}})} \geq \frac{\lambda_{\max}(\mathbf{K})/d_{\max}}{\lambda_{\min}(\mathbf{K})/d_{\min}} = \frac{1}{\gamma} \kappa(\mathbf{K}). \qedhere\] ◻

Proof. Since \(\mathbf{K}= D \tilde{\mathbf{K}}\), we have \(\mathbf{K}^{-1} = \tilde{\mathbf{K}}^{-1} D^{-1}\). Thus: \[v_1^\top \mathbf{K}^{-1} v_1 = v_1^\top \tilde{\mathbf{K}}^{-1} D^{-1} v_1 = \frac{1}{\mu_1} v_1^\top D^{-1} v_1 = \frac{\alpha}{\mu_1}\] where the second equality uses \(\tilde{\mathbf{K}}^{-1} v_1 = \frac{1}{\mu_1} v_1\). Since \(D^{-1}\) is positive diagonal and \(v_1 \neq 0\), we have \(\alpha > 0\). ◻

Proof of Theorem 8 (TNP Depth Lower Bound). Step 1: Linearization. By Lemma 4, there exists \(M(X)\) with \(\|M(X) - \mathbf{K}^{-1}\| \leq 2\varepsilon + L_2/2\). For \(\varepsilon\) sufficiently small relative to the fixed architecture constant \(L_2\), this is \(O(\varepsilon)\).

Step 2: Polynomial structure. By Corollary 5, \(M(X)\) has the form: \[M(X) = \sum_{\substack{m_1, \ldots, m_k \geq 0 \\ m_1 + \cdots + m_k \leq L}} C_0(X) \tilde{\mathbf{K}}^{m_1} C_1(X) \cdots C_k(X)\] where each \(C_i(X)\) depends on context locations and network parameters, but not on \(y_C\).

Step 3: Restriction to controlled family. We use the family \(\{\mathbf{K}_t\}\) from Lemma 7 with \(\mu_{\min} = 1/\kappa\) and \(\mu_{\max} = 1\). This family satisfies:

• Condition number \(\kappa(\mathbf{K}_t) = \kappa\) (ratio of largest to smallest eigenvalue is \(1/(1/\kappa) = \kappa\))

• Row-sum ratio \(\gamma = 1\) (since \(D_t = I\))

• Eigenvector coefficient \(\alpha = v_1^\top D_t^{-1} v_1 = \|v_1\|^2 = 1\)

Step 4: Univariate reduction. By Lemma 8, for this family: \[v_1^\top M(\mathbf{K}_t) v_1 = q(\mu_1(t))\] where \(\mu_1(t) = \lambda_{\min}(\tilde{\mathbf{K}}_t)\) and \(q\) is a polynomial of degree at most \(2L\).

Step 5: Target value. By Lemma 10: \[v_1^\top \mathbf{K}_t^{-1} v_1 = \frac{\alpha(t)}{\mu_1(t)} \geq \frac{\alpha_0}{\mu_1(t)}.\]

Step 6: Chebyshev barrier. The approximation requirement \(\|M - \mathbf{K}_t^{-1}\| \leq O(\varepsilon)\) implies: \[\left| q(\mu_1) - \frac{\alpha(t)}{\mu_1} \right| \leq O(\varepsilon) \quad \text{for all } \mu_1 \in [\mu_{\min}, \mu_{\max}].\]

Since \(\alpha(t) \geq \alpha_0\) and \(q\) must approximate \(\alpha(t)/\mu_1 \geq \alpha_0/\mu_1\), Theorem 15 gives: \[\sup_{\mu_1 \in [\mu_{\min}, \mu_{\max}]} \left| q(\mu_1) - \frac{\alpha_0}{\mu_1} \right| \geq \frac{2\alpha_0}{\mu_{\min}(1 + \kappa)} \cdot \rho^L\] where \(\rho = (\sqrt{\kappa} - 1)/(\sqrt{\kappa} + 1)\).

Step 7: Solve for \(L\). For the bound \(O(\varepsilon)\) to hold: \[\frac{2\alpha_0}{\mu_{\min}(1 + \kappa)} \cdot \rho^L \leq O(\varepsilon).\]

Taking logarithms: \[L \geq \frac{1}{\log(1/\rho)} \log\left( \frac{c \alpha_0}{\varepsilon \mu_{\min}(1+\kappa)} \right).\]

Using \(\log(1/\rho) = \log\frac{\sqrt{\kappa}+1}{\sqrt{\kappa}-1} = 2\,\mathrm{arctanh}(1/\sqrt{\kappa}) \approx \frac{2}{\sqrt{\kappa}}\) for large \(\kappa\), and noting that \(q\) has degree at most \(2L\): \[2L \geq \frac{\sqrt{\kappa}}{2} \log\left( \frac{c' \alpha_0}{\varepsilon} \right), \quad \text{hence} \quad L \geq \frac{\sqrt{\kappa}}{4} \log\left( \frac{c' \alpha_0}{\varepsilon} \right)\] for a constant \(c'\) absorbing the \(\mu_{\min}\) and \((1+\kappa)\) factors into the logarithm. ◻

Proof of Theorem 9 (Dimension Scaling), part (c). The GP posterior mean at target \(x_t\) is: \[\mu(x_t | C) = \sum_{i=1}^n w_i(x_t; C) y_i, \quad w_i(x_t; C) = [k(x_t, X_C) \mathbf{K}^{-1}]_i.\]

Encoding strategy: Use initial encoding \(h_i^{(0)} = (e_i, y_i, x_i) \in \mathbb{R}^{n + d_y + d_x}\) where \(e_i\) is a one-hot index vector.

After \(L\) self-attention layers: By Proposition [app:prop:gram-encoding] and the polynomial computation theorem, representations can encode sufficient information about \(\mathbf{K}\) and its powers to approximate \(\mathbf{K}^{-1} y_C\) via the Neumann series.

Cross-attention: With query-dependent attention weights \(\alpha_i(x_t) \propto k(x_t, x_i)\), the cross-attention output is: \[r(x_t) = \sum_i \alpha_i(x_t) h_i^{(L)}.\] If \(h_i^{(L)}\) encodes the \(i\)-th component of \(\mathbf{K}^{-1} y_C\) (call it \(z_i\)), then with \(\alpha_i(x_t) = k(x_t, x_i) / \sum_j k(x_t, x_j)\): \[r(x_t) \approx \frac{\sum_i k(x_t, x_i) z_i}{\sum_j k(x_t, x_j)} = \frac{k(x_t, X_C) \mathbf{K}^{-1} y_C}{\sum_j k(x_t, x_j)}.\] A decoder with access to \(\sum_j k(x_t, x_j)\) (computable via an auxiliary attention head) recovers the unnormalized posterior mean. ◻

Proof of Proposition [prop:convcnp-equivariance] (Translation Equivariance). The functional channels satisfy \(\rho_{C+\tau}(x+\tau) = \sum_i w(x+\tau - x_i - \tau) = \rho_C(x)\), and identically for \(s_{C+\tau}\). Convolution layers commute with translation: for any filter \(\phi\) and translated function \(f_\tau(x) = f(x - \tau)\), \((\phi * f_\tau)(x) = (\phi * f)(x - \tau)\). Pointwise nonlinearities preserve this. By induction over CNN layers, \(\tilde{r}_{C+\tau}(x+\tau) = \tilde{r}_C(x)\). ◻

Proof of Proposition [prop:convcnp-injective] (Injectivity of Convolutional Aggregation). Step 1: Recover locations. Taking Fourier transforms, \(\hat{\rho}_C(\xi) = \hat{w}(\xi) \sum_{i=1}^n e^{-2\pi i \xi \cdot x_i}\). Since \(\hat{w}(\xi) \neq 0\), we recover the characteristic function of the discrete measure \(\mu = \sum_i \delta_{x_i}\), which determines \(\{x_1, \ldots, x_n\}\) as a multiset.

Step 2: Recover values. Given the locations, \(s_C(x_j) = \sum_{i=1}^n w(x_j - x_i)\, h(y_i)\) for \(j = 1, \ldots, n\) is the linear system \(\mathbf{s} = W \mathbf{h}\) with \(W_{ji} = w(x_j - x_i)\). For positive definite \(w\) (e.g.Gaussian) and distinct \(x_i\), \(W\) is a positive definite Gram matrix, hence invertible. Injectivity of \(h\) then recovers \(y_i\). ◻

Proof of Proposition [prop:convcnp-kernel] (Pure ConvCNP Represents Stationary Kernel Smoothers). Set \(w = K\) and \(h(y) = (y, 1) \in \mathbb{R}^{d_y+1}\). Then \(s_C(x_t) = (\sum_i K(x_t - x_i) y_i,\; \sum_i K(x_t - x_i))\) and \(\rho_C(x_t) = \sum_i K(x_t - x_i)\). The decoder \(g(s, \rho, x_t) = s_{1:d_y} / s_{d_y+1}\) extracts the kernel smoother exactly. ◻

Proof. A pure ConvCNP computes: \[F(C, x_t) = g\!\left(\sum_{i=1}^n \frac{w(x_t - x_i)}{\sum_j w(x_t - x_j)}\, h(y_i),\; \rho_C(x_t),\; x_t \right).\] The weight \(\alpha_i(x_t) = w(x_t - x_i)/\sum_j w(x_t - x_j)\) on context point \(i\) depends only on the query–point distance \(x_t - x_i\) and the set of all such distances \(\{x_t - x_j\}_{j=1}^n\). It does not depend on the inter-context distances \(\{x_i - x_j\}_{j \neq i}\).

The GP posterior weight \(w_i(x_t; C) = [k(x_t, X_C)\mathbf{K}^{-1}]_i\) depends on the full Gram matrix \(\mathbf{K}\), which couples all context points. The same two-point counterexample from Theorem 6 applies: the GP weight on \(y_1\) depends on \(k(x_1, x_2)\), which no factorized weight can capture. ◻

Proof. Evaluating the convolution at a context location \(x_i\): \[(\phi_\ell * \tilde{r}^{(\ell-1)})(x_i) = \int \phi_\ell(x_i - x')\, \tilde{r}^{(\ell-1)}(x')\, dx'.\] When \(\tilde{r}^{(\ell-1)}\) is concentrated near the context locations (which holds for localized \(w\)), the integral is dominated by contributions from neighborhoods of each \(x_j\): \[(\phi_\ell * \tilde{r}^{(\ell-1)})(x_i) \approx \sum_{j=1}^n \phi_\ell(x_i - x_j) \int_{B_\delta(x_j)} \tilde{r}^{(\ell-1)}(x')\, dx' \approx \sum_{j=1}^n \delta^{d_x}\, \phi_\ell(x_i - x_j)\, \tilde{r}^{(\ell-1)}(x_j).\] Since \(x_i - x_j\) depends only on the grid displacement \(i - j\), the matrix \([\mathbf{A}_\ell]_{ij} = \delta^{d_x} \phi_\ell(x_i - x_j)\) is Toeplitz. ◻

Proof of Theorem 10 (ConvCNP Depth for GP Posteriors). On a regular grid, \(\mathbf{K}\) is Toeplitz. The Chebyshev iteration \(p_L(\mathbf{K}) = \prod_{\ell=1}^L (\mathbf{I}+ \alpha_\ell \mathbf{K})\) uses parameters \(\alpha_\ell\) as in Proposition [prop:chebyshev-upper]. Each factor \(\mathbf{I}+ \alpha_\ell \mathbf{K}\) is Toeplitz (the sum of identity and a scaled Toeplitz matrix), so each factor is implementable by a single CNN layer with filter \(\phi_\ell(u) = \alpha_\ell K(u) / \delta^{d_x}\) via Proposition [app:prop:cnn-toeplitz].

The first error term is the Chebyshev approximation rate from Proposition [prop:chebyshev-upper]. The \(O(\delta)\) term accounts for discretization of the convolution integral and boundary effects; both vanish as \(\delta \to 0\) for compactly supported contexts.

After \(L\) CNN layers, the representation at each context location \(x_i\) encodes the \(i\)-th component of \(p_L(\mathbf{K}) y_C \approx \mathbf{K}^{-1} y_C\). The readout step recovers the posterior mean \(\mu(x_t | C) = k(x_t, X_C)\mathbf{K}^{-1} y_C\) via convolutional cross-attention with filter \(w = K\). ◻

Proof. We trace the Jacobian through the three stages of the ConvCNP: encoding/aggregation, CNN processing, and readout.

Stage 1: Encoding and aggregation. The signal channel is \(s_C(x_i) = \sum_j w(x_i - x_j)\, h(y_j)\). Its Jacobian with respect to \(y_m\) is: \[\frac{\partial s_C(x_i)}{\partial y_m} = w(x_i - x_m)\, h'(y_m).\] At \(y_C = 0\), this becomes \(w(x_i - x_m) \cdot h'(0)\), the Toeplitz matrix \(W\) with entries \(W_{im} = w(x_i - x_m)\), scaled by \(h'(0)\). On the periodic grid, \(W\) is circulant with DFT \(\hat{w}(k)\).

The density channel \(\rho_C(x_i) = \sum_j w(x_i - x_j)\) is independent of \(y_C\) and hence contributes zero to the Jacobian. Note that \(\rho_C\) is constant across grid locations by translation invariance of the periodic grid: \(\rho_C(x_i) = \rho_0\) for all \(i\).

The constant component \(h(0)\) of the encoder contributes \(\sum_j w(x_i - x_j)\, h(0)\), which is also independent of \(y_C\) and does not affect the Jacobian. Thus only the linear term \(h'(0)\, y\) in the encoder expansion contributes.

Stage 2: CNN processing. At \(y_C = 0\), the signal channel vanishes (its \(y_C\)-dependent part is zero) and the density channel is the spatial constant \(\rho_0\). The CNN input is therefore spatially uniform at \(y_C = 0\).

Consider the \(\ell\)-th layer ?? . Its Jacobian with respect to its input, evaluated at \(y_C = 0\), is: \[J^{(\ell)} = I + D_\ell\, T_\ell,\] where \(T_\ell\) is the circulant matrix of filter \(\phi_\ell\) and \(D_\ell = \operatorname{diag}(\sigma'(\phi_\ell * \tilde{r}^{(\ell-1)}(x_i) + b_\ell)|_{y_C = 0})\). Since the input \(\tilde{r}^{(\ell-1)}|_{y_C=0}\) is spatially uniform (by induction the base case holds as shown above, and each layer preserves spatial uniformity when the input is spatially uniform), the argument of \(\sigma'\) is the same at every location. Thus \(D_\ell = d_\ell I\) for a scalar \(d_\ell \in \mathbb{R}\).

The full CNN Jacobian is \(J_\Phi = \prod_{\ell=1}^{L} (I + d_\ell T_\ell)\). Since each factor is circulant and products of circulant matrices are circulant, \(J_\Phi\) is circulant with DFT: \[\hat{J}_\Phi(k) = \prod_{\ell=1}^{L} (1 + d_\ell\, \hat{\tau}_\ell(k)).\] Each \(\hat{\tau}_\ell(k) = \sum_{|m| \leq \lfloor p/2 \rfloor} \phi_\ell(m\delta)\, e^{-2\pi i k m / n}\) is a trigonometric polynomial of degree at most \(\lfloor p/2 \rfloor\).

Stage 3: Readout. The readout \(g(\tilde{r}_C(x_t), \rho_C(x_t), x_t)\) is evaluated at a single location. On the periodic grid with stationary readout, the Jacobian of the readout with respect to the CNN output is a circulant matrix with DFT \(\hat{g}(k)\). (For the readout structure in Proposition [prop:convcnp-kernel], where \(g\) divides by \(\rho_C\), \(\hat{g}(k)\) is the constant \(1/\rho_0\).)

Composing the three stages by the chain rule gives the stated factorization. ◻

Proof. By Lemma 11, the Jacobian at frequency \(k\) is \(\hat{J}(k) = \hat{g}(k) \cdot (1 + d_1 \hat{\tau}_1(k)) \cdot h'(0) \cdot \hat{w}(k)\). Setting \(\hat{J}(k) = 1/\lambda_k\) and solving: \[\hat{\tau}_1(k) = \frac{1}{d_1}\!\left(\frac{1}{\lambda_k \cdot \hat{g}(k) \cdot h'(0) \cdot \hat{w}(k)} - 1\right).\] This determines \(\hat{\tau}_1(k)\) independently at each of the \(n\) frequencies. With \(p = n\), the DFT \(\phi_1 \mapsto (\hat{\tau}_1(0), \ldots, \hat{\tau}_1(n-1))\) is a bijection on \(\mathbb{C}^n\), so \(\phi_1\) exists and is unique. The solution is well-defined provided \(d_1 \neq 0\) (nonzero activation derivative at \(y_C = 0\), which holds for standard activations like GELU or softplus evaluated at the uniform input), \(h'(0) \neq 0\) (nontrivial encoder, which holds for \(h(y) = (y, 1)\) since \(h'(0) = (1, 0)\)), and \(\hat{w}(k) \neq 0\) for all \(k\) (which holds for positive definite filters such as Gaussians, cf.Proposition [prop:convcnp-injective]). ◻

Proof. Step 1: Linearization. The target \(T(y_C) = \mathbf{K}^{-1} y_C\) is linear. By the same argument as Lemma 4 (applied to the ConvCNP as a map \(\mathbb{R}^n \to \mathbb{R}^n\)), \(\varepsilon\)-approximation of \(T\) implies that the Jacobian \(M = \partial F / \partial y_C|_{y_C = 0}\) satisfies \(\|M - \mathbf{K}^{-1}\| \leq O(\varepsilon)\), where the constant absorbs the smoothness bound \(L_2/2\) which depends on the architecture but not on \(\varepsilon\) or \(\kappa\).

Step 2: Fourier structure. By Lemma 11, \(M\) is circulant with DFT: \[\hat{M}(k) = \hat{g}(k) \cdot \prod_{\ell=1}^{L}(1 + d_\ell\, \hat{\tau}_\ell(k)) \cdot h'(0) \cdot \hat{w}(k).\] Define \(q(\omega) = \prod_{\ell=1}^{L}(1 + d_\ell\, \hat{\tau}_\ell(\omega))\), which is a trigonometric polynomial of degree at most \(D = L \cdot \lfloor p/2 \rfloor\). Then \(\hat{M}(k) = \hat{g}(\omega_k) \cdot q(\omega_k) \cdot h'(0) \cdot \hat{w}(\omega_k)\).

Step 3: Approximation requirement. Since \(M\) and \(\mathbf{K}^{-1}\) are both circulant, \(\|M - \mathbf{K}^{-1}\| = \max_k |\hat{M}(k) - 1/\lambda_k|\). The approximation bound from Step 1 gives: \[\left|\hat{g}(\omega_k) \cdot q(\omega_k) \cdot h'(0) \cdot \hat{w}(\omega_k) - \frac{1}{\lambda_k}\right| \leq O(\varepsilon) \quad \text{for all } k = 0, \ldots, n-1.\] Rearranging, the trigonometric polynomial \(r(\omega) = \hat{g}(\omega) \cdot h'(0) \cdot \hat{w}(\omega) \cdot q(\omega)\) of degree at most \(D + D_0\) (where \(D_0\) is the degree contribution from \(\hat{g}\) and \(\hat{w}\), a fixed constant depending on the kernel and readout) satisfies: \[\left|r(\omega_k) - \frac{1}{\hat{K}(\omega_k)}\right| \leq O(\varepsilon) \quad \text{for all } k.\]

Step 4: From grid to uniform. The trigonometric polynomial \(r(\omega) - 1/\hat{K}(\omega)\) has degree at most \(D + D_0 + D_K\), where \(D_K\) is the degree of the numerator of \(r(\omega) \hat{K}(\omega) - 1\) expressed as a ratio of trigonometric polynomials. A trigonometric polynomial of degree \(N\) with \(|t(\omega_k)| \leq O(\varepsilon)\) at \(n\) equispaced points satisfies \(\|t\|_\infty \leq O(\varepsilon)\) provided \(n > 2N\) (since a trigonometric polynomial of degree \(N\) is determined by \(2N+1\) equispaced samples). The condition \(n > 2L \lfloor p/2 \rfloor\) ensures this (absorbing the fixed contribution \(D_0\) for \(n\) sufficiently large relative to \(D_0\)).

Thus \(r\) is a trigonometric polynomial of degree at most \(D + D_0\) that uniformly \(O(\varepsilon)\)-approximates \(1/\hat{K}(\omega)\) on \([0, 2\pi]\). By Definition 4, \(D + D_0 \geq \mathcal{N}_{O(\varepsilon)}(1/\hat{K})\). Since \(D_0\) is a fixed constant, \(D = L \cdot \lfloor p/2 \rfloor \geq \mathcal{N}_{O(\varepsilon)}(1/\hat{K}) - D_0\), giving \(L \cdot \lfloor p/2 \rfloor \geq \mathcal{N}_{O(\varepsilon)}(c/\hat{K})\) as stated. ◻

Proof. The function \(1/\hat{K}(\omega)\) takes values in \([1/\hat{K}_{\max},\, 1/\hat{K}_{\min}]\). By the substitution \(\mu = \hat{K}(\omega)\), approximating \(1/\hat{K}(\omega)\) in the trigonometric sense reduces to approximating \(1/\mu\) on the interval \([\hat{K}_{\min}, \hat{K}_{\max}]\).

More precisely, let \(t(\omega)\) be any trigonometric polynomial satisfying \(|t(\omega) - 1/\hat{K}(\omega)| \leq \varepsilon\) uniformly. Define \(p(\mu) = t(\hat{K}^{-1}(\mu))\) on any monotone branch of \(\hat{K}\). Then \(|p(\mu) - 1/\mu| \leq \varepsilon\) on \([\hat{K}_{\min}, \hat{K}_{\max}]\). The degree of \(t\) is at least the degree needed for \(p\), which by the classical Chebyshev barrier (Theorem 15) is \(\Omega(\sqrt{\kappa}\,\log(1/\varepsilon))\). (The substitution can increase degree by at most the factor \(\lfloor q/2 \rfloor\), the trigonometric degree of \(\hat{K}\) itself, which is a fixed constant depending on the kernel support.)

Theorem 16 then gives \(L \cdot \lfloor p/2 \rfloor \geq \Omega(\sqrt{\kappa}\,\log(1/\varepsilon))\), yielding the stated bound. ◻

Proof of Theorem 11 (ConvCNPs and ANPs Are Incomparable). \(\mathcal{F}_{\mathrm{ANP}} \not\subseteq \mathcal{F}_{\mathrm{ConvCNP}}\): Let \(\sigma: \mathcal{X}\to \mathbb{R}_+\) be non-constant and define the non-stationary kernel smoother: \[F(C, x_t) = \frac{\sum_i \sigma(x_t)\sigma(x_i) K(x_t - x_i)\, y_i}{\sum_i \sigma(x_t)\sigma(x_i) K(x_t - x_i)}.\] This is ANP-representable by Theorem 4 with non-stationary kernel \(\tilde{K}(x,x') = \sigma(x)\sigma(x')K(x-x')\). However, \(F\) is not translation equivariant: shifting all inputs by \(\tau\) replaces \(\sigma(x_i)\) with \(\sigma(x_i + \tau) \neq \sigma(x_i)\) generically. Since every ConvCNP is translation equivariant (Proposition [prop:convcnp-equivariance]), \(F \notin \mathcal{F}_{\mathrm{ConvCNP}}\).

\(\mathcal{F}_{\mathrm{ConvCNP}} \not\subseteq \mathcal{F}_{\mathrm{ANP}}\): For a stationary kernel, the GP posterior mean is translation equivariant (\(K(x+\tau, x'+\tau) = K(x-x')\) implies invariance of \(\mathbf{K}\) under joint translation). By Theorem 10, a ConvCNP with sufficient CNN depth approximates it to arbitrary precision on grid contexts. By Theorem 6, it is not ANP-representable. ◻

Proof of Theorem 12 (Expressiveness Hierarchy). Part (a): Attention branch.

\(\mathcal{F}_{\mathrm{CNP}}^{(d)} \subseteq \mathcal{F}_{\mathrm{ANP}}^{(d)}\): Set uniform attention weights \(\alpha_i = 1/n\) (achieved by constant query and key functions).

\(\mathcal{F}_{\mathrm{CNP}}^{(d)} \neq \mathcal{F}_{\mathrm{ANP}}^{(d)}\): Kernel smoothers are in \(\mathcal{F}_{\mathrm{ANP}}^{(d)}\) (4) but not in \(\mathcal{F}_{\mathrm{CNP}}^{(d)}\). To see the latter, note that a CNP computes \(F(C, x_t) = g(\bar{h}_C, x_t)\) where \(\bar{h}_C\) is independent of \(x_t\). For the Gaussian kernel smoother with \(n=2\) points, configurations \(C = \{(0, 0), (1, 1)\}\) and \(C' = \{(0.25, 0), (0.75, 1)\}\) can satisfy \(\bar{h}_C = \bar{h}_{C'}\) for appropriate \(h\), yet the kernel smoother outputs differ: at \(x_t = 0\), configuration \(C\) weights the points roughly equally while \(C'\) strongly favors the nearby point \((0.25, 0)\).

\(\mathcal{F}_{\mathrm{ANP}}^{(d)} \subseteq \mathcal{F}_{\mathrm{TNP}}^{(1,d)}\): An ANP is a TNP with \(L=0\) self-attention layers. With \(L=1\) and \(W_v^{(1)} = 0\), we recover ANP.

\(\mathcal{F}_{\mathrm{ANP}}^{(d)} \neq \mathcal{F}_{\mathrm{TNP}}^{(1,d)}\): GP posteriors are in \(\mathcal{F}_{\mathrm{TNP}}^{(L,d)}\) for sufficient \(L\) (Proposition [app:thm:tnp-gp-approx]) but not in \(\mathcal{F}_{\mathrm{ANP}}^{(d)}\) (6).

\(\mathcal{F}_{\mathrm{TNP}}^{(L,d)} \subsetneq \mathcal{F}_{\mathrm{TNP}}^{(L+1,d)}\): The inclusion follows by adding a layer with \(W_v^{(L+1)} = 0\). We prove strictness under Assumptions 1–2 with scalar value weights; the global lower bound of Theorem 8 establishes the corresponding result for representation-based attention at the coarser granularity of \(\Theta(\sqrt{\kappa}\log(1/\varepsilon))\) total layers.

An \(L\)-layer TNP with scalar value weights computes \(p_L(\tilde{\mathbf{K}}) H^{(0)}\) where \(p_L(x) = \prod_{\ell=1}^{L}(1 + \alpha_\ell x)\). The achievable set \(\mathcal{P}_L = \{p_L : \alpha_1, \ldots, \alpha_L \in \mathbb{R}\}\) satisfies \(\mathcal{P}_L \subset \mathrm{Poly}_L\), the space of polynomials of degree at most \(L\).

Let \(\mathbf{K}\) have condition number \(\kappa > 1\) with eigenvalues in \([\lambda_{\min}, \lambda_{\max}]\). The GP posterior requires \(\mathbf{K}^{-1}\), which acts as \(1/\lambda\) on each eigenspace. The minimax error for degree-\(L\) polynomial approximation to \(1/x\) on \([\lambda_{\min}, \lambda_{\max}]\) is \[E_L^* = \inf_{p \in \mathrm{Poly}_L} \sup_{x \in [\lambda_{\min}, \lambda_{\max}]} |p(x) - 1/x| = \Theta\left(\frac{\rho^L}{\lambda_{\min}}\right)\] where \(\rho = (\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)\); see [14]. Since \(\mathcal{P}_L \subset \mathrm{Poly}_L\): \[\inf_{p \in \mathcal{P}_L} \|p(\mathbf{K}) - \mathbf{K}^{-1}\| \geq E_L^*.\]

For the upper bound at depth \(L+1\), Proposition [prop:chebyshev-upper] provides explicit real parameters \(\alpha_1, \ldots, \alpha_{L+1}\) such that \(p_{L+1}(\mathbf{K}) = \prod_{\ell=1}^{L+1}(\mathbf{I}+ \alpha_\ell \mathbf{K})\) satisfies \[\|p_{L+1}(\mathbf{K}) - \mathbf{K}^{-1}\| \leq \frac{2}{\lambda_{\min}}\rho^{L+1}.\] Combining bounds: \[\frac{\inf_{L\text{-layer}} \|p(\mathbf{K}) - \mathbf{K}^{-1}\|}{\inf_{(L+1)\text{-layer}} \|p(\mathbf{K}) - \mathbf{K}^{-1}\|} \geq \frac{E_L^*}{C\rho^{L+1}/\lambda_{\min}} = \Theta(\rho^{-1}) > 1.\] Thus the GP posterior (restricted to accuracy \(\varepsilon\) with \(E_{L+1}^* < \varepsilon < E_L^*\)) lies in \(\mathcal{F}_{\mathrm{TNP}}^{(L+1,d)} \setminus \mathcal{F}_{\mathrm{TNP}}^{(L,d)}\).

Part (b): Convolutional branch.

\(\mathcal{F}_{\mathrm{CNP}}^{(d)} \subsetneq \mathcal{F}_{\mathrm{ConvCNP}}^{(0)}\): Every CNP function is a pure ConvCNP function: set \(w = \mathbf{1}\) (constant filter) to recover mean aggregation \(s_C(x_t) = \sum_i h(y_i)\) with \(\rho_C(x_t) = n\), giving \(F(C, x_t) = g(\frac{1}{n}\sum_i h(y_i), x_t)\). Strictness: stationary kernel smoothers are in \(\mathcal{F}_{\mathrm{ConvCNP}}^{(0)}\) (Proposition [prop:convcnp-kernel]) but not in \(\mathcal{F}_{\mathrm{CNP}}^{(d)}\) for any finite \(d\), since the kernel smoother weight on \(y_i\) depends on \(x_t\) via \(K(x_t - x_i)\), which the query-independent CNP representation cannot capture.

\(\mathcal{F}_{\mathrm{ConvCNP}}^{(0)} \subsetneq \mathcal{F}_{\mathrm{ConvCNP}}^{(1)}\): The inclusion follows by setting the CNN filter to zero. Strictness: consider the one-hop kernel-weighted sum \[F(C, x_t) = \frac{\sum_i K(x_t - x_i) \bigl[\sum_j K(x_i - x_j)\, y_j\bigr]}{\sum_i K(x_t - x_i)}\] which depends on inter-context distances \(K(x_i - x_j)\). A single CNN layer computes this (Proposition [app:prop:cnn-toeplitz]), but a pure ConvCNP cannot represent it: the weight on \(y_j\) in the pure ConvCNP factors as \(\alpha_j(x_t) = w(x_t - x_j)/\sum_m w(x_t - x_m)\), which is independent of all other context locations \(\{x_i\}_{i \neq j}\). The one-hop sum assigns \(y_j\) a weight proportional to \(\sum_i K(x_t - x_i) K(x_i - x_j)\), which couples \(x_j\) to every other context point through the intermediate summation.

\(\mathcal{F}_{\mathrm{ConvCNP}}^{(L)} \subsetneq \mathcal{F}_{\mathrm{ConvCNP}}^{(L+1)}\): The same Chebyshev argument as in Part (a) applies. On regular grids, \(L\) CNN layers compute Toeplitz polynomials of degree \(L\) in \(\mathbf{K}\) (Proposition [app:prop:cnn-toeplitz]). The set of achievable Toeplitz polynomials at degree \(L\) is contained in \(\mathrm{Poly}_L\), so the minimax barrier \(E_L^*\) applies. At depth \(L+1\), the Chebyshev construction of Theorem 10 achieves error \(C \rho^{L+1}/\lambda_{\min}\), giving the same separation ratio \(\Theta(\rho^{-1}) > 1\).

Part (c): Incomparability.

\(\mathcal{F}_{\mathrm{ANP}}^{(d)} \not\subseteq \mathcal{F}_{\mathrm{ConvCNP}}^{(L)}\): Non-stationary kernel smoothers are ANP-representable (Theorem 4) but not ConvCNP-representable at any depth, since every ConvCNP is translation equivariant and non-stationary kernel smoothers generically violate translation equivariance.

\(\mathcal{F}_{\mathrm{ConvCNP}}^{(L)} \not\subseteq \mathcal{F}_{\mathrm{ANP}}^{(d)}\): For \(L \geq 1\), ConvCNPs with CNN layers can approximate GP posteriors for stationary kernels on regular grids (Theorem 10). GP posteriors are not ANP-representable (Theorem 6). For \(L = 0\), stationary kernel smoothers are exactly representable by pure ConvCNPs (Proposition [prop:convcnp-kernel]) but only approximately representable by ANPs (Theorem 4), giving a strict separation in the exact representation sense. ◻

Proof. The latent distribution depends on \(C\) only through \(r_C\). If \(r_C = r_{C'}\), then \(q(z|C) = q(z|C')\). The predictive distribution \(p(y_T | X_T, C) = \int p(y_T | X_T, z) q(z|C) dz\) then coincides for \(C\) and \(C'\). ◻

Proof of Theorem 13, part (a) (Mean Bottleneck). Fix context locations \(X_C\) with \(n\) points in general position for a universal kernel \(k\). Define \(\phi(x_t) = \mathbf{K}^{-1} k(X_C, x_t) \in \mathbb{R}^n\), so the GP posterior mean is \(\phi(x_t)^\top y_C\).

Step 1: Construct target points with independent weight vectors. For a universal kernel, the vectors \(\{\phi(x_t) : x_t \in \mathcal{X}\}\) span \(\mathbb{R}^n\). Choose \(n\) target points \(x_{t_1}, \ldots, x_{t_n}\) such that \(\Phi = [\phi(x_{t_1}), \ldots, \phi(x_{t_n})]^\top \in \mathbb{R}^{n \times n}\) is invertible.

Step 2: Analyze the composite map. Define \(F: \mathbb{R}^k \to \mathbb{R}^n\) by \(F(z) = (f(x_{t_1}, z), \ldots, f(x_{t_n}, z))\). The matching condition requires: \[F(g(X_C, y_C)) = \Phi y_C \quad \forall y_C \in \mathbb{R}^n.\]

Step 3: Dimension argument. Since \(\Phi\) is invertible, the map \(y_C \mapsto \Phi y_C\) is a bijection on \(\mathbb{R}^n\). Thus \(F \circ g: \mathbb{R}^n \to \mathbb{R}^n\) is surjective.

The image of \(g: \mathbb{R}^n \to \mathbb{R}^k\) has dimension at most \(\min(n, k)\). For the composite \(F \circ g\) to be surjective onto \(\mathbb{R}^n\), we need \(\dim(\mathrm{im}(g)) \geq n\), hence \(k \geq n\).

The stochastic case reduces to the deterministic case by considering the low-variance limit \(q(z|C) = \mathcal{N}(m(C), \sigma^2 I)\) as \(\sigma \to 0\). ◻

Proof. From 2 , \(\mathrm{Cov}(y_T | X_T, C) - \sigma^2 I = A(X_T) S(C) A(X_T)^\top\). This matrix has rank at most \(\min(m, k, \mathop{\mathrm{rank}}(S(C))) \leq k\). ◻

Proof. The GP posterior covariance is: \[\tilde{\Sigma}_T = K_{TT} - K_{TC} \mathbf{K}^{-1} K_{CT}\] where \(K_{TT} = [k(x_{t_i}, x_{t_j})]_{ij} \in \mathbb{R}^{m \times m}\), \(K_{TC} = [k(x_{t_i}, x_j)]_{ij} \in \mathbb{R}^{m \times n}\), and \(K_{CT} = K_{TC}^\top\).

This is the Schur complement of \(\mathbf{K}\) in the joint covariance matrix: \[\begin{pmatrix} \mathbf{K}& K_{CT} \\ K_{TC} & K_{TT} \end{pmatrix}.\]

For a universal kernel, this joint matrix is positive definite when all \(n + m\) points are distinct. The Schur complement of a positive definite block in a positive definite matrix is positive definite. Thus \(\tilde{\Sigma}_T \succ 0\), which implies \(\mathop{\mathrm{rank}}(\tilde{\Sigma}_T) = m\). ◻

Proof. The GP posterior covariance (minus observation noise) has rank \(m\) by Theorem 18. The latent NP predictive covariance (minus observation noise) has rank at most \(k\) by Theorem 17. For \(m > k\), exact matching is impossible. ◻

Proof of Theorem 13 (Latent NP Cannot Represent GP Posterior). Part (a) is proven above (Mean Bottleneck). Part (b) is Corollary 8. Part (c) follows from (b) since we can choose arbitrarily many target points. ◻

Proof. \((\Rightarrow)\) A Gaussian latent NP with linear decoder \(f(x, z) = a(x)^\top z + b(x)\) and latent \(z | C \sim \mathcal{N}(m(C), S(C))\) induces: \[\begin{align} \mathbb{E}[f(x) | C] &= a(x)^\top m(C) + b(x) \\ \mathrm{Cov}(f(x), f(x') | C) &= a(x)^\top S(C) a(x') \end{align}\] which is a rank-\(k\) GP.

\((\Leftarrow)\) Any rank-\(k\) GP with mean \(\mu(x) = a(x)^\top m + b(x)\) and covariance \(\tilde{k}(x, x') = a(x)^\top S a(x')\) is realized by setting the latent distribution to \(\mathcal{N}(m, S)\) and decoder to \(f(x, z) = a(x)^\top z + b(x)\). ◻