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

arXiv: https://arxiv.org/abs/2605.28001 · HTML: https://mlsanity.com/paper/2605.28001/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 10 references that are in the map.
- First posted on arXiv 27 May 2026.

## Builds on (most cited first, 6 of 6)

- [Red Teaming Language Models with Language Models](https://mlsanity.com/paper/2202.03286/) (2022)
- [Red Teaming Language Models to Reduce Harms: Methods, Scaling Behaviors, and Lessons Learned](https://mlsanity.com/paper/2209.07858/) (2022)
- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [Rainbow Teaming: Open-Ended Generation of Diverse Adversarial Prompts](https://mlsanity.com/paper/2402.16822/) (2024)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [On Provable Copyright Protection for Generative Models](https://mlsanity.com/paper/2302.10870/) (2023)

## Abstract (arXiv)

We empirically audit the k-NAF budget-accounting mechanism in Anchored Decoding using (i) a fixed, class-stratified workload (approximately 8,500 randomized executions across six prompt classes) and (ii) an adaptive prompt-search procedure targeting high proxy spend ratios. On the fixed workload, mean cumulative KL spend remains far below the sequence-level budgets K in {600, 1000}, and an empirical Bernstein-style proxy stays below K for every class; surface-overlap diagnostics (ROUGE-L and 5-gram Jaccard) are correspondingly small. Adaptive search increases the proxy spend ratio but does not produce clear budget exhaustion. On a held-out copyright-domain workload at k = 3, several prompts exhibit proxy ratios above 1 under early-stopped evaluations with small realized sample sizes; re-evaluating the same prompts with larger allocation reduces the proxy ratio to the range [0.26, 0.40] under comparable mean spend, consistent with proxy artifacts rather than per-trajectory budget failures.