acceptodds
Under review as a conference paper at ICLR 2027

Certifying Multi-Step Logical Computation in Fixed-Parameter Transformers

Abstract

A language model can answer a logical question correctly without necessarily executing the reasoning process that justifies the answer. We study conditions under which a fixed-parameter Transformer can be certified to perform finite-step Horn-rule deduction during inference. We first give sufficient conditions for consistent variable binding, showing that shared state reads together with attention-score separation ensure that repeated occurrences of a variable refer to the same entity across the premises of a rule. We then construct invariant neighborhoods of logical fact assignments using update errors at reference states and bounds on the corresponding Jacobians. These neighborhoods guarantee that derived facts remain available across successive reasoning steps, while local dependency structure can reduce reference-state verification to combinations of only the relevant facts. We further construct fixed-parameter Transformer templates using finite-temperature softmax, RMS normalization, and SiLU that internally enumerate substitutions, read both current and previously derived facts, and update the logical state. Rule templates are shared across substitutions, so the parameters and caches need not store an expanded list of ground rule instances. We give explicit bounds on representation size, parameter count, verification cost, and substitution-enumeration time, and show that the same parameters and invariant neighborhoods support every finite number of repeated scans. The resulting guarantees imply soundness and, under rule coverage, bounded completeness. Numerical experiments confirm stable logical-state execution over long repeated runs and illustrate the reduction in representation storage without eliminating substitution-enumeration cost.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Logical Reasoning, Formal Verification, Neurosymbolic AI

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_eDMqOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies whether a fixed-parameter Transformer can be formally certified to execute multi-step Horn-rule deduction during inference. The experimental evaluation includes numerical tests of the proposed update construction, comparisons of storage and substitution-enumeration costs, synthetic logical interventions, and exploratory interventions on a pretrained Mistral model. Overall, the paper aims to establish a formal connection between neural computation and multi-step symbolic reasoning. However, the technical development is highly dense, and I found it difficult to follow the overall argument and assess whether the stated guarantees are sufficiently supported by the assumptions and verification procedures.

Critical strengths
  • An important theoretical question: The paper addresses the distinction between producing correct logical answers and actually implementing logical reasoning through a model's internal computation. Establishing this distinction formally is a meaningful research direction, particularly for understanding the reasoning mechanisms of Transformers.
  • An ambitious attempt at formal guarantees: The authors attempt to provide explicit sufficient conditions and quantitative bounds for persistent logical computation, including the effects of finite-temperature attention, normalization, and nonlinear activations. If the proposed construction and guarantees can be clearly established, they could provide useful theoretical insights into Transformer-based logical computation.
Critical weaknesses

My primary concern is the presentation and organization of the theoretical development. The paper is exceptionally dense, introducing many definitions, assumptions, mathematical objects, and technical results in rapid succession, without sufficient intuition or explanation of how they fit together.

In particular, Sections 3–6 develop several seemingly distinct components: variable-binding consistency, invariant-neighborhood certificates, an explicit Transformer construction, and logical and causal consequences. However, the relationships and dependencies among these components are not sufficiently clear. For example, Theorem 2 studies invariant neighborhoods under fixed blockwise rule selection, while Theorem 5 introduces internal substitution enumeration and relies on a separate direct box-inclusion argument. Although this distinction is mentioned, it is difficult to understand how the various theoretical results combine into a unified certification framework, and which conditions are essential for the main claims.

Moreover, many crucial technical details are distributed across lengthy appendices. The presentation often moves directly from complicated definitions to formal bounds without providing enough intuition, intermediate explanation, or a simple running example. This makes it extremely difficult to follow the logical progression of the arguments.

This is not merely a matter of writing style. For a paper whose main contribution is a formal certification framework, the ability to independently inspect and verify the proposed guarantees is essential. Despite substantial effort, I found it difficult to reliably check the central claims and understand exactly how the stated assumptions lead to the advertised guarantees. I cannot identify a definitive mathematical counterexample, but the current presentation prevents me from developing sufficient confidence in the overall theoretical argument.

Questions for authors

