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

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.

📋 한 줄 요약

**[Impossibility Result → Design Spec]** Deterministic Horizon — 12 transformer 구조에서 19~31 reasoning depth로 측정되는 architecture-bound accuracy 한계 — 등 16개 impossibility를 trustworthy AI의 설계 사양으로 전환.

🎯 핵심 기여도

Turing·Arrow·No Free Lunch 등 fundamental limit를 호기심거리에서 design rule로 전환하는 thesis 전체 비전 제시.
Flagship 결과 — architecture alone에 의한 accuracy ceiling 증명: critical reasoning depth를 넘으면 어떤 학습량·adapter rank·sample size·loss function으로도 이동 불가. Layer 수·embedding width로 deployment 이전 계산 가능한 Deterministic Horizon이 12개 transformer 구조에서 19~31로 측정, optimal-length trace로 fine-tuning 시 4 percentage point 이내로 회복.
메커니즘: residual stream의 capacity invariant이며 정보 이론적 변환이 horizon 이후 super-exponential accuracy decay 유도. Modular exponentiation에 대한 constant-depth prime-modulus circuit의 무조건적 회로 복잡도 lower bound로 보완.
동일 논거를 다양 분야로 전이 — preference learning(misspecified model 하 sample complexity 불연속 도약), multi-stage retrieval(독립 metric 수 ≥ stage 수), prompt-dependent valuation 환경에서 표준 truthful auction 실패, neural inference의 zero-knowledge 검증이 non-linear activation당 110~190× 측정된 오버헤드. 총 16 specification — computable boundary·정량 violation cost·constructive design rule 페어링.

💡 핵심 아이디어

모든 fundamental limit는 동시에 설계 규칙이며, impossibility result는 회피해야 할 한계가 아니라 trustworthy AI 시스템을 만들기 위한 사양으로 변환되어야 한다 — 이를 systematically 수행하면 16개의 computable, quantified, constructive 디자인 가이드라인이 도출된다.

🔬 기술적 접근법

**방법론**: Impossibility-specification methodology — 16 spec catalog.
**핵심 기법**: (1) Deterministic Horizon — residual stream capacity invariant 기반 accuracy ceiling, (2) 정보 이론 conversion으로 super-exponential decay 유도, (3) Modular exponentiation의 무조건적 회로 lower bound, (4) Preference learning·retrieval·auction·ZK 검증 각각의 impossibility를 spec으로 전환, (5) 두 composition 증명·하나 honest obstruction·네 미해결 open.

📊 주요 결과

Deterministic Horizon: 12 transformer에서 19~31 사이로 측정, optimal trace fine-tuning으로 4 pp 이내 회복.
ZK 검증 overhead: non-linear activation당 110~190×.
Preference learning sample complexity: misspecification 시 discontinuous 도약.
Multi-stage retrieval: 독립 metric 수 ≥ stage 수.
16 spec 중 2개 composition 증명, 1개 obstruction, 4개 open.

💭 의의 및 한계

**의의**: 이론적 한계를 실무 설계 지침으로 시스템화, trustworthy AI의 generative 연구 프로그램 방법론 제안, 다양 분야 통합 catalog. **한계**: Thesis 형태로 방대 — 검증 부담, 일부 한계의 실측 가능성·도메인 일반화 미완, 4개 미해결 spec.

🚀 실용적 활용

AI 시스템 설계 단계 의사결정 가이드.
안전·검증 가능 AI 인증 표준.
Architecture·workflow 계획 사전 검증 도구.