acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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, -gram tables, and conditional-memory modules, and give two results that together settle the question. First, an effective-depth accounting survives Transformer-specific attention branching and an input-keyed multiplicative gate, giving . Second and centrally, we construct a lookup-only recursive-retrieval witness that attains 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 -bit precision the depth weighting saturates at retrieval steps, yet each table entry still realises 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 and scales the witness to keys, checking labels with zero mismatches. A controlled placement study with a frozen backbone is consistent with governing realised capacity, sublinearly, though SGD is not shown to attain the VC ceiling itself.

Primary area:
learning theory
Keywords:
Sample Complexity, Gated Lookup Injection

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_j3mWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2(+1)
Soundness
3
Read review
Paper summary

The paper investigates the statistical estimation costs of multiplication-free table-lookup parameters in transformer models. It shows that these parameters can substantially affect the model's predictive capacity by upper- and lower-bounding the model’s VC dimension. The analysis follows a careful accounting of how the parameters travel through and thus affect the predictions. The authors additionally analyze the effects of model precision and the location where the lookup parameters are injected in the model.

Critical strengths
  • I believe the topic studied in the paper is generally interesting and well-aligned with modern practice in lookup-based computations.
    • I also think the question is quite novel and important.
    • I also appreciate the realistic model (with standard assumptions such as hard attention).
  • To the extent that I was able to check (I am not familiar with the topic and related literature), the claims seem correct and well-posed.
Critical weaknesses
  • The organization and exposition of the paper are quite difficult to follow, from the Abstract to the main theoretical passages. This was my main issue with the paper, as it made it, despite the interesting topic, hard to read and follow.
    • For example, none of the quantities on Lines 18–21 in the Abstract are defined, and it is not clear what those sentences are saying.
      • Similar holds for writing such as “depth weighting saturates at …” (Line 24) and “confirms the precision law” (Line 29).
    • Moreover, on Lines 47–49, the authors say “they answer this”, without specifying what the question is, and it is unclear what the bound O(LWlog⁡(TW))O(LW\log(TW)) is referring to.
    • Similar things occur throughout the Introduction and the paper (undefined quantities in Eq. (11) and other contribution bullet points, etc.)
  • While I don’t think there’s anything inherently wrong with rewriting the draft with AI to fix grammatical errors and improve readability, this text reads like very AI-written (with passages such as Lines 160 and 161, among many others), which I imagine is what led to many undefined quantities and unclear writing as well.
  • While I was able to follow the main results behind the effects of the parameters on the VC dimension, I struggled to grasp the importance of the effects of the precision (Section 5.2). This section, and others in Section 5 as well, seem less motivated, and it’s unclear to me what purpose they serve.
  • Similarly, it is unclear to me what additional value the experiments serve. They are delivered with no introduction and connection to the theoretical part, leaving the reader to infer how they augment the work.
Questions for authors
  1. I am quite unfamiliar with the literature on GLI, and one question I had when I first read the paper (and which I cannot formulate an answer to yet) is: why is it necessarily surprising that non-matrix-multiplicative parameters have the same capacity as other parameters in the model? Classical non-parametric nn-gram models similarly have a large capacity (for large enough nn), so I am not too surprised that they affect the statistical properties of the model. What am I missing?
  2. Do the results change substantially if we allow parameter tying across injection sites?
2 comments

We thank the reviewer for recognising the novelty and practical relevance of the question, and for the frank assessment of the presentation, which we agree with. We have rewritten the affected parts.

Presentation.

  • The abstract is now written in words and contains no undefined quantity. It defines the depth-weighted budget, states both bounds, and states what survives finite precision.
  • The introduction states the research question in its second paragraph: how much does one lookup parameter add to the sample complexity of a Transformer, compared with one ordinary weight?
  • Each contribution bullet defines its quantities (wℓw_\ell, Φ\Phi, ΩΛ\Omega_\Lambda) before using them.
  • Phrases such as "depth weighting saturates" and "confirms the precision law" have been replaced by explicit statements.
  • We revised the prose throughout.

