Prompt Sketching for Large Language Models

We thank the reviewer for their insightful questions, which we address below, and are encouraged to hear that they find prompt sketches to be a highly interesting idea.

Q: How does Sketching with BeamVar/Var relate to Self-Consistency and can you add it as a baseline?
The self-consistency [1] decoding strategy improves LLM reasoning by greedily sampling multiple (chain-of-thought) reasoning paths and aggregating the resulting final answers, by (unweighted or weighted) majority vote. In contrast, sketch-aware decoders generate answers token-by-token or thought-by-thought (not path by path), can branch on the top-n alternatives at each step, and do not aggregate the final results. Instead, a single sequence is chosen as the one answer to an input, considering the model likelihood of the underlying token sequence only (no aggregation or majority voting). With this, self-consistency and sketching can be considered orthogonal approaches and could even be applied jointly, i.e., sample-decode a sketch multiple times and aggregate the results.
We added a comparison of sketching and self-consistency to the revised manuscript (Appendix D). For this comparison, we choose $n=2$/$n=4$ samples for self-consistency, as this aligns with the computational overhead of our branching decoders BeamVar/Var with $n=2$. However, our results show that, in many cases, self-consistency with such a low number of samples does not even outperform argmax CoT which is the main baseline we outcompete with sketching. This aligns with the self-consistency paper itself [1], which reports that around 5-20 consistency samples are required to outperform simple argmax CoT. We thus find that within this compute budget ($n=2$/$n=4$), argmax CoT and thus sketching both outperform self-consistency decoding.

Q: Is CoT+BeamVar a better baseline for Sketching+BeamVar?
Comparing CoT+BeamVar with Sketching+BeamVar, we observe an accuracy increase of $8-12$ with OpenAI models for AQuA, StrategyQA, Tracking Shuffled Objects and Matrix Shapes. On these tasks, CoT+BeamVar is thus clearly outperformed by sketching. For Date Understanding, Multistep Arithmetic, GSM8K on the other hand we indeed observe comparable performance with sketching+BeamVar. This can be explained by the two-part nature of the zero-shot CoT formulation [2] (first decoding reasoning and then the final answer). Applying a sketch-aware decoder like BeamVar to this kind of prompt already boosts performance, as BeamVar can exploit this two-variable structure. For a baseline comparison (no interaction between multiple variables), we thus have to look at Beam+CoT (one column to the left). There, we find that Multistep Arithmetic and GSM8K again perform worse. Only for Date Understanding do sketching and sketch-aware decoders not appear to bring particular benefit for OpenAI models, which is reflected in our overall summary: sketching outperforms sequential prompting on 7/8 tasks.

Q: Can you extend your evaluation of additional applications and further demonstrate the effectiveness of sketching in this context?
We have scaled our experiments on the additional applications (Section 4.2) by a factor of 10 and now evaluate a larger number of samples (100 samples per model/decoder configuration). We report the results in the updated manuscript. Overall, we observe comparable trends to before, i.e., sketch-aware decoders clearly show the ability to backtrack in Sudoku solving and solve the Dungeon Escape tasks more efficiently (fewer steps), when compared to naive argmax decoding. We have also added an additional experiment on TextWorld [3] exploration, which leverages our decoders for LLM-guided world exploration. Again, we find that sketch-aware decoders clearly outperform greedy argmax decoding, completing TextWorld quests of different lengths with 20% fewer steps. We further discuss our TextWorld results in Appendix B.2.

References
[1] Self-consistency improves chain of thought reasoning in language models, X. Wang et al., ICLR’23
[2] Large language models are zero-shot reasoners, K. Takeshi et al., NeurIPS’22
[3] Textworld: A learning environment for text-based games, M.-A. Côté et al., IJCAI’18

We thank the reviewer for their insightful questions, which we address below, and are encouraged to hear that they find prompt sketches to be an intuitive format for chained queries.

Q: Can you comment on the overhead of writing sketches as opposed to prompts?
Similar to prompt engineering, templates have to be constructed, tested, and debugged with example data to ensure the best performance. With current models, however, this prompt/template engineering effort cannot be avoided, as a single input/sentence is typically not sufficient to ensure that the model conforms to very specific and precise requirements. In this context, we consider sketching a more controlled form of prompting, where the output format is guaranteed and not up to prompt engineering and randomness in the generation process. Nonetheless, we agree that a human effort has to be made to properly prompt, template, and use LLMs. See also Section 4.3 for more discussion of this aspect.

