본 논문은 제약 만족 문제(CSP)를 위한 Transformer 기반 프레임워크인 ConsFormer를 제안합니다. 기존의 지도 학습이나 강화 학습 기반 접근 방식은 NP-Complete 문제인 CSP의 해답이나 많은 학습 비용 및 복잡한 보상 신호 설계를 필요로 하는 한계가 있습니다. ConsFormer는 이러한 문제점을 해결하기 위해, 자기 지도 학습 방식을 사용하여 Transformer를 해답 개선자로 활용합니다. 국소 탐색을 모방하여 반복적으로 해답을 구성하며, 가능한 해답을 레이블 데이터로 사용하는 대신, CSP의 이산 제약 조건에 대한 미분 가능한 근사치를 고안하여 모델 학습을 유도합니다. 모델은 단일 단계에서 무작위 할당을 개선하도록 훈련되지만, 테스트 시에는 반복적으로 배포되어 지도 학습 및 강화 학습의 병목 현상을 우회합니다. Sudoku, 그래프 컬러링, 간호사 스케줄링, MAXCUT 등의 실험을 통해 제안된 방법이 추가적인 반복을 통해 분포 외 CSP를 해결할 수 있음을 보여줍니다.
