arXiv:2610.10604v1 cs.SE

타입 검사를 넘어서: 정형 명세 생성의 종합적 평가를 향하여

Beyond Type-checking: Towards Holistic Evaluation of Formal Specification Generation

Srijith Nair, Aditya Vempaty, Jia Liu, Ashish Jagmohan

제출 2026-10-07

저자 비고

arXiv Comments

Accepted at NeurIPS 2026 Workshop on AI for Verifiable Coding (20 pages, 7 figures)

한국어 초록

검증 가능한 코드를 생성할 때, 대규모 언어 모델(LLM)과 에이전트(agent) 워크플로를 사용하여 자연어 요구사항을 기계 검증된 코드로 매핑합니다. 이 파이프라인의 핵심 구성 요소는 에이전트가 구현의 정확성을 증명할 수 있는 정형 계약을 생성하는 명세 생성(SpecGen)입니다. 증명 생성은 정리 증명기(theorem prover)로부터 결정론적 피드백을 얻을 수 있지만, SpecGen은 생성된 명세가 사용자의 의도를 제대로 포착했는지에 대한 결정적인 검증 수단이 부족합니다. 따라서 검증을 통과한 증명이라 하더라도 의도된 동작을 잘못 나타내는 명세를 기준으로 정확성을 입증하는 문제가 발생할 수 있습니다. 본 연구에서는 VERINA의 $189$개 및 CLEVER의 $161$개를 포함하여 기존의 $350$개 Lean 작업으로 구성된 통합 데이터셋(dataset)과, 정형적 타당성, 참조 유사도 및 동치성, 동작 적절성을 다루는 프레임워크를 통해 총체적인 SpecGen 평가를 향한 한 걸음을 내딛습니다. 본 연구는 필수 입력의 수용을 유효한 출력의 수용 및 무효한 출력의 거부와 구별하는 동시에, 각 지표의 근거 범위를 명시적으로 만듭니다. 네 가지 SpecGen 구성에 걸쳐 참조 유사도 측정 지표인 일반화된 트리 편집 거리(GTED) 비교를 공동 측정이 가능한 $32$개의 VERINA 작업으로 제한하면, 평균 유사도에서 VERINA 구성의 순위가 2위에서 4위로 변경되어 측정 범위(coverage)의 중요성을 보여줍니다. 직접 작성한 대조군 실험에서는 한 명세가 필수 입력을 $0\%$만 수용하면서도 $100\%$의 양성 테스트 재현율(recall) 및 음성 테스트 거부를 달성했습니다. 이는 완벽한 사후 조건 점수가 사용 불가능한 입력 계약을 놓칠 수 있음을 입증하며, 입력 범위와 출력 제약 조건에 대한 분리된 피드백의 필요성을 시사합니다.

원문 초록

When generating verifiable code, natural language requirements are mapped to machine checked code using LLMs and agentic workflows. A crucial component of this pipeline is specification generation (SpecGen), which produces a formal contract against which an agent can prove implementation correctness. Proof generation can obtain deterministic feedback from a theorem prover, but SpecGen lacks a definitive check that a generated specification captures the user's intent. A checked proof can therefore establish correctness against a specification that misrepresents the intended behaviour. We take a step towards holistic SpecGen evaluation with a unified dataset assembled from $350$ existing Lean tasks, including $189$ from VERINA and $161$ from CLEVER, and a framework covering formal validity, reference similarity and equivalence, and behavioural adequacy. We distinguish acceptance of required inputs from acceptance of valid outputs and rejection of invalid outputs, while making each metric's evidence scope explicit. Across four SpecGen configurations, restricting the generalized tree edit distance (GTED) comparison, a reference similarity measure, to $32$ jointly measurable VERINA tasks changes the VERINA configuration's position from second to fourth in mean similarity, showing the importance of measurement coverage. In an authored control, a specification achieves $100\%$ positive test recall and negative test rejection while accepting $0\%$ of required inputs. This demonstrates that perfect postcondition scores can miss an unusable input contract, motivating separate feedback on input coverage and output constraints.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.10604v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.00885v1cs.SE공통 태그 Code Generation, theorem proving, formal verification

