Fast segmentation of watermarked texts from large language models through an epidemic change-point framework

Technische Samenvatting: Snelle Segmentatie van Watermerkteksten uit Grote Taalmodellen via een Epidemisch Veranderingspunt-framework

Probleemstelling
De proliferatie van Grote Taalmodellen (LLM's) heeft robuuste mechanismen vereist voor het detecteren van door machines gegenereerde inhoud om zorgen over authenticiteit, auteursrecht en academische integriteit aan te pakken. Hoewel watermerkregelingen—het inbedden van statistische signalen in de token-generatie met behulp van geheime sleutels—zijn ontwikkeld om de aanwezigheid van door LLM gegenereerde tekst te detecteren, blijft de fijnmaziger taak van het lokaliseren van specifieke watermerksegmenten binnen een tekst met gemengde bronnen (bevatten zowel menselijke als door machines gegenereerde inhoud) onderbelicht. Bestaande segmentatiealgoritmen lijden vaak aan een verbijsterende computationele complexiteit, waardoor ze ongeschikt zijn voor lange teksten, of missen theoretische garanties die robuust zijn tegen parafrasering en nabewerking. Bovendien worstelen huidige methoden er moeizaam mee om efficiënt meerdere disjuncte watermerkintervallen binnen één enkel document te identificeren.

Methodologie: Het Epidemisch Veranderpunt-perspectief
De auteurs stellen WISER voor (Watermark Identification via Segmenting Epidemic Regions), een algoritme dat het probleem van watermerksegmentatie herformuleert als een epidemisch veranderpunt-detectieprobleem.

1. Pivot-statistieken en Verhoogde Alternatieven: De methode vertrouwt op "pivot-statistieken" ($Y_t$), die functies zijn van de gegenereerde tokens en pseudo-willekeurige sleutels. Onder de nulhypothese (door mensen gegenereerde/niet-watermerktekst) volgen deze statistieken een bekende, stationaire distributie met gemiddelde $\mu_0$. Onder de alternatieve hypothese (watermerktekst) vertonen de statistieken een eigenschap van "verhoogde alternatieven", waarbij hun verwachte waarde strikt groter is dan $\mu_0$ door een marge $d$, ongeacht de specifieke Next Token Distribution (NTP) van de LLM.
2. Epidemische Modellering: In tegen tegenover standaard veranderpuntproblemen waarbij een verschuiving onophoudelijk voortduurt, creëert watermarking "epidemische" intervallen: het gemiddelde van de pivot-statistieken verschuift omhoog voor een specifiek aaneengesloten segment (het watermerk) en keert terug naar de baseline buiten dat segment.
3. Algoritmeontwerp:
   • Single Segment Estimator: Voor een enkel watermerkpatroon passen de auteurs een estimator aan die een bevooroordeelde surplus minimaliseert buiten een kandidaat-interval. Door een bufferterm ($\rho \tilde{d}$) af te trekken van de som van de statistieken buiten het interval, straft het algoritme het opnemen van niet-watermerktekst af, terwijl het het uitsluiten van verhoogde watermerktekst beloont.
   • Multi-Segment Strategie (WISER): Om meerdere segmenten te behandelen zonder voorafgaande kennis van hun aantal ($K$), hanteert WISER een vierfasen-pipeline:
     • Blocking (Blokvorming): De tekst wordt verdeeld in blokken. Blokken waarvan de sommen een drempelwaarde $Q$ overschrijden, worden behouden.
     • Discarding (Wegwerpen): Verbonden componenten van de behouden blokken worden gevormd. Korte componenten (waarschijnlijk fout-positieven) worden weggegooid op basis van een lengtedrempel ($c\sqrt{\log n}$).
     • Enlargement (Vergroting): De resterende verbonden regio's worden uitgebreid met een factor $\sqrt{n}$ om ervoor te zorgen dat ze de werkelijke watermerksegmenten volledig dekken.
     • Refined Local Search (Verfijnde Lokale Zoektocht): Binnen deze uitgebreide regio's wordt de single-segment estimator toegepast om de begin- en eindpunten nauwkeurig te lokaliseren.
   • Computationele Efficiëntie: Door de zoekruimte te beperken tot de uitgebreide regio's die voortkomen uit de screeningsfase, bereikt WISER een computationele complexiteit van $O(n)$, wat het eerste algoritme maakt met een theoretisch gegarandeerde lineaire tijdcomplexiteit.

Belangrijkste Bijdragen

• Nieuw Perspectief: Het artikel legt een formele verbinding tussen watermerklokalisatie en epidemische veranderpuntdetectie, een framework dat voorheen onderbenut werd in dit domein.
• Theoretische Garanties: De auteurs bieden foutmarges voor eindige steekproeven en bewijzen de consistentie van WISER voor het detecteren van meerdere watermerksegmenten. Stelling 3.1 stelt vast dat de symmetrische differentie tussen de geschatte en ware intervallen convergeert naar nul met een snelheid van $O((\rho \tilde{d})^{-1})$. Stelling 4.1 breidt dit uit naar het multi-segment geval en bewijst dat WISER het aantal segmenten en hun locaties met een hoge waarschijnlijkheid correct identificeert wanneer $n \to \infty$.
• Algoritmische Innovatie: WISER is het eerste algoritme dat een bewijsbaar theoretisch geldige multi-segment watermerklokalisatie biedt terwijl het een $O(n)$ computationele efficiëntie behoudt.
• Robuustheid: De methode is ontworpen om agnostisch te zijn voor de specifieke LLM-architectuur of NTP, waarbij enkel wordt vertrouwd op de eigenschappen van de pivot-statistieken en de hypothese van verhoogde alternatieven.

Experimentele Resultaten
Uitgebreide numerieke experimenten zijn uitgevoerd op benchmark-datasets (C4 News) met diverse LLM's (bijv. OPT, Gemma, Llama-3, Mistral) en uiteenlopende watermerkregelingen (Gumbel, Inverse Transform, Red-Green, Permute-and-Flip).

• Nauwkeurigheid: WISER presteerde consequent beter dan de state-of-the-art baselines (Aligator, SeedBS-NOT, Waterseeker) op alle metrieken, inclusclusief Intersection-over-Union (IoU), Precisie, Recall en F1-score. In veel scenario's bereikte WISER een prestatie die nabij de "Oracle"-estimator ligt (die kennis veronderstelt van het ware aantal segmenten $K$).
• Snelheid: Empirische runtime-analyse bevestigde de theoretische $O(n)$ complexiteit. WISER was aanzienlijk sneller dan concurrerende methoden, die vaak super-lineaire of kwadratische schaling vertoonden.
• Robuustheid: Het algoritme behield een hoge prestatie onder variërende niveaus van temporele afhankelijkheid in de token-generatie en toonde veerkracht tegen menselijke bewerkingen (substitutie, insertie, deletie) in teksten met gemengde bronnen.

Betekenis en Claims
Het artikel positioneert WISER als een cruciaal instrument voor AI-moderatie en inhoudsverificatie. De auteurs beweren dat zij, door klassieke statistische theorie (epidemische veranderpunten) te verbinden met moderne generatieve AI-uitdagingen, een oplossing hebben geproduceerd die zowel theoretisch geldig als computationeel efficiënt is.

De betekenis ligt in het adresseren van een gat in de literatuur waar bestaande methoden ofwel te traag waren voor praktische inzetbaarheid op lange documenten, ofwel een gebrek hadden aan rigoureuze statistische garanties. De auteurs benadrukken dat hun aanpak geen kennis vereist van de specifieke LLM-architectuur, wat het een generaliseerbare oplossing maakt voor het detecteren en lokaliseren van watermerkgehalte in real-world scenario's met gemengde mens-AI tekst. Het werk benadrukt ook het nut van pivot-statistieken bij het afhandelen van de niet-stationaire aard van watermerktekstsequenties, een kenmerk dat het onderscheidt van de standaard veranderpuntdetectie-literatuur.