XMark: Reliable Multi-Bit Watermarking for LLM-Generated Texts

1. 문제 정의 (Problem)

대형 언어 모델 (LLM) 의 급속한 발전으로 인해 가짜 뉴스, 피싱 이메일, 사기성 리뷰 등 악의적인 콘텐츠 생성이 가능해지면서, AI 생성 텍스트의 출처를 추적하고 저작권을 보호할 수 있는 워터마킹 (Watermarking) 기술이 필수적입니다.

기존의 연구들은 다음과 같은 한계점을 가지고 있었습니다:

• Zero-bit 워터마킹: 단순히 "AI 가 생성함" 여부만 판별할 수 있어, 구체적인 사용자 ID 나 메타데이터를 포함하는 다중 비트 (Multi-bit) 정보 전달이 불가능합니다.
• 기존 Multi-bit 방법의 한계:
  • 계산 비용: 긴 메시지를 인코딩/디코딩하기 위해 모든 가능한 메시지 후보를 브루트포스 (Brute-force) 방식으로 탐색해야 하거나, 블록 단위 처리 시 텍스트 품질이 급격히 저하됩니다.
  • 품질 vs 정확도 트레이드오프: 텍스트 품질을 유지하려면 워터마크 신호가 약해져 디코딩 정확도가 떨어지고, 정확도를 높이려면 텍스트의 자연스러움 (Perplexity) 이 크게 손상됩니다.
  • 짧은 텍스트 문제: 실제 환경에서 생성된 텍스트의 길이가 제한적일 경우 (예: 짧은 답변), 기존 방법들의 디코딩 정확도가 현저히 떨어집니다.

2. 제안 방법: XMARK (Methodology)

저자들은 XMARK라는 새로운 다중 비트 워터마킹 기법을 제안합니다. 이는 텍스트 품질을 유지하면서도 제한된 토큰 수에서도 높은 디코딩 정확도를 달성하기 위해 세 가지 핵심 기술을 결합합니다.

가. Leave-one-Shard-out (LOSO) 전략

• 기존 방식 (MPAC 등): 인코딩할 메시지 블록의 값에 해당하는 하나의 'Shard(조각)'를 선택하여 이를 'Green List(녹색 목록)'로 지정하고, 해당 토큰의 로짓 (Logit) 을 증폭시킵니다. 이때 Green List 의 비율이 낮아 ($2^{-d}$) 텍스트 품질이 떨어집니다.
• XMARK 의 LOSO: 반대로, 메시지 블록 값에 해당하는 하나의 Shard 를 제외하고 나머지 모든 Shard 를 Green List 로 선택합니다.
  • 효과: Green List 비율이 $1 - 2^{-d}$로 크게 증가하여 (예: $d=2$일 때 75% 이상), 토큰 샘플링 분포의 왜곡을 최소화하고 텍스트 품질을 극대화합니다.
  • 디코딩: 디코딩 시 가장 적은 횟수로 등장한 Shard(제외된 Shard) 를 찾아 메시지를 복원합니다.

나. Evergreen List (영구 녹색 목록)

• 다중 해시 키 활용: $k$개의 서로 다른 해시 키를 사용하여 어휘 (Vocabulary) 를 $k$번 다르게 순열 (Permutation) 합니다.
• 교집합 구성: 각 순열에서 LOSO 전략으로 생성된 $k$개의 Green List 의 **교집합 (Intersection)**을 'Evergreen List'로 정의합니다.
• 장점: Evergreen List 에 속한 토큰들의 로짓을 증폭시킵니다. 이는 Green List 의 크기를 유지하면서도 ($E[|E|] \approx (1-2^{-d})^k |V|$), 여러 순열을 통해 더 많은 관측 데이터를 확보하여 디코딩 신뢰도를 높입니다.

다. 제한된 토큰 - Shard 매핑 행렬 (Constrained TMM, cTMM)

• 문제: 짧은 텍스트에서는 토큰 - Shard 매핑을 정확히 추정하기 어렵습니다. 기존 방식에서는 하나의 토큰이 여러 순열에서 같은 Shard 에 속할 경우, 해당 Shard 의 카운트가 과도하게 증가하여 (Over-counting) 신호를 왜곡할 수 있습니다.
• 해결: XMARK 는 cTMM을 도입합니다. 각 토큰이 디코딩 과정에서 각 Shard 에 기여할 수 있는 횟수를 최대 1 회로 제한합니다.
  • 효과: 증폭되지 않은 Shard(메시지를 인코딩한 Shard) 와 증폭된 Shard 간의 차이를 명확하게 구분하여, 짧은 텍스트에서도 높은 디코딩 정확도를 보장합니다.

