【AI의 돌파구】 단 80만 파라미터로 스도쿠를 100% 푸는 「Lattice Deduction Transformer (LDT)」가 놀랍다

안녕하세요! AI나 데이터 사이언스를 공부하는 여러분, 매일의 공부에 노고가 많으십니다.

여러분은 "ChatGPT와 같은 거대한 AI (Frontier Model)라면, 스도쿠나 미로 찾기 정도는 식은 죽 먹기 아니겠어?"라고 생각하고 계시지 않나요?

사실 기존의 AI (Transformer)는 이러한 "단계별로 논리적으로 풀어야 하는 문제 (추론 태스크, Reasoning Task)"에 매우 취약했습니다. 아무리 거대해져도 정답률이 0%에 가깝거나, 퍼즐 전용으로 만든 500만 파라미터의 AI조차 90% 정도에서 한계에 부딪히곤 했습니다.

그러던 중, 단 80만(800K) 파라미터라는 초미니멀한 사이즈임에도 불구하고, 스도쿠나 미로를 "거의 100%"의 정확도로 풀어내는 기법이 등장했습니다.

그것이 바로 이번에 소개할 **『Lattice Deduction Transformer (LDT)』**입니다!

AI의 구조와 학습의 상식을 뒤엎는 이 기법에 대해, 대학교 1학년 수준에 맞춰 이해하기 쉽게 풀어서 설명해 드리겠습니다.

먼저, 이 연구가 왜 이렇게 큰 화제가 되고 있는지 숫자로 살펴보겠습니다.

모델 타입	사이즈 (파라미터 수)	스도쿠 및 미로 정답률
초거대 AI (Frontier Model)	수천억~조 단위 규모	거의 0%
기존 퍼즐 전용 AI	500만 (5M)	약 90%
Lattice Deduction Transformer (LDT)	단 80만 (800K)	거의 100%

"크면 똑똑하다"라는 기존 AI의 상식을 압도적인 효율성으로 뒤집은 것이 바로 LDT입니다.

LDT가 이토록 똑똑한 이유는 AI에게 시키는 **"문제 풀이 방식 (설정)"**을 고안했기 때문입니다.
기존의 AI는 "빈칸에 들어갈 숫자를 한 번에 맞춰라!"라는 명령을 받았지만, LDT는 "후보를 조금씩 좁혀 나가는" 접근 방식을 취합니다.

여기서 사용되는 것이 수리 과학의 개념인 **"라티스 (Lattice: 격자/체)"**입니다.

스도쿠를 예로 들어 생각해 봅시다.

아직 아무것도 모르는 칸은 1부터 9까지의 모든 숫자가 들어갈 가능성이 있습니다. 이것이 라티스의 **"최상위 (모든 후보가 남아 있는 상태)"**입니다.

초기 상태: {1, 2, 3, 4, 5, 6, 7, 8, 9}

(최상위) -
1단계 전진: "이 세로줄에 3이 있으니까, 3은 지울 수 있겠네" $\rightarrow$ {1, 2, 4, 5, 6, 7, 8, 9}

더 전진: "가로줄을 보니 더 좁힐 수 있겠어" $\rightarrow$ {1, 3, 5}

이처럼 후보 집합을 깎아내어 더 구체적인 상태로 "아래로, 아래로 이동하는 조작"을 모델에게 학습시킨 것입니다. LDT는 현재의 후보 집합을 입력으로 받아, **"다음에 어떤 후보를 지워도 되는지"**를 예측합니다.

LDT는 단순히 무턱대고 후보를 지우기만 하는 것이 아닙니다. 인간이 스도쿠를 풀 때처럼, **"만약 여기에 5를 넣는다면 어떻게 될까?"라는 가설 (탐색, Search)**을 세웁니다.

만약 진행한 결과 모순 (예: 같은 열에 같은 숫자가 2개 나와버림!)이 발생할 경우, 해당 경로를 버리고 이전 상태로 돌아갑니다. 이는 프로그래밍 기초에서 배우는 **"깊이 우선 탐색 (DFS)"**나 **"백트래킹 (Backtracking)"**과 유사한 움직임입니다.

확률적 백트래킹 (Probabilistic Backtracking): 하나의 경로를 순차적으로 시도하는 것이 아니라, 여러 가능성 (탐색 가지)을 동시에 병렬로 실행하며, 잘못된 경로는 확률적으로 버려 나갑니다. -
재귀적 트랜스포머 (Recurrent Transformer): LDT의 내부 구조는 1회의 처리 (Forward pass) 과정 안에서 내부적으로 16번이나 루프 (반복)하는 구조로 되어 있습니다. 이 루프 안에서 "후보 삭제"와 "모순 검출"을 수없이 반복함으로써 압도적인 사고의 깊이를 실현합니다.

일반적인 AI는 마지막까지 풀게 한 뒤 "정답!" 혹은 "오답!"이라는 결과만을 피드백받는 경우가 많습니다. 하지만 이 방식으로는 중간의 어느 지점에서 틀렸는지 알 수 없습니다.

LDT의 학습 (On-policy 학습)에서는 탐색의 모든 중간 단계에 대해 "이 상태라면 어떤 후보를 지우는 것이 옳은가"라는 정답 (교사 신호, Teacher Signal)을 직접 제공합니다.

이는 "프로세스 (절차) 보상"에 가까운 개념으로, AI가 길을 잃지 않고 "올바른 삭제 방법"을 최단 경로로 배울 수 있는 이유입니다.

LDT는 현시점에서는 "스도쿠나 미로"를 풀기 위한 전용 모델이며, 이대로 ChatGPT처럼 무엇이든 대화할 수 있는 것은 아닙니다. 하지만 이 연구가 보여준 **"사고 방식의 응용성"**은 매우 광범위합니다.

• 구조화된 데이터의 퍼즐에 강함:

프로그램 코드 작성이나 구조화된 데이터를 다루는 태스크 등, '해의 공간(solution space)'이 명확히 정해져 있는 문제에는 이 '격자(lattice)를 통해 깎아 나가는' 접근 방식을 그대로 응용할 수 있을 가능성이 있습니다.

'반복해서 생각하기(Iteration)' 트렌드의 도래:

최근 AI의 트렌드로서, 데이터를 한 번 통과시키고 끝내는 것이 아니라 모델 내부에서 '여러 번 루프를 돌려 추론을 심화하는 (Recurrent Transformer)' 수법이 일반화되고 있습니다.

'모델을 크게 만들면 된다'는 시대에서, **'문제의 해결 방식(구조)을 고안하면 작은 AI라도 천재가 될 수 있다'**는 시대로. AI 연구의 정수가 담긴 매우 설레는 논문이네요!

여러분도 앞으로 프로그래밍 수업에서 '탐색 알고리즘 (search algorithm)'이나 '자료 구조 (data structure)'를 배울 때는, 꼭 이 LDT의 영리한 메커니즘을 떠올려 보세요!