Turing Award laureate Leslie Valiant argues that the LLM reasoning problem can be addressed by 'splitting relations' — making hidden relational structure in text explicit so that reasoning gains the same theoretical grounding that language fluency already has.
Reading the paper, one image comes to mind: someone hammering nails into a wall, but every swing misses. Not for lack of strength — they're hammering with their eyes closed. LLMs are like that: they write fluent paragraphs, but they can't 'see' what their output actually means. Valiant says: open your eyes; here's a method.
About the Author
Leslie Valiant, 2010 Turing Award winner and founder of computational learning theory (PAC Learning), has spent his career asking: 'What can computers actually learn?' Now he targets the most fragile link in LLMs — reasoning.
1. The Problem: We Trust LLM Prose, Not Its Content
Valiant states it bluntly: we can trust that LLMs produce fluent prose — that is defensible on machine learning principles — but there is no equally rigorous basis for the correctness of the content.
When we ask an LLM to do multi-step reasoning (e.g., 'A is in B's city, B is C's neighbor, where is C's publisher?'), the model is essentially guessing. The traditional fix is more data, parameters, and compute, hoping the model guesses right statistically.
Valiant says no — this is a fundamental theoretical question: can LLM reasoning rest on theory as firm as its language capability?
2. The Remedy: Put Relations on the Table
The scheme has two steps.
Step 1: Preprocessing — make hidden relations explicit.
Take: 'Bob insulted Joe. Sue likes Joe. Sue took revenge on Bob.' A human instantly sees Sue's motive; an LLM sees a token stream. Valiant proposes attaching a 'relation backpack' to each token, containing that token's relations to others.
Concretely, each binary relation is split into two unary relations: Insulted(Bob, Joe) becomes Insulted1(Bob) and Insulted2(Joe); Likes(Sue, Joe) becomes Likes1(Sue) and Likes2(Joe). These annotations are inserted back into the token sequence — each token gains h-1 'augmented tokens' carrying encodings of all relations it participates in. The encoding is called Unary Relational Integracode (URI) — 'integra' from Latin, meaning complete.
Step 2: Train the model to predict these relations.
Once data is re-encoded, training becomes a standard (and possibly easier) machine learning problem: predicting which unary relations hold at each position.
Valiant proves a key result: under URI encoding, core Robust Logic rules take the form of k-DNF Boolean formulas, and k-DNF is PAC-learnable — meaning the learning process can carry theoretical guarantees instead of statistical guesswork.
His complexity analysis is also notable. A traditional Transformer costs O(dN² + d²N), where N is window size and d embedding dimension. URI expands token count by h and dimension by g', but with a linear O(dN) architecture, URI's total cost is O(g'h·dN). If g'·h is much smaller than d and N — a reasonable assumption — the savings are substantial.
3. Robust Logic: Armor for Uncertain Inference
Valiant's earlier Robust Logic framework handles reasoning with knowledge learned from data, which is therefore uncertain. Classical logic assumes rules are absolutely correct; machine learning rules carry statistical error.
Robust Logic replaces implication (→) with an approximate equivalence (≈) relation:
The left side is not a sufficient condition for the right but 'roughly equivalent' to it: the two must statistically match on large samples in both directions.
> Author's note: I am less certain about this section. The formal definitions and PAC-learnability proofs involve deep computational learning theory. My core understanding: via URI, Robust Logic rules become k-DNF, which is PAC-learnable — but k-DNF learning can be exponential in k in the worst case, and the paper claims natural language data won't trigger that worst case. Whether that assumption holds, I'm unsure.
4. Three Reasoning Capabilities
1. Applying rules within one classifier call — rules learned in training (e.g., 'Insulted + Likes → Revenges') used directly at inference. 2. Chained reasoning across classifier calls — URI's unique advantage: augmented tokens carry relational information into the next call, whereas current Transformers lose internal relational state between next-token predictions. 3. Multi-layer chained reasoning within one classifier — a more speculative idea: rules learned at different layers of an end-to-end network could compose automatically at inference.
5. My Verdict: Valuable Direction, Far from Deployment
What excites me is that this comes from a true master thinking about a fundamental problem with a theoretically grounded answer. Valiant has spent his life building foundations for learning — PAC learning, computational learning theory, robust logics. He approaches from first principles: what data representation do we need to make reasoning controllable, trustworthy, and provable?
But I must honestly flag my uncertainties:
- Semantic analyzer precision. URI's effectiveness depends entirely on the quality of the first-stage semantic analysis (subject-verb-object extraction, coreference resolution). Would noisy analysis compound downstream?
- Practical feasibility of k-DNF learning. k-DNF is PAC-learnable in theory, but real algorithms face computational challenges at large k. Whether natural language avoids the worst case needs experiments.
- Lack of experimental validation. The paper is purely theoretical — no new experiments. It builds on Valiant's small-scale 2019 Knowledge Infusion experiment, which did not use URI. URI's effectiveness remains a theoretical hypothesis.
- Title: Enhanced and Efficient Reasoning in Large Learning Models
- Author: Leslie G. Valiant (Harvard University, 2010 Turing Award laureate)
- Preprint: arXiv:2605.14036 (cs.AI)
- Submitted: May 13, 2026
- Core contribution: proposes Unary Relational Integracode (URI), a data encoding that makes textual relations explicit, transforming Robust Logic rules into PAC-learnable k-DNF formulas for efficient, reason-capable LLM architectures
- Link: https://arxiv.org/abs/2605.14036
Still, this is an important paper — a construction blueprint, not a finished house. It says: if we design this way, we should be able to build a sturdier house. If anyone builds an efficient implementation on this blueprint, it could be a qualitative leap in LLM reasoning.
---
Paper Information
1. Valiant, L.G. (2026). Enhanced and Efficient Reasoning in Large Learning Models. arXiv:2605.14036. 2. Valiant, L.G. (2014). Robust Logics. 3. Valiant, L.G. (2024). The Importance of Being Educable. Princeton University Press. 4. Valiant, L.G. (1984). A Theory of the Learnable. *Communications of the ACM*, 27(11):1134–1142. 5. Valiant, L.G. (2019). A First Experimental Demonstration of Massive Knowledge Infusion.