{"id":"5c28fe29-f11d-45f4-bf50-e9b649aff9ca","arxiv_id":"2601.16873","paper_version":2,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Single-head attention parameters are learnable with O(d²) queries or O(rd) via compressed sensing, extendable to one-layer models if FFNs are learnable, but multi-head attention lacks identifiability from queries alone.","lead":"This paper develops algorithms for learning the parameters of attention mechanisms in Transformer models by querying their outputs with chosen input sequences. Understanding this learnability could help in verifying, auditing, or efficiently training large AI models without full internal access.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"O(d²) query bound for single-head attention hinges on an unstated query construction that isolates softmax interactions","rationale":"The reader's weakest assumption (exact single-head target + adaptive query access) is precisely the point at which the missing algorithmic construction must be verified; the multi-head non-identifiability result is noted as well-supported, so the single-head positive result is the only load-bearing piece still unconfirmed.","tokens_in":1742,"tokens_out":327,"duration_ms":36335,"concrete_test":"Implement the claimed elementary algorithm (or the closest reconstruction from the proof sketch) for d=8 with randomly drawn full-rank W_Q, W_K, W_V; run it on exact oracle outputs and measure the number of queries until parameter error < 1e-8. If the query count exceeds 3d² or fails to recover the matrices on >10% of random instances, the O(d²) claim does not hold.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim requires that there exists an adaptive strategy using only O(d²) black-box queries that recovers the exact query/key/value matrices despite the nonlinear softmax. The abstract gives no indication of how the learner chooses the sequences (e.g., repeated tokens, orthogonal bases, or norm-controlled vectors) to produce invertible linear systems or exact attention-score equations. If the construction implicitly assumes that the value matrix is full-rank and that the chosen queries keep all softmax arguments in a regime where the nonlinearity can be algebraically inverted, the bound fails for generic parameter settings.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript studies the learnability of Transformer sequence models under adaptive black-box query access to outputs. For single-head attention regressors of width d it claims an elementary algorithm recovering the exact query/key/value parameters with O(d²) queries; this extends to one-layer Transformers assuming an oracle for learning ReLU FFNs. When head dimension r ≪ d it obtains O(rd) queries via compressed-sensing arguments. It also proves polynomial-query robustness to additive noise under mild norm and margin conditions, and shows that multi-head attention is not identifiable from queries alone.","tokens_in":1828,"tokens_out":442,"duration_ms":36521,"significance":"If the central claims hold, the work supplies the first explicit query-complexity bounds for recovering attention parameters, together with a clean separation between identifiable single-head and non-identifiable multi-head cases. The compressed-sensing reduction and the reduction to FFN learnability are technically standard yet cleanly applied; the non-identifiability result is a useful negative finding.","major_comments":[{"comment":"The O(d²) algorithm for single-head attention (abstract and the corresponding theorem) asserts that an adaptive query strategy recovers the exact matrices despite the softmax nonlinearity, yet the manuscript provides no explicit description of the query sequences (e.g., repeated tokens, orthogonal bases, or norm-controlled vectors) that produce the required invertible linear systems. Without this construction the bound cannot be verified for generic parameter settings.","section":"Single-head attention learning section"},{"comment":"The compressed-sensing claim for the r ≪ d regime (abstract) relies on the value matrix being full-rank and on the chosen queries keeping softmax arguments in an algebraically invertible regime; neither condition is stated as an explicit assumption nor shown to hold generically.","section":"Compressed-sensing subsection"}],"minor_comments":[{"comment":"The abstract refers to an “elementary algorithm” without a high-level pseudocode sketch or step-by-step outline; adding one would improve readability.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the detailed reading and for identifying two points where the presentation of our algorithms requires additional explicit detail. Both comments are fair and we will revise the manuscript to address them. No standing objections remain after these clarifications.","responses":[{"response":"We agree that the current text describes the high-level recovery strategy (linear systems obtained after canceling the softmax via carefully chosen differences) but does not spell out the concrete adaptive query sequences. In the revision we will add an explicit construction in the proof of the O(d²) theorem: the learner first queries with scaled standard-basis vectors e_i repeated across positions to isolate each row of the query and key matrices, then perturbs with small orthogonal vectors drawn from a fixed basis to ensure the softmax arguments remain strictly positive and the resulting map is invertible by finite differences. This construction works for any fixed parameter matrices of bounded norm and yields exactly the claimed query count.","revision_made":"yes","referee_comment":"[Single-head attention learning section] The O(d²) algorithm for single-head attention (abstract and the corresponding theorem) asserts that an adaptive query strategy recovers the exact matrices despite the softmax nonlinearity, yet the manuscript provides no explicit description of the query sequences (e.g., repeated tokens, orthogonal bases, or norm-controlled vectors) that produce the required invertible linear systems. Without this construction the bound cannot be verified for generic parameter settings."},{"response":"The referee is correct; both conditions were used implicitly but not stated. In the revised manuscript we will add them as formal assumptions (value matrix V has full column rank r and all queried softmax inputs lie in an open set where the softmax is locally invertible). We will also include a short generic argument: for random Gaussian parameter matrices the value matrix is full-rank with probability 1, and a random perturbation of the query vectors of size O(1/d) keeps the arguments inside the invertible regime with high probability. The O(rd) bound then follows directly from standard compressed-sensing recovery.","revision_made":"yes","referee_comment":"[Compressed-sensing subsection] The compressed-sensing claim for the r ≪ d regime (abstract) relies on the value matrix being full-rank and on the chosen queries keeping softmax arguments in an algebraically invertible regime; neither condition is stated as an explicit assumption nor shown to hold generically."}],"tokens_in":1427,"tokens_out":505,"duration_ms":41412,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main result is an elementary algorithm that learns single-head attention parameters with O(d²) queries, plus a compressed sensing version that drops to O(rd) when the head dimension r is much smaller than d. They also show multi-head attention cannot be identified from queries alone. This is useful because it gives concrete positive bounds for the single-head case and a clear negative for the multi-head setting that is common in practice. The extension to one-layer transformers by reducing to FFN learning is a reasonable modular step, and the robustness to noisy outputs under mild conditions is a practical addition. The citations to compressed sensing are appropriate and the arguments seem to build on standard techniques without circularity. The soft spot is the O(d²) algorithm itself. The abstract claims it exists but does not describe how the adaptive queries are chosen to disentangle the softmax nonlinearity and recover the exact matrices. If the construction relies on special input sequences that keep the attention scores in a regime where inversion is possible, it may not hold for arbitrary parameters or inputs. The stress test concern about isolating the interactions looks worth checking in the full proofs. This paper is for people working on the theoretical learnability of Transformers and query-based access models. It has enough new bounds and a solid negative result to merit serious refereeing, though the single-head part may require careful verification of the query details during review.","headline":"Single-head attention can be learned with O(d²) queries while multi-head attention is not identifiable from black-box queries.","tokens_in":2307,"tokens_out":343,"would_cite":false,"duration_ms":28900,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Cost/FunctionalEquation.lean","rs_theorem":"washburn_uniqueness_aczel","paper_passage":"Theorem 4.1 ... two-row input X=[(u+e_j)^T; e_j^T] ... α(u;j)=σ(u^T w_j) ... u^T w_j = σ^{-1}((y-v_j^*)/(u^T v^*)) ... solve linear system"},{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/ArithmeticFromLogic.lean","rs_theorem":"absolute_floor_iff_bare_distinguishability","paper_passage":"Proposition 7.1 ... multi-head attention parameters are not identifiable from value queries"}],"headline":"Query-based exact recovery of single-head softmax attention parameters via length-2 probes and sigmoid inversion is orthogonal to RS","alignment":"orthogonal","rationale":"The paper's core machinery (Theorem 4.1: length-2 queries X=[(u+e_j)^T; e_j^T] reduce softmax to σ(u^T w_j), invert via logit to obtain linear system Zw_j=t, recover W columnwise in O(d²) queries; low-rank ROP reduction in Thm 5.2; multi-head non-identifiability in Prop 7.1) operates entirely in statistical learning theory with black-box value queries. It never invokes ratio-symmetric costs, J(x)=½(x+x⁻¹)−1, φ-ladders, 8-tick periodicity, or any forcing from a single distinction. No overlap with RS modules such as Cost.FunctionalEquation (washburn_uniqueness_aczel), Foundation.AbsoluteFloorClosure, or AlexanderDuality (D=3 forcing).","tokens_in":52142,"confidence":"high","tokens_out":409,"duration_ms":22790,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Single-head attention regressors can be learned exactly with O(d^2) adaptive black-box queries.","keywords":["attention","transformer","query complexity","black-box learning","parameter recovery","compressed sensing","multi-head attention","learnability"],"falsifier":"Two distinct single-head attention parameter sets that produce identical outputs on every possible input sequence would show the parameters are not uniquely recoverable.","tokens_in":2635,"feed_emoji":"🔍","tokens_out":703,"duration_ms":48839,"temperature":0.7,"pith_summary":"The paper examines learning Transformer sequence models when only black-box access to their outputs is given, allowing adaptive queries with any sequence of vectors. It proves that single-head attention parameters for width d are recoverable by an elementary algorithm using O(d^2) queries. The approach extends directly to one-layer Transformers once ReLU feedforward networks are assumed learnable. Compressed sensing cuts the query count to O(r d) when the head dimension r is much smaller than d. The work also shows polynomial-query recovery to epsilon accuracy under mild noise, norm, and margin conditions, while establishing that multi-head attention is not identifiable from queries alone.","feed_headline":"Single-head attention recovered with O(d^2) queries","feed_subtitle":"An elementary algorithm reconstructs exact attention parameters from adaptive black-box output queries.","key_machinery":"The adaptive black-box query procedure that selects input sequences of vectors, observes outputs, and solves for the attention weight matrices via linear algebra or compressed sensing.","core_discovery":"We show that for a model with width d, there is an elementary algorithm to learn the parameters of single-head attention with O(d^2) queries. Further, we show that if there exists an algorithm to learn ReLU feedforward networks, then the single-head algorithm can be easily adapted to learn one-layer Transformers with single-head attention. In the regime where the head dimension r ≪ d, single-head attention-based models can be learned with O(r d) queries via compressed sensing arguments. Under mild norm and margin conditions, parameters can be estimated to ε accuracy with a polynomial number of queries even when outputs are provided only up to additive tolerance. Multi-head attention is not 1","pith_inferences":["The query complexity result suggests layer-wise recovery strategies could scale to deeper attention stacks.","Non-identifiability of multi-head attention may explain the practical value of random head initialization during training.","Similar black-box techniques might recover parameters of other attention variants such as linear or kernel attention.","Efficient recovery could enable post-training verification or compression of deployed attention models."],"forward_implications":["One-layer Transformers with single-head attention become learnable by combining the attention learner with any ReLU FFN learner.","Epsilon-accurate parameter recovery is possible with polynomially many queries even under additive output noise.","Query complexity reduces to O(r d) via compressed sensing whenever the head dimension is small relative to width.","Multi-head attention requires extra structural assumptions such as orthogonality for identifiability and learnability."],"fun_headline_variants":["O(d^2) queries recover single-head attention parameters","Learning one-layer Transformers from attention queries","O(rd) queries learn single-head attention via sensing","Multi-head attention not identifiable from output queries"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The target function is exactly a single-head attention regressor and the learner has adaptive black-box access to query any sequence of vectors.","fun_headline_variants_meta":{"raw":{"variants":["O(d^2) queries recover single-head attention parameters","Learning one-layer Transformers from attention queries","O(rd) queries learn single-head attention via sensing","Multi-head attention not identifiable from output queries"]},"model":"grok-4.3","cost_usd":0.00739,"raw_usage":{"total_tokens":3359,"prompt_tokens":752,"num_sources_used":0,"completion_tokens":57,"cost_in_usd_ticks":73903000,"prompt_tokens_details":{"text_tokens":752,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2550,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":752,"tokens_out":57,"duration_ms":19136,"temperature":1.0,"reasoning_tokens":2550,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-16T11:25:01.926025+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Two distinct single-head attention parameter sets that produce identical outputs on every possible input sequence would show the parameters are not uniquely recoverable.","supporting_citations":[],"review_version":1}