acceptodds
Under review as a conference paper at ICLR 2027

Training a -token attention is NP-hard

Abstract

As the title indicates, this work is inspired by the celebrated paper of Blum and Rivest, "Training a -node neural network is NP-complete." They showed that for a -layer, -node, -input neural network (arguably the simplest neural network), deciding whether weights exist that fit a given training set exactly is NP-complete. We show that for an attention head with -dimensional query, key, and value, and -dimensional token input (arguably the simplest attention head), the analogous exact-fit problem on a training set of -token sequences is NP-hard, and that if softmax is replaced with hardmax, the decision problem becomes NP-complete. These hardness results persist when fitting allows a fixed positive tolerance, measured coordinatewise or by mean squared loss.

Primary area:
learning theory
Keywords:
computational complexity, NP-hardness, NP-completeness, complexity theory of attention mechanisms

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_QTheOpenReview ↗
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
  1. Theoretically solid paper which investigates an interesting problem.
  2. Within my (limited) capacity, I find no flaws in the proofs.
Critical weaknesses
  1. 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
  1. 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.
  2. Can the authors state the potential utility of this work beyond filling a theoretical blank?
5 comments
AuthorsOpenReview ↗

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,WVW_Q,W_V with WKW_K prescribed, versus learning only WQ,WKW_Q,W_K with WVW_V 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.

Q1. 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.

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=1025n=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.

Sequence lengthQKKVQVQKVV only
35.98e-281.16e-60.12220.13333.17e-9
42.80e-195.03e-40.11790.12411.45e-7
54.72e-150.13320.11470.11914.81e-6

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,1025n=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=1025n=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.

AuthorsOpenReview ↗

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 T≥3T\ge3, with exactly TT 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 [a,F][a,F] sharing a nonzero FF, plus duplicate pairs [u,u][u,u]. 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.

SupervisionLearn Q,KLearn Q,VLearn Q,K,VLearn any one weight matrix
Final output onlyPNP-hardNP-hardP
Both outputs, targets (y,y)(y,y)PNP-hardNP-hardP
Both outputs, arbitrary targetsNP-hardNP-hardNP-hardP

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 FF gives scores through w=WQ⊤WKFw=W_Q^\top W_K F. 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.

AuthorsOpenReview ↗

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 n=1025n=1025, 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 FF (the common-final-token condition). In Appendix I.7, we relax this condition by perturbing FF 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 n=129,513n=129,513. 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 n=513n=513, 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 n=513n=513 with common FF. 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.

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

The paper studies the problem of training a single-head attention layer given a training dataset of 2-token samples. This problem occurs as a subproblem in training LLMs based on transformer architectures. The authors prove that exactly fitting soft- and hardmax attention is NP-hard even if the query, key and value dimension is 1. They achieve this via polynomial-time reductions from 1-in-3-SAT which seem rather simple. They also prove membership in NP for the hardmax case and containment in some existential theory over reals for softmax.

The results appear to be correct, but it is not clear to me why NP-hardness is particularly interesting or surprising. Also, the proofs are not nicely presented. They simply describe the hardness construction without any intuitive guidance, which makes it hard for a human reader to get any insights into the problem. It is mostly some technical calculations, involving no subtle aspects.

Critical strengths

The paper establishes NP-hardness for a relevant training problem in deep learning.

Critical weaknesses

The hardness reductions seem not to be very sophisticated and are not presented in a very informative way. The reader does not get a good intuition for what exactly makes the problem hard.

It is not clear, why NP-hardness is particularly interesting or surprising. Training attention heads is a more complex problem than training other simpler single-neuron networks (which is already known to be NP-hard), so it is quite natural that it is also NP-hard.

Questions for authors

What is the gain of knowing NP-hardness? Was it open or unexpected?

Can you deduce something interesting from the hardness constructions? Does it indicate some directions for necessary assumptions making the problem tractable in practice?

7 comments
AuthorsOpenReview ↗

Sketch of responses to weaknesses and questions

Overview of our response to Reviewer 7J1m (Reply 1)

