Research map / Large language models / Language, safety and interpretability
Approximately Aligned Decoding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Approximately Aligned Decoding (AprAD), which uses speculative-sampling prefix selection to backtrack after constraint violations, balancing distribution distortion against compute for error-free LLM generation.
Problem
Generating LLM outputs that avoid undesired content (error sets) either requires expensive resampling (rejection sampling, ASAp) or distorts the output distribution by amplifying improbable sequences (constrained decoding).
Approach
After an error is sampled, reuse the sampled prefix via speculative sampling's accept/reject step, comparing the adjusted distribution (with the error added to the banned set) against the current one, so that most of the prefix is kept while probability amplification is bounded per backtrack.
Key results
- On the simulated testbench, AprAD's KL-divergence is well below constrained generation (e.g., 0.0074 vs 0.0155 for AAA, CCC) at generation ratio ~1.01 versus ASAp's 1.04 for the same set.
- On lipograms with Mistral-7B, AprAD scores quality 4.52 vs 3.56 for constrained and 1.72 for ASAp, at generation ratio 4.20 vs ASAp's 321.00.
- On BigCodeBench with StarCoder2-15B, AprAD pass@1 is 0.26 vs 0.22 for constrained generation, matching ASAp (0.26) at generation ratio 1.08 vs 1.56.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AprAD instead of constrained generation | Simulated model · Simulated task, AAA | KL-divergence: 0.0075 -> 0.0046 | Helped |
| Use AprAD instead of ASAp | Simulated model · Simulated task, AAA | Generation ratio: 1.020 -> 1.004 | Helped |
| Use AprAD instead of constrained generation | Mistral-7B-Instruct-v0.2 · Lipograms | Quality: 3.56 $\pm$ 0.34 -> 4.52 $\pm$ 0.23 | Helped |
| Use AprAD instead of constrained generation | Mistral-7B-Instruct-v0.2 · Lipograms | Constraint intent: 2.32 $\pm$ 0.18 -> 2.84 $\pm$ 0.11 | Helped |
| Use AprAD instead of constrained generation | Mistral-7B-Instruct-v0.2 · Lipograms | Generation ratio: 1.00 $\pm$ 0.00 -> 4.20 $\pm$ 0.91 | Hurt |
| Use AprAD instead of constrained generation | Starcoder2-15B · BigCodeBench, divergent-output tasks | Pass@1: 0.22 $\pm$ 0.01 -> 0.26 $\pm$ 0.01 | Helped |
| Use AprAD instead of ASAp | Starcoder2-15B · BigCodeBench, divergent-output tasks | Generation ratio: 1.56 $\pm$ 0.12 -> 1.08 $\pm$ 0.01 | Helped |
| Use AprAD instead of ASAp | Starcoder2-7B · BigCodeBench, divergent-output tasks | Pass@1: 0.15 $\pm$ 0.01 -> 0.14 $\pm$ 0.01 | Hurt |
| Use AprAD instead of constrained generation | Starcoder2-7B · BigCodeBench, divergent-output tasks | !NameErr@1: 0.89 $\pm$ 0.01 -> 0.95 $\pm$ 0.01 | Helped |
Surprising findings
- ASAp's generation ratio is extremely high on lipograms (321x), making it impractical within the 2000-invocation budget despite exact sampling in theory.
Limitations
- Still exhibits some probability amplification, bounded per backtrack but not eliminated.
- Additional overhead compared with constrained generation; on very dense error sets constrained generation or a tempered variant may be needed.
- Efficiency measured by generation ratio rather than wall-clock time.
Experimental setup
Datasets: BigCodeBench v0.1
Benchmarks: BigCodeBench v0.1 Lipogram (excluded vowels) tasks Simulated known-distribution testbench
Metrics: KL-divergence generation ratio quality (1-5) constraint intent (1-3) pass@1 pass@5 NameError-free rate
Baselines: Constrained generation ASAp Rejection sampling Unconstrained generation
Builds on: speculative sampling ASAp constrained generation
Closest papers by meaning
- Grammar-Aligned Decoding (NeurIPS 2024 · similarity 0.90)
- Fast Best-of-N Decoding via Speculative Rejection (NeurIPS 2024 · similarity 0.90)
- GRIFFIN: Effective Token Alignment for Faster Speculative Decoding (NeurIPS 2025 · similarity 0.90)
- Optimized Multi-Token Joint Decoding With Auxiliary Model for LLM Inference (ICLR 2025 · similarity 0.89)
- A Theoretical Perspective for Speculative Decoding Algorithm (NeurIPS 2024 · similarity 0.89)
- Judge Decoding: Faster Speculative Sampling Requires Going Beyond Model Alignment (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.