arXiv:2607.02491v1 cs.AI

G-RRM: Guiding Symbolic Solvers with Recurrent Reasoning Models

Timo Bertram, Sidhant Bhavnani, Richard Freinschlag, Erich Kobler, Andreas Mayr, Günter Klambauer

제출 2026-07-02

원문 초록

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.

요약

순환 추론 모델(RRM)은 제약 만족 문제에서 높은 예측 정확도를 보이지만 전역적 정합성을 보장하지 못하는 한계가 있어, 본 연구는 심볼 등변 RRM(SE-RRM)의 해 제안을 백트래킹 및 SAT 솔버(Glucose 4.1, CaDiCaL 3.0.0)의 분기 힌트로 활용하는 뉴로-심볼릭 프레임워크 G-RRM을 제안한다. 9×9 스도쿠 실험에서 백트래킹은 33.3×, Glucose 4.1은 1.70× 속도 향상을 달성했으나, 힌트를 덮어쓰지 못하는 CaDiCaL 3.0.0에서는 유의미한 성능 향상이 나타나지 않아 신경망 가이던스의 효과가 탐색 공간의 규모와 솔버의 힌트 수정 능력에 달려 있음을 밝혔다.

제출 이력

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

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

함께 살펴볼 논문

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

arXiv:2607.21188v1cs.AI공통 태그 Combinatorial Optimization, Graph Neural Network, neuro-symbolic

머신러닝을 활용한 단일 상수 곱셈의 효율적 SAT 인코딩을 위한 우수 규칙 식별

Identifying Good Rules for Efficient SAT Encodings of Single-Constant Multiplication Using Machine Learning

단일 상수 곱셈(Single Constant Multiplication, SCM) 문제는 하드웨어 설계에서 기본적인 NP-hard 최적화 작업으로, 고정 상수를 덧셈, 뺄셈, 비트 시프트만을 사용하여 분해하는 것을 목표로 한다. 동적 프로그래밍 방법은 SCM에 대해 근최적 SAT 인코딩을 생성할 수 있지만, 큰 상수에 대해서는 인코딩 비용이 여전히 높다. 우리는 분해 과정에서 연산자 선택을 안내하는 우수 규칙을 식별함으로써 SCM SAT 인코딩을 가속화하는 신경-기호(neuro-symbolic) 프레임워크를 제안한다. 우리 접근법은 상수 분해로부터 유망한 연산자 유형을 예측하기 위해 그래프 신경망(graph neural network) 모델을 사용하고, 그 결과 신뢰도 점수를 활용하여 기호적 탐색에서 no-good 선택을 가지치기(prune)한다. 보지 못한 17–32비트 상수에 대한 실험 결과는 인코딩 시간이 1~2자릿수 감소하고, 메모리 사용량이 97% 이상 감소하며, 분기(branching)가 한 자릿수 감소함을 보여주면서, 덧셈 측면에서 근최적 인코딩 품질을 유지한다. 이 결과는 학습 기반 기호적 전략이 SCM 인코딩의 확장성과 효율성을 크게 개선할 수 있음을 보여준다. 우리의 코드와 데이터는 https://github.com/Chufeng-Jiang/SCM_MLDP 에서 공개적으로 이용 가능하다.

arXiv:2607.09737v2physics.chem-ph공통 태그 Combinatorial Optimization, Graph Neural Network

Q-Score: 분자 도킹을 위한 양자 네이티브 스코어링 함수

Q-Score: A Quantum-Native Scoring Function for Molecular Docking

분자 도킹은 소분자가 단백질에 결합하는 방식을 예측하며, 신약 개발의 핵심 병목 단계이다. 고전적인 스코어링 함수는 경험적 쌍별 접촉을 합산하는 방식으로, 결합 특이성을 결정하는 궤도 전하 이동과 같은 양자역학적 효과를 반영하지 못한다. 본 연구에서는 Q-Score를 제안한다. Q-Score는 GNN으로 예측된 궤도 전자 공여-수용 에너지를 가중 그래프로 인코딩하고, Digitized-Counterdiabatic QAOA를 통해 최대 가중치 정점 클리크 문제를 풀어 결합을 스코어링한다. 각 상호작용 앵커는 하나의 큐비트에 대응되며, 호환성 제약 조건은 에지로 표현된다. 11개의 단백질 타겟에 대해 DC-QAOA는 10큐비트에서 8개의 타겟에서 정확한 최적해를 복원한다. AI 생성 분자 1,000개에 대해 Q-Score는 Spearman rho 0.05로 고전적 스코어링과 직교하며, rho 0.90으로 궤도 품질에 의해 주도되고, 분자량 바이어스가 없으며, 무작위 대비 두 배의 비율로 강한 궤도 상호작용을 농축시킨다. DC-QAOA는 52%의 정확률과 함께 평균 근사 비율 0.94를 달성한다. IBM Eagle에서 1,000개의 회로 실행을 통해 NISQ 하드웨어상 6큐비트 문제의 해결 가능성이 확인되었다.

