acceptodds
Under review as a conference paper at ICLR 2027

Extracting Linear Temporal Logic Formulas from Hard Attention Transformers

Abstract

There has been an increased interest into finding exact encodings of hard attention transformers (HAT) for binary classification into Linear Temporal Logic (LTL), so that the mature ecosystem of LTL tools can be applied to verify and reason about such models. Although several theoretical encoding approaches have been proposed, to the best of our knowledge, none of them have been implemented. In this work, we propose an exact encoding of a HAT into LTL with past operators amenable to practical implementation. We also propose an encoding of the notion of a sufficient reason w.r.t. an input w, that is, a formula extracted from a HAT with the property that any other input w′ that satisfies it has the same classification as w. We implement both the encoding of a HAT and of a sufficient reason for an input and perform experiments using synthetic data. We also include experiments for the balanced parenthesis problem.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
hard attention, transformers, linear temporal logic, rule extraction, verification, explanation, formal guarantees

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_9y7WOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers the problem of extracting LTL formulas from hard attention transformers. Previous translations from transformers to LTL produce very large formulas, and previous work has not attempted the extraction. This works proposed an encoding of transformers into LTL that can be “unfolded” from top to bottom, focusing on the outputs which are of interest (eg those which capture a “sufficient reason” for acceptance of a string). Experiments are run on extracting formulas from small transformers trained on synthetic data.

Critical strengths

Novelty

Much theoretical work has discussed the possibility of extracting formulas from transformers, but they never actually did it. Doing this for the first time is quite interesting, and the successes/failures will be relevant for future work.

Rigor

The paper’s methodology is rigorous. The extraction of formulas is exact, unlike other kinds of interpretability methods. Also, the proofs/concepts are presented in a rigorous and readable style — a major strength of papers.

Critical weaknesses

Unclear empirical analysis

Several important details are unclear which renders the conclusions of the experiments slightly weaker. First, the test accuracy is never >90%. It’s unclear whether this was a design choice for the experiments or a limitation of training using hard attention. Second, analysis of the sufficient reason is lacking. In particular they are motivated for being more compact and efficient than extracting the whole network, but we need to know to what are the tradeoffs.

Questions for authors

Questions

  • Was the suboptimal prediction accuracy form the transformers to be extracted from a design choice or an issue with optimization? For the latter, a typical trick to use is temperature annealing, which gradually lowers the temperature across training. If this was the problem then this may help with training.
  • Can you clarify about the function of the sufficient reason? Is it meant to approximate the behavior of the whole network? If so, how well do the sufficient reasons capture the entire network, for the sufficient reasons extracted in the experiments?
  • What distinguishes the proposed encoding from the one used by Jerad et al 2025? Is the transformer model the same?
3 comments

We thank the reviewer for their response and suggestions.

Q1. Was the suboptimal prediction accuracy form the transformers to be extracted from a design choice or an issue with optimization? For the latter, a typical trick to use is temperature annealing, which gradually lowers the temperature across training. If this was the problem then this may help with training.

We did not tune for accuracy, since extraction is exact for any trained model. Annealing is a good suggestion, however, and it fits well our setup as the forward pass stays hard; we will try it.

Q2. Can you clarify about the function of the sufficient reason? Is it meant to approximate the behavior of the whole network? If so, how well do the sufficient reasons capture the entire network, for the sufficient reasons extracted in the experiments?

A sufficient reason is specific to a single input ww: it is a formula guaranteeing that any input satisfying it receives the same classification as ww. Therefore, we can see it as describing the exact behaviour of the whole network on ww, rather than approximating the network. Its purpose is to explain the network's classification for ww.

Q3. What distinguishes the proposed encoding from the one used by Jerad et al 2025? Is the transformer model the same?

No, the model is different. Jerad et al. (2025) also study transformers with left-most hard attention, but they consider future masking, whereas our HAT has no masking (and other minor differences). Their translation serves to prove an expressivity result and is not designed to be implemented. Unlike Jerad et al., we also extract sufficient reasons, which explain the classification of a single input.

Reviewer_9y7WOpenReview ↗

Response to the Rebuttal

Thank you for your response. In particular, the clarification on the exact model and the motivation behind the experiments was helpful.

