Constrained Decoding with Speculative Lookaheads (2025)

Abstract: Constrained decoding with lookahead heuristics (CDLH) is a highly effective method for aligning LLM generations to human preferences. However, the extensive lookahead roll-out operations for each generated token makes CDLH prohibitively expensive, resulting in low adoption in practice. In contrast, common decoding strategies such as greedy decoding are extremely efficient, but achieve very low constraint satisfaction. We propose constrained decoding with speculative lookaheads (CDSL), a technique that significantly improves upon the inference efficiency of CDLH without experiencing the drastic performance reduction seen with greedy decoding. CDSL is motivated by the recently proposed idea of speculative decoding that uses a much smaller draft LLM for generation and a larger target LLM for verification. In CDSL, the draft model is used to generate lookaheads which is verified by a combination of target LLM and task-specific reward functions. This process accelerates decoding by reducing the computational burden while maintaining strong performance. We evaluate CDSL in two constraint decoding tasks with three LLM families and achieve 2.2x to 12.15x speedup over CDLH without significant performance reduction.

## introduction alignment of llms to human preferences is important for their general applicability. constrained decoding in large language models (llms) is an effective method as a post-training step to align llm generations to human preferences such as harmless text generation @xcite , faithful summarization @xcite , formatted generation, flow adhering planning @xcite , among other use 80.0 82.5 85.0 87.5 90.0 92.5 95.0 97.5 harmless text generation performance (%) cases. within constrained decoding methods, the "lookahead" heuristics-based approach (cdlh) has demonstrated the best performance across several tasks @xcite . cdlh examines the top k beams, generates d additional tokens as "lookahead" for each beam, scores them using taskspecific reward functions for constraint satisfaction, and selects the beam that maximizes constraint fulfillment while discarding the others. however, the computational expense of generating lookaheads makes this approach prohibitively costly in terms of runtime, limiting its practical applicability in real-world scenarios. speculative decoding (sd) is a recently proposed technique for improving the inference speed of llms @xcite . this approach employs a draft-then-verify strategy @xcite , utilizing a smaller and more efficient draft llm's generation to approximate the output of a larger target llm. at each step, the draft's output is validated by the target llm. in transformer-based llms, this validation is performed through a forward pass, which is less computationally intensive than autoregressively generating tokens. as a result, sd significantly reduces the inference time for the target llm while preserving generation quality. however, it should be noted that sd does not have any specific mechanism to align its generations with task-specific constraints. drawing inspiration from speculative decoding, in this work, we propose constrained decoding with speculative lookaheads (cdsl) to improve the inference time of constrained decoding algorithms. cdsl begins by autoregressively speculating the lookahead tokens using a small and efficient draft llm. speculated lookaheads are then validated by the larger target llm, to ensure that the output from the draft adheres to the same distribution as the target llm. to enforce constraints on generations, validated speculative lookaheads are also scored using a task specific reward function, which assesses their adherence to the required constraints. based on the feedback from the target llm and the reward function, we define a set of states and corresponding actions that determine whether to accept or reject the lookaheads. to demonstrate the effectiveness of the proposed approach we experiment with three llm families and two constraint-satisfaction tasks -constrained commonsense generation, commongen @xcite and harmless text generation, htg (anthropic hh-rlhf @xcite ). the cdlh method serves as an upperbound for constraint satisfaction performance and a baseline for runtime performance. similarly, greedy decoding serves as a runtime upper-bound and performance baseline. we observe that our proposed cdsl gives a practical middle-ground by significantly improving upon the inference efficiency of cdlh without experiencing drastic performance reduction often seen with greedy methods, as shown in figure 1 . concretely, cdsl delivers an inference speedup of 2.2× to 12.15× over cdlh, along with constraint satisfaction performance improvements of up to +10.1% points on htg and +20.9% points on commongen compared to greedy decoding. ## proposed algorithm in this section, we first propose a novel baseline that is simple yet effective, by optimizing the looakhead mechanism of cdlh with a smaller llm. then we propose our algorithm "constrained decoding with speculative lookaheads" which combines the paradigms of cdlh and speculative decoding. our approach leverages the strength of both paradigms (better alignment from constrained decoding and faster decoding from speculative decoding), leading to a powerful yet practical method. ## results and ablations in this section, we first describe the performance of our model compared to the baseline and skyline approaches. then, we perform an extensive ablation study and error analysis of our proposed approach. ## related work speculative decoding (sd) has emerged as a technique for reducing llm inference time with a faster small lm @xcite @xcite . different optimizations and variations have been further proposed on top of sd. for example, usage of a layerskipped lighter version of the target llm as a draft @xcite , using a segment of the model as draft @xcite , retrieval as draft @xcite , recurrent drafter @xcite , tree-based drafting @xcite , graph structured sd for managing more than one hypothesis @xcite , etc. other approaches includes incorporation of contrastive learning is sd @xcite , focusing on more effective tokens during sd @xcite , knowledge distillation in drafts for better acceptance @xcite , online sd @xcite , etc. another line of research focuses on scalability, robustness @xcite , and parallelism for sd @xcite @xcite . in a different paradigm, constrained decoding based approaches are used as an alignment technique for llms at post-training phase @xcite . the most effective approaches @xcite for constrained decoding rely on lookahead-based approaches @xcite . as a result, controlled generation @xcite @xcite with lookahead heuristic is prohibitively expensive in terms of runtime. in this paper, we combine the two paradigms, constrained decoding with lookahead heuristic and speculative decoding, with a goal to improve the runtime of such approaches while preserving the performance. ## conclusion we propose constrained decoding with speculative lookaheads, a novel algorithm that combines the principles of constrained decoding with lookahead heuristics and speculative decoding, in order to improve the runtime efficiency of constrained decoding approaches. our approach yields significant speedup over the constrained decoding with lookahead heuristics (cdlh) approach without major drop in performance and contributes to adaptability of such approaches in real-world use cases.