Segmenting Human-LLM Co-authored Text via Change Point Detection

Technical Summary: Segmenting Human–LLM Co-authored Text via Change Point Detection

Problem Statement
The proliferation of Large Language Models (LLMs) has necessitated robust methods to distinguish human-written text from machine-generated content. While existing research predominantly addresses this as a binary classification problem for entire passages, such approaches are insufficient for "hybrid" or co-authored documents where human and LLM contributions are intermixed. In practical scenarios—such as technical reports where users draft methodologies while LLMs generate descriptive text, or creative writing collaborations—the goal shifts from global classification to localization: identifying specific segments authored by humans versus LLMs. Current sentence-level detectors often fail to account for the structural dependencies between sentences and suffer from suboptimal performance when applied naively to segmentation tasks due to heterogeneous detection score variability (e.g., scores vary significantly based on sentence length).

Methodology
The authors propose a framework that reframes the text segmentation problem as a change point detection task within time-series analysis. The core observation is that the transition between human and LLM authorship constitutes a structural change in the sequence of detection scores.

1. Detection Statistics: The framework utilizes detection scores $\phi(X_t)$ for each sentence $X_t$. These can be zero-shot statistics (e.g., FastDetectGPT based on next-token prediction probabilities) or ML-based classifiers. The intuition is that LLM-generated text yields higher scores than human text.
2. Vanilla Adaptation (VCP): The authors first adapt the standard Narrowest-Over-Threshold (NOT) algorithm using the Cumulative Sum (CUSUM) statistic on the sequence of sentence scores. However, they identify a limitation: standard CUSUM treats all observations uniformly, ignoring that detection reliability varies with sentence length and inherent variance. Shorter sentences often yield noisier scores, making change points near them harder to detect.
3. Weighted Algorithm (WCP): To address heterogeneity, the authors introduce a Weighted Change Point (WCP) algorithm. This method assigns weights $w_i$ to each sentence score, typically inversely proportional to the variance of the score (or approximated by sentence length). The weighted CUSUM statistic amplifies the contribution of high-confidence (low-variance) observations, leading to more accurate localization.
4. Generalized Algorithm (GCP): A third approach, Generalized Change Point (GCP), computes detection scores on concatenated segments rather than individual sentences before applying the CUSUM statistic. Theoretically, under specific conditions (e.g., when $\phi$ is a zero-shot statistic or based on rewrite distance), GCP is shown to be equivalent to WCP.
5. Localization Procedure: After estimating change points $\{\hat{\tau}_k\}$, the text is partitioned into segments. A clustering algorithm (e.g., $k$-means with $k=2$) is applied to the segment-level scores to classify each segment as human- or LLM-authored based on the cluster means.

Theoretical Contributions
The paper provides rigorous finite-sample theoretical guarantees:

• Error Bounds: The authors derive non-asymptotic error bounds for both VCP and WCP. They prove that the localization error of VCP is governed by the maximum variance of the sentence scores, whereas WCP's error depends on the harmonic mean of the variances. This formally demonstrates that WCP outperforms VCP, particularly when variances are heterogeneous.
• Minimax Optimality: A minimax lower bound for the change point estimation error is established. The authors show that the upper bound achieved by WCP matches this lower bound, establishing minimax optimality. Furthermore, they prove the equivalence of WCP and GCP under appropriate conditions, extending this optimality guarantee to the generalized approach.

Empirical Results
The proposed methods were evaluated across diverse datasets (WikiQA, News, Story) and LLM generators (GPT-5-mini, Claude 4.5).

• Baselines: Comparisons included sentence-level predictors, majority voting, direct LLM prompting, TextTiling, and partial LLM detectors (PaLD).
• Performance: WCP consistently outperformed all baselines. In single change-point scenarios, WCP reduced segmentation errors (measured by WindowDiff) by up to 50% compared to strong baselines.
• Robustness: The method demonstrated robustness in multiple change-point settings (up to 8 transitions), adversarial attacks (decoherence and paraphrasing), and varying proportions of LLM content.
• Real-World Application: On the CoAuthor dataset (a real-world human-AI co-writing corpus with three classes: human, collaborative, LLM), WCP achieved the lowest WindowDiff scores, outperforming supervised models like SegFormer in boundary localization despite SegFormer having a lower count error.

Significance and Claims
The paper claims to bridge the gap between classical time-series analysis and modern LLM detection. Its primary significance lies in:

1. Conceptual Innovation: Identifying the structural connection between text segmentation and change point detection, providing a new theoretical lens for the problem.
2. Algorithmic Advancement: Developing weighted and generalized algorithms that explicitly handle the heterogeneity of detection scores, a factor often overlooked in prior localization work.
3. Theoretical Rigor: Establishing the first minimax optimality results for this specific segmentation problem, characterizing the intrinsic difficulty in terms of signal-to-noise ratios and heterogeneous variances.
4. Practical Efficacy: Demonstrating that leveraging change point structures significantly improves the accuracy of localizing human-LLM boundaries compared to naive sentence-level classification or existing heuristics.

The authors maintain a modest stance, noting that while their framework is general, the specific performance gains are tied to the quality of the underlying sentence-level detection scores and the validity of the change point assumptions in real-world co-authoring scenarios.