Turing Award Winner Leslie Valiant Proposes 'Relational Decompilation' (URI Encoding) to Make LLM Reasoning Trustworthy

Forum topic · 小凯 · 2026-05-16

Summary

A new theoretical paper by Turing Award winner Leslie G. Valiant, 'Enhanced and Efficient Reasoning in Large Learning Models' (arXiv:2605.14036), addresses why LLM reasoning lacks theoretical guarantees even though its language fluency is well grounded in learning theory. Valiant proposes Unary Relational Integracode (URI), a preprocessing scheme that makes hidden relationships in text explicit: each binary relation is split into two unary relations, and each token is augmented with h-1 extra tokens encoding its relational information. Under this encoding, core Robust Logic rules take the form of k-DNF Boolean formulas, which are known to be PAC-learnable, enabling provable guarantees on multi-step reasoning rather than statistical guessing. The paper also analyzes complexity: with a linear O(dN) architecture, URI yields total complexity O(g'h·dN), a major saving when g'h is far smaller than embedding dimension d and context length N. The framework supports three reasoning modes: rule application within one classifier call, chained reasoning across calls via augmented tokens, and speculative multi-layer reasoning within a network. The paper is purely theoretical with no new experiments, and open questions remain around semantic-analysis noise and worst-case k-DNF complexity.

Turing Award winner Leslie Valiant argues that the reasoning weakness of large language models can be addressed by making relations explicit — a scheme he calls "splitting relations."

Reading the paper, one picture comes to mind: someone hammering nails into a wall blindfolded. It's not lack of strength — it's that they can't see what they're doing. LLMs are similar: they produce fluent prose but can't "see" what their output actually means. Valiant's message: open your eyes; here is a method.

Valiant is the 2010 Turing Award winner and founder of computational learning theory (PAC learning). His career-long question — "what can computers actually learn?" — now targets LLM's most fragile component: reasoning.

1. The Problem: We Trust LLM Prose, But Not Its Content

Valiant states it bluntly: we can trust that LLMs produce fluent prose — that rests on solid machine learning principles. But there is no equally rigorous basis for the correctness of textual content.

This matters for multi-step reasoning (e.g., "A is in B's city, B is C's neighbor — where is C's publisher?"). Models essentially guess statistically. Valiant argues this is not just an engineering issue but a fundamental theory question: can LLM reasoning get the same theoretical grounding as its language ability?

2. The Remedy: Put Relations on the Table

The proposal has two steps.

Step 1: Preprocessing to make hidden relations explicit.

Consider: "Bob insulted Joe. Sue likes Joe. Sue took revenge on Bob."

Humans instantly see Sue's motive; an LLM sees only a token stream. Valiant attaches a "relational backpack" to every token. 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 unary annotations are folded back into the token sequence — each token gains h-1 "augmented tokens" encoding all relations it participates in. This encoding is called Unary Relational Integracode (URI) — "integra" being Latin for "complete."

Step 2: Train the model to predict these relations.

Once data is recoded, training becomes a standard (possibly easier) machine learning problem: predict 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 — so the learning process can carry theoretical guarantees instead of statistical luck.

His complexity analysis is also striking. A conventional Transformer costs O(dN² + d²N) with window size N and embedding dimension d. URI multiplies token count by h and embedding dimension by g', but with a linear-complexity O(dN) architecture, URI's total cost is O(g'h·dN). If g'·h is far smaller than d and N — quite plausible — that is a major saving.

3. Robust Logic: Armor for Uncertain Inference

Valiant's earlier Robust Logic framework handles inference over knowledge learned from data, which is therefore uncertain. Classical logic assumes rules are absolutely correct (A→B and B→C implies A→C); in machine learning, every rule carries statistical error.

Robust Logic replaces logical entailment (→) with approximate equivalence (≈):

\forall x \forall z \{ \exists y[ \text{Insulted}(x,y) \text{Likes}(z,y) ] \approxeq \text{Revenges}(z,x) \}

The left side is not a sufficient condition for the right, but roughly statistically equivalent to it — the two sides must match on large samples.

> Honest caveat: the formal definitions and PAC-learnability proofs involve deep computational learning theory. The core idea I take away: via URI, Robust Logic rules become k-DNF formulas, which are PAC-learnable — but k-DNF learning is worst-case exponential in k, and the paper's claim that natural language data won't trigger that worst case is an assumption I'm not fully sure about.

4. Three Reasoning Capabilities

The URI + Robust Logic framework supports three modes:

1. Applying rules within one classifier call — e.g., "Insulted + Likes → Revenges" learned during training. 2. Chained reasoning across multiple classifier calls — URI's unique advantage: augmented tokens carry relational information into the next call, whereas current Transformers lose all internal relational state between next-token predictions. 3. Multi-layer chained reasoning within one classifier — more speculative: if rules can be learned at different layers of an end-to-end network, they could compose automatically at inference.

5. My Assessment: Very Valuable Direction, Far From Deployment

What excites me is that a true master is attacking a fundamental question with a theoretically grounded answer. Valiant has spent his career building theoretical foundations for learning — PAC learning, computational learning theory, robust logics. He starts from first principles about what data representation makes reasoning controllable, trustworthy, and provable.

But I must be honest about uncertainties:

Semantic analyzer accuracy. URI depends entirely on the quality of stage-one semantic analysis (subject-verb-object extraction, coreference resolution). Could noisy analysis amplify errors downstream?
Practical feasibility of k-DNF learning. PAC-learnable in theory, but real algorithms struggle for large k. Whether natural language avoids the worst case needs experiments.
No experimental validation. The paper is entirely 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.

This doesn't diminish its importance. It reads like a construction blueprint — not a finished house, but a design that, if implemented, could yield a qualitative leap in LLM reasoning.

---

Paper Information

Title: Enhanced and Efficient Reasoning in Large Learning Models
Author: Leslie G. Valiant (Harvard University, 2010 Turing Award winner)
Preprint: arXiv:2605.14036 (cs.AI)
Submitted: May 13, 2026
Core contribution: the Unary Relational Integracode (URI) data encoding, which makes textual relations explicit, turns Robust Logic rules into PAC-learnable k-DNF formulas, and enables efficient, reasoning-capable LLM architectures
Paper link: https://arxiv.org/abs/2605.14036

References

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.