Could the authors explain more explicitly how Theorems 1, 2, 5, 6, and 7 relate to one another? In particular, which results are required to establish the complete end-to-end guarantee of the constructed Transformer, and which provide alternative or independent sufficient conditions?

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

This paper develops a formal framework for certifying multi-step Horn-rule deduction in fixed-parameter Transformers. It combines shared-register binding, invariant neighborhoods, and shared templates with SiLU correction to preserve logical states and reuse derived facts. The theory shows when the model can reason correctly over multiple steps and when different ways of making the same logical edit have the same effect on its answer. The experiments test the proposed construction and explore whether editing Mistral’s hidden states changes its answers as expected from the underlying logic.

Critical strengths

The contributions form a coherent theoretical framework connecting native Transformer operations to logical guarantees. The theoretical depth and completeness are strong, and the experiments provide useful support for the constructions. Overall, I lean toward acceptance.

Critical weaknesses

The robustness of the pretrained-model results remains unclear: although all ten seeds are included in the aggregate, only one satisfies all development criteria. Theorem 2 also assumes fixed blockwise rule selection and does not directly cover general state-dependent control; this scope restriction should be emphasized.

Questions for authors
  1. Could the authors summarize the development acceptance criteria from Appendix in the main text and report nonzero and zero-effect agreement separately for each of the ten seeds?
  2. Could the authors provide prototype verification results for a program with 50–100 atoms, including local dependency-set sizes, Jacobian-bound estimates, and total verification time?
Reviewer_s3cLOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies if Transformer models can carry out specific logical computations internally. They show that softmax transformers can follow a specified Horn-rule evaluation. They therefore develop a correspondence between the neural states of a transformer and the evaluation of Horn formulas. They then construct transformer models to implement this correspondence und show that the constructed system is numerical stable and give storage requirements for their translation. They complement their theoretical findings with experiments, which on the one hand test their hand-crafted transformer models on test inputs and also test on a pretrained Mistral model.

Critical strengths
  • The study of the theoretical capabilities of transformer models is a timely and important topic in general.
  • The paper gives a detailed construction covering real-world implementation details like softmax, RMS normalization and SiLU activation functions.
  • Caring about the intermediate computation and the effects of internal interventions instead of only focussing on the output is a interesting research direction.
Critical weaknesses
  1. I found it difficult to follow how the definitions and results build toward the central contribution. Terms such as "original decoder execution", "native boundary", "register transport", or "exact executable abstraction" are introduced before the reader has a concrete intuitive picture of what the actual plan of the paper is. It is often difficult to distinguish what is assumed, what is supplied by the construction and what is actually proved. Addtionally the mathematics is pretty compressed. Several intuitive ideas are hidden in layers of notation with little explanation. This makes following the arguments and ideas hard.
  2. My main concern regarding the results is that the paper does not convincingly explain what the actual new contribution is. The transformer is constructed for a fixed Horn program and a fixed finite domain. This immediately gives a fixed upper bound on the number of steps the transformer has to make independently of the initial facts. From a computability standpoint this means that you construct a transformer which can execute a particular bounded algorithm. But there are several more general results on the simulation of programs with softmax transformers. For example Brösamle & Eckstein (2026) show that softmax transformer with low precision can simulate arbitrary turing machines for a fixed number of steps. While this does not directly establish the present paper's exact architectural and robustness guarantees, it leaves unclear where the substantive new contribution lies.
  3. The experiments offer limited evidence beyond checking the papers own construction. The first three experiment blocks mainly verify the expected properties of the system explicitly designed to have these properties. The Mistral experiment trains a model to modify hidden states so that the answer of the Mistral model changes as expected under a logical edit. However, the trained model gets the intervention category as input and each category determines the desired final answer. Therefore, the trained model could just learn to change Mistrals output to Yes resp. No without the need of changing the actual logical computation.

Overall due to my main concerns regarding the novelty of the theoretical results, the unconvincing experiments and the poor exposition of the paper, I recommend rejection.

Brösamle, M. & Eckstein, S.. (2026). The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:9933-10000 Available from https://proceedings.mlr.press/v306/brosamle26a.html.

Questions for authors

Please comment on the Weaknesses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.