I am left still wondering how to assess the efficacy of the sufficient reasons. What kind of analysis can they be used for explaining? Out of the words w' such that T(w')=T(w), how many are actually captured by the sufficient reason for w? Without this analysis or explicit use cases of sufficient reasons, it is unclear how to compare them to full extraction of the network.

For now I will maintain my rating. Thank you again to the authors.

We thank the reviewer for their suggestion. The advantage of sufficient reasons is that they can still be computed when the global formula cannot, as in our experiments with 1000 symbols. We agree that measuring how many inputs with the same label a sufficient reason covers would be a useful addition. For our six-symbol datasets this can be computed exactly, since by Proposition 2 it suffices to consider the words without repeated symbols, and we will include these numbers in the final version.

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

The paper studies the semantics of (Unique) Hard Attention Transformers (HAT) without positional encodings and without maskings. Concretely, from a given HAT the authors describe how to compute an LTL (with past) formula that is, applied to any word w, true if and only if the transformer accepts that language. To this end, one constructs a finite set of formulas per attention layer describing that a position labeled with a letter aa attends to another position labeled with bb which can then be inductively unfolded into one (large) LTL formula. The authors also explain how to obtain, from a HAT and a given input word, a (smaller) formula proving that the word is accepted or not. The theoretical results are complemented with several experiments.

