# Sketch-Guided Constrained Decoding for
Boosting Blackbox Large Language Models without Logit Access

Saibo Geng, Berkay Döner, Chris Wendler, Martin Josifoski, Robert West
EPFL
{saibo.geng, berkay.doner, chris.wendler, martin.josifoski,
<EMAIL_ADDRESS>
###### 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 (SGCD), a
novel approach to constrained decoding for blackbox LLMs, which operates
without access to the logits of the blackbox LLM. SGCD 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
SGCD through experiments in closed information extraction and constituency
parsing, showing how it enhances the utility and flexibility of blackbox LLMs
for complex NLP tasks.111We will release the code and data upon publication.

##  1 Introduction

Figure 1: Overview of sketch-guided constrained decoding (SGCD). In the
initial sketching phase, a blackbox LLM generates a preliminary “sketch”
answer without applying any constraints. Then, in the constrained generation
phase, an auxiliary model, the constrained generator, refines the sketch. The
refined, final output respects the specified constraints by construction.

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 (Bubeck et al., 2023; Schick et al., 2023; Poesia et al., 2022;
Shah et al., 2022; Zhang et al., 2023; Hua et al., 2023). Despite their
versatility, LLMs often struggle with constraint adherence in few-shot
scenarios, leading to outputs that violate task-specific requirements (Chen
and Wan, 2023; Agrawal et al., 2023; Huang et al., 2023).

Constrained decoding offers a solution, restricting model outputs to respect
predefined constraints without necessitating model retraining or architectural
modifications (Poesia et al., 2022; Shin et al., 2021; Beurer-Kellner et al.,
2023; Scholak et al., 2021; Geng et al., 2023). 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 (Lee et al., 2023), this has
restricted the application of constrained decoding methods.

Contributions. In response, we present sketch-guided constrained decoding
(SGCD), which bypasses the need for direct logit access. SGCD uses a locally
hosted auxiliary model to refine the outputs of a blackbox LLM while
respecting the specified constraints. We validate our method on closed
information extraction and constituency parsing, two challenging NLP tasks
that require the model to generate highly structured and grounded outputs. Our
experiments show that SGCD significantly boosts the performance of LLMs and
beats previous approaches by a wide margin.

##  2 Method

SGCD splits the constrained decoding task into two distinct phases: sketching
and constrained generation.

During sketching, a sketcher—a powerful blackbox LLM denoted as
$P_{\text{sk}}$—is employed. It interprets an instruction $I$ alongside a set
of demonstration pairs $D=\\{(x^{i},y^{i})\\}_{i=1}^{n}$, producing a
preliminary draft $y^{*}$ via unconstrained decoding:

$\displaystyle y^{*}\approx\operatorname*{arg\,max}_{y\in
S}P_{\text{sk}}(y\,|\,I,D,x),$ (1)

where $S$ is the set of all possible sequences.

Constrained generation is done by a constrained generator, a smaller-scale,
locally hosted LLM $P_{\text{cg}}$. Given an instruction $I_{\text{cg}}$, a
set of input–sketch–output demonstrations
$D_{\text{cg}}=\\{(x^{i},y^{i},z^{i})\\}_{i=1}^{n}$, the original input $x$,
and the sketch $y^{*}$, it refines $y^{*}$ into

$z^{*}\approx\operatorname*{arg\,max}_{z\in S\cap
C}P_{\text{cg}}(z\,|\,I_{\text{cg}},D_{\text{cg}},x,y^{*}),$ (2)

subject to constraints $C$. (Optionally, $x$ and $x^{i}$ may be omitted, with
loss of information.)

The sketcher’s output $y^{*}$ is typically of high quality, encapsulating the
necessary information for the constrained generator to produce the final
sequence $z^{*}$ that adheres to the constraints $C$. Given the quality of
$y^{*}$, the constrained generator can be implemented using a much smaller
model, as its primary task is to rewrite the sketch $y^{*}$ with the help of
constrained decoding, thus facilitating deployment on standard consumer-grade
hardware.

On the contrary, classical, direct few-shot prompting with constrained
decoding would usually require a larger constrained generator $P_{\text{cg}}$
to be run locally, in order to find

$w^{*}\approx\operatorname*{arg\,max}_{w\in S\cap
C}P_{\text{cg}}(w\,|\,I,D,x).$ (3)

Another basic alternative, unconstrained few-shot prompting (Brown et al.,
2020), yields $y^{*}$ as the end product.

SGCD builds on the expectation that the constrained refined output $z^{*}$
should be at least as good as both $y^{*}$ (as $z^{*}$ respects the
constraints) and $w^{*}$ (as $P_{\text{sk}}$ is a more powerful LLM than
$P_{\text{cg}}$).

##  3 Experiments

| Wiki-NRE | SynthIE-text
---|---|---
| Precision | Recall | F1 | Precision | Recall | F1
_With logit access_ |  |  |  |
LLaMA-2-7B + CD | 31.7± 2.7 | 36.8± 2.9 | 31.9± 2.5 | 36.6± 2.3 | 29.4± 2.0 | 31.2± 2.0
LLaMA-2-13B + CD | 31.4± 2.6 | 40.7± 3.0 | 33.1± 2.5 | 38.9± 2.4 | 32.6± 2.1 | 33.6± 2.1
_Without logit access_ |  |  |  |
GPT4 | 43.2± 2.7 | 47.2±3.0 | 42.8± 2.6 | 46.8± 2.3 | 45.3± 2.2 | 45.8± 2.2
GPT4 + SGCD | 56.9± 3.2 ($\uparrow$13.7) | 47.4± 2.9 ($\uparrow$2.1) | 48.6± 2.8 ($\uparrow$2.8) | 53.2± 7.9 ($\uparrow$3.5) | 43.0± 2.3 ($\downarrow$-2.3) | 45.6± 2.2 ($\downarrow$-0.2)
GPT3.5 | 29.6± 2.7 | 27.0± 2.7 | 26.7± 2.5 | 25.7± 2.0 | 24.0± 1.9 | 24.6± 1.9
GPT3.5 + SGCD | 47.6± 3.3 ($\uparrow$18.0) | 37.9± 2.8 ($\uparrow$10.9) | 39.4± 2.8 ($\uparrow$12.7) | 44.2± 2.8 ($\uparrow$18.5) | 32.4± 2.1 ($\uparrow$8.4) | 35.3± 2.1 ($\uparrow$10.7)
Claude | 37.6± 3.1 | 31.3± 2.8 | 32.5± 2.7 | 27.5± 2.0 | 27.6± 2.0 | 27.4± 2.0
Claude + SGCD | 49.4± 2.5 ($\uparrow$11.8) | 37.5± 2.8 ($\uparrow$6.2) | 40.3± 2.9 ($\uparrow$7.8) | 46.2± 2.5 ($\uparrow$18.7) | 35.8± 2.2 ($\uparrow$8.2) | 38.3± 2.2 ($\uparrow$10.9)
Claude-instant | 25.3± 2.9 | 17.8± 2.2 | 19.9± 2.4 | 16.3± 1.7 | 15.9± 1.6 | 16.0± 1.6
Claude-instant + SGCD | 39.6± 3.3 ($\uparrow$24.3) | 29.6± 2.7 ($\uparrow$11.8) | 31.9± 2.5 ($\uparrow$12.0) | 37.8± 2.6 ($\uparrow$21.5) | 27.2± 2.1 ($\uparrow$11.3) | 30.0± 2.1 ($\uparrow$14.0)
PaLM-2-text | 19.1± 1.9 | 23.0± 2.4 | 19.9± 2.0 | 28.1± 2.1 | 26.7± 2.0 | 27.1± 2.0
PaLM-2-text + SGCD | 43.5± 3.2 ($\uparrow$24.4) | 33.1± 2.7 ($\uparrow$10.1) | 35.2± 2.7 ($\uparrow$15.3) | 42.9± 2.6 ($\uparrow$23.8) | 31.9± 2.1 ($\uparrow$8.9) | 34.6± 2.1 ($\uparrow$7.5)
Average improvement |  $\uparrow$16.4 |  $\uparrow$7.9 |  $\uparrow$10.7 |  $\uparrow$15.4 |  $\uparrow$5.8 |  $\uparrow$8.1

Table 1: Results for closed information extraction, in terms of triplet-based
precision, recall, and F1-score (micro-averaged, with bootstrapped 95%
confidence intervals) on the Wiki-NRE and SynthIE-text datasets. The results
compare the effectiveness of SGCD (blue rows) against two baselines: (1) few-
shot-prompted unconstrained decoding with powerful blackbox LLMs (“without
logit access”, white rows, Eq. 1) and (2) few-shot-prompted constrained
decoding (“CD”) with open-source LLMs (“with logit access”, Eq. 3). Four
demonstrations are used in few-shot prompting. LLaMA-7B serves as the
constrained generator $P_{\text{cg}}$ for SGCD.

In our experimental setup, we evaluate the efficacy of SGCD 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 SGCD method remains
flexible and is agnostic to the exact implementation of constrained decoding.
Here we adopt the grammar-constrained decoding framework of Geng et al.
(2023), 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.

###  3.1 Closed information extraction

Task description. The goal of closed information triplet extraction (IE) is to
extract a comprehensive set of facts from natural-language text. Formally,
given a knowledge base represented by a knowledge graph (KG) containing a
catalog of entities $\mathcal{E}$ and a catalog of relations $\mathcal{R}$,
the goal is to extract the complete set
$y_{\text{set}}\subset\mathcal{E}\times\mathcal{R}\times\mathcal{E}$ of fact
triplets expressed in a given input text $x$. It is crucial that the entities
and relations in these triplets be accurately grounded in the KG’s catalog. An
example of this process can be seen in Fig. 1. The instructions $I$ and
$I_{\text{cg}}$ for the sketcher and constrained decoder, respectively, are
listed in Appendix D.1.

Constraints. We use the constraints in Appendix D.2, which restrict entities
(1.5 million) and relations (857) to the Wikidata KG, and enforce the
structural constraint that outputs must be formatted as sequences of
entity–relation–entity triplets.

Datasets and evaluation metrics. We use the Wiki-NRE (Trisedya et al., 2019)
and SynthIE-text Josifoski et al. (2023) datasets (details in Appendix D.3).
Performance is measured using micro precision, recall, and F1-score.

Results. Table 1 illustrates that powerful blackbox LLMs, even without
constrained decoding, already exceed the performance of open-source LLMs that
employ constrained decoding. SGCD further enhances the performance of blackbox
LLMs. Notably, precision shows a significant increase—by an average of 16.4%
on Wiki-NRE and 15.4% on SynthIE-text—, demonstrating the efficacy of
constrained decoding in producing outputs that are aligned with the KG. The
gains in recall are more modest, with improvements of 7.9% and 5.8% on Wiki-
NRE and SynthIE-text respectively, implying that constrained decoding
primarily ensures alignment with the KG, rather than completeness. A detailed
analysis of output grounding is provided in Appendix D.5.

Degeneration. Our method is built on the assumption that the sketcher will
generate a high-quality sketch $y^{*}$, which the constrained generator will
refine into $z^{*}$, meeting the specified constraints. Ideally, $z^{*}$
should match or surpass the quality of $y^{*}$, but in certain cases we
observe a contrary outcome, which we term “degeneration”. This occurs when the
constrained generator diverges from following the sketch $y^{*}$, opting to
produce an alternative $z^{*}$ that, while meeting the constraints, is of
inferior quality. Note (Table 1) that this issue leads to a (slight) decline
in overall performance (in terms of recall) only with GPT-4 as the blackbox
LLM, and only on the SynthIE-text dataset.

###  3.2 Constituency parsing

Penn Treebank
---
Method | B-precv | B-recallv | B-F1v | Tag accuracyv | Validity
_With logit access_ |  |  |
LLaMA-2-7B + CD | 8.2± 0.1 | 12.5± 0.2 | 9.9± 0.1 | 14.5± 0.1 | 92.0
LLaMA-2-13B + CD | 12.9± 0.1 | 20.2± 0.2 | 15.7± 0.1 | 16.6± 0.1 | 95.0
_Without logit access_ |  |  |
GPT4 | 35.0± 0.1 | 30.6± 0.1 | 32.7± 0.1 | 47.0± 0.1 | 50.3
GPT4 + SGCD | 63.0± 0.1 ($\uparrow$28.0) | 57.4± 0.1 ($\uparrow$26.8) | 60.1± 0.1 ($\uparrow$27.4) | 89.5± 0.1 ($\uparrow$42.5) | 100 ($\uparrow$49.7)
GPT3.5 | 31.0± 0.1 | 24.6± 0.1 | 27.4± 0.1 | 47.1± 0.1 | 51.1
GPT3.5 + SGCD | 55.6± 0.1 ($\uparrow$24.6) | 44.9± 0.1 ($\uparrow$20.3) | 49.7± 0.1 ($\uparrow$22.3) | 87.3± 0.1 ($\uparrow$40.2) | 100 ($\uparrow$48.9)
Claude | 22.4± 0.2 | 19.2± 0.1 | 20.7± 0.1 | 31.3± 0.1 | 33.2
Claude + SGCD | 47.4± 0.1 ($\uparrow$25.0) | 41.3± 0.1 ($\uparrow$22.1) | 44.1± 0.1 ($\uparrow$23.4) | 69.0± 0.2 ($\uparrow$37.7) | 99 ($\uparrow$65.8)
Claude-instant | 23.6± 0.1 | 19.1± 0.1 | 21.1± 0.1 | 31.1± 0.1 | 34.6
Claude-instant + SGCD | 54.2± 0.1 ($\uparrow$30.6) | 44.7± 0.1 ($\uparrow$25.6) | 49.0± 0.1 ($\uparrow$27.9) | 77.2± 0.1 ($\uparrow$46.1) | 99.5 ($\uparrow$64.9)
PaLM-2-text | 8.8± 0.5 | 6.7± 0.3 | 7.6± 0.3 | 13.2± 0.1 | 14.0
PaLM-2-text + SGCD | 60.9± 0.1 ($\uparrow$52.1) | 48.7± 0.1 ($\uparrow$42.0) | 54.1± 0.1 ($\uparrow$46.5) | 86.7± 0.1 ($\uparrow$73.5) | 100 ($\uparrow$86)
Average improvement |  $\uparrow$32.1 |  $\uparrow$27.4 |  $\uparrow$29.4 |  $\uparrow$48.0 |  $\uparrow$63.1

Table 2: Results for constituency parsing, in terms of bracketing recall,
precision, F1-score, and tag accuracy (with bootstrapped 95% confidence
intervals), adjusted for validity (B-precv etc.), where each metric is scaled
by the percentage of valid parse trees as per the EVALB tool. We compare the
same methods as in constituency parsing (Table 1). Few-shot prompting uses
three demonstrations.

Task description. Constituency parsing involves breaking down a sentence into
its syntactic components to form a parse tree that represents the sentence’s
structure. For instance, the sentence “I saw a fox” corresponds to the parse
tree [S [NP [PRP I]] [VP [VBD saw] [NP [DT a] [NN fox]]]]. For a visual
representation of this tree, see Appendix E, Fig. 5. The instructions $I$ and
$I_{\text{cg}}$ are listed in Appendix E.1.

Constraints. We apply the constraints in Appendix E.2 to ensure that parse
trees are complete, brackets are balanced, and labels are consistent.

Dataset and evaluation metrics. Our evaluation uses the Penn Treebank test
split. We assess performance using bracketing recall and precision, as well as
tag accuracy, as measured by the EVALB tool Sekine and Collins (2008). Since
these metrics are only applicable to valid parse trees, and since models
typically generate valid trees only for simpler inputs, a direct comparison of
metrics can be challenging. Therefore, we employ validity-adjusted metrics,
following the approach of Hemmer et al. (2023), to gauge SGCD’s effectiveness
by multiplying the metrics by the fraction of valid parse trees.

Results. As indicated in Table 2, even advanced LLMs like GPT-4 face
challenges in generating valid parse trees, particularly for longer sentences.
LLaMA-2 models (7B, 13B), even using constrained decoding, exhibit much low
performance, struggling predominantly with longer inputs Geng et al. (2023).
However, with the aid of SGCD, the validity of output parse trees approaches
100% by construction (it may still be slightly less than 100% because the
maximum output length is sometimes reached before the end of generation).

The validity adjustment also significantly enhances other metrics, reducing
the penalty for invalid outputs. The most common errors in the unconstrained
setting include unbalanced brackets and omissions. Appendix E, Fig. 7,
provides a detailed example showing how SGCD effectively corrects these errors
in draft parse trees.

##  4 Related work

Constrained decoding. Deutsch et al. (2019) introduced a general constrained-
decoding framework for text generation based on automata. Further developments
in this area (cf. Geng et al. (2023) for a more complete overview) include the
work of Scholak et al. (2021) and Poesia et al. (2022), who implemented
incremental parsing for SQL generation. Additionally, Beurer-Kellner et al.
(2023) and Poesia et al. (2023) have proposed iterative approaches to
constrained decoding using blackbox LLM APIs, albeit with potential
limitations such as excessive API calls (thus increasing monetary cost), as
detailed in Appendix C.

Collaborative generation. In the realm of collaborative generation, Vernikos
et al. (2023) and Welleck et al. (2023) explored training smaller language
models to refine the outputs from larger models for enhanced quality. The
skeleton-of-thought approach, proposed by Ning et al. (2023), generates an
initial output skeleton and then concurrently develops each segment.
Meanwhile, grammar prompting, as suggested by Wang et al. (2023), involves
creating a meta-grammar to guide the output of LLMs in producing valid
results.

In contrast to these methods, SGCD offers a versatile approach that is not
confined to any specific API design. It is particularly aimed at enabling
constraint application to the outputs of blackbox LLMs, addressing a distinct
challenge in the field.

##  5 Conclusion

We propose sketch-guided constrained decoding (SGCD), a simple method for
constrained decoding with blackbox LLMs that does not require access to next-
token logits during generation. Our work is complementary to existing methods
for constrained decoding and can be used in conjunction with them. Despite its
simplicity, SGCD achieves strong performance on constrained generation tasks,
outperforming vanilla LLMs (both blackbox and open-source) by a large margin.

##  6 Limitations

  * •

Limitation 1: The degeneration problem sometimes hampers SGCD. More
investigation is needed to understand its causes and how to mitigate it.

  * •

Limitation 2: As LLMs keep getting better, the benefits of SGCD might diminish
on some tasks. This is, however, not a limitation of SGCD per se, but rather
of constrained decoding in general.

## Acknowledgments

We thank Grant Slatton for insightful discussions during the ideation phase.
West’s lab is partly supported by grants from Swiss National Science
Foundation (200021_185043, TMSGI2_211379), Swiss Data Science Center (P22_08),
H2020 (952215), Microsoft Swiss Joint Research Center, and Google, and by
generous gifts from Facebook, Google, and Microsoft.

## References

  * Agrawal et al. (2023) Lakshya A. Agrawal, Aditya Kanade, Navin Goyal, Shuvendu K. Lahiri, and Sriram K. Rajamani. 2023.  Guiding Language Models of Code with Global Context using Monitors.
  * Beurer-Kellner et al. (2023) Luca Beurer-Kellner, Marc Fischer, and Martin Vechev. 2023.  Prompting is programming: A query language for large language models.  _Proceedings of the ACM on Programming Languages_ , 7(PLDI):1946–1969.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.
  * Bubeck et al. (2023) Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, Harsha Nori, Hamid Palangi, Marco Tulio Ribeiro, and Yi Zhang. 2023.  Sparks of artificial general intelligence: Early experiments with gpt-4.
  * Chen and Wan (2023) Xiang Chen and Xiaojun Wan. 2023.  A comprehensive evaluation of constrained text generation for large language models.
  * Choi et al. (2023) Sehyun Choi, Tianqing Fang, Zhaowei Wang, and Yangqiu Song. 2023.  KCTS: Knowledge-Constrained Tree Search Decoding with Token-Level Hallucination Detection.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 14035–14053, Singapore. Association for Computational Linguistics.
  * Deutsch et al. (2019) Daniel Deutsch, Shyam Upadhyay, and Dan Roth. 2019.  A general-purpose algorithm for constrained sequential inference.  In _Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL)_ , pages 482–492, Hong Kong, China. Association for Computational Linguistics.
  * Geng et al. (2023) Saibo Geng, Martin Josifoski, Maxime Peyrard, and Robert West. 2023.  Grammar-constrained decoding for structured NLP tasks without finetuning.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 10932–10952, Singapore. Association for Computational Linguistics.
  * Hemmer et al. (2023) Arthur Hemmer, Mickael Coustaty, Nicola Bartolo, Jerome Brachat, and Jean-marc Ogier. 2023.  Lazy-k Decoding: Constrained Decoding for Information Extraction.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 6727–6736, Singapore. Association for Computational Linguistics.
  * Hendrycks et al. (2021) Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. 2021.  Measuring massive multitask language understanding.  _Proceedings of the International Conference on Learning Representations (ICLR)_.
  * Hokamp and Liu (2017) Chris Hokamp and Qun Liu. 2017.  Lexically constrained decoding for sequence generation using grid beam search.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1535–1546, Vancouver, Canada. Association for Computational Linguistics.
  * Hua et al. (2023) Wenyue Hua, Shuyuan Xu, Yingqiang Ge, and Yongfeng Zhang. 2023.  How to index item ids for recommendation foundation models.  In _Proceedings of the Annual International ACM SIGIR Conference on Research and Development in Information Retrieval in the Asia Pacific Region_ , SIGIR-AP ’23. ACM.
  * Huang et al. (2023) Wenlong Huang, Fei Xia, Dhruv Shah, Danny Driess, Andy Zeng, Yao Lu, Pete Florence, Igor Mordatch, Sergey Levine, Karol Hausman, and Brian Ichter. 2023.  Grounded Decoding: Guiding Text Generation with Grounded Models for Embodied Agents.
  * Huguet Cabot and Navigli (2021) Pere-Lluís Huguet Cabot and Roberto Navigli. 2021.  REBEL: Relation extraction by end-to-end language generation.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 2370–2381, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Josifoski et al. (2022) Martin Josifoski, Nicola De Cao, Maxime Peyrard, Fabio Petroni, and Robert West. 2022.  GenIE: Generative information extraction.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 4626–4643, Seattle, United States. Association for Computational Linguistics.
  * Josifoski et al. (2023) Martin Josifoski, Marija Sakota, Maxime Peyrard, and Robert West. 2023.  Exploiting asymmetry for synthetic training data generation: SynthIE and the case of information extraction.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 1555–1574, Singapore. Association for Computational Linguistics.
  * Lee et al. (2023) Tony Lee, Michihiro Yasunaga, Chenlin Meng, Yifan Mai, Joon Sung Park, Agrim Gupta, Yunzhi Zhang, Deepak Narayanan, Hannah Benita Teufel, Marco Bellagente, Minguk Kang, Taesung Park, Jure Leskovec, Jun-Yan Zhu, Li Fei-Fei, Jiajun Wu, Stefano Ermon, and Percy Liang. 2023.  Holistic evaluation of text-to-image models.
  * Marcus et al. (1993) Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993.  Building a large annotated corpus of English: The Penn Treebank.  _Computational Linguistics_ , 19(2):313–330.
  * Ning et al. (2023) Xuefei Ning, Zinan Lin, Zixuan Zhou, Zifu Wang, Huazhong Yang, and Yu Wang. 2023.  Skeleton-of-Thought: Large Language Models Can Do Parallel Decoding.  ArXiv:2307.15337 [cs].
  * Poesia et al. (2023) Gabriel Poesia, Kanishk Gandhi, Eric Zelikman, and Noah D. Goodman. 2023.  Certified deductive reasoning with language models.
  * Poesia et al. (2022) Gabriel Poesia, Alex Polozov, Vu Le, Ashish Tiwari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. 2022.  Synchromesh: Reliable code generation from pre-trained language models.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net.
  * Ranta (2019) Aarne Ranta. 2019.  Grammatical framework: an interlingual grammar formalism.  In _Proceedings of the 14th International Conference on Finite-State Methods and Natural Language Processing_ , pages 1–2, Dresden, Germany. Association for Computational Linguistics.
  * Schick et al. (2023) Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023.  Toolformer: Language models can teach themselves to use tools.
  * Scholak et al. (2021) Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. 2021.  PICARD: Parsing incrementally for constrained auto-regressive decoding from language models.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 9895–9901, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Sekine and Collins (2008) Satoshi Sekine and Michael Collins. 2008.  Evalb: Bracket scoring program.
  * Shah et al. (2022) Dhruv Shah, Blazej Osinski, Brian Ichter, and Sergey Levine. 2022.  Lm-nav: Robotic navigation with large pre-trained models of language, vision, and action.
  * Shin et al. (2021) Richard Shin, Christopher Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. 2021.  Constrained language models yield few-shot semantic parsers.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 7699–7715, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Trisedya et al. (2019) Bayu Distiawan Trisedya, Gerhard Weikum, Jianzhong Qi, and Rui Zhang. 2019.  Neural Relation Extraction for Knowledge Base Enrichment.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 229–240, Florence, Italy. Association for Computational Linguistics.
  * Vernikos et al. (2023) Giorgos Vernikos, Arthur Bražinskas, Jakub Adamek, Jonathan Mallinson, Aliaksei Severyn, and Eric Malmi. 2023.  Small language models improve giants by rewriting their outputs.
  * Wang et al. (2023) Bailin Wang, Zi Wang, Xuezhi Wang, Yuan Cao, Rif A. Saurous, and Yoon Kim. 2023.  Grammar prompting for domain-specific language generation with large language models.
  * Welleck et al. (2023) Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. 2023.  Generating sequences by learning to self-correct.  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net.
  * Zhang et al. (2023) Kexun Zhang, Hongqiao Chen, Lei Li, and William Wang. 2023.  Syntax error-free and generalizable tool use for llms via finite-state decoding.

