Lattice Deduction Transformers
Liam Davis, Leopold Haller, Alberto Alfarano, Mark Santolucito · 2026
Read Lattice Deduction Transformers by Liam Davis, Leopold Haller, Alberto Alfarano, Mark Santolucito (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-08605.txt.
Introduction
Liam Davis, Leopold Haller, Alberto Alfarano, and Mark Santolucito build a small recurrent transformer that reasons by deduction. Between passes, the Lattice Deduction Transformer projects its inner state through a lattice, mimicking how a constraint solver narrows possible solutions. Training follows the solver's own search, guided by an abstract estimate of remaining candidates that works across domains.
A model under a million parameters solves the hardest Sudoku test sets fully and answers correctly or stays silent, never guessing wrong in the reported trials. A slightly larger version nearly masters a hard maze set where giant frontier models score zero. Efficient reasoning research gains a sound, abstaining alternative to scale alone.
Catalog record
| CREATOR | Liam Davis, Leopold Haller, Alberto Alfarano, Mark Santolucito |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.08605
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lattice Deduction Transformers Liam Davis, Leopold Haller, Alberto Alfarano, Mark Santolucito Abstract We introduce the Lattice Deduction Transformer (LDT), a recurrent transformer that approximates logically sound deduction by projecting its latent state through a lattice between forward passes. We train on-policy in a process that mirrors deduction in a search-based constraint solver and supervise training via a domain-agnostic, abstract-interpretation-based approximation of the set of solution candidates. An 800 800 K-parameter LDT achieves 100 % 100\% accuracy on Sudoku-Extreme and Snowflake Sudoku, at a fraction of the training cost of prior small recurrent reasoners, while remaining empirically sound: the model returns a correct answer or abstains. A 1.8 1.8 M-parameter variant reaches 99.9 % 99.9\% accuracy on Maze-Hard. Frontier LLMs score 0 % 0\% on all three benchmarks. LayerNorm Multi-Head Attention LayerNorm Feed Forward 4\times Lattice encoding Lattice encoding 16\times Branch 1234 \emptyset 123 124 134 234 12 13 14 23 24 34 1 2 3 4 Figure 1 : The Lattice Deduction Transformer (LDT) performs sound deduction on a lattice using a recurrent transformer which is alternated with search via stochastic branching. 1 Introduction Reasoning in large language models has become largely synonymous with the chain-of-thought paradigm 42 and its test-time-compute extensions 41 ; 34 , in which the model generates intermediate reasoning tokens before producing a final answer. In contrast, automated logical reasoning procedures operate in close analogy to discrete diffusion models 3 , by iterative refinement of a partial information state. In diffusion, information is partial in the sense that some tokens are masked; refinement proceeds by progressively unmasking them. We can then view logical solvers as a special case of discrete diffusion procedures that aim to recover an element of a uniform target distribution over valid solutions, in contrast to the broader, non-uniform distributions over plausible outputs more commonly studied in the diffusion literature. It is then natural to ask whether techniques developed in the automated-reasoning literature transfer to diffusion-style algorithms, and conversely. We consider reasoning from the perspective of abstract interpretation 9 ; 10 , which models information states as elements of a lattice with a top element \top representing no information (every solution still possible) and a bottom element \bot representing inconsistency (no solution remains). Deduction is a process that descends from \top toward more informative states; a state that collapses to \bot signals that no valid solution remains. The procedure is sound by design but incomplete: a deduction step may fail to derive a true fact, but never derives a false one. Concretely, we use a recurrent transformer whose latent state is projected to and from a lattice representation between forward passes; we call this the Lattice Deduction Transformer (LDT). The interpretability of the abstract domain lets us leverage symbolic search processes at both training and inference time. On hard problems with logical structure, LDT exceeds comparable reasoning transformers with smaller models and less training. On some domains it further achieves empirical soundness given a sufficient training budget: the search either returns a correct answer or abstains; it is never incorrect. We make four contributions. First, an architecture that projects a recurrent transformer’s latent state onto an abstract lattice at every iteration, turning each forward pass into a sound deduction step. Second, an on-policy training procedure where lattice states evolve under the model’s own forward pass, keeping training states in-distribution with search states encountered during inference. Third, the alpha operator , which aggregates the valid solutions still consistent with the current lattice state. This places our training in a regime we are not aware of in prior work: on-policy yet still supervised by a domain-agnostic, state-dependent target. Fourth, an experimental characterization of the train/test compute trade-off in learned sound inference, showing that additional training shortens inference search by orders of magnitude. The rest of the paper is organized as follows: Section 2 reviews related work. Section 3 provides relevant background on abstract interpretation and lattice structures. Section 4 details the architecture, training and inference of the Lattice Deduction Transformer. Section 5 provides an evaluation of the Lattice Deduction Transformer against comparable reasoning transformers and frontier LLMs. Finally, we conclude and discuss future directions in section 6 . 2 Related Work Our approach draws from research on small recurrent models that outperform far larger ones on hard reasoning problems. Adaptive Computation Time 21 introduced variable-iteration neural computation for recurrent networks, later adapted to transformers by Universal Transformers 14 . The Hierarchical Reasoning Model 38 uses a dual-loop recurrent architecture, and the Tiny Recursive Model 24 shows that a 2-layer network with recursion can outperform it with a smaller model. We build directly on Sotaku 26 , a recurrent transformer specialized for Sudoku. LDT can also be characterized as a neuro-symbolic method, combining a neural network with the lattice representation that search-based constraint solvers use to track partial information. SATNet 40 and Learning Modulo Theories 19 embed MAX-SAT and SMT solvers as network layers, preserving a hard neural/symbolic boundary. Closer to our setting, machine learning has been applied throughout the abstract-interpretation pipeline: Neural Abstract Interpretation 20 trains sound differentiable abstract transformers, LAIT 23 learns a neural policy that prunes redundant constraints, and SAIL 22 synthesizes sound transformers via LLMs with SMT validation. Earlier work targets the control loop instead, selecting among sound transformers via RL 33 or learning widening thresholds 5 . D3PM 3 , the discrete-diffusion generalization of masked language modeling 15 , iteratively commits information about partially-masked sequences; we recast this process as a fixed-point computation over a lattice. D3PM in fact admits an arbitrary token-transition matrix Q , which can be instantiated over tokens that themselves form a lattice – closely related in spirit to our setup, though we do not develop our method as a diffusion procedure. Several recent diffusion variants push in this direction. For example, ReMDM 39 reintroduces backtracking by allowing already-generated tokens to be remasked at inference time, Prime 6 relaxes the masked/unmasked dichotomy by letting tokens occupy intermediate states between \top and a concrete value, and HDLM 43 organizes the vocabulary into a refinement hierarchy whose forward process abstracts upward and reverse process refines downward. Each can be read as moving along a particular partial-information ordering; in our framing, that ordering is the lattice. 3 Abstract Interpretation Abstract interpretation, introduced by Cousot and Cousot 9 ; 10 , is a framework for sound approximate reasoning over systems where exact reasoning is computationally infeasible. Originally developed for program analysis, it replaces costly computation over a concrete domain C with efficient computation over an abstract domain A , while guaranteeing soundness : any property established in the abstract holds in the concrete. Soundness comes at a price: a reasoner over A may fail to derive a true fact even when one is provable in C , a loss of completeness . In finite domains, completeness can be restored via search procedures. Propositional satisfiability algorithms such as DPLL 12 ; 11 , CDCL 27 , and Stålmarck’s procedure 32 ; 25 can be cast as sophisticated search-based refinement operators on an abstract domain 17 ; 37 . In the canonical setting, the C and A are both lattices, with the order encoding precision (lower elements are more informative; \top the least