💻 computer science

On the (Intuitionistic) Logic of Next-Token Prediction

This paper models next-token prediction in autoregressive neural networks using intuitionistic implicational logic and the Curry-Howard correspondence, where token generation corresponds to modus ponens and sequence processing to constructive proof extension, ultimately deriving a neural architecture equivalent to multiplicative RNNs and validating its properties through specialized theorem provers.

Original authors: Paul Tarau (University of North Texas)

Published 2026-08-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Paul Tarau (University of North Texas)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to tell a story. You give it the first few words, and it has to guess the next one. Most modern robots, like the ones powering today's chatbots, do this by looking at the whole story so far and asking, "What word usually hangs out with these ones?" They use a giant spotlight called "attention" to scan the past words and find the best match. It's like a librarian who remembers every book ever written and finds the one that sounds most similar to the one you're holding.

But there's another way to think about this. Instead of just looking for similar words, what if the robot treated the story like a chain of logical steps? Imagine that every word isn't just a word, but a tiny instruction that changes the state of the story. If you say "The cat," that isn't just a description; it's a command that sets up a specific expectation for what comes next. In this view, predicting the next word is like solving a math puzzle or completing a proof: if you have the right starting conditions, the next step is the only logical thing that can happen. This paper dives into that idea, asking if we can build a robot that learns by following these logical chains rather than just mimicking patterns.

The Arrow Model: When Words Become Wrenches

In this paper, Paul Tarau proposes a fresh way to look at how AI predicts the next word in a sentence. He calls his new idea the Arrow Language Model. Instead of the usual method where the AI scans a huge list of past words to find similarities, Tarau suggests we treat the sequence of words as a logical proof.

Here is the core idea: Imagine you are building a tower out of blocks. In the old way (like Transformers), you look at the whole tower and ask, "What block fits best on top?" In Tarau's new way, every block you add is actually a special tool, like a wrench or a screwdriver. When you add a block, it doesn't just sit there; it changes the shape of the tower underneath it. The next block you add has to fit the new shape created by the previous one.

Tarau uses a branch of math called intuitionistic logic to describe this. In this logic, a sentence isn't just a list of words; it's a long, nested chain of "if-then" statements.

If you have the word "The," it sets up a condition.
If you add "cat," it changes that condition.
If you add "sits," it changes it again.

The paper suggests that predicting the next word is exactly like Modus Ponens, a famous rule of logic that says: "If I have 'If P then Q', and I have 'P', then I must have 'Q'." In the AI's brain, the current state of the sentence is the "If P then Q," and the new word is the "P." The result? The next word pops out as the "Q."

How the Machine Works

To make this work in a real computer, Tarau built a neural network where every word is an operator. Think of the AI's memory (its "hidden state") as a piece of clay.

In normal AI, words are like stickers you put on the clay.
In the Arrow Model, words are like hands that squeeze and twist the clay.

When the word "The" comes in, it twists the clay one way. When "cat" comes in, it twists it a different way. Because twisting the clay with "The" first and then "cat" creates a different shape than doing "cat" first and then "The," the order of words is built right into the math. You don't need to tell the computer "this word is first" or "this word is second" with extra codes; the twisting action naturally remembers the order.

The paper shows that this twisting action is mathematically the same as multiplying matrices (a way computers do math with grids of numbers). This makes the model very efficient. It doesn't need to look back at the whole history of the sentence every time; it just needs to know the current shape of the clay and apply the next twist.

The Experiments: Can It Learn?

The author tested this idea with a very specific goal: to see if the model could "memorize" a book by learning the logical structure of its sentences. They took public domain books (like War and Peace and Moby Dick) and fed them to the model.

To make sure the test was fair and clear, they didn't ask the model to write new stories. Instead, they asked it to finish sentences it had already seen.

