반증 격차: 최적성 주장의 양쪽을 모두 인증하기
The Refutation Gap: Certifying Both Halves of an Optimality Claim
한국어 초록
합성 파이프라인은 점점 프로그램이 올바르다는 것뿐 아니라 최적이라는 주장까지 내세우고 있다. 이러한 주장은 검증 관점에서 근본적으로 다른 두 부분으로 나뉜다. 상한(upper bound)—"크기 m인 프로그램이 존재한다"—은 재실행할 수 있고 명세와 동치임을 증명할 수 있으며, 기계 검증(machine-checked) 인증서와 함께 배포할 수 있는 산출물(artifact)로 입증된다. 하한(lower bound)—"크기 m-1인 프로그램은 존재하지 않는다"—은 입증자(witness)가 없으며, 솔버가 UNSAT을 보고할 때까지 실행하여 입증한다. 조합 최적화(combinatorial optimization)는 수십 년 동안 이 비대칭을 알고 있었고 대체로 해결해 왔다. 인증 알고리즘(certifying algorithms)이 이를 명시적으로 다루고(McConnell et al., 2011), 의사 부울(pseudo-Boolean) 증명 로깅은 형식적으로 검증된 검증기로 최적성을 처음부터 끝까지 인증할 수 있다(Bogaerts et al., 2023; Koops et al., 2025). 그러한 규율은 회로 최소화(circuit minimization)에는 이르지 못했다. 우리는 이를 반증 격차(refutation gap)라 부른다. 최소 XOR 회로에 대한 발표된 게이트 수는 주장의 어느 쪽에 대해서도 인증서를 제공하지 않으며, 우리가 직접 산출한 121건의 최적성 결과 역시 마찬가지였다. 우리는 GF(2) 위의 최소 선형 straight-line 프로그램을 합성하는 파이프라인으로 이 격차를 메운다. 여기서 모든 결정적 UNSAT 응답은 독립적인 제3자 검증기가 검사하는 DRAT 증명을 출력한다. n = 6부터 9까지 프로젝트에서 확립한 121건의 최적성 결과를 모두 인증한다. 111건은 독립적으로 검증된 반증(refutation)을 갖고, 10건은 무상 counting bound로 종결되며, 어느 것도 미인증 값과 불일치하지 않는다. 증명의 중앙값 크기는 1.1 MB이며 검증 비용은 풀이의 1.9배이다. 코드 리뷰가 잡지 못한 결함을 검증이 포착한 다섯 가지 사례 연구를 제시하고, 실무자를 미인증 경로로 밀어가는 두 가지 인터페이스 장애물을 보고하며, 적대적 감사(adversarial audit)를 통해 우리가 곧 문제 탓으로 돌릴 뻔했던 실패 꼬리(failure tail)가 실제로는 자체 예산(budget) 때문이었음을 밝혀 냈다.
원문 초록
Synthesis pipelines increasingly claim not just that a program is correct, but that it is optimal. Such a claim has two halves with radically different verification stories. The upper bound, "a program of size m exists", is witnessed by an artifact that can be re-executed, proved equivalent to its specification, and shipped with a machine-checked certificate. The lower bound, "no program of size m-1 exists", has no witness and is discharged by running a solver until it reports UNSAT. Combinatorial optimization has known this asymmetry for decades and has largely addressed it: certifying algorithms make it explicit (McConnell et al., 2011), and pseudo-Boolean proof logging can certify optimality end to end with a formally verified checker (Bogaerts et al., 2023; Koops et al., 2025). That discipline has not reached circuit minimization. We call this the refutation gap: published gate counts for minimal XOR circuits provide no certificate for either half of the claim, and neither did 121 optimality results we ourselves produced. We close the gap with a pipeline that synthesizes minimal linear straight-line programs over GF(2), where every decisive UNSAT answer emits a DRAT proof checked by an independent third-party checker. We certify all 121 optimality results established by the project, across n = 6 to 9: 111 carry independently verified refutations, 10 are closed by a free counting bound, and none disagrees with the uncertified value. The median proof is 1.1 MB and checking costs 1.9x solving. We give five case studies where verification caught defects that code review did not, report two interface obstacles that push practitioners toward the uncertified path, and describe an adversarial audit that revealed a failure tail we were about to attribute to the problem was actually caused by our own budget.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.20873v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.