Purpose of Section 5.2 and of the experiments. Section 5.2 now opens with its motivation. Models are trained in 16 or 32 bits, so an exact-arithmetic capacity result is useful only if one knows which part of it survives rounding. The per-parameter capacity of a table entry survives; the placement advantage of the ceiling does not.

Section 7 now opens by distinguishing two kinds of experiment:

  • Verification experiments (7.1, 7.2, 7.4) execute the proofs, so a single error would falsify a theorem.
  • Realisation experiments (7.3, 7.5, 7.6) measure how much of the proven capacity training uses. They are evidence about practice, not about the theorems.

Q1. Why is it surprising? This question led to a sharper statement, which is now in the introduction ("Why the answer is not obvious"). An nn-gram or lookup classifier on its own has small capacity: with KK keys and rows of width pp, it realises at most one label per key, so its VC dimension is at most KK, independent of pp and depth (Proposition 33). Our lower bound shows that the same KpKp entries inside a Transformer realise Θ(pLlog⁡T)\Theta(pL\log T) labels per key, which is the rate of an ordinary weight. The surprise is therefore not that tables have capacity, but that attention multiplies it by pLlog⁡TpL\log T.

New evidence (Section 7.5, Tables 19 and 21):

  • Exact. The witness realises 9 to 936 labels per key, against at most 1 for any attention-free table, with zero mismatches on 17,528 labels.
  • Trained, table only. Without attention, no training set is fitted, which is the nn-gram ceiling. With attention, the memorisation threshold grows with width (8, 64, 192 for p=4p=4, 16, 64) and with depth.
  • Real text, all parameters trained. Adding a table raises the generalisation gap in every corpus at 4M tokens, by up to 136% with an engram table. Lookup parameters are therefore statistically real in practice as well.

Q2. Parameter tying. Yes, and the answer is clean (new Proposition 16, proof in Appendix C). A table shared across all sites in Λ\Lambda is first live at min⁡Λ\min\Lambda. It contributes Kp(L−min⁡Λ+1)Kp(L-\min\Lambda+1) to Φ\Phi, and VC=Θ(Kp(L−min⁡Λ)log⁡T)\mathrm{VC}=\Theta(Kp(L-\min\Lambda)\log T) from the table, independently of ∣Λ∣|\Lambda|. A tied table is thus priced like one untied slice at its first site, with ∣Λ∣|\Lambda| times fewer parameters. The lower bound holds because the hat gates of the witness close every site other than the start layer.

  • Exact. The tied witness has 0 mismatches on 1,120 labels in exact arithmetic.
  • Trained. Tying the table over 0,4,8\\{0,4,8\\} halves the memorisation threshold (1024 to 512) while using a third of the table parameters (Table 20).

We hope the revised presentation now makes the contribution easy to follow, and we thank the reviewer again for the questions, both of which led to new results in the paper.

I thank the authors for the helpful clarifications and, importantly, improvements to the presentation. I have adjusted my score accordingly.

Reviewer_k2MLOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the statistical capacity of gated lookup injection in hard-attention Transformers. The authors introduce the depth-weighted parameter budget Φ=∑ℓwℓ(L−ℓ+1)\Phi = \sum_{\ell} w_{\ell}(L-\ell+1) and prove a VC-dimension upper bound of O(Φlog⁡(TLΦ))O(\Phi\log(TL\Phi)). They then construct a lower-bound example in which all label-dependent information is stored in the lookup tables, obtaining matching depth-weighted capacity within a specified regime. The paper also considers finite precision and table placement, and includes numerical checks of the construction and synthetic memorization experiments. The main analysis uses hard attention and excludes residual-stream normalization.

Critical strengths

For me, the lookup-only lower bound is the most interesting part of the paper. An upper bound would only show that lookup parameters fit within an existing capacity analysis. The construction goes further by showing how a fixed retrieval backbone can actually use the information stored in those entries. I think this gives a clear explanation of why the remaining depth after injection matters.

I appreciate that the authors distinguish the capacity of the constructed model from what gradient-based training actually achieves. The numerical checks, including higher-precision reruns of failing cases, are useful supplements to the proof. The discussion of the placement experiments is also appropriately cautious about confounding and does not claim that SGD reaches the VC bound.

Critical weaknesses

