프로그램 검증에서 에이전트 오케스트레이션을 통한 비용 효율적인 정리 증명
Cost-Efficient Theorem Proving via Agent Orchestration in Program Verification
한국어 초록
프로그램 검증은 정리 증명기(theorem prover)에서 구축된 기계 검증 가능 증명을 통해 소프트웨어의 정확성을 확립합니다. 이는 유창하지만 정확성을 보장할 수 없는 대규모 언어 모델(LLM) 생성 코드에 특히 유용한 보증입니다. 그러나 기존의 거의 모든 증명기는 샘플링이나 탐색 예산이 얼마나 들든 합격률(pass rate)만을 추구하며 성공 대비 비용 곡선(success-vs-cost frontier)을 간과합니다. 하지만 실제 소프트웨어는 수백 개의 상호의존적인 증명 의무를 수반하는 경우가 많으므로, 대규모 환경에서 중요한 것은 하나의 정리를 증명할 수 있느냐가 아니라 얼마나 많은 정리를 경제적으로 증명할 수 있느냐입니다. 본 논문에서는 비용 제약 하에서의 메타레벨 의사결정으로 비용 효율적인 프로그램 증명을 공식화하고 2단계 증명 그래프에 기반한 CoCo-Prover를 소개합니다. 각 선언 내부의 AND/OR 증명 하이퍼그래프는 선언 간 보조정리 의존성 그래프와 결합되며, 매 단계마다 어떤 미해결 목표(open goal)를 선택할 것인지, 그리고 이러한 목표에 대해 어떤 행동을 비용을 지불하고 취할 것인지라는 두 가지 질문에 답합니다. 목표 선택은 증명 그래프에 대한 위상 정렬 순회로서 기호적(symbolic) 방식을 유지합니다. 행동 선택은 메타레벨 의사결정을 통한 에이전트 오케스트레이션입니다. 즉, 에이전트 기반 라우터는 한정된 전문가 호출 각각을 개별적으로 가격이 책정된 최선 노력(best-effort) 연산으로 취급하고, 증거가 축적됨에 따라 발전하는 라우팅 규칙에 따라 이종 전문가 에이전트들을 다양한 구성과 함께 매칭합니다. 함수 수준의 CLEVER, VERINA, AlgoVeri와 저장소 수준의 NTP4VC 및 Vero를 포함한 Lean 4 기반의 5개 프로그램 검증 벤치마크에서, CoCo-Prover가 프론티어 코딩 에이전트 및 최첨단 LLM 기반 증명기를 포함한 기준선(baseline) 대비 더 우수한 성공 대비 비용 곡선을 달성함을 보여줍니다. CoCo-Prover는 모든 벤치마크에서 최고 해결률을 달성했으며 두 벤치마크에서는 최대 100%를 기록했습니다. 또한 본 평가에서 가장 강력한 LLM을 사용한 가장 강력한 기준선과 비교해 비용을 최대 30.9% 절감합니다.
원문 초록
Program verification establishes software correctness through machine-checkable proofs constructed in theorem provers. It's a guarantee especially valuable for code generated by large language models (LLMs), which is fluent but carries no assurance of correctness. Almost all existing provers, however, pursue pass rates alone at whatever sampling or search budget it takes, and overlook the success-vs-cost frontier; yet real software often carries hundreds of interdependent proof obligations, so what matters at scale is not whether one theorem can be proved, but how many can be proved economically. 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. Selection stays symbolic as a topological pass over the proof graphs. 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. 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. It also reduces cost by up to 30.9% compared to the strongest baseline with the strongest LLM in our evaluation.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.