Thank you for carefully checking the proofs and recognizing the soundness of our theoretical results. Since the discussion covers several aspects, we provide an overview to make our core arguments clear. Replies 2 and 3 develop the arguments and evidence. Where relevant, we also share new empirical observations prompted by Reviewer QThe’s questions to illustrate the significance and implications of our framework.

W1. The hardness reductions seem not to be very sophisticated and are not presented in a very informative way. The reader does not get a good intuition for what exactly makes the problem hard.

We sketch the intuition here, with more detail in Reply 2, W1. In our softmax construction, additive value constraints and multiplicative attention-odds constraints force Boolean choices. Shared parameters and clause targets make fitting equivalent to satisfying the encoded SAT instance. Hardmax achieves the same consistency through value calibration and winner selection. We have added this explanation to the revised introduction and proofs.

W2. It is not clear, why NP-hardness is particularly interesting or surprising. Training attention heads is a more complex problem than training other simpler single-neuron networks (which is already known to be NP-hard), so it is quite natural that it is also NP-hard.

We note that the fitting objective matters here. Exact fitting of an ordinary affine logistic neuron is in P, while the known single-neuron hardness result (see Reply 2) concerns a positive loss threshold. Our theorem establishes a complexity distinction between that neuron and minimal attention, and the construction explains how learned values and attention probabilities create this difficulty (Reply 2, Q2 / W2 and W1).

Q1. What is the gain of knowing NP-hardness?

Beyond establishing worst-case hardness, our reduction also provides a way to study training behavior. It translates instances of the well-studied 1-in-3-SAT problem into attention-training datasets whose constraints we can inspect and vary. For example, satisfiable instances generate realizable data for comparing which weight matrices are learned and how targets are generated. In a complete three-token construction at n=1025n=1025, joint QKV training has median normalized mean squared error (NMSE) 0.1333 after 2,000 Adam updates. Changing the targets on the same inputs gives 0.0005687 under the same protocol. In the two-token study at the same dimension, joint QKV training has median NMSE 1.43×10−61.43\times10^{-6} on inputs and targets from the 1-in-3-SAT construction, compared with 4.49×10−314.49\times10^{-31} on Gaussian inputs with targets from a random attention head (Reply 3, Q1).

Q2. Was it open or unexpected?

We establish hardness of exact numerical fitting for one scalar head and two tokens. The closest prior attention results address multihead distributional learning or four-token categorical-error optimization. The surprise is that hardness occurs at the first sequence length permitting nontrivial token interactions: one-token fitting is linear, yet two tokens suffice, with growing ambient dimension and sample count. The nearby polynomial-time cases in Q3 further show that which quantities must be learned matters even within this minimal module (Reply 2, Q2 / W2 and Q3).

Q3. Can you deduce something interesting from the hardness constructions?

As one illustration, consider freezing the key weight matrix (i.e. training WQW_Q and WVW_V only, with ground-truth WKW_K). The construction in Proposition 2 supervises one output per sequence and already uses the same fixed key weight matrix for every satisfying assignment. The same construction therefore proves hardness when only Q and V are learned. On the common-reference two-token family, prescribing values instead gives polynomial-time fitting under final-only or repeated full targets. Thus which weight matrix is frozen matters even when the number of learned matrices is unchanged (Reply 2, Q3). This theoretical distinction is also reflected in our two-token experiments: at n=1025n=1025, QV has larger mean and median errors than QK on the construction inputs after 2,000 Adam updates (Reply 3, Q1).

Q4. Does it indicate some directions for necessary assumptions making the problem tractable in practice?

The input and target comparisons motivate studying how dependencies in natural data affect optimization. We also find that supervising additional outputs can change the relative fitting errors of QK and QV. With K prescribed, some of those outputs impose linear constraints on V independently of Q. This gives a concrete direction for studying which supervision makes optimization easier, alongside the sufficient conditions for exact fitting in Q3 (Reply 3, Q4).

Appendices H–J of the revised manuscript contain the detailed proofs, experimental results, figures and protocols.

AuthorsOpenReview ↗

Minimality, proof mechanism and theoretical consequences (W1, W2, Q2, Q3)

On minimality, proof mechanism and theoretical consequences (Reply 2)

