← Proof Notes
Counterexample / Transformers & in-context learning

Failure of the L∞ approximation lemma

Big Bird: Transformers for Longer Sequences ↗

3,071 citations ↗Semantic Scholar · 2026-09-09

2020 · v2 · Reviewed 09 September 2026

An explicit example contradicts the selected statement as written.

Paper context

Overview

Big Bird introduces sparse attention that combines local, random and global connections so that attention costs grow linearly with sequence length when the number of connections per token is fixed. The paper argues that this design retains key expressive and computational properties of full attention, and evaluates its longer context on language and genomics tasks.

Role of the theoretical result

Lemma 5 transfers a construction using hard attention and piecewise activations to ordinary softmax/ReLU networks. Its asserted infinity-norm case supports the appendix’s worst-case approximation argument; the counterexample concerns this transfer, rather than the finite-p main theorem or the experiments.

Original paper ↗

01 / Summary

Summary of the result

Lemma 5 includes the L∞ endpoint in an approximation result whose intermediate class permits discontinuous activations. Every finite softmax/ReLU transformer is continuous. A unit jump therefore imposes an L∞ error of at least 1/2, independently of network size or parameter magnitude. The finite-p approximation argument remains compatible with this example because the measure of the transition region can tend to zero. The objection concerns the endpoint of the supporting lemma and its use in the appendix.

02 / Statement

Statement under review

Appendix A.2.3, Lemma 5: arXiv v2 PDF page 21; published NeurIPS supplement PDF page 5 (printed page 20). · paraphrased

Every network in the modified hardmax/piecewise-linear class can be approximated arbitrarily accurately by an ordinary softmax/ReLU transformer, including at p=infinity.

∀gˉ∈T‾2,1,1,1≤p≤∞:∃g∈T2,1,4,dp(g,gˉ)≤ε/3.\forall\bar g\in\overline{\mathcal T}^{2,1,1},\quad 1\le p\le\infty:\quad\exists g\in\mathcal T^{2,1,4},\quad d_p(g,\bar g)\le\varepsilon/3.
Relevant assumptions ↘
  • The modified class permits hardmax and piecewise-linear activations with discontinuities, inherited from the cited Yun et al. construction.
  • The ordinary network has finite weights and finitely many softmax/ReLU layers, so its output is continuous on the compact input cube.
  • The selected claim includes p=infinity. The main-text Theorem 1 instead states 1<p<infinity.

03 / Derivation

Counterexample and derivation

4 steps · complete derivation
  1. 01

    Choose an allowed jump

    Disable attention by setting its value/output weights to zero. A width-one modified feed-forward residual layer can add a step in one input coordinate. Along that coordinate its output is x plus the indicator of x>1/2.

    gˉ1(X)=X11+1{X11>1/2}.\bar g_1(X)=X_{11}+\mathbf 1\{X_{11}>1/2\}.
  2. 02

    Use continuity of the approximant

    Fix the other input coordinates in the interior of the cube. The first coordinate of any finite ordinary transformer has the same limit from the left and right at x=1/2. Call this common value c. The target limits are 1/2 and 3/2.

    max⁡{∣c−1/2∣,∣c−3/2∣}≥1/2.\max\{|c-1/2|,|c-3/2|\}\ge 1/2.
  3. 03

    The essential supremum also fails

    For any proposed error strictly below 1/2, one side of the jump has error above that threshold. Continuity on that open side gives an open set of inputs with the same failure. Thus the obstruction has positive measure; it is not just the value assigned at the discontinuity.

    d∞(g,gˉ)≥1/2.d_\infty(g,\bar g)\ge 1/2.
  4. 04

    Separate the endpoint from finite p

    A transition region of width delta can have finite-p error tending to zero as delta shrinks. That argument does not make the maximum error vanish.

    ∥eδ∥p=O(δ1/p)  (p<∞),∥eδ∥∞≥1/2.\|e_\delta\|_p=O(\delta^{1/p})\ \ (p<\infty),\qquad\|e_\delta\|_\infty\ge 1/2.