arXiv:2609.38806v2cs.LG공통 태그 Combinatorial Optimization, constraint satisfaction

전역 제약 조건 문제에서 블랙보드 지능이 자기회귀 방식을 능가할 수 있다

Blackboard Intelligence Can Surpass Autoregressive on Globally Constrained Problems

다음 토큰 예측(next-token prediction)은 대규모 언어 모델(LLM)의 눈부신 발전을 이끌어왔으나, 점차 늘어나는 연구 결과들은 복잡한 전역 제약 조건(global constraints)이 지배하는 문제에서 이러한 모델들이 어려움을 겪을 수 있음을 시사합니다. 본 연구에서는 이러한 영역에 주목하여, 이 한계 중 일부가 다음 토큰 예측 자체가 유도하는 추론 인터페이스에서 비롯되는지 질문을 던집니다. 우리는 인과적(causal)이고 좌에서 우로 진행되는 궤적에 얽매이지 않고 고정된 수정 가능한 캔버스 위에서 작업하며 후보 해 상태를 탐색하는 추론 시점(inference-time) 관점인 블랙보드 지능(blackboard intelligence)을 통해 이 문제를 연구합니다. 우리는 임의 순서 예측 인터페이스를 통해 부분적으로 채워진 해 상태에 대한 예측을 자연스럽게 제공하는 확산 언어 모델(diffusion language model)로 이 개념을 구현합니다. 우리의 핵심 관찰은 표준 마스크 기반 확산 목적함수에서 얻을 수 있는 단순한 모델 내부 수치인 평균 신뢰도(mean confidence)가 전역 일관성(global coherence)에 대한 유용한 프록시 역할을 하며 추론 시점의 탐색과 수정을 안내할 수 있다는 점입니다. 실험적으로 ZebraLogic, 간호사 근무 일정 배정(Nurse Rostering), 작업장 스케줄링(Job-Shop Scheduling, JSSP) 전반에 걸쳐 Blackboard는 파인튜닝된 LLaDA-8B-Instruct 체크포인트를 고정한 상태에서도 일관되게 추론 성능을 향상시키며 동일한 규모의 자기회귀(autoregressive) 베이스라인을 크게 능가하여 ZebraLogic-Hard에서 90.4%의 정확도, Nurse Rostering에서 76.4%의 정확한 실행 가능성(exact feasibility), JSSP에서 80.2%의 최적성(optimality)을 달성했습니다. 더 강력한 자기회귀 탐색 및 정제 기법으로도 ZebraLogic-Hard에서의 격차를 좁히지 못했으며, Blackboard는 훨씬 더 큰 규모와 강력한 테스트 시점 추론 능력을 갖춘 테스트 대상 프론티어 LLM들을 ZebraLogic-Hard 및 JSSP에서 능가했습니다. 우리는 코드베이스를 https://github.com/jwoosang1/blackboard-intelligence 에 오픈소스로 공개합니다.

arXiv:2609.25149v2cs.LG공통 태그 Combinatorial Optimization, Graph Neural Network

최대 독립 집합을 위한 Dual-GNN 다중 수준 조 정

Dual-GNN Multilevel Coarsening for Maximum Independent Set

최대 독립 집합(maximum independent set, MIS) 문제는 스케줄링, 자원 할당, 네트워크 분석 등에 응용되는 기본적인 NP-hard 조합 최적화(combinatorial optimization) 문제이다. 정확 솔버(exact solver)는 고품질 해 또는 최적성 증명(optimality certificate)을 제공할 수 있으나, 계산 비용은 그래프 크기에 따라 급격히 증가한다. 반면 수작업 휴리스틱(hand-crafted heuristic)은 보장을 희생하는 대신 확장성(scalability)을 개선한다. 학습 기반 방법은 그래프 인스턴스 간 구조적 패턴을 활용하는 대안을 제공하지만, 독립 집합을 직접 예측하면 대규모 그래프에서 전역 조율(global coordination)이 어려워질 수 있다. 우리는 대신 학습을 이용해 다중 수준 그래프 조 정(multilevel graph coarsening)을 안내하고, 최종 의사 결정에는 조합 탐색(combinatorial search)을 유지한다. Dual-GNN 다중 수준 조 정 프레임워크는 Partition GNN으로 후보 수축(contraction)을 점수화하고, Representative GNN으로 각 최종 클러스터에 대해 상위 k개의 지역 독립 집합 상태를 선택한다. 최대 2,000개 정점(vertex)을 갖는 Erdős–Rényi 그래프 실험에서 유리한 품질–실행 시간 트레이드오프(quality–runtime trade-off)를 보여준다. 인증된 최적해가 있는 500정점 인스턴스에서, 본 방법은 평균 독립 집합 크기 19.20을 달성하며 이는 최적값 19.30의 99.5%에 해당한다. 정확 해법의 평균 벽시계 시간(wall-clock time) 643.57초를 3.41초로 줄여 약 189배 속도 향상(speedup)을 얻는다. 1,000 및 2,000 정점의 더 큰 그래프에서는 평가된 모든 방법 중 최고의 평균 해 품질을 달성한다. 또한 가장자리 확률(edge probability) $p=0.35$인 Erdős–Rényi 그래프에서만 학습했음에도, 학습된 조 정 정책은 보지 못한 그래프 밀도와 구조적으로 다른 그래프 계열 모두에 효과적으로 일반화(generalize)된다.

