Provable Robust Watermarking for AI-Generated Text

 

https://arxiv.org/abs/2306.17439

Provable Robust Watermarking for AI-Generated Text

LLM 생성 텍스트에 워터마크를 넣되, 품질 저하 앖이, 낮은 오탐, 미탐율. 패러 프라이즈에 견고해야 함  -> 간단한 워터마크를 제안

 

기존 그린 레드 리스트 방식을 고정된 분할로 단순화 및 z-score 통계로 검출 

어휘 집하에서 특정 비율로 Green list를 만들어 로짓을 일정 부분 더한다. 

이러면 분포가 변하기에 출력물에서 Green list의 수를 통해 검출할 수 있고, z-score를 조정하며 판별 정도를 확인할 수 있음 

 

이론적으로 z-score 경계로 오탐률을 직접 제어할 수 있음 

 

문제 상황	LLM이 생성한 텍스트를 탐지하기 위한 워터마크 기법이 존재하지만, 기존 방식(KGW 2023)은 ① 편집(삽입·삭제·치환)이나 패러프레이즈 공격에 약하고, ② 품질 저하(Perplexity 증가)와 오탐률(FPR) 조절의 이론적 보장이 없었음. 본 논문은 고품질 유지 + 낮은 오탐 + 강한 편집 견고성을 동시에 만족하는 워터마킹을 제안.
방법론	Unigram-Watermark 기법 제안: ① 어휘 집합 V 중 일정 비율 γ(예: 0.5)를 Green 리스트로 고정 선택. ② 생성 시 Green 토큰의 로짓에 +δ(예: 2.0)를 더해 확률 p̂으로 샘플링. ③ 검출 시 Green 토큰의 비율을 세고 z-score로 판단
학습 데이터 & 실험 설정	모델: LLaMA-7B, OPT-6.7B, GPT-NeoX. 데이터셋: • LFQA (Long-Form QA) – 장문 질의응답 생성 • OpenGen – 일반 오픈 도메인 생성. 비교 기준: KGW(K-gram watermark). 디코딩 설정: Greedy, Beam, Nucleus Sampling. 파라미터: γ=0.5, δ=2.0, α=0.01, n≈512~1024 tokens.
실험 내용	① KGW 대비 AUC(검출 성능) 비교. ② Perplexity 비교로 품질 보존 확인. ③ 패러프레이즈·편집 공격 하 강건성 평가. ④ 화이트박스 공격(그린 리스트 추정) 실험. ⑤ 디코딩 방식별 성능 비교(Greedy, Beam, Nucleus).
결과	🔹 AUC 성능: 모든 데이터/모델/공격 환경에서 KGW 대비 향상. 🔹 품질 영향: δ=2.0 기준 Perplexity 변화 ≤0.5 (유의미하지 않음). 🔹 편집 견고성: η=0.3 수준 편집에도 z-score 유지 → KGW 대비 AUC 하락폭 ½ 수준. 🔹 디코딩 독립성: Beam/Nucleus 등 디코딩 방법에 영향 거의 없음. 🔹 화이트박스 공격: Green 리스트 추정 시도에도 AUC 0.8 이상 유지.
기여	1️⃣ 세계 최초의 수학적(Provable) LLM 워터마크 이론 제시 – 품질·오탐·미탐·편집 견고성을 모두 정리로 증명. 2️⃣ 고정(Unigram) 분할 설계로 KGW 대비 단순 + 편집 내성 2배 강화. 3️⃣ 입력 적응형 임계치 τ 계산식 제시 → 목표 FPR(α)로 동적 제어 가능. 4️⃣ 퍼플렉서티 보존 경계식으로 품질 저하 상한 제시. 5️⃣ LLM·디코딩 독립성 확보 → 실사용 가능성 높음.
한계	⚠️ 텍스트 다양성 의존성: Type-I 경계식이 V(y), Cₘₐₓ(y)에 의존 → 템플릿형·단조로운 텍스트(코드, 챗봇 짧은 답변)는 오탐 제어 어려움. ⚠️ 짧은 텍스트(n↓): z∝√n 관계로 문장이 짧을수록 검출력↓. ⚠️ 화이트박스 추정 완전 방어 불가: 충분한 쿼리로 Green 리스트 일부 추정 가능. ⚠️ 비암호학적 보안: 통계적 탐지 기반으로, 암호학 수준의 비가역성은 아님. ⚠️ 영어 중심 평가: 다국어 적용 시 γ, δ 재조정 필요.

 

 

