Technical Summary: Adaptivity Under Realizability Constraints

Problem Statement

This paper investigates the theoretical limits of in-context learning (ICL) versus agentic learning in the context of uniform approximation for families of functions. The central question is: When does sequential, adaptive interaction with a task provide a genuine advantage over fixed, pre-specified queries, and how does this advantage change when the learning mechanism is constrained by realizability (specifically, implementation via bounded-size ReLU neural networks)?

The authors formalize two axes of comparison:

1. Query Strategy: Fixed queries (In-Context) vs. Adaptive queries (Agentic).
2. Representational Constraint: General functions (unrestricted) vs. ReLU-realizable functions (implemented by bounded-size ReLU networks).

This yields four distinct regimes:

• ICG: General In-Context Learning.
• AG: General Agentic Learning.
• ICR: ReLU-realizable In-Context Learning.
• AR: ReLU-realizable Agentic Learning.

The goal is to characterize the approximation power of these regimes relative to one another under equal sample and computational budgets.

Methodology

The authors adopt a uniform approximation framework over a compact domain $X \subseteq \mathbb{R}^d$. They define a task family $\mathcal{T}$ and measure performance via the worst-case uniform error ($L_\infty$ norm).

Definitions

• In-Context Learner ($\Psi_{IC}$): Uses a fixed set of $N$ query points $x_1, \dots, x_N$ and a predictor that maps the context $C_N = \{(x_i, f(x_i))\}$ and a new input $x$ to a prediction.
• Agentic Learner ($\Psi_{A}$): Selects query points sequentially. The $n$-th query $x_n$ is determined by a map $q_n$ based on the previous context $C_{n-1}$.
• Realizability: A learner is "realizable" if its query maps and final predictor are implemented by ReLU neural networks with a bounded number of weights ($m$).

Comparison Metric

The paper defines a relation $R_1 \leq R_2$ if, for every task family and budget, the worst-case error of regime $R_2$ is no greater than that of $R_1$. Strict inequality ($R_1 < R_2$) indicates a strict advantage.

The authors establish the baseline monotonicity:
$$ICG \leq AG \quad \text{and} \quad ICR \leq AR$$
This holds because an agent can always choose to ignore adaptivity and mimic a fixed query strategy. The core contribution lies in identifying when these inequalities are strict and how realizability alters them.

Key Contributions and Results

The paper isolates four distinct approximation scenarios, each demonstrated by an explicit, constructed task family. These scenarios reveal that the interaction between adaptivity and representational constraints is non-trivial.

1. Adaptivity Reveals More Information (Advantage Survives Realizability)

• Task Family: Cubical-path tasks ($\mathcal{T}^{path}_{d,L}$). Tasks are defined by a nested sequence of dyadic cubes.
• Mechanism: An adaptive agent can perform a binary search (in 1D) or a generalized search to identify the hidden path of cubes level-by-level.
• Result:
  • General: $ICG < AG$. Fixed queries miss information that adaptive queries can sequentially uncover.
  • Realizable: $ICR < AR$. The adaptive strategy (querying centers of child cubes and using residuals) can be implemented exactly by ReLU networks.
• Implication: In this scenario, the information-theoretic advantage of adaptivity is robust to the constraints of ReLU networks.

2. Realizability Generates Adaptivity Advantage

• Task Family: Pointed-value family ($\mathcal{T}^{val}_{N,m}$). Tasks consist of fixed "hats" at known locations carrying coefficients, and a "moving hat" at a location $q^*$ carrying a value $g_m(s)$, where $g_m$ is a hard-to-approximate function.
• Mechanism:
  • General: $ICG = AG$. Both fixed and adaptive learners can read the location $q^*$ from the context and then compute $g_m(s)$ (since they are unrestricted).
  • Realizable: $ICR < AR$. A ReLU in-context learner must internally approximate the hard map $s \mapsto g_m(s)$, which is impossible with bounded weights. However, a ReLU agent can query the value $g_m(s)$ directly at the location $q^*$ (which it determined adaptively), bypassing the need for internal computation.
• Implication: Realizability constraints can create a scenario where adaptivity is strictly superior, even when it offers no advantage in the unrestricted setting.

3. Adaptivity Advantage Removed by Realizability

• Task Family: Address-spike family ($\mathcal{T}^{addr}_{N,m}$). Similar to the pointed-value family, but the location of the moving hat $q^*(s)$ is determined by a hard-to-approximate function $g_m(s)$. The hidden bit $\beta$ is located at $q^*(s)$.
• Mechanism:
  • General: $ICG < AG$. An unrestricted agent can compute $q^*(s)$ from the static coefficients and query the hidden bit.
  • Realizable: $ICR = AR$. To find the informative query point $q^*(s)$, the agent must approximate the hard map $s \mapsto q^*(s)$. Since the agent's query maps are also constrained to be ReLU networks with bounded weights, it cannot compute the location better than the in-context learner. The "hard computation" required to determine where to query negates the benefit of adaptivity.
• Implication: Representational constraints can eliminate the advantage of adaptivity that exists in the general setting.

4. No Advantage

• Scenario: For singleton task families or specific trivial cases, adaptivity yields no improvement ($ICG = AG$ and $ICR = AR$).

Significance and Claims

The paper claims to provide a conceptual classification of how adaptivity interacts with architectural constraints. The primary significance lies in demonstrating that:

1. Adaptivity is not universally superior: Its benefit is contingent on the specific structure of the task family and the computational capabilities of the learner.
2. Realizability is a critical variable: The transition from unrestricted to ReLU-realizable settings does not merely scale performance; it qualitatively changes the relationship between in-context and agentic learning.
   • Advantages can survive (Cubical-path).
   • Advantages can emerge (Pointed-value).
   • Advantages can disappear (Address-spike).

The authors emphasize that these results are derived from worst-case uniform approximation theory, isolating the core phenomena of information acquisition and representational capacity without relying on statistical assumptions or noise models. They further note that their results extend to Transformer architectures via a canonical conversion from ReLU MLPs, suggesting these theoretical limitations apply to modern large language models as well.

The work extends classical results on non-adaptive approximation by MLPs, arguing that the structure of information acquisition (adaptivity) plays a central role alongside function class complexity in determining learning limits.