G-RRM: 순환 추론 모델을 이용한 심볼릭 솔버 가이드

G-RRM: Guiding Symbolic Solvers with Recurrent Reasoning Models

본 연구에서는 SE-RRM(Symbol-Equivariant Recurrent Reasoning Models)에 초점을 맞추고 있으며, 이는 더 큰 문제 크기로의 일반화 능력이 향상된 RRMs의 한 형태입니다. 우리는 ``순환 추론 모델을 이용한 가이드(Guiding with Recurrent Reasoning Models, G-RRM)``라는 신경-심볼릭 접근 방식을 제안합니다. 이 방식은 SE-RRM을 제약 조건 만족 문제에 대한 심볼릭 솔버와 통합하여 사용합니다. SE-RRMs는 완전한 해결책 제안을 생성하고, Glucose 4.1 및 CaDiCaL 3.0.0과 같은 기존의 심볼릭 솔버(예: 백트래킹 또는 SAT 기반 방법)를 안내하는 신경망 솔버 역할을 합니다. 핵심적으로, 우리는 G-RRM을 사용한 신경망 가이드가 심볼릭 솔버의 탐색 효율성을 향상시키는 조건을 조사합니다. 실험 결과는 G-RRM의 효과성이 두 가지 조건에 따라 달라짐을 보여줍니다. 첫째, 잠재적인 이점을 활용할 수 있도록 문제 인스턴스가 광범위한 조합 탐색 공간을 가져야 합니다. 둘째, 솔버 아키텍처가 신경망 힌트가 완벽하지 않은 경우에도 동적으로 분기 선택을 재정의하여 복구할 수 있어야 합니다. 이러한 조건이 충족되면 가이드 기능은 평균 충돌 횟수를 0으로 만들고 상당한 실행 시간 단축을 가져옵니다. 예를 들어, SE-RRM이 91.1%의 인스턴스를 정확하게 해결하는 $9 imes9$ 스도쿠에서 백트래킹은 33.3배 빠르게 실행되고 Glucose 4.1은 1.70배 빠르게 실행됩니다(중앙값, p<0.001). 또한 Glucose 4.1은 완벽한 힌트를 제공하는 $25 imes25$ 격자의 경우에도 1.17배의 속도 향상을 유지합니다. 반대로, CaDiCaL 3.0.0은 실행 시간이 오버헤드로 인해 지배되며, 주입된 분기 힌트를 재정의하지 않고 항상 준수하기 때문에 유의미한 속도 향상을 보이지 않습니다(중앙값 1.02배, 통계적으로 유의하지 않음) 심지어 $9 imes9$에서 작은 의미 있는 평균 감속(0.90배)을 보이기도 합니다. 이러한 결과는 신경망 가이드가 실제적인 속도 향상으로 이어지는 조건을 명확하게 보여줍니다.

In this work, we focus on SE-RRMs, a symbol-equivariant instantiation of RRMs that exhibits improved extrapolation to larger problem sizes. We propose a neuro-symbolic approach, ``Guiding with Recurrent Reasoning Models'' (G-RRM), which integrates SE-RRMs with symbolic solvers for constraint satisfaction problems. SE-RRMs act as neural solvers that generate full solution proposals and guide classical symbolic solvers, such as backtracking or SAT-based methods like Glucose 4.1 and CaDiCaL 3.0.0, that produce globally correct solutions. Centrally, we investigate when neural guidance with G-RRM improves the search efficiency of symbolic solvers. % Our experiments show that the efficacy of G-RRM depends on two conditions: first, the problem instances must have an expansive combinatorial search space to expose potential gains, and second, the solver architecture must be capable of dynamically overwriting its branching choices to recover when neural hints are imperfect. When these conditions hold, guidance drives median conflict counts to zero and yields significant wall-clock speedups: on $9\times9$ Sudoku, where the SE-RRM correctly solves $91.1\%$ of instances, backtracking accelerates by $33.3\times$ and Glucose 4.1 by $1.70\times$ (median, $p<0.001$), with Glucose 4.1 retaining a $1.17\times$ speedup on perfect-hint $25\times25$ grids. In contrast, CaDiCaL 3.0.0, whose runtime is overhead-dominated and which always respects the injected branching hints rather than overwriting them, shows no significant speedup (median $1.02\times$, n.s.) and even a small significant mean slowdown ($0.90\times$) on $9\times9$. These results delineate the regimes in which neural guidance translates into practical speedups.