##  Appendix A Blackbox LLM logit access

Model | Logit bias | Token probs | MMLU
---|---|---|---
GPT4-0614 | Yes | Top 5 | 86.4
GPT3.5-0614 | Yes | Top 5 | 70.0
Claude-2.1 | No | No | 78.5
Claude-instant | No | No | 73.4
PaLM-2-text-bison | Yes | Top 5 | 78.3

Table 3: The blackbox LLMs we use in our experiments and the access they
provide to the logit distribution. MMLU is the mainstream metric for LLM
benchmarking.

Logit bias indicates whether the model’s API allows user to pass in a logit
bias vector to steer the decoding process, i.e., write access to the logit
distribution. Token probs indicates whether the model’s API allows user to
access the model’s next token probability distribution, i.e., read access to
the logit distribution. MMLU (Hendrycks et al., 2021) is the mainstream metric
for LLM benchmarking.

##  Appendix B Grammar constrained decoding

Grammar-constrained decoding takes a formal grammar $G$ as input and ensures
that the output string $w$ is a valid sentence in the formal language $L(G)$
defined by the grammar $G$. This process is achieved through the integration
of two key components: a grammar completion engine (Poesia et al., 2022) and a
sampling method, e.g. greedy search, nucleus sampling, etc. The grammar
completion engine is used to ensure the grammaticality of the output string,
while the LLM is used to ensure the plausibility of the output string.

