💻 computer science

MaxSAT-Based Feedback for Guiding Vision-Language Models in Sudoku

이 논문은 후보 할당을 검증하고 구조화된 피드백을 제공하기 위해 MaxSAT 오라클을 사용하여 논리적 일관성을 강제하고 솔루션 정확도를 향상시킴으로써, 스도쿠 퍼즐에 대한 시각-언어 모델의 성능을 강화하는 뉴로-심볼릭 프레임워크를 제안한다.

원저자: Pedro Orvalho, Guillem Alenyà, Felip Manyà

게시일 2026-07-15

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Pedro Orvalho, Guillem Alenyà, Felip Manyà

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신에게 사진을 보고 그 안에 무엇이 있는지 기가 막히게 맞히는 아주 똑똑한 로봇 친구가 있다고 상상해 보세요. 당신은 이 로봇에게 스도쿠 퍼즐(1부터 9까지의 숫자를 채워 넣는 9x9 격자판) 사진을 보여주고, 로봇은 숫자를 어디에 넣을지 추측하려고 노력합니다. 이 로봇은 **시각-언어 모델(Vision-Language Model, VLM)**과 같습니다. 이 로봇은 격자를 '보고' 단서들을 '읽는' 데는 뛰어나지만, 재미있는 약점이 하나 있습니다. 바로 논리적인 규칙집이 내장되어 있지 않다는 점입니다. 로봇은 언뜻 보기에 적절해 보이는 숫자를 제시할 수는 있지만, 규칙을 어길 수도 있습니다. 예를 들어 한 줄에 5를 두 번 넣는 식이죠. 이는 마치 아름다운 하늘을 그려낼 수 있는 재능 있는 화가가 물리 법칙을 잊어버려 같은 위치에 태양을 두 개 그려 넣는 것과 같습니다.

이 논문은 이를 해결하기 위해 새로운 팀워크를 소개합니다. 그들은 예술가적인 로봇과 엄격하고 논리적인 **MaxSAT 오라클(MaxSAT Oracle)**을 짝지어 줍니다. MaxSAT 오라클은 스도쿠의 공식 규칙집을 들고 있는 매우 체계적인 심판이라고 생각하면 됩니다. 심판은 그림을 그리려고 노력하는 대신, 로봇의 추측을 지켜보며 규칙에 부합하는지 확인합니다.

이 팀워크는 다음과 같이 작동합니다:

추측: 로봇은 퍼즐 이미지를 보고 숫자를 어디에 배치할지 제안합니다.
확인: 심판은 이 제안들을 가져옵니다. 심판은 스도쿠 규칙을 "강한 법칙"(반드시 따라야 하는 것)으로 취급하고, 로봇의 추측을 "부드러운 제안"(맞기를 바라지만 규칙을 어길 경우 수정할 수 있는 것)으로 취급합니다.
수정: 만약 로봇이 실수를 하면, 심판은 단순히 "틀렸어!"라고 말하는 데 그치지 않습니다. 심판은 서로 조화를 이루며 작동하는 가장 큰 추측 그룹을 찾아내어 로봇에게 이렇게 말합니다. "이것들은 유지하되, 저것들은 구체적으로 수정해." 그런 다음 심판은 퍼즐 위에 어디에서 충돌이 발생하는지 그림을 그려 설명과 함께 보여줍니다.
재시도: 로봇은 심판의 노트를 보고 실수를 바로잡아 다시 시도합니다.

연구진은 쉬운 단계부터 어려운 단계까지 다양한 스도독 퍼즐을 대상으로 이들을 테스트했습니다. 그들은 세 가지 로봇을 사용했는데, 두 가지는 오픈 소스 모델(Molmo2와 Qwen3-VL)이고, 하나는 매우 강력한 폐쇄형 모델(GPT-5.5)입니다.

그들은 무엇을 발견했을까요?
심판이 없었을 때 로봇들은 자주 막히거나 말이 안 되는 숫자를 채워 넣었습니다. 하지만 MaxSAT 심판을 추가했을 때:

로봇들이 규칙을 훨씬 더 잘 따르게 되었습니다.
훨씬 더 많은 퍼즐을 해결했습니다. 예를 들어, 전체 판을 한 번에 풀도록 요청받았을 때 GPT-5.5 로봇은 45개의 퍼즐을 풀던 것에서 73개로 늘어났습니다. 평균 완결성(얼마나 많은 칸을 맞혔는지)은 72.0%에서 80.7%로 급증했습니다.
오픈 소스 로봇들도 개선되었지만, 대형 모델만큼은 아니었습니다. Molmo2는 17개에서 28개로, Qwen3-VL은 10개에서 13개로 해결 능력이 향상되었습니다.