형식 수학 및 소프트웨어 검증에서 감사 가능한 추론을 위한 FORALL-LEAN-AGENT

FORALL-LEAN-AGENT for Auditable Reasoning in Formal Mathematics and Software Verification

코딩 에이전트(agent)는 Lean 증명 개발을 점점 더 자동화하고 있지만, 컴파일 성공만으로는 후보 증명이 허용 가능한 가정 하에서 의도한 명제를 증명한다는 점을 확증하지 못합니다. 본 논문에서는 형식 수학 및 소프트웨어 검증에서 감사 가능한 추론을 위한 프런트엔드 독립적 프레임워크인 FORALL-LEAN-AGENT를 제시합니다. 이 프레임워크는 격리된 작업 공간, Lean 도구, 새로운 검토를 명제 비교, 공리 감사, 그리고 지원되는 경우 독립적인 증명 검사와 결합합니다. 검증 증거와 검토자의 결정은 동일한 후보 아티팩트에 바인딩되어 수락 과정을 추적할 수 있도록 합니다. 우리는 VeriSoftBench, PutnamBench, 그리고 Lean Eval 소프트웨어 검증 트랙의 두 문제 모두에서 이 프레임워크를 평가합니다. 100개 과제로 구성된 VeriSoftBench 하위 집합에서, FORALLLEAN-AGENT와의 통합은 GPT-5.6 Sol의 벤치마크 규칙 성공을 낮은 노력으로 93개에서 100개로 높이는 동시에 비용을 69달러에서 62달러로 절감합니다. PutnamBench 평가에서는 전체 672개 문제를 평균 4.72달러에 모두 통과시킵니다. 이러한 결과는 에이전트 하네스 설계가 총 해결 횟수를 넘어서는 증거를 제공하는 동시에 정확성과 효율성을 향상시킬 수 있음을 보여줍니다.

arXiv:2610.13461v1cs.AI공통 태그 theorem proving, formal verification

SqueezeBench: 포화에 강건한 수학적 능력 평가

SqueezeBench: Saturation-Resilient Evaluation of Mathematical Capability

AI 시스템은 수학 분야에서 빠르게 발전하고 있지만, 이러한 발전을 측정하기는 어렵다. 이미 풀린 문제들로 구성된 벤치마크(benchmark)는 포화(saturate)되며, 미해결 문제들로 구성된 벤치마크에서는 각 문제가 최초로 단 한 번만 해결될 수 있다. 우리는 포화에 강건한 벤치마크인 SqueezeBench를 제시한다: 성공은 문제를 제거하는 대신 기준을 높인다. 각 문제는 작은 $n$에 대해서만 값이 알려진 정수 함수 $f(n)$을 고정하며, 벤치마크는 이에 대한 하한(lower) 기록과 상한(upper) 기록을 유지한다. 기록(record)은 $f$를 한정(bound)함을 기계 검증된 증명(machine-checked proof)으로 보인 계산 가능한 Lean 함수이다. 제출(submission)은 새로운 함수를 제안하고, 그 함수가 $f$를 한정하며, 모든 $n$에서 현재 기록보다 나쁘지 않고, 일부 $n$에서는 엄밀히 더 우수함을 증명한다. 채택되면 해당 제출은 다음 제출이 넘어서야 할 새로운 기록이 된다. 따라서 이 시스템은 한계값(bound)뿐 아니라 그 증명까지 선택하며, 단일 $n$에서의 기록을 개선할 수도 있고 성장률(growth rate)을 개선할 수도 있다. 모든 $n$에서 두 기록 사이의 간극은 인증된 한계값들이 $f(n)$을 결정하는 데에서 얼마나 떨어져 있는지를 보여준다. 모든 증명은 두 개의 독립적인 Lean 커널에 의해 검증되므로, 심판이 수학적 내용을 검토할 필요가 없다. 검증 과정은 또한 작은 $n$에서 전수 탐색(exhaustive search)으로 $f$를 계산하는 함수를 거부하며, 유지관리자(maintainer)는 제출자의 보고서만 읽고 더 큰 $n$에서 그러한 탐색이 있는지를 확인한다. 우리는 극단적 조합론(extremal combinatorics) 분야의 열 가지 문제를 스무 개의 증명된 초기 기록 및 승인 도구(admission tools)와 함께 공개한다. 기준선(baseline)으로서, 최신(frontier) 언어 모델(language model) 기반 에이전트(agent)는 기록당 최대 한 시간을 사용하여 82건의 제출을 승인받았고 모든 기록을 개선했으며, 이는 기존 발표된 문헌의 범위를 넘어서지는 않았다. 이후 두 개의 더 새로운 모델(model) 기반 에이전트들이 이 기록들로부터 시작하여 60건의 추가 제출을 승인받았고, 20개의 기록 중 19개를 다시 개선했다. 열 가지 문제 중 여덟 가지 문제에서는, 적어도 하나의 기록이 여전히 발표된 최선의 한계값(bound)에 비해 점근적으로(asymptotically) 뒤처져 있다.