Q: Is prompt-sketching less effective with smaller LLMs?
We note that even with a smaller Llama-2 Chat model (13B parameters), sketching outperforms sequential prompting on 6/8 reasoning tasks while exhibiting even greater performance gains than for large OpenAI models (up to 8% vs. up to 4%). However, as we acknowledge in our evaluation, Llama-2 seems incapable of solving the Matrix Shape and AQuA reasoning tasks, irrespective of the prompting/sketching scheme, leading to inconclusive results on these datasets. Other tasks are not as strongly affected and show comparable trends to the OpenAI results. Further, we demonstrate in Appendix B.1 that sketching can be very effective with smaller models, for instance when asking a model to produce valid JSON output: For the small text-curie-001, sketching allows us to guarantee valid JSON output, whereas the same model with a corresponding prompts, is unable to produce any valid JSON at all.

Potentially, our description in Section 4 was unclear in this regard. We have updated it in the rebuttal revision to make the above points more clear.

Q: Does the sample size in the evaluation impact the credibility of the results?
We understand your concerns regarding sample size and statistical significance for the OpenAI-specific part of our evaluation. Unfortunately, we cannot scale our OpenAI experiments further, due to cost constraints ($4000 for the results at the current scale). However, we have expanded our Llama-2-based experiments (Table 2) to include all decoder/dataset configurations and for 10 times as many samples as in the OpenAI experiments (1000 per dataset, or the full datasets in many cases). We also provide confidence intervals for the Llama results in the new appendix Table 8. In this much larger-scale Llama-2 setting, we observe comparable trends to the smaller-scale OpenAI experiment: Across tasks, sketching improves overall reasoning performance when compared to sequential prompting, while sketch-aware decoders can provide further gains in exchange for higher computational cost.

Q: How does the presented approach differ from Guidance?
Indeed, practical tools like Guidance also enable a form of stop-and-go inference, which can be seen as a simple form of sketching. However, Guidance is an ad-hoc approach, where templates are simply decoded using multiple isolated LLM calls. In contrast, sketching theoretically anchors this approach as a multi-part sequence decoding problem, enabling sketch-aware decoders. Further, prior work (including Guidance) does not provide insights on whether this form of structural guidance positively impacts model reasoning capabilities. This is evaluated as the argmax version of prompt sketching. Our experimental results are thus also of interest to Guidance-like frameworks, as we show that structural guidance during inference can indeed improve reasoning capabilities, beyond syntax and structure. To the best of our knowledge, this has not been shown before and therefore improves the understanding of simple stop-and-go inference in general. We have updated the introduction of the paper to better reflect this.

We thank the reviewer for their insightful questions, which we address below, and are encouraged to hear that they find prompt sketches to be an intuitive format for chained queries.

Q: Can you clarify the motivation for sketching and provide failure modes of existing models/decoding methods?
As pointed out by the reviewer, template-guided decoding can also be implemented by simply showing the LLM a template and asking it to produce a corresponding response. However, there are several limitations and failure modes with this approach:

• Instruction Following Capabilities: Only big and powerful models are currently capable of this kind of instruction-following (e.g., see how text-curie-001 fails for this kind of task in Table 3, Sudoku). In contrast, sketching also works with small models, which may not understand the template, but can still produce useful completions for individual template variables.
• Prompt Size: Including large templates fully in the prompt will greatly increase the number of required tokens, possibly even exceeding the context window of the model. Further, LLM retrieval across large inputs remains difficult, which can lead to deviations from the provided template. In contrast, sketching guides the model through the template, step by step, without increasing the total number of tokens or requiring long-range retrieval.
• Accuracy, Reliability, and Automation: Instruction-following models are still not perfect, which means templates may be violated and not followed strictly. In contrast, sketching provides a 100% guarantee that the template will be adhered to. This is crucial in automated settings, where the LLM’s output format must always be correct to enable processing by other systems that expect a specific format (e.g., function calling).
• Dynamic Templates and Interactive Environment: In some cases, providing the full template may also not be possible, as it may not be known fully ahead of time. For instance, templates may be dynamic, e.g., multiple repetitions of some template part, until a certain variable value is produced. Models can be instructed to respect such constraints, but this kind of prompting ultimately remains unreliable while sketching can enforce these properties strictly (cf. sketched CoT in the paper). Further, sketching is also applicable to interactive settings, where the template depends on and reacts to model output. For instance, in Table 3 we experimented with Dungeon-style graph traversal (Table 3), and in the updated revision, we added an additional experiment on TextWorld exploration.