이 논문은 이러한 팀워크가 로봇이 거의 다 맞았지만 약간의 논리적 실수만 저질렀을 때 특히 도움이 된다고 제안합니다. 심판은 그 실수들을 정리하여 완벽한 해답을 얻도록 도와줍니다.

이 논문이 말하는 '이것이 아닌 것'은 무엇일까요?
저자들은 매우 명확하게 밝히고 있습니다. 그들은 로봇을 심판으로 대체하려는 것이 아닙니다. 심판이 퍼즐을 스스로 풀 수 있다고 해서(몇 초면 가능합니다) 심판이 직접 풀게 하려는 것이 아닙니다. 목표는 심판의 속도를 이기는 것이 아니라, 심판이 로봇을 더 신뢰할 수 있게 가르칠 수 있는지 보는 것입니다. 또한 그들은 어려운 퍼즐(Difficulty 1)이 여전히 쉬운 퍼즐보다 까다로웠지만, 심판이 이전보다 로봇이 이를 훨씬 더 잘 다룰 수 있도록 도왔다는 점을 언급했습니다.

요약하자면, 시각적 AI에게 검토를 담당할 논리적인 "동료"를 주는 것이 퍼즐 해결 능력을 훨씬 더 향적으로 만든다는 것을 이 논문은 보여줍니다. 이는 창의적인 추측가와 엄격한 규칙 검사자를 결합하는 것이 각각의 모델이 혼자일 때보다 더 똑똑한 시스템을 만든다는 것을 증명하며, 팀워크의 승리를 보여줍니다.

기술 요약: 스도쿠 내 시각-언어 모델 가이드를 위한 MaxSAT 기반 피드백

문제 정의
시각-언어 모델(VLM)은 스도쿠와 같은 그리드 기반 퍼즐을 포함하여 구조화된 시각적 추론 작업에서 유망한 능력을 입증해 왔다. 그러나 강력한 지각 능력에도 불구하고, VLM은 논리적 일관성을 강제하는 명시적인 메커니（mechanism）가 부족하다. 이들은 원칙적인 제약 추론보다는 패턴 인식에 의존하는 경우가 많으며, 이로 인해 구조적 제약(예: 행 또는 열에서의 숫자 중복)을 위반하거나 잘못된 솔루션을 수정하려는 시도 시 불안정한 동작을 보이는 경우가 빈번하다. 제약 프로그래밍(CP) 및 만족 가능성(SAT) 방법론은 형식적인 건전성(soundness)을 보장하지만, 현대적인 VLM이 가진 지각적 유연성과 제안 생성 능력은 결여되어 있다. 본 논문은 형식적인 제약 최적화가 VLM이 시각적 논리 퍼즐을 더 신뢰성 있게 해결하도록 가이드할 수 있는지에 대한 질문을 다룬다.

방법론
저자들은 VLM이 제안 생성기(proposal generator) 역할을 수행하고, MaxSAT 오라클이 일관성 검증기 및 정제 엔진 역할을 수행하는 하이브리드 신경-기호(neuro-symbolic) 프레임워크를 제안한다. 이 접근 방식은 다음과 같은 반복적인 상호작용 루프를 통해 작동한다:

정식화(Formulation): 스도쿠 문제를 부분 MaxSAT 인스턴스로 인코딩한다.
- 강한 절(Hard Clauses, $\Phi_h$ ): 근본적인 스도쿠 제약 조건을 인코딩한다 (각 셀에는 정확히 하나의 숫자가 포함되어야 함; 모든 행, 열, 서브그리드에 각 숫자가 정확히 한 번씩 나타나야 함). 이는 타협 불가능한 조건이다.
- 약한 절(Soft Clauses, $\Phi_s$ ): VLM이 제안한 후보 배치들을 단위 절(unit clauses)로 인코딩한다.
상호작용 루프:
- VLM은 퍼즐 이미지를 바탕으로 후보 할당(셀에 숫자를 배치하는 것)을 생성한다.
- 이러한 할당값들은 MaxSAT 솔버(구체적으로 PySAT 툴킷의 RC2 솔버)로 전달된다.
- 솔버는 모든 강한 절을 만족하면서 동시에 만족되는 약한 절의 수를 최대화하는(즉, 제약을 위반하지 않으면서 VLM의 제안을 최대한 많이 유지하는) 할당을 계산한다.
- 피드백 생성: 만약 VLM의 제안이 일관되지 않을 경우, MaxSAT 솔버는 가장 크고 상호 일관된 할당 집합을 식별한다. 거부된 할당들(소프트 절 세트에 포함되어 있으나 최적의 솔루션에는 포함되지 않은 것들)은 불일치에 대한 텍스트 설명과 퍼즐 이미지 상의 충돌하는 셀을 강조하는 시각적 주석을 포함한 구조화된 피드백으로 변환된다.
- VLM은 이 피드백을 사용하여 정제된 제안을 생성한다.
프로토콜: 프레임워크는 두 가지 상호작용 모드를 평가한다:
- 반복적 단일 배치(Iterative Single-Placement): VLM이 한 번에 하나의 움직임을 제안한다. MaxSAT는 이를 검증하며, 일관되면 수용하고 그렇지 않으면 피드백과 함께 거부한다.
- 전체 보드 정제(Full-Board Refinement): VLM이 전체 보드 상태를 제안한다. MaxSAT는 전체 보드의 가장 큰 일관된 부분 집합을 식별하며, 충돌하는 셀만을 거부하고 전역적 정제를 위한 피드백을 반환한다.