We use Grammatical Framework’s runtime powered completion engine Ranta (2019)
with constrained beam search as the sampling method.

##  Appendix C Logit bias-based iterative decoding

Most blackbox LLM APIs do not provide complete access to the model’s next
token probability distribution at each decoding step. Nonetheless, many allow
users to input a logit bias parameter to influence the decoding process, i.e.,
granting users write access but not read access to the model’s logits at each
decoding step. This parameter accepts a vector of logits that is added to the
logits of the next token probability distribution at each decoding step. By
using the logit bias parameter, users can direct the decoding process,
effectively masking the logits of invalid tokens. This approach is
particularly effective for static constraints, such as lexical constraints
(Hokamp and Liu, 2017), where the constraints remain constant throughout the
decoding.

However, the logit bias parameter is a static array and does not change during
the decoding process. This makes it challenging to apply dynamic constraints,
which change as decoding progresses, such as constraints involving membership
in formal languages (Deutsch et al., 2019; Poesia et al., 2022; Geng et al.,
2023).

A straightforward but costly solution for dynamic constraints is to
iteratively invoke the blackbox LLMs API with updated logit bias vectors at
each decoding step (Beurer-Kellner et al., 2023; Poesia et al., 2023; Agrawal
et al., 2023; Choi et al., 2023). However, this approach is prohibitively
expensive. Each API call generates only a single token, and the cost is
calculated based on both the input and output tokens222See
https://openai.com/pricing for details.. The expense of iteratively calling
the blackbox LLMs API with new context and prefix at each step scales
quadratically, being $O(n^{2})$ where $n$ is the length of the output
sequence. Although methods like those proposed by Beurer-Kellner et al. (2023)
and Poesia et al. (2023) use speculation to reduce the number of API calls,
the costs can remain high, especially when the constraints are complex.

