PaperlayerView exact revision on arXiv

Source-linked AI summary

Stealing the Decoding Algorithms of Language Models

Ali Naseh, Kalpesh Krishna, Mohit Iyyer, Amir Houmansadr

arXiv:2303.04729v4cs.LGcs.CLcs.CR

TL;DR

Choosing and tuning decoding algorithms for language-model APIs is costly, making their types and hyperparameters valuable targets. This paper develops an API-based attack to infer them and reports near-perfect decoding-type accuracy at low cost across GPT models, alongside an evaluated defense.

  • Problem

    Selecting decoding algorithms matters for text-generation performance, but choosing and tuning them is costly because quality evaluation requires human assessment.

    Source: §1 · p. 1

  • Method

    The attack infers decoding types and hyperparameters from API observations, using distinguishable output signatures and assuming access to the target LM’s inner probability distribution.

    Source: §1 · p. 2

  • Results

    $0.8, $1, $4, and $40 are the reported costs for attacks on four GPT-3 versions, which achieve near-perfect decoding-type accuracy and accurate hyperparameter estimates across GPT-2, GPT-3, and GPT-Neo.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The findings identify decoding strategies as targets for low-cost theft and motivate defenses for LM-based systems.

    Source: §11 · p. 14

    Stages requiring inner probabilities need a reference model of the same type as the target, although some attack stages do not require those probabilities.

    Source: §9 · p. 14

Abstract

from arXiv · show

A key component of generating text from modern language models (LM) is the selection and tuning of decoding algorithms. These algorithms determine how to generate text from the internal probability distribution generated by the LM. The process of choosing a decoding algorithm and tuning its hyperparameters takes significant time, manual effort, and computation, and it also requires extensive human evaluation. Therefore, the identity and hyperparameters of such decoding algorithms are considered to be extremely valuable to their owners. In this work, we show, for the first time, that an adversary with typical API access to an LM can steal the type and hyperparameters of its decoding algorithms at very low monetary costs. Our attack is effective against popular LMs used in text generation APIs, including GPT-2, GPT-3 and GPT-Neo. We demonstrate the feasibility of stealing such information with only a few dollars, e.g., $\$0.8$, $\$1$, $\$4$, and $\$40$ for the four versions of GPT-3.

1 INTRODUCTION

Decoding choices are costly to tune and valuable to providers, and this paper introduces an API-based attack to infer them. The attack achieves near-perfect decoding-type detection with accurate hyperparameter estimates, and the paper also evaluates a defense.

1 INTRODUCTION

  • Decoding choices affect text-generation performance, while selecting and tuning them requires costly human evaluation and makes them valuable service-provider assets.The preferred approach can differ by task: beam search is more common for translation, while sampling methods are preferred for story diversity.Source: §1 · p. 1
  • The paper presents the first LM decoding-algorithm stealing attack, asking whether API access can reveal decoder types and hyperparameters and at what monetary cost.The attack targets the decoder as a second black box, distinct from the LM.Source: §1 · pp. 1–2
  • The attack infers decoder types and hyperparameters from API outputs, using distinguishable output signatures and assuming access to the target LM’s inner probability distributions.The paper describes several scenarios for obtaining those distributions, including top-token probabilities exposed by GPT-3’s API.Source: §1 · p. 2
  • $0.8, $1, $4, and $40 are the reported costs for attacks on four GPT-3 versions, with near-perfect decoding-type accuracy and accurate hyperparameter estimates.The experiments use custom decoding algorithms with GPT-2, GPT-3, and GPT-Neo rather than targeting real deployments.Source: §1 · p. 2
  • The estimated decoder’s output distributions were similar to the targeted API’s distributions in all reported cases.The authors also evaluate the number of queries needed for accurate attacks theoretically and practically.Source: §1 · p. 2
  • 0.1 average deviations in inferred temperature and nucleus-sampling p accompany a defense that does not substantially affect perplexity.The inferred values differ from their true values under the countermeasure.Source: §1 · p. 2

2 BACKGROUND

The section introduces autoregressive text generation and the decoding choices that select each next token. It contrasts deterministic search with sampling methods and their trade-offs in open-ended generation.