I could not fully follow the finite-precision argument in Appendix C.8. The proof controls round-off in the address register and then applies the exact-arithmetic retrieval lemma. However, the attention scores have the form 2rt−t2+M2rt-t^2+M: their magnitudes can be of order Tc2T_c^2, while the gap between neighboring candidates can remain of constant order. I do not see where the proof controls rounding in these score computations well enough to preserve the argmax. I am also unsure how the bb-bit mantissa assumption in Theorem 10 is reconciled with the total bb-bit parameter encoding required for the WbWb counting bound. These details seem important for the finite-precision claim.

I also have two concerns about Proposition 22. First, the proof counts at most one normalizer per token key and layer, but Eq. (2) uses Hi(0)=TE0(xi)+PE(i)H_i^{(0)} = \mathrm{TE}_0(x_i) + \mathrm{PE}(i). Unless the projection excludes the positional component, the same token at different positions need not have the same normalizer. Second, Eq. (15) uses

LK∣Λ∣≤Kp∑ℓ∈Λ(L−ℓ+1).LK|\Lambda| \le Kp\sum_{\ell\in\Lambda}(L-\ell+1).

Taking Λ=L−1\Lambda=\\{L-1\\} reduces this to LK≤2KpLK\le 2Kp, which fails when L>2pL>2p. These issues may be fixable, and they do not directly affect the unnormalized main theorem, but I do not think the normalization extension is established by the argument as written.

Questions for authors
  1. What exactly is rounded in Theorem 10? Does the model include rounding in the attention-score computations, or only in the stored parameters and address registers? Could you explain how the argmax remains correct under the intended arithmetic model, and how mantissa precision relates to the parameter bit budget in Proposition 12?

  2. Does Proposition 22 assume that the injection projection ignores positional encodings? Also, how should the counting argument be modified for tables placed near the final layers, where Eq. (15) fails? A corrected argument or an explicit statement of the additional assumptions would resolve much of my concern.

3 comments

We thank the reviewer for a precise and expert reading, and for identifying the lookup-only lower bound as the central contribution. Both soundness points are correct. We have repaired both proofs and verified the repairs under exactly the arithmetic model the reviewer described.

Q1. What is rounded in Theorem 10, and why does the argmax survive?

The reviewer is right that the submitted proof controlled round-off only in the address register. The scores 2rt−t2+Mηt2rt - t^2 + M\eta_t have terms of size Θ(T2)\Theta(T^2), while neighbouring candidates differ by a constant. Our submitted precision experiment had the same blind spot, because it rounded only the table entries. The revision makes three changes.

  1. Arithmetic model. Theorem 10 now states it. Every stored value and the result of every elementary operation is rounded to nearest with a bb-bit mantissa: each product, each partial sum of every dot product (including the attention scores), each bias and residual addition, and the attention average. Formally, fl(x∘y)=(x∘y)(1+δ)\mathrm{fl}(x\circ y)=(x\circ y)(1+\delta) with ∣δ∣≤2−b|\delta|\le 2^{-b}, and the exponent range is unbounded.

  2. New Lemma 34 (retrieval with rounded scores). Suppose the register holds s+δ~s+\tilde\delta with ∣δ~∣≤3/8|\tilde\delta|\le 3/8, T≥8T\ge 8 and b≥2log⁡2T+7b\ge 2\log_2 T+7. Then:

    • Positional keys tt and −t2-t^2 are integers below 2b2^b, so they are stored exactly.
    • The exact score of t∗=st^\ast=s exceeds that of any other context position by at least 1−2∣δ~∣≥1/41-2|\tilde\delta|\ge 1/4, and that of any non-context position by at least M−1/4M-1/4.
    • The computed scores differ from the exact ones by at most γ3⋅4T2<1/10\gamma_3\cdot 4T^2<1/10.

    The rounded argmax is therefore exactly {s}\{s\}, no tie can arise, and the head returns the bit and address exactly.

    The register recursion is the submitted one with margin 1/81/8 instead of 1/41/4. We also treat explicitly a ReLU clipping case (δ+ε<0\delta+\varepsilon<0) that the submitted proof omitted. Theorem 10 thus holds under the added hypothesis b≥2log⁡2T+c2b\ge 2\log_2T+c_2 (c2=7c_2=7). The truncation length Bb=⌊(b−c1)/log⁡2(2Tc)⌋B_b=\lfloor (b-c_1)/\log_2(2T_c)\rfloor, the bound (Eq. 8) and the rate of Corollary 13 are unchanged.

  3. Experiment (Section 7.4, Figure 6, Table 18). We evaluate the witness with every operation rounded (sequential accumulation, exact-equality argmax) over 293,340 labels.

    • In all 104 cells with b≥2log⁡2T+6b\ge 2\log_2T+6, the fully rounded witness realises exactly the chain length of the table-only arm.
    • Slopes are within 3% of 1/log⁡2(2Tc)1/\log_2(2T_c).
    • Below that range a new entry threshold appears: 7, 7, 9, 10 and 12 bits at Tc=8,…,128T_c=8,\dots,128. It grows with log⁡Tc\log T_c as the lemma predicts and always lies below the sufficient condition.
    • Executed natively on the GPU, the witness agrees with the emulation in all 20 (format, TcT_c) cells. In particular, native bf16 at Tc≥32T_c\ge 32 realises no chain, although rounding only the table predicts one. This is precisely the score round-off the reviewer identified, and the revised theorem accounts for it.