##  Appendix D Task 1. closed information extraction

In this section, we provide more details about the closed information
extraction task.

###  D.1 Task instruction

We provide the instruction for the IE task in Figure 2. The few-shot
demonstrations are rather long and thus we do not include them here. The full
prompt is available in our code repository.

Extract the subject-relation-object triples in fully-expanded format from
texts below. The subjects and objects are entities in Wikidata, and the
relations are Wikidata properties. Here are a few examples. (a) Instruction
for sketcher

In this task, you will be provided with texts along with draft annotations
that represent extracted information triples in the form of subject-relation-
object. Your role is to refine these triples to ensure completeness and
accuracy. Here are a few examples. (b) Instruction for constrained generator

Figure 2: Instructions for parsing tasks.

###  D.2 Grammar

The grammar is defined as follows, where $V$ represents the set of variables,
$\Sigma$ the set of terminal symbols, and $P$ the set of production rules:

$\displaystyle V=\\{S,T,A,B,C,E,R\\},\Sigma=\\{\texttt{tokens}\\}$
$\displaystyle P=\\{S\rightarrow[ST|\epsilon],T\rightarrow[ABC\texttt{[e]}]$
$\displaystyle
A\rightarrow[\texttt{[s]}\;E],E\rightarrow(\texttt{entity1}|\texttt{entity2}|...),$
$\displaystyle
B\rightarrow[\texttt{[r]}\;R],R\rightarrow(\texttt{rel1}|\texttt{rel2}|...)$
$\displaystyle
C\rightarrow[\texttt{[o]}\;E],\epsilon\rightarrow\texttt{</s>}\\}$

