Identifiability of Sequential LLM Rewriting Channels

Abstract

A document produced by one language model may be rewritten by others beforeanyone sees it, so the observable text is the endpoint of a latent sequence ofstochastic transformations. Modelling each rewriting mechanism as a Markovkernel and a lineage as an ordered composition of kernels, we ask when thelineage is identifiable from the law of the final text. Order is governed by a commutator: the two orderings of mechanisms A and Bdiffer by P0[K_A, K_B]. Under uniform contractivity, later rewriting damps thatdifference geometrically — a common suffix s contracts any separation by theDobrushin coefficient d(K_s), uniformly over what precedes it. A precedingrewrite acts differently, changing the source distribution at which thecommutator is evaluated, and may amplify, attenuate or eliminate the ordersignal. The main results concern recovery under uniform contraction. For partialrecovery — the regime in which Fano's inequality does not exploit thesequential structure — an Assouad argument on the lineage hypercube shows thatthe expected number of lineage positions recoverable above chance, averagedover the family, is at most (W/2)(1 - d_AB^k) at depth k, hence at most thedepth-independent provenance window W/2 = D1 / (2(1 - d_AB)). For exact recovery of the whole lineage, the coordinatewise separations give asharp upper-envelope exponent: the optimal success probability satisfieslimsup_k (S_k*)^(1/k) <= max{1/2, d_AB}, with a phase transition at d_AB = 1/2.A single explicit reset-and-append family attains all of this — thefinite-depth Hamming bound and the corresponding finite-depth bound onI(pi; X_k) with equality at every k, and the exact-recovery exponent, which itexhibits as a transition in the exponential moment of the retained lineagedepth. For a latent prefix observed after a known common continuation we also give aclosed-form provenance horizon, together with consistency conditions forsignature recovery under dependent tokens.