Threshold Choice, Not Sample Size, Bounds Trustless Verification of Nondeterministic Compound AI Workflows

• URL: http://arxiv.org/abs/2609.10601v1
• Date: Mon, 07 Sep 2026 22:10:54 GMT
• Title: Threshold Choice, Not Sample Size, Bounds Trustless Verification of Nondeterministic Compound AI Workflows
• Abstract summary: Compound AI pipelines chain LLM calls, retrievers, and tools are nondeterministic.<n>We give a protocol covering all three: it commits digests of each stage's inputs, outputs, and context.<n>On a synthetic HotpotQA pipeline a calibrated fixed threshold accepts 44 of 45 honest reproductions and rejects 104 of 105 divergent pairs.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• When Agent Metrics Measure Different Things: An Evidence-Grounded Audit of the Praxa AI Pipeline [0.0]
  We present a retrospective measurement audit of selected Praxa AI implementation files, historical evaluation artifacts, and operational records.<n>A 139-case offline routing report contains 112 passes and 27 failures despite zero gating failures.<n>The pooled recorded 99th percentile is 2,147,483,647 ms, versus 38,118.31 ms among server-observed completed calls.
  arXiv  Detail & Related papers  (2026-09-10T07:55:12Z)
• SWE-Test: Benchmarking LLM Vulnerability Discovery via Input Prediction [13.719725391379276]
  Vulnerability discovery is an important ability of large language model (LLM) agents.<n>We recast its measurement as an input-prediction task with a closed, deterministic ground truth.<n>This decomposes discovery into three task modes over 22 real-world C/C++ programs spanning 15 domains.
  arXiv  Detail & Related papers  (2026-09-05T19:04:41Z)
• When Many Answers Are Valid, Voting Fails: Symbolic Verification for Best-of-K Causal Reasoning in LLMs [42.32694162421078]
  We introduce CALVER, a training-free symbolic verifier that scores structured traces against Pearl's causal criteria.<n>On CLEAR find-one-valid queries that admit multiple graph-valid answers, CALVER reaches 42.1% where plurality, a reward model, an LLM judge, and model confidence remain near 30%.
  arXiv  Detail & Related papers  (2026-08-04T11:45:46Z)
• TraceCompiler: Skill-Guided Mining and Compilation of LLM Agent Traces into Mostly Deterministic Workflows [2.435006380732194]
  We present TraceCompiler, a skill-guided system that compiles noisy traces into trajectories.<n>Every hard edge carries an auditable evidence, and ambiguous relations are marked suspected.<n>We measure call reduction but not offline compilation cost, so we claim no net efficiency result.
  arXiv  Detail & Related papers  (2026-08-03T01:05:06Z)
• A multiverse-consensus pipeline for reproducible feature selection in untargeted LC-MS metabolomics [1.452875650827562]
  Untargeted LC-MS metabolomics requires a long chain of preprocessing decisions.<n>We adapt multiverse analysis to untargeted metabolomics feature selection.
  arXiv  Detail & Related papers  (2026-07-19T17:14:17Z)
• SpanUQ: Span-Level Uncertainty Quantification for Large Language Model Generation [39.25766957943906]
  We introduce SPANUQ, a lightweight probe that distills the uncertainty knowledge from expensive multi-sample inference into a single forward pass over hidden states.<n>We construct SPANUQ-BENCH, the first span-level uncertainty benchmark comprising 20K prompts, 293K annotated spans, and continuous soft labels.<n>Experiments show that SPANUQ consistently achieves the best span-level uncertainty quality, outperforming the strongest probe baseline and all sampling-based methods.
  arXiv  Detail & Related papers  (2026-07-07T01:09:46Z)
• Metric Aggregation Divergence: A Hidden Validity Threat in Agent-Based Policy Optimization and a Contractual Remedy [7.1976264551575895]
  Metric aggregation divergence (MAD) is the silent inconsistency that arises when distinct pipeline stages in an agent-based model.<n>We introduce the metric contract - a single callable runtime enforced at dispatch time - as the remedy.
  arXiv  Detail & Related papers  (2026-06-27T18:17:33Z)
• SNARE: Adaptive Scenario Synthesis for Eliciting Overeager Behavior in Coding Agents [40.270213696031625]
  A coding agent executes a benign task as a sequence of shell, file, and network actions, any of which can quietly exceed the authorized scope while the task still completes.<n>We call this overeager behavior: the prompt is not adversarial and the run succeeds, yet an out-of-scope step can leak credentials or delete files.<n>Existing benchmarks miss it: task-completion suites credit any finished run, jailbreak suites probe adversarial prompts, and the one prior overeager benchmark applies a single fixed prompt to every agent-model pair.<n>We present SNARE, a pipeline that composes benign scenarios from reusable scope
  arXiv  Detail & Related papers  (2026-05-27T08:14:07Z)
• Distributional Energy-Based Models for Uncertainty-Aware Structured LLM Reasoning [40.342912574072024]
  Large Language Models produce structured outputs such as travel plans or code solutions.<n>Individual reasoning steps may appear correct while the output as a whole violates budgets, fails test cases, or contradicts earlier deductions.<n>We propose a learned quality scorer with deterministic analytical constraint penalties for verifying structured LLM outputs.
  arXiv  Detail & Related papers  (2026-05-15T17:08:27Z)
• Large Language Models Are Bad Dice Players: LLMs Struggle to Generate Random Numbers from Statistical Distributions [50.1404916337174]
  We present the first large-scale, statistically powered audit of native probabilistic sampling in large language models (LLMs)<n>We show that batch generation achieves only modest statistical validity, with a 13% median pass rate, while independent requests collapse almost entirely.<n>We conclude that current LLMs lack a functional internal sampler, necessitating the use of external tools for applications requiring statistical guarantees.
  arXiv  Detail & Related papers  (2026-01-08T22:33:12Z)
• Ensemble Threshold Calibration for Stable Sensitivity Control [0.0]
  We present an end-to-end framework that achieves exact recall with sub-percent variance over tens of millions of geometry pairs.<n>Our approach consistently hits a recall target within a small error, decreases redundant verifications relative to other calibrations, and runs end-to-end on a single TPU v3 core.
  arXiv  Detail & Related papers  (2025-10-02T15:22:28Z)
• Eigen-1: Adaptive Multi-Agent Refinement with Monitor-Based RAG for Scientific Reasoning [53.45095336430027]
  We develop a unified framework that combines implicit retrieval and structured collaboration.<n>On Humanity's Last Exam (HLE) Bio/Chem Gold, our framework achieves 48.3% accuracy.<n>Results on SuperGPQA and TRQA confirm robustness across domains.
  arXiv  Detail & Related papers  (2025-09-25T14:05:55Z)
• Fact or Facsimile? Evaluating the Factual Robustness of Modern Retrievers [34.31192184496381]
  Dense retrievers and rerankers are central to retrieval-augmented generation (RAG) pipelines.<n>We evaluate how much factual competence these components inherit or lose from large language models (LLMs) they are based on.<n>For every embedding model, cosine-similarity scores between queries and correct completions are significantly higher than those for incorrect ones.
  arXiv  Detail & Related papers  (2025-08-28T04:13:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.