The outputs are structured as a sequence of triplets, where each triplet is
separated by a special marker [e]. Every triplet consists of a subject, a
relation, and an object. These elements are each preceded by a special marker:
[s] for the subject, [r] for the relation, and [o] for the object,
respectively. The subject and object are pre-defined Wikidata entities, and
the relation is a pre-defined Wikidata property. This grammar is classified as
context-free, more specifically, as a regular grammar.

###  D.3 IE datasets

The original SynthIE-text and Wiki-NRE datasets comprise 50,000 and 30,000
samples, respectively. To minimize the evaluation cost on Large Language
Models (LLMs), we use a smaller subset consisting of 1,000 samples from each
dataset.

As noted by Josifoski et al. (2023), the Wiki-NRE dataset displays a
significant skew in its relations distribution: the top 10 relations
constitute 92% of the triplets, with the top 3 alone accounting for 69%. To
ensure our test set accurately reflects the overall dataset, we have
downscaled it to 1,000 samples to balance the distribution of relations, as
shown in Fig. 3

The SynthIE-text dataset, synthesized by reverse prompting Text-Davinci-003
with triplets from Wikidata, stands out due to its substantial size, diverse
content, and high-quality human ratings, as highlighted in Josifoski et al.
(2023). This contrasts with prior datasets such as REBEL Huguet Cabot and
Navigli (2021), whose annotation quality is low (Josifoski et al., 2022).
However, a potential minor bias may exist towards GPT-4 and GPT-3.5, as
SynthIE-text was generated from a model in their family, Text-Davinci-003.
Despite this, we maintain that this does not compromise the validity of our
method, given that our primary focus is on the comparative performance with
and without the application of SGCD.

