Cost-Efficient Theorem Proving via Agent Orchestration in Program Verification

Key points

• Program verification establishes software correctness through machine-checkable proofs constructed in theorem provers.1
• Selection stays symbolic as a topological pass over the proof graphs.1
• Action choice is agent orchestration via metalevel decision-making: an agentic router treats every bounded specialist invocation as a separately priced, best-effort computation, matching heterogeneous specialist agents together with configurations, under evolved routing rules as evidence accumulates.1
• On five program verification benchmarks in Lean 4 including function-level CLEVER, VERINA, and AlgoVeri, and repository-level NTP4VC and Vero, we show that CoCo-Prover achieves a better success-vs-cost frontier than baselines including frontier coding agents and state-of-the-art LLM-based provers: it achieves the best solve rate on every benchmark and up to 100% on two benchmarks.1

Sources (1)

• [1]Cost-Efficient Theorem Proving via Agent Orchestration in Program Verification
  arXiv (AI, ML, NLP, CV, robotics, multi-agent) · Oct 7, 08:42 AM

  We introduce CoCo-Prover, which formalizes cost-efficient program proving as metalevel decision-making under cost, grounded on two-level proof graphs: an AND/OR proof hypergraph within each declaration is joined to a lemma-dependency graph across declarations; and at each step, it answers two questions: which open goals to select, and which actions to purchase on these goals.

  Program verification establishes software correctness through machine-checkable proofs constructed in theorem provers.

Extractive summary: sentences quoted from the sources.