Theorem 0 — Exact score recovery lower bound

Parent: Research'/maths/outputs/17_attention_output_approximation_new_theorem.txt (PART 0)

Statement (engineering form)

Let keys \(k_1,\ldots,k_m \in \mathbb{R}^d\).

Scores \(s_i(q)=\langle q,k_i\rangle/T\).

Any object \(O\) that allows exact recovery of the full score vector

\((s_1(q),\ldots,s_m(q))\) for all \(q\) in a d-dimensional open set

must encode at least Θ(m d) continuous parameters (for m > d, up to GL(d) ambiguities).

The map \(q \mapsto (s_i(q))_i\) is a rank-d linear map \(\mathbb{R}^d \to \mathbb{R}^m\).

From d independent queries you recover \(Q K^\top\) with \(Q\) invertible ⇒ recover \(K\) up to GL(d).

Free parameters ~ \(md - d^2 = \Theta(md)\).

Cannot promise “tiny O + perfect full attention scores for all queries.”
Early research lines (08–16) that targeted exact score moduli O(d) are false on generic supports.
Correct target shifts to approximate attention output \(A(q)\).

Exact recovery on degenerate low-rank query supports.
Approximate recovery.
Exact reconstruction of K/V from residual if architecture makes them deterministic projections (different problem — KV-Direct class).