arXiv:2606.06518v1 cs.AI

DiBS: 확산 정보 기반 분기 선택

DiBS: Diffusion-Informed Branch Selection

Bo Liu, Yuan Xie, Yuan Gao, Xiaolong Luo, Peng Ye, Tao Chen, Fujun Han

제출 2026-06-02

한국어 초록

스도쿠는 엄격한 이산 제약 하에서 전역적 구조 추론이 필요한 대표적인 제약 만족 문제이다. 기존 스도쿠 해법 연구는 주로 두 가지 지배적 접근, 즉 전통적 휴리스틱과 심층 학습 솔버에 초점을 맞춰 왔다. 그러나 이들은 두 가지 상보적 한계를 지닌다. 학습 기반 솔버는 엄격한 정확성 보장이 부족하고, 완전한 기호적 솔버는 여전히 롱테일 검색에 취약하다. 이러한 단점을 해결하기 위해, 우리는 분기 선택 검색 과정을 위해 DiBS라고 명명한 새로운 확산 모델 가이드 접근법을 제안한다. 구체적으로 DiBS는 기호적 솔버의 완전성을 유지하면서 확산 모델을 분기 순서 가이드로 사용한다. 핵심 방법은 현재 부분 할당과 경량 일관성 신호 하에서 후보 값들을 순위화하는 것이다. 또한 우리는 그것이 어떻게 작동하고 왜 작동하는지 밝히기 위해 심층 이론적 증명을 제공한다. 도전적인 Royle 17-clue Sudoku 벤치마크에 대한 실험에서 DiBS는 강력한 휴리스틱 기준선 대비 검색 비용, 특히 노드 수, 백트랙 횟수, 롱테일 백분위수에서 상당히 감소시킴을 보여준다. 또한 이러한 결과는 학습된 전역 가이드가 분기 순서 오류의 비용이 가장 큰 어려운 인스턴스에서 효과적임을 확인한다. 모든 코드는 https://github.com/shanxierdan/DiBS 에서 이용 가능하다.

원문 초록

Sudoku is a representative constraint satisfaction problem that requires global structural reasoning under strict discrete constraints. The existing works of solving Sudoku mainly focus on two dominant approaches, i.e., traditional heuristic and deep learning solver. However, they suffer from two complementary limitations: learning-based solvers lack hard correctness guarantees, while complete symbolic solvers are still prone to long-tail search. To address these shortcomings, we propose a novel diffusion model-guided approach, termed as DiBS, for the branch selection search process. Specifically, DiBS keeps the symbolic solver complete and uses the diffusion model as a branch-ordering guide. The core method is ranking candidate values under the current partial assignment and lightweight consistency signal. Furthermore, we provide an in-depth theoretical proof to reveal how it works and why it works. Experiments on the challenging Royle 17-clue Sudoku benchmark show that our DiBS substantially reduces search cost relative to strong heuristic baselines, especially in nodes, backtracks, and long-tail percentiles. Besides, these results confirm that learned global guidance is effective on hard instances where branch-order mistakes are most expensive. All codes are available at https://github.com/shanxierdan/DiBS.

제출 이력

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

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

함께 살펴볼 논문

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

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 에 오픈소스로 공개합니다.

토론

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