3. 주요 기여 (Key Contributions)

1. LOSO 인코딩 방식: Green List 비율을 높여 텍스트 품질 (Perplexity) 을 기존 방법보다 획기적으로 개선했습니다.
2. Evergreen List 및 cTMM: 제한된 토큰 수 환경에서도 신뢰할 수 있는 디코딩을 가능하게 하는 새로운 디코딩 메커니즘을 설계했습니다.
3. 성능 우위: 다양한 다운스트림 작업 (텍스트 완성, 요약, 스토리 생성) 에서 기존 최첨단 방법 (MPAC, StealthInk 등) 을 능가하는 높은 비트 정확도 (Bit Accuracy) 와 우수한 텍스트 품질을 동시에 달성했습니다.

4. 실험 결과 (Results)

LLaMA-2-7B 모델을 기반으로 한 광범위한 실험 결과는 다음과 같습니다:

• 디코딩 정확도 (Bit Accuracy):
  • 짧은 텍스트 (T=150): 텍스트 완성 작업에서 XMARK 는 **98.75%**의 정확도를 기록하여, 2 위인 CycleShift(95.25%) 보다 3.5%p 이상 우위를 점했습니다.
  • 긴 메시지 (b=32): 메시지 길이가 길어질수록 정확도가 떨어지는 기존 방법들과 달리, XMARK 는 $b=32$에서도 82.62% 의 높은 정확도를 유지했습니다.
  • 제한된 토큰: 토큰 수가 100 개로 줄었을 때 기존 방법들의 정확도가 급락하는 반면, XMARK 는 cTMM 덕분에 상대적으로 안정적인 성능을 보였습니다.
• 텍스트 품질 (Perplexity):
  • LOSO 전략 덕분에 MPAC(Perplexity 5.08) 보다 낮은 Perplexity(4.61) 를 기록하며, 비워터마크 텍스트에 가까운 자연스러운 문장을 생성했습니다.
  • StealthInk 는 품질은 좋았으나 정확도가 낮았고, XMARK 는 두 가지 요소를 모두 균형 있게 충족했습니다.
• 강건성 (Robustness):
  • 텍스트 편집 공격 (Copy-Paste, Paraphrase): 텍스트를 복사/붙여넣기하거나 재구성 (Paraphrase) 하는 공격에 대해 XMARK 는 다른 방법들보다 더 높은 정확도로 워터마크를 복원했습니다.
  • 기계 번역: WMT14 독일어 - 영어 번역 작업에서도 BLEU 점수가 가장 높았으며, 워터마크가 번역 품질에 미치는 부정적 영향을 최소화했습니다.
• 효율성: 인코딩 및 디코딩 시간이 기존 방법들과 유사하거나 더 빠르며, 계산 비용이 거의 추가되지 않았습니다.

5. 의의 및 결론 (Significance)

XMARK 는 LLM 생성 텍스트의 다중 비트 워터마킹 분야에서 품질과 정확도의 트레이드오프를 해결한 획기적인 방법론입니다.

• 실용성: 실제 서비스 환경에서 자주 발생하는 '짧은 텍스트'나 '메시지 길이 제한' 상황에서도 신뢰할 수 있는 출처 추적이 가능합니다.
• 확장성: 사용자 ID, 타임스탬프 등 다양한 메타데이터를 안전하게 임베딩할 수 있어, AI 생성 콘텐츠의 악용 방지 및 책임 소재 규명에 기여할 수 있습니다.
• 미래 방향: 더 긴 메시지 ($d$ 증가) 에 대한 적응, 공격에 대한 명시적 강건성 강화, 하이퍼파라미터 ($k, \delta$) 의 자동 최적화 등이 향후 연구 과제로 제시되었습니다.

결론적으로, XMARK 는 LLM 의 안전한 활용을 위한 강력한 기술적 기반을 제공하며, 기존 방법들의 한계를 극복하고 새로운 표준을 제시합니다.