Sketch-Guided Constrained Decoding for Boosting Blackbox Large Language Models without Logit Access (2024)

Abstract: Constrained decoding, a technique for enforcing constraints on language model outputs, offers a way to control text generation without retraining or architectural modifications. Its application is, however, typically restricted to models that give users access to next-token distributions (usually via softmax logits), which poses a limitation with blackbox large language models (LLMs). This paper introduces sketch-guided constrained decoding (SketchGCD), a novel approach to constrained decoding for blackbox LLMs, which operates without access to the logits of the blackbox LLM. SketchGCD utilizes a locally hosted auxiliary model to refine the output of an unconstrained blackbox LLM, effectively treating this initial output as a “sketch” for further elaboration. This approach is complementary to traditional logit-based techniques and enables the application of constrained decoding in settings where full model transparency is unavailable. We demonstrate the efficacy of SketchGCD through experiments in closed information extraction and constituency parsing, showing how it enhances the utility and flexibility of blackbox LLMs for complex NLP tasks.

## introduction large language models (llms) have seen a remarkable expansion in scope, being used for diverse tasks including tool interaction, sql translation, robotic navigation and item recommendations, where adherence to specific constraints is paramount @xcite @xcite @xcite . despite their versatility, llms often struggle with constraint adherence in few-shot scenarios, leading to outputs that violate task-specific requirements @xcite @xcite . figure 1 : overview of sketch-guided constrained decoding (sketchgcd). in the initial sketching phase, a blackbox llm generates a preliminary "sketch" answer without applying any constraints. then, in the constrained decoding phase, an auxiliary model, the constrained decoder, refines the sketch. the refined, final output respects the specified constraints by construction. constrained decoding offers a solution, restricting model outputs to respect predefined constraints without necessitating model retraining or architectural modifications @xcite @xcite @xcite . however, existing constrained decoding methods require access to the model's logits during inference, which is not always feasible in practice (cf. appendix a). since the most powerful llms tend to be commercial and blackbox @xcite , this has restricted the application of constrained decoding methods. ## experiments in our experimental setup, we evaluate the efficacy of sketchgcd by comparing it against two established baselines: (1) few-shot-prompted unconstrained decoding with powerful blackbox llms (eq. 1) and (2) few-shot-prompted constrained decoding with open-source llms (eq. 3). the sketchgcd method remains flexible and is agnostic to the exact implementation of constrained decoding. here we adopt the grammar constrained decoding framework of @xcite , but any other constraining method can be plugged in. in our evaluation, we distinguish between sequences that are valid (i.e., that satisfy the constraints) and those that are correct (i.e., those that are equal to the intended output for the given input). a valid output is a prerequisite for being correct, but it is not the sole criterion for correctness. ## conclusion so far, constrained decoding has been limited to open-source models that provide access to their logits during generation. overcoming this limitation, we propose sketch-guided constrained decoding (sketchgcd), a simple method for constrained decoding with blackbox llms that does not require access to next-token logits during generation. by using separate sketching and refinement phases, sketchgcd allows to benefit from the power of blackbox llms while still enforcing constraints. our work is complementary to existing methods for constrained decoding and can be used in conjunction with them. despite its simplicity, sketchgcd achieves strong performance on tasks exhibiting strong structural constraints, outperforming unconstrained generation by a large margin.