기술 요약: 대규모 언어 모델을 위한 동기화 불필요 대수적 핑거프린트

1. 문제 정의

대규모 언어 모델(LLM)의 광범각한 배포는 생성된 텍스트를 귀속시키고, 책임을 보장하며, 오용을 탐지하기 위한 신뢰할 수 있는 워터마킹 방법의 시급한 필요성을 창출했다. 기존의 LLM 워터마킹 체계는 일반적으로 통계적, 어휘적, 구문적 또는 암호학적 범주에 속한다. 그러나 현재 접근 방식들의 근본적인 한계는 대부분의 방식이 **동기화 의존성(synchronization dependence)**을 가진다는 점이다. 이러한 방식들은 일반적으로 워터마크 비트를 순차적으로 또는 고정된 크기의 블록 내에 임베딩하며, 토큰의 정밀한 위치 순서에 의존한다. 결과적으로 삽입, 삭제, 패러프레이징(paraphrasing) 또는 문장 재배치와 같은 일반적인 편집 작업은 인코더와 디코더 사이의 정렬을 파괴하여 워터마크를 복구 불가능하게 만든다. 본 논문은 임의의 텍스트 편집 후에도 신뢰할 수 있는 탐지가 가능한 동기화 불필요(synchronization-free) 워터마킹 기술의 개발이 이 분야의 주요 과제임을 식별하였다.

2. 방법론

저자들은 복구 과정에서 명시적인 토큰 정렬의 필요성을 제거하는 새로운 워터마킹 프레임워크를 제안한다. 핵심 혁신은 모든 워터마크 비트가 인접한 두 토큰 쌍에 독립적으로 임베딩되는 리드-솔로몬(Reed–Solomon) 코드 기반의 대수적 핑거프린팅 체계이다.

2.1 대수적 프레임워크

• 정체성 표현: 비밀 정체성 $S$는 $n$비트 이진 벡터로 표현되며, 유한체 $\mathbb{F}_q$ (여기서 $q > 2^n$인 홀수 소수) 상의 차수가 최대 $n-1$인 다항식 $f_S(x)$로 매핑된다.
• 이진 핑거프린트: 전체 필드 값 $f_S(\alpha)$를 전송하는 대신, 본 체계는 단일 이진 관측값인 평가의 패리티(parity), 즉 $\phi_S(\alpha) = f_S(\alpha) \pmod 2$를 추출한다.
• 임베딩 메커니즘: 모든 연속된 토큰 쌍 $(t_i, t_{i+1})$에 대하여:
  1. 첫 번째 토큰 $t_i$는 고유한 평가 지점 $\alpha_i = H(K, \text{id}(t_i)) \pmod q$를 결정한다. 여기서 $H$는 암호학적 해시이고 $K$는 비밀 키이다.
  2. 워터마크 비트 $w_i = \phi_S(\alpha_i)$가 계산된다.
  3. 두 번째 토큰 $t_{i+1}$은 특정 토큰 클래스(예: "그린" 또는 "레드")에 속하도록 생성되거나 편향된다. 이 클래스는 비트 값 $w_i$에 대응한다.
• 독립성: 각 비트는 오직 로컬 토큰 쌍과 비밀 키에만 의존하므로, 한 비트의 임베딩은 이전 비트의 위치나 상태에 의존하지 않는다.

2.2 복구 및 디코딩

복구는 토큰들이 원래 순서대로 있을 것을 요구하지 않는다. 디텍터는 살아남은 토큰 쌍의 집합을 수집하고, 비밀 키를 사용하여 평가 지점 $\alpha_j$를 재계산하며, 그에 대응하는 비트 $\hat{w}_j$를 관찰한다. 목표는 모든 관찰된 쌍에 대해 $\phi_S(\alpha_j) = \hat{w}_j$를 만족하는 유일한 정체성 $S$를 찾는 것이다.

• 알고리즘: 본 논문은 정체성 크기에 따라 세 가지 복구 알고리즘을 제안한다:
  1. 전수 조사 (Exhaustive Search): 작은 $n$ ($n \lesssim 20$)의 경우.
  2. 만남의 광장 (Meet-in-the-Middle): 중간 규모의 $n$ ($20 < n \le 60$)의 경우, 복잡도를 $O(2^n)$에서 $O(2^{n/2})$로 감소시킨다.
  3. 파편화 (Fragmentation): 긴 정체성의 경우, 비밀을 독립적인 파편으로 나누어 더 작은 하위 문제들을 병렬로 복구할 수 있게 한다.

2.3 손상 모델링

저자들은 워터마킹 과정을 **이진 대칭 채널(Binary Symmetric Channel, BSC)**로 모델링한다. 이들은 삽입, 삭제, 치환 및 임베딩의 불완전성이 모두 단일 교차 확률 $p$로 추상화될 수 있다고 주장한다.

• 삽입/삭제: 단일 삭제가 이후의 모든 비트를 이동시키는 블록 기반 방식과 달리, 여기서는 삽입이나 삭제가 단순히 독립적인 관측값들을 제거하거나 추가할 뿐이다. 탐지되지 않는 편집의 확률은 약 $1/4$로 나타나며, 이는 대부분의 편집이 탐지 가능한 불일치를 유발함을 의미한다.
• 복구 확률: 성공적인 복구 확률은 살아남은 올바른 관측값의 수 $r$에 의해서만 결정된다. 만약 $r \ge n + \lambda$라면, 실패 확률은 $2^{-\lambda}$로 제한된다.