The paper is well-written and the theoretical results seem to be correct (I haven't checked the proofs in the Appendix). However, the theoretical results are also not very surprising since Yang, Chiang, and Angluin (NeurIPS 2024) proved a similar result for a more powerful model that is also implying the main result of this paper. It would be more interesting to have an exact characterization of the model. I actually also don't think that the experiments are very helpful here, since all the trained models have pretty low accuracy. I guess one of the reasons is that the trained formulas are not expressible via the very restrictive HAT model (e.g. the balanced parenthesis language cannot be described via an LTL formula since it is not regular).

Evaluation

The main statement of this paper is basically a corollary of a known result (Yang et al. (2024)), while a more interesting statement (Proposition 2) was just given as some kind of side note. I think, by shifting the focus of the paper to this statement, would make it a good paper for an ML conference. This is not just a small revision and, hence, I recommend rejection of this paper.

Detailed comments:

  • l. 84: What is the reason for having two matrices VlV^l and OlO^l for each layer? They always appear together as Vl⋅OlV^l\cdot O^l, so you could actually merge them to one (d x d)-matrix.
  • l. 163-164: This sounds a bit like multiple positions of a letter aa can attend to different letters bb, which is not true since left-most hard attention is independent of the position of the letter aa.
  • Def. 4: This definition is confusing. First, you should make clear that you start with an LTL^- formula over the alphabet ΣL\Sigma_L and then inductively replace letters from Σl\Sigma_l by formulas over Σl−1\Sigma_{l-1}. Actually it is also better to reindex the formulas here such that ϕ°,L\phi^{°,L} is the original formula and ϕ°,l\phi^{°,l} the one over Σl\Sigma_l - in particular, ϕ°,0\phi^{°,0} is the one over Σ\Sigma. The usage of ϕ\phi, ψ\psi, and ψ°,l\psi^{°,l} is a bit confusing, too.
  • Def. 5: It is not a good idea to write ΣL+\Sigma^+_L since this is usually the language of all non-empty words over ΣL\Sigma_L. Similarly, later you use wlw^l for a word corresponding to ww but with letters from Σl\Sigma_l. However, wlw^l usually denotes the word consisting of ll repetitions of the the word ww.
  • l. 186: It is not true that ϕ°,l\phi^{°,l} is always a formula over Σ\Sigma - only if ϕ\phi is a formula over Σl\Sigma_l.
  • Lemma 2: Maybe you should recall beforehand that "correspondence" refers to Def. 2.
  • l. 252/253: It is very confusing that you are using the symbols ll and ℓ\ell.
  • Sec. 4.2: Can you say anything about the accuracy of the trained HAT in Table 4? I don't think the results here have any meaning if the accuracy is low. So, you should add this.

Typos:

  • l. 166: "before bb" -> "before the first bb"
  • l. 177: "results in a finite set of formulas"
  • l. 179: indexing should start with ϕ°,0\phi^{°,0}
  • l. 180/181: ∈≤\in\leq -> ≤\leq
  • l. 239: "there is b′b' and [...]" -> "there are b′b' and [...]"
Critical strengths
  • The paper is well-written (except for a few parts that are a bit confusing, but easily fixable).
  • The theoretical statements are correct.
Critical weaknesses
  • The studied model is relatively weak: any computation depends just on the relative order of the first occurrences of each letter (this is basically stated in Proposition 2).
  • The given main result is just a corollary of the paper of Yang, Chiang, and Angluin at NeurIPS 2024: Here, the authors studied HAT with masking and showed that they can express exactly the languages described by LTL formulas. Here, we have a stricly weaker model (by removing masking) and hence, we the main result states that all HATs can still be expressed via LTL (with past - which is equivalent to LTL without past).
  • The actual main result (Prop. 2) which is characterizing the languages expressible via HAT is given as some kind of side note at the end of the theoretical part of the paper (and without a proof).
  • The experiments are somewhat meaningless since all of the trained HAT have a pretty low accuracy (and some of them don't even state accuracy). I guess the reason for this is that the trained formulas are not expressible via this very restrictive HAT model. For example, the balanced parentheses languages (or Dyck language) is clearly not regular and, hence, not expressible via LTL (and HAT).
Questions for authors

none

3 comments

We thank the reviewer for their response. We have uploaded a new version where the noted typos and other minor infelicities have been corrected. We next address the remaining comments:

W2. The given main result is just a corollary of the paper of Yang, Chiang, and Angluin at NeurIPS 2024: Here, the authors studied HAT with masking and showed that they can express exactly the languages described by LTL formulas. Here, we have a stricly weaker model (by removing masking) and hence, we the main result states that all HATs can still be expressed via LTL (with past - which is equivalent to LTL without past).

We agree that LTL-definability of our HATs follows from the prior expressivity results of Yang et al. (2024). However, Theorem 3.1 states more than that: it establishes the correctness of a specific construction, the formula ΦT\Phi_T of Definition 5. This matters because ΦT\Phi_T can be extracted from a trained model and passed to existing LTL tools, as in Section 4.

More generally, our paper is not intended as a study of the semantics of leftmost HATs without masking. As stated in the introduction, our focus is practical implementation: we give a construction for an exact encoding of HATs into LTL and demonstrate that it can be implemented. The translation of Yang et al. (2024) was designed to establish expressivity. It proceeds through the intermediate language B-RASP and a normal form that, as they note in Section 3.3, may be exponentially larger, and it has not been implemented. We also introduce and implement sufficient reasons, which are not considered in Yang et al. (2024). Definitions 5, 7, Theorem 3.2, and Section 4 in our paper are no less important than Theorem 3.1.

W3. The actual main result (Prop. 2) which is characterizing the languages expressible via HAT is given as some kind of side note at the end of the theoretical part of the paper (and without a proof).

Please note that we provide a full proof of Proposition 2 in the appendix. For completeness, we are preparing a revised version where we sketch its core ideas in the main text. We agree that the proposition says something about the expressive power of leftmost HATs without masking. While it may deserve a central place in a potential paper characterising these models, that is not the aim of this paper; here it plays a supporting role in reducing the set of words we need to check in the experiments.

W1 & W4. The experiments are somewhat meaningless since all of the trained HAT have a pretty low accuracy (and some of them don't even state accuracy). I guess the reason for this is that the trained formulas are not expressible via this very restrictive HAT model. For example, the balanced parentheses languages (or Dyck language) is clearly not regular and, hence, not expressible via LTL (and HAT).

The synthetic target formulas are theoretically expressible by HATs; we will mention this in the revised version and update the appendix with a proof. The case of balanced parenthesis is a prototypical case study used in related work where the depth of the nesting of parenthesis is fixed and, therefore, regular. Accuracies are reported for all models: Table 1 for the parentheses task, Table 2 for all synthetic targets and depths, and the text of Section 4.2 for the large-alphabet models. The models used in Tables 3 and 4 are those of Table 2

In contrast, the proposal in the paper of Yang, Chiang, and Angluin at NeurIPS 2024 was not implemented, and by Lemma 22 in their appendix, it is not practically implementable.

I don't think that Lemma 22 is a good reason for practical implementability since the statement is also true for your variant of transformers (in fact it holds for any HAT with finite-imaged positional enconding - independent of the usage of masking or not).

We also introduce and implement sufficient reasons, which are not considered in Yang et al. (2024). In short, Definitions 5, 7, Theorem 3.2, and Section 4 in our paper are no less important than Theorem 3.1.

I agree that your result about sufficient reasons is new. You should point this out a bit more. However, I still think that section 4 is not very helpful. Your experiment just show that the learned formulas are still far away from the correct ones.

For completeness, we are preparing a revised version where we sketch its main idea in the main text.

I think that is a good addition to the paper.

Another note since the other reviewers critizied the exponential growth of your formulas: one of the outstanding papers of ICLR 2026 ("Transformers are Inherently Succinct" by Bergsträßer, Cotterell, Lin) showed that HATs are exponentially more succinct than LTL formulas. Maybe you could also add a note on this to your paper.

All in all, I lift my score slightly since the authors showed efforts to substantially improve the paper, but I am still not fully convinced that the results are very interesting.

We thank the reviewer for their further comments and suggestions. We agree that Bergsträßer et al. 2026 is a relevant reference for this work and will note it in the next revision; we'll also further highlight the sufficient reasons' novelty.

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

The paper studies how to translate a trained hard-attention Transformer into a logical formula that captures its classification behavior. For single-head transformer with leftmost hard attention, the authors construct an equivalent Linear Temporal Logic formula with past operators. For an individual input, they also extract logical conditions under which the model is guaranteed to make the same prediction. The authors implement their methods and evaluate them on synthetic logical classification tasks, with additional experiments on a parentheses dataset. The experiments expose discrepancies between learned behavior and intended task rules, while the formulas describing the entire model become much larger as the number of layers increases.

Critical strengths
  • The proposed translation aims to preserve the model’s predictions on every input sequence, rather than merely matching sampled examples. Within the restricted architecture. This helps reveal what rules the model has learned and whether they match the intended task, rather than relying on test accuracy alone.

  • The sufficient-reason construction extracts conditions that guarantee the original prediction without requiring a formula describing the entire model. Experiments show substantially smaller formulas and faster extraction in many cases, including larger alphabets, offering a useful alternative when full-model extraction becomes intractable.

Critical weaknesses
  • Severe formula growth limits the demonstrated practical value. Even for three-layer models over six symbols, extracted formulas can contain approximately 10^{11} symbols and operators. Input-specific explanations are often smaller, but the 1,000-symbol experiment still includes an explanation of length approximately 4.3 * 10^{10}. Combined with the restrictive architecture, e.g., single-head hard attention without positional encoding or masking, these results leave limited evidence that the approach yields tractable explanations or useful verification at realistic scales.

  • The extracted formulas reveal the specific rules learned by the models, which goes beyond establishing architectural limitations. However, the evaluation primarily reports formula sizes, extraction times, and agreement with model predictions. It provides limited evidence that these formulas enable useful verification, such as certifying systematically finding counterexamples beyond the observed data. This leaves the motivating benefit of access to LTL verification tools insufficiently demonstrated.

  • Minor comment: the equivalence proof contains inconsistencies that require clarification. Definition 4 defines unfolding from a specified layer down to the input alphabet, whereas Claim 1 uses the same notation for a single-layer substitution at an arbitrary layer.

Questions for authors

Can the extracted formulas be used to find previously unseen inputs on which the model violates the target specification?

1 comment

We thank the reviewer for their response.

W3. Minor comment: the equivalence proof contains inconsistencies that require clarification. Definition 4 defines unfolding from a specified layer down to the input alphabet, whereas Claim 1 uses the same notation for a single-layer substitution at an arbitrary layer.

We agree with this observation. We have uploaded a new version of the document where a different notation is used to separate layer-wise unfolding from unfolding down to the input alphabet.

Q1. Can the extracted formulas be used to find previously unseen inputs on which the model violates the target specification?

Yes. The extracted formula ΦT\Phi_T is an exact encoding of the model, meaning that it satisfies exactly those sequences classified as positive by the model, and only those. Then, the logical difference between the extracted formula and the target formula corresponds to the inputs on which the model violates the target specification φ\varphi. In other words, any word satisfying (ΦT∧¬φ)∨(¬ΦT∧φ)(\Phi_T \land \neg\varphi) \lor (\neg\Phi_T \land \varphi) is a counterexample. An LTL−\mathrm{LTL}^{-} satisfiability checker such as BLACK returns one whenever it exists, whether or not it appears in the data. For example, the one-layer parenthesis models in Sec 4.1 accept ()), which is neither balanced nor prefix valid and is shorter than any of our training words.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.