한국어 초록
복잡한 알고리즘의 형식 검증에는 프로그램 명세, 불변식 구성, 수학적 증명, 자동 정리 증명기 관리에 대한 전문성이 필요하다. 대규모 언어 모델(LLM)이 프로그램 코드와 증명 조각을 생성할 수는 있지만, 완전한 기계 검증 결과를 안정적으로 개발하는 일은 여전히 어렵다. 이는 명세와 불변식을 구성하고 검증하며, 증명을 구축하고, 솔버 실패를 진단하며, 검증 성능을 최적화하는 반복 과정을 요구하기 때문이다. 본 논문은 Dafny 검증 시스템을 사용하여 과학 알고리즘을 LLM 지원으로 검증하기 위한 체계적인 10단계 워크플로를 제시한다. 이 워크플로는 알고리즘 형식화, 계약 개발, 경험적 불변식 검증, 증명 구축, 병목 프로파일링, 자원 기반 증명 최적화를 통합한다. 본 연구는 Anthropic의 Claude Opus 5 및 Opus 5.5 모델을 사용하여 워크플로를 적용했으며, LLM 주도 개발을 자동화된 테스트 및 검증 피드백과 결합하고 정확성이 중요한 결정과 전략적 개입에는 사람의 감독을 유지했다. 그래프 이론과 레이블 전이 시스템의 복잡한 알고리즘 37개에 대해 이 접근법을 평가한다. 특히 Hopcroft-Tarjan 삼연결성 검사를 검증하였으며, 이는 매우 어려운 알고리즘 검증 과제도 구조화된 LLM 지원 워크플로를 통해 수행할 수 있음을 보여 준다. 기계 검증된 결과 중 다수는 몇 시간에서 며칠 정도의 대화형 개발 내에 얻어졌다. 이러한 결과는 LLM 지원 워크플로가 사람 검증자의 역할을 세부적인 증명 구성에서 감독, 명세 검토, 전략적 안내로 옮길 수 있음을 시사한다.
원문 초록
Formal verification of complex algorithms requires expertise in program specification, invariant construction, mathematical proof, and the management of automated theorem provers. Although large language models (LLMs) can generate program code and proof fragments, reliably developing complete machine-checked verifications remains challenging: it requires an iterative process of constructing and validating specifications and invariants, building proofs, diagnosing solver failures, and optimizing verification performance. This paper presents a systematic ten-step workflow for LLM-assisted verification of scientific algorithms using the Dafny verification system. The workflow integrates algorithm formalization, contract development, empirical invariant validation, proof construction, bottleneck profiling, and resource-driven proof optimization. We applied the workflow using Antrhopic's Claude Opus 5 and Opus 5.5 models, combining LLM-driven development with automated testing and verification feedback, while retaining human oversight for correctness-critical decisions and strategic interventions. We evaluate the approach on 37 complex algorithms from graph theory and labelled transition systems. Notably, we verified the Hopfcroft-Tarjan triconnectivity test, demonstrating that even highly challenging algorithmic verification tasks can be carried out through a structured LLM-assisted workflow. Many of our machine-checked verifications were obtained within hours to a few days of interactive development. Our results suggest that LLM-assisted workflows can shift the role of the human verifier from detailed proof construction toward supervision, specification review, and strategic guidance.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
16 pages (excluding references), 20 pages including references; 1 figure, 2 tables. Submitted to FSEN 2027