arXiv:2609.39022v3cs.SE공통 태그 Code Generation, formal verification

검증 실패로부터 코딩 에이전트를 위한 재사용 가능한 지침 도출하기

From Verification Failures to Reusable Guidance for Coding Agents

코딩 에이전트(coding agent)는 프로그램이 명세(specification)를 만족하고, 해당 명세가 요구된 동작을 정확히 담아내고 있음을 입증해야 합니다. 본 연구에서는 검증 실패에 대한 전문가의 진단이 어떻게 이러한 작업을 위한 재사용 가능한 지침이 될 수 있는지 살펴봅니다. 본 접근 방식은 K 프레임워크의 실행 가능한 언어 정의와 명세 작성, 증명 수정, 그리고 적절성 감사를 위한 절차 키트를 결합합니다. 164개의 파이썬 프로그래밍 작업으로 구성된 벤치마크인 HumanEval에서 인간 주도형 개발을 진행한 결과, 해당 시맨틱과 키트를 적용하고 두 차례의 집중 수정을 거쳐 최종 AI 감사에서 '통과(Pass)' 판정을 받음으로써 164/164의 성공률을 달성했습니다. 성공적인 증명에서도 해결되지 않은 문제를 감사가 감지할 수 있는지 검증하기 위해, 저자 검토를 거친 12쌍의 정상 패키지와 결함 패키지를 구축했습니다. 모든 패키지는 K 증명을 통과했으며, 완료된 감사는 모든 결함을 식별하고 정상 패키지를 모두 승인했습니다. 이어 연산자 의미가 변경된 31개 프로그램을 대상으로 KleverBench를 사용하여 명세 및 증명 생성을 테스트했습니다. 완전한 수락 규칙 및 동일한 길이의 일반적인 조언과의 비교에서는 두 가지 모델과 예산 설정에 걸쳐 엇갈린 결과가 나타났으며, 이는 자원 한도 내에서 유용한 지침을 선별하는 후속 연구의 필요성을 시사합니다. 인간이 검토한 Optimism 증명은 무제한 가스 환경의 London 시맨틱 하에서 선언된 입력 범위 내 6개 연산에 대해 예상되는 일시 중지 되돌리기(pause revert)를 규명합니다. 본 논문에서는 검증 가능한 정확성 논거를 갖춘 프로그램을 제공하는 에이전트를 향한 진전, 난제, 그리고 교훈을 보고합니다.

arXiv:2608.20153v3cs.CL공통 태그 theorem proving, formal verification

FormalTCS: 대규모 언어 모델의 최전선 형식 이론 전산학 연구 전 과정(End-to-End) 벤치마킹

FormalTCS: Benchmarking End-to-End Frontier Formal Theoretical Computer Science Research of Large Language Models