The Setup: They gave the model a chunk of a sentence (like "The cat") and asked it to predict the rest.
The Logic Check: They also built a "logic robot" (using a programming language called Prolog) that could solve the same sentences using pure math rules.
The Result: The Arrow Model learned to predict the next words almost perfectly, matching the logic robot's answers.

The paper reports that the model could train on large books very quickly. For example, it took about 7 minutes and 52 seconds to train on War and Peace (which has over 560,000 words) using a standard computer graphics card. It could also finish a sentence in about 0.1 to 0.3 seconds.

What This Means (and What It Doesn't)

The paper suggests that we don't need the giant "spotlight" (attention) that most modern AI uses to understand order. Instead, order can be built directly into how the words change the AI's state. This offers a different, perhaps simpler, way to build language models.

However, the author is careful to point out the limits. This experiment worked because the AI was only asked to finish sentences it had already seen, like a student reciting a poem they memorized. The paper admits that this model might struggle if you give it a sentence with a typo, a missing word, or a weird phrasing it hasn't seen before. Real-world language is messy, and this "logical proof" approach is currently best at handling clean, exact patterns.

The author also notes that while this model is great at understanding order through twisting and turning, it doesn't yet handle the "big picture" connections that the spotlight method does. It's a promising new direction, suggesting that the future of AI might not just be about finding similar words, but about understanding how each word logically transforms the story.

In short, this paper proposes that the secret to predicting the next word isn't just remembering the past, but treating every word as a tool that reshapes the future. It's a playful, logical, and mathematically elegant way to think about how machines might learn to speak.

Technical Summary: On the (Intuitionistic) Logic of Next-Token Prediction

Problem Statement

The paper addresses the lack of logical transparency in current foundational Generative AI models, particularly Transformers. While Transformers effectively learn next-token prediction via unsupervised training on massive datasets, their reliance on positional encodings and similarity-based attention mechanisms obscures the underlying logical structure of sequence prediction. The author posits that the task of predicting the next token can be reinterpreted not merely as statistical pattern matching, but as a constructive proof completion task within intuitionistic implicational logic. The core challenge is to derive a neural architecture that naturally embodies this logical interpretation, replacing attention mechanisms with operator composition that intrinsically encodes order.

Methodology

1. Logical Formalism: Left-Nested Implication

The author proposes modeling token sequences as left-nested intuitionistic implications. Unlike right-nested implications (which collapse to conjunctions and are permutation-invariant), left-nested implications preserve order sensitivity.

Representation: A sequence of tokens $w_1, \dots, w_n$ is encoded as $L_n = ((((w_1 \to w_2) \to w_3) \to \dots) \to w_n)$ .
Inference Mechanism: Next-token prediction is mapped to Modus Ponens. Given a prefix implication $I_p$ and a full implication $I_f = (I_p \to w)$ , predicting $w$ corresponds to the elimination step $I_f \to (I_p \to I_f) \to w$ .
Curry-Howard Correspondence: Under this isomorphism, propositions are types, proofs are $\lambda$ -terms, and next-token prediction is the construction of a term inhabiting an implicational type. The process of predicting a sequence is viewed as successive $\beta$ -reductions (state updates).

2. Theoretical Tools

The author utilizes Roy Dyckhoff's LJT calculus, a sequent calculus for propositional intuitionistic logic restricted to the implicational fragment. They implement specialized theorem provers in Prolog (lprove/2) to:

Validate the soundness of the logical encoding.
Demonstrate that order is preserved in left-nested chains (e.g., $((p \to q) \to r)$ is not equivalent to $((q \to p) \to r)$ ).
Perform information retrieval by treating sentence fragments as subformulas (suffixes of prefixes) of stored implication chains.

3. Neural Architecture: The Arrow Language Model

The paper derives a recurrent neural architecture, the Arrow Model, which serves as a numeric realization of the logical proof construction.

Hidden State as Proof Context: The hidden state $h_t \in \mathbb{R}^d$ represents the accumulated proof context (assumptions and justifications) after processing a prefix.
Tokens as Operators: Instead of additive embeddings, each token $t$ acts as a linear operator $M_t: \mathbb{R}^d \to \mathbb{R}^d$ that transforms the current state.
Low-Rank Parameterization: To handle large vocabularies efficiently, the operator is defined as $M_t = I + U \text{diag}(s_t) V^\top$ , where $U, V$ are shared matrices and $s_t$ is a token-specific gate vector derived from embeddings.
State Update (Modus Ponens): The recurrence relation implements implication elimination:
$h_{t+1} = \text{LayerNorm}(h_t + U((V^\top h_t) \odot s_t))$
This update is non-commutative ( $M_a M_b \neq M_b M_a$ ), meaning token order is encoded intrinsically by the algebra of operator composition, eliminating the need for explicit positional encodings.
Training: The model uses standard next-token cross-entropy with teacher forcing. To manage memory for large vocabularies, loss is computed in a streaming fashion.

Key Contributions

Logical Interpretation of Next-Token Prediction: The paper establishes a formal correspondence where next-token prediction is equivalent to constructive proof extension (Modus Ponens) in intuitionistic implicational logic.
Derivation of the Arrow Model: A novel recurrent architecture is derived directly from the proof-theoretic interpretation, where tokens function as state-transforming operators rather than static embeddings.
Order Sensitivity without Positional Encodings: The model demonstrates that non-commutative operator composition inherently encodes sequence order, offering an alternative to the positional encoding strategies used in Transformers.
Symbolic-Neural Retrieval Framework: The author demonstrates a unified framework where both symbolic retrieval (via Prolog theorem proving on implication chains) and neural retrieval (via the Arrow model) operate on the same underlying logical structure.

Experimental Results

The author conducted experiments to validate the logic-based algorithms and their neural equivalents using public-domain texts from Project Gutenberg.

Setup: The experiments utilized a "Sanity Check" regime where the models were trained to overfit small corpora (e.g., The Wizard of Oz, Moby Dick) to verify learning capacity and architectural efficiency.
Data Augmentation: To mimic the logic-level retrieval of subformulas, the training set was augmented with all contiguous fragments of sentences.
Performance:
- Training Efficiency: The Arrow model trained on large documents (e.g., War and Peace with ~560k words) in under 8 minutes on a single consumer GPU (RTX 3090).
- Inference: The retrieval-first pipeline (candidate enumeration followed by neural scoring) achieved inference times of 0.1–0.3 seconds per query, largely independent of the total corpus size.
- Symbolic Baseline: The Prolog-based retrieval system demonstrated fast database initialization (1–2 seconds) and interactive query times (~0.5 seconds), confirming the feasibility of using logic-level retrieval as an interpretable baseline.

Significance and Claims

The paper presents the Arrow Language Model as a logic-first foundation for next-token prediction that is distinct from similarity-based attention (Transformers) and convolution/state-space alternatives.

Explanatory Power: By mapping neural operations to proof-theoretic concepts (implication elimination, $\beta$ -reduction), the model offers an explanatory connection between neural dynamics and symbolic reasoning that Transformers lack.
Architectural Perspective: The Arrow Model is positioned as a logic-driven alternative for tasks where order sensitivity and constructive proof extension are paramount, though the author explicitly notes it is not yet a drop-in replacement for foundational models in general settings.
Limitations: The author acknowledges that the current work focuses on exact contiguous substructures. It does not yet address the robustness requirements of modern language modeling, such as handling misspellings, paraphrases, or non-contiguous evidence, which are areas for future work.
Future Directions: The paper identifies the emulation of Transformer-style inference (approximate matching) using similar logic-based techniques as a central open challenge.

The work is presented as a step toward "alternatives to transformer-based foundational models," grounded in the intuition that the logical structure of sequence prediction can be made explicit and constructive through intuitionistic logic.