- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper examines whether an unusually simple attention model (two-token inputs and scalar Q/K/V) can still be difficult to train. It shows that determining whether the model can exactly fit a given dataset is NP-hard in the worst case. This hardness also extends to casual attention.
Critical strengths
- Theoretically solid paper which investigates an interesting problem.
- Within my (limited) capacity, I find no flaws in the proofs.
Critical weaknesses
- Its impact on practice is limited. The work targets an unusually small attention module (scalar projections and two-token sequences) and is based on worst-case scenarios.
Questions for authors
- Can the authors conduct simple (e.g., synthetic) experiments to validate their conclusions? I believe this can improve the paper's quality. For example, show the existence of hardness in a realistic setting.
- Can the authors state the potential utility of this work beyond filling a theoretical blank?
5 comments
Deducing interesting consequences (W1, Q2)
Consequences for fitting and training (Reply 2)
W1. Its impact on practice is limited. The work targets an unusually small attention module (scalar projections and two-token sequences) and is based on worst-case scenarios.
We chose the minimal module to isolate the first nontrivial token interaction: one-token fitting is linear, whereas two tokens and scalar projections already suffice for hardness. Minimality also helps us understand the mechanism by isolating the roles of the query, key and value matrices. For example, freezing different matrices lets us examine how the choice of learned matrices affects fitting complexity and training behavior (Q2 below). Our softmax and hardmax hardness theorems hold for every fixed positive key and value dimension, with the larger weight matrices fully trainable. Ambient dimension and sample count grow with the source instance. Appendix J also extends scalar softmax QV/QKV hardness to every fixed length , with exactly tokens per sample, a common final token and final-output supervision. The experiments cover lengths two to five and key dimensions one, two and four.
In the softmax proof, additive value constraints and multiplicative attention-odds constraints force globally consistent Boolean choices. The worst-case construction explains fitting difficulty and generates datasets whose input and target structure we can vary. Reply 1 uses these datasets to study Adam training, including joint QKV training. Theorem 6 also establishes a fixed positive gap in mean squared loss per sample, with bounded inputs and targets, so hardness persists beyond exact fitting.
Q2. Can the authors state the potential utility of this work beyond filling a theoretical blank?
For example, consider freezing the key weight matrix in the construction in Proposition 2. Completeness already uses the same prescribed key matrix for every satisfying assignment, so the same reduction proves hardness when only Q and V are learned. On common-reference two-token inputs with final-output supervision, prescribing V instead permits polynomial-time fitting. Which matrix is supplied matters even when the number of learned matrices stays the same.
Appendix H gives the following exact-feasibility comparison for one scalar softmax head. Inputs are rational pairs sharing a nonzero , plus duplicate pairs . Targets and prescribed matrices are rational, and learned matrices have finite real entries. P means polynomial time in the binary input length. Columns list learned weight matrices. All remaining matrices are prescribed. Both-output supervision is unmasked.
| Supervision | Learn Q,K | Learn Q,V | Learn Q,K,V | Learn any one weight matrix |
|---|---|---|---|---|
| Final output only | P | NP-hard | NP-hard | P |
| Both outputs, targets | P | NP-hard | NP-hard | P |
| Both outputs, arbitrary targets | NP-hard | NP-hard | NP-hard | P |
The QK column shows that changing repeated full targets to arbitrary full targets changes the classification from P to NP-hard. Under the paper's score convention, a common final token gives scores through . For two-token final-output fitting, unequal prescribed values determine the required attention probabilities, whose log-odds give consistency equations. Equal-value cases are checked directly. QKV has the same score representation and also learns values, retaining their coupling. In scalar KV fitting, the supplied query fixes the score direction and K learns its multiplier. V-only fixes the attention features and gives linear least squares. For final-output supervision, Appendix J gives polynomial-time KV fitting when prescribed query-score differences lie on a rational grid with polynomially bounded within-sample integer span. General KV fitting on the two-token family remains open.
Reply 3 discusses what the input, target and supervision controls reveal about the construction's empirical implications.
Ablation study
Further interpretation and implications of control experiments / ablation studies (Reply 3)
The hardness proof supplies the structure of the difficult training tasks, and the controls show why that structure matters. In the two-token study at , retaining the construction inputs but generating targets with a random attention head gives QV/QKV median normalized mean squared error (NMSE) of 1.93e-5 / 3.20e-6, compared with 4.27e-31 / 4.49e-31 on Gaussian inputs with random-head targets. Each condition uses 24 independent datasets with four random initializations each (96 runs) and 2,000 cosine-scheduled Adam updates. Training on the constructed inputs therefore retains much larger median errors than on Gaussian inputs after replacing the construction targets (Figures 1–3).
The complete three-token comparison in Reply 1 also shows sensitivity to target structure: on identical inputs, QKV median NMSE is 0.1333 for construction targets and 0.0005687 for random-head targets. Together, these controls show how the proof's input and target relationships provide concrete ways to investigate optimization difficulty.
In the paired two-token variant of the 1-in-3-SAT construction, every sample ends with the same reference token (the common-final-token condition). In Appendix I.7, we relax this condition by perturbing separately for each sample, and also test supervising all outputs (Figure 11). We retain the constructed nonfinal tokens and recompute targets from the same generating head. With random-head targets on construction inputs, QKV has larger mean and median final-output NMSE than QK, KV and V-only in all four token/supervision combinations at both . These conditions use 24 datasets, four starts each (96 runs) and 2,000 cosine-scheduled Adam updates at initial rate 0.3. In the same experiment, with both changes at , QKV mean / median NMSE is 0.0280 / 0.0269, compared with 0.00245 / 1.38e-31 on Gaussian inputs with random-head targets. Joint-training difficulty therefore remains observable when the task no longer requires a shared final token or final-only supervision.
Changing supervision gives another useful comparison. We used the two-token variant's construction inputs with targets from a random attention head, at with common . After 2,000 Adam updates at initial rate 0.3, supervising all outputs changes QV's mean final-output NMSE from 0.0120 to 1.79e-8, while QK changes from 8.26e-11 to 0.00748. Each condition uses 24 independent datasets with four random initializations each (96 runs). Both are evaluated on the same final-output targets (Appendix I.7, Figure 11). With K prescribed, some added outputs have uniform attention and impose linear constraints on V independently of Q. This suggests studying how those additional constraints affect optimization.
These examples extend the empirical use of the reduction beyond its exact targets and task conditions. They also reveal how supervision changes which conditional training problem is easier, giving concrete directions for investigating the roles of inputs, targets and learned matrices.
Appendices H–J contain the new proofs, protocols and figures. We would be happy to clarify the experimental comparisons or any remaining questions about the framework's utility.
Experiment: using the reduction from hardness proof to construct data (Q1), see more in revised manuscript figures 1-12
Synthetic experiments from the paper's constructions (Reply 1)
Thank you for recognizing the soundness of the theoretical results and for suggesting synthetic experiments. Our asymptotic worst-case complexity results are established by proof. The experiments investigate whether a distinction exposed by the two-token construction also appears in Adam training: learning only WQ,WV with WK prescribed, versus learning only WQ,WK with WV prescribed. Below, Q, K and V denote the weight matrices, and combinations such as QV identify those learned.
We also investigate joint QKV training, longer sequences and larger key dimensions. We chose the minimal module to isolate the source of difficulty. Our hardness theorems also cover every fixed positive key and value dimension (Reply 2). The revised introduction and proofs also explain the mechanism underlying the construction.
The construction in Proposition 2 generates realizable datasets from planted satisfiable 1-in-3-SAT instances. Our two-token study compares three conditions: Inputs and targets from the 1-in-3-SAT construction, Same inputs, targets from a random attention head, and Gaussian inputs, targets from a random attention head. QV and QKV retain larger mean and median errors than QK on both conditions with construction inputs. With construction targets, the QV difference concerns high-accuracy fitting. Figures 1–3 show the training trajectories and accuracy profiles.
The relations between scores and values extend to longer sequences while preserving every calibration constraint needed for hardness. Appendix J proves QV/QKV hardness for this complete 1-in-3-SAT construction. For KV on these construction-target tasks, the supplied queries have bounded normalized integer score differences, which permit polynomial-time fitting. At ambient dimension n=1025, each condition uses 24 independent datasets with four random initializations each (96 runs). Every regime uses 2,000 full-batch Adam updates with a cosine learning-rate schedule and initial rate 0.1. The table reports final median normalized mean squared error (NMSE), the squared residual sum divided by target energy, for construction inputs and targets. V-only learns the value matrix alone.
At lengths three and four, QV/QKV have errors around 0.1 while KV fits much more accurately. This ordering holds by both mean and median across n=129,513,1025. At length five, KV has a higher median and a slightly lower mean than QV/QKV. With only V learned, Adam optimizes a linear least-squares objective under the same budget. Prescribed matrices come from the generating head and can encode the planted assignment, so the comparison also reflects the information supplied by each frozen matrix.
Changing the targets on identical inputs gives a second comparison. For Same inputs, targets from a random attention head, at length three and n=1025, median NMSE is 0.008918 for QV and 0.0005687 (95% CI [0.0004897, 0.0006587]) for QKV, compared with 0.1222 and 0.1333 (95% CI [0.1209, 0.1390]), respectively, for construction targets. Each 95% confidence interval uses 1,000 bootstrap resamples of whole datasets, retaining all starts and pairing across conditions. These generating heads keep the key matrix fixed and use Gaussian query and value directions rescaled to match score and target root-mean-square magnitudes. At initial rate 0.1, construction-target QV/QKV errors are larger by both mean and median in all nine combinations of length and dimension. The smaller learning-rate study shows that this ordering can change with the optimizer settings.
Appendix I.6 gives the full protocol. Table 7 and Figures 9–10 show all three lengths, means and medians, controls on the same inputs, and task-level uncertainty. Further experiments on variants of the construction cover lengths two to five and key dimensions one, two and four. Figures 4–5 compare final errors at lengths two and three side by side, Figures 6–7 show convergence trajectories separately by ambient dimension, and Figure 8 examines key dimension. These studies use a common final token and final-output supervision. Appendix I.7 and Reply 3 examine changes to final tokens and supervised outputs.
The construction gives us realizable tasks with substantial residual errors under Adam, including joint QKV training, and a way to investigate how those errors depend on learned components and target structure.