Q: How exactly do BeamVar/Var address these failure modes (with $n=2$)?
As pointed out above, sketching alone already greatly alleviates these failure modes as it leads to strict adherence to the template and allows for scripted follow-up. Sketch-aware decoders (BeamVar/Var) additionally allow us to jointly score multiple variables (while standard decoders only allow the last variable to be scored conditioned on all preceding ones). This enables picking variables based on later sequences in the template, which is particularly important in dynamic environments where the template text depends on the value of prior variables. While modern RLHF models are very strong and typically assign high probabilities to the top-1 token, a small beam width of n=2, can already be useful to track an alternative hypothesis when ambiguities arise (demonstrated by our experiments on reasoning tasks). For our more advanced experiments with other applications (cf. Table 3), we apply BeamVar and Var with higher beam width (n=5 and n=3 respectively), as clarified in the revised draft, which enables the exploration of a broader hypotheses space.

Q: Why are you focusing on relatively simple formatting constraints?
We chose to focus on simple sketches, to examine whether structural support can improve model reasoning capabilities at all. Indeed, more complex or even grammar-guided approaches are possible, however, the design space of such sketches/reasoning grammars is very large and requires significant prompt engineering. In contrast, the main goal of this research is to establish foundational insight on whether structural guidance of the LLM reasoning process can improve its capabilities at all. Nonetheless, our sketching framework and decoders are general and capable of more complicated forms of template-guided inference, setting up future work to explore this direction.

We thank the reviewer for their encouraging response (clear motivation, thorough empirical study, useful for various tasks) and insightful observations and reply to their queries below.

Q: Can you comment on the effectiveness of sketching/sketch-aware decoders with different tasks and models, and how it compares to argmax+CoT?
We consider the contribution of our experimental results to be twofold:

• We demonstrate that template-guided inference via simple argmax-decoded sketches (stop-and-go) and comparatively simple structural templates can already improve task accuracy on reasoning tasks (OpenAI: 7/8, Llama-2: 6/8) significantly (4% and 8% respectively). To the best of our knowledge, this has not been demonstrated before, as existing work on template-guided inference does not discuss the impact on reasoning performance. We thus, for the first time, empirically validate the effectiveness of template-guided (stop-and-go) inference on reasoning tasks, using our sketching framework. Computationally, argmax sketching is cheaper than sequential decoding for the same output (e.g., argmax+CoT), as in sketching/stop-and-go, the model does not have to autoregressively process fixed template parts (assuming sufficient model access and key-value caching). In comparison, simple sketching thus provides accuracy improvements without necessarily incurring any computational overhead (potentially even reducing it).
• We also demonstrate that while argmax sketching/stop-and-go inference can be effective, sketch-aware decoding brings even further improvements. These decoders incur computational overhead, but, as with traditional beam search, can be worth the additional compute if downstream performance is absolutely crucial. Of course, in practice this trade-off depends entirely on the concrete use case, compute budget, and user requirements.

Q: Can you extend your evaluation of additional applications and further demonstrate the effectiveness of sketching in this context?
We have scaled our experiments regarding additional applications by a factor of 10, and now evaluate a larger number of samples (100 samples per model/decoder configuration). We report the results in the updated manuscript in Table 3. Overall, we observe comparable trends to before, i.e., sketch-aware decoders clearly show the ability to backtrack in Sudoku solving and solve the Dungeon Escape tasks more efficiently (fewer steps). We have also added an additional experiment on TextWorld [1] exploration (Table 3), which leverages our decoders for LLM-guided world exploration. Again, we find that sketch-aware decoders clearly outperform greedy argmax decoding, completing TextWorld quests of different lengths with ~20% fewer steps. We discuss our TextWorld result in appendix B.2.

Q: How is custom decoding possible with the OpenAI API?
The proposed decoders only require rather minimal support by the API/model. In particular, we require the possibility to extend all of the sequences in the beam and obtain logprobs for these sequences for at least their top $n$ continuations. For the OpenAI Completion API models we use in the paper, these capabilities are available.

Q: How does sketching perform when combined with few-shot prompting?
Sketching and few-shot prompting are orthogonal strategies, i.e., can be applied independently and jointly. We provide results on combining both in Appendix C.1. Overall, we find that few-shot prompting improves performance across the board, however, sketching still outcompetes sequential prompting, and in some cases zero-shot sketching even outperforms two-shot sequential prompting, suggesting that sketching can even serve as a replacement for few-shot demonstrations. We hope to have been able to address all the reviewers’ concerns, are happy to answer any follow-up questions they might have, and are looking forward to their reply.

References
[1] Textworld: A learning environment for text-based games, M.-A. Côté et al., IJCAI’18