(a) Original relation distribution in WikiNRE test set

(b) Stratified relation distribution in WikiNRE test set

Figure 3: Relation distribution in WikiNRE before and after stratification.

###  D.4 Discussion of GPT-4 on cIE

An intriguing finding is that SGCD’s performance on the SynthIE-text dataset
using GPT-4 (F1=45.6) is marginally lower than that achieved with few-shot
prompting alone, without constrained decoding (F1=45.8). Our analysis suggests
that the constrained generator occasionally struggles to adhere to the
sketcher’s outline, resulting in fewer triplets than expected in the output.
This observation is consistent with Wang et al. (2023)’s findings, where
constrained decoding was noted to reduce the diversity of the generated
samples.

More critically, since SynthIE-text is synthetically generated by reverse
prompting Text-Davinci-003 with triplets from Wikidata, its text doesn’t
exhibit the naturalness characteristic of the Wiki-NRE dataset. For instance,
sentences in SynthIE-text often resemble direct copies with slight alterations
from the original entity and relation names. This tendency facilitates the
LLMs’ task of grounding entities and relations in the Knowledge Graph (KG),
thereby diminishing the necessity for constrained decoding.

However, in real-world scenarios, text is typically more intricate, and
grounding entities and relations in the KG is not as straightforward. Despite
this, the overall performance enhancement provided by SGCD across various
models remains noteworthy, averaging gains of up to 10.7% and 8.1% on Wiki-NRE
and SynthIE-text, respectively.

