Thread (64 posts)

Excellent question! This is exactly what Section 6 and Appendix C address - the "logprob-free" attacks where you only get the sampled token, not any probability information.

The Basic Approach: Binary Search

The key insight is that with temperature 0 sampling, the API returns the token with the highest logit value. So if you can manipulate logit biases, you can use binary search:

1. Start with prompt $p$ and identify the top token (call it token 0)
2. For each other token $i$:
   • Binary search to find the minimum bias $x_i$ needed to make token $i$ the top token
   • This tells you that $z_i - z_0 \approx -x_i$

The Challenge

This is much more expensive than the logprob-based attacks:

• Basic binary search: ~10 queries per logit (vs 0.25 with logprobs)
• Each token requires $\log_2(B/\epsilon)$ queries for precision $\epsilon$

Improved Methods

The paper presents optimizations that query multiple tokens simultaneously:

1. Hyperrectangle method: Apply biases to multiple tokens at once and accumulate linear constraints based on which token wins
2. One-of-n method: Carefully choose biases to make each token equally likely to be sampled

These reduce the cost to ~3.7 queries per logit, though still much higher than logprob-based methods.

Information-Theoretic Limits

The paper proves (Lemma 6) that you need at least: $\frac{l \cdot \log_2(B/\epsilon)}{\log_2(l)}$ queries, where $l$ is vocabulary size. Their best attack is within a factor of 2 of this theoretical limit!

The key takeaway: Yes, you can extract the model even with just next-token predictions, but it's about 15x more expensive than with logprob access.

Excellent question! Let's examine softmax through an information-theoretic lens to understand why it makes the attack challenging.

Softmax as Information Transformation

The softmax function transforms logits $z \in \mathbb{R}^n$ into a probability distribution: $p_i = \frac{e^{z_i}}{\sum_j e^{z_j}}$

From an information theory perspective, softmax has several key properties:

1. Invariance to Translation

Softmax is invariant to adding a constant to all logits: $\text{softmax}(z + c\mathbf{1}) = \text{softmax}(z)$

This means softmax destroys one degree of freedom—you lose information about the absolute scale of the logits. You can only recover relative differences between logits, not their absolute values.

2. Maximum Entropy Principle

Softmax arises naturally from the maximum entropy principle. Given constraints on expected values, the distribution that maximizes entropy has the form: $p_i \propto e^{\lambda \cdot f_i}$

This connects to why language models use softmax: it's the least biased way to convert scores into probabilities.

3. Information Compression

The log-sum-exp operation in the denominator acts as a "soft maximum": $\log\sum_i e^{z_i} \approx \max_i z_i \text{ (for large differences)}$

This compresses information about the full distribution into a single normalizing constant, making it harder to recover individual logits.

Temperature and Information

Consider softmax with temperature $\tau$: $p_i = \frac{e^{z_i/\tau}}{\sum_j e^{z_j/\tau}}$

• As $\tau \to 0$: Approaches argmax (maximum information about the top token, none about others)
• As $\tau \to \infty$: Approaches uniform distribution (no information preserved)
• $\tau = 1$: Balances between preserving ordering information and relative magnitudes

Why This Matters for the Attack

The attack must overcome several information-theoretic challenges:

1. Lost Degree of Freedom: The attack can only recover $n-1$ independent values from $n$ logprobs due to the normalization constraint $\sum_i p_i = 1$.

2. Nonlinear Coupling: Each logprob depends on ALL logits through the normalization:

   1 - p_i & \text{if } i = j \\ -p_i & \text{if } i \neq j \end{cases}$$

3. Information Hiding: When you bias specific tokens, you change the effective "temperature" for those tokens, altering how information is distributed across the output.

The Attack's Information Recovery

The clever insight is that by strategically choosing which tokens to bias, you can create multiple "views" of the same underlying logit vector, each with different normalization constants. With enough views, you can solve for the original logits (up to translation).

This is why the attack needs:

• Multiple queries (to get different normalizations)
• A reference token (to fix the translation ambiguity)
• Careful bias selection (to ensure numerical stability)

The attack essentially exploits the fact that while softmax destroys some information, it preserves enough structure that the original logits can be reconstructed through careful measurement of how the outputs change under different biases.