한눈에 보는 핵심

• 문제: LLM 생성 텍스트에 워터마크를 넣되, 품질 저하 없이(quality), 낮은 오탐(Type-I), 낮은 미탐(Type-II), 편집/패러프레이즈에 견고(robust)해야 함. 이 논문은 이 요구를 이론적으로 보장하는 간단한 워터마크(“Unigram-Watermark”)를 제안.
• 아이디어: 기존 “그린/레드 리스트” 방식(KGW+23)을 고정된(unigram 기반) 분할로 단순화하고, z-score 통계로 검출. 이때 품질 보장, 오탐/미탐 한계, 편집 내성을 정리된 정리(theorem)로 제시.
• 주요 결과: 이론적으로는 z-score 경계로 오탐률을 직접 제어(τ 임계치 선택식 제공), 미탐률은 δ·√n 규모로 분리 마진 확보. 편집 η회 후에도 z-score 하락이 **최대 O(η/√n)**으로 제한됨(고정 분할이라 KGW 대비 편집에 2배 강건).
• 실험: LLaMA-7B 등 3개 LLM, 2개 데이터(LFQA, OpenGen)에서 AUC가 기존보다 높고, 다양한 편집·패러프레이즈 공격에서도 우수.

---

방법(검출 절차 포함) — Step by Step

1) 고정 Green/Red 분할(Unigram-Watermark, 생성)

• 어휘 집합 V를 비율 γ로 무작위 고정 선택해 Green 리스트 G를 만든다(크기 γ|V|). 각 시점 t에서 분포 p를 그대로 두되, Green 토큰의 로짓에 +δ를 더한 분포 (\hat p_t)에서 샘플링. (δ: 워터마크 강도)
• 이는 KGW의 “이전 토큰 해시 기반 가변 분할”과 달리 고정 분할이라 분석과 견고성 보장이 쉬워짐. (KGW 개요는 부록 인용)

2) 검출(Detection)

• 의심 텍스트 (u_1,\dots,u_m)에서 인접 쌍 ((u_{t-1},u_t))을 훑어 (u_t)가 **Green( (u_{t-1}) )**에 들어가면 1을 세서 (|u|_G)를 계산.
• 귀무가설 (H_0): “Green 규칙과 무관하게 생성됨” → 기대 (\mathbb E[|u|_G]=\gamma m).
• 검정 통계량:
  [
  z ;=; \frac{|u|_G-\gamma m}{\sqrt{m,\gamma(1-\gamma)}}
  ]
• (z>\tau)이면 “워터마크 생성”으로 판단. (τ는 목표 오탐률 α에 맞춰 선택)

---

이론적 보장(요지)

(A) 품질 보장(Per-token 분포 왜곡 상한)

• 수정된 분포 (\hat p_t)와 원 분포 (p_t)는 (δ,0)-indistinguishable에 해당(최대 발산 2δ 등), 누적해도 전체 시퀀스 KL이 **(O(n\min{\delta,\delta^2}))**로 제한. ⇒ 퍼플렉서티 영향이 작다는 의미.

(B) 오탐(Type-I) 제어 — 임계치 (\tau) 선택식

• 임의(사람) 텍스트 y에 대해
  [
  z_y \le \underbrace{\sqrt{\tfrac{64V(y)\log(9/\alpha)}{1-\gamma}}}{\text{다양성 }V};+;\underbrace{\tfrac{16C{\max}(y)\log(9/\alpha)}{\sqrt{n\gamma(1-\gamma)}}}{\text{반복최대 }C{\max}}
  ]
  가 **확률 ≥ (1-\alpha)**로 성립. 따라서 위 RHS보다 큰 (\tau)를 택하면 FPR ≤ α를 보장. (V, (C_{\max})는 y로부터 계산 가능 → 입력 적응적 τ)
• **중복 제거 버전(Unique)**을 쓰면 (V=C_{\max}=1)이라 더 촘촘한 경계와 간단한 비대칭정규 임계치(Φ⁻¹) 선택식 제공.

(C) 미탐(Type-II) 상계 — “분리 마진”

• 합리적 가정(평균 고엔트로피, homophily)하에 워터마크 텍스트의 z-score는
  [
  z_y ;\gtrsim; (e^{\delta}-1)\sqrt{n,\gamma(1-\gamma)}
  ]
  규모로 증가 → 비워터마크의 (O(1))과 마진 분리 가능(τ를 중간에 배치).