###  D.5 Grounding analysis

In this study, we delve into the grounding efficacy of GPT-4’s output. A
triplet is deemed grounded when both its subject and object entities, as well
as the relation, are present in the KG. Furthermore, for a grounded triplet to
be considered correct, it must also be part of the target triplet set.

Given that being grounded is essential but not solely adequate for being
correct, it is crucial to assess how well GPT-4’s output aligns with the KG.
According to the data presented in Table 4, we observe that a significant
portion of the output triplets from GPT-4 are not grounded in the KG,
amounting to 45% and 37% on the Wiki-NRE and SynthIE-text datasets,
respectively. This finding sheds light on the importance of constrained
decoding, as it ensures that the output is grounded in the KG, thereby
increasing the likelihood of validity.

| Ratio of invalid triplets
---|---
| Wiki-NRE | SynthIE-text
| Entity | Rel | Triplet | Entity | Rel | Triplet
GPT4 | 19.4 | 21.9 | 45.2 | 7.6 | 28.1 | 37.3
GPT3.5 | 23.4 | 50.2 | 65.8 | 13.8 | 52.5 | 63.3
Claude | 17.0 | 41.1 | 55.5 | 17.4 | 52.8 | 64.6
Claude-ins | 19.6 | 48.4 | 62.6 | 13.8 | 43.3 | 52.7
PaLM-2 | 23.2 | 55.8 | 69.1 | 9.1 | 56.3 | 62.4
Average | 20.5 | 43.5 | 59.6 | 12.3 | 46.6 | 56.1
SGCD | 0 | 0 | 0 | 0 | 0 | 0

Table 4: Triplets grounding analysis. We report the percentage of generated
entities, relations, and triplets that are not present in the knowledge
catalogue in few-shot unconstrained setting. The grounding precision for
constrained methods is 100% by construction, and thus 0% invalid triplets.

##  Appendix E Task 2. constituency parsing

In this section, we provide more details about the constituency parsing task.

###  E.1 Task instruction

We provide the instruction for the CP task in Figure 4. The few-shot
demonstrations are rather long and thus we do not include them here. The full
prompt is available in our code repository.

