Abstract
We develop a foundational framework for hallucination-free language generation grounded in dependent type theory and categorical semantics. Our central thesis is that language generation should be reconceived as type inhabitation rather than statistical sampling: instead of computing argmax P(t | ctx), a correct language model computes argmin C(a) subject to the constraint Γ ⊢ a : A, where C is a cost function and the constraint enforces type-correctness in a dependent type theory of semantic meaning. We establish five generation principles that jointly guarantee hallucination freedom: (1) Generation as Type Inhabitation, recasting next-token prediction as proof search; (2) Certified Derivations, equipping every generated term with a polynomial-time-checkable derivation tree via the Curry–Howard correspondence; (3) Abstention on Empty Types, replacing hallucination with the type-theoretically correct response ⊥ when the goal type is uninhabited; (4) Context as Fibration, modeling the context window as a dependent telescope forming a fibration p: E → B; and (5) Attention as Weighted Limit, replacing softmax-weighted sums in Vect with weighted limits in the semantic category Sem. We prove that this framework is sound (every generated term is semantically valid) and complete relative to the knowledge base (every derivable claim is generable). The framework is formalized in Haskell with GADTs and dependent types, providing executable specifications for all core constructs.
Key Theorems
Let Γ ⊢ a : A be a judgment derivable in T_Sem with derivation δ. Then a is semantically valid: the claim a is a grounded, non-hallucinated statement. More precisely, for every interpretation ⟦·⟧: T_Sem → Sem, we have ⟦a⟧ ∈ ⟦A⟧.
If the goal type A is provably uninhabited in T_Sem (i.e., A ≃ ∅), then the generation procedure terminates with output ⊥ ("I cannot answer"). This is the unique type-theoretically correct response when no valid claim of type A exists. Returning any non-⊥ answer would constitute a hallucination.
The categorical attention mechanism lim^W D — the weighted limit of diagram D: J → Sem with weight W: J^op → Set — preserves semantic coherence: if D is a coherent diagram (all 2-cells are invertible), then lim^W D is a valid semantic type, and the canonical projections π_j: lim^W D → D(j) are certified derivations.
Five Generation Principles
| Principle | Replaces | Guarantee |
|---|---|---|
| P1: Generation as Type Inhabitation | argmax P(t|ctx) | Every output has a valid type derivation |
| P2: Certified Derivations | Black-box generation | O(|δ|·|A|) polynomial-time verifiable proof |
| P3: Abstention on Empty Types | Forced hallucination | Returns ⊥ when A is uninhabited |
| P4: Context as Fibration | Flat token window | Dependent telescope Γ = (x₁:A₁, x₂:A₂(x₁), ...) |
| P5: Attention as Weighted Limit | Softmax in Vect | Categorical coherence preserved under aggregation |
Download Full Paper
The complete 24-page paper in PDF format, including all proofs, Haskell formalizations, and appendices.
Download PDF (24 pages)