(D) 편집/패러프레이즈 견고성(에디트 거리 η)

• 제안법(고정 분할)의 검정점수 변화:
  [
  z_u ;\ge; z_y ;-; \max!\left{\frac{(1+\gamma/2)\eta}{\sqrt{n}},;\frac{(1-\gamma/2)\eta}{\sqrt{n-\eta}}\right}
  ]
  ⇒ η가 커져도 (\Delta z = O(\eta/\sqrt{n})). KGW(가변 분할)의 경우 위 계수가 2배로 더 취약.

---

실험(설정 및 결과)

• 설정: 3개 LLM과 LFQA/OpenGen 등에서 검출 성능(AUC), 디코딩별(뉴클리어스/다항/빔) 오탐 비교, 패러프레이즈·편집 공격(동의어 치환, 삭제, 스왑) 방어.
• 품질 영향: 빔서치는 퍼플렉서티가 낮지만 출력이 짧아 다양성이 줄 수 있음(오탐 비교 표). 제안법은 퍼플렉서티 유사/비교가능 선에서 동작.
• 견고성: 패러프레이즈·편집 공격에서 AUC가 KGW 대비 지속적으로 우수. 예: LFQA-LLaMA-7B 패러프레이즈, OpenGen-편집(동의어치환·삭제·스왑) 전 범위에서 AUC 상승.

---

구현 디테일(실전 체크리스트)

• 하이퍼파라미터: γ(그린 비율, 보통 0.5), δ(강도, 예: 2). z-검정 임계치 τ는 목표 FPR=α에 맞춰 입력 적응적으로 (V(y), C_{\max}(y))로 계산. Unique-검출 시 더 간단.
• 디코딩 무관성: 오탐 경계 정리는 그리디/뉴클리어스/빔 등 디코딩 방식과 무관(사람 텍스트 포함).
• 화이트박스 위협: 그린/레드 리스트 추정을 시도해도, 리스트 정확 추정이 어렵고(0.7M 토큰 수집 시나리오에도 난해) 고정 분할의 추가 견고성으로 여전히 유효.

---

표 — 논문의 핵심 정리(실험 적용용 “1장 요약표”)

구분 내용 근거

문제 정의	고품질 유지+낮은 오탐/미탐+편집 견고 워터마킹
방법	고정 Green/Red 분할(+δ 로짓 증폭)·z-score 검출
품질 보장	(\mathrm{KL}(\hat p|p) \le O(n\min{\delta,\delta^2})) 등 분포 거리 상한
Type-I(오탐)	(z_y \le \tilde O!\big(\sqrt{V} + C_{\max}/\sqrt{n}\big)) ⇒ τ로 FPR≤α 제어(입력 적응형)
Type-II(미탐)	워터마크 z는 (\Omega((e^{\delta}-1)\sqrt{n\gamma(1-\gamma)})) 규모
편집 견고성	(z_u \ge z_y - O(\eta/\sqrt{n})) (제안법), KGW는 계수 2배 악화
실험 세팅	3 LLM / LFQA, OpenGen, 다양한 디코딩·공격
실험 결과	AUC↑, 퍼플렉서티 유사, 공격에도 우수

---

왜 “고정 분할”이 강한가? (직관)

• 가변 분할(해시 기반)은 편집 한 번에도 이웃 쌍(bigram) 규칙이 2곳까지 흔들려 z-score 감소가 큼(최대 2η 영향). 반면 고정 분할은 unigram 단위만 변해 η 영향으로 제한. ⇒ 이론상 “2배” 견고.

---

실험 재현용 체크리스트

1. 파라미터 선택: (\gamma=0.5), (\delta\in{1.5,2.0}) 등. 목표 FPR=α 설정 후, 입력 텍스트별 (V(y), C_{\max}(y)) 계산 → 식에 따라 τ 산정. (Unique-검출 시 더 단순)
2. 생성 시 주의: 디코딩 자유(그리디/빔/뉴클리어스) — 단, 너무 저다양성(prompt 반복) 출력은 이론 경계가 무의미(오탐 제어 불가) → 프롬프트/디코딩으로 다양성 확보.
3. 공격 평가: 동의어 치환/삭제/스왑 비율(0.1/0.3/0.5)로 AUC 측정, 패러프레이즈(DIPPER 등) 포함.

