Estimating near-verbatim extraction risk in language models with decoding-constrained beam search

• URL: http://arxiv.org/abs/2603.24917v1
• Date: Thu, 26 Mar 2026 01:15:16 GMT
• Title: Estimating near-verbatim extraction risk in language models with decoding-constrained beam search
• Abstract summary: We show that greedy-decoding methods miss how extraction risk varies across sequences.<n>We introduce decoding-constrained beam search, which yields deterministic lower bounds on near-verbatim extraction risk.
• Score: 66.14049361268074
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent work shows that standard greedy-decoding extraction methods for quantifying memorization in LLMs miss how extraction risk varies across sequences. Probabilistic extraction -- computing the probability of generating a target suffix given a prefix under a decoding scheme -- addresses this, but is tractable only for verbatim memorization, missing near-verbatim instances that pose similar privacy and copyright risks. Quantifying near-verbatim extraction risk is expensive: the set of near-verbatim suffixes is combinatorially large, and reliable Monte Carlo (MC) estimation can require ~100,000 samples per sequence. To mitigate this cost, we introduce decoding-constrained beam search, which yields deterministic lower bounds on near-verbatim extraction risk at a cost comparable to ~20 MC samples per sequence. Across experiments, our approach surfaces information invisible to verbatim methods: many more extractable sequences, substantially larger per-sequence extraction mass, and patterns in how near-verbatim extraction risk manifests across model sizes and types of text.

Related papers

• Contaminated Multi-task Learning with Heterogeneity: Fundamental Limits and Optimal Algorithms [5.54992643082602]
  We study a contaminated multi-task empirical risk minimization framework.<n>Our goal is to estimate both the global minimizer of the average risk and the clean task-specific minimizers.<n>We propose a computationally efficient filtering-based robust multi-task gradient descent method.
  arXiv  Detail & Related papers  (2026-07-02T18:23:41Z)
• Beyond Indistinguishability: Measuring Extraction Risk in LLM APIs [12.914333266854102]
  We show that indistinguishability properties are neither sufficient nor necessary for preventing data extraction in LLM API.<n>We formalize a privacy-game separation between extraction and indistinguishability-based privacy.<n>We provide actionable mitigation guidelines across model training, API access, and decoding configurations.
  arXiv  Detail & Related papers  (2026-04-20T18:00:22Z)
• Decoding-Free Sampling Strategies for LLM Marginalization [15.214953630908477]
  Modern language models operate on subword-tokenized text in order to make a trade-off between model size, inference speed, and vocabulary coverage.<n>We investigate sampling strategies that are decoding-free, instead relying entirely on extremely cheap sampling strategies that are model and tokenizer agnostic.
  arXiv  Detail & Related papers  (2025-10-23T04:50:14Z)
• Measuring memorization in language models via probabilistic extraction [29.438509661725117]
  Large language models (LLMs) are susceptible to memorizing training data.<n>Discoverable extraction is the most common method for measuring this issue.<n>We introduce probabilistic discoverable extraction, which, without additional cost, relaxes discoverable extraction by considering multiple queries.
  arXiv  Detail & Related papers  (2024-10-25T11:37:04Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Token-Level Adversarial Prompt Detection Based on Perplexity Measures and Contextual Information [67.78183175605761]
  Large Language Models are susceptible to adversarial prompt attacks. This vulnerability underscores a significant concern regarding the robustness and reliability of LLMs. We introduce a novel approach to detecting adversarial prompts at a token level.
  arXiv  Detail & Related papers  (2023-11-20T03:17:21Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB)<n>We introduce an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor.<n>We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  This paper unifies the analysis of risk-averse Thompson sampling algorithms for the multi-armed bandit problem. Using the contraction principle in the theory of large deviations, we prove novel concentration bounds for continuous risk functionals. We show that a wide class of risk functionals as well as "nice" functions of them satisfy the continuity condition.
  arXiv  Detail & Related papers  (2021-08-25T17:09:01Z)
• MLE-guided parameter search for task loss minimization in neural sequence modeling [83.83249536279239]
  Neural autoregressive sequence models are used to generate sequences in a variety of natural language processing (NLP) tasks. We propose maximum likelihood guided parameter search (MGS), which samples from a distribution over update directions that is a mixture of random search around the current parameters and around the maximum likelihood gradient. Our experiments show that MGS is capable of optimizing sequence-level losses, with substantial reductions in repetition and non-termination in sequence completion, and similar improvements to those of minimum risk training in machine translation.
  arXiv  Detail & Related papers  (2020-06-04T22:21:22Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  We develop Thompson Sampling-style algorithms for mean-variance MAB. We also provide comprehensive regret analyses for Gaussian and Bernoulli bandits. Our algorithms significantly outperform existing LCB-based algorithms for all risk tolerances.
  arXiv  Detail & Related papers  (2020-02-01T15:33:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.