2.4 확산 모델(Diffusion Models)로의 확장

이 프레임워크는 텍스트를 자기회귀적(autoregressive)이 아닌 반복적으로 생성하는 확산 언어 모델(DLM)로 확장된다. 저자들은 노이즈 제거 과정 중에 워터마크 제약 조건을 강제하기 위해 세 가지 "커밋 알고리즘(Commit Algorithms)"을 제안한다:

1. 기본 커밋 (Basic Commit): 왼쪽 제약 조건이 충족되면 토큰을 커밋한다.
2. 정교한 커밋 (Refined Commit): 왼쪽 제약 조건에 기반하여 커밋하되, 오른쪽 제약 조건이 실패할 경우 이웃을 취소(revoke)함으로써 국소적 자기 수정을 허용한다.
3. 슬라이딩 커밋 (Sliding Commit): 커밋된 영역과 커밋되지 않은 영역 사이의 경계가 이동할 수 있도록 하며, 국소적 불일치를 해결하기 위해 과정을 랜덤 워크(random walk)로 취급한다.

3. 주요 기여

본 논문은 다음과 같이 기여를 요약한다:

• 동기화 불필요 프레임워크: 모든 워터마크 비트가 독립적으로 임베딩되어, 복구 시 토큰 정렬을 필요로 하지 않는 방법론을 제공한다.
• 리드-솔로몬 인코딩: 위치에 관계없이 충분히 큰 올바른 관측값의 집합으로부터 정체성을 재구성하는 구조를 제시한다.
• BSC 모델링: 모든 손상 원인(임베딩 오류 및 편집)을 단일 이진 대칭 채널로 모델링할 수 있음을 입증하여, 경험적 분석이 아닌 수학적이고 분석적인 강건성 평가를 가능하게 한다.
• 확률 공식: 규정된 신뢰 수준으로 성공적인 복구를 위해 필요한 최소 텍스트 길이를 예측하는 정확 및 근사 공식을 도출한다.
• 확장성: 긴 정체성을 파편으로 분할하여 동기화 불필요 특성을 유지하면서도 계산 복잡도를 줄이는 경량화된 변형 모델을 제공한다.
• 확산 모델 확장: 효율적인 토큰 커밋 알고리즘과 확률적 분석을 포함한 확산 기반 모델에 대한 프레임워크 확장을 제시한다.

4. 결과 및 분석

• 강건성: 분석 결과, 높은 토큰 손상율에서도 신뢰할 수 있는 복구를 위해 적은 중복성(redundancy)만 필요함을 보여준다. 예를 들어, 30%의 오류율($p=0.3$)을 가진 채널에서 32비트 정체성을 99% 신뢰도로 복구하려면 단 25개의 추가 토큰 쌍(총 57개 쌍)만 필요하다.
• 효율성: "만남의 광장" 알고리즘을 통해 표준 워크스테이션에서 $n \approx 60$ 비트까지의 정체성을 실용적으로 복구할 수 있다. 파편화는 임의의 길이의 정체성을 처리할 수 있게 한다.
• 확산 수렴 (Diffusion Convergence):
  • 기본 커밋 알고리즘은 $O(\ln N / \epsilon)$ 번의 반복 내에 수렴한다.
  • 슬라이딩 커밋 알고리즘은 $O(N)$ 번의 반복 내에 수렴하지만, 국소적 불일치가 고착되지 않고 결국 해결됨을 보장한다.
  • 정교한 커밋 알고리즘은 초기 커밋 속도는 빠르지만, 기본 방식에 비해 전체 시퀀스의 안정성을 늦출 수 있는 "변동(churn)"(유효한 커밋을 취소하는 현상)을 유발한다.

5. 의의 및 주장

본 논문은 자신의 주요 의의가 기존의 워터마킹 방식들을 무력화했던 근본적인 장벽인 동기화 문제를 제거하는 데 있다고 주장한다. 워터마크 비트를 순차적 위치로부터 분리함으로써, 제안된 방법은 기존 방식들을 무효화하는 편집 작업들에 대해 강건함을 유지한다.

나아가, 저자들은 평가 방법론의 전환을 주장한다. 모델별로 수행되는 광범위하고 빠르게 구식이 될 수 있는 실험적 평가 대신, 이진 대칭 채널 추상화를 사용할 것을 제안한다. 이를 통해 단일 파라미터인 유효 오류 확률 $p$를 기준으로 서로 다른 모델과 편집 전략 간의 워터마킹 체계를 원칙적이고 수학적으로 비교할 수 있다.

본 논문은 BSC가 단순화된 모델이기는 하나, 모든 편집 작업이 궁극적으로 복구된 패리티 비트에서의 독립적인 오류로 나타나기 때문에 동기화 불필요 체계에 대해 매우 유용한 근사치를 제공한다고 결론짓는다. 이 접근법은 복구 확률에 대한 명시적인 보장을 제공하며, 보다 강건한 워터마킹 시스템 설계를 단순화한다.