Consequential decisions in law, medicine, finance, and public services are increasingly mediated by AI systems, yet no widely adopted infrastructure allows an authorized third party to later verify, with cryptographic assurance, what observable factors caused a specific AI output. Explainable AI (XAI) methods characterize model behavior in general, not a single transaction; governance frameworks specify process, not evidentiary mechanism; and forensic/audit logging is rarely designed for AI-specific provenance (retrieved context, tool invocation, policy evaluation) or for graduated, privacy-preserving legal disclosure. We systematize this gap and propose the AI Accountability Infrastructure (AAI), centered on a formally defined, hash-chained, digitally signed AI Accountability Record (AAR) and a graduated, threshold-cryptography-enforced disclosure model in which no single party — including the AI provider — holds unilateral access to evidentiary content. We give (i) a formal model of record integrity and non-repudiation with informal correctness arguments grounded in established cryptographic primitives; (ii) a STRIDE-based threat model spanning both AI-specific and classical evidentiary risks; (iii) a privacy analysis using established data-minimization and disclosure-control concepts; (iv) a complexity and overhead analysis of the proposed mechanisms; and (v) an evaluation methodology intended for future empirical validation. This paper is explicitly a framework and formal-model contribution: it does not report novel experimental results, and we state this limitation directly rather than fabricate benchmark figures. We situate AAI against the NIST AI Risk Management Framework, ISO/IEC 42001, and the EU AI Act, and identify open problems suitable for a doctoral research program.