- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes "algorithmic capture": a transformer captures a combinatorial task if, after a finite pretraining budget P0 at sizes up to T0, it can reach error at most delta at every larger size T with only C0 log(T/T0) extra fine-tuning samples. It also introduces EPTHS, a distributional heuristic complexity class: a task is in EPTHS of complexity O(T^k) if for every delta some algorithm runs in time eta(1/delta) T^k and is correct with probability above 1 minus delta. The main theoretical result is that the NNGP or NTK predictor of an infinite-width transformer can be estimated by Monte Carlo in O(P N_MC T^3) time. The Kronecker structure of the score covariance gives O(T^3) score sampling, and a Lipschitz analysis of the attention and MLP kernel recursions makes the MC error accumulation T-independent. So a captured task has EPTHS complexity O(T^{3+eps}). Under an assumed P^gamma/N convergence of finite networks to the kernel limit, which is also assumed to hold in the rich regime, this improves to O(T^{2+eps}). The experiments train small finite transformers on induction, vocabulary sorting, 3-token string matching, shortest path, MinCut and CFG recognition, and plot relative adaptation cost P/P0 against T. The first three are read as capture and the last three as non-capture. CFG non-capture is presented as predicted by the theory.
Critical strengths
The kernel-evaluation analysis in Sec. 4.3 and App. A.6 and B is careful and mostly correct. Two parts are what make the O(T^3) per-sample cost work. First, a joint score draw uses the Kronecker factorization Sigma' tensor Sigma' and a Cholesky whitening of the conditional covariance into I tensor I minus H tensor H. Second, the softmax-Jacobian trace terms of the Hron et al. NTK recursion reduce to four T by T matrix products. I re-derived Eqs. 61, 77, 81 and the constants 6, 26, 20 and 176 and got the same results. The max-norm Lipschitz argument showing that MC error does not grow with T is the one non-obvious piece. It is the right tool, because a naive operator-norm argument would pick up powers of T. As a lemma about infinite-width attention kernels, this has value beyond this paper.
The capture definition is a sensible formalization of a vague debate. Fixing the pretraining budget and allowing only logarithmic re-adaptation, motivated by attention dilution and Edelman et al., separates recalibration from relearning. The definition also applies unchanged to CoT and RLVR settings, as the discussion notes. It gives the community a concrete quantity to measure, namely P/P0 against log T, and that framing is likely to outlast the specific bounds.
Critical weaknesses
First, the theory-to-experiment link in the abstract, intro and Fig. 1 is not supported. The paper says the CFG result is "as predicted by our upper EPTHS complexity bound" on p. 5, lines 255 to 256. The Fig. 1 caption on p. 6, lines 297 to 298 says "our theoretical bounds prohibit capture at fixed depth regardless of model capacity". Corollaries 4.7 and 4.11 only say that a captured task has an EPTHS of complexity T^{3+eps} or T^{2+eps}. To conclude non-capture you need a lower bound showing the task, under this specific input measure and with error delta, is not in that class. The paper never proves or cites one.
For CFG, the paper offers no such bound, and the known evidence does not supply one for this setting. Recognition is in O(T^omega) by Valiant's reduction. The strongest known hardness result, Abboud, Backurs and Vassilevska Williams (FOCS 2015), shows that beating Valiant's parser by a polynomial factor, even for constant size grammars, would break the k-Clique hypothesis. That is a conditional, worst-case statement for some grammar. It excludes T^{2+eps} only if omega exceeds 2, and it says nothing about the specific 20-variable grammar or the input measure used here. The paper cites none of this. Under the unconditional Corollary 4.7, cubic CYK is allowed outright. EPTHS is also distributional. The negatives in App. E.1, p. 33, lines 1745 to 1750 come from a single subtree substitution, so the input measure is specific. The paper gives no argument that this measure is hard. App. E.2, line 1798 even lists CFG among "the four capture tasks".
The empirical non-capture claims also rest on T from 10 to 22 for CFG, 10 to 30 for SPP and about 10 to 25 for MinCut, per Fig. 1 d to f. That is too narrow to tell log growth from linear growth. The CFG curves at delta = 10% and at 40% look alike, so the problem is the range, not the threshold. On top of that, SPP and MinCut use a different, non-incremental training protocol from the capture tasks, p. 34, lines 1821 to 1822. The authors concede on p. 5, lines 258 to 259 and p. 9, lines 464 to 468 that SPP and MinCut are allowed by the bounds and need a refined theory. With CFG unsupported, the theory makes no checkable prediction about any of the six experiments.
Second, the strongest bound is either trivial or assumed. Lemma A.1 already shows that any finite transformer runs in O(L H d_model T^2), and the paper itself states the consequence on p. 5, lines 265 to 268. All experiments use finite networks of width 64 to 256, so for them the T^2 statement needs no infinite-width theory. Corollary 4.11 gets T^{2+eps} for infinite width by approximating the kernel limit with a finite network again. This depends entirely on Assumption 4.9. The offered support, Prop. 4.10, covers a different object: the posterior mean of a Langevin-trained network against the NNGP. Assumption 4.9 is about the NTK and gradient flow, yet Corollary 4.11 invokes it for "the lazy or rich regime". A single posterior sample does not approximate f_K, since its predictive variance stays O(1) out of distribution. Footnote 3 on p. 30, line 1619 states that the result does not apply to mean-field scaling. Yet Table 1 and the abstract claim the same bound in the rich regime on the strength of a "reasonable assumption", p. 2, lines 65 to 66. The step in Prop. 4.10 that carries Naveh et al. over to transformers, with T-independent fourth cumulants, is asserted rather than proved, p. 30, lines 1582 to 1587 and 1609 to 1610. What remains rigorous is the lazy-regime T^{3+eps} bound, which is weaker than the trivial finite-width one. The abstract's claim of an "inductive bias that disfavors higher-complexity algorithmic procedures" amounts to the cost of evaluating the predictor, not a bias in what is learned.
Questions for authors
- Can you give any task, input measure and delta for which a lower bound above T^{3+eps}, or above T^{2+eps}, on EPTHS complexity is known? For CFG, can the conditional worst-case hardness of Abboud, Backurs and Vassilevska Williams be transferred to your grammar and to your distribution of positives and single-substitution negatives? Without one, Corollaries 4.7 and 4.11 rule out nothing concrete. If no such task exists, please explain what grounds the CFG claim on p. 5, lines 255 to 256 and p. 6, lines 297 to 298.
- The delta-implementation in Corollary 4.7 needs the C0 log(T/T0) labeled adaptation samples at size T. Producing those labels requires solving g. Is the resulting EPTHS non-uniform, with labeled examples acting as advice? If so, how do you compare it with standard uniform heuristic complexity classes when arguing for non-capture?
- How does Prop. 4.10, which is about the NNGP posterior mean under noisy GD, support Assumption 4.9, which is about NTK convergence of a single trained network? How many posterior samples or ensemble members are needed for the forward-pass surrogate in Corollary 4.11?
- If SPP and MinCut were rerun with the incremental protocol used for the capture tasks, over at least one order of magnitude in T, would the non-capture verdict survive? What does CFG look like over a T range several times wider than 10 to 22?
- Could the kernel spectrum conjecture on p. 9, lines 467 to 468 be turned into a bound that provably separates SPP or MinCut from the captured tasks?
4 comments
Response to Reviewer Z56Y's comments, weaknesses, and questions Part II
- Corollary 4.11 gets for infinite width by approximating the kernel limit with a finite network again. The offered support, Prop. 4.10, covers a different object: the posterior mean of a Langevin-trained network against the NNGP.
Response: Corollary 4.11 is explicitly conditional on Assumption 4.9. Proposition 4.10 addresses the corresponding finite-width approximation question for the NNGP posterior mean, one of the three infinite-width predictors considered in our study; it is not claimed to establish the NTK convergence assumption. Precisely because we address the NNGP case separately, Assumption 4.9 concerns the remaining NTK cases. We have not established analogous cumulant control underlying the expansion in Eq. (138) for those cases and leave this for future work.
- Assumption 4.9 is about the NTK and gradient flow, yet Corollary 4.11 invokes it for "the lazy or rich regime".
Response: We have corrected Assumption 4.9 to include the rich regime. Finite-width corrections in this regime have been studied in the literature at fixed , as we comment one paragraph below; their scaling with and remains part of the assumption.
- A single posterior sample does not approximate , since its predictive variance stays O(1) out of distribution.
Response: We agree with the referee that, for the forward-pass surrogate of the kernel results, an average over independently trained networks is needed, where is the single-network variance. We have added a comment about this to the proof of Corollary 4.11.
Response to Reviewer Z56Y's comments, weaknesses, and questions Part III
- Footnote 3 on p. 30, line 1619 states that the result does not apply to mean-field scaling. Yet Table 1 and the abstract claim the same bound in the rich regime.
Response: Footnote 3 concerns the scope of Proposition 4.10, whose cumulant expansion is restricted to standard scaling. The rich-regime conclusion of Corollary 4.11 does not invoke that proposition; it is conditional on a separately assumed finite-width approximation property for the rich limit. This distinction is now made in Assumption 4.9.
- The step in Prop. 4.10 that carries Naveh et al. over to transformers is asserted rather than proved.
Response: We agree that proofs are always more desirable, but in this complex field one often has to settle for a physics-level argument. On these grounds, all the machinery used in Naveh's work is generic and, at least within standard physics-level rigor, transfers directly to our setting. To make this status explicit, the proof in App. C now states the two inputs taken at this level of rigor.
- The abstract claim of an "inductive bias that disfavors higher-complexity algorithmic procedures" amounts to the cost of evaluating the predictor, not a bias in what is learned.
Response: First we would like to point out that this framing downplays one main aspect of our work -- showing lack of capture despite unlimited expressibility, compute, width, and training resources for the initial () stage. Even when given unbounded resources the lazy (proven ceiling) and rich (conjectured ceiling) would fail to capture any polynomial-complexity task above that ceiling. Treating inductive bias as the set of assumptions, preferences, or built-in rules that a machine learning algorithm uses to predict outputs for unseen data, the preference of some scaling families of transformers not to express a good approximation to the correct algorithm (which they can given their unbounded width) counts as implicit bias.
- Can you give any task, input measure and delta for which a lower bound above , or above , on EPTHS complexity is known?
Response: Please see our response to (1.). To answer directly: we know of no natural task with a proven lower bound of this kind, and we cannot transfer the hardness of Abboud et al. to our grammar and input measure; the CFG statement rests on the hypothesis of the first item. Under standard conjectures our corollaries do exclude concrete tasks, for example planted-clique detection under the planted clique conjecture.
- The delta-implementation in Corollary 4.7 needs the labeled adaptation samples at size T. Producing those labels requires solving g. Is the resulting EPTHS non-uniform, with labeled examples acting as advice?
Response: The -implementation in Corollary 4.7, i.e., , is the kernel predictor. Lines 333-335 in Sec. 4.1 exclude the training complexity, which incorporates data generation, from inference-time complexity.
- How does Prop. 4.10, which is about the NNGP posterior mean under noisy GD, support Assumption 4.9, which is about NTK convergence of a single trained network?
Response: Only by analogy; the sentence in Sec. 4.4 that presented Proposition 4.10 as evidence for Assumption 4.9 has been reworded (see our responses above on Proposition 4.10). On the ensemble size, see our response on the single posterior sample: independently trained networks, polylogarithmic in .
- If SPP and MinCut were rerun with the incremental protocol used for the capture tasks, over at least one order of magnitude in T, would the non-capture verdict survive? What does CFG look like over a T range several times wider than 10 to 22?
Response: Our revised Fig. 1. now uses the incremental protocol over one decade in (from to ) for SPP, MinCut and CFG, showing no signs of capture, as before.
- Could the kernel spectrum conjecture on p. 9, lines 467 to 468 be turned into a bound that provably separates SPP or MinCut from the captured tasks?
*Response: Possibly, but not with what we have. It would require the spectrum of the transformer kernel under , uniformly in , and a proof that the SPP and MinCut targets keep a non-vanishing fraction of their norm outside their leading eigenspaces while the captured targets do not.
Thanks for taking the time to respond. I believe this work can be substantially strengthened in the next round of reviewing. I decided to keep my score as is.
Response to Reviewer Z56Y's comments, weaknesses, and questions Part I
We thank Reviewer Z56Y for their attentive consideration of our paper. We have enumerated Reviewer Z56Y's comments below and will respond to them accordingly.
Response: Reviewer Z56Y rightly points out that saying that “our theoretical bounds prohibit capture” is too strong. Non-capture of the CFG task follows from Corollary 4.11 only under Assumption 4.9 and a further hypothesis which was left unstated in the previous version: for some ϵ>0, the task under our grammar and input measure has no EPTHS of complexity O(T2+ϵ) (Def. 3.2, which now allows advice; see our answer on non-uniformity below). The revised manuscript now states this openly (Sec. 3.4 and App. E.1) and comments on the complexity implications of our hypothesis (e.g. implies ω>2, which is open). Namely, no proof-grade results are claimed with respect to CFG.
Nevertheless, we do stand by the practical content of the claim, and the revision states it explicitly. If a transformer captured this task, Corollary 4.11 would turn it into a T2+ϵ heuristic for it (one can even envision, with today's mechanistic interpretation approaches, that such a capturing instance could be further be turned into an actual RASP algorithm and proved). We know of no such algorithm: for general grammars the fastest known recognizer is Valiant’s O(Tω). While definitely short of a proof, a transformer discovering a better algorithm as part of its next-token prediction seems extremely unlikely. We note that this expectation concerns our specific grammar and input measure, for which the known worst-case results are suggestive only. This merits, in our minds, the statement that "our bound suggests that CFG cannot be captured", which is the formulation now used in the text. Zooming out of this CFG issue, we hope the referee can appreciate the overall aspects of our work: Operationalizing algorithmic understanding using fine-tuning scaling laws, demonstrating that our definition is not empty, linking complexity theory to fine-tuning scaling laws.
Response: Lines 1798-1799 say "For the four capture tasks Induction, Sorting Vocabulary, String Matching, and CFG, we utilized an incremental curriculum for evaluating adaptation costs." This is indeed a typo and the word "capture" has been omitted. The two sentences cited in the first item (lines 255--6 and 296--8) have been reworded as described in our response there.
Response: Our revised Fig. 1. now contains further experiments, extending the range of non-captured tasks up to T=100. Appendix E.3. shows that taking T0 to be twice or four times as large (SPP from T0=20 and 40, MinCut from T0=20) does not alter the picture.
Response: The revised Fig. 1. now reports SPP and MinCut results with an incremental schedule. Regarding checkable predictions: among the six tasks our bound bears on CFG only, under the hypothesis discussed in our response to the first item; for SPP and MinCut the bound is not binding, as stated in the paper and in the new Table 2.
Response: Indeed, a fixed finite transformer has quadratic inference complexity, as we state in Sec. 4. Our infinite-width analysis addresses whether a computational restriction persists when the finite parameter-budget constraint is removed. Lemma A.1 alone cannot answer this question: its evaluation cost depends on width and head count and diverges in the infinite-width limit. Our kernel analysis supplies a finite evaluation procedure with controlled error for the limiting predictor. Under the explicitly stated Assumption 4.9, we further obtain a quadratic exponent since polylogarithmic width then suffices when the adaptation budget grows logarithmically. This is a conditional extension, rather than a consequence of fixing the experimental networks’ widths. The finite-network experiments investigate adaptation scaling in practical models; they are not presented as requiring infinite-width theory to establish their forward-pass cost.