Counterexample

For ε=1, Lemma 5 requires an approximation error at most 1/3. The discontinuous target has distance at least 1/2 from every continuous approximant in the uniform norm.

gˉ(x)=x+1{x>1/2},inf⁡g∈C([0,1])∥g−gˉ∥∞≥12>13.\bar g(x)=x+\mathbf1\{x>1/2\},\qquad\inf_{g\in C([0,1])}\|g-\bar g\|_\infty\ge\frac12>\frac13.
Numerical illustration

Uniform and integrated approximation error

0.00.51.0
Worst-case error0.500
Integrated absolute error0.100

The solid curve is a continuous ramp approximating a unit step (dashed). A narrower ramp reduces the area of error. It never removes the half-unit error beside the jump. This illustrates the obstruction; the proof applies to every continuous approximant.

Horizontal axis: x from −1 to 1. Vertical axis: function value.

04 / Implications

Implications and proposed correction

Theoretical implications

Affected result

Refutes the infinity endpoint of Lemma 5 and invalidates that intermediate-network approximation route to the appendix endpoint theorem. It does not refute uniform universality for continuous target functions proved by a different construction.

Empirical scope

Relation to reported experiments

No experimental result, training run, or implementation benchmark was re-evaluated by this counterexample.

Proposed correction

Sufficient conditions and revised bound

Restrict the modified-to-ordinary approximation lemma to finite p. For a uniform approximation theorem on continuous targets, supply a separate construction that controls the transition regions in the uniform norm. The cited Yun et al. Lemma 9 explicitly has p<infinity. Its finite-p smoothing argument permits error on sets whose measure tends to zero.

Implementation implications

No code change follows from the finite-p repair. Uniform-error promises require a continuous target and an appropriate uniform-error analysis.

Limits of this review

  • Only one supporting lemma is refuted.
  • The continuous-target endpoint theorem could have another proof.
  • The witness uses the modified activation class, not a discontinuity in the deployed softmax/ReLU architecture.

05 / References

Sources and correction history

  1. 01
    Big Bird, arXiv v2 ↗

    Lemma 5 and Appendix Theorem 2, PDF p.21; main Theorem 1, PDF p.4

  2. 02
    Published NeurIPS supplement ↗

    Lemma 5, PDF p.5 / printed p.20

  3. 03
    Yun et al., Are Transformers Universal Approximators? ↗

    Modified activation class, PDF p.5; finite-p Lemma 9, PDF p.14

  4. 04
    Sumformer: Universal Approximation of Permutation Equivariant Functions ↗

    Section 4.2 and Appendix B: separate finite-p and continuous-target uniform constructions

  5. 05
    Author repository public issues ↗

    Open and closed issue history

Download the arithmetic witnesses · Python, no dependencies ↓
Correction search · 09 September 2026

2026-09-09 Fresh arXiv submission history: latest v2, 8 January 2021. Re-read and visually inspected the archived v2 lemma; checked the published supplement in the earlier audit. Targeted exact-title, Lemma 5, uniform-approximation, infinity, correction and erratum searches refreshed for publication. Prior same-day repository audit inspected all 36 issue/PR records and 41 comments. A fresh API refresh hit the GitHub rate limit. Read the cited Yun finite-p boundary and Sumformer uniform-approximation treatment; neither makes the arbitrary discontinuous-target lemma true. No addressing source for this exact endpoint statement was found in the documented search. This is a bounded search, not evidence that nobody has noticed the issue. The repository refresh was rate-limited.

A bounded search is not evidence of priority or proof that no correction exists.

Entirely AI-generated analysis, including cross-checks by separate AI agents; no independent human verification. Authors have not been contacted. Review standard.

Suggest a correction with a source ↗
Next analysisInsufficient radius control in perturbed gradient descent