G-RRM: 순환 추론 모델(Recurrent Reasoning Models)을 이용한 심볼릭 솔버(Symbolic Solvers) 가이드
요약
순환 추론 모델(RRM)을 심볼릭 솔버와 통합하여 제약 충족 문제를 해결하는 G-RRM 프레임워크를 제안합니다. 신경망이 생성한 힌트를 심볼릭 솔버가 동적으로 활용할 때 탐색 효율성이 극대화됨을 입증했습니다.
핵심 포인트
- SE-RRMs를 활용한 뉴로-심볼릭 접근 방식 제안
- 확장 가능한 조합 탐색 공간에서 신경망 가이드의 효능 확인
- 스도쿠 문제에서 Glucose 4.1 솔버의 최대 1.7배 가속 달성
- 솔버가 신경망 힌트를 동적으로 덮어쓸 수 있는 구조의 중요성 강조
본 연구에서는 더 큰 문제 규모에 대해 향상된 외삽(extrapolation) 성능을 보이는 RRM의 심볼릭 등변(symbol-equivariant) 인스턴스화인 SE-RRMs에 집중합니다. 우리는 제약 충족 문제(constraint satisfaction problems)를 위해 SE-RRMs를 심볼릭 솔버(symbolic solvers)와 통합하는 뉴로-심볼릭(neuro-symbolic) 접근 방식인 "순환 추론 모델을 이용한 가이드(Guiding with Recurrent Reasoning Models)"(G-RRM)를 제안합니다. SE-RRMs는 전체 솔루션 제안을 생성하는 신경망 솔버(neural solvers) 역할을 하며, 전역적으로 올바른 솔루션을 생성하는 백트래킹(backtracking) 또는 Glucose 4.1 및 CaDiCaL 3.0.0과 같은 SAT 기반 방식과 같은 전통적인 심볼릭 솔버를 가이드합니다. 핵심적으로, 우리는 G-RRM을 통한 신경망 가이드가 언제 심볼릭 솔버의 탐색 효율성을 향상시키는지 조사합니다. 우리의 실험은 G-RRM의 효능이 두 가지 조건에 달려 있음을 보여줍니다: 첫째, 잠재적 이득을 드러내기 위해 문제 인스턴스가 확장적인 조합 탐색 공간(combinatorial search space)을 가져야 하며, 둘째, 솔버 아키텍처가 신경망 힌트가 불완전할 때 복구할 수 있도록 분기 선택(branching choices)을 동적으로 덮어쓸 수 있어야 합니다. 이러한 조건이 충족될 때, 가이드는 중앙값 충돌 횟수(median conflict counts)를 0으로 유도하며 상당한 실제 실행 시간(wall-clock) 가속을 가져옵니다: SE-RRM이 인스턴스의 $91.1%$를 올바르게 해결하는 $9\times9$ 스도쿠(Sudoku)에서, 백트래킹은 $33.3\times$, Glucose 4.1은 $1.70\times$ 가속되었으며(중앙값, $p<0.001$), Glucose 4.1은 완벽한 힌트가 제공되는 $25\times25$ 그리드에서도 $1.17\times$의 가속도를 유지했습니다. 반면, 실행 시간이 오버헤드에 의해 지배되고 주입된 분기 힌트를 덮어쓰기보다 항상 준수하는 CaDiCaL 3.0.0은 유의미한 가속을 보이지 않았으며(중앙값 $1.02\times$, 유의미하지 않음), $9\times9$에서 심지어 약간의 유의미한 평균 속도 저하($0.90\times$)를 보였습니다. 이러한 결과는 신경망 가이드가 실질적인 가속으로 이어지는 영역을 정의합니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.AI의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기