Can Machines Reason?

Part I: Is the Appearance of Reasoning Effectively Reasoning?

The Functionalist Thesis

This question maps precisely onto the central debate in philosophy of mind between functionalism and its critics. The functionalist position — articulated most forcefully by Putnam (1967) and Dennett (1987) — holds that mental states are defined exhaustively by their functional roles: their causal relations to inputs, outputs, and other internal states. Under strict functionalism, if a system $\mathcal{S}$ produces input-output mappings $f:\mathcal{X}\to \mathcal{Y}$ that are indistinguishable from those produced by a known reasoner $\mathcal{R}$ across all possible inputs, then $\mathcal{S}$ is reasoning, definitionally. There is no residual "ghost" to account for.

This is a serious position, and it deserves honest engagement. The strongest version of the argument runs as follows:

Claim: If $\forall x\in \mathcal{X}:\mathcal{S}\left(x\right)=\mathcal{R}\left(x\right)$, and this equivalence holds not merely over a test set but over the entire input domain including adversarial, out-of-distribution, and counterfactual queries, then the distinction between "real" and "simulated" reasoning is metaphysically vacuous.

There is genuine force here. If no experiment — no matter how cleverly designed — can distinguish the two systems, then insisting on a difference amounts to positing an unobservable, unfalsifiable property. This is precisely the epistemological territory of the Turing Test.

The Counter-Arguments

However, there are several rigorous objections that resist easy dismissal:

1. Distributional Completeness Is Unachievable in Practice

The functionalist argument requires equivalence over all possible inputs. But the space of possible queries is countably infinite (and, if we permit variable-length inputs, effectively unbounded). No finite training corpus $\mathcal{D}$ can cover this space. The model's behavior on the complement $\mathcal{X}\setminus \mathcal{D}$ is determined by the inductive biases of the architecture and optimizer — and there is no guarantee these biases will generalize in the same way that a genuine reasoning engine would.

This is not a hypothetical concern. It is empirically demonstrated: autoregressive models trained on vast corpora fail on simple compositional tasks that require systematic recombination of known primitives in novel configurations (Lake & Baroni, 2018). A system that passes every test you have administered is not the same as a system that will pass every test you could administer.

2. Searle's Chinese Room, Formalized

Searle's (1980) argument can be stated with more precision than it usually receives. Consider a system $\mathcal{S}$ that implements a lookup table $T:\mathcal{X}\to \mathcal{Y}$ of sufficient size to answer every question in the domain. $\mathcal{S}$ is behaviorally indistinguishable from a reasoner, yet it is manifestly not reasoning — it is performing $O\left(1\right)$ retrieval with no inferential process whatsoever. The input-output map is identical; the computational structure is categorically different.

The autoregressive model occupies an intermediate position: it is more than a lookup table (it generalizes), but the nature of its generalization is interpolation over a learned manifold, not deduction over a structured model. The question is whether "sufficiently sophisticated interpolation" crosses a qualitative threshold into reasoning, or whether it merely becomes an increasingly convincing simulacrum.

3. The Intensional vs. Extensional Distinction

Two functions $f$ and $g$ are extensionally equivalent if they agree on all inputs. They are intensionally equivalent if they are computed by the same algorithm. Reasoning is plausibly an intensional property — it pertains not to what is computed but to how it is computed. A system that arrives at $2+2=4$ by retrieving a memorized fact and a system that arrives at $2+2=4$ by applying the successor function twice from the Peano axioms produce the same output, but only the latter is performing arithmetic.

If we accept that reasoning is intensional, then behavioral equivalence is necessary but not sufficient for reasoning. The appearance of reasoning is evidence for reasoning, but it is not constitutive of it.

Verdict

The honest answer is that this remains genuinely unresolved. The strongest version of the functionalist argument is irrefutable on its own terms — but those terms require an idealization (distributional completeness) that is physically unrealizable. In practice, what we observe is that autoregressive models exhibit reasoning-like behavior within their training distribution and degrade in characteristic, non-reasoning-like ways outside it. This degradation pattern — not any single failure — is the strongest evidence that something categorically different from reasoning is occurring.

A sufficiently complex model trained on a genuinely complete distribution would, by construction, produce correct outputs for every input. Whether that constitutes "real reasoning" depends entirely on whether you define reasoning by its outputs or by its process. The mathematical facts do not settle this — it is a question about which definition carves nature at its joints.

Part II: Mathematical Foundations for Deriving Improved Architectures

2.1 The Curry-Howard-Lambek Correspondence