Q2 / W2: Was it open or unexpected?

Exact numerical fitting on rational data is NP-hard at the smallest nontrivial attention setting: one head, scalar queries, keys and values, and two-token samples. With one token, the attention weight is identically one and fitting is linear. The surprise is that two-token interactions already suffice at minimal projection dimensions. Ambient dimension and sample count grow. Our softmax and hardmax hardness theorems also cover every fixed positive key and value dimension, with all matrices trainable.

The closest attention results address different learning questions. Chen and Li give two-token distributional learning lower bounds using a growing number of heads, already with rank-one maps per head. Tesfaye et al. establish single-head hardness for optimizing categorical endpoint-selection error on four-token graph sequences with learned embeddings and readout.

The comparison with a single neuron also depends on the objective. Šíma's hardness theorem concerns a supplied positive squared-loss threshold. Exact fitting of an ordinary affine logistic neuron with unrestricted finite real parameters on rational data is in P: sigmoid inversion gives linear equations with rational coefficients and logarithms of positive rationals on the right, whose consistency is decidable using Etessami et al., Proposition 2.1.

W1: What exactly makes the problem hard?

The construction couples learned values and attention probabilities to enforce consistent Boolean choices. Linear relations among tokens induce additive relations among values. At the shared reference token, softmax turns the corresponding score relations into products of attention odds. The targets force the positive literal odds α,β\alpha,\beta to satisfy α+β=3\alpha+\beta=3 and αβ=2\alpha\beta=2. Their only possibilities, (1,2)(1,2) and (2,1)(2,1), encode a Boolean choice. Shared parameters make these choices agree across samples, and clause targets enforce exactly-one satisfaction. Fitting therefore solves the encoded SAT constraints.

For hardmax, value calibration and two-token winner constraints force complementary literal values zero and one, after which clause targets impose the exactly-one condition. At scalar key dimension, guessing key signs and query order, including ties, leaves rational linear feasibility. Polynomial-size rational certificates give NP-completeness for arbitrary rational datasets. Hardness also persists under approximate fitting: Theorem 6 gives a fixed positive gap in mean squared loss per sample between exact-fit YES instances and NO instances, with bounded inputs and targets and exactly two tokens. Proposition 2 gives the causal final-output counterpart.

Q3: Can you deduce something interesting from the hardness constructions?

For example, consider freezing WKW_K. The construction in Proposition 2 supervises one output per sequence. Completeness uses WK=e1⊤W_K=e_1^\top for every satisfying assignment, while soundness permits all three matrices to vary. The same reduction therefore proves QV hardness, including Proposition 2's loss gap. Adjusting the tokens so that the prescribed key is one on each token gives the repeated-full-target case below.

Prescribing WVW_V instead makes final-output fitting tractable on two-token pairs sharing a final token. Unequal token values determine the required attention probabilities, whose log-odds give consistency equations. Equal-value cases are checked directly. Exact fitting is therefore in P. QKV learns both scores and values, so their coupling remains.

The table concerns exact fitting by one scalar softmax head on rational pairs [a,F][a,F] sharing a nonzero FF, plus duplicate pairs [u,u][u,u], with rational targets. Columns list learned matrices with finite real entries. All remaining matrices have prescribed rational entries. P means polynomial time in the binary input length. Both-output supervision is unmasked.

SupervisionLearn Q,KLearn Q,VLearn Q,K,VLearn any one weight matrix
Final output onlyPNP-hardNP-hardP
Both outputs, targets (y,y)(y,y)PNP-hardNP-hardP
Both outputs, arbitrary targetsNP-hardNP-hardNP-hardP

Both the learned matrices and the supervision affect complexity. General KV fitting on this family remains open. For final-output supervision, Appendix J gives a polynomial-time algorithm when prescribed query-score differences lie on a rational grid with polynomially bounded within-sample integer span.

Appendix H gives the proofs for Table 1. The reduction translates 1-in-3-SAT instances into attention-fitting datasets whose constraints we can inspect and vary. Reply 3 discusses the experiments.

AuthorsOpenReview ↗

