Can we Watermark Low-Entropy LLM Outputs?

1. 문제 정의 (Problem Statement)

• 배경: LLM 에 의해 생성된 콘텐츠와 인간이 생성한 콘텐츠를 구분하기 위해 워터마킹 기술이 활발히 연구되고 있습니다. 이상적인 워터마킹은 (1) 검출 불가능성 (Undetectability): 원본 LLM 출력 분포를 변경하지 않아야 하며, (2) 강건성 (Robustness): 공격자가 토큰을 치환 (substitution), 삭제 (deletion), 삽입 (insertion) 하여 워터마크를 제거하려 해도 검출되어야 합니다.
• 기존 연구의 한계: Christ et al. [CG24], Golowich et al. [GM24] 등의 최근 연구는 강력한 강건성을 제공하지만, 높은 엔트로피를 가정합니다.
  • 구체적으로, 출력의 일정 부분 토큰들이 알파벳 크기 $|T|$에 비례하는 엔트로피 ($O(\log |T|)$) 를 가져야 합니다.
  • 자연어는 특정 문맥에서 매우 예측 가능하여 (예: "Hello" 다음에 "World"가 올 확률이 높음) 많은 토큰이 낮은 엔트로피를 가집니다. 이러한 저엔트로피 영역에서는 기존 워터마킹 기법이 실패하거나, 이진화 (binary encoding) 과정에서 엔트로피 요구 사항이 더 커지는 문제가 발생합니다.
• 핵심 질문: 토큰 알파벳 크기에 의존하지 않고, 토큰당 엔트로피가 상수 (예: 1 비트) 만으로도 검출 불가능하고 강건한 워터마킹이 가능한가?

2. 방법론 (Methodology)

저자들은 **이진 의사난수 코드 (Binary Pseudorandom Code, PRC)**를 기반으로 하되, 대규모 토큰 알파벳을 가진 LLM 출력에 적용할 수 있는 새로운 프레임워크를 제안합니다.

2.1 핵심 아이디어: 해싱 기반 임베딩

기존의 [CG24] 방식은 이진 토큰에 직접 PRC 코드를 임베딩하거나, 토큰을 이진 비트열로 변환하여 임베딩했습니다. 그러나 토큰을 이진화하면 엔트로피 요구량이 증가하고, 토큰 수준의 공격 (예: 동의어 치환) 을 이진 비트 치환으로 매핑하기 어렵습니다.

저자들의 접근법은 다음과 같습니다:

1. 해싱 (Hashing): LLM 이 생성한 각 토큰 $t$를 무작위 해시 함수 $h: T \to \{0, 1\}$를 통해 1 비트로 매핑합니다.
2. 임베딩 전략:
   • LLM 의 다음 토큰 분포 $D$에서 두 개의 독립적인 샘플 $t_0, t_1$을 추출합니다.
   • 성공 (Success): $h(t_0) \neq h(t_1)$인 경우, PRC 의 해당 비트 $c_i$와 일치하는 해시 값을 가진 토큰 ($t_{c_i}$) 을 선택하여 출력합니다. 이 경우 토큰 분포를 왜곡하지 않으면서 PRC 비트를 정확히 임베딩합니다.
   • 실패 (Failure): $h(t_0) = h(t_1)$인 경우, 임의의 토큰을 선택합니다. 이 경우 PRC 비트가 50% 확률로 잘못 임베딩될 수 있지만, 엔트로피가 충분히 높은 토큰의 경우 이 실패 확률이 낮게 유지됩니다.
3. 블록 단위 해시 재사용: 삽입/삭제 공격에 대응하기 위해, 전체 출력에 하나의 해시 함수를 쓰는 것이 아니라, PRC 코드워드 하나를 임베딩하는 블록 단위로 해시 함수를 재사용합니다. 이를 통해 삭제된 토큰이 있더라도 해당 블록의 해시 함수를 사용하여 복호화가 가능합니다.

2.2 엔트로피 요구 사항

이 방식은 토큰의 엔트로피가 1 비트 이상만 있으면 됩니다. 즉, 토큰 알파벳 크기 $|T|$에 무관하게, 토큰이 2 개 이상의 가능한 값을 가지며 그 확률이 균등하지 않더라도 (엔트로피 $\ge 1$) 워터마킹이 가능합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

저자들은 다양한 공격 모델에 대한 강건성을 보장하는 여러 정리를 증명했습니다.

3.1 무작위 치환 공격에 대한 강건성 (Theorem 1 & Corollary 1)