---

기여(Contribution)

• 단순하고 분석 가능한 고정 분할 워터마크 제안 + 정량적 보장(품질/오탐/미탐/편집).
• KGW 방식에 대한 새 이론 경계(편집 민감도 2배)와 경험적 비교.

한계/주의

• 다양성 의존: 텍스트가 지나치게 단조로우면(Type-I 경계의 V, (C_{\max}) 악화) 오탐 제어식이 무력화.
• 가정 필요: Type-II 보장은 평균 고엔트로피·homophily 가정에 의존(현실에서 충분히 성립하는지 검증 필요).
• 화이트박스 추정: 리스트 추정이 어렵지만, 충분한 쿼리/메타정보가 있으면 일부 약화될 여지는 존재(실험상 완전 무력화는 어려웠음).

---

실무 적용 팁(연구/운영)

• 운영 임계치: 목표 FPR(예: 1%) 고정 → 입력별 (V, C_{\max})로 동적 τ. 반복/템플릿형 답변에는 Unique-검출 권장.
• 길이 효과: (z\sim \delta\sqrt{n})으로 증가하므로, 너무 짧은 응답은 검출력이 떨어짐 → 서비스 정책에 최소 길이 가이드.
• 강도 조절: δ↑는 검출력↑/품질변형↑ 트레이드오프 → 본 논문 경계(분포 거리 상한) 참조해 δ 튜닝.

 

좋아요. 업로드하신 논문(Provable Robust Watermarking for AI-Generated Text)을 축으로 삼아, 텍스트 워터마킹 관련 주요 계열을 한눈에 비교·정리했습니다. 모든 근거는 업로드 본문에서만 인용합니다.

전체 흐름(빅픽처)

1. 統계적(K-gram) 워터마크의 등장 → 해시로 그린/레드 리스트를 **접두어(이전 토큰)**에 따라 매 시점 새로 정하고, 그린 토큰의 로짓에 +δ를 줘 샘플링(소프트 워터마크; KGW’23). 편집·패러프레이즈에 비교적 취약하다는 문제가 제기됨.
2. 본 논문(Unigram-Watermark) → 분할을 고정(unigram) 으로 단순화하고 동일한 z-검정으로 탐지. 이 단순화 덕분에 편집(η) 에 대한 z-점수 감소가 (O(\eta/\sqrt{n}))으로 절반 수준(KGW 대비)임을 **정리(정량 보장)**로 제시.
3. 동시·별개 계열(암호학적 워터마크) → Aaronson(2023), Christ et al.(2023) 등 암호학적 접근은 효용 저하/트레이드오프의 성격이 달라 계보가 분리됨(본 논문은 통계적 계열의 가정/경계를 명시적으로 세움).
4. 탐지기 기반(비-워터마킹) 판별 → 기존 AI-콘텐츠 탐지기들이 사람 글을 오탐하는 한계가 보고됨(예: 비원어민 글). 워터마크는 이런 분포 이동에서도 임계치(z)로 안정적 선별이 가능하다는 실험을 제시.

---

핵심 비교표(요약)

축 KGW’23 K-gram(소프트) Unigram-Watermark(본 논문) 암호학적 워터마크(동시연구) 일반 탐지기(비-워터마킹)

기본 아이디어	접두어로 그린/레드 가변 분할, 그린 로짓 +δ	고정 분할(unigram) + z-검정	암호프리미티브/키로 강건성 설계	분류기/검출기 스코어링
이론 보장	기존 방식 설명·분석 제공(부록 D)	품질·오탐·미탐·편집 모두 정리로 보장, 편집 견고성 2배	보장 형태/트레이드오프가 상이	보장 부재, 분포 이동·오탐 문제
편집/패러프 공격	접두어 의존 → 동의어 교체 등에서 취약 사례	z-점수 감소가 (O(\eta/\sqrt{n})), 2배 강건	설계에 따라 다름	패러·리라이팅에 취약
화이트박스 추정	(분석 대상)	그린 리스트 추정 난해, 알아도 견고성 일부 유지	설계 난이도↑	우회 용이
디코딩 의존성	공통적으로 z-검정 사용	공통. 빔/뉴클리어스 등 전반 비교 제공	별개	별개
품질 영향	δ 조절로 저하 제한	Renyi 발산 상한 등 분포 거리를 이론 상한화	설계에 따름	N/A
대표 강점	구현 단순, 기존 표준	간결+분석가능, 편집 강건성/오탐 제어 명시	보안적 강점	도입 쉬움(워터마크 불요)
대표 한계	접두어 의존으로 패러프에 취약	고정 분할이 항상 최적은 아님, 전지전능 X	구현/운영 복잡	오탐·공정성 이슈