Synthetic experiments constructed from the hardness proof's reduction (Q1, Q4)

Training behavior and tractable restrictions (Reply 3)

Q1: What is the gain of knowing NP-hardness?

Satisfiable 1-in-3-SAT instances generate realizable tasks for comparing training regimes distinguished by the theory.

Prior work connects complexity theory to numerical training. Song et al., NIPS 2017 train networks with momentum SGD on functions from their statistical-query lower-bound construction. Ding et al., NeurIPS 2025 compare Adam-trained linear attention with least squares in an enlarged predictor class, relating this to reconstruction hardness.

Our two-token study uses planted satisfiable instances and the construction in Proposition 2, preserving duplicate calibrations and dividing targets and values by 5. Controls keep the generating key fixed and use rescaled Gaussian query and value weights to produce targets on the same inputs or Gaussian inputs. Prescribed matrices come from the generating head and can encode the planted assignment. At n=1025n=1025, each condition uses 24 independent datasets with four random initializations each (96 runs) and 2,000 cosine-scheduled Adam updates. QK, KV, QV and QKV name the learned matrices. Final normalized mean squared error (NMSE) is the squared residual sum divided by target energy.

DatasetStatisticQKKVQVQKV
Inputs and targets from the 1-in-3-SAT constructionMean2.69e-331.45e-337.15e-109.84e-6
Median2.14e-331.44e-331.02e-111.43e-6
Same inputs, targets from a random attention headMean4.61e-314.70e-334.41e-54.56e-6
Median1.73e-334.71e-331.93e-53.20e-6
Gaussian inputs, targets from a random attention headMean9.58e-321.41e-314.65e-311.83e-3
Median6.81e-321.20e-314.27e-314.49e-31

On both families with construction inputs, QV and QKV have larger mean and median errors than QK and KV. With construction targets, the QV difference concerns high-accuracy fitting. QV has larger errors on construction inputs than on Gaussian inputs by both summaries, even with random-head targets. QKV has the same median ordering. A few high-error Gaussian runs raise its mean. The trajectories and accuracy profiles appear in Appendix I.

A natural extension retains every calibration constraint at longer sequence lengths and remains NP-hard for QV/QKV fitting (Appendix J). At length three and n=1025n=1025, joint QKV training has median NMSE 0.1333 (95% CI [0.1209, 0.1390]) for construction targets and 0.0005687 (95% CI [0.0004897, 0.0006587]) for targets from a random attention head on the same inputs. These results use 24 independent datasets with four starts each (96 runs per condition), 2,000 full-batch cosine-scheduled Adam updates and initial rate 0.1. Each 95% confidence interval uses 1,000 bootstrap resamples of whole datasets, retaining all starts and pairing across conditions. The random generating heads keep K fixed and match score and target root-mean-square magnitudes. The full comparisons across lengths, dimensions and learning rates appear in Appendix I.6, Table 7 and Figures 9–10.

Q4: Does it indicate some directions for necessary assumptions making the problem tractable in practice?

With V prescribed, exact fitting is in P on common-reference two-token inputs with final-only supervision or repeated full targets. Prescribing K instead, or using arbitrary full unmasked targets with V prescribed, retains NP-hardness (Reply 2, Table 1). Logit-equation and least-squares fitting are evaluated in Appendix I.3, Table 4.

Another direction is to identify assumptions on the joint distribution of inputs and targets that permit efficient training. Our construction deliberately coordinates examples to enforce Boolean choices and clause satisfaction. The comparisons with Gaussian inputs and random-head targets motivate investigating how such dependencies differ in natural data and affect optimization.

Supervision also affects training. On the two-token variant's construction inputs with random-head targets, a common final token and n=513n=513, supervising all outputs changes mean final-output NMSE from 0.0120 to 1.79e-8 for QV and from 8.26e-11 to 0.00748 for QK. Both conditions use 24 datasets, four starts each (96 runs), 2,000 Adam updates at initial rate 0.3 and the same final-output evaluation targets (Appendix I.7, Figure 11). With K prescribed, some added outputs impose linear constraints on V independently of Q through uniform attention. Joint QKV training retains larger errors than QK, KV and V-only after varying final tokens and supervising all outputs (Figure 11, QThe Reply 3).