주요 기여

신경-기호 프레임워크: VLM이 생성한 스도쿠 솔루션을 MaxSAT 오라클을 사용하여 검증하고 정제하는 새로운 아키텍처를 제시하며, 지각을 담당하는 신경 구성 요소와 논리적 일관성을 강제하는 기호 구성 요소 간의 명확한 역할 분담을 확립한다.
부분 MaxSAT 통합: 부분 MaxSAT를 VLM 해결 루프에 통합하여, 모델이 생성한 배치를 소프트 제약으로 취급한다. 이를 통해 시스템은 전체 출력을 폐기하는 대신, 제안의 가장 크고 상호 일관된 부분 집합을 식별하고 수리할 수 있다.
실증적 평가: 여러 오픈 소스(Molmo2, Qwen3-VL) 및 폐쇄형 접근(GPT-5.5) VLM을 대상으로 스도쿠 벤치마크 데이터셋에서 종합적인 평가를 수행하여, 제약 가이드 피드백의 효능을 입증하였다.

결과
실험은 200개의 스도쿠 인스턴스(난이도 0과 1 각각 100개씩)에 대해 수행되었다. 결과는 MaxSAT 기반 피드백이 유효성 전용(validity-only) 피드백에 비해 논리적 일관성과 해결률을 유의미하게 향고함을 보여준다:

전체 보드 정제: 이 모드가 가장 강력한 이득을 보였다. GPT-5.5의 경우, 해결률이 유효성 전용 피드백의 22.5%에서 MaxSAT 피드백 적용 시 36.5%로 증가했다. 최종 보드의 평균 완결성(AC)은 72.0%에서 80.7%로 상승했다. 특히 어려운 퍼즐(난이도 1)의 경우, 해결된 인스턴스의 수가 두 배 이상 증가했으며(10개에서 21개로), AC는 62.2%에서 76.7%로 개선되었다.
반복적 해결: MaxSAT 피드백은 단계별 해결 과정에서도 개선 효과를 보였으며, GPT-5.5의 해결된 인스턴스 수를 두 배로 늘렸고(21개에서 44개로), AC를 44.8%에서 52.2%로 높였다.
모델 편차: 모든 모델이 혜택을 받았으나, 독점 모델인 GPT-5.5가 가장 상당한 개선을 보였다. 이는 초기 신경 제안이 이미 전역적 일관성에 근접해 있을 때 기호적 정제가 가장 효과적임을 시사한다. 오픈 소스 모델들은 보다 완만한 이득을 보였으나 여전히 향상된 논리적 일관성을 입증했다.

의의 및 주장
본 논문은 VLM의 해결 루프에 기호적 최적화를 통합하는 것이 신경 모델을 대체하지 않으면서도 VLM의 추론 신뢰성을 높인다고 주장한다. 저자들은 자신들의 목표가 전문적인 기호 솔버(수 초 내에 데이터셋을 해결하는)를 능가하는 것이 아니라, 일반 목적의 VLM이 일관된 솔루션으로 나아가도록 기호적 기법이 가이드할 수 있는지를 연구하는 것임을 강조한다.

연구 결과는 기호적 정제가 "부분적으로는 불일치하지만 전역적으로는 일관된" 신경 예측에 대해 강력한 교정 메커니즘으로 작용함을 시사한다. MaxSAT 오라클에 논리적 일관성 검사를 위임함으로써, 시스템은 수용된 모든 배치가 형식적으로 검증되었음을 보장한다. 본 연구는 통계적 AI와 기호적 AI의 시너지를 발전시키며, 신경적 지각과 기호적 최적화의 상호 보완적인 강점을 조명한다. 저자들은 기호적 정제가 VLM의 모든 한계를 해결하는 완전한 처방은 아니지만, 특히 전체 보드 시나리오에서 논리적 오류를 완화하고 솔루션 품질을 크게 향상시킨다는 점을 언급하며 겸허한 태도를 유지하고 있다.

유사한 논문