근거: KGW 방식/탐지식 개요(부록 D)와 편집 민감도 비교, 본 논문 기여·보장, 패러프 문제 제기, 암호학 계열 분기, 탐지기 한계 및 사람 글 오탐 사례.

---

각 계열별 장·단점 및 차이(조금 더 깊게)

1) KGW’23 K-gram(“소프트 워터마크”)

• 장점: LLM 로짓 접근만 있으면 구현 간단, 그린/레드 비율 γ와 강도 δ로 직관적 조절 가능.
• 단점: 접두어 기반 가변 분할이라, 동의어 치환/매 토큰 교대 편집 등에서 그린/레드 추론이 무너져 탐지 약화.
• 차이(대비 본 논문): 편집에 대한 z 감소 상계가 최대 계수 2가 붙어 더 큼(같은 η 대비). 본 논문은 같은 z-검정이더라도 분할을 고정해 민감도를 절반으로 줄임.

2) Unigram-Watermark(본 논문)

• 장점
  • 품질 보장: 워터마크 적용 LLM과 원 LLM의 분포 거리가 이론적으로 상한화(퍼플렉서티 열화 통제 가능).
  • 오탐(Type-I) 제어: 텍스트 길이/다양성에 따라 임계치 τ를 계산해 목표 FPR로 캘리브레이션. (본문 전반 서술)
  • 미탐(Type-II) 경계 및 편집 견고성: z가 (\Omega(\sqrt{n}))로 성장, 편집 η에 대해 **(O(\eta/\sqrt{n}))**만 하락 → 길수록 강함.
  • 실증: LLaMA-7B 등에서 패러프/편집 공격 전반 AUC 우위.
• 단점/주의
  • 고정 분할의 비최적 가능성(텍스트/모델 특성 따라 최적 γ, δ 다름)과 보편 무적 아님(공격 면역 X) — 저자들이 한계로 직접 언급.
  • 화이트박스에서 그린 리스트 추정을 시도할 수 있으나, 정확 추정이 어려웠고, 알아도 일부 견고성 유지(실험).

3) 암호학적 워터마크(동시 연구)

• 장점: 키 재료·암호 구성으로 보안적 해석이 명확, 특정 위협 모델에서 강한 보장이 가능.
• 단점/차이: 효용·트레이드오프가 통계적 계열과 다름(본 논문은 별개 계열로 분리해 언급). 연구 난이도·시스템 통합의 복잡성이 상대적으로 큼.

4) 일반 탐지기(비-워터마킹)

• 장점: 모델·서비스 수정 없이 바로 사용 가능.
• 단점/차이: 분포 이동(예: 비원어민 글쓰기)에 오탐 문제가 빈발 — 워터마크 대비 신뢰 가능한 임계치 보정이 어려움(본 논문 실험에서 사례 제시).

---

공격·대응 관점의 차이

• 패러프레이즈/편집: 본 논문은 편집 거리 η로 위협을 포멀화하고, z-점수 변화 상계를 직접 제시(η가 커져도 (\sim\eta/\sqrt{n})). KGW는 같은 프레임에서 계수가 2배 커 더 약함.
• 트릭 프롬프트(이모지/알파벳 삽입): K>1 계열을 깨는 공격(“파인애플/이모지”)에 대해, Unigram + Unique 탐지기는 여전히 동작(Unique로 중복 제거).
• 화이트박스/리스트 추정: 충분한 쿼리로 그린 리스트를 추정 시도해도 정확도가 낮았고, 설혹 알아도 성능이 완전 붕괴되지는 않음(실험).

---

디코딩/품질 트레이드오프 차이

• 빔서치는 퍼플렉서티는 낮게 보이지만 출력 길이가 짧고 다양성이 줄 수 있어(데이터 분포 편향), 워터마크 통계와의 상호작용이 달라짐. 본 논문은 디코딩별 경험적 오탐/TPR 표를 제공.

---

실무 적용 가이드(연구 체크리스트)