Appendices H–J give the proofs and protocols. We would be happy to clarify the proof intuition or these implications.

Reviewer_yepmOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the computational complexity of training a single-head attention layer to exactly fit a training set and proves NP-hardness of the problem via a reduction from the distinct-literal version of 1-in-3 SAT, even with at most two tokens per sample and scalar key and value dimensions. The paper then strengthens this result by showing that hardness persists whilst relaxing the goal to approximate fitting, with a constant gap in mean squared loss.

Critical strengths
  • I found the paper well written, and the ideas flow well! The paper elegantly makes a direct connection between the problem of optimizing/finding an exact-fit softmax-attention head and the very well-studied problem of 1-in-3 SAT, drawing inspiration from Blum and Rivest’s classic result on the computational complexity of a simplified neural network.
  • The proofs used in the paper seem technically sound and rigorous.
Critical weaknesses

Weak Points

  • The main concern I have with this paper is the lack of qualification with recent work ESP Paper that appeared in last year’s ICLR conference. In particular, its Theorems 4–5 already show the NP-hardness (and APX-hardness) of finding a minimal-error single-head, single-layer, attention-only softmax model with a linear readout (a similar simplified model to the one used by this paper) over a dataset constructed over cyclic graphs. Both papers use a shared key token to prove their results. Since one can find a polynomial reduction between 1-in-3 SAT and MAS (through, say, Independent Set), the two papers seem to reach a similar conclusion from two different directions. Additionally:
    • Both proofs exploit parameter sharing to impose globally coupled constraints across input instances. It would be useful to clarify whether there is a connection.
    • The ESP paper also seems to partly answer the posed open problem -- “A complementary direction is to identify restricted data” that admit poly-time algorithms -- since the paper argues that the problem can be solved with zero error for a dataset constructed over DAGs (the construction uses topological ordering, which can be computed in polynomial time in the size of the graph).

I still think the paper’s ideas are valuable, and it provides a simpler 2-token input construction that leads to computational hardness. I would be willing to consider increasing my score provided the paper addresses how it adds to or extends this prior result, or provides additional explanation of the ideas that underlie the two results to position them as complementary rather than overlapping.

Questions for authors

I put my main questions in the weaknesses section above.

4 comments
AuthorsOpenReview ↗

Relationship to ESP and the source of hardness (Weakness 1, 2)

Relationship to ESP and the source of hardness (Reply 1)

Thank you for carefully reading the paper, recognizing the soundness of the proofs, and pointing us to Tesfaye et al., Two (narrow) heads are better than (an arbitrarily wide) one. We have added this work to the related-work discussion and conclusion. We explain the relationship between the results and proofs below. Reply 2 discusses the DAG example and further implications.

W1: Relationship between the hardness results. Since one can find a polynomial reduction between 1-in-3 SAT and MAS (through, say, Independent Set), the two papers seem to reach a similar conclusion from two different directions.

Both results establish worst-case hardness for a single attention head, and the source decision problems are polynomially interreducible. The difference lies in the attention-fitting problems produced by the reductions. ESP's Theorems 4–5 establish NP-hardness and APX-hardness for optimizing categorical endpoint-selection error on four-token graph sequences, with learned embeddings and a linear readout. Its optimum error is determined by the minimum feedback arc set. Zero error corresponds to an acyclic graph. Our result establishes hardness of exact numerical fitting on fixed rational inputs, already with two tokens and scalar queries, keys and values. Thus deciding zero error on ESP's graph family reduces to acyclicity, while numerical realizability in our construction is NP-hard. Our result also distinguishes an attained exact fit from a fixed positive mean squared loss, with bounded inputs and targets (Theorem 6).

This minimal setting is deliberate: one-token fitting is linear, so two tokens isolate the first nontrivial attention interaction. Our softmax and hardmax hardness theorems also cover every fixed positive key and value dimension, with all weight matrices trainable.

W2: Connection between the proofs. Both proofs exploit parameter sharing to impose globally coupled constraints across input instances. It would be useful to clarify whether there is a connection.

