arXiv:2609.27105v1 cs.AI

LLM을 이용한 증명 가능한 완전 일반화 계획

Provably Complete Generalized Planning with LLMs

Katharina Stein, Chaahat Jain, J\"org Hoffmann, Alexander Koller

제출 2026-09-24

한국어 초록

일반화 계획(generalized planning)은 계획 도메인(planning domain)의 모든 인스턴스를 풀 수 있는 계획을 계산하는 것을 목표로 한다. 최근 연구는 LLM을 사용하여 Python 프로그램 형태의 이러한 일반화 계획을 자동으로 생성·디버깅하였고, 여러 도메인에서 테스트 데이터에 대한 완벽한 커버리지를 달성했다. 그러나 이러한 일반화 계획이 실제로 완전(complete)한지, 즉 도메인의 모든 인스턴스를 풀 수 있는지는 수동 평가로만 판별할 수 있었다. 본 논문에서는 입력으로 주어진 도메인 제약 사양에 대해 완전성을 증명하는 Lean 형식의 일반화 계획과 그 증명을 함께 자동 생성하는 방법을 제안한다. 의미 보존(semantic-preserving) PDDL-to-Lean 변환을 도입하고, LLM으로 도메인 제약을 만족하는 모든 인스턴스를 풀 수 있음을 보여주는 형식 증명과 일반화 계획을 모두 생성한다. 완전성 증명의 정확성은 Lean의 커널이 판정한다. LLM으로 GPT-5.6-Sol을 사용하여 널리 쓰이는 13개 벤치마크 도메인에서 방법을 평가한다. 12개 도메인에서는 유효한 완전성 증명과 함께 일반화 계획을 얻었다. 이는 자동 일반화 계획 완전성 증명 분야에서 최신 기술(state of the art)의 큰 진전이다.

원문 초록

Generalized planning aims to compute a plan that solves all instances of a planning domain. Recent work has used LLMs to automatically generate and debug such generalized plans in the form of Python programs and achieved perfect test data coverage for several domains. However, whether these generalized plans are actually complete, i.e. solve all instances of the domain, could only be determined by manual evaluation. Here, we present an approach for automatically generating generalized plans in Lean together with proofs of their completeness relative to a specification of the domain constraints provided as input. We introduce a semantic-preserving PDDL-to-Lean conversion, and use an LLM to generate both the generalized plan and the formal proof that it solves every instance satisfying the domain constraints. The correctness of the completeness proof is determined by Lean's kernel. We evaluate our approach on 13 commonly used benchmark domains, using GPT-5.6-Sol as the LLM. For 12 of the domains we obtain generalized plans together with valid completeness proofs. This is a major advancement of the state of the art in automatic generalized-plan completeness proofs.

제출 이력

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

  1. arXiv:2609.27105v1제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2610.10954v1cs.AI공통 태그 automated planning, generalized planning

지수적으로 더 적은 공간으로 계획을 탐색하는 방법 학습

Learning How to Search for Plans with Exponentially Less Space

계획(plan)에 대한 휴리스틱 탐색(heuristic search)은 휴리스틱이 거의 완벽하더라도 지수적으로 많은 상태를 저장할 수 있다. 우리는 대신 탐색 제어(search control)를 학습하는데, 이는 도메인별로 하나씩 작성되는 인덱시컬 정책(indexical policy)으로서, 객체를 담는 레지스터(register)와 규칙을 순서화하는 모드를 갖는 일반화된 정책(generalized policy)이다. 우리는 객체를 레지스터에 적재하고 백트래킹 지점을 표시하는 choose 규칙을 추가하는데, 이 지점에서는 하나의 후보만으로 충분하다. 그 외의 모든 규칙은 가능한 모든 결과에 대해 작동해야 하며 탐색을 필요로 하지 않는다. 우리의 주요 결과는, 무한 실행을 배제하는 구조적 종료성(structural termination)이 객체 수에 대한 다항식으로 모든 실행을 제한한다는 것이다. 그러면 깊이 우선 절차(depth-first procedure)는 상태 공간이 얼마나 크더라도 방문한 상태의 목록 없이 다항식 공간(polynomial space) 안에서 계획을 찾아낸다. 그 대가는 시간이며, 이는 실행 과정에서의 실제 선택 횟수인 선택 깊이(choice depth)에 대해서만 지수적이다. 따라서 이러한 정책이 풀 수 있는 모든 클래스는 NP에 속하며, 선택 깊이가 상수일 때는 P에 속한다. 우리는 종료성을 증명하고 학습 과제를 검증하며 선택 깊이를 작게 유지하는 반례 기반(counterexample-guided) 루프에서 언어 모델로 이러한 정책들을 학습시킨다. 학습된 정책을 사용하여, 이 절차는 IPC 2023 Learning Track과 Autoscale Agile 스위트의 1,890개 테스트 과제 중 1,709개를 풀어내며, 이는 LAMA, BFWS, Levitron보다 더 많고, 그중 대부분을 1초와 100MiB 이내에 해결한다.

arXiv:2610.13461v1cs.AI공통 태그 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:2603.25414v5cs.PL공통 태그 formal verification

구조적 결정 가능성: 진정한 무결점 시스템을 위한 설계 시점 검증