Q1 (continued). Mantissa bits versus the counting bound.

Proposition 12 now counts mantissa, exponent and sign: VC≤W(b+e+1)\mathrm{VC}\le W(b+e+1). The witness needs exponents only in a range of O(b)O(b) binades, since its nonzero values lie in [β−Bb−1,4T2][\beta^{-B_b-1},4T^2], so e=O(log⁡b)e=O(\log b) suffices. Its ceiling is therefore W(b+O(log⁡b))=Θ(Wb)W(b+O(\log b))=\Theta(Wb), and Corollary 13 matches it up to constants. For IEEE formats with b≥11b\ge 11 one also has e≤be\le b.

Q2. Proposition 22 (now Proposition 23).

Both observations are correct.

  • (i) Position dependence. Eq. (2) feeds TE0(xi)+PE(i)\mathrm{TE}_0(x_i)+\mathrm{PE}(i) into PprojP_{\mathrm{proj}}, so the normaliser can depend on position.
  • (ii) Eq. (15) fails for late tables. For Λ=L−1\Lambda=\\{L-1\\} it requires L≤2pL\le 2p. Our audit finds it violated in 2,606 of 10,296 configurations, by up to a factor of 20 (Appendix H.2).

We replaced the argument with a containment proof that uses no auxiliary variables and needs no inequality of this kind. If the injection input z~i(ℓ)\tilde z^{(\ell)}_i is any function of the token xix_i alone, then the network computes the same function as an unnormalised GLI network with Pproj=0P_{\mathrm{proj}}=0 and table rows E′(ℓ)[x]=z~(ℓ)(x)/sE'^{(\ell)}[x]=\tilde z^{(\ell)}(x)/s. This covers RMS normalisation with a learned gain, and any other token-wise map. That network has the same Λ\Lambda and no more parameters at any layer, so Theorem 6 applies to it with the same (in fact smaller) ΩΛ\Omega_\Lambda, for every Λ\Lambda, including tables near the final layers.

The proposition now states its assumption explicitly: the projection reads the token embedding. This is the deployed design, since Gemma injects positions only through rotary attention. If the projection also reads an additive PE(i)\mathrm{PE}(i), the same argument gives the bound with KK replaced by KTKT, and we state this as well.

Numerical checks (Appendix H.2):

  • The containment holds to 10−1510^{-15} relative error on random networks.
  • The number of distinct normalisers is K∣Λ∣K|\Lambda| when the projection reads the token only, and grows to KT∣Λ∣KT|\Lambda| when it also reads PE\mathrm{PE}.
  • The normalised witness at Λ=L−1\Lambda=\\{L-1\\} for L≤12L\le 12 with p=3p=3, exactly the regime where Eq. (15) failed, has 0 mismatches on 1,116 labels.