The Curry-Howard isomorphism establishes a deep structural identity between proofs in intuitionistic logic, programs in typed lambda calculus, and morphisms in Cartesian closed categories. This is not merely an analogy — it is a formal bijection:

Logic	Type Theory	Category Theory
Proposition $A$	Type $A$	Object $A$
Proof of $A$	Term of type $A$	Morphism $1\to A$
$A⟹B$	Function $A\to B$	Exponential $B^A$
$A\wedge B$	Product $A\times B$	Product $A\times B$

Under this correspondence, a valid deductive inference is a well-typed program. This suggests a concrete architectural principle: a system whose internal computations are constrained to be well-typed in an appropriate type system would, by construction, produce only valid inferences. Current transformer architectures impose no such constraints — their internal representations live in untyped continuous vector spaces with no structural guarantees on compositionality or logical validity.

Architectural implication: A neural system that learns to construct terms in a dependent type theory — where the type of the output encodes the proof obligation — would have reasoning correctness as a structural invariant, not a statistical regularity.

2.2 Category Theory and Compositional Semantics

Category theory provides the natural language for formalizing compositionality. A category $\mathcal{C}$ consists of objects and morphisms with an associative, unital composition law. The critical observation is that genuine reasoning is functorial — it preserves compositional structure.

Formally, if $\mathcal{L}$ is the category of linguistic expressions (with composition given by syntactic combination) and $\mathcal{M}$ is the category of meanings (with composition given by semantic combination), then understanding is a functor $F:\mathcal{L}\to \mathcal{M}$ that satisfies:

$$F(g\circ f)=F\left(g\right)\circ F\left(f\right)$$

This is precisely the property that autoregressive models approximate but do not guarantee. A model that satisfies this functorial constraint would exhibit perfect compositional generalization — the meaning of a novel composite expression would be determined entirely by the meanings of its parts and the mode of composition.

Architectural implication: Designing internal representations that live in a monoidal category with explicit composition operations would enforce compositionality at the structural level.

2.3 Computational Complexity and Depth

A fundamental result in circuit complexity is that the transformer architecture, as a fixed-depth computation, belongs to the complexity class ${\mathsf{TC}}^0$ — the class of problems solvable by constant-depth, polynomial-size threshold circuits. This class is strictly contained in ${\mathsf{NC}}^1\subseteq \mathsf{P}$.

Many reasoning tasks — including graph reachability, satisfiability, and general first-order theorem proving — are $\mathsf{P}$-complete or harder. A fixed-depth transformer literally cannot solve these problems in general, regardless of its width or the quality of its training data. This is not an empirical observation; it is a theorem.

The implication is stark: no amount of scaling will make a fixed-depth autoregressive transformer a general reasoner. What is needed is adaptive depth — the ability to perform a variable number of computational steps proportional to the difficulty of the problem. Chain-of-thought prompting is a crude external approximation of this, offloading the depth extension to the token sequence. But it is a hack that routes computation through the narrow bottleneck of natural language tokens, not a principled solution.

Architectural implication: Architectures that permit dynamic-depth computation — where the number of inferential steps is determined at runtime by the problem structure — are strictly more powerful. Universal Transformers, adaptive computation time mechanisms, and neural Turing machines all gesture in this direction.

2.4 Algorithmic Information Theory and Compression

Solomonoff's theory of inductive inference establishes that the optimal predictor is the one that finds the shortest program (in the Kolmogorov complexity sense) generating the observed data. Current training via gradient descent on cross-entropy loss is an approximation to this ideal, but it is biased toward solutions that are smooth interpolations rather than discrete algorithmic compressions.

True reasoning often involves discovering algorithms — compact, discrete procedures that generate infinite families of correct outputs. A system that memorizes the first ${10}^6$ prime numbers is using $O(nlogn)$ bits; a system that discovers the Sieve of Eratosthenes uses $O\left(1\right)$ bits (up to the program description). The latter is reasoning; the former is not. Current architectures are biased toward the former.

Architectural implication: Training objectives that explicitly reward compressibility of the learned representation — not just predictive accuracy — would bias learning toward algorithmic solutions. Minimum description length (MDL) principles and the Bayesian Occam's razor provide the theoretical grounding.

Part III: Designing a System for Genuine Reasoning — From First Principles

Setting aside the transformer entirely, let us ask: what would a machine need to be, computationally, to reason? We begin with the formal desiderata and work toward engineering.

3.1 The Desiderata, Precisely Stated

A system $\mathcal{R}$ is a genuine reasoner if and only if:

1. Structured World Model: $\mathcal{R}$ maintains an explicit, compositionally structured internal model $\mathcal{W}$ of entities, relations, properties, and causal dependencies. $\mathcal{W}$ is not a flat vector — it is a graph, a database, a typed structure with queryable relations.
2. Inference Engine: $\mathcal{R}$ possesses a set of inference rules $\mathcal{I}$ that operate on $\mathcal{W}$ to derive new facts. These rules are sound (they preserve truth) and, ideally, complete (they derive all derivable truths).
3. Variable-Depth Computation: The number of computational steps $\mathcal{R}$ expends is a function of the problem, not a fixed constant. $\mathcal{R}$ can chain an arbitrary number of inferential steps, with halting determined by the logical structure of the derivation.
4. Counterfactual Simulation: $\mathcal{R}$ can create modified copies $\mathcal{W}\text{'}$ of its world model, propagate the consequences of stipulated changes through $\mathcal{W}\text{'}$, and compare $\mathcal{W}$ with $\mathcal{W}\text{'}$.
5. Metacognitive Monitoring: $\mathcal{R}$ maintains a calibrated model of its own epistemic state — it knows what it knows, what it doesn't know, and what it would need to learn to resolve specific uncertainties.
6. Grounding Interface: $\mathcal{R}$'s internal symbols are connected, via causal-informational channels, to the external world, such that updates to the world produce corresponding updates to $\mathcal{W}$ and vice versa.

3.2 Proposed Architecture: The Inference Mesh

I will describe a hypothetical architecture — call it the Inference Mesh — designed from first principles to satisfy these desiderata. This is not a product proposal; it is a formal thought experiment about what the minimal sufficient architecture might look like.

Component 1: The Structured Knowledge Substrate (SKS)

The SKS replaces the flat, continuous latent space of a transformer with a typed hypergraph database. Nodes represent entities (typed: physical object, agent, proposition, set, number, etc.). Hyperedges represent n-ary relations. Each node and edge carries:

• A type signature (drawn from a dependent type theory)
• A confidence score $\in [0,1]$ (epistemic status)
• A provenance chain (how this fact was derived — from perception, from inference, from testimony)
• A modal tag (actual, hypothetical, negated, uncertain)

This is not a neural embedding. It is a discrete, queryable, introspectable structure — closer to a Prolog database than to a weight matrix. The key innovation is that the type system constrains what inferences are well-formed: you cannot apply a physical-domain inference rule to a mathematical entity, because the types will not unify.

Formally, the SKS is a structure:

$$\mathcal{K}=(\mathcal{N},\mathcal{E},\tau ,\kappa ,\pi ,\mu )$$

where $\mathcal{N}$ is the node set, $\mathcal{E}$ the edge set, $\tau$ the typing function, $\kappa$ the confidence function, $\pi$ the provenance function, and $\mu$ the modality function.

Component 2: The Inference Kernel (IK)

The IK is a learned program synthesizer that operates on the SKS. Given a query $q$ (a goal proposition with unresolved variables), the IK:

1. Identifies relevant subgraphs of $\mathcal{K}$ (attention-like retrieval, but over a structured graph, not a flat sequence)
2. Selects and instantiates inference rules from a library $\mathcal{I}$ (which includes deductive rules, inductive schemas, abductive hypotheses, analogical mappings)
3. Applies the selected rules, producing new nodes/edges in $\mathcal{K}$
4. Checks type constraints — if the resulting derivation is ill-typed, the step is rejected and alternatives are explored
5. Iterates until the goal is satisfied, a resource bound is reached, or the system concludes the goal is underivable from current knowledge

The critical property is that this is a variable-depth, goal-directed search over a structured space, not a single forward pass through a fixed-depth network. The IK is closer to a neural theorem prover than to a language model.

The IK itself may be parameterized by learned weights — but what it learns is not a token distribution. It learns which inference strategies are likely to succeed on which kinds of problems. This is meta-reasoning: learning to reason, not learning to predict.

Component 3: The Counterfactual Sandbox (CS)

The CS provides the capacity for hypothetical reasoning. Given a stipulation "suppose $P$ were true" (or false), the CS:

1. Creates a fork of the relevant subgraph of $\mathcal{K}$ — call it ${\mathcal{K}}_P$
2. Applies the stipulation (inserts $P$ into ${\mathcal{K}}_P$, or removes $\neg P$)
3. Runs the IK on ${\mathcal{K}}_P$ to propagate consequences
4. Compares ${\mathcal{K}}_P$ with $\mathcal{K}$ to identify the difference set — the propositions that differ between the actual and counterfactual worlds

This is, formally, an implementation of Pearl's do-calculus at the symbolic level: replacing observational conditioning $\left(P\right(Y\mid X=x\left)\right)$ with interventional evaluation $\left(P\right(Y\mid \mathrm{do}(X=x)\left)\right)$.

Component 4: The Epistemic Controller (EC)

The EC monitors the system's own knowledge state and directs the allocation of computational resources. It maintains:

• An uncertainty map: for each proposition in $\mathcal{K}$, the EC knows the confidence $\kappa$ and can compute the expected value of information (EVOI) for resolving that uncertainty
• A resource budget: the EC allocates inference steps, memory, and external queries based on the importance and tractability of the current goal
• A calibration model: the EC tracks its own historical accuracy and adjusts confidence scores to maintain calibration

The EC is the seat of metacognition. It is what enables the system to say "I don't know" with justified confidence, and to know what it would need to learn to resolve its ignorance.

Component 5: The Grounding Interface (GI)

The GI connects the SKS to the external world via perception (sensory input → typed graph updates) and action (graph queries → motor commands or communicative acts). Critically, the GI is bidirectional and causal: changes in the world cause changes in $\mathcal{K}$, and actions derived from $\mathcal{K}$ cause changes in the world.

Without the GI, the system is a formal reasoner but not a grounded one — it can derive valid conclusions from premises, but it cannot verify that its premises correspond to reality. The GI is what distinguishes a reasoning system from a proof checker.

3.3 The Learning Problem

The Inference Mesh, as described, has many learnable components:

• The structure of $\mathcal{K}$ — what entities, types, and relations to represent
• The inference rule library $\mathcal{I}$ — which rules exist, their preconditions and effects
• The search heuristics of the IK — which rules to try first, how to prune the search space
• The attention mechanism over $\mathcal{K}$ — how to identify the relevant subgraph for a given query
• The calibration model of the EC — how confident to be in each derivation

The crucial insight is that the learning objective is not token prediction. The learning objective is:

$$\mathcal{L}\left(\theta \right)=-{\mathbb{E}}_{(q,a)\sim \mathcal{D}}[\log P_{\theta }(a\mid q,\mathcal{K})+\lambda ·\text{Validity}(\text{derivation}\left)\right]$$

where Validity is a type-checking term that penalizes ill-formed derivations regardless of whether they happen to produce the correct answer. The system is rewarded for being right for the right reasons — for producing derivations that are both correct and logically valid.

This is a fundamentally different optimization landscape. A system trained under this objective cannot achieve low loss by memorizing input-output pairs, because the validity term requires the intermediate derivation to be well-formed. Shortcuts and spurious correlations produce high loss even when they yield correct answers.

3.4 What This Architecture Can Do That Transformers Cannot

1. Guaranteed compositional generalization: Because inference rules are applied to typed structures via unification, novel combinations of known entities and relations are handled by the same mechanism as familiar ones. The system does not need to have seen "Does a blue elephant fly?" to answer it — it unifies elephant: Animal, fly: Action, and applies the rule ¬CanFly(x) ← Heavy(x) ∧ ¬HasWings(x).
2. Sound multi-step deduction: Each step in the derivation is type-checked and validated. The system does not drift into incoherence over long chains of reasoning because each link is independently verified.
3. Principled uncertainty: The confidence scores are propagated through the derivation via probability theory (or Dempster-Shafer, or another appropriate calculus), so the system's stated uncertainty about its conclusion is a mathematically justified function of its uncertainty about its premises.
4. Genuine counterfactual reasoning: The Counterfactual Sandbox provides a clean, formal mechanism for hypothetical evaluation that does not require "fighting" a learned prior.
5. Interpretable derivations: Every conclusion comes with a provenance chain that can be inspected, critiqued, and debugged by a human — or by the system itself.

3.5 What Remains Hard

This architecture is not a panacea. Several fundamental challenges remain:

• Knowledge acquisition: Populating the SKS from raw perceptual data is itself a staggeringly difficult problem — essentially the full problem of scene understanding and conceptual abstraction.
• Rule discovery: Learning new inference rules from experience (as opposed to applying hand-coded ones) requires a form of inductive logic programming that remains an open research problem.
• Tractability: Unrestricted search over a typed hypergraph is computationally explosive. The heuristic guidance of the IK must be extremely good to keep inference tractable — and learning those heuristics may itself require something like neural function approximation.
• Integration: The most powerful system would likely combine the Inference Mesh with something like a neural perceptual frontend and a language model interface — not as a crutch, but as a grounding and communication layer. The hybrid integration problem is itself deeply nontrivial.

3.6 The Philosophical Implication

The Inference Mesh, if realized, would constitute a system that reasons by construction. Its outputs would be accompanied by verifiable derivations. Its uncertainty would be calibrated. Its generalization would be compositional. It would not be a stochastic parrot, nor would it be a Chinese Room — it would be a system whose internal processes have the same logical structure as the reasoning they implement.

Whether such a system would be conscious, or would understand in the phenomenological sense, remains as unanswerable as ever. But it would satisfy every functional criterion for reasoning that we can articulate with mathematical precision, and it would do so not by statistical accident but by architectural necessity.

Coda: The Current Moment

We stand at an unusual juncture. Autoregressive language models have demonstrated — against the expectations of most researchers — that an enormous amount of reasoning-like behavior can be extracted from distributional statistics over text. This is a profound empirical discovery about the structure of natural language and, by extension, about the degree to which linguistic surface form encodes deep semantic structure.

But it is a mistake to confuse this discovery with the conclusion that the problem of reasoning is solved, or that scaling the current paradigm will solve it. The ${\mathsf{TC}}^0$ depth limitation is a theorem, not a conjecture. The lack of compositional guarantees is a structural property, not a training data gap. The absence of a veridical world model is an architectural fact, not an emergent property waiting to appear at the next order of magnitude.

The path forward almost certainly involves hybrid architectures that combine the extraordinary pattern-recognition and linguistic facility of neural models with the structural guarantees of symbolic inference. The Inference Mesh is one sketch of what such a hybrid might look like. The mathematical foundations — type theory, category theory, algorithmic information theory, causal inference — are mature enough to support serious architectural design. What remains is the engineering.

The most important intellectual contribution of the current generation of language models may ultimately be not what they can do, but the precision with which their failures illuminate what reasoning actually requires.

Question 1: Can You Scale Your Way to Real Reasoning?

Short answer: No, but you can get disturbingly far.

Here's what actually happens in practice. You train a model on trillions of tokens. It absorbs an enormous amount of implicit structure — logical patterns, causal regularities, mathematical identities, procedural knowledge — all encoded as conditional token distributions. When you prompt it with a problem that's structurally similar to things it's seen, it produces outputs that are functionally indistinguishable from reasoning. For maybe 85-90% of practical queries, the difference is genuinely academic.

But then you hit the wall. And the wall is always the same shape:

Novel composition. Ask it to chain 7+ inferential steps on a problem whose surface structure doesn't match training templates. Accuracy drops off a cliff. Not gradually — catastrophically. A real reasoner degrades gracefully; a pattern-matcher falls off a table.

Negation and counterfactuals. Tell it "assume gravity doesn't exist, what happens to bridges?" It will fight you. The learned prior is enormously strong and the architecture has no mechanism to cleanly suppress it. You get hedged, muddled outputs that blend the counterfactual stipulation with real-world priors.

Consistency over long contexts. Ask it to maintain 15 interdependent constraints across a 10,000-token generation. It can't. It doesn't have a constraint solver — it has a next-token predictor that locally maximizes likelihood, which means each token is approximately correct given recent context but there's no global consistency enforcement.

These aren't training data gaps. They're architectural limits. Specifically:

The depth ceiling is real. A transformer is a fixed-depth circuit. Fixed-depth circuits provably cannot solve problems that require sequential dependency chains longer than their depth. Chain-of-thought is a workaround — it externalizes the depth into the token sequence — but it routes all intermediate computation through the bottleneck of natural language tokens, which is lossy and slow. It works, but it's duct tape.

The training objective is wrong for reasoning. Cross-entropy loss on next-token prediction rewards the model for producing likely continuations, period. It does not reward valid derivations. It does not penalize correct answers arrived at via spurious shortcuts. A model that memorizes "the answer to questions shaped like X is usually Y" gets the same reward as a model that actually derives Y from X, and gradient descent will find the cheaper path every time.

What would "complete distribution" actually require?

People handwave about "just train on all of mathematics and logic." Let's do the math. The space of valid first-order logic derivations up to length $n$ grows faster than exponential in $n$. You can't enumerate it. You can't sample it uniformly. Any finite training set will have systematic gaps, and the model's behavior in those gaps is determined by inductive bias, not by reasoning.

The practical upshot: scaling gets you better pattern-matching, not reasoning. The two are different computations. One is lookup with interpolation. The other is search with verification. No amount of data converts the first into the second.

Question 2: What Can We Actually Derive from Current Theory?

There are exactly four theoretical results that have direct engineering implications. Not vague "insights" — concrete constraints on what architectures can and cannot do, with clear prescriptions.

Result 1: The TC⁰ Barrier (Merrill & Sabharwal, 2023)

What it says. A standard transformer with fixed depth $L$ and $\text{poly}\left(n\right)$ width can only compute functions in the complexity class TC⁰. This class does not contain problems like graph connectivity, context-free language recognition, or general Boolean satisfiability.

What it means for engineering. If your task requires determining whether node A can reach node B in a graph of arbitrary size, a fixed-depth transformer literally cannot solve it — regardless of parameter count, training data, or training time. This is a proof, not a conjecture.

What to build. You need adaptive depth. Concrete options that exist today:

• Universal Transformers (Dehghani et al., 2019): Share weights across layers and iterate until a halting criterion is met. Turing-complete in principle. In practice, training is unstable and the halting mechanism is crude.
• Adaptive Computation Time (Graves, 2016): Learn a per-position "ponder" distribution that controls how many steps to apply. Theoretically elegant. In practice, the ponder distribution collapses to either 1 step or max steps — the gradient signal for intermediate depths is weak.
• Looped Transformers (Yang et al., 2024): Fix a small transformer and iterate it many times with output feeding back as input. Simplest to implement. Surprisingly effective on algorithmic tasks. The open problem is making the loop count problem-dependent rather than fixed.

The most pragmatic near-term path: Looped transformers with a learned halting condition, trained on tasks that explicitly require variable-depth computation.

Result 2: Compositional Generalization Requires Structural Inductive Bias

What it says. Models generalize compositionally (understanding "blue cat" from knowing "blue" and "cat" separately) only when the architecture has an explicit structural bias toward compositional representation. MLP + attention alone doesn't have this. Tree-structured models, graph neural networks, and neurosymbolic hybrids do.

What it means for engineering. If you need reliable compositional generalization — and you do, for any form of genuine reasoning — you need architectures that explicitly decompose representations into structured, recombineable parts.

What to build. The most mature option is neurosymbolic integration:

• Use a neural frontend (can be a transformer) for perception and language understanding
• Parse into a structured symbolic representation (typed graph, logical form, program sketch)
• Run symbolic inference on the structure (type-checked, sound, compositionally guaranteed)
• Use a neural backend for generation, ranking, and naturalness

This is not hypothetical. AlphaProof (DeepMind, 2024) does exactly this for mathematical reasoning: a neural model proposes proof steps, and a formal verifier (Lean 4) checks them. The neural component handles heuristic search; the symbolic component guarantees correctness. The combination solved IMO-level problems that neither component could solve alone.

Result 3: Verification Is Cheaper Than Generation

What it says. For most reasoning tasks, checking whether a derivation is valid is computationally much cheaper than finding the derivation in the first place. (This is the P vs. NP intuition, applied architecturally.) A SAT solution is hard to find but trivial to check. A proof is hard to construct but mechanical to verify.

What it means for engineering. Don't try to make the generative model perfect. Make it prolific and pair it with a fast verifier. Generate many candidate derivations, check each one, keep the valid ones.

What to build. This is already being built. The pattern is:

• Generator: LLM proposes candidate solutions / reasoning chains / proof steps
• Verifier: Formal system (type checker, SAT solver, unit test suite, symbolic math engine) validates each candidate
• Search: MCTS or beam search over the generate-verify loop, guided by a learned value function

This is the architecture of AlphaProof, of OpenAI's process reward models, of code generation with unit test feedback. It works now. The bottleneck is the quality of the verifier — and for many domains (mathematics, code, logic), excellent verifiers already exist.

Result 4: The Training Objective Determines the Ceiling

What it says. A model optimized for

$$\mathcal{L}=-\mathbb{E}[\log P(x_t\mid x_{<t}\left)\right]$$

will converge to the conditional distribution of the training corpus, not to the distribution of valid reasoning chains. These are different distributions. The training corpus contains errors, shortcuts, and plausible-but-wrong reasoning. A model that perfectly fits this distribution will reproduce all of these failure modes.

What it means for engineering. If you want a model that reasons, you need to train it on an objective that rewards valid reasoning, not on an objective that rewards predicting text.

What to build. Outcome-based and process-based reward models:

• Outcome reward: Train with RL where reward = whether the final answer is correct (checked by a verifier). This works but is credit-assignment-hard — the model doesn't know which steps were good.
• Process reward: Train with RL where reward = whether each intermediate step is valid. This is much more signal-rich but requires step-level supervision, which is expensive to obtain (unless you have a formal verifier — see Result 3).
• Self-play with verification: Generate reasoning chains, verify them formally, use verified chains as training data, iterate. This is the core loop of AlphaProof and it's the closest thing we have to a proven recipe for training genuine reasoning.

Question 3: How Would You Actually Build a Reasoning System?

Forget the transformer. Forget autoregressive generation. Start from what reasoning actually requires and work backward to the engineering.

What reasoning requires (the non-negotiable list)

1. A structured, queryable model of what the system knows
2. Operations that transform that model according to valid rules
3. The ability to chain an unbounded number of those operations
4. The ability to hypothesize, simulate, and compare alternatives
5. The ability to know what it doesn't know
6. The ability to acquire new knowledge from the environment

A concrete system design

Here's how I'd actually build it with existing technology. No magic, no hypothetical physics — just components we know how to make, assembled differently.

Layer 1: The Knowledge Graph with Types

Not a vector database. Not an embedding space. An actual typed, relational knowledge graph stored in something like a property graph database (Neo4j-style, but in-memory for speed).

Every node has:

• A type from a predefined type hierarchy (Entity, Proposition, Quantity, Relation, ...)
• A confidence score (0 to 1)
• A source tag (perceived, inferred, assumed, told)

Every edge has:

• A relation type (causes, implies, part-of, greater-than, ...)
• A type constraint on its endpoints (e.g., "causes" requires both endpoints to be Events)

This is your world model. It's explicit, inspectable, and queryable. When the system "knows" something, that means there's a node or edge in this graph with confidence above threshold.

How to build it: Use an in-memory graph database. Populate it initially from a knowledge base (Wikidata, ConceptNet, domain-specific ontologies). Extend it at runtime via perception and inference.

Layer 2: The Inference Engine

This is the core. It's a learned program synthesizer that operates on the knowledge graph via typed graph rewriting rules.

Each rule has the form:

IF [pattern P matches in the graph]
AND [type constraints are satisfied]
AND [confidence of matched nodes > threshold]
THEN [add new nodes/edges to the graph]
WITH [confidence = f(input confidences)]

The system comes with a library of hard-coded rules (modus ponens, transitivity, numerical comparison, causal propagation) and also learns new rules from data via inductive logic programming or neural rule induction.

The inference engine runs as a goal-directed search:

1. Receive a query (e.g., "Is X true?")
2. Check if the answer is already in the graph → if yes, return it with confidence
3. If not, identify rules whose consequents could produce the answer
4. Apply those rules, which may generate subgoals
5. Recurse on subgoals
6. If search tree exceeds resource budget, return "unknown" with explanation of what's missing

This is variable-depth computation by design. Simple queries terminate in 1-2 steps. Complex queries chain dozens of rules. The system allocates computation proportional to problem difficulty, not as a fixed architectural constant.

How to build it: The search is essentially a Prolog-style backward chaining engine, but with learned heuristics for rule selection and subgoal ordering. The heuristics can be a small neural network (a GNN over the local graph neighborhood) that scores candidate rules. Train the heuristics via RL on a curriculum of reasoning tasks with verified solutions.

Layer 3: The Verifier

Every inference chain produced by Layer 2 is checked by an independent verification module. The verifier is simple and trustworthy — it doesn't generate anything, it just checks:

• Are all type constraints satisfied?
• Does each step follow from a valid rule?
• Are confidence propagations computed correctly?
• Does the derivation actually prove the goal?

This is mechanical — it's a type-checker. It's fast. It's reliable. And it means the system never presents an unverified conclusion as though it were verified. If the derivation fails verification, the system says so.

How to build it: This is a straightforward implementation. Dependent type checkers exist (Lean, Coq, Agda). You don't need a full proof assistant — a simpler type system tailored to your rule language is sufficient and much faster.

Layer 4: The Counterfactual Engine

When the system needs to answer "what if X?", it:

1. Forks the relevant subgraph of the knowledge graph (copy-on-write for efficiency)
2. Applies the stipulated change (insert X, or remove ¬X)
3. Propagates consequences using the inference engine on the forked graph
4. Returns the diff between the original and forked graphs

This is precisely how causal reasoning frameworks work (Pearl's do-calculus, structural causal models). The engineering challenge is efficiency — you can't deep-copy a million-node graph for every hypothetical. Copy-on-write semantics with lazy evaluation make this tractable.

How to build it: Implement the knowledge graph with immutable data structures (persistent data structures in the functional programming sense). Forking is then O(1) — you share all unchanged structure and only allocate memory for modifications.

Layer 5: The Uncertainty Module

Every conclusion carries a calibrated confidence. The uncertainty module:

• Propagates uncertainty through inference chains using probability theory (or Dempster-Shafer for conflicting evidence)
• Tracks which premises each conclusion depends on, so that retracting a premise automatically retracts all downstream conclusions (truth maintenance)
• Computes expected value of information: "If I could learn the answer to sub-question Q, how much would that reduce my uncertainty about the main question?" This drives active information-seeking.

How to build it: Bayesian networks over the inference graph. Each inference step corresponds to a conditional probability. The overall confidence is computed by message-passing (belief propagation). For truth maintenance, use an ATMS (Assumption-based Truth Maintenance System) — these have been well-understood since the 1980s.

Layer 6: The Language Interface

Everything above is symbolic and structured. To interact with humans, the system needs a natural language layer. This is where a language model is actually useful — not as the reasoning engine, but as a translator:

• Input: LLM parses natural language query → extracts a structured goal for the inference engine
• Output: Inference engine produces a derivation → LLM renders it as natural language explanation

The LLM is a peripheral, not the core. It handles ambiguity, context, and fluency. The reasoning is done by Layers 1-5.

How to build it: Fine-tune a moderate LLM (7B-70B is plenty) on paired data of (natural language query, formal goal) and (formal derivation, natural language explanation). This is a well-understood sequence-to-sequence translation task.

What this system can do

• Guaranteed sound multi-step deduction: Every chain is verified. No hallucination of logical steps.
• Compositional generalization: New entity + known rule = valid inference, by construction.
• Calibrated uncertainty: "I'm 73% confident because premise A is strong but premise B is only supported by one source."
• Genuine counterfactuals: Clean graph forking, not fighting a prior.
• Transparency: Every conclusion comes with a human-readable proof trace.
• Knows what it doesn't know: The uncertainty module and truth maintenance system make this explicit.

What this system cannot do (yet)

• Perception: Converting raw images/audio into typed graph nodes is a hard open problem. You'd need a neural perception frontend, and the interface between continuous perception and discrete symbols is not solved cleanly.
• Abductive reasoning at scale: The system can do deduction and some induction. Generating good hypotheses — the creative leap of "what if the explanation is Z?" — is where learned heuristics are weakest. This is arguably the hardest subproblem.
• Learning entirely new domains from scratch: The type system and rule library need initial structure. The system can extend and refine them, but cold-starting a new domain from raw data alone is out of reach without significant human scaffolding.
• Speed on simple tasks: For "what's the capital of France?", a lookup table (or an LLM) is faster. This architecture is overkill for retrieval. It shines on tasks that actually require reasoning.

The realistic roadmap

What you can build today (2026):

• The knowledge graph (well-understood technology)
• The hard-coded inference rules + backward chaining search (Prolog-era technology, mature)
• The verifier / type checker (mature technology)
• The LLM interface layer (current technology)
• The uncertainty propagation (Bayesian networks, ATMS — mature)
• The counterfactual engine with persistent data structures (straightforward engineering)

What requires active research:

• Learning new inference rules from data (inductive logic programming is improving but not robust)
• Training the search heuristics to be fast enough for real-time use
• The perception-to-symbol grounding interface
• Scaling the knowledge graph to billions of nodes without killing query performance

What's probably 5-10 years out:

• A full system that integrates all six layers smoothly
• Robust abductive reasoning (hypothesis generation)
• Self-improving rule libraries that grow with experience
• Performance competitive with LLMs on both retrieval tasks and reasoning tasks

The bottom line

The architecture for genuine reasoning is not mysterious. The individual components mostly exist. The hard part is integration, scale, and learning — making the symbolic core fast enough and flexible enough to handle real-world messiness, while keeping the guarantees that make it a reasoner rather than a guesser.

The irony is that LLMs have made everyone think reasoning is a language problem. It isn't. Language is the interface to reasoning. Reasoning itself is search over structured representations with verification. We've known this since the 1960s. What's changed is that we now have the neural components to handle the messy frontend (language understanding, heuristic guidance, perceptual grounding) and the compute to run the search at useful scale.

The correct architecture is almost certainly a hybrid: neural periphery for perception and language, symbolic core for inference and verification, learned heuristics bridging the two. This is not a new idea — it's the neurosymbolic thesis. What's new is that we finally have both halves good enough to make the integration worth attempting seriously.