Lean과 LLM을 이용한 증명 자동화
Lean과 LLM을 이용한 증명 자동화
LLM은 형식적 검증을 실용적으로 만들고 있다
의존형 타입 언어의 채택에 대한 주요 장벽은 역사적으로 "증명 노력"—즉, 프로그램이 지정된 불변식을 준수함을 증명하기 위해 필요한 엄청난 양의 수작업—that... The seL4 마이크로커널 프로젝트는 이 오버헤드에 대한 벤치마크 역할을 하는데, 엔지니어들이 시스템을 설계하고 구현하는 데 걸린 시간보다 약 10배 더 많은 시간을 증명에 소비하여, C 코드보다 증명 코드의 줄 수가 20배 더 많게 되었습니다.
대형 언어 모델(LLM)은 이러한 증명 생성을 자동화함으로써 이 환경을 변화시키고 있습니다. Lean과 같은 의존형 타입 시스템은 증명이 올바른지 기계적으로 검증할 수 있기 때문에 LLM의 "환각" 위험이 제거됩니다: LLM이 잘못된 증명을 생성하면 타입 검 semplicemente 거부합니다. 이로 인해 소프트웨어 엔지니어링의 부담이 구현과 증명 작성을 하는 것에서 정확한 형식 명세를 작성하는 것으로 이동합니다.
사례 연구: Lean에서의 검증된 Zstandard 디컴프레서
Lean과 LLM 자동화의 교차점을 탐구하기 위해 Zstandard(zstd) 디컴프레서를 구현했습니다. Zstandard는 LZ77과 정교한 엔트로피 인코더인 Finite State Entropy(FSE)의 조합을 사용하는 고성능 압축 유틸리티입니다.
FSE의 도전
FSE는 여러 상태에 심볼을 분배함으로써 심볼당 분수 비트를 허용하는 상태 머신 기반 엔트로피 인코더입니다.これにより 허프만 코딩보다 높은 압축률을 달성할 수 있는데, 허프만 코딩은 정수 비트 증분에만 제한됩니다. 그러나 FSE는 디컴프레서가 블록의 끝에서 비트를 뒤로 읽도록 요구하여 구현 복잡성을 크게 증가시킵니다.
불변식 형식화
표준 언어에서는 최적화된 디코딩 루프에 필요한 가정들이 일반적으로 주석이나 런타임 검사로 밀려납니다. Lean에서는 이를 형식적 정리로 인코딩할 수 있습니다. FSE 테이블 구축에 대해 다음의 보편적 속성들이 LLM의 도움을 받아 형식적으로 증명되었습니다:
- Correct Table Size: 테이블은 지정된 정확도 상수와 일치합니다.
- Symbol Distribution: 심볼에 할당된 상태의 수는 그 확률을 정확히 반영합니다.
- State Validity: 어떤 상태에 대해서도 기준값과 읽은 비트를 유효한 상태 번호로 만들 수 있습니다.
- Reachability: 0이 아닌 확률을 가진 모든 심볼에 대해, 어떤 목표 상태에도 도달할 수 있는 상태는 정확히 하나입니다.
이 증명들은 전통적으로 수작업으로 몇 시간 또는 며칠이 걸렸겠지만, LLM은 약 20분 만에 생성했습니다.
시스템 프로그래밍을 위한 Lean의 기술적 장점
Lean은 전통적인 정립 증명기보다 프로그래밍에 더 적합하도록 여러 가지 기능을 제공합니다:
- Strict Evaluation: Haskell의 게으름과 달리 Lean은 엄격하여 성능과 자원 사용을 추론하기 쉽게 만듭니다.
- Imperative Sugar: Lean의 모나딕
do표기법은 for-루프, 반환 문, break 문을 지원하여 명령형 코딩 스타일을 허용합니다. - Reference Counting 최적화: Lean은 객체의 참조 횟수가 하나이면 제자리 변이를 수행할 수 있어 명령형 언어와 유사한 효율적인 배열 업데이트를 가능하게 합니다.
검증된 소프트웨어의 미래에 대한 관점
명세 공학으로의 전환
산업 논의에 따르면 프로그래머의 역할이 "명세 공학"으로 이동하고 있다고 합니다. 만약 구현이 LLM에 의해 생성된 아티팩트이고 정립 증명기에 의해 검증된다면, 소프트웨어의 유일한 인간 대면 부분은 명세 자체가 됩니다. 이로 인해 명세는 모듈식이면서 합성 가능하고 인간이 검증하기에 충분히 짧아야 합니다.
확장성 문제
일부 비평가들은 의존형 타입이 일반적인 유지보수에 확장되지 못한다고 주장합니다. 프로그램에 새로운 불변식을 추가하는 것은 종종 코드베이스 전체에 걸쳐 모든 의존형 타입을 정제하고 모든 증명을 적응시켜야 하는데, 이는 계산과 증정이 서로 얽혀 있기 때문입니다. 제안된 대안은 의존형 타입을 주로 모듈 경계에서 사용하여 불투명한 타입을 노출시키고, 내부 문제는 별도로 처리하는 것입니다.
검증된 어셈블리와 성능
AWS의 LNSym(AArch64용 시맨틱 및 시뮬레이터)과 같은 도구를 사용하여 고수준 Lean 함수와 최적화된 어셈블리 구현 간의 동등성을 증명하는 데 큰 관심이 있습니다.これにより LLMs은 기능적 버그를 도입하지 않고 어셈블리 코드를 공격적으로 최적화할 수 있는데, 이는 동등성을 형식적으로 검증할 수 있기 때문입니다.
"잘못된 것의 정확성" 위험
형식적 검증은 구현이 명세와 일치함을 증명하지만, 명세 자체가 사용자가 실제로 의도한 것임을 증명할 수는 없습니다. 커뮤니티 논의에서 언급된 바와 같이, LLM에게 제공된 명세도 반대로 되어 있다면, LLM은 완전히 뒤집혀 구현된 기능의 정확성을 성실히 증명할 수 있습니다.