Effect on the paper. Neither issue affected the unnormalised upper bound (Theorem 6) or the exact-arithmetic lower bound (Theorem 8). Both repaired results now hold under weaker or more explicit assumptions than before.

Presentation. Following both reviews, the abstract and introduction now define every quantity before using it, and Section 7 separates verification from realisation experiments. Every pre-registered prediction and its outcome is listed in Table 23.

We are grateful for the review: it led to a strictly stronger Theorem 10, whose arithmetic model is fully specified and whose hypotheses are confirmed by hardware execution in four formats. We hope the corrected proofs, together with the verification under the arithmetic model the reviewer described, resolve the soundness concerns, and we would be grateful if the reviewer would consider updating the assessment.

Thank you for the careful revisions. I appreciate that Theorem 10 now accounts for rounding in every operation, including the attention-score computations, and that the normalization result has been replaced with a containment argument covering all table placements. These changes address my main soundness concerns, and I have raised my score accordingly.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We thank both reviewers for careful and constructive reviews. We have uploaded a revised PDF and a new supplement. Numbering below refers to the revised PDF.

Why the question matters. Lookup parameters are now a large and growing share of deployed models, and they are routinely reported as nearly free. In the released Gemma-3n E2B configuration, the per-layer embedding tables hold 2.06B parameters, against 2.36B for the entire backbone including its input embedding. Recent work scales nn-gram tables as an alternative to mixture-of-experts. Model cards now report an "effective" parameter count that excludes such tables. The justification is purely about systems (memory traffic and FLOPs), and no statistical account existed. Our paper gives one: a depth-weighted sample-complexity bound for gated lookup injection, together with a lookup-only construction that attains it. Each table entry is therefore as expensive in capacity as a matrix-multiplied weight. With the corrected proofs below, the released configuration carries 42% of its depth-weighted budget in tables that are never multiplied by another parameter (Section 5.3, Appendix H.6).

Changes in the revision.

  1. Proofs (Reviewer k2ML).
    • Theorem 10 now fixes its arithmetic model explicitly: every stored value and every elementary operation is rounded, including the attention scores. The theorem rests on a new lemma on retrieval with rounded scores (Lemma 34). The saturation rate Θ(b/log⁡T)\Theta(b/\log T) and the bit-matching Corollary 13 keep their rates.
    • The counting ceiling (Proposition 12) now accounts for mantissa, exponent and sign bits.
    • The normalisation result (former Proposition 22, now Proposition 23) is re-proved by a containment argument that holds for every placement.
  2. Exposition (Reviewer j3mW).
    • The abstract and introduction no longer use undefined symbols and state the research question explicitly.
    • A new paragraph explains why the answer is not obvious.
    • Section 5.2 is motivated, and Section 7 now separates experiments that verify proofs from experiments that measure what training achieves.
  3. Two new results answer the reviewers' questions: tables without attention have VC dimension at most KK (Proposition 33, now discussed in the introduction), and tied tables are priced at their first site (Proposition 16).
  4. New experiments (Sections 7.4 to 7.6, Appendix H, about 56 H100-hours). Every prediction was registered before running, and all outcomes are listed in Table 23, including the three that did not hold. The main results:
    • The witness evaluated with every operation rounded, and executed natively in fp32, fp16 and bf16.
    • Numerical checks of the new normalisation proof.
    • Routing and tying, both exact and trained.
    • Language models trained on WikiText-103 and FineWeb-Edu, with token-keyed (PLE-style) and hashed-bigram (engram-style) tables.
    • A knowledge-storage benchmark.
    • Exact accounting for Gemma-3n computed from its released configuration.

Main new empirical findings.

  • Adding a table raises the generalisation gap. At 4M training tokens the gap rises from 6.18 to between 6.26 and 7.59 nats on WikiText-103, from 4.61 to between 5.15 and 6.34 on FineWeb-Edu, and to as much as 14.58 with an engram table.
  • Placement reduces this cost. Moving the same table from layers {0,1,2} to {9,10,11} lowers the gap in all six settings, by 8% to 57%. Parameters, memory and FLOPs are unchanged.
  • Depth after injection is necessary. Table rows injected two layers before the output store no measurable knowledge at any width. The same rows injected early store up to 7.8 bits per person.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.