Provenance Algebra for Deterministic AI Execution: Replay Semantics for Stochastic Program Generators

When AI systems generate computational pipelines from natural language, provenance -- the record of what was executed and why it is reproducible -- is typically treated as execution metadata: logs, run IDs, artifact URIs. This paper argues that provenance for deterministic execution systems is not metadata but a semantic factorization of execution identity. Building on prior work that established admissibility boundaries (Paper 1), canonical execution semantics (Paper 2), and quotient execution categories (Paper 3), we define a provenance map over the quotient execution category, assigning to each execution equivalence class an 8-layer hash record that decomposes execution identity into semantic dependency boundaries. The provenance of a composed execution is determined by the provenance of its parts together with the declared dependency map between them. This compositional provenance structure enables four operational capabilities: replay equivalence (identical provenance records operationally witness replay-equivalent execution under deterministic evaluation and collision-resistance assumptions), divergence localization (when two executions differ, the first observable divergence is localized to a specific semantic layer), partial replay (layers below the divergence point need not be re-executed), and provenance-preserving registry evolution (discovery metadata changes preserve all provenance layers). We validate against the empirical measurements of Papers 1-3: 50 replay runs, 1,200 LLM generations, 5 canonical specifications, and registry drift detection across targeted modifications. All constructions are operational, registry-relative, and replay-grounded. The semantics do not claim universal provenance structures, trustless computation, or cross-system replay guarantees.