기술 요약: 격자 추론 트랜스포머

문제 제기

현재의 대규모 언어 모델 (LLM) 은 최종 답변에 도달하기 위해 중간 추론 토큰을 생성하는 체인 오브 씽킹 (chain-of-thought) 패러다임에 크게 의존합니다. 많은 작업에서 효과적이지만, 이 접근법은 자동 추론 시스템에서 발견되는 엄격한 논리적 타당성이 종종 부족합니다. 반면, 전통적인 자동 추론 (예: SAT 솔버) 은 이산 확산 모델과 유사한 방식으로 부분 정보 상태의 반복적 정제를 통해 작동하지만, 이러한 방법들은 신경 아키텍처와 구별되는 경우가 많습니다.

저자들은 다음과 같은 간극을 제기합니다: 자동 추론, 특히 추상 해석 (abstract interpretation) 의 기법이 신경 아키텍처에 통합되어 타당한 추론 (sound deduction) 을 수행하는 모델을 만들 수 있을까요? 목표는 어려운 논리적 문제에서 올바른 답변을 반환하거나 유보할 뿐, 결코 잘못된 솔루션을 생성하지 않는 모델을 구축하는 것이며, 이는 기존 순환 추론기나 최첨단 LLM 보다 훨씬 적은 매개변수와 학습 비용으로 달성하는 것입니다.

방법론

격자 추론 트랜스포머 (LDT)

핵심 기여는 논리적으로 타당한 추론을 근사하도록 설계된 순환 트랜스포머 아키텍처인 격자 추론 트랜스포머 (Lattice Deduction Transformer, LDT) 입니다.

1. 추상 해석 프레임워크:
모델은 추론을 정보 상태의 격자 (lattice) 를 통한 하강으로 취급합니다.

• 구체 도메인 ($C$): 모든 유효 솔루션의 멱집합 (예: 모든 유효한 스도쿠 그리드).
• 추상 도메인 ($A$): 각 셀이 생존 가능한 후보들의 집합을 보유하는 "그리드 멱집합 격자".
  • 최상 ($\top$): 정보가 없음을 나타냄 (모든 후보가 가능).
  • 최하 ($\bot$): 모순을 나타냄 (어떤 후보도 불가능).
• 추론: $\top$ 에서 더 많은 정보를 가진 상태 쪽으로 이동하는 과정. 상태가 $\bot$ 으로 수렴하면 현재 분기에 유효한 솔루션이 없음을 신호합니다.

2. 아키텍처:

• 순환 트랜스포머: 모델은 4 개의 어텐션 레이어 스택을 사용하여 순방향 통과당 16 회 내부 반복을 펼칩니다.
• 격자 인코딩: 추상 상태는 텐서로 인코딩됩니다. 그리드 문제 (스도쿠 등) 의 경우, 각 셀이 특정 후보가 여전히 "생존"하고 있다는 확신을 나타내는 이진 시그모이드를 갖는 멀티핫 인코딩입니다.
• 투영: 순방향 통과 사이에서 잠재 상태는 격자 표현으로 투영되고 다시 투영됩니다. 이는 모든 순방향 통과가 타당한 추론 단계로 작용하도록 강제합니다.
• 충돌 감지: 전용 CLS 토큰 시그모이드가 모순 ($\bot$) 을 예측하여 모델이 만족 불가능한 상태를 감지할 수 있게 합니다.

3. 학습 절차 (온-정책 풀 루프):
학습은 추론 과정을 반영하여, 모델이 테스트 시간에 마주하게 될 격자 상태의 분포와 동일한 분포를 보도록 합니다.

• 풀 루프: 다음 두 단계 사이를 오가는 확률적 검색 과정입니다:
  1. 추론: 트랜스포머가 격자 상태를 정제합니다 (후보 제거).
  2. 분기: 상태가 솔루션이나 충돌이 아닌 경우, 모델은 확률적으로 무작위 다중 후보 셀을 단일 값에 "고정"합니다 (살아있는 후보에 대한 소프트맥스에서 샘플링).
• $\alpha$ 연산자를 통한 감독: 단일 정답 솔루션에 대해 학습하는 대신, 모델은 현재 상태와 일관된 유효 솔루션 집합의 추상화에 대해 감독을 받습니다.
  • 목표 $\hat{y} = x \sqcap \alpha(\{y \in Y \mid y \text{ is consistent with } x\})$.
  • 이는 모델이 여러 유효 솔루션에서 동시에 학습할 수 있게 하여 (다중 솔루션 감독), 여러 솔루션이 존재할 때 임의의 단일 정답에 집착하는 것에 대한 패널티를 피합니다.
• 손실 함수: 다음들의 조합:
  • 후보 제거를 위한 비대칭 이진 교차 엔트로피 (BCE) (타당성을 보장하기 위해 잘못된 제거를 강력하게 패널티화).
  • 충돌 감지를 위한 대칭 BCE.
  • 단일 후보로 수렴한 셀을 위한 교차 엔트로피.