1. 목표 FPR 먼저 고정(예: 1%) → 텍스트 길이·다양성에 맞춰 임계치 τ를 보정(z-검정). 짧거나 템플릿성 답변에는 Unique 탐지로 중복 방어.
2. 편집 견고성 요구가 클수록: 고정 분할(unigram), γ≈0.5, δ는 품질 한계 내에서 점증적으로 조정(논문은 분포 거리/품질 영향 상한 제시).
3. 공격 평가: 동의어·삭제·스왑(0.1/0.3/0.5), DIPPER·ChatGPT 패러프 등 공격 스위트로 AUC/TPR/F1을 보고 KGW 대비 차이를 확인.

---

원하시면 위 비교를 LaTeX/HTML 표나 연구 메모 템플릿(γ, δ, τ 산정식 포함)으로 바로 써먹을 수 있게 정리해 드릴게요.

 

아래 설명은 업로드하신 원문(PDF)만을 근거로, **방법론(생성·검출·이론 보장·공격 모델)**을 단계별로 재구성한 것입니다. 필요한 곳에 줄 번호 인용을 달았습니다.

전체 개요

• 제안법 이름: Unigram-Watermark — 기존 그린/레드 리스트 워터마크를 고정(unigram) 분할로 단순화해, 품질 저하를 이론적으로 제한하고(품질 보장), 오탐/미탐/편집 견고성을 정리 수준으로 증명합니다.
• 논문 구성: 문제 설정(정의·위협모델) → 방법(Method) → 이론 결과(품질·Type-I/II·보안/편집) → 실험.

---

핵심 구성요소(기호 정리)

기호/항목 의미