2 BACKGROUND

  • Transformers, including GPT-2 and GPT-3, are among the architectures used as language models for text generation.The background also mentions recurrent networks and attention-based encoder-decoder models.Source: §2 · p. 3

2.1 Open-Ended Text Generation

  • Open-ended generation produces a left-to-right continuation from context, with each next-token choice based on conditional probabilities.The section contrasts tasks with constrained outputs, such as translation and summarization, with tasks where diverse outputs are desirable.Source: §2.1 · p. 3

2.2 Decoding Algorithms

  • The section surveys six decoding algorithms: greedy search, beam search, random sampling, temperature sampling, top-k sampling, and nucleus sampling.Greedy search and beam search are deterministic; the other four use probabilistic sampling.Source: §2.2 · p. 3

2.2.1 Maximization-Based Methods.

  • Greedy and beam search maximize sequence probability, but can produce low-quality, low-diversity text in open-ended generation.Greedy search can make locally optimal but globally suboptimal choices; beam search considers multiple hypotheses and is more suited to constrained tasks such as translation.Source: §2.2.1 · p. 3

2.2.2 Sampling-Based Methods.

  • Sampling-based methods support diverse open-ended output, while top-k’s fixed token count can mismatch distributions that shift between flat and peaked.Nucleus sampling instead selects the smallest token set whose cumulative probability exceeds p; temperature changes the relative likelihood of high- and low-probability tokens, with smaller temperatures associated with less diversity and higher quality.Source: §2.2.2 · p. 3

3 HIGH-LEVEL OVERVIEW OF OUR ATTACK

The section frames decoding-algorithm theft as an attack on the decoding component of a language-model API and specifies the adversary’s information and goal. It motivates the risk, describes ways to obtain the model’s inner probabilities, and outlines a staged mathematical attack.

3 HIGH-LEVEL OVERVIEW OF OUR ATTACK

  • The overview organizes the attack around terminology, adversary capabilities and targets, motivation, prerequisites, and the high-level approach.The attack targets the decoding algorithm, the second of two black-box components in text-generation systems.Source: §3 · p. 4

3.1 Terminologies

  • The inner distribution is generated by the language model before decoding, while the final distribution reflects the API after decoding.The paper illustrates both distributions in Figure 1.Source: §3.1 · p. 4

3.2 Threat Model

  • The adversary aims to identify the decoding type and its hyperparameters using the inner probabilities, specifically the top two tokens, and match the victim’s final token distribution.The study targets GPT-2, GPT-3, and GPT-Neo; most experiments use GPT-2 because it is free and millions of queries were needed.Source: §3.2 · p. 4

3.3 Attack’s Motivation

  • Tuned decoding algorithms are described as a competitive advantage, and an example estimates $63,000 to evaluate nine configurations with crowd workers.The example assumes 100 paragraphs per configuration, 20 workers, and payment of $3.5 per paragraph, excluding qualification-exam expenses.Source: §3.3 · p. 4

3.4 Attack’s Prerequisites

  • The attacker can obtain inner probabilities directly from an API, approximate them with a base model, or infer them through model stealing.The passages note that fine-tuning can alter pretrained model weights, affecting the base-model reference.Source: §3.4 · p. 5

3.5 High-level Attack Approach

  • The mathematical attack detects decoding methods in consecutive stages using their properties, then estimates hyperparameters from inner and final probabilities.The paper says it provides theoretical reasoning for the estimation formulas’ accuracy.Source: §3.5 · p. 5

4 DETAILS OF OUR ATTACK ALGORITHMS

The attack uses staged API queries to identify a decoding algorithm and estimate its hyperparameters. Its tests distinguish sampling from deterministic decoding and then inspect output behavior and probabilities.

Stage 1: Is it a sampling decoding algorithm or not?

  • Repeated outputs distinguish sampling from non-sampling; rare apparent consistency under sampling becomes less likely as queries increase.Repeated generations also approximate the API’s final probability distribution by token frequency.Source: §4 · pp. 5–6

Stage 2: Is it greedy or beam search?

  • Greedy search preserves earlier generated tokens, whereas beam search may revise them; the maximum observed token rank estimates beam size.Repeating the rank test across arbitrary sequences and taking the maximum makes the estimate more reliable.Source: §4 · p. 5