arXiv:2609.28085v1cs.LG공통 태그 Combinatorial Optimization, Graph Neural Network

잡 샵 스케줄링을 위한 GNN 기반 강화학습에서의 커리큘럼 러닝

Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling

잡 샵 스케줄링 문제(job shop scheduling problem)는 까다로운 조합 최적화(combinatorial optimization) 문제이며, 최근 그래프 신경망(GNN)을 활용한 강화학습(RL) 접근법은 문제 인스턴스로부터 스케줄링 정책을 직접 학습하는 데 유망함을 보여주었다. 그러나 대규모 인스턴스에 대한 학습은 여전히 연산 비용이 많이 들고, 다양한 인스턴스 크기에 걸친 일반화는 여전히 어려운 과제로 남아 있다. 본 논문에서는 잡 샵 스케줄링 문제에서 그래프 신경망 기반 강화학습을 위한 커리큘럼 러닝(curriculum learning)을 연구하며, 세 가지 타깃 크기인 20 x 20, 25 x 25, 30 x 30에 대해 단일 크기 학습(single-size training)과 비교한다. 커리큘럼 환경에서는 정책을 먼저 더 작은 인스턴스에서 학습시킨 후 점진적으로 더 큰 타깃 크기에 적응시켜, 초기 단계에서 학습된 스케줄링 동작이 더 큰 인스턴스에서의 학습을 뒷받침하도록 한다. 모델은 모든 평가 크기에 걸친 일반화와 타깃 크기에 대한 특화(specialization)를 모두 고려하여, 최적성 갭(optimality gap)을 사용해 8 x 8부터 30 x 30까지의 미확인(unseen) 인스턴스에서 평가된다. 실험 결과에 따르면 커리큘럼 러닝은 실제 학습 소요 시간(wall-clock training time)을 일관되게 단축하며, 타깃 크기가 커질수록 그 이점이 더 커지는 것으로 나타났다. 가장 강력한 이점은 30 x 30에서 관찰되었는데, 커리큘럼 러닝은 모든 평가 크기에 걸친 평균 최적성 갭을 약 8.1%포인트 줄이고, 타깃 크기의 평균 최적성 갭을 약 8.6%포인트 줄였으며, 학습 시간을 약 50시간 절약했다.

arXiv:2607.22356v1cs.LG공통 태그 Combinatorial Optimization, Graph Neural Network

심층 강화학습을 활용한 라스트마일 픽업 통합 주문 배차 및 경로 최적화

Integrated Order Dispatching and Routing for Last-Mile Pickup via Deep Reinforcement Learning

최근 몇 년간 라스트마일 픽업 운영의 복잡성이 증가하면서 물류 플랫폼에서 빠르고 정확한 의사결정에 대한 필요성이 커졌다. 이 과제는 근본적으로 두 가지 핵심적이고 긴밀히 결합된 의사결정 과정, 즉 주문 배차와 경로 최적화에 의해 촉발된다. 이들을 개별적으로 해결하면 상호 의존성을 간과하게 되며, 완전한 end-to-end 학습은 희소 보상(sparse reward)으로 인해 대규모이고 가변적인 규모의 인스턴스에서 불안정하고 비용이 많이 든다. 이 문제를 해결하기 위해, 학습된 경로 오라클(routing oracle)과 실시간 배차 휴리스틱을 결합하는 통합 최적화 프레임워크를 제안한다. 경로 최적화 하위 문제에 대해서는 Look-Ahead Courier-Personalized 디코더를 갖춘 Dynamic-Residual Graph Attention Network 인코더를 개발한다. 배차 하위 문제에 대해서는 경로 오라클이 지도하는 국소 탐색(local search) 기반 배차 휴리스틱을 개발하며, 오라클은 실시간 확장성을 유지하면서 후보 배송 기사를 선택하기 위한 근최적 해를 제공한다. Cainiao Logistics의 실제 데이터셋을 활용한 광범위한 실험을 통해 오프라인 평가와 온라인 롤링 호라이즌(rolling-horizon) 시뮬레이션을 포함하여 접근법의 성능을 검증했다. 실험 결과, 제안 방법은 해 품질과 해결 시간 측면에서 다른 벤치마크를 능가하며, 실시간 대규모 라스트마일 픽업 문제 해결에 물류 기업을 효과적으로 지원할 수 있음을 보여준다.

토론

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