2026-05-25原文

The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems

This paper turns fundamental limits from Turing, Arrow, and No Free Lunch theorems into design rules, introducing the Deterministic Horizon: an accuracy ceiling set by architecture alone, beyond which no training can improve. Measured between 19 and 31 across 12 transformer architectures, fine-tuning on optimal-length traces recovers under 4%. The work extends to preference learning, retrieval pipelines, truthful auctions, and zero-knowledge verification, forming a catalogue of 16 specifications pairing computable boundaries, quantified violation costs, and constructive design rules.

Article intelligence

EngineersAdvanced

Key points

The Deterministic Horizon is a pre-deployment computable accuracy ceiling based on layer count and embedding width.
Across 12 transformer architectures, the horizon ranges from 19 to 31, with fine-tuning recovering less than 4 percentage points.
The thesis provides 16 specifications that turn impossibility results into actionable design rules for trustworthy AI.

Why it matters

This matters because the Deterministic Horizon is a pre-deployment computable accuracy ceiling based on layer count and embedding width.

Technical impact

May affect model selection, inference cost, product capability, and evaluation benchmarks.

[2605.23024] The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems

[Submitted on 21 May 2026]

Title:The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems

View a PDF of the paper titled The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems, by Dongxin Guo

View PDF

Abstract:Large language models now write software, draft legal documents, and produce clinical notes, yet fundamental limits, from Turing and Arrow to the No Free Lunch theorems, shape what computation can do. This thesis turns such impossibility results from curiosities into design rules. Its flagship result proves an accuracy ceiling set by architecture alone: past a critical reasoning depth, no amount of training moves it, at any adapter rank, sample size, or loss function. Computable before deployment from layer count and embedding width, this Deterministic Horizon is measured between nineteen and thirty-one across twelve transformer architectures, and fine-tuning on optimal-length traces recovers under four percentage points. The mechanism is a capacity invariant of the residual stream, and an information-theoretic conversion yields super-exponential accuracy decay past the horizon. An unconditional circuit-complexity lower bound for modular exponentiation against constant-depth prime-modulus circuits complements this result. The same argument recasts across subfields: preference learning under any misspecified model jumps discontinuously in sample complexity; multi-stage retrieval pipelines require at least as many independent metrics as stages; standard truthful auctions fail for agents with prompt-dependent valuations; and zero-knowledge verification of neural inference pays a measured overhead of one hundred ten to one hundred ninety times per non-linear activation. Together these form a catalogue of sixteen specifications, each pairing a computable boundary, a quantified violation cost, and a constructive design rule: two compositions are proved, one pairing is an honest obstruction, and four remain open. The impossibility-specification methodology is offered for the generative research programme that trustworthy AI may need. Every fundamental limit of AI is also a design rule.

Comments: PhD thesis, Department of Computer Science, The University of Hong Kong, 2026. 271 pages, 18 figures, 15 tables, 5 algorithms

Subjects:

Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Computation and Language (cs.CL); Machine Learning (cs.LG)

ACM classes: I.2.7; I.2.6; F.1.3

Cite as: arXiv:2605.23024 [cs.AI]

(or arXiv:2605.23024v1 [cs.AI] for this version)

https://doi.org/10.48550/arXiv.2605.23024

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Dongxin Guo [view email] [v1] Thu, 21 May 2026 20:48:35 UTC (856 KB)

Full-text links:

Access Paper:

View a PDF of the paper titled The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems, by Dongxin Guo

View PDF

TeX Source

view license

Current browse context:

cs.AI

new | recent | 2026-05

Change to browse by:

cs cs.CC cs.CL cs.LG

References & Citations

NASA ADS

Google Scholar

Semantic Scholar

Data provided by:

Bibliographic Tools

Bibliographic and Citation Tools

Bibliographic Explorer Toggle

Bibliographic Explorer (What is the Explorer?)

Connected Papers Toggle

Connected Papers (What is Connected Papers?)

Litmaps Toggle

Litmaps (What is Litmaps?)

scite.ai Toggle

scite Smart Citations (What are Smart Citations?)

Code, Data, Media

Code, Data and Media Associated with this Article

alphaXiv Toggle

alphaXiv (What is alphaXiv?)

Links to Code Toggle

CatalyzeX Code Finder for Papers (What is CatalyzeX?)

DagsHub Toggle

DagsHub (What is DagsHub?)

GotitPub Toggle

Gotit.pub (What is GotitPub?)

Huggingface Toggle

Hugging Face (What is Huggingface?)

ScienceCast Toggle

ScienceCast (What is ScienceCast?)

Demos

Replicate Toggle

Replicate (What is Replicate?)

Spaces Toggle

Hugging Face Spaces (What is Spaces?)

Spaces Toggle

TXYZ.AI (What is TXYZ.AI?)