Detecting combined decoding strategies

  • For combined sampling strategies, the attack identifies which methods are used and then estimates their corresponding hyperparameters.The paper considers combinations of temperature, top-k sampling, and nucleus sampling.Source: §4 · p. 5

Stage 3: Does the API use temperature to decode?

  • The same formula estimates temperature across the described sampling combinations; an estimate near 1 indicates temperature is not used.The paper says the formula applies across the cases considered in its theorems.Source: §4 · pp. 6–7

Stage 4: Is the decoding algorithm one of top-k or temperature and top-k combined?

  • Repeatedly regenerating next tokens reveals top-k: the unique-token count estimates k, but this test does not determine whether top-k precedes nucleus sampling.The count-based test is used with earlier stages to distinguish top-k from temperature-plus-top-k.Source: §4 · p. 8

Stage 5: Does the API use Nucleus Sampling as part of its decoding algorithm?

  • For nucleus sampling, the cumulative inner probabilities of retained tokens provide an acceptable estimate of p, though it may differ slightly from the actual value.The paper states that sampling with this estimate leaves the final probability distribution unchanged.Source: §4 · p. 8

Second approach for estimating p in Nucleus Sampling

  • A second nucleus-p estimator is less dependent on victim-model probabilities and may help when exact inner probabilities are unavailable, though it may be less accurate.The first approach can become inaccurate when small changes occur in those probabilities.Source: §4 · p. 8

Stage 6: Is top-k used before Nucleus Sampling?

  • When top-k precedes nucleus sampling, the estimated p varies across time steps; the paper proposes iterating across candidate k values to estimate both parameters.The authors characterize this combined case as the most complicated in their analysis and arguably not very practical.Source: §4 · pp. 8–9

5 EVALUATIONS AND EXPERIMENTS

The evaluations test the attack on GPT-2, GPT-3, and GPT-Neo, using distribution comparisons and experiments on individual attack stages. They also examine prompt engineering as a setting for obtaining a reference distribution.

5.1 Evaluation Metrics

  • The evaluation compares victim and estimated distributions using the Kolmogorov-Smirnov test and KL divergence; same-setting pairs averaged 0.0017 ± 0.0007 KL divergence.KL divergence typically exceeded 0.1 when hyperparameters differed.Source: §5.1 · p. 9

5.2 Evaluation of Each Stage on GPT-2

  • Across 1,000 APIs randomly using greedy or beam search (beam sizes 2–10), the method detected decoding type with 100% accuracy and estimated beam size with high accuracy using 40 arbitrary prompts.Source: §5.2 · p. 10
  • Temperature estimation improves with more queries: 1,000 were insufficient, while 10,000 allowed an estimate; top-k estimates can fail if a top-k token is never generated.Temperature in addition to top-k lowers the chance of generating less likely tokens, so more queries may be needed.Source: §5.2 · pp. 10–11

5.3 Experiments on GPT-3

  • GPT-3 experiments use the API’s inner probabilities and repeated queries to estimate temperature or nucleus-sampling parameters, within the API’s available options.The API supports temperature and top-p, but not top-k or beam search; using both temperature and top-p results in only temperature being applied.Source: §5.3 · pp. 11–12

5.4 Experiments on GPT-Neo

  • For GPT-Neo 1.3B, the reported hyperparameter estimates align across scenarios and are on par with the GPT-2 and GPT-3 results.Experiments used 10,000 queries per run and repeated the process four times.Source: §5.4 · p. 12

5.5 Attack Efficacy in an API with Prompt Engineering

  • For prompt-engineered APIs, a long prompt in the same context can approximate the victim’s internal distribution using the same prompt and base model as reference.The experiments report that adding a prompt to the beginning of a long text does not significantly change the next-token distribution.Source: §5.5 · p. 12

6 ANALYSIS OF THE COST OF THE ATTACK

The paper estimates API-query costs for the attack, using a worst-case query count and GPT-3 pricing examples.

