Modeling Next-Token Prediction as Left-Nested Intuitionistic Implication
PAUL TARAU · 2026
Read Modeling Next-Token Prediction as Left-Nested Intuitionistic Implication by PAUL TARAU (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-2601-19915.txt.
Introduction
Paul Tarau reimagines the architecture of language models through the lens of logic. Standard models encode word order by adding position signals to token vectors and mixing them with attention. Tarau instead reads next-token prediction as intuitionistic implication, a constructive form of logical deduction. The prefix of a sentence becomes a chain of implications.
His Arrow Language Model encodes that chain directly. Each token implies the next in a left-nested structure. Order is preserved by non-commutative composition, meaning the chain cannot be shuffled without changing meaning. The design tests whether logical structure can replace attention's mixing. It is a conceptual probe as much as a practical model. Such probes clarify what mainstream architectures actually rely on.
Catalog record
| CREATOR | PAUL TARAU |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-19915
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Modeling Next-Token Prediction as Left-Nested Intuitionistic Implication PAUL TARAU Abstract We introduce the Arrow Language Model , a neural architecture derived from an intuitionistic-logic interpretation of next-token prediction. Instead of representing tokens as additive embeddings mixed by attention, we encode a prefix as a left-nested implication chain whose structure preserves order through non-commutative composition. Next-token prediction corresponds to modus ponens , and sequence processing becomes constructive proof extension under the Curry–Howard correspondence. Our Prolog-based specialized theorem provers validate fundamental properties of the neural models, among which relations between commutative vs. non-commutative sequencing and single-token vs. multi-token prediction choices. We show that a neural architecture equivalent to multiplicative RNNs arises naturally from a proof-theoretic interpretation of next-token prediction as nested intuitionistic implication, we present a practical low-rank neural realization and position the model relative to Transformers and state-space models. Keywords: logic-based derivation of neural architectures, intuitionistic implicational logic, token-as-operator neural models, state-space models, alternatives to transformer-based foundational models. \lst@SaveOutputDef ‘_ \underscore@prolog 1 Introduction Foundational Generative AI models involve mechanisms like next token(s) prediction that naturally benefit from unsupervised training on very large data sets at a scale closely matching the total multi-modal content of the internet. The resulting distribution, encapsulated in the parametric memory of the model, constructively completes the initial sequence derived from the prompt and subsequently generated tokens with a set of probability-weighted next token candidates. The underlying logic of the derivation of the next token hints to an intuitionistic implicational logic proof of q seen as an implication from assumptions in context E , E\rightarrow q . This is can be stated as finding a way to transform a proof of an assumption context E into a proof of a consequence q . In the neural world this materializes as a transformation of the overall statistical evidence for E into a predicted probability for q . In the case of the transformer models Vaswani et al., 2017 , order information is learned via dedicated positional encodings that complement the parallel attention heads that learn deep dependencies relating to the “past” token sets while having the set of “future tokens” masked. This is a highly effective approach, but it obscures the logical structure of sequence prediction and provides little explanatory connection to symbolic reasoning. We will explore here an alternative view: next-token prediction as implication completion. We ask whether the task of predicting the next word in a sequence can be understood as extending a proof in intuitionistic propositional logic—and whether this interpretation leads naturally to a viable neural architecture. Our answer is affirmative. Starting from a symbolic encoding of sequences as left-nested intuitionistic implications, we derive a recurrent neural model in which each token acts as an operator transforming a proof state. The resulting architecture, which we call the Arrow Language Model , replaces similarity-based attention with non-commutative operator composition as the carrier of both semantic content and order. Our logic-based insights will also be extended to cover multi-token prediction and it naturally relates to type inference and type inhabitation via the Curry-Howard isomorphism. The rest of the paper is organized as follows. Section 2 introduces our theorem provers for propositional implicational intuitionistic logic. Section 3 justifies our choice of the logic formalism modeling content and order in the next token prediction. Section 4 illustrates instances of valid formulas relating left-nested implicational sequences, relevant for the next word(s) prediction task. Section 5 introduces an information retrieval mechanism by using implicational logic subformulas derived from a corpus split into sentences. Section 6 describes the a neural realization of the derived Arrow Architecture . Section 7 describes our experiments involving validation of our logic-based algorithms and their neural equivalents. Section 8 discusses limitations and future work directions. Section 9 overviews related work. Section 10 concludes the paper. Our full open-source code is available at https://github.com/ptarau/nextword . The literate Prolog code extracted from this paper is at https://github.com/ptarau/nextword/blob/main/nextword.pro . 2 Our tools : implicational intuitionistic logic theorem provers We will start by motivating our choice of a purely symbolic logic representation that does not involve reliance on numerical implementations of ordering. Implicational propositional logic allows reasoning, when seen as a Hilbert system with modus-ponens as its only inference rule: and with as little as two axioms corresponding via the Curry-Howard isomorphism to combinators K and S: K combinator: p->q->p S combinator: (p->q->r)->(p->q)->p->r For the same formalism, when seen via the sequent calculus, simple and efficient theorem provers become available. We will introduce them next as they will be used to support our logical inference mechanisms. The predicate iprove implements Roy Dyckhoff’s LJT calculus, restricted to the implicational fragment of propositional intuitionistic logic, proven as sound and complete in Dyckhoff, 1992 . LJT_{1}:\penalty\ \penalty\ \penalty\ \penalty\ \frac{\penalty\ }{A,\Gamma\penalty\ \vdash\penalty\ A}\\ \\ LJT_{2}:\penalty\ \penalty\ \penalty\ \penalty\ \frac{A,\Gamma\penalty\ \vdash\penalty\ B}{\Gamma\penalty\ \vdash\penalty\ A\rightarrow B}\\ \\ LJT_{3}:\penalty\ \penalty\ \penalty\ \penalty\ \frac{B,A,\Gamma\penalty\ \vdash\penalty\ G}{A\rightarrow B,A,\Gamma\penalty\ \vdash\penalty\ G}\\ \\ LJT_{4}:\penalty\ \penalty\ \penalty\ \penalty\ \frac{D\rightarrow B,\Gamma\penalty\ \vdash\penalty\ C\rightarrow D\penalty\ \penalty\ \penalty\ \penalty\ B,\Gamma\penalty\ \vdash\penalty\ G}{\left(C\rightarrow D\right)\rightarrow B,\Gamma\penalty\ \vdash\penalty\ G}\\ Termination is ensured as one can identify a multiset ordering-based size definition that decreases after each step Dyckhoff, 1992 . ⬇ iprove(T ) :- iprove(T , []) . iprove(A , Vs ) :- memberchk(A , Vs ) , ! . iprove((A -> B ) , Vs ) :- ! , iprove(B , [ A | Vs ]) . iprove(G , Vs1 ) :- select((A -> B ) , Vs1 , Vs2 ) , iprove_imp(A , B , Vs2 ) , ! , iprove(G , [ B | Vs2 ]) . iprove_imp((C -> D ) , B , Vs ) :- ! , iprove((C -> D ) , [ (D->B )| Vs ]) . iprove_imp(A , _ , Vs ) :- memberchk(A , Vs ) . The predicate lprove adds generation of a proof term by introducing lambda terms l(X,E) with lambda variable X and expression E , and a(A,B) representing application of a source A to target B . ⬇ %% X is the proof term of T %% or , via Curry-Howard , X:T holds when X is an inhabitant of the type T lprove(T , X ) :- lprove(X , T , []) , ! . lprove(X , A , Vs ) :- memberchk(X : A , Vs ) , ! . % leaf variable lprove(l(X , E ) , (A->B ) , Vs ) :- ! , lprove(E , B , [ X : A | Vs ]) . % introduce lambda term lprove(E , G , Vs1 ) :- select(S : (A->B ) , Vs1 , Vs2 ) , % source of application lprove_imp(T , A , B , Vs2 ) , % target of application ! , lprove(E , G , [ a(S , T ): B | Vs2 ]) . % apply source to traget lprove_imp(l(X , E ) , (C->D ) , B , Vs ) :- ! , lprove(E , (C->D ) , [ X : (D->B )| Vs ]) . lprove_imp(E , A , _ , Vs ) :- memberchk(E : A , Vs ) . 3 Content and order in propositional intuitionistic implicational logic Next we will express the “next token prediction” as logical inference in implicational intuitionistic logic. Thus,