• 가정: 하위 지수적 LPN (Learning Parity with Noise) 문제의 난이도 가정.
• 결과: LLM 출력의 일정 부분 ($\delta$) 이 최소 엔트로피 (1 비트) 를 가진다면, 무작위 치환 (random substitutions) 공격 (최대 $1/2 - \epsilon$ 비율) 에 대해 강건한 워터마킹이 가능합니다.
• 의의: 기존 [CG24] 의 이진 모델에서 저자들은 치환 공격을 이진 대칭 채널로 모델링했지만, 저자들은 대규모 알파벳에서의 치환 (예: 동의어 교체) 을 더 일반화된 방식으로 정의하고 이를 해결했습니다.

3.2 무작위 치환 및 삭제 공격에 대한 강건성 (Theorem 2 & Corollary 2)

• 조건: "자연스러운 프롬프트 (Natural Prompt)" 또는 "일관된 오차 분포" 가정을 추가합니다.
  • 즉, 워터마킹 과정과 무작위 치환/삭제가 결합된 오차가 이진 대칭 채널 (Binary Symmetric Channel) 로 모델링될 수 있다고 가정합니다. (기존 [CG24] 의 "sufficiently variable" 가정의 일반화).
• 결과: 위 가정이 성립할 때, 무작위 치환 및 무작위 삭제 (random deletions) 공격에 대해 강건합니다.
• 한계: "자연스러운 프롬프트" 가정이 성립하지 않는 극단적인 경우 (예: 이모지 공격) 에는 약점이 있을 수 있습니다.

3.3 헤uristic 가정 없이 삭제/편집 공격에 대한 강건성 (Theorem 3, 4 & Corollary 3)

• 접근: PRC 자체의 강건성을 강화하여 헤uristic 가정을 제거합니다.
• PRC 요구사항: [CGG+25] 의 "Permuted Codes" 가정을 기반으로 한 PRC 를 사용합니다. 이 PRC 는 적대적 치환 (adversarial substitutions) 과 무작위 삭제에 대해 강건합니다.
• 결과: 추가적인 헤uristic 가정 없이도, 최소 엔트로피 조건을 만족하는 출력에 대해 무작위 치환 및 삭제에 강건한 워터마킹이 가능합니다.
• 주의점: 적대적 편집 (Insertion/Deletion) 에 대한 강건성을 얻기 위해서는 전체 출력의 상당 부분이 엔트로피를 가져야 하며, [CGG+25] 의 파라미터화로 인해 허용 가능한 편집 비율 ($\epsilon'$) 이 매우 작습니다.

4. 기술적 요약표 (Figure 1 비교)

특성	기존 연구 ([CG24], [GM24])	본 논문 (Corollary 1, 2, 3)
엔트로피 요구사항	$O(\log |T|)$ (알파벳 크기에 비례)	$O(1)$ (상수, 알파벳 크기 무관)
강건성 (치환)	이진 치환 또는 대규모 알파벳 치환	무작위 치환 (대규모 알파벳)
강건성 (삭제)	제한적 또는 추가 가정 필요	무작위 삭제 (가정 필요) / 적대적 삭제 (PRC 의존)
토큰 구조 보존	이진 변환 시 토큰 구조 손실	토큰 구조 보존 (해싱 기반)
가정	LPN 또는 큰 알파벳 PRC	LPN 또는 Permuted Codes

5. 의의 및 결론 (Significance)

1. 실용성 증대: 자연어는 많은 토큰이 낮은 엔트로피를 가지므로, 기존 고엔트로피 가정을 가진 워터마킹은 실제 LLM 에 적용하기 어렵습니다. 본 논문은 저엔트로피 환경에서도 워터마킹이 가능함을 보여줌으로써 실제 적용 가능성을 크게 높였습니다.
2. 토큰 수준의 공격 방어: 토큰을 이진 비트열로 변환하는 방식은 토큰 단위 공격 (예: 단어 교체, 삭제) 을 비트 단위 공격으로 잘못 모델링할 수 있습니다. 본 논문은 토큰 단위로 워터마킹을 수행하여 더 현실적인 공격 모델 (예: 동의어 치환, 문장 다듬기) 에 대한 강건성을 제공합니다.
3. 이론적 한계 극복: 알파벳 크기에 의존하지 않는 엔트로피 요구 사항을 달성함으로써, 암호학적 난이도 가정 (LPN 등) 하에서 LLM 워터마킹의 이론적 한계를 확장했습니다.

결론적으로, 이 논문은 LLM 의 저엔트로피 출력을 대상으로 하더라도 검출 불가능하고 다양한 편집 공격에 강건한 워터마킹 체계를 구축할 수 있음을 증명하며, AI 생성 콘텐츠의 저작권 보호 및 출처 추적에 중요한 이론적 기반을 제공합니다.