We agree that shared parameters and a common reference token connect the proofs. They couple outputs across examples in both constructions, leading to different constraints on the shared parameters.

In ESP, the inputs (u,v,1,\\#) and (u,v,2,\\#) differ only in the selector. Clearing the positive softmax denominator gives unnormalized vocabulary-logit vectors buv+c1b_{uv}+c_1 and buv+c2b_{uv}+c_2. The vector buvb_{uv} collects contributions shared by the two examples. The selector contributions c1,c2c_1,c_2 are independent of the edge. For successful selector predictions, ESP's proof uses the comparisons

\qquad (b_{uv}+c_2)_u<(b_{uv}+c_2)_v.$$ Subtracting cancels $b_{uv}$ and gives $p_u>p_v$, where $p_w=(c_1-c_2)_w$. Thus all edges whose two selector predictions are correct follow one global vertex ordering. The matching construction from a topological order makes optimal classification correspond to a maximum acyclic subgraph (Sections 3.1–3.2 and Appendix B). Our numerical inputs instead obey fixed linear relations such as $P_i=L_i+\bar L_i-F$. Every learned value map and score functional must respect these relations. At the reference token, let $\alpha_i=e^{s(F,F)-s(L_i,F)}$ and $\beta_i=e^{s(F,F)-s(\bar L_i,F)}$. Value linearity and the fitting targets force their sum to be three. Score additivity turns the relation for $P_i$ into multiplication of these odds, and another target forces their product to be two: $$\alpha_i+\beta_i=3,\qquad \alpha_i\beta_i=2 \quad\Longrightarrow\quad \\{\alpha_i,\beta_i\\}=\\{1,2\\}.$$ These equations fix two possible literal states. A clause token containing $k$ true literals has output $(6+k)/(1+2^k)$, whose prescribed target $7/3$ forces $k=1$ (Section 3, Lemmas 2–3). Shared parameters make the Boolean choices consistent across the dataset. ESP enforces a global ordering and optimizes the edges compatible with it. Our additive value and multiplicative odds equations enforce simultaneous Boolean constraints through prescribed numerical outputs. These are two uses of shared attention parameters, yielding complementary results for classification-error optimization and numerical realizability.
AuthorsOpenReview ↗

Tractable restrictions and further implications (Weakness 3)

Tractable restrictions and further implications (Reply 2)

W3: Tractable data and the DAG construction. the problem can be solved with zero error for a dataset constructed over DAGs

ESP's topological-order construction efficiently achieves zero classification error on its acyclic graph data. We now cite this example in the conclusion and specify the intended numerical-fitting direction: identify structural conditions on supplied rational input vectors and numerical targets that permit efficient fitting when all three weight matrices are learned jointly.

The minimal setting also permits a closely matched comparison: prescribing different weight matrices gives both hard and tractable cases. Consider freezing the key weight matrix in the construction in Proposition 2. Its completeness proof uses the same key matrix for every satisfying assignment, so the construction already proves NP-hardness when only Q and V are learned. Supplying V instead makes final-output fitting polynomial-time on the corresponding scalar two-token family. Which matrix is supplied matters even when two matrices are learned in either case.

More precisely, this family consists of rational pairs [a,F][a,F] sharing a nonzero final token FF, together with duplicate pairs [u,u][u,u], and rational targets. Prescribed weight matrices are rational. Learned matrices have finite real entries. With V supplied, unequal token values determine the required attention probabilities, and their log-odds yield consistency equations. Equal-value cases are checked directly. Appendix H proves this polynomial-time result in the ordinary binary model and the corresponding QV/QKV hardness. Table 1 also shows how supervision changes the classification: with V prescribed, repeated full targets permit polynomial-time fitting, whereas arbitrary full targets give NP-hardness under unmasked supervision.

The constructions also provide datasets for studying numerical training. ESP investigates gradient-based training on its graph-defined tasks (Section 5). From satisfiable 1-in-3-SAT instances, our reduction generates realizable attention-training datasets that we can use to study optimization, including joint QKV training.

For example, a natural extension to longer sequences retains every calibration constraint and the sum and product equations of Reply 1. Appendix J proves QV/QKV hardness for every fixed length of at least three. At length three and ambient dimension n=1025n=1025, each condition uses 24 independent datasets with four random initializations each (96 runs), with 2,000 full-batch cosine-scheduled Adam updates at initial rate 0.1. Median final normalized mean squared error (NMSE) for joint QKV training is 0.1333 (95% CI [0.1209, 0.1390]) for Inputs and targets from the 1-in-3-SAT construction, versus 0.0005687 (95% CI [0.0004897, 0.0006587]) for Same inputs, targets from a random attention head. NMSE is the squared residual sum divided by target energy. Each 95% confidence interval uses 1,000 bootstrap resamples of whole datasets, retaining all starts and pairing across conditions. The random generating heads keep the key matrix fixed and use Gaussian query and value directions rescaled to match score and target root-mean-square magnitudes.

The difference on identical inputs gives a reason to investigate how target structure affects optimization. Together with the parameter comparison, it illustrates how the proof can guide studies of training behavior.

Keeping the constructed inputs but replacing their targets with outputs from a random attention head still gives larger QV/QKV median errors than Gaussian inputs in the two-token study. In the two-token variant, joint QKV training also retains larger mean and median errors than QK, KV and V-only after varying final tokens and supervising all outputs. These controls show that the proof supplies empirically useful structure beyond its exact targets and task conditions (Appendix I.7, Figure 11, QThe Reply 3).

Appendix I.6, Table 7 and Figures 9–10 give comparisons across lengths, dimensions and learning rates, with means, medians and uncertainty. Our replies to 7J1m and QThe discuss these implications further. Appendices H–J contain the supporting proofs and experiments.

We would be happy to clarify the connection to ESP further, or discuss any other concerns that the Reviewer would like us to address.

Reviewer_yepmOpenReview ↗

Reply to Authors

I would like to thank the authors for taking the time and effort to address my raised concerns, elaborating on the similarities and differences between the two results and explaining implications of this work.

However, I am still not convinced regarding the further implication/generality of this result. For instance it is not surprising to me that the problem moves to P when you supply the weights of the value matrix. If I understand this correctly the paper doesn't say much about the hardness of training on datasets outside of the specially constructed ones used to induce the SAT constraints (for instance the construction puts a constraint on the vectors encoding the inputs themselves, which is not usually the case with learned token embeddings).

After considering the additional explanations, I am retaining my original score, although the response has improved my assessment of the paper.

Thank you for considering our responses. We appreciate your concerns about the datasets being specially constructed, which narrows the scope of direct implications. We would like to clarify a little more about such implications and generality of our results, since our experiments do cover cases when the output targets are perturbed by randomizing the attention heads used as teacher models (Appendix I.2).

Our main contribution is theoretical. We identify tractable and NP-hard exact-fitting regimes within a minimal attention head. The reduction used in our complexity proof also provides a framework for investigating how the learned components, supervision and data constraints affect fitting difficulty (Table 1, Appendix H). Its distinction from existing theory work in literature has been discussed in Reply 1 and 2.

It is surely desirable for theoretical work to have implications in very general empirical settings, which we hope to advance in future work. And we agree that our hardness proof uses specially constructed datasets (though NP-membership implies a reduction to SAT for any rational hardmax fitting problem covered by Theorem 4). But we also note that even when various conditions, including the dataset construction, deviate from the theory's assumptions, we still empirically observe differences in training behavior similar to those suggested by the tractability separation. The experiments examine specific changes to the constructed dataset. Keeping the constructed inputs fixed, we replace the SAT targets with outputs from a random attention head. QV and QKV still have larger mean and median errors than QK and KV (Figures 1–3). Increasing the sequence length to four or five tokens also preserves the QV and QKV comparison with QK for both target choices (Appendix I.5, Figure 8). We also vary the final tokens across samples and supervise all output positions. QKV training still has larger mean and median final-output errors than QK, KV and V-only training (Figure 11, 24 datasets with four initializations each). These comparisons give concrete directions for further theoretical analysis and empirical investigation.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.