Decidable By Construction: Design-Time Verification for Truly Fearless Systems

컴파일러가 대기 상태(wait-for) 엣지를 추적하고, 멀티스레드 작업의 건전성을 증명하며, 분산 경계 계약을 보존할 때 동시성, 병렬성 및 분산 실행은 진정으로 두려움 없는(fearless) 시스템이 됩니다. 본 설계에서 저자들의 Composer 컴파일러는 C나 벤더 API를 통한 변환 없이 Clef를 네이티브 CPU, GPU, NPU 및 FPGA 코드로 직접 저수준화(lowering)하는 과정에서도 증명을 보존합니다. 본 연구의 프로그램 의미론 그래프(Program Semantic Graph)는 BAREWire의 언박싱된 경계 계약을 정당화하는 값, 관계 및 전제를 유지합니다. 또한 C 및 C++ 인터페이싱은 명시적인 마샬링 경계 역할을 하며, 증명은 실제 인자, 변환 및 반환값에 연계됩니다. 네 가지 검증 계층(tier)이 본 설계에 대한 설명을 유기적으로 연결합니다. 계층 1은 주 차원 유형(principal dimensional types)에 기반한 구조적 추론(inference)을 제공합니다. 계층 2는 노드(node) 수준에서 로컬 산술, 표현 및 계산 무결성을 생성하고 검사합니다. 계층 3은 Iris, Actris, Aneris가 지원하는 분산 증명을 포함하여 재사용 가능한 도메인 및 시스템 보조정리(lemma)를 인스턴스화합니다. 계층 1~3은 개발자의 어노테이션을 요구하지 않으며, 사용 사례 확장에 맞춰 적용 범위를 넓힐 수 있도록 인용 기반 보조정리 라이브러리 설계를 활용합니다. 계층 4는 계산 및 확률적 관계 증명을 수용하며, 프로젝트 어노테이션을 통해 필요한 관계를 식별합니다. 또한 동일한 라이브러리 방향성을 확장하여 하이퍼그래프 구조로부터 관계적 구성을 인식하도록 합니다. 형식적 합성 규칙은 산술, 소유권, 프로토콜 및 실체화 근거를 연결합니다. 본 연구에서 구현한 분산 리덕션(distributed reduction)은 동시 작업자, 도착 순서 변경 및 경계 매핑 전반에 걸쳐 명시된 단일 결과를 보존합니다. 그 확률적 확장은 명시적인 오류 허용 예산(failure budget)과 함께 작업자 및 변환 오류를 수용합니다. Urschel의 최근 연구와 결합하여, 바운드가 재사용 가능한 증명 항의 유효한 원천을 제공함을 입증합니다. 이러한 구조적 설계를 통해 다양한 하드웨어 타깃 전반에서 검증을 진정한 무결점 프로그램 및 시스템을 위한 핵심 엔지니어링 원칙으로 확립합니다.

arXiv:2610.10580v1cs.AR공통 태그 formal verification

LLM 통합 하드웨어 설계 검증에 관한 서베이

A Survey on LLM-Integrated Hardware Design Verification

대규모 언어 모델(LLM)은 명세서 해석, 검증 산출물 생성, 디버깅, 정형 추론, 도구 오케스트레이션을 자동화하기 위해 하드웨어 검증에 점차 통합되고 있습니다. 본 서베이는 SystemVerilog 어서션 생성, 자극 및 테스트벤치 생성, 버그 위치 특정 및 설계 수정, 모델 검사 및 동등성 검사, SAT/SMT 최적화, 최신 에이전트 기반 검증 워크플로 전반에 걸친 LLM 지원 하드웨어 기능 검증에 대한 체계적인 검토를 제공합니다. 본 논문은 방법론, 검증 목표, 도구 상호작용, 벤치마크, 평가 기준별로 관련 문헌을 정리하며, 프롬프팅, 검색, 구조화된 추론, 에이전트 기반 워크플로를 포함한 추론(inference) 시점 기법과 학습(training) 시점 적응을 모두 살펴봅니다. 이러한 영역 전반에서 공통적인 패턴이 나타납니다. 시뮬레이터, 정형 엔진, 커버리지 도구, 솔버가 실행 가능한 피드백과 정확성 증거를 제공하는 반면, LLM은 검증을 고려한 워크플로 내에 내장된 의미론적 추론, 탐색, 오케스트레이션 구성 요소로서 가장 효과적입니다. 그러나 어서션, 테스트, 수정 또는 증명이 완전한 설계 의도를 충실히 포착하지 못한 채 제공된 검사만을 만족할 수도 있으므로, 도구 승인만으로는 검증 정확성이 확립되지 않습니다. 따라서 명세서와 검증 증거 간의 의미론적 정렬, 결정론적 도구와의 확장 가능한 통합, 미확인 설계에 대한 일반화, 그리고 정확성, 비용, 강건성, 인적 노력에 대한 엄격한 평가를 핵심 과제로 식별합니다. 마지막으로, LLM의 유연성과 독립적으로 검증 가능한 검증 증거를 결합하는 명세 중심, 신경-기호(neuro-symbolic), 지속형 에이전트 검증 시스템을 향한 새로운 방향을 논의합니다.

토론

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