Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints

논문 개요

이 논문은 대형 언어 모델 (LLM) 의 생성 텍스트에 다중 비트 (multi-bit) 워터마킹을 적용할 때, 최악의 경우 오경보 (worst-case false-alarm) 제약 조건 하에서 달성 가능한 최적의 성능을 규명하고, 이를 달성하는 새로운 부호화 - 복호화 기법을 제안합니다. 기존 연구에서 주장되었던 최적성 증명에 치명적인 결함이 있음을 지적하고, 이를 해결하는 두 가지 새로운 구성 (Construction) 을 제시하여 다중 비트 생성 워터마킹 문제를 완전히 해결합니다.

1. 문제 정의 (Problem Statement)

• 배경: LLM 생성 텍스트의 급증으로 인해 가짜 뉴스 및 학술 위조 등의 문제가 발생하고 있으며, 이를 식별하기 위한 워터마킹 기술이 필수적입니다. 기존 연구는 주로 '0 비트' (AI 생성 여부만 판별) 에 집중했으나, 더 많은 정보를 인코딩하는 '다중 비트' 워터마킹이 필요합니다.
• 목표: 생성된 텍스트에 숨겨진 메시지 $m$을 인코딩하고, 검출기가 이를 정확히 복호화하도록 하는 것입니다.
• 제약 조건:
  1. 왜곡 없음 (Distortionless): 워터마킹이 적용된 텍스트의 토큰 분포는 원본 LLM 의 분포와 통계적으로 동일해야 합니다.
  2. 최악의 경우 오경보 (Worst-case False-Alarm): 텍스트가 워터마크가 없는 경우 (메시지 $m=0$), 검출기가 임의의 토큰 분포를 가진 텍스트를 잘못해서 워터마크가 있다고 판단할 확률 (오경보 확률) 이 임계값 $\alpha$를 넘지 않아야 합니다.
  3. 최소화 목표: 주어진 오경보 제약 하에서, 워터마크가 있는 텍스트를 놓치는 확률 (Miss-detection probability) 을 최소화하는 것입니다.

2. 기존 연구의 한계 및 발견 (Limitations of Prior Work)

• He et al. [11] 의 문제점: 최근 He 등 [11] 은 유한 토큰 regime 에서 miss-detection 확률의 하한을 유도하고 이를 달성한다고 주장하는 부호화 - 복호화 기법을 제시했습니다.
• 본 논문의 발견: 저자들은 He et al. 의 기법이 실제로 주장된 하한을 달성하지 못함을 증명했습니다. 그 근본 원인은 과도하게 제한적인 복호기 (Decoder) 설계에 있었습니다. 특정 키 패턴에 대한 제약이 너무 강해 최적의 확률 분포를 할당할 수 없었기 때문입니다.

3. 주요 방법론 (Methodology)

저자는 문제를 선형 계획법 (Linear Program) 으로 공식화하고, 최적성을 달성하기 위한 구조적 조건을 유도했습니다.

A. 최적 하한 (Lower Bound) 재확인

임의의 토큰 분포 $P_X$와 오경보 임계값 $\alpha$에 대해, 달성 가능한 최소 miss-detection 확률 $\beta^*$는 다음과 같습니다:
$$\beta^*[\alpha, P_X] = 1 - \sum_{x \in X} \min\left(\frac{\alpha}{T}, P_X(x)\right)$$
여기서 $T$는 인코딩 가능한 메시지 수입니다.

B. 두 가지 새로운 최적 구성 (Optimal Constructions)

이 하한을 달성하는 두 가지 새로운 인코딩 - 디코딩 기법을 제안했습니다.

1. 구현 A: 분해 접근법 (Decomposition Approach)

   • 핵심 개념: 토큰 분포 $P_X$를 세 부분으로 분해합니다: $P_X = P_X^{(1)} + P_X^{(2)} + P_X^{(3)}$.
     • $P_X^{(1)}$: $T$-hot representable (특정 벡터 합으로 표현 가능) 인 부분.
     • $P_X^{(2)}$: 꼬리 부분에 제한된 양의 성분을 가진 단계적 벡터 (step-vector) 부분.
     • $P_X^{(3)}$: 나머지 잔여 부분.
   • 동작:
     • $P_X^{(1)}$은 $T$-hot 벡터를 기반으로 키 공간에 균일하게 분배하여 행/열 합 불변성을 유지합니다.
     • $P_X^{(2)}$는 '앵커 키 (Anchored Key)' 집합을 사용하여 분배되는데, 이로 인해 행 합 불변성 (Row-sum invariance) 이 깨질 수 있습니다.
     • $P_X^{(3)}$은 $P_X^{(2)}$로 인해 발생한 행 합 불균형을 보정하는 역할을 하여 전체 시스템이 왜곡 없는 조건을 만족하도록 합니다.
   • 특징: 키 집합의 크기가 상대적으로 작습니다 ($|Z| \approx \frac{N!}{(N-T)!} + 1$).

2. 구현 B: 의사 토큰 접근법 (Pseudo-Token Approach)

   • 핵심 개념: 원래 토큰 집합 $X$에 $n$개의 '의사 토큰 (pseudo-tokens)'을 추가하여 확장된 공간에서 문제를 풉니다.
   • 동작: 확장된 분포 $P'_X$가 $T$-hot representable 이 되도록 구성한 후, 알고리즘 2 를 적용합니다. 이후 의사 토큰에 할당된 확률 질량을 원래 토큰 공간으로 다시 매핑합니다.
   • 특징: 개념적으로 매우 직관적이고 구현이 단순하지만, 필요한 키 집합의 크기가 구현 A 보다 클 수 있습니다.

4. 주요 결과 (Key Results)

• 최적성 증명: 제안된 두 가지 구성 (A 와 B) 은 모두 He et al. [11] 에서 유도된 이론적 하한을 정확히 달성함을 증명했습니다.
• 기존 기법의 무효성 증명: He et al. 의 특정 키 집합 선택과 복호기 설계가 최적 해를 찾을 수 없음을 이차 문제 (Dual problem) 를 통해 반증했습니다.
• 성능 비교:
  • 구현 A: 키 집합 크기가 작아 저장 및 관리 측면에서 유리합니다.
  • 구현 B: 키 집합이 더 클 수 있지만, 알고리즘 구조가 단순하여 개념적 이해와 구현이 용이합니다. 토큰 분포가 균일하고 $N$이 크다면 두 방법의 키 크기 차이는 미미해집니다.

5. 의의 및 결론 (Significance)

• 이론적 기여: 다중 비트 생성 워터마킹의 정보 이론적 한계를 완전히 규명했습니다. 특히, 왜곡 없는 워터마킹 하에서 오경보 제약과 탐지 오류 간의 최적 트레이드오프를 수학적으로 정립했습니다.
• 실용적 기여: 기존에 제안된 비최적 기법의 문제를 지적하고, 실제 시스템에 적용 가능한 두 가지 최적 알고리즘을 제공함으로써, LLM 워터마킹의 신뢰성과 효율성을 높이는 기초를 마련했습니다.
• 미래 전망: 이 연구는 생성형 AI 의 저작권 보호와 악용 방지를 위한 표준적인 워터마킹 프레임워크를 제시하며, 향후 더 복잡한 시나리오 (예: 시퀀스 기반 확률 고려) 로의 확장을 위한 토대가 됩니다.

요약하자면, 이 논문은 LLM 다중 비트 워터마킹의 최적 성능 한계를 증명하고, 기존 연구의 오류를 수정하여 이를 달성하는 두 가지 실용적인 알고리즘을 제시했다는 점에서 중요한 의의를 가집니다.