Perform constituency parsing on the provided sentences in accordance with the
Penn TreeBank annotation guidelines. Here are a few examples. (a) Instruction
for sketcher

In this task, you will be provided with a draft annotations that represent the
parse tree of a sentence in Penn TreeBank format. Your task is to rewrite the
parse tree and fix error if any. Here are a few examples. (b) Instruction for
constrained generator

Figure 4: Instructions for parsing tasks.

###  E.2 Constraints and grammar

[.S [.NP [.PRP I ] ] [.VP [.VBD saw ] [.NP [.DT a ] [.NN fox ] ] ] ]

(a) The correct constituency parse tree

[.S [.VP [.VBD I ] [.NP [.DT saw ] [.NN a ] [.NN fox ] ] ] ]

(b) A grammatical but incorrect parse tree

Figure 5: Parse trees for the sentence “I saw a fox”.

Here we describe the grammar used to constrain the generative constituency
parsing task.

Linearization. A constituency parse tree is inherently a recursive structure.
To effectively represent this tree as a sequence of tokens for generation by a
Large Language Model (LLM), a linearization is required. Two common strategies
for this linearization are pre-order traversal and post-order traversal.

We have chosen to adopt the pre-order traversal strategy. This approach is
also the default method used in the PYEVALB tool Sekine and Collins (2008) and
in the construction of the Penn Treebank Marcus et al. (1993). As an
illustration, the parse tree in Fig. 5(a) is linearized in the following
format: [S [NP [PRP I]] [VP [VBD saw] [NP [DT a] [NN fox]]]].

The linearised parse tree needs to satisfy the following structural
constraints:

  * •

Completeness: Every word in the sentence needs to be included in the parse
tree.

  * •

Balanced brackets: At any point in the linearized parse tree, the right
bracket ] should close a previously unclosed left bracket [ and every left
bracket [ should be eventually closed by a right bracket ].

  * •

Label consistency: The label of terminal and non-terminal nodes needs to be
consistent with the Penn Treebank format.

Grammar. The tree structure of the parse tree is usually captured by a
context-free grammar. However, the context-free grammar is not sufficient to
capture the completeness constraint, motivating the use of a more restrictive
grammar. We use the same grammar as in Geng et al. (2023) as shown in Fig. 6.

$\displaystyle S\to B_{0,0}$ $\displaystyle B_{i,j}\to[\alpha\,(B_{i,j+1}\mid
C_{i,j+1})];$ $\displaystyle C_{i,j}\to x_{i}\,(C_{i+1,j}\mid E_{i+1,j});$
$\displaystyle C_{n,j}\to E_{n,j};$ $\displaystyle E_{i,j+1}\to]\,(E_{i,j}\mid
B_{i,j});$ $\displaystyle E_{n,j+1}\to]\,E_{n,j};$ $\displaystyle
E_{n,0}\to\varepsilon;$ $\displaystyle\text{where}\,\alpha=(S\mid NP\mid
VP\mid\ldots)$ $\displaystyle\text{and}\,x_{i}\in\text{tokens}$ Figure 6:
Grammar for constituency parsing used in constrained decoding.

The grammar falls into the category of regular grammar and is input-dependent.
it reproduces the input sentence, represented as a sequence $x=\langle
x_{0},\dots,x_{n-1}\rangle$ of words, in left-to-right order, interspersing it
with node labels and balanced brackets. In order to guarantee balanced
brackets, the non-terminals $B_{i,j}$ count the number of opened left brackets
[ using the second subscript index $j$, and the rules ensure that the number
of closed brackets can never exceed the number of previously opened brackets.

###  E.3 Example of constituency parsing correction

We provide an example to show the correction from our method in Figure 7. As
shown in the figure, the parse tree of the input sequence is not valid because
the number of closing brackets is 2 times less than the number of opening
brackets and some tags are not consistent with the Penn Treebank format. The
constrained generator generates a sequence of tokens that is consistent with
the grammar and fixes the parse tree to be valid.

However, the fixed parse tree is not yet identical to the target parse tree,
cf. blue nodes in Figure 7. This is expected because the constrained generator
can only fix the parse tree to be consistent with the grammar but cannot
guarantee that the parse tree is identical to the target parse tree.

Figure 7: Example to show the correction process of our method. The red nodes
are the nodes that are corrected by constrained generator. The blue nodes are
the nodes that different from the target parse tree( some of them are not
corrected by constrained generator because they are not violating the
grammar).

###  E.4 Validity adjusted metric

We use the validity adjusted metric as done in Hemmer et al. (2023) to measure
the effectiveness of our method. It is defined as follows:

$\displaystyle\text{Metric}^{\text{v}}=\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}(\text{valid}(y_{i}))\cdot\text{Metric}(y_{i})$
$\displaystyle\text{valid}(y_{i})=\begin{cases}1&\text{if the parse tree is
valid}\\\ 0&\text{otherwise}\end{cases}$

##  Appendix F Data contamination risk

There is a rising concern over the data contamination risk of evaluating LLMs
on downstream tasks. The datasets of our experiments are publicly available on
internet so there is a risk that the models may have seen the data, such as
the ground true parse tree of Penn Treebank during pretraining. However, the
risk of data contamination is independent of our method and doesn’t affect the
validity of our conclusions.