Source-linked AI summary
Threshold Choice, Not Sample Size, Bounds Trustless Verification of Nondeterministic Compound AI Workflows
Alper Alimoglu
TL;DR
Compound AI workflows require verification despite nondeterministic outputs, untrusted recorders, and intermittent access to shared records. The paper commits and anchors stage evidence, then challenges it through median re-execution, but finds that threshold choice—not larger sample size—limits soundness against same-input fabrication.
Problem
Compound AI verification must handle nondeterminism, dishonest reporting, and intermittent connectivity together, a combination prior work addresses at most two at once.
Method
The protocol commits stage inputs, outputs, context, and policy, anchors them under execution links, defers during partitions, and evaluates challenges using median re-executions without a quorum.
Results
Holding the metric and pipeline spread fixed, a per-execution threshold detects 19 of 29 fabrications versus 9 for the best constant with zero honest rejections at k=5.
Takeaways & Limitations
Threshold selection bounds soundness: increasing k sharpens estimates but does not repair fabrications whose population median lies within the accepted region.
Takeaways & Limitations
The proof-of-concept uses a synthetic three-stage HotpotQA pipeline in one process and does not stress distributed retrieval, restart recovery, or live edge-cloud-orbital deployment.
Abstract
from arXiv · showhide
Compound AI pipelines chain LLM calls, retrievers, and tools and are nondeterministic: sampling, model updates, and volatile tool responses make one input yield different outputs across runs. Such pipelines increasingly run across edge, cloud, and orbital nodes owned by no single party, whose optimizations discard intermediate results before inspection. Verifying reproduction there means tolerating nondeterministic outputs, a node that may not report honestly, and intermittent access to any shared record; existing work addresses at most two at once. We give a protocol covering all three: it commits digests of each stage's inputs, outputs, and context under a policy digest pinning the metric and threshold, anchors them without trusting the executing node, defers under partition, and decides a challenge on the median of $k$ re-executions, with no quorum. Where that procedure breaks is the main result. On a synthetic HotpotQA pipeline a calibrated fixed threshold accepts 44 of 45 honest reproductions and rejects 104 of 105 divergent pairs, yet lets same-input fabrication through in 27 of 29 trials at k=5, more samples being no help since sampling sharpens an estimate without moving it. Holding that metric and this pipeline's re-execution spread fixed, the binding constraint is the threshold rather than the sample size: one derived per execution detects 19 of 29 where the best constant matched to the same zero honest rejections reaches 9, rejects no honest commitment at k=5 though 3 of 15 at k=3, and catches 11 of 15 of an attacker built against it, which has to aim at a target drawn only after its commitment exists. That rule is measured rather than deployed.
1 Introduction
Compound AI workflows combine nondeterministic multi-stage computation with distributed ownership and disappearing intermediate state, making reproduction verification difficult. The paper proposes a trustless protocol addressing nondeterminism, dishonest reporting, and intermittent connectivity together.
- Compound AI pipelines can vary across runs because sampling, model drift, and changing tool responses affect stage outputs.
- Edge, cloud, and orbital optimizations may delete or relocate intermediate results needed for independent reproduction checks.
- Verification must tolerate legitimate nondeterminism, dishonest recorders, and unreachable shared records, whereas prior work addresses at most two conditions together.
- The protocol commits stage data and policy, anchors claims without a trusted arbiter, supports deferred anchoring, and challenges using median re-executions.
2 Related Work
Prior work separately studies semantic reproduction, decentralized provenance, and continuum placement, but no prior line combines all three verification conditions. This paper addresses that gap while limiting soundness to divergent claims rather than fabrication inside an accepted equivalence class.
- Semantic-reproduction methods compare meaning but may trust the recorder and assume a reachable reference, while provenance systems often assume deterministic computation.
- Prior work covers semantic comparison, decentralized anchoring, or distributed placement, but Table 1 identifies no line covering all three conditions together.
- Continuum orchestrators improve placement without preserving a verifiable record for later reproduction.
- The paper’s soundness claim concerns divergent commitments, not fabrication that remains inside the metric’s accepted equivalence class.
3 Problem and Threat Model
The paper models nondeterministic stages whose semantic reproduction is defined by a committed metric and threshold rather than bit equality. It assumes an untrusted recorder and eventual ledger reachability, while bounding identifier and provenance guarantees.
- A stage produces an output and execution context, and reproduction succeeds when a later run satisfies the committed stage-specific metric threshold.
- Semantic comparison replaces bit equality because nondeterministic stages may legitimately produce different outputs.
- The recorder may fabricate, replay, or withhold claims, while signatures protect anchored commitments from alteration.
- On-chain execution identifiers and predecessor links prevent duplicate or non-extending commitments per recorder, but do not establish execution provenance.
- The model assumes eventual ledger reachability and pre-fixed policy and dispatch identity; it excludes provider compromise, key-management issues, and universal challenger collusion.
4 Protocol Design
The protocol commits stage artifacts and policy at execution boundaries, anchors them in a predecessor chain, and lets any party challenge independently using median re-executions. Retention failures defer or terminate verification, while the procedure remains vulnerable to accepted-region fabrication.
- 4.1 Commitment at the Stage Boundary: Stage commitments hash inputs, outputs, context, recorder identity, execution links, and a policy fixing the metric, threshold, environment, and retention interval.
- 4.1 Commitment at the Stage Boundary: A digest is saved before intermediate-state deletion and anchored on a decentralized ledger so later parties can rerun the stage without a trusted arbiter.
- 4.2 Nondeterminism Classes: Metrics and thresholds vary by nondeterminism type, including semantic thresholds for sampling, numeric tolerances for pinned seeds, and spread-derived thresholds.
- 4.3 The Challenge Procedure: A challenge retrieves committed data, reruns the stage k times, and accepts exactly when the median metric is at most τ.
- 4.3 The Challenge Procedure: The procedure uses no quorum, but challengers may disagree and attackers can pass every challenge by fabricating within the metric’s acceptance region.
- 4.4 Artifact Retention: If required artifacts are unavailable within the retention interval, verification returns Unavailable without re-execution and cannot distinguish refusal from partition or challenger fault.
5 Implementation
The implementation anchors stage-level digests and enforces execution and recorder-chain bindings through a Solidity contract, while the harness verifies retained artifacts before re-execution. Environment pinning improves reproducibility but remains incomplete because provider weights and machine configuration can change.
- 5.1 Anchor Contract: AnchorRegistryV2 stores stage digests, policy and chain metadata, while execution identifiers and predecessor links are recovered from events.The contract enforces sequence monotonicity, unique execution commitments, and chain extension through three reverting mappings.
- 5.1 Anchor Contract: The contract costs 216,998 gas per anchor and was deployed on Sepolia after verification against all three bindings.The deployment uses Solidity 0.8.35 and exposes the execution identifier and chain link through logs rather than stored fields.
- 5.2 Synthetic Pipeline: The harness computes and anchors three boundary digests, retaining stage artifacts in content-addressed storage for challenge-time retrieval and re-hashing.A challenger verifies artifact availability and integrity before re-executing against the committed material.
- 5.2 Synthetic Pipeline: Prompt pinning corrected an early 0.95 score gap between honest reproductions, but provider weights, machine configuration, and model-name-only pinning remain unreconstructable.The resulting environment commitment identifies an environment without fully reproducing it, so thresholds calibrated here require recalibration elsewhere.
6 Evaluation
The evaluation shows that verification quality is bounded more by threshold design than by repeated sampling: fixed thresholds handle divergent outputs but often accept same-input fabrication, while a per-execution rule improves detection under the tested conditions. Partition tests additionally show deferred anchoring and ordered chains, but not liveness against a recorder that withholds evidence.
- 6.2 Semantic-Reproduction Fidelity: 44 of 45 honest reproductions were accepted and 104 of 105 divergent pairs rejected at the calibrated fixed threshold, but no threshold separated the two populations.The held-out accuracy was 98.7%, with one error of each kind; the populations overlapped between 0.577 and 0.651.
- 6.3 Soundness Under an Adversarial Recorder: 27 of 29 same-input fabrications passed at k = 5, showing that repeated sampling sharpened the distance estimate without moving a fabrication already below the threshold.Detection fell from 10% at k = 1 to 7% at k = 5 in the reported trials.
- 6.4 A Per-Execution Threshold: 19 of 29 same-input fabrications were detected by the per-execution rule, versus 9 of 29 for the best matched constant with zero honest rejections.The constant used τ = 0.437 and was granted the same zero-false-rejection operating point; the comparison was scored on identical trials.
- 6.4 A Per-Execution Threshold: At k = 3, 4, and 5, per-execution detection was 19, 20, and 19 of 29 for D2, while honest acceptance rose from 12 of 15 to 15 of 15.The rule estimates spread from 3 pairwise distances at k = 3 versus 10 at k = 5, so sparse estimates can falsely accuse honest recorders.
- 6.4 A Per-Execution Threshold: The threshold-aware attacker was detected in 11 of 15 trials, whereas the committed threshold detected none of those same commitments.The challenger’s threshold is estimated from re-executions drawn after the commitment exists, so the attacker targets a not-yet-realized value.
- 6.5 Partition Tolerance and Fork Behaviour: Three disconnected commitments were deferred and anchored in order after reconnect, but a partitioned recorder’s undisclosed fork was not detected at anchor time.The evaluation therefore supports ordered immutability conditional on eventual submission, not liveness against the recorder itself.
7 Discussion and Limitations
The evaluation is a proof-of-concept with synthetic, single-process scope and several untested distributed assumptions. The paper identifies concrete extensions for calibrated sequential testing and detecting withheld branches.
- Scope limitations: The proof-of-concept does not evaluate live edge-cloud-orbital execution, distributed retrieval, challenges across gaps, or restart recovery.The pipeline is a synthetic three-stage HotpotQA sequence running in one process; contact-window durations also come from orbital-mechanics literature rather than live traces.
- Scope limitations: The metrics cover only this pipeline’s three nondeterminism categories, while soundness remains relative to the committed metric rather than correctness.The execution identifier and predecessor chain are exercised with one recorder on one testnet and serialize by construction, so stalled predecessors block queued work.
- Scope limitations: The protocol establishes plausibility under a committed metric, not execution provenance, and its diagnostic is not yet adjudicated.Adjudication would require pinned rules and challenge randomness, an on-chain verdict, verifiable request and delivery evidence, and a dispatcher signature.
- Future work: An anytime-valid e-process could bound false-accusation rates and allow challengers to stop when evidence suffices.This would replace the hand-fixed κ in Section 6.4 with a conformal p-value formulation.
- Future work: Witnesses that countersign and gossip a recorder’s claimed head could detect a withheld branch once one witness is honest and reachable.The proposed mechanism addresses the fork that cannot be caught at commit time.
8 Conclusion and Future Work
The paper presents a quorum-free protocol for nondeterministic verification under untrusted execution and intermittent connectivity. Its central finding is that threshold choice, rather than increasing the re-execution sample size, bounds detection under the tested metric and pipeline.
- 8 Conclusion and Future Work: A per-execution threshold detects 19 of 29 fabrications at k = 5, versus 9 for the best matched constant, without rejecting honest commitments.The comparison holds the metric and pipeline re-execution spread fixed; the matched constant uses the same zero honest rejections.
- 8 Conclusion and Future Work: The protocol commits stage inputs, outputs, context, and policy, anchors them under an execution identifier and predecessor chain, and challenges median k re-executions without a quorum.The conclusion frames this design as addressing three conditions that prior work covers at most two of at once.
- 8 Conclusion and Future Work: Fabrications close under the committed metric passed in most trials, showing that increasing sample size does not repair the tested diagnostic.The conclusion reports the threshold as the binding boundary while holding the metric and re-execution spread fixed.
- 8 Conclusion and Future Work: The diagnostic caught 11 of 15 trials against an attacker built after the commitment existed, and 6 of 10 when that attacker could abstain.The committed constant caught none in the first comparison, while the matched constant caught 2.
- 8 Conclusion and Future Work: The contract, pipeline, and analysis scripts behind the reported numbers are publicly available.The paper provides a GitHub repository for these artifacts.