Deterministic Execution Certificates: Verifiable Evidence for Hybrid LLM-Agent Workflows

When an LLM agent acts in a regulated domain, "the model followed its instructions" is not an audit answer. Auditors, regulators, and downstream systems need a different statement: this specific output was produced from these specific inputs by this specific, reviewed, versioned method — and they need to be able to check it without trusting the operator's word. Yet agent executions are hybrid: some steps are genuinely deterministic (a limit calculation, a rules evaluation, a unit conversion), while others are irreducibly generative. Treating the whole run as an opaque LLM transaction throws away the verifiability the deterministic majority could provide; treating it as fully deterministic is a lie. This paper proposes the Deterministic Execution Certificate (DEC): a signed, hash-chained, per-step evidence artifact for agent workflows. Each step in an agent run is classified by nondeterminism level (ND0 fully deterministic through ND3 open generation). ND0 steps receive replayable certificates — commitments to inputs, outputs, and the exact versioned method, such that a verifier can re-execute and confirm bit-for-bit correspondence. Generative steps receive bounded-nondeterminism attestations: provenance of the full generation configuration, the behavioral contract the component was certified against, and stability statistics from repeated conformance probing — an honest certificate of what can be certified, in place of a false certificate of determinism. Step certificates chain by hash into a run-level certificate, so an end-to-end agent transaction is verifiable step-by-step, and the boundary between computed and generated content is cryptographically explicit. We define the certificate format (canonicalized JSON, Ed25519 signatures, salted commitments for selective disclosure), the verification procedure, and the trust model (attestation issuers replacing reputation); we position DECs against supply-chain provenance (in-toto, SLSA), verifiable credentials, trusted execution, and zero-knowledge ML; and we state the limits plainly — a DEC proves the declared method executed, never that the method is right, and generative steps are attested, not certified. An open specification, JSON Schema, worked signed example, and reference verifier accompany the paper.