Cheap in Memory, Not in Capacity: Depth-Weighted Sample Complexity of Gated Lookup Injection

Lookup tables are treated as “free” parameters because they are indexed rather than used as matrix multiplies. We show they are not free statistically. Working in the tight VC framework for hard-attention Transformers, we study gated lookup injection (GLI), a class covering per-layer embeddings, $n$-gram tables, and conditional-memory modules, and give two results that together settle the question. First, an effective-depth accounting $\Phi ={\sum }_{\ell }{w}_{\ell }(L-\ell +1)$ survives Transformer-specific $T^3$ attention branching and an input-keyed multiplicative gate, giving $\mathrm{VCdim}=O(\Phi \log (TL\Phi ))$. Second and centrally, we construct a lookup-only recursive-retrieval witness that attains $\Omega ({\Omega }_{\Lambda }\log T)$ in the exact-arithmetic tightness window: every capacity-carrying parameter in the construction sits in the table, so indexed entries realise the same statistical capacity rate as ordinary parameters despite never appearing in a matrix multiply. At $b$-bit precision the depth weighting saturates at $\Theta (b/\log T)$ retrieval steps, yet each table entry still realises $\Omega (b)$ bits of capacity, matching the counting ceiling any parameter obeys: the capacity result survives finite precision intact, even though the placement lever collapses. State-keyed lookup admits only a weaker upper bound. Exact experiments verify the construction and branching claims; a GPU implementation confirms the precision law within $2\%$ and scales the witness to $1.3\times 10^5$ keys, checking $449,184$ labels with zero mismatches. A controlled placement study with a frozen backbone is consistent with $\Phi$ governing realised capacity, sublinearly, though SGD is not shown to attain the VC ceiling itself.