6 ANALYSIS OF THE COST OF THE ATTACK

  • The worst case requires approximately 400,000 queries of five tokens each, totaling 2,000,000 tokens.This case assumes the API uses both top-k and nucleus sampling, requiring every attack stage.Source: §6 · p. 12
  • The cost calculation applies the per-1,000-token price to the 2,000,000-token worst-case total.The paper expresses the estimate as (2,000,000/1000 × x), where x is the cost per 1,000 tokens.Source: §6 · pp. 12–13
  • $0.8, $1, $4, and $40 are the estimated costs for Ada, Babbage, Curie, and Davinci, respectively.These estimates use the stated GPT-3 prices per 1,000 tokens.Source: §6 · p. 13

7 POTENTIAL COUNTERMEASURE

The proposed countermeasure perturbs generated tokens to disrupt hyperparameter extraction, while aiming to limit effects on API performance.

7 POTENTIAL COUNTERMEASURE

  • Randomly replacing generated tokens with probability 0.1 is proposed to add noise to the API’s final probability distribution.The attack depends on the accuracy of that final distribution.Source: §7 · p. 13
  • The added noise changes the final distribution and makes hyperparameter extraction more difficult, especially for sensitive temperature estimates.The paper reports that Table 10 shows the method effectively defends against the attack.Source: §7 · p. 13
  • The paper notes that a defense may hurt API performance and suggests replacing tokens only among the most probable tokens to minimize that impact.Perplexity is used to compare generated text with and without the defense, but the supplied passage gives no result.Source: §7 · p. 13

8 ETHICS DISCUSSIONS

The authors report that their experiments used their own language-model systems, not real-world systems. They discuss disclosure and potential countermeasures for the threat to downstream LM services.

8 ETHICS DISCUSSIONS

  • The experiments did not attempt to steal decoding algorithms from real-world LM systems; they used the authors’ own systems.The paper frames its findings as demonstrating the possibility of stealing IP from real-world systems, not as an attack conducted against them.Source: §8 · p. 13
  • The paper discloses the threat to the community because it says contacting the many downstream users of GPT models for responsible disclosure would not be possible.The authors note that the attacks target third parties using GPT models for downstream tasks, not GPT-2, GPT-3, or GPT-Neo themselves.Source: §8 · p. 13
  • The authors discuss a countermeasure whose table reports disrupted hyperparameter estimates and a minor change in system perplexity.Table 10 describes p-values for new estimates and a before-and-after perplexity comparison.Source: §8 · p. 13, Table 10 · p. 14

9 LIMITATIONS

The attack has stages with different access requirements: some can identify decoding behavior without inner probabilities, while others rely on them.

9 LIMITATIONS

  • Greedy and beam search detection, and identifying k in top-k sampling, do not require inner probabilities and can apply to any LM type.These are examples of attack stages that do not depend on the target model’s probability distributions.Source: §9 · p. 14
  • For stages that require inner probabilities, the reference model used to obtain them must be the same type as the target because different models behave differently on sequences.The paper says outputs from likely base models such as GPT-2, GPT-3, or GPT-Neo can be compared to help identify the target’s base model.Source: §9 · p. 14
  • The authors state that identifying the API’s base model is not overly challenging because decoding algorithms reweight token probabilities without changing their order.The paper says the base model can be detected by comparing outputs with texts generated by candidate models.Source: §9 · p. 14

10 RELATED WORKS: ATTACKS ON NLP

Prior NLP security work covers several attack families, but the paper positions decoding-algorithm stealing against open-ended text generation as a distinct, broader hyperparameter-stealing problem.

10 RELATED WORKS: ATTACKS ON NLP

  • Membership inference, embedding vulnerability, memorization-based data extraction, and model inversion are described as NLP attack lines.The cited examples concern training-data membership, vulnerable word embeddings, LM memorization, and reconstructing representative views of examples.Source: §10 · p. 14
  • Backdoor attacks inject triggers during training so a poisoned example can activate an attacker-chosen output while benign behavior remains normal.The paper also notes several works investigating backdoors in language models.Source: §10 · p. 14
  • Model extraction seeks to replicate a victim model’s functionality, with extracted models potentially used to construct adversarial examples.The passage places extraction work in classification and computer-vision settings and mentions both theoretical and empirical studies.Source: §10 · p. 14
  • Earlier API extraction work often targets restricted or predictable outputs; open-ended generation with more diverse output had not been explored in that line of work.The paper cites BERT-based APIs and black-box machine-translation stealing as examples of prior NLP extraction research.Source: §10 · p. 14
  • Hyperparameter stealing had received less study, and concurrent work detected top-k or nucleus sampling while this paper considers a broader range of decoding algorithms and hyperparameters.The passage distinguishes decoding-specific settings from hyperparameters shared across machine-learning algorithms.Source: §10 · p. 14