대규모 언어 모델(LLM)은 이론 전산학(TCS) 연구 자동화에서 점점 더 큰 잠재력을 보여 왔지만, 기존 벤치마크는 현실적인 연구 환경과는 여전히 거리가 멀다. 본 논문에서는 최전선(frontier)의 end-to-end TCS 연구에 대한 LLM 평가를 위한, 전문가가 검증한 벤치마크인 \ourbenchmark를 소개한다. \ourbenchmark는 2025-2026년 STOC, FOCS, SODA, COLT에 채택된 논문에서 추출한 $143$개의 인스턴스로 구성되며, 논문별 정의, 가정, 증명 의존성을 그대로 보존하고, 전문가가 검증한 Lean 형식화와 증명을 포함한다. 주요 LLM에 대한 평가 결과, 현재 모델들은 전체 연구 파이프라인을 안정적으로 완수하는 데 여전히 크게 못 미치는 것으로 나타났다. 특히 자동 형식화(autoformalization)가 가장 큰 병목이다. 가장 성능이 좋은 모델은 자연어 주장을 형식 정리 명제로 번역하는 과제에서 $11.5$에 그친 반면, 사람이 제공한 형식 명제를 증명하는 과제에서는 Pass@8 기준 $28.6$을 달성했다. \ourbenchmark를 바탕으로, 새로운 주장을 생성하고, 형식화하고, 필터링하고, 증명하는 자동화된 TCS 연구 프레임워크도 추가로 개발한다. 생성된 $64$개의 주장 중 최종적으로 전문가 평가와 증명 검증을 모두 통과한 것은 $6$개에 불과했으며, 이는 형식화 외에도 제한적인 연구 안목(research taste)이 자율적 TCS 연구를 가로막는 또 다른 주요 장벽임을 시사한다.

arXiv:2609.21190v2cs.LG공통 태그 Code Generation, formal verification

SWE-Proof: 언어 모델이 기계 검증 증명으로 실세계 이슈를 해결할 수 있는가?

SWE-Proof: Can Language Models Resolve Real-World Issues with Machine-Checked Proofs?

LLM이 생성한 코드의 정확성을 보장하는 것은 현대 소프트웨어 공학의 핵심 과제이다. 에이전트 기반 코드 생성 벤치마크는 홀드아웃 테스트 스위트로 정확성을 검사하지만, 이는 본질적으로 불완전하고 점점 암기(memorization)에 취약해지고 있다. 형식 검증(formal verification)은 두 문제를 모두 피할 수 있으나, 기존 연구는 입력으로 명세가 주어진 독립형 작업만 다루며, 대규모 저장소를 건드리고 의도를 모호한 자연어로 표현하는 실제 이슈는 다루지 않는다. 우리는 알려진 올바른 패치가 있는 코딩 과제를 형식적으로 검증된 과제로 바꾸는 파이프라인 Benchproofer를 제시한다. 새 코드에 대한 명세(specification)를 작성하고, 그 코드가 호출하는 기존 함수들을 공리(axiom)로 요약하며, 기계적·적대적 게이트가 일치할 때만 인스턴스를 채택한다. SWE-bench Verified에 적용하면 테스트가 아닌 형식 검증으로 정확성이 입증된 500개의 실제 이슈인 SWE-Proof가 만들어지며, SWE-bench Pro로도 확장된다. Claude Opus 4.8을 평가한 결과, 검증은 테스트가 놓치는 것을 잡아낸다. 테스트를 통과한 패치의 4분의 1이 반례(counterexample)를 허용하며, 구조화된 자연어 명세는 이를 고치지 못하지만 올바른 형식 명세는 해결률을 85%에서 95%로 끌어올린다. 그 명세를 작성하는 것이 어려운 부분이다. 스스로 명세를 써야 하는 에이전트는 돕지 않은 기준선보다 이득이 없으며, 그러한 명세 중 56%만이 우리 감사(audit)를 통과한다. 흔한 실패는 충실성(faithfulness)으로, 필요한 동작의 일부만 제약하고 나머지는 자유롭게 두는 명세이다. 명세 품질은 여전히 결과와 상관관계를 보이며, 미해결 인스턴스의 92%에서 실패하는 반면 해결된 인스턴스에서는 51%에서 실패한다. 이로써 충실한 명세 합성은 구체적인 미해결 문제가 된다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.