4. 추론:
추론은 병렬 풀 과정을 실행합니다. 여러 체인이 검색 공간을 동시에 탐색합니다. 체인이 격자 상태나 CLS 토큰에 의해 감지된 충돌에 부딪히면, 백트래킹하거나 재시작합니다. 시스템은 경험적으로 타당하도록 설계되었습니다: 답변을 반환하면 그것은 정확하며, 경로를 찾지 못하면 유보합니다.

주요 기여

1. 아키텍처: 모든 반복에서 잠재 상태를 추상 격자에 투영하는 순환 트랜스포머로, 순방향 통과를 타당한 추론 단계로 변환합니다.
2. 온-정책 학습: 격자 상태가 모델 자체의 순방향 통과 하에서 진화하는 학습 절차로, 학습 상태를 추론 검색 상태와 분포 내 (in-distribution) 에 유지합니다.
3. $\alpha$ 연산자: 현재 격자 상태와 일관된 유효 솔루션들을 집계하는 감독 메커니즘입니다. 이는 "온-정책이면서도 도메인 중립적이고 상태 의존적인 목표에 의해 감독되는" 체제를 만들어, 여러 유효 솔루션이 있는 문제를 자연스럽게 처리합니다.
4. 연산 트레이드오프 특성화: 학습 연산의 증가가 추론 시 필요한 순방향 통과 (검색 단계) 수를 획기적으로 단축시킨다는 경험적 증거로, 테스트 시간 검색의 부담을 학습 시간 학습으로 전환합니다.

결과

저자들은 LDT 를 최첨단 LLM(Claude Opus 4.6, DeepSeek V4-Pro, GPT-5.4) 과 기존 순환 추론기 (HRM, TRM, Sotaku) 와 비교하여 세 가지 벤치마크에서 평가했습니다.

• 스도쿠-익스트림 (Sudoku-Extreme):
  • 80 만 매개변수 LDT 가 스도쿠-익스트림 및 스노우플레이크 스도쿠에서 100% 정확도를 달성했습니다.
  • 4,000 단계 학습으로 경험적 타당성 (100% 정확 또는 유보) 에 도달했습니다.
  • 비용: 단일 B200 GPU 에서 약 15 분 동안 학습되었으며, 이는 기존 방법들의 비용의 일부입니다 (예: TRM 은 4 개의 L40S GPU 에서 36 시간 소요).
  • 최첨단 LLM: 모든 벤치마크에서 0% 점수를 기록했습니다.
• 스노우플레이크 스도쿠:
  • 모델은 고정된 커버링 그리드와 마스킹을 사용하여 아키텍처 변경 없이 가변 토폴로지 육각형 그리드 (차수 $n=4$ 에서 $8$) 로 일반화되었습니다.
  • 4 분의 학습으로 100% 정확도를 달성했습니다.
• 미로-하드 (Maze-Hard):
  • 180 만 매개변수 변형이 여러 유효한 최단 경로를 가진 30x30 미로에서 99.9% 정확도를 달성했습니다.
  • 다중 솔루션 감독 ($K=512$) 은 단일 솔루션 감독 ($K=1$) 보다 성능을 향상시켰습니다.
  • 최첨단 LLM 은 다시 0% 점수를 기록했습니다.

효율성: LDT 는 강력한 트레이드오프를 보여줍니다: 추가 학습 연산은 추론 시 필요한 순방향 통과 수를 획기적으로 줄입니다.

중요성과 주장

이 논문은 LDT 가 격자 위의 고정점 계산으로 추론을 취급함으로써 신경망과 자동 추론 사이의 간극을 성공적으로 연결했다고 주장합니다.

• 타당성: 환각을 일으킬 수 있는 표준 LLM 과 달리, LDT 는 경험적으로 타당하도록 설계되었습니다. 검증된 올바른 답변을 반환하거나 유보할 뿐, 결코 잘못된 양성을 반환하지 않습니다.
• 효율성: 이 특정 온-정책, 격자 기반 접근법으로 학습된 작은 모델 (200 만 매개변수 미만) 은 논리적 벤치마크에서 훨씬 큰 순환 추론기와 오류 없는 최첨단 LLM 보다 우수한 성능을 발휘합니다.
• 일반화: 이 접근법은 격자 구조에 대해 도메인 중립적입니다. 조합 퍼즐에 구현되었지만, 이 아키텍처는 이론적으로 추론 연산자를 허용하는 모든 추상 도메인에 적용될 수 있습니다.
• 한계: 저자들은 LDT 가 현재 명확하고 고정된 논리적 규칙을 가진 작업에 가장 적합하다고 지적합니다. 규칙 자체가 퓨샷 (few-shot) 데모에서 추론되어야 하는 ARC-AGI 와 같은 작업에서는 사전 정의된 추론 연산자가 없으면 충돌 헤드가 신뢰할 수 없게 되어 어려움을 겪습니다. 이 간극을 해소하려면 더 깊은 재귀 구조나 솔루션을 생성하는 프로그램에 대한 추상 도메인이 필요할 수 있습니다.

요약하자면, LDT 는 구조화된 논리적 문제에 대해 체인 오브 씽킹 추론의 확장 가능하고 타당하며 효율적인 대안을 제공하며, 신경 검색을 안내하기 위해 추상 해석을 활용합니다.