11 CONCLUSION

The paper concludes that decoding-algorithm stealing against language models is feasible at relatively low cost, proposes a potential defense, and notes that some inferences need no direct probability access. An appendix supplies further beam-size estimation examples.

11 CONCLUSION

  • The authors conclude that decoding strategies and their hyperparameters can be stolen at relatively low cost, and propose a potential defense against the attack.They also say some information can be inferred without direct access to the API model’s probabilities.Source: §11 · p. 14
  • The authors present the work as the first decoding-algorithm stealing attack on language models and call for further attention and research on these vulnerabilities.They state that organizations invest significant resources in selecting decoding strategies and corresponding hyperparameters.Source: §11 · p. 14

A MORE EXAMPLES ON ESTIMATING BEAM SIZE

  • Additional examples illustrate beam-size estimates of 7, 8, and 9 using prompts from a genre-based story-generation dataset and short stories generated by ChatGPT.The appendix also provides token ranks for the prompts at each time step.Source: A MORE EXAMPLES ON ESTIMATING BEAM SIZE · p. 16

B EFFECT OF THE SIZE OF THE MODEL

The attack performs similarly across GPT-2 and GPT-3 model sizes, while applying it to prompt-engineered APIs depends on the prompt and original text sharing a context. Longer queries make the victim and base-model distributions more similar, and the authors test this approach on small GPT-2 and GPT-3 models.

B EFFECT OF THE SIZE OF THE MODEL

  • Performance remains similar across GPT-2 and GPT-3 model sizes, while GPT-Neo 2.7B is impractical under the authors’ computational constraints.The authors attribute the GPT-Neo constraint to limited computational resources.Source: B EFFECT OF THE SIZE OF THE MODEL · p. 16

C HOW TO APPLY THE ALGORITHM IF THE API USES PROMPT ENGINEERING?

  • For prompt-engineered APIs, the attack is effective only when the original text and API prompt share a context; distribution differences decrease as query length increases.The authors connect this to findings that long-range context does not significantly affect local decisions [25].Source: C HOW TO APPLY THE ALGORITHM IF THE… · p. 16, Figure 5 · p. 16
  • The authors test prompt engineering on small GPT-2 and GPT-3 models by using base-model distributions as references and assuming the API prepends the prompt.The results are presented in Table 14.Source: C HOW TO APPLY THE ALGORITHM IF THE… · p. 17

D OTHER DISCUSSIONS

The discussion describes attack stages that remain usable without internal probabilities, while noting that the study covers only a limited, representative subset of decoding strategies. It also identifies settings and tables relevant to beam-size and hyperparameter estimation.

D OTHER DISCUSSIONS

  • Without access to internal probabilities, attackers can still use the first two stages and infer beam size from final probability distributions.They can also detect final-stage top-k sampling and infer k without internal probabilities.Source: D OTHER DISCUSSIONS · p. 17
  • The study examines a limited but representative subset of decoding strategies, leaving state-of-the-art and novel strategies for future vulnerability research.The authors say future decoding methods should consider privacy and security.Source: D OTHER DISCUSSIONS · p. 17
  • Table 11 illustrates beam-size estimation using the highest rank among generated tokens as the estimate.Its Rank column gives the highlighted token’s position in the model’s sorted token list.Source: Table 11 · p. 18
  • Tables 12 and 13 report estimates of temperature and nucleus-sampling p for Medium and Large GPT-2 and GPT-3 models; Table 14 covers prompt engineering without internal probabilities.The captions specify the model and setting scope, but do not provide result values.Source: Table 12 · p. 18, Table 13 · p. 19, Table 14 · p. 19
Loading 2303.04729v4…