Efficient Branch-and-Bound Testing and Verification of zkVMs

• URL: http://arxiv.org/abs/2609.15020v1
• Date: Mon, 14 Sep 2026 04:35:11 GMT
• Title: Efficient Branch-and-Bound Testing and Verification of zkVMs
• Abstract summary: We present ZEBRA, a fully automated verification and bug-detection framework.<n>ZEBRA reduces zkVM verification to a solution-set cardinality problem over a canonical trace space.<n>ZEBRA discovers 11 zero-day bugs; 6 have already been independently confirmed and 3 have been fixed by developers.
• Score: 26.60003840008197
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Zero-knowledge virtual machines (zkVMs) enable verifiable execution of general-purpose programs by translating virtual machine semantics into algebraic constraints over execution traces. The correctness of these constraints is critical: a single incorrect constraint can admit forged proofs (under-constrained) or reject valid executions (over-constrained). Existing approaches do not provide meaningful guarantees at production scale: fuzzers and unit tests often miss bugs, SMT solvers struggle with the size and nonlinearity of constraints, and theorem provers require substantial manual effort. We present ZEBRA, a fully automated verification and bug-detection framework: for a given program and input, the constraint must admit exactly one valid execution trace - no more and no fewer. This reduces zkVM verification to a solution-set cardinality problem over a canonical trace space, where redundancies such as null-row padding and non-deterministic permutations are eliminated prior to counting. To compute cardinality tractably, ZEBRA lifts analysis from finite-field witnesses to an integer interval lattice, exploiting a structural sparsity property of zkVM constraints: across 5 real-world zkVMs, constraints utilize only 14.0% of their theoretical connectivity capacity on average. This sparsity enables tight interval propagation with limited approximation error. ZEBRA performs a parallel branch-and-bound search that either produces a concrete counter-example or certifies the absence of violations within a bounded region. We evaluate ZEBRA on five real-world zkVMs. ZEBRA discovers 11 zero-day bugs; 6 have already been independently confirmed and 3 have been fixed by developers. Compared to SMT-based verification, ZEBRA is 51.5x faster, verifies 16.5 percentage point more instances, and its range verification provides up to 63x efficiency gain over repeated single-input verification.

Related papers

• Constraint-Aware Synthetic Tabular Data Generation via Inter-Column Constraint Discovery with LLM Agents [3.7680093320209553]
  We study the discovery and enforcement of three complementary inter-column constraint families.<n>Our unified tool-grounded workflow represents all three as machine-executable hypotheses.
  arXiv  Detail & Related papers  (2026-08-15T08:19:54Z)
• Constraint-Anchored Reasoning Traces [9.39195684989942]
  Autoregressive multimodal large language models (MLLMs) suffer from error snowballing.<n>In state-of-the-art open-source MLLMs, once the first error occurs, the reasoning cascades into failure across all remaining steps in 65% of such cases.<n>We propose Constraint-Anchored Reasoning Traces (CART), a neuro-symbolic framework that trains MLLMs to interleave natural language reasoning steps with symbolic constraint assertions.
  arXiv  Detail & Related papers  (2026-07-18T09:24:45Z)
• LinAlg-Bench: A Forensic Benchmark Revealing Structural Failure Modes in LLM Mathematical Reasoning [0.0]
  LinAlg-Bench is a diagnostic benchmark evaluating 10 frontier large language models on structured linear algebra computation.<n>The benchmark exhaustively evaluates 6,600 model outputs.
  arXiv  Detail & Related papers  (2026-05-15T22:30:57Z)
• CCTU: A Benchmark for Tool Use under Complex Constraints [66.87622847854337]
  We introduce CCTU, a benchmark for evaluating large language models (LLMs) under complex constraints.<n>The benchmark comprises 200 carefully curated and challenging test cases across diverse tool-use scenarios.<n>We develop an executable constraint validation module that performs step-level validation and enforces compliance.
  arXiv  Detail & Related papers  (2026-03-16T14:05:13Z)
• zkCraft: Prompt-Guided LLM as a Zero-Shot Mutation Pattern Oracle for TCCT-Powered ZK Fuzzing [7.274627641804014]
  zkCraft is a framework that combines deterministic, R1CS-aware localization with proof-bearing search to detect semantic inconsistencies.<n>We show that proof-bearing localization detects diverse under- and over-constrained faults with low false positives and reduces costly solver interaction.
  arXiv  Detail & Related papers  (2026-01-31T11:31:00Z)
• CARE What Fails: Contrastive Anchored-REflection for Verifiable Multimodal [84.71254539482369]
  Group-relative reinforcement learning with verifiable rewards (RLVR) often wastes the most informative data it already has the failures.<n>We present CARE, a failure-centric post-training framework for multimodal reasoning that turns errors into supervision.<n> CARE improves accuracy and training smoothness while explicitly increasing the share of learning signal that comes from failures.
  arXiv  Detail & Related papers  (2025-12-22T16:34:21Z)
• Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification [9.733843486234878]
  State-of-the-art neural network (NN) verifiers demonstrate that applying the branch-and-bound (BaB) procedure with fast bounding techniques plays a key role in tackling many challenging verification properties.<n>We introduce the linear constraint-driven clipping framework, a class of scalable and efficient methods designed to enhance the efficacy of NN verifiers.
  arXiv  Detail & Related papers  (2025-12-11T19:59:37Z)
• Unsupervised Conformal Inference: Bootstrapping and Alignment to Control LLM Uncertainty [49.19257648205146]
  We propose an unsupervised conformal inference framework for generation.<n>Our gates achieve close-to-nominal coverage and provide tighter, more stable thresholds than split UCP.<n>The result is a label-free, API-compatible gate for test-time filtering.
  arXiv  Detail & Related papers  (2025-09-26T23:40:47Z)
• Latent Veracity Inference for Identifying Errors in Stepwise Reasoning [78.29317733206643]
  We introduce Veracity Search (VS), a discrete search algorithm over veracity assignments.<n>It performs otherwise intractable inference in the posterior distribution over latent veracity values.<n>It generalizes VS, enabling accurate zero-shot veracity inference in novel contexts.
  arXiv  Detail & Related papers  (2025-05-17T04:16:36Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• SEAL: Steerable Reasoning Calibration of Large Language Models for Free [58.931194824519935]
  Large Language Models (LLMs) have demonstrated compelling capabilities for complex reasoning tasks via the extended chain-of-thought (CoT) reasoning mechanism.<n>Recent studies reveal substantial redundancy in the CoT reasoning traces, which negatively impacts model performance.<n>We introduce SEAL, a training-free approach that seamlessly calibrates the CoT process, improving accuracy while demonstrating significant efficiency gains.
  arXiv  Detail & Related papers  (2025-04-07T02:42:07Z)
• RAYEN: Imposition of Hard Convex Constraints on Neural Networks [47.494620411594624]
  RAYEN is a framework to impose hard convex constraints on a neural network. It achieves times between 20 and 7468 times faster than state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2023-07-17T09:12:05Z)

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.