(V)	어휘 크기 (
(\gamma\in(0,1))	Green 리스트 비율(예: 0.5) — (
(\delta>0)	워터마크 강도(그린 토큰 로짓 가중)
(y=y_{1:n})	의심 텍스트(검출 입력)
(	y
(z_y=\dfrac{	y
(\tau)	임계치(목표 오탐률 (\alpha)에 맞춰 계산)

정의·표기는 본문 Algorithm/정리에서 그대로 가져옵니다.

---

방법론 — 생성(Embed) 단계

Algorithm(생성 시 워터마크 주입)

1. Green 집합 고정: 어휘 (\mathcal V)에서 무작위 균일하게 (|G|=\gamma V)인 고정 Green 리스트 (G\subset\mathcal V)를 선택(비밀 키로 시드화 가능).
2. 로짓 조정: 시점 (t)에서 원래 분포 (p_t(\cdot|h)) 대신, 그린 토큰에 **로짓 +(\delta)**를 더한 (\hat p_t)에서 샘플링하여 토큰을 생성(roll-out). 이때 각 이벤트 확률의 로그-오즈가 (\pm\delta) 범위로만 변하므로, ((\delta,0))-indistinguishable 성질을 가집니다(품질 보장 근거).

요점: 분할은 고정(unigram), 조작은 로짓에 일정량 (\delta) — 구현 단순성↑, 분석 용이성↑.

---

방법론 — 검출(Detect) 단계

기본 검출기(Algorithm 2 요지)

• 입력 텍스트 (y=y_{1:n})에 대해, 그린 토큰 개수 (|y|_G)를 세고 (z)-점수
  [
  z_y=\frac{|y|_G-\gamma n}{\sqrt{n\gamma(1-\gamma)}}
  ]
  를 계산합니다. **(z_y>\tau)**이면 워터마크로 판정합니다.

임계치((\tau)) 선택 — 오탐률 (\alpha) 제어식

• Type-I(오탐) 상계 정리에 따라, 텍스트 다양도 지표 (V(y)), 반복최대치 (C_{\max}(y))를 이용해
  [
  \tau;>;\sqrt{\frac{64,V\log(9/\alpha)}{1-\gamma}};+;\frac{16,C_{\max}\log(9/\alpha)}{\sqrt{n\gamma(1-\gamma)}}
  ]
  로 잡으면 **FPR (\le\alpha)**가 보장됩니다(입력 적응형 (\tau)).

대안 검출기 — “Unique”

• (y)를 중복 제거한 시퀀스 (\mathrm{Unique}(y))로 바꿔 같은 검출기를 적용(Algorithm 4). 이 경우 (V=C_{\max}=1)이 되어 더 깔끔한 오탐 상계와 비대칭정규 기반 (\tau) 선택식이 성립합니다.

---

이론적 보장(방법의 핵심 성질)

1) 품질 보장(Distribution Shift 상한)

• 로짓에 (\delta)를 가하는 변형은 매 시점 ((\delta,0))-indistinguishability를 만족(각 사건 (S)에 대해 로그-오즈가 (\pm\delta)로 제한). 이로부터 Rényi/KL/TV 거리의 상한이 도출되어, 퍼플렉서티 저하가 제한적임을 보입니다.

2) Type-I(오탐) 보장

• 앞의 정리(“No false positives”): 어떤 비워터마크 텍스트든 (z_y)는 위의 경계 내에 있으므로, (\tau)를 그보다 크게 잡으면 **오탐률 (\le\alpha)**로 제어됩니다. (디코딩 방식과 무관: 그리디/뉴클리어스/빔 등)

3) Type-II(미탐) 보장(“Only true positive”)

• 평균 고엔트로피 및 homophily 가정 하에서, 워터마크 텍스트의 (z)-점수는
  [
  z_y;\gtrsim;(e^{\delta}-1)\sqrt{n,\gamma(1-\gamma)}
  ]
  규모로 자라므로, 비워터마크의 (O(1))과 큰 마진으로 분리됩니다(적절한 (\tau) 존재).

4) 편집/패러프레이즈 견고성(보안 성질)

• **편집 거리 (\eta)**가 있을 때, 워터마크 텍스트 (y)와 수정본 (u)의 검출 통계는
  [
  z_u ;\ge; z_y;-;\max!\left{\frac{(1+\gamma/2)\eta}{\sqrt{n}},;\frac{(1-\gamma/2)\eta}{\sqrt{,n-\eta,}}\right}
  ]
  으로 **최대 (O(\eta/\sqrt{n}))**만 감소합니다(견고성 정리).

KGW(접두어 의존) 대비 2배 강건: KGW는 **가변 분할(k=1 Markov)**이라 한 번의 편집이 빅그램 두 곳을 흔들어 최대 교란이 2(\eta)로 늘어납니다. 반면 제안법은 **고정(unigram, k=0)**이라 (\eta)에만 비례합니다.

---

위협 모델과 비교 포인트(방법에 내장된 방어 논리)

• 화이트박스/리스트 추정: Green 리스트를 알고자 하는 시도에 대해, 설령 일부 정보를 추정해도 탐지 AUC가 완전 붕괴되지 않음을 실험으로 보입니다(동의어 대체를 “정직하게” 늘릴수록 품질 급락).
• 디코딩 비의존: 오탐 보장은 디코딩과 무관(그리디/뉴클리어스/빔).

---

실험에 쓰인 검출기 설정 팁(방법 재현 관점)

1. (\tau) 선택: 목표 FPR=(\alpha)를 정하고, (,V(y),C_{\max}(y))를 입력별로 계산하여 위 식으로 (\tau)를 입력 적응적으로 산정. (짧거나 반복성이 큰 텍스트는 상계가 무의미할 수 있으므로 주의)
2. “Unique” 사용: 템플릿성/반복성이 큰 데이터에는 중복 제거 검출기가 오탐 제어에 유리. (\tau)의 비대칭정규식도 제공됩니다.
3. 길이 효과: (z\sim \delta\sqrt{n})으로 증가 → 최소 길이 정책을 두면 검출력 확보에 도움.

---

(부록) KGW 방식과의 방법론적 차이를 짚어보기

• 분할 방식: KGW는 접두어 의존(해시 기반) 가변 분할, k=1-Markov, 본 논문은 고정(unigram), k=0. k가 커질수록 편집 견고성은 선형으로 악화됩니다.
• 검출 카운트: KGW는 본질적으로 “빅그램이 Green 규칙을 만족하는 항목 개수”를 세는 것과 동치(편집 한 번에 빅그램 2개 영향) — 여기서 2배 민감의 원인이 나옵니다.

---

요약(한 줄)

Unigram-Watermark는 고정 Green 분할 + z-검정이라는 단순한 설계로, **품질(분포 거리 상한)·오탐(입력 적응 (\tau))·미탐((\Omega(\sqrt{n})) 분리)·편집((O(\eta/\sqrt{n})))**을 동시에 이론 보장하며, KGW(k=1) 대비 편집 견고성이 2배 높도록 설계되었습니다.

필요하시면, 파이썬 의사코드/실제 코드(Green 생성, z-검정, 입력 적응 (\tau), Unique 변형 포함)를 바로 실행 가능한 형태로 만들어 드리겠습니다.