{"id":"7c689a1a-3d64-4a77-ae53-1d8943e8b79f","arxiv_id":"2412.09925","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"Softmax transformers can approximately simulate hard-attention transformers, using a temperature that depends on the reciprocal of the attention-score gap.","lead":"This paper proves that transformers with standard soft attention can mimic the stronger hard attention behavior used in many theoretical constructions, by scaling the attention temperature or by using position embeddings that grow with the input length. The results give explicit recipes for converting hard-attention language recognizers into soft attention ones with bounded error.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader identified the real-valued arithmetic and unbounded position embedding assumptions as the weakest assumption. I agree that this is a domain assumption rather than an internal inconsistency: the paper explicitly studies a real-valued model and uses temperature scaling or unbounded PEs as the mechanism to escape Hahn's lemma. The constructions are explicit and the bounds are stated with enough detail to be independently checked. The minor proof gap in the layer-wise recursion of Theorem 26 is real but not load-bearing: the affine error bound in Lemma 25 is stated only for input error <= 1, and the proof of Theorem 26 iterates this bound without explicitly showing that the input error to every layer remains <= 1. However, since the error sequence is nondecreasing when r > 0, choosing the implicit constant in the O-bound so that the final error is below 1/2 guarantees the condition holds at every layer; this is a standard bootstrapping argument and does not alter the asymptotic temperature bound. There is no other step where the central claim appears to rely on an unstated or false premise. The paper's comparison with existing work, including the S-RASP gap bound of Omega(1/n^3) and the flip-flop gap of 1/n, is consistent with the derived temperature bounds. I see no reason to change the reader's ACCEPT verdict.","tokens_in":23469,"tokens_out":18825,"duration_ms":199792,"concrete_test":"Independently re-derive the proof of Theorem 26 for a two-layer average-hard attention transformer with gap gamma(n)=1/n and x_max(n)=1, checking that the claimed temperature tau(n)=Theta(1/(n log n)) yields final error below any inverse-polynomial bound while keeping each intermediate layer's input error below the epsilon <= 1 condition of Lemma 25.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The central claim of Theorem 26—that any average-hard attention transformer with gap gamma(n) can be approximate-simulated by a temperature-scaled softmax transformer with the same parameters and 1/tau in O((1/gamma) log(n x_max/gamma))—is supported by a coherent chain of bounds: Lemma 6 gives exponential softmax-vs-hard concentration under a ziggurat score pattern; Lemmas 8 and 7 adapt this to tie-breaking and table lookup; Lemma 25 bounds per-layer error; Lemma 29 bounds activation growth; and Theorem 26 composes the layers via a geometric series. The only caveats are the explicit model assumptions of exact real arithmetic and unbounded position embeddings, which the reader also identified and which are standard for this line of work. One minor rigor gap is that the error recursion in the proof of Theorem 26 applies Lemma 25, which is stated for input errors epsilon <= 1, without explicitly verifying that intermediate errors stay below 1; however, this is easily patched by choosing the constant in the O-bound so the final error bound is below 1, which is possible for any inverse-polynomial epsilon(n). This does not threaten the result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies when softmax attention can simulate hard attention in transformers. It first proves that several fragments of linear temporal logic (TL[⊖,⊕], TL[since,until], and the counting logic LTL[↼#,⇀#,+,Mon]) can be simulated by temperature-scaled softmax transformers, either with inverse-polynomial temperature or with polynomially unbounded position embeddings. These results cover the star-free languages recognized by unique-hard attention transformers and extend to counting terms and numerical predicates. The paper then proves its main theorem (Theorem 26): any average-hard attention transformer with gap γ(n) can be approximated by a softmax transformer with the same parameters, using a temperature τ(n) satisfying 1/τ(n) in O((1/γ(n)) log(n x_max(n)/γ(n))). In the typical case γ(n)=1/n^k and x_max(n) in n^{O(1)}, this gives 1/τ(n) in O(n^k log n). The proofs are carried out through explicit softmax-versus-hardmax concentration bounds, tie-breaking constructions, and a layerwise error propagation lemma. The paper closes with applications to induction heads, S-RASP transductions, and Dyck language membership.","tokens_in":23710,"tokens_out":10843,"duration_ms":114600,"significance":"If the results hold, they resolve a natural open question about the relationship between hard and soft attention in a parameter-uniform, rate-explicit way. The constructions are general and parameter-uniform, and the temperature schedule is tied to a concrete, checkable quantity (the attention-score gap). The paper gives explicit credit to prior work, including the parameter-free UHAT-equals-LTL characterization of Yang et al. (2024), and builds on it without circularity. The main theorem is supported by a detailed chain of lemmas (Lemma 6, Lemmas 8 and 7, Lemma 25, Lemma 29, and the geometric-series composition in Theorem 26). The applications to induction heads, S-RASP, and Dyck-k are concrete and illustrate the reach of the results. A caveat, stated clearly in the paper, is that the constructions use exact real arithmetic and unbounded position embeddings; the quantitative guarantees would need revisiting under fixed-precision arithmetic.","major_comments":[{"comment":"Lemma 25 is stated for input perturbations with ε ≤ 1, but the iterative proof of Theorem 26 applies the lemma layer after layer without explicitly verifying that the intermediate layer errors stay bounded by 1. This is a genuine gap in the proof as written, though it is easily fixed: choose the constant in the O-bound so that the final error bound is below 1; because the geometric bound is monotone in the layer index, all intermediate bounds are then also below 1. Adding this verification would make the proof fully rigorous.","section":"Section 5, Theorem 26 (Appendix C.4)"}],"minor_comments":[{"comment":"The symbol γ is used both for the gap of the original scores and for the scaling factor in the transformed scores. The proof is correct, but the double use is confusing; consider renaming one of the two parameters.","section":"Section 3.3, Lemma 8"},{"comment":"The recursion as displayed contains two typos: the term 'a = K x_max n e^{γ/τ}' should read 'a = K x_max n e^{-γ/τ}', and the condition on ε(n) should be ε(n) ≥ α/n^β rather than ε(n) ≤ α/n^β, since ε(n) ∈ Ω(1/poly(n)) is a lower bound on the allowed error. The intended reasoning is clear, but the displayed formulas should be corrected.","section":"Appendix C.4, proof of Theorem 26"},{"comment":"The score formula ͡s_{ij}=6(½(−1)^j+j/(2n)) is combined with temperature τ=1/n to obtain the effective scaled scores of Theorem 8b. The role of the temperature in producing the factor n could be made explicit, since the connection is easy to miss.","section":"Section 4.1, Theorem 12(a)"},{"comment":"The definition of x_max(n) as the maximum absolute entry of initial activation vectors is fine, but the sentence 'This is well defined because there are finitely many different inputs of length n' should also mention that the position embedding PE_n(i) and the word embedding take only finitely many values for fixed n; this is implicit but worth stating.","section":"Section 5, Definition of x_max"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically sound and the central claim is well supported. The only substantive issue is the missing ε≤1 verification in the iterative application of Lemma 25, which is a local and easily patchable gap. The remaining issues are typos and notational ambiguities. The self-citations to Yang et al. (2024) and Yang and Chiang (2024) are used legitimately as independent lemmas; I see no circularity concern. The paper fits the journal's scope and will be of interest to the transformer expressivity community."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The reader's take is right, and I agree with it. The main result is Theorem 26: any average-hard attention transformer with gap gamma(n) can be approximately simulated by a softmax transformer with the same parameters, using temperature tau with 1/tau in O((1/gamma) log(n x_max/gamma)). That is new, it is parameter-uniform, and it improves on Sanford et al.'s non-parameter-uniform construction. The LTL fragment simulations are also new and worth having, especially the tie-breaking and counting constructions. The proofs are detailed, the lemmas are explicit, and the error bounds are concrete. I checked the ziggurat and tie-breaking arguments and they work. The paper is honest about what it assumes: exact real arithmetic and unbounded position embeddings. That is a real limitation, but it is standard in this line of work and not a hidden flaw. The self-cited UHA-equals-LTL theorem is parameter-free and independently established, so relying on it is legitimate. The notational ambiguity in Lemma 8, where gamma is used both for the score gap and the scaling factor, is annoying but harmless; the proof only needs the original gap to be at least 1, and the applications respect that. The one tiny rigor gap is in the proof of Theorem 26, where Lemma 25 is applied without explicitly verifying that intermediate errors stay below 1. The stress-test note is right that this is easily patched by choosing the constant in the O-bound so the final error is below 1. That is a minor fix, not a substantive concern. The paper is a solid theoretical contribution. It resolves an open question, it gives a general transfer theorem, and it provides explicit constructions that are independently checkable. The writing is clear, and the comparison with prior work is fair. I would bring this to a reading group, and I would cite it. It deserves a serious referee, and my guess is that a referee will come back with minor comments about the assumptions and the proof patch, not with a fundamental objection. My recommendation: send it to peer review and let it through with minor revisions.","headline":"A genuinely new and correct simulation theorem: softmax transformers can approximate average-hard attention with temperature tied to the score gap; the paper deserves a serious review.","tokens_in":24191,"tokens_out":1123,"would_cite":true,"duration_ms":13737,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68Q45","03B44"],"pacs":[],"model":"deepseek-v4-flash","headline":"A gap-based temperature bound makes softmax attention a faithful stand-in for average-hard attention, with the same transformer parameters.","keywords":["average-hard attention","temperature scaling","softmax attention","temporal logic with counting","transformers","position embeddings","parameter-uniform simulation"],"falsifier":"Run the paper's S-RASP-derived DYCK-2 transformer in fixed-precision floating point (say 32-bit) for $n = 2^{16}$, with the prescribed temperature $\\tau \\approx 1/(n^3 \\log n)$, and check whether the winning position still receives a clear majority of attention weight; if rounding makes the scores collapse to a tie, the simulation depends essentially on the unbounded-precision assumption, which the paper states but does not remove.","tokens_in":23292,"feed_emoji":"🌡️","tokens_out":12675,"duration_ms":130549,"temperature":0.7,"pith_summary":"This paper asks when the standard softmax attention used in transformers can replicate hard attention, where all weight is placed on the maximally scoring position or positions even though softmax never assigns exact zeros or ones. It proves that for several logics that capture what hard-attention transformers recognize—temporal logics with previous/next, since/until, and counting terms—softmax transformers can simulate them using either an inverse-polynomial temperature or polynomially growing position embeddings. The main theorem is general: an average-hard attention transformer whose attention scores are separated by a gap $\\gamma(n)$ can be approximated by the same-parameter softmax transformer at temperature $\\tau$ with $1/\\tau(n) \\in O((1/\\gamma(n)) \\log(n x_{\\max}(n)/\\gamma(n)))$. For the gap $\\gamma(n)=1/n^k$ and polynomially bounded inputs, this is $1/\\tau(n) \\in O(n^k \\log n)$, so the cooling needed stays inverse-polynomial. This matters because many discrete reasoning tasks have previously been solved only with hard attention, and the result gives parameter-uniform soft-attention solutions with controlled error.","feed_headline":"Inverse-polynomial cooling lets soft attention mimic hard attention","feed_subtitle":"A new proof shows a gentle cooling schedule is enough to copy hard attention on discrete tasks.","key_machinery":"The load-bearing object is the gap $\\gamma(n)$: the smallest difference between a maximal attention score and any other score, over all inputs of length $n$. The mechanism is temperature-dependent softmax, $\\mathrm{softmax}_\\tau(s)_j = \\exp(s_j/\\tau)/\\sum_k \\exp(s_k/\\tau)$, which concentrates on the maximum once the gap is amplified to $\\gamma/\\tau$. The proof bounds the approximation error per layer by roughly $n e^{-\\gamma/\\tau}$ plus a propagated input error multiplied by $x_{\\max}/\\tau$, using a ziggurat score-shape lemma, parabolic table-lookup scores, and specially constructed tie-breaking score perturbations that turn rightmost or leftmost hardmax into softmax-friendly patterns. A feedforward rounding function converts approximate Booleans back to exact $0/1$ values, and first/last-position markers supply quantities like $1/i$ that the attention patterns need. Iterating the per-layer error bound through $L$ layers yields the temperature formula in Theorem 26, with constants that may grow exponentially in depth but not in $n$.","core_discovery":"The central claim is Theorem 26: every average-hard attention transformer $T$ with gap $\\gamma(n)$ can be approximately simulated by the softmax transformer obtained by replacing $\\mathrm{ahardmax}$ by softmax at temperature $\\tau$, with exactly the same parameters, provided $1/\\tau(n) \\in O((1/\\gamma(n)) \\log(n x_{\\max}(n)/\\gamma(n)))$. Here $x_{\\max}(n)$ bounds the initial activation entries over all inputs of length $n$, and $\\gamma(n)$ is the minimum separation between the maximum attention score and every lower score across all layers, positions, and inputs of that length. If $\\gamma(n) = 1/n^k$ and $x_{\\max}(n)$ is polynomial in $n$, then $1/\\tau(n) \\in O(n^k \\log n)$. The paper also proves matching simulations for subclasses: the logics $\\mathrm{TL}[\\ominus,\\oplus]$, $\\mathrm{TL}[\\text{since},\\text{until}]$, and the counting logic $\\mathrm{TL}[\\reflectbox{$\\leftharpoonup$}\\#,\\rightharpoonup\\#, +, \\mathrm{Mon}]$ can each be computed by softmax transformers with $\\tau = 1/n$ and bounded position embeddings, or with $\\tau = 1$ and position embeddings that include $n$, $i/n$, $i$, and $i^2$ as needed.","pith_inferences":["A testable practical reading is that training with a temperature schedule tied to sequence length—cooling like $1/n$ or $1/(n^k \\log n)$ for tasks with known gap—should let a standard softmax transformer solve discrete subroutines rather than merely approximating them; this is an extension, since the paper proves existence in an exact-arithmetic model, not trainability.","The results suggest that hard attention is not an expressivity boost over soft attention for these classes; the same parameters run in soft mode already suffice once temperature or position embeddings are allowed to vary with input length. An implicit consequence is that the real obstruction in previous no-go results is fixed temperature and bounded position embeddings, not softness itself.","A natural next step would be to combine temperature scaling with layer normalization or rounding and ask whether the required precision or cooling can be reduced; the paper lists these as separate interventions but does not analyze their interaction.","For practitioners, the gap $\\gamma(n)$ can be measured empirically by running a trained or constructed model over all inputs up to some $n$ and recording the minimum score separation; if that gap decays faster than any inverse polynomial, the theory predicts such a model will need much colder temperatures to keep its hard-attention behavior."],"forward_implications":["Every transduction expressible in the S-RASP programming language is computable by a softmax transformer with temperature $\\tau(n) \\in \\Omega(1/(n^3 \\log n))$, because S-RASP compiles to an average-hard attention transformer with gap $\\Omega(1/n^3)$.","The DYCK-$k$ balanced-bracket language becomes computable by a softmax transformer with the same $\\Omega(1/(n^3 \\log n))$ temperature, via the paper's S-RASP program for prefix validity.","The basic and iterated induction-head tasks are computable by a softmax transformer with $\\tau(n)=1/n$, because they are definable in the since/until temporal logic that the paper simulates at that temperature.","All these simulations are parameter-uniform: the same weights work for every input length, unlike earlier rounding-based simulations whose depth or width must grow with $n$.","Because approximate Booleans are rounded exactly, the simulations compose: a module with a fixed-size acceptance gap can feed into later modules that expect exact discrete inputs."],"supporting_citations":[{"why":"Supplies the Lipschitz obstruction (an $O(1/n)$ output sensitivity for soft attention with bounded position embeddings) that the paper's temperature and embedding constructions must overcome.","marker":"Hahn (2020)"},{"why":"Provides the softmax-versus-ahardmax gap bound $2n e^{-\\gamma/\\tau}$ used as the base of the per-layer error analysis.","marker":"Edelman et al. (2022)"},{"why":"Defines the counting temporal logic $\\mathrm{TL}[\\leftharpoonup\\#,\\rightharpoonup\\#, +, \\mathrm{Mon}]$ and its simulation by average-hard attention transformers, the target class of Section 4.","marker":"Barceló et al. (2024)"},{"why":"Characterizes masked unique-hard attention via LTL and supplies the induction-style simulation of previous/next and since/until formulas.","marker":"Yang et al. (2024)"},{"why":"Introduces S-RASP and compiles it to average-hard attention with gap $\\Omega(1/n^3)$, an application of Theorem 26.","marker":"Strobl et al. (2025)"},{"why":"Gives the average-hard-attention construction for DYCK-$k$ that the paper re-expresses in S-RASP and simulates softly.","marker":"Yao et al. (2021)"},{"why":"Provides the rounding-based non-parameter-uniform simulation of $k$-hop induction heads that motivates the paper's parameter-uniform alternative.","marker":"Sanford et al. (2024)"},{"why":"Shows temperature scaling around $1/\\log n$ can help length generalization and constructs parity with softmax, background for the temperature method.","marker":"Chiang and Cholak (2022)"}],"fun_headline_variants":["Cooling softmax attention achieves hard attention","Temperature scaling lets soft attention emulate hard","Polynomial cooling simulates hard attention","Soft attention with cooling mimics hard attention","Inverse-polynomial cooling makes soft attention hard"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The constructions assume exact real-valued arithmetic, so attention scores can encode differences as small as $1/\\mathrm{poly}(n)$ and position embeddings can carry unbounded values like $n$, $i/n$, and $1/i$ without precision loss.","fun_headline_variants_meta":{"raw":{"variants":["Cooling softmax attention achieves hard attention","Temperature scaling lets soft attention emulate hard","Polynomial cooling simulates hard attention","Soft attention with cooling mimics hard attention","Inverse-polynomial cooling makes soft attention hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00052,"raw_usage":{"total_tokens":2509,"prompt_tokens":924,"completion_tokens":1585,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":540,"completion_tokens_details":{"reasoning_tokens":1521}},"tokens_in":540,"tokens_out":1585,"duration_ms":13542,"temperature":1.0,"reasoning_tokens":1521,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:35:48.399938+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's S-RASP-derived DYCK-2 transformer in fixed-precision floating point (say 32-bit) for $n = 2^{16}$, with the prescribed temperature $\\tau \\approx 1/(n^3 \\log n)$, and check whether the winning position still receives a clear majority of attention weight; if rounding makes the scores collapse to a tie, the simulation depends essentially on the unbounded-precision assumption, which the paper states but does not remove.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the rounding-based non-parameter-uniform simulation of $k$-hop induction heads that motivates the paper's parameter-uniform alternative."}],"review_version":1}