Research map / Large language models / Reasoning and chain of thought
On the Query Complexity of Verifier-Assisted Language Generation
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.
Develops a theoretical query-complexity framework for verifier-assisted constrained generation and proposes tokenwise rejection sampling with backtracking, which reduces CodeLlama/Dyck generation errors while cutting queries.
Problem
Verifier-assisted inference-time generation (e.g. best-of-n, process-verifier guided decoding) lacks a principled understanding of when verifiers make constrained generation tractable and how to design query-efficient algorithms.
Approach
Formalizes constrained generation with an autoregressive oracle and a process verifier that decides prefix completability, shows hardness without a verifier versus easy generation with one, and proposes tokenwise rejection sampling augmented with backtracking (erase last B tokens, regenerate with argmax, up to Q times).
Key results
- On error-inducing Dyck prefixes, B=8 backtracking with nucleus sampling raises accuracy from 0.331 to 0.790.
- On CodeLlama test-case generation, tokenwise rejection sampling with backtracking (Q=4, B=4) reaches Acc_distinct 0.714 vs 0.660 for the best nucleus+temperature baseline at similar query cost (~39.4k vs ~38.2k).
- On unseen OOD Dyck prompts, errors drop from 240 to 179 with top_p=0.9 and from 462 to 200 with top_p=1.0 using Q=4, B=4.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add tokenwise backtracking with Q=4, B=4 and a trained verifier | CodeLlama-7B test-case generation · Python append test cases | Acc_distinct: 0.660 ± 0.042 -> 0.714 ± 0.011 | Helped |
| Add tokenwise backtracking with Q=4, B=4 | Dyck-trained Transformer · Dyck OOD unseen prompts, top_p=0.9 | completion errors: 240.0 ± 5.177 -> 179.4 ± 1.020 | Helped |
| Add tokenwise backtracking with Q=4, B=4 | Dyck-trained Transformer · Dyck OOD unseen prompts, top_p=1.0 | completion errors: 461.8 ± 8.304 -> 200.0 ± 3.225 | Helped |
| Use a perfect process verifier with tokenwise rejection sampling instead of full-string rejection sampling | Constrained generation of 0^D from uniform binary strings · Uniform binary strings; target 0^D | expected oracle calls: 2^D D -> 2 D | Helped |
| Use layer 27 verifier representations instead of layer 31 (ablation) | Tokenwise rejection sampling with backtracking on CodeLlama-7B · Python append test cases | Acc_distinct: 0.688 ± 0.028 -> 0.714 ± 0.011 | Helped |
| Use error prediction threshold 0.1 instead of 0.5 (ablation) | Tokenwise rejection sampling with backtracking on CodeLlama-7B · Python append test cases, top_p=0.95 and temperature=1.0 | Acc_distinct: 0.676 ± 0.019 -> 0.714 ± 0.011 | Helped |
| Use a 1-layer verifier instead of a 4-layer verifier (ablation) | Tokenwise rejection sampling with backtracking on CodeLlama-7B · Python append test cases | Acc_distinct: 0.699 ± 0.038 -> 0.714 ± 0.011 | Helped |
| Replace the trained verifier with a random verifier (ablation) | Tokenwise rejection sampling with backtracking on CodeLlama-7B · Python append test cases | Acc_distinct: 0.714 ± 0.011 -> 0.663 ± 0.027 | Hurt |
| Increase backtrack quota Q from 4 to 10 (ablation) | Tokenwise rejection sampling with a trained verifier on CodeLlama-7B · Python append test cases | Acc_distinct: 0.714 ± 0.011 -> 0.692 ± 0.025 | Hurt |
| Increase backtrack stride B from 4 to 10 (ablation) | Tokenwise rejection sampling with a trained verifier on CodeLlama-7B · Python append test cases | Acc_distinct: 0.714 ± 0.011 -> 0.622 ± 0.046 | Hurt |
| Increase backtrack stride B from 0 to 8 at an error-inducing prefix (ablation) | Dyck-trained Transformer · Dyck OOD error-inducing prefixes | accuracy: 0.331 -> 0.790 | Helped |
Surprising findings
- Using a much larger backtrack quota or stride (Q or B = 10) did not improve and sometimes decreased accuracy, attributed to the imperfect generator.
- Naive tokenwise rejection sampling with a process verifier does not sample from the restricted distribution, reweighting valid strings non-uniformly.
Limitations
- Query complexity is used as the efficiency metric; wall-clock time and batched inference are not analyzed.
- Verifier is a single linear layer on frozen features; the test-case task uses a single function (list append) and a rule-based evaluator.
- Tokenwise rejection sampling does not target the restricted distribution, so outputs may not be calibrated.
Experimental setup
Datasets: synthetic Dyck grammar data generated Python append test-case prompts
Benchmarks: Dyck OOD prompts (in-house) Python list append test-case generation (in-house)
Metrics: accuracy distinct correct test cases (Acc_distinct) query complexity diversity
Baselines: rejection sampling nucleus sampling temperature scaling block best-of-n greedy argmax decoding
Builds on: best-of-n nucleus sampling rejection sampling process reward models
Closest papers by meaning
- Variation in Verification: Understanding Verification Dynamics in Large Language Models (ICLR 2026 · similarity 0.89)
- Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking (ICLR 2026 · similarity 0.88)
- Generative Verifiers: Reward Modeling as Next-Token Prediction (ICLR 2025 · similarity 0.88)
- Guaranteed Generation from Large Language Models (ICLR 2025 · similarity 0.87)
- CRANE: Reasoning with constrained LLM generation (ICML 2025 · similarity 0.86)
- Learning How Hard to Think: Input-Adaptive Allocation of LM Computation (ICLR 2025 · similarity 0.86)
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.