An Empirical Audit of k-NAF Budget Accounting for Anchored Decoding

This paper empirically audits the k-NAF budget-accounting mechanism in Anchored Decoding across fixed and adaptive workloads, finding that cumulative KL spend consistently remains well below sequence-level budgets and that instances of apparent budget exhaustion are attributable to proxy artifacts rather than actual mechanism failures.

The Gist

Imagine you have a very strict librarian (the "Safe Model") and a creative, slightly mischievous storyteller (the "Risky Model"). The storyteller wants to tell a story, but there's a rule: they can't copy too much from the librarian's book. If they get too close to the librarian's exact words, they are "spending" their budget.

The paper you provided is an audit (a detailed check-up) of a specific rulebook called "Anchored Decoding" (specifically the k-NAF system) designed to keep the storyteller in line. The goal was to see if this rulebook actually works as promised when the storyteller is pushed to their limits.

Here is the breakdown of what the researchers found, using simple analogies:

1. The Setup: The "Spending" Rule

Think of the storyteller's budget as a fuel tank.

• The Limit: The rulebook says, "You can only spend a total of K units of fuel on your entire story."
• The Meter: The system tries to track how much fuel is used at every single word (token) the storyteller writes.
• The Goal: Ensure the storyteller never runs out of fuel before the story is done, and more importantly, never accidentally "steal" (copy) too much from the librarian's book.

2. The First Test: The "Fixed Workload" (The Daily Routine)

The researchers first asked the storyteller to write about 8,500 different stories across six different genres (like "neutral facts," "creative fiction," or "attack prompts"). They didn't try to trick the system; they just wanted to see how it behaved normally.

• The Result: The storyteller was incredibly conservative. They only used about 15% to 30% of their total fuel tank.
• The Analogy: It's like driving a car with a 100-gallon tank, but you only ever drive 20 miles before stopping. You have a massive amount of "slack" (extra room).
• The Check: They also checked if the stories sounded like the librarian's book. The overlap was tiny (like finding two identical grains of sand in a beach).
• Conclusion: In normal, everyday use, the system works perfectly and is very safe.

3. The Second Test: The "Adversarial Search" (The Stress Test)

Next, the researchers tried to "break" the system. They used a smart computer program (an optimizer) to generate thousands of tricky prompts, trying to find the one story that would force the storyteller to use up the entire fuel tank. They wanted to see if they could trick the system into "overspending."

• The Result: They got very close! They found prompts where the "spending ratio" looked like it hit 98.8% of the limit.
• The "Violation": In a few specific cases, the math said the storyteller had spent more than 100% of their fuel (a ratio greater than 1). This looked like a failure.

4. The Twist: The "Small Sample" Illusion

Here is the most important part of the paper. The researchers realized the "violation" wasn't because the storyteller actually broke the rules. It was a mathematical illusion caused by looking at too little data.

• The Analogy: Imagine you are trying to guess the average height of a basketball team.
  • Scenario A: You measure 4 players. One is a bit taller than average. Because your sample is so small, your "safety margin" (a statistical buffer) is huge. Your calculation might say, "The average is 7 feet!" even if the real average is 6'5".
  • Scenario B: You measure 20 players. The average settles down to the real number, 6'5".
• What Happened in the Paper:
  • The system stopped evaluating the tricky prompts after only 4 stories (a small sample size).
  • Because the sample was so small, the "safety margin" in the math formula became huge, making the spending look like it exceeded the limit (a "violation").
  • When the researchers forced the system to evaluate those same prompts with 20 stories (a larger sample), the "violation" disappeared. The spending ratio dropped back down to a safe 26%–40%.

5. The Final Verdict

The paper concludes with two main takeaways:

1. The System Works: The "Anchored Decoding" rulebook is doing its job. The storyteller isn't actually burning through the fuel tank or copying the librarian's book. In fact, they are being very cautious.
2. The Math Needs a Tune-Up: The tool used to measure the spending (the "proxy") gets confused when it doesn't have enough data. It sounds the alarm too loudly when it only sees a few examples.

The Recommendation:
The authors suggest that if you are testing this system, you shouldn't stop after just 4 stories. You need to wait until you have at least 20 stories to get a clear picture. If you do that, the "false alarms" go away, and you can see that the system is actually very safe.

In short: The "guard dog" (the system) is doing a great job. The "alarm system" (the math tool) just needs to wait for more evidence before it starts barking.

Technical Summary

Technical Summary: An Empirical Audit of k-NAF Budget Accounting for Anchored Decoding

Problem Statement
This paper addresses the empirical validity of Anchored Decoding, a mechanism designed to enforce "near access-freeness" (k-NAF) in generative models. The core objective of Anchored Decoding is to limit the divergence between a controlled decoder (trained on potentially copyrighted data) and a designated safe reference model (trained without such data). This is operationalized by enforcing a sequence-level Kullback-Leibler (KL) budget, $K = kT_{max}$, through a composition of local, per-token constraints.

The central question investigated is whether a concrete implementation of this mechanism actually realizes the intended accounting behavior under realistic workloads and adversarial stress. Specifically, the authors ask if the decoder can be forced to exhaust its budget or if the accounting mechanism (specifically the empirical Bernstein-style proxy used to estimate spend) behaves reliably under small-sample conditions.

Methodology
The audit employs a two-stage design mirroring the tester/finder separation used in differential privacy auditing:

1. Stage 1: Fixed-Workload Diagnostic Evaluation

   • Scope: Approximately 8,500 randomized executions across six prompt classes (neutral, validation, test, attack training, factual, creative) using two values of the per-token budget parameter $k \in \{3, 5\}$ (with $T_{max}=200$).
   • Metrics: The study logs per-step KL expenditure and aggregates it to compute a cumulative spend proxy, UEBB (Upper Empirical Bernstein Bound). This proxy combines the sample mean, a variance term, and a deterministic term dependent on the effective range ($R_{eff}$) and sample size ($M$).
   • Controls: Executions use common-random-numbers batching to ensure protocol-dependent diagnostics. Overlap diagnostics (ROUGE-L and 5-gram Jaccard) are computed against available references to measure surface-form copying.

2. Stage 2: Adaptive Adversarial Search

   • Goal: To maximize the proxy spend ratio $\rho = \text{UEBB} / B_{eff}$, where $B_{eff}$ is the effective remaining budget.
   • Process: An optimizer model proposes candidate prompts, which are ranked by a learned surrogate (MLP over Sentence-T5 embeddings + TF-IDF). The search utilizes multi-fidelity evaluation: prompts start with a minimum allocation of $N=4$ trajectories. A "survivor test" determines if prompts are "topped up" to larger allocations (up to $N=20$ or $30$) based on whether their current UEBB remains below a threshold of the budget.
   • Stress Testing: The search runs for four generations to identify prompts that push the proxy ratio close to or above 1.

Key Contributions

1. Fixed-Workload Audit: Demonstrates that under a fixed, class-stratified workload, the mean cumulative KL spend remains substantially below the configured sequence-level budgets ($K \in \{600, 1000\}$), typically occupying only $\approx 30\%$ of the budget. The empirical Bernstein proxy stays below $K$ for all classes, and surface-overlap metrics are low.
2. Adaptive Search Results: The search procedure successfully elevates the proxy spend ratio to $\rho \approx 0.988$ at $k=3$ and $\rho \approx 0.760$ at $k=5$. However, the search does not produce prompts that clearly exhaust the budget in a per-trajectory sense.
3. Diagnostic of Proxy Artifacts: The paper identifies that apparent "violations" (where $\rho > 1$) observed in a held-out copyright-domain workload at $k=3$ are artifacts of the empirical Bernstein proxy at small sample sizes ($N=4$).
   • At $N=4$, the deterministic term in the Bernstein bound dominates the calculation, inflating the UEBB estimate even when the mean spend is low.
   • Re-evaluating these same prompts with larger allocations ($N=20$) or at a higher budget ($k=5$) collapses the ratio to $\rho \in [0.26, 0.40]$, confirming the decoder did not actually exceed its budget.

Results

• Budget Slack: In the fixed workload, the mean spend is consistently $\lesssim 0.3K$. Even with a conservative range parameter, the UEBB remains below $K$.
• Surface Overlap: ROUGE-L scores are $\le 0.20$ and 5-gram Jaccard scores are $\le 0.05$, indicating limited verbatim copying in the fixed workload.
• The "Violation" Artifact: Three prompts in the held-out set showed $\rho > 1$ at $k=3$. Analysis revealed:
  • Mean spend was $\approx 180-200$ (well below $K=600$).
  • The deterministic Bernstein term alone accounted for 71–97% of the effective budget at $N=4$.
  • Increasing $N$ to 20 or doubling $K$ to 1000 ($k=5$) resolved the "violation," yielding $\rho < 0.5$.
• Search Limitations: The adversarial search did not significantly improve upon the initial seed prompts. The archive maximum for $k=3$ was set in the first generation and remained static, suggesting the surrogate was saturated and the search was driven by seed quality rather than optimization.

Significance and Claims
The paper concludes that the Anchored Decoding implementation exhibits substantial slack relative to its configured budgets and does not fail under the tested conditions. The primary significance of the work lies in its diagnostic of the audit methodology itself:

• Proxy vs. Mechanism: The study distinguishes between the behavior of the decoding mechanism and the behavior of the statistical proxy used to audit it. The "violations" were not evidence of budget exhaustion by the decoder but rather a failure of the proxy to be tight under small-sample allocation ($N=4$).
• Protocol Recommendations: The authors propose specific protocol modifications to prevent such artifacts in future audits:
  1. Enforce a minimum sample size floor (e.g., $N \ge 20$) for prompts with high preliminary spend ratios.
  2. Report the width of the Bernstein bound alongside the point estimate to indicate uncertainty.
  3. Use data-dependent range parameters ($R_{eff}$) rather than conservative worst-case bounds.
  4. Ensure capability matching between the safe anchor and the risky target to avoid conflating capability gaps with memorization divergence.

The authors explicitly state this is an empirical audit, not a formal verification, and that the results highlight the necessity of careful proxy calibration when evaluating safety mechanisms under adaptive sampling.