스도쿠(Sudoku)처럼 엄격한 이산 제약 조건 하에서 전역적인 구조적 추론을 요구하는 제약 만족 문제(Constraint Satisfaction Problem, CSP)는 인공지능 분야의 오랜 난제 중 하나입니다. 기존에는 주로 전통적인 휴리스틱(heuristic) 방법이나 딥러닝 기반 솔버가 사용되었지만, 각각 완전한 정확성 보장의 어려움과 긴 꼬리 탐색(long-tail search) 문제라는 상호 보완적인 한계를 가지고 있었습니다. 이러한 단점을 극복하기 위해, 최근 'DiBS(Diffusion-Informed Branch Selection)'라는 새로운 접근 방식이 제안되어 주목받고 있습니다.
DiBS는 심볼릭 솔버(symbolic solver)의 완전성을 유지하면서도, 확산 모델(diffusion model)을 활용해 탐색 과정 중 '가지 선택(branch selection)'을 안내하는 방식을 사용합니다. 구체적으로, 현재 부분적으로 할당된 상태와 가벼운 일관성 신호(consistency signal)를 바탕으로 후보 값들의 순위를 매겨, 다음 탐색할 가지를 효율적으로 결정합니다. 연구진은 이 방법이 작동하는 원리와 이유에 대한 심층적인 이론적 증명도 함께 제시했습니다. 특히, 악명 높은 'Royle 17-clue Sudoku' 벤치마크 실험에서 DiBS는 기존 강력한 휴리스틱 기준선 대비 탐색 노드, 백트랙(backtrack) 수, 그리고 긴 꼬리 백분위수(long-tail percentiles)를 포함한 탐색 비용을 크게 줄이는 성과를 보였습니다.
이러한 결과는 가지 선택 오류가 가장 큰 비용으로 이어지는 어려운 문제 인스턴스에서 학습된 전역적 안내(global guidance)가 매우 효과적임을 입증합니다. DiBS는 확산 모델이 단순히 이미지 생성뿐만 아니라, 복잡한 논리적 추론 및 탐색 문제 해결에도 강력한 도구가 될 수 있음을 보여주며 AI 연구의 새로운 방향을 제시합니다. 이는 향후 스케줄링, 자원 할당 등 다양한 실제 제약 만족 문제 해결에 확산 모델을 적용할 수 있는 가능성을 열어줄 것으로 기대됩니다.