Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning
Authors: Saibo Geng
Martin Josifoski
Maxime Peyrard
Robert West
Venue: EMNLP 2023 Main (2023)
Keywords: Grammar-Constrained Decoding
Large Language Model
LLM
Structured NLP
Information Extraction
Entity Disambiguation
TL;DR: We cast structured NLP tasks as constrained decoding from an LLM, where only outputs that conform with a task-specific grammar are allowed. This approach, termed grammar-constrained decoding (GCD), significantly enhances the performance of LLMs.

Abstract: Despite their impressive performance, large language models (LMs) still
struggle with reliably generating complex output structures when not finetuned
to follow the required output format exactly. To address this issue,
grammar-constrained decoding (GCD) can be used to control the generation of
LMs, guaranteeing that the output follows a given structure. Most existing GCD
methods are, however, limited to specific tasks, such as parsing or code
generation. In this work, we demonstrate that formal grammars can describe the
output space for a much wider range of tasks and argue that GCD can serve as a
unified framework for structured NLP tasks in general. For increased
flexibility, we introduce input-dependent grammars, which allow the grammar to
depend on the input and thus enable the generation of different output
structures for different inputs. We then empirically demonstrate the power and
flexibility of GCD-enhanced LMs on (1) information extraction, (2) entity
disambiguation, and (3) constituency parsing. Our results indicate that
grammar-constrained LMs substantially outperform unconstrained LMs or even beat
task-specific finetuned models. Grammar constraints thus hold great promise for
harnessing off-the-shelf LMs for a wide range of structured NLP tasks,
especially where training data is scarce or finetuning is expensive. Code and
data: https://github.com/epfl-dlab/GCD.

Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning
Saibo Geng, Martin Josifoski, Maxime Peyrard," Robert West
EPFL Université Grenoble Alpes, CNRS, Grenoble INP, LIG
(saibo.geng, martin.josifoski, robert. west @epfl.ch, maxime. maxime.peyrarde teii-grenoollealee..ff
Abstract
Grammar for closed information extraction (ciE):
S -- di [=] [=] # [a] 8)
Despite their impressive performance, large lan- guage models (LMs) still struggle with reliably generating complex output structures when not finetuned to follow the required output for- mat exactly. To address this issue, grammar- constrained decoding (GCD) can be used to control the generation of LMs, guarantceing that the output follows a given structure. Most existing GCD methods are, however, limited to specific tasks, such as parsing or code genera- tion. In this work, we demonstrate that formal grammars can describe much wider range of tasks and argue that GCD can serve as a unified framework for structured NLP tasks general. For increased flexibil- ity, we introduce imput-dependent grammars, which allow the grammar to depend on the in- put and thus enable the generation of different output structures for different inputs. We then empirically demonstrate the power and flexi- bility of GCD-enhanced LMs (1) informa- tion extraction, (2) entity disambiguation and (3) constituency parsing. Our results indicate that grammar-constraing, LMs substantially outperform unconstrained LMs or even beat task-specific finetuned models. Grammar con- straints thus hold great promise for harnessing offethe-shelf LMs for a wide range of struc- tured NLP tasks, especially where training data is scarce or finetuning is expensive. Code and data: https: //g thub. com/epfl-dlab
(Ertity Entity M) (Relation
Relation M/)
"Burand
Burundi
moved its capital from Bujumbura
LM
[c] capital
[o] Gitagg"
Gitege"
Grammar--onstrrinned
decoding (GCD)
-
During
Burundi
Znil
GM
capitai
member
Aee
eise
t=2
Graega
Bujumbura
output space for
tm3
Airport
is
new
LEGEND:
root non-torminal
Input
empty string
y: output
az entiiies from KB
forbidder tokens decoding path
$: end of sequenie
relations from KB
Grammar- coammarrconstrained decoding (GCD), plied the task closed information extraction, where the goal is to extract list of subject-relation wewe--rellattotbeeeeeeeeee object triplets from the input text x. Subjects and objects are constrained Wikidata entities, relations be Wi- kidata relation. During decoding, only valid token con- tinuations compliant with the grammar are considered. For simplicity, omit the special marker symbols [s], [r], and [o] in the schema of the generation process.
Figure I:
can be finetuned for specific tasks with minimal modifications to the training process while still ben- efiting from the advantages of pretraining. More recently, the scaling of language models to larger sizes has introduced notable in-context learning capabilities (Brown et al., 2020; Radford et al.. 2019; Schick and Schütze, 2021), such that large language models (LLMs) can quickly and effec- tively adapt new tasks without finetuning, when shown only few demonstrations as part of their context.
1 Introduction
Pretrained language models (LMs) have achieved impressive results across a range of tasks, such as machine translation, summarization, and dialogue generation (Brown et al., 2020; Touvron et al., 2023). All of these models are pretrained on next- token prediction task, encouraging researchers to cast other NLP tasks in the same autoregressive generation framework. By framing tasks autore- gressive generation, pretrained language models
Certain important tasks, however, such closed information extraction (cIE), entity disambiguation (ED), or constituency parsing (CP), require the out- put to follow predefined format and adhere to
Work done while at EPFL.

---

a restricted vocabulary (entities, relations, senses, dependency labels, etc.). Whereas LMs excel at generating free-form text, they are not specifically designed for structured prediction tasks where only a small subset of the output space is valid. Conse- quently, structured prediction tasks present unique challenges because constrained output spaces de- mand both structural coherence and compliance with a predefined vocabulary. For instance, Josi- foski al. (2023) have demonstrated that few-shot- prompted large language models such as GPT-3.5 struggle with tasks such as cIE. This difficulty is primarily due to the extensive output vocabulary, which includes 2.7 million Wikidata entity names and approximately 1,000 Wikidata relation names, which is too vast to be conveyed with just few demonstration examples.
perspective, the grammar-constrained decoding (GCD) framework allows researchers to focus on writing the grammar while ignoring the implemen- tation details of the constrained decoding process. This is in contrast to previous work, where the con- straints were expressed in the form of finite-state automata or trie-based data structures, which re- quire a significant engineering effort to implement. We envision GCD be as simple to use regular expressions, the sense that the user can specify a desired output structure in a declarative way, and the LM-generated sequences will be guaranteed to be valid. With the introduction of input-dependent grammars, the scope of tasks that can be tackled with GCD can be further extended to tasks such as entity disambiguation and entity linking, where the output space is not fixed but depends the input. We show that, by combining GCD with powerful LLMs, we achieve remarkable improvements with few-shot learning, even rivaling the performance of finetuned task-specific models. This is particularly exciting because shows that LMs can be used to solve a much wider range of structured tasks than before, without the need for finetuning. Our contributions can be summarized as follows:
One way forward is to finetune LMs for spe- cific tasks, which involves linearizing the desired output format into a string format, thus enabling training through standard next-token prediction. For instance, De Cao et (2021) and Josifoski et al. (2022) successfully applied this technique to ED and CIE, respectively. However, this ap- proach has limitations: it necessitates an expen- sive finetuning pipeline for each new task, which lacks flexibility and requires bespoke training data. Orthogonally, constrained decoding (Tromble and Eisner, 2006) is technique that can be used to enforce constraints on the output space of an autoregressive language model during infer- ence. Constrained decoding has been used in se- mantic role labeling (Deutsch et al.. 2019), con- stituency parsing (Deutsch et al., 2019), code gen- eration (Scholak et al., 2021), and entity disam- biguation (De Cao et al., 2021). The constraints have been expressed in the form of finite-state au- tomata (Deutsch et al., 2019) or trie-based data structures for fast lookup (De Cao et al., 2021).
We demonstrate that the output spaces of many structured NL.P tasks can be formulated as formal languages, thus converting the tasks into cuummar-constrained decoding problems. This formulation provides a unified frame- work to tackle structured NLP tasks.
2. We introduce input-dependent grammars, which extend the set of tasks that can be tack- led with GCD. We show that this can be useful, among others, for tasks such as ED and CP. Through empirical experiments, we demon- strate the effectiveness of GCD on three struc- tured NLP tasks: cIE, ED, and CP. We show that our method can achieve competitive re- sults on cIE and ED without any finetuning.
In this work, we show that, for much wider range NLP tasks, the respective output space can be described with a formal grammar, giving rise to a unified framework for structured NLP tasks. Given an appropriately defined grammar, we use an incremental parser to play the role of a com- pletion engine, which determines the set of valid next tokens given the current prefix. We integrate this completion engine with pretrained language model to iteratively generate sequences that are valid according to the grammar and plausible ac- cording to the LM (cf. Fig. 1). From a practical
2 Method
We now describe GCD and how it can constrain the output of LMs at decoding time based on formal grammar. We first explain how to specify the output spaces of various NLP tasks via formal grammars. Then we show how an incremental parser can be used as a completion engine to constrain the LM's generation process to produce grammatically valid outputs only.

---

Token-level formal grammars. A formal gram- mar G is defined as a tuple V.E) where
Closed information extraction: see Fig. (2)' Entity disambiguation:
f m [o]r, where left context of mention m. is right context, and is disjunction of candidate entities for mention
V is a finite set of non non-terminal symbols,
(3) Constituency parsing: S > BB of B,, [a (,,, C
iilli C, -X X, (C... Ji C.y E ; E |. VE, B
Σ is finite set of terminal symbols.
E Juje 1E E - v; where a = (SINP/VP/...)
(4) Coreference resolution: S, x, [0x, 1x,1 1)] S
P is finite set of production rules,
S. i, where L means "no referent"
S E V is the start symbol.
(6) Part-of-speech tagging: S, > X, [(NOUN] | VERB| ADJ
...] S, S. F
(6) Dependency parsing: s, -x [ROOT| NSUBJ D
We illustrate the suitability of formal grammars for specifying the output spaces of structured NLP tasks in Fig. 2 using 14 common tasks as examples. In our approach, the user first writes a formal grammar G over characters. In order to obtain a token-level grammar Gook that can be used to con- strain the direct output of LMs-ttken sequences- we use the token set Yook as terminal symbols and apply the tokenizer to the sequences of terminal symbols appearing in the rules P. obtaining the token-level rules Rok- This yields the token-level grammar Gook = (V; Prk: which describes the same language as the character-level grammar G. We then use an incremental parser (see below) to decide whether a token sequence y is in the lan- guage generated by Giok-
...) (x. |x, L S, + 5, where 1 means "no head"
(7)" Word sense disambiguation: S, x, [a,]] S. -e.
where a the disjunction
WordNet glosses word x (8)* Phrase chunking: S B B, [C; B, -+,; C
(C.,, [a] B, C. <], where (NP VP PP ...)
(9)* Semantic role labeling: Same as phrase chunking,
but with e = (TARGET| ARGO| ARG1 ...)
(10)* Entity linking: Same as phrase chunking. but with the disjunction
KB entity names (or for "no entity") (11)* CCG parsing: Same as constituency parsing, but with syntactic types (e.g.. (SNNPVMP) instead constituent labels. Extra constraints ensure that nodes have most two children and that syntactic types combine correctly. (12)* Question answering: S [q] [A]; {f A),
where q is the question and the disjunction of all vocabulary words
(13)* Extractive summarization: S - (e [[a]S] S). where a is
the disjunction of all sentences from input x (14)* Semantic parsing with A-calculus: A logical form a rooted tree, generated by a context-free grammar
Figure 2: Formal grammars for structured NLP tasks, highlighting the general applicability of grammar- constrained decoding. All 14 grammars are context-free (mostly regular). * marks input-dependent grammars. are sequences of lexical units
Despite its simplicity, this approach has some limitations. Widely used tokenization methods such as BPE (Sennrich al., 2016) allow the same string to be tokenized in different ways. For ex- ample, the string "C[[" can be tokenized as "[C [", "CCC" or "[ [", all of which would be detokenized to the original string "[[C". To avoid this ambiguity, we can add extra spaces between the brackets in the grammar and force the single bracket to be token. This approach is. however, not principled and relies on a specific tokenizer. We therefore believe that a principled approach for defining token-level grammars is an interesting direction for future work.
Inputs == (M0, .,, (e.g.. words): 0 < i S n - 1; single capital letters are non-terminal symbols;
So is the start symbol; e is the empty string; [ and are special terminal symbols.
2.1
NLP tasks formal languages
The input x and output y of NLP tasks are typi- cally sequences of tokens, x = (xo....., and y= (yo--...Jmmmi> Whereas the input x is usually arbitrary, for many tasks the output y needs to fol- low a specific structure. For instance, in informa- tion extraction, y required to consist of subject- relation-object triplets (cf. Fig. 1). Since formal languages provide a rigorous and complete frame- work for describing the structure of any computable set of object (according to the Church- Church-Turing the- sis), they offer a promising way to define the output spaces of structured NLP tasks. In order to define the formal languages corresponding to the output spaces of structured NLP tasks, our framework re- lies on formal grammars, a universal formalism that can describe any formal language. For tractability, we focus on the class of context-free grammars.
Grammatical Framework. Since the token-level grammar Gjok is tokemizer-dependenn, there are in general multiple token-level grammars for the same grammar G. This one-to-many mapping from a character-level grammar to a token-level grammar is analogous to the one-to-many mapping from ab- stract syntax trees to different programming lan- guages. For this reason, adopt Grammatical Framework (GF) (Ranta, 2019) to define both the grammar G and the token-level grammar Giok- GF is a meta-language for multilingual grammar appli- cations, which allows us to define an abstract gram- mar as well as concrete grammars for linearizing

---

abstract syntax trees into different tokenizer-spe- cific "languages". In our case, the abstract grammar is the character-level grammar and the concrete grammars are the token-level grammars for differ- ent tokenizers.
2.3 Few-shot learning with GCD
To adapt a pretrained LM to a new task, one can either finetune the LM on task-specific training data or few-shot learning if the LM is powerful enough. In this work, we use GCD in conjunc- tion with few-shot learning to adapt pretrained large LM (LLM) to new tasks. Instead of prompt- ing the LLM to generate free-form text, we use GCD to constrain the output to be grammatically correct. This allows us to leverage the LLM's few- shot learning capability together with the grammar- induced knowledge of the task's output structure.
Input-dependent grammars (IDG), While the output of many NLP tasks can be described by a formal grammar, some tasks require a grammar that is dependent on the input sequence. For example, in entity dismbiguation, the output needs to be con- strained to the set of entity candidates, which usu- ally contains dozens of entity names semantically related to the target mention in the input sequence. In constituency parsing, outputs are parse trees whose terminal nodes are the input tokens. These two tasks both require a grammar that is dependent on the input. Existing work has focused on using a single grammar to constrain the decoding regard- less of the input sequence. Whereas this is suitable for tasks where the output space is independent of the input sequence, such code generation (Poesia al., 2022) or information extraction (Josifoski al., 2022) (ef. Fig. 1). 13 of the 14 tasks listed in Fig. (those with an asterisk) require an input- dependent grammar.
For the same task, we can use different grammars to constrain the output of the LLM. For example. in entity disambiguation, we can use a grammar Gi that depends on the input sequence to constrain the output to the input-specific candidate set, or we could use grammar G2 that is independent of the input to constrain the output to be any valid entity name. While both G and G2 can be used to constrain the output of the LLM, G₁ reduces the search space more and thus is more effective.
3 Experimental setup
Although GCD can be applied to many tasks, we concentrate on three tasks in order to showcase its effectiveness: closed information extraction (cIR), entity disambiguation (ED), and constituency pars- ing (CP). The first two tasks are examples where the output is restricted to a predefined set of en- tities and relations, while the third is an example of a task where the output is a complex tree struc- ture. All three tasks are challenging for LLMs in the few-shot setting, and we show that GCD significantly improve LLM performance.
2.2
Grammar-constrained decoding (GCD)
The LM decoding process produces tokens one by one. To enforce the formal grammar, intervene during decoding by pruning the probability distri- bution include only the subset of tokens that are allowed by the formal grammar. The subset of al- lowed tokens is returned by an incremental parser, which takes the partially generated sequence and the formal grammar as inputs and returns the set of next allowed tokens. The role of the parser can be abstracted completion engine (Poesia et al., 2022), which derives completion candidates from the partial sequence and the formal grammar G. In this work, we use the incremental parser of Gram- matical Framework (Angelov, 2009) as the comple- tion engine. This process is compatible with any decoding algorithm, including greedy decoding, beam search, top-k sampling, etc. GCD can also be applied to any autoregressive language model, provided that have access to the distribution over the vocabulary at each decoding step. Since API-based services such as OpenAl do not provide access to the distribution over the vocabulary, they cannot be used with GCD.
3.1 Closed information extraction (cIE)
Task description. The goal of closed information extraction (cIE) is to extract a comprehensive set of facts from natural- llaguage text. Formally, given knowledge base (KB) containing collection of entities & and collection of relations L, the goal is to extract the complete set Yset 6 2 x & of fact triplets from given input text
Grammar. We implement the grammar shown in Fig. 1. Outputs are sets ysei of triplets represented as structured sequences y of tokens. Each triplet consists of subject entity name, a relation name, and an object entity name, each preceded by the special marker [s], [r], or [o], respectively. For

---

instance, the two-triplet set Yse {(Witchita, cast member, John Smith); (Witchita, instance of, film)) is mapped to y = "[s] Witchita [r] cast member [o] John Smith [s] Witchita [r] instance of [o] film". Entity and relation names are restricted to a predefined set of entities (2.7M) and relations (888) from the Wikidata KB (Vrandečié, 2012). The grammar is context-free and allows an arbitrary number of triplets to be generated, including zero.
in the data of Le and Titov (2018)). The constraints imposed by IIG are thus weaker than those of IDG, Moreover, forcing the model via the IDG to repeat the left context (e.g.. "There are two types of elec- tricity:") may guide the model (via conditioning) in generating the correct entity name.
Dataset and evaluation metric. For the ED task, we employ six widely used datasets: AIDA- CoNLL (Hoffart et al., 201 I), MSNBC, ACE2004, AQUAINT, CLUEWEB, and WIKI (Gabrilovich et al., 2013; Guo and Barbosa, 2017). We use only the test data to evaluate the effectiveness of our method in few-shot learning setting. To mea- sure the performance of our approach, we employ micro-accuracy as the evaluation metric. Further details about the datasets and evaluation metric are provided in Appendix D.
Dataset and evaluation metric. We the SynthTE-text dataset (Josifoski et al., 2023), a syn- thetic dataset generated by prompting GPT-3.5. This datasct, in comparison to previous ones like REBEL (Huguet Cabot and Navigli, 2021), is char- acterized by its larger size, increased diversity, and higher quality according to human ratings (Josi- foski et al., 2023). The SynthlE-text dataset com- prises 10K validation samples and 50K test sam- ples. For the purpose of evaluating our method the few-shot scenario, we exclusively employ the test data. We measure performance via triplet- based micro-precision, recall, and Fi-score, follow- ing Josifoski et al. (2022).
3.3 Constituency parsing (CP)
Task description. Constituency parsing (CP) is the task of parsing a sentence into a constituency parse tree capturing the syntactic structure of the sentence.
3.2 Entity disambiguation (ED)
Grammar. The output in CP must be valid-but not necessarily correct--cnssituency parse tree in Penn Treebank format (Sekine and Collins, 2008). A valid parse tree is defined as a tree that satisfies the constraints of completeness (every word in the sentence is included somewhere the parse tree), balanced brackets (every right bracket closes a pre- viously unclosed left bracket, and every left bracket is eventually closed by a right bracket), and label consistency (the label of terminal and non-terminal nodes is consistent with the Penn Treebank format).
Task description. Entity disambiguation (ED) is the task of identifying the exact entity from a pre- defined knowledge base (e.g., Wikidata) referred by a mention demarcated by special tokens in an input text. In certain cases, the input may also contain a set of candidate entities to narrow the search scope.
Grammar. We use grammar of Fig. 2. Fol- lowing De Cao et al. (2021), the output structure consists of the mention followed by the inferred entity name in square brackets. For instance, given the input "There are two types of electricity: <ent> DC </ent> and AC", the output is represented as "There are two types of electricity: <ent> DC
To capture these constraints, we use grammar 3 of Fig. 2. The grammar reproduces the input, rep- resented as sequence = (xo..... -Xa- 1) of words, in left-to-righh order, interspersing it with node la- bels and balanced brackets. In order to guarantee balanced brackets, the non-terminals B count the number of opened left brackets using the sec- ond subscript index j. and the rules ensure that the number of closed brackets can never exceed the number of previously opened brackets. As an ex- ample, for the input "Nkurunziza leads Burundi from Gitega", one valid parse tree would be "[S [NP Nkurunziza] [VP leads [NP Burundi][PP from CNP Gitega]]]]"'
[Direct current] </ent> and AC". The grammar regular and input-dependent. forces the model to generate the mention first, followed by an opening square bracket, an entity name from the candidate set, and finally closing square bracket. The can- didate set is mention-dependee the dataset. To demonstrate the benefits of using an input-dependent grammar (IDG), we also exper- iment with an inptt-indeeendent grammar (IIG). For such a grammar, the candidate set needs to be the entire entity catalog of all entities (e.g., 470K
and is provided in
Note that the grammar in this task needs to be input-dependent due to the aforementioned com-

---

pleteness constraint. To demonstrate this, we also experiment with an input-independent gram- mar, a context-free grammar that recursively gen- erates a parse tree of arbitrary size whose terminal nodes are anonymized as XX. This grammar sat- isfies the balaneed-brackets and label-consistnncy constraints, but not the completeness constraint. As the grammar is context-free, it can generate a parse tree with an arbitrary number of nodes, possibly larger or smaller than the number of words in the input, which would result in an invalid parse tree.
Method
Precision
Recall
Weakly supervised GenlL' T5-base
49.6
26.8 202
34.8 201
Few-shot unconstrained
LLaMA-7B
10.2
14.3207
11,92u5
LLaMA-13B
10.3
17.0z09
12.9.04
LLaMA-33B
14.
23.
17.5+ to
Vicuna-7B
12.5a02
16.7201
14,3202
Vicuna- 13B
13.4a02
15.2402
14.4au2
Few-shot constrained
LLaMA-7B
27. 27.920a
20.2a05
23.5aus
LLaMA-13B
36.2407
26.5.05
30.6.us
LLaMA-33B
39.3209
33.2a
36.0 207
Dataset and evaluation metric. We use the test split of Penn Treebank to evaluate the effective- ness of our method in a few-shot learning setting. Since we observed that the LLaMA models used in our experiments struggle generate fully correct parse trees for long imput sentences, both with and without constraints, we use only sentences with gold parse trees shorter than 64 tokens. We report the bracketing Fi-score returned by the PYEVALB tool as our main evaluation metric. As we observed that LLaMA without constraints often generates invalid parse trees, also report validity (the per- centage of valid parse trees) an additional metric.
Vicuna-7B
25.4200
15.8203
19.5a03
Vicuna-133
38.7=10
19.8208
26.1
Table I: Main results for closed information extrac- tion (4 shots), in terms of precision, recall, and F1 Fl-score (micro-averaged, with 90% confidence intervals) on the SynthlE-text-sman dataset (Josifoski et al., 2023). Best results bold. We report the GenlE model (Josifoski et al., 2022) for the supervised setting.
4.1 Closed information extraction (cIE)
Results for cIE are reported in Table 1. Uncon- strained LLaMA, even with few-shot demonstra- tions, performs poorly on cIE. This is not surpris- ing, since the cIE task requires generating valid entity and relation names from knowledge base (Wikidata in our case). Although LLMs have been exposed Wikidata to certain extent during pre- training, they still struggle with generating accurate entity and relation names contained in the KB. This can be seen as a special case of the hallucination problem, where the model generates entities and relations not present in the KB.
3.4 LLMs and prompting
We utilize LLaMA (Touvron et al., 2023) and Vi- cuna (Chiang et al., 2023) as backbone LMs, with- out performing any finetuning on downstream tasks. Concretely, we evaluate the LLaMA-(7B, 13B, 33B) and Vicuma- (7B, 13B) models. To construct the prompt, we begin by randomly selecting sev- eral data points from the training set and use them manually craft multiple prompts for each task. For more details about the used prompts and the decoding settings, see Appendices and F.
We see a significant improvement when con- straining the generation to only produce valid enti- ties and relations. Notably, LLaMA-33B beats Gen- IE T5-base (Josifoski et al., 2022), state-of-the- art autoregressive model specifically trained for the cIE task on supervised data from the REBEL data- set (Huguet Cabot and Navigli, 2021). In the table, we refer to GenlE as weakly supervised because it was not trained on the train split of SynthTFE-text, but on REBEL. We observe that the grammar-con- strained LLaMA models balance precision vs. re- call better than GenlE, achieving a higher F1-score. While GenlE exhibits higher precision, its recall is lower, implying that it misses many entities and re- lations. This may be because GenlE was optimized for the REBEL dataset and may have memorized the entities and relations in the dataset. As domain- specific training data is often searce (Dunn et al.,
4 Experimental results
Next, we present the results for each task, show- ing that, whereas the unconstrained LLaMA and Vicuna models perform poorly, the grammar- constrained versions perform significantly better. We also show input-dependent grammars to be cru- cial for performance, as they allow the models to adapt the input and generate more accurate out- puts. Out of the tested few-shot-prompted mod- els, ILaMA-33B with input-dependent grammars achieves the best performance on all tasks, even rivaling finetuned models on cIE and ED.

---

Method
AIDA
MSNBC
AQUAINT
ACE2004
CWeh
WIKT
Avg.
Supervised
Le and Titov (2018)
89.6
92.2
90.7
88.1
78.2
81.7
86.8
BLINK candidate set
79.6
80.0
82.5
75.5
77.0
BLINK (Wu et al., 2020)
86.7
90.3
88.9
88.7
86.1
87.2
GENRE only AIDA data
88.6
88.1
77.1
82.3
71.9
71.7
80.0
GENRE (De Cao al., 2021)
93.3
94.3
89.9
90.1
77.3
87.4
88.8
ReFinED w/o pretraining
88.2
92.3
86.8
90.6
75.1
74.5
84.6
ReFinED (Ayoola et al., 2022)
93.9
94.1
90.8
90.8
79.4
87.4
89.4
Few-shol unconstrained
LJaMA-7B
42.0
44.6
30.2
43.8
35.8
27.7
37.4
LIaMA-13B
48.1
50.2
36.2
47.5
40.7
37.2
43.3
LLaMA-33B
62.6
63.0
42.9
56.3
48.1
51.4
54.1
Few-shot constrained (IIG)
LLaMA-7B
56.3
57.3
61.6
54.6
50.5
47.0
54.5
L1aMA-13B
51.8
57.3
53.3
50.8
48.2
39.7
50.6
LLAMA-33B
69.8
73.3
74.9
71.7
61.6
57.6
68.2
Few-shot constrained (IDG)
LLaMA-7B
73.4
87.6
83.2
82.9
69.4
67.1
77.2
LLaMA-13B
75.8
86.6
82.4
84.2
68.1
68.1
77.5
LLAMA-33B
81.0
88.2
86.2
85.4
70.7
70.5
80.3
Table 2: Main results for entity disambiguation (4 shots), in terms of micro-accuracy. Width of 90% confidence intervals is between 0.1 and 0.3 for all results. Best results bold. IIG stands for "input-independent grammar". IDG for "input-dependent grammar".
2022), this result highlights the potential for LLMs excel on cIE without finetuning.
4.3 Constituency parsing (CP)
Results for CP are reported in Table 3. In con- trast to the previous two tasks, the performance of LLMs with or without GCD- on constituency parsing is much worse when compared to bespoke methods. This is not surprising, constituency parsing requires syntactic understanding of the in- put, as opposed the other tasks, which only required semantic understanding. Through error inspection, we found that, although the LLMs are able to generate seemingly reasonable output, their outputs are often syntactically incorrect. (For ex- amples, see Appendix I.)
4.2 Entity disambiguation (ED)
Results for ED are reported in Table 2. Whereas constrained LLaMA models perform poorly, GCD (either input-dependent [TDG] or input-independent [IGG] significantly improves the performance of LLaMA. Although there still a gap with respect to the state-of-the-art model, GENRE (De Cao et al., 2021), grataae- LLaMA-33B performs better than version of GENRE trained only the AIDA dataset (without pretraining on Wikipedia). Considering that many domain- specific information extraction tasks have limited data available (Dunn et al.. 2022), the constrained LLaMA models can thus be a good choice for low-resource settings. Among the GCD-powered LLaMA models, we observe that IDG performs better than IIG, highlighting the benefits of using input-dependent grammar. The latter allows the model to leverage an input-specific candidate set, whereas an input-independent grammar can only use the entire knowledge hase as the candidate set. We believe this flexibility is crucial for GCD to achieve good performance on various tasks.
While overall, LLaMA models perform poorly on CP, the GCD-powered LLaMA models still sig- nificantly outperform the unconstrained LLaMA models. Importantly, with an input-dependent grammar, GCD guarantees that the generated out- put is valid constituency parse tree, which is not the case with input-independent grammar.
In conclusion, GCD substantially improves the performance of LLMs constituency parsing, but performance still falls short of the F1-scores achieved by supervised methods (95% and above). We not, however, rule out the possibility that GCD might produce better results once the under- lying LLMs become more powerfull

---

Method
Validity
Model/task
Latency
Bespoke methods
Unconstrained LLaMA-7B
54
Vinyals al. (2015a)
92.1
98.5
Dyer et al. (2016)
93.3
100.0
Unconstrained LLaMA-33B
87
Kitaey and Klein ()018)
95.6
100.0
Unconstrained LLaMA-65B
136
Zhang (2020)
95.7
100.0
GCD overhead: cIE
69
Few-shot unconstrained
GCD overhead: ED
LLaMA-7B
28.1
54.3
1LLMA-138
42.8
69.4
GCD overhead: CP
4
LLMMA-33B
42.9
64.2
Table 4: Per-token decoding latency (in milliseconds) for unconstrained decoding (top 3 rows, measured on A100 GPU), compared to overhead due to grammar- constrained decoding (bottom 3 rows, measured on con- sumer CPU).
Few-shot constrained (IIG)
LLaMA-7B
34.7
65.9
LLaMA-13B
45.4
80.3
LLMMA-33B
47.1
72.3
Few-shot constrained (IDG)
LLaMA-7B
45.8
100.0
LLaMA-13B
53.4
100.0
put of neural machine translation models is usually an empty string.
I.AMMA33B
54.6
100.0
Table 3: Main results for constituency parsing (8 shots), in terms of bracketing Fl-score and parse- tree validity. For few-shot-prompted LLaMA models, test. set was restricted to gold parse trees shorter than 64 tokens, as LLaMA models perform poorly longer sentences. For bespoke methods, entire Penn Treebank test set was used. Width of 90% confidence intervals between 4.0 and 6.0 for all Fl-scores. Best results in bold.
We hypothesize that the empty-string issue is caused by a likelihood misalignment between the grammar and the language model. We use the cIE task as an example to illustrate the issue. In the case of cIE, the first generated token must either be the left-bracket token "[" or the end-of-sequence token "$" The latter denotes the situation where no triplets can be extracted from the input. With beam size k 2 2, both "[" and "$" will be in- cluded in the beam at the first step. Assume that the likelihood of "[" is p and the likelihood of "s" is q. Since "$" denotes the end of the sequence, this generation is considered as a complete genera- tion with a total likelihood of q. In the other beam, the generation continues with "[" the prefix, but as the generation proceeds, the likelihood of the generation may decrease below q.
4.4 Latency
Incremental parsing imposes additional over- head on top of pure vanilla decoding. To quantify this overhead, we report the latency of pure de- coding and compare it to the added latency due to enforcing grammar constraints Table 4. Note that GCD operates entirely on the CPU, not on the GPU, so GCD latency is measured on a consumer CPU. As shown in Table 4, the added latency from GCD is negligible for the ED and CP tasks. For cIE, GCD adds modest additional latency com- parable or inferior to the latency of pure decoding, depending on the model used (cf. Appendix for more dctails).
Since LLMs such as LLaMA are trained to max- imize the likelihood of human language, the struc- ture imposed by the grammar may be unnatural to the model, especially when the model is not finetuned on the respective task. In the extreme case, the correct ground-truth ttunh output could have a likelihood lower than that of the empty string "s", resulting in the latter being returned as the top generation. This intuition gives rise to a simple fix: penalize the model for generating short strings, e.g., by adjusting the length normalization parameter in the length-adjusted sentence score S/m", where is the unadjusted score for the sentence and is the number of tokens the sentence. As shown in Table 5, this fix indeed solves the problem.
5 Likelihood misalignment in GCD
In the cIE and CP tasks, regardless of model size, the top generation is consistently an empty string (technically, a string "$" consisting of the end-of- sequence token only) and the second most likely generation and subsequent generations are non- empty output sequences. The issue is not unique to particular LLM,, but emerges consistently. is also similar to an observation by Stahlberg and Byrne (2019), who found that the most likely out-
We also observed that the empty-string issue can be alleviated by using instruction-tungr models. While, without applying the aforementioned length normalization fix, LLaMA-13 133 always outputs the

---

Length normalization
1.0
1.5
2.0
2.5
3.0
3.5
Neubig (2017) proposed grammar-powered neu- ral architecture for general- code genera- tion. Shin et al. (2021) proposed to use grammar- constraints to solve semantic parsing tasks with GPT-3 and envisioned that a semantic parser can be built by combining a large language model with carefully designed grammar. Roy et al. (2022) re- leased toolkit for grammat--cossrraneed decoding to generate valid meaning representations. Finally, Stengel-Este -ssin et al. (2023) tested the ability of LLMs to solve parsing task under ambiguity and used grammar constraints to ensure the grammati- cality of the output.
Top generation = "
x
x
x
Length normalization mitigates the empty- string issue: larger favors longer sequences and = 0 means no effect (results for LLaMA-13B).
Table 5:
empty string "$" as its top generation on the cIE task, the instruction-tunet version Vicuna-13BB outputs non-empty oulput its top generation only 46% of the time. (The smaller Vicuna-7B, however, still always outputs "$" as its top generation.)
6 Related work
Autoregressive structured prediction in NLP. It has become popular to autoregressive genera- tive models for structured prediction tasks, this fits the training mode and specific strengths of lan- guage models (Vinyals et al., 2015b; Athiwaratkun et al., 2020; De Cao et al., 2021; Paolini et al., 2021). For instance, Vinyals et al. (2015b) mod- eled dependency parsing as a sequence generation problem and leveraged LSTMs to tackle it effec- tively. De Cao et al. (2021) proposed autoregressive language models to address entity linking, entity disambiguation, and document retrieval tasks.
Conclusion
This work introduces grammar-conssrained decod- ing (GCD) for enhancing the few-shot performance of LLMs on challenging structured NLP tasks. We showed that many NLP tasks can be formulated as formal grammars, and that GCD can enhance the performance of LLMs on these tasks. With input- dependent grammars, we further broaden the scope of GCD to accommodate tasks where the set of valid output structures is constrained by the given input. Our experiments indicate that, whereas un- constrained LLMs have difficulty tackling tasks requiring structured outputs, GCD can significantly bolster the performance of LLMs such tasks. We envision GCD swift and cost-efficient adupta- tion strategy, allowing LLMs to generate reliable structured outputs without the necessity for costly and cumbersome finetuning. Given the fast pace of LLM evolution, we anticipate the usefulness of GCD for boosting pretrained LLMs to further increase over time.
Constrained decoding. For tasks where the out- put needs satisfy certain constraints, constrained decoding has been proposed to guide the genera- tion process to produce valid outputs. For instance, Hokamp and Liu (2017); Hu et al. (2019); Post and Vilar (2018) proposed lexically-oonstrained se- quence decoding for generation tasks. Anderson et al. (2017) extended the beam search algorithm by pruning the search space based on constraints. Scholak al. (2021) leveraged an incremental pars- ing technique to generate approximately valid SQL queries. De Cao et al. (2021) addressed entity dis- ambiguation with trie-based lexical constraints at decoding time to force outputs to be valid entities. Josifoski et al. (2022) addressed closed informa- tion extraction by combining trie-based lexical con- straints with state-based constraints to force the out- put to be valid triplet sequences. Wang et al. (2023) used Earley parser-based constraints force out- puts to lie in a domain-specific language.
Best practices for GCD. We conclude with con- siderations regarding the effective use of GCD.
1. GCD is more effective with larger LLMs. When possible, use the largest available LLM.
2. Grammars should be restrictive as possible. Consider using input-dependent grammars.
3. While GCD is broadly applicable to many tasks, is not a silver bullet. Tasks that require syntactic understanding of the input (e.g., con- stituency parsing) are less suitable for GCD,
Grammar-constraines decoding. Deutsch al. (2019) proposed a general framework for push- down buse constraints and applied it to parsing tasks, which is equivalent to CFG-based constraints in terms of expressiveness. Yin and
4. In the presence of task-specific training data, finetuning a small model may still yield better performance, at the cost of decreased conve- nience (cf. Appendix A).

---

Limitations
Ben Athiwaratkun, Cicero Nogueira dos Santos, Jason Krone, and Bing Xiang. 2020. Augmented natu- ral language for generative sequence labeling. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 375-385, Online. Association for Computa- tional Linguistics.
Compatibility with API-based LLMs. GCD works by modifying the decoding process of an LLM. If the LLM is hosted in the cloud (as is the case for OpenAT's GPT series) and the API does not provide user control over the decoding process, GCD cannot be used.
Tom Ayoola, Shubhi Tyagi. Joseph Fisher. Christos Christodoulopoulos, and Andrea Pierleoni. 2022. Re- FinED: An efficient zero-shot-capable approach to end-to-end entity linking, In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Industry Track, pages 209- 220, Hybrid: Seattle, Washington Online. Associa- tion for Computational Linguistics.
Latency. The introduction of constraints into the generation process increases latency. The extra overhead of GCD is introduced by the completion step where the next allowed token is determined based on the current prefix and the grammar. The speed of the completion step depends on the com- plexity of the grammar and the parsing algorithm of the underlying completion engine. In case the grammar is simple, we do not observe signifi- cant increase in latency (the overhead is negligible compared to the latency of the LM). However, in case the grammar contains large number (e.g., millions) of rules, such the grammar for the cIF task, the latency of the incremental parsing step grows. (See results in Table 4.)
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neclakantan, 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.
Acknowledgements
Wei-L.in Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang. Yonghao Zhuang. Joseph E. Gonzalez, lon Stoica, and Eric P. Xing. 2023. Vicuna: An open- source chatbot impressing gpt-4 with 90%* * chatgpt quality.
We thank Viktor Kunčak and Chris Wendler for insightful discussions and suggestions, well the Grammatical Framework community, espe- cially Inari Listenmaa, for answering our questions. We also thank Zheng Zhou and Yifei Li for their help setting up the infrastructure for the experi- ments. West's lab is partly supported by grants from Swiss National Science Foundation (200021_- 185043), Swiss Data Science Center (P22_08), H2020 (952215), Microsoft Swiss Joint Research Center, and Google, and by generous gifts from Facebook, Google, and Microsoft.
Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni. 2021. Autoregressive entity retrieval.
Daniel Deutsch, Shyam Upadhyay, and Dan Roth. 2019. A general-purpose algorithm for constrained sequen- tial inference. In Proceedings of the 23rd Confer- ence on Computational Natural Language Learning (CoNLL)), pages 482-492, Hong Kong, China. Asso- ciation for Computational Linguistics.
Alexander Dunn, John Dagdelen, Nicholas Walker, Sanghoon Lee, Andrew S. Rosen, Gerbrand Ceder. Kristin Persson, and Anubhav Jain. 2022. Structured information extraction from complex scientific text with fine-tuned large language models.
References
Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2017. Guided open vocabulary im- age captioning with constrained beam search. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 936- 945, Copenhagen, Denmark. Association for Compu- tational Linguistics.
Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros. and Noah A. Smith. 2016. Recurrent neural network grammars.
Evgeniy Gabrilovich, Michael Ringgaard, and Amarnag
Subramanya. 2013. Faccl: Freebase annotation of clueweh corpora, version (release date 201 2013-06-26 format version 1, correction level 0).
Krasimir Angelov. 2009. Incremental parsing with par- allel multiple context-free grammars. In Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009), pages 69-76, Athens, Greece. Association for Computational Linguistics.
Octavian- Ganea and Thomas Hofmann, 2017. Deep joint entity disambiguation with local neural attention.

---

Zhaochen Guo and Denilson Barbosa. 2017. Robust named entity disambiguation with random walks. Se- mantic Web, 9:1-21.
Nikita Kitaev and Dan Klein, 2018. Constitueney pars- ing with a self-attentive encoder.
Phong Le and Ivan Titov. 2018. Improving entity link- ing by modeling latent relations between mentions. In Proceedings of the 56th Annual Meeting of the Association for Compulational Linguisties (Volume I: Long Pupers), pages 1595-1604, Melbourne, Aus- tralia. Association for Computational Linguistics.
Johannes Hoffart, Mohamed Amir Yosef, Iariia Bordino, Hagen Fürstenau, Manfred Pinkal, Mare Spaniol, Bilyana Taneva Stefan Thater, and Gerhard Weikum. 2011. Robust disambiguation of named entities in text. In Proceedings of the 2011 Conference Em- pirical Methods in Natural Language Processing, pages 782-792, Edinburgh, Scotland, UK. Associa- tion for Computational Linguistics.
Giovanni Paolini, Ben Athiwaratkun, Jason Krone, JIE MA, Alessandro Achille, Rishita Anubhai, Ci- cero Nogueira dos Santos, Bing Xiang, and Stefano Soatto. 2021. Structured prediction as translation be- tween augmented natural languages. In ICLR 2021.
Chris Hokamp and Qun Liu. 2017. Lexically con- strained decoding for sequence generation using grid beam search. Proceedings of the 55th Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pages 1535-1544 1546, Vancouver, Canada, Association for Computational Linguistics.
Gabriel Poesia, Oleksandr Polozov, Vu Le, Ashish Ti- wari, Gustavo Soares, Christopher Meek, and Sumit Gulwani. 2022. Synchromesh: Reliable code genera- tion from pre-trained language models.
Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang. and Weizhu Chen. 2021. Lora: Low-rank adaptation of large language models.
Matt Post and David Vilar. 2018. Fast lexically con- strained decoding with dynamic beam allocation for neural machine translation. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Hu- mun Language Technologies, Volume 1 (Long Pu- pers), pages 1314-1324, New Orleans, Louisiana. Association for Computational Linguisties.
J. Edward Hu, Huda Khayrallah, Ryan Culkin, Patrick Xia, Tongfei Chen, Matt Post, and Benjamin Van Durme. 2019. Improved lexically constrained decoding for translation and monolingual rewriting. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies, Volume I (Long and Short Pupers), pages 839-850, Minncapolis, Minnesota. Association for Computa- tional Linguisties.
Alec Radford, Jeff Wu. Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners.
Colin Raffel, Noam Shazeer, Adam Roberts. Katherine Lee, Sharan Narang. Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2019. Exploring the limits of transfer learning with a unified text-to-text trans- former. CORR, abs/1910.10683.
Pere-Lluis Huguet Cabot and Roberto Navigli. 2021. REBEL: Relation extraction by end-to-end language generation. In Findings of the Association for Com- putational Linguistics: EMNLP 2021, pages 2370- 2381, Punta Cana, Dominican Republic. Association for Computational Linguistics.
Aarne Ranta. 2019. Grammatical framework: an inter- lingual grammar formalism. In Proceedings of the 14th International Conference on Finite-State Meth- ods and Natural Language Processing, pages 1-2. Dresden, Germany, Association for Computational Linguistics.
Bernal Jimenez Gutierrez, Nikolas McNeal, Clayton Washington, You Chen, Lang Li, Huan Sun, and Yu Su. 2022. Thinking about GPT-3 in-context learn- ing for biomedical IE? think again. In Findings of the Association for Computational Linguistics: EMNLP 2022, pages 4497-4512, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
Subhro Roy, Sam Thomson, Tongfei Chen, Richard Shin, Adam Pauls, Jason Eisner, and Benjamin Van Durme, 2022. Benchclamp: A benchmark for evalu- ating language models on semantic parsing.
Martin Josifoski. Nicola De Cao, Maxime Peyrard, Fabio Petroni, and Robert West. 2022. GenlE: Gen- erative information extraction. In Proceedings of the 2022 Conference of the North American Chap- ter of the Association for Computational Linguistics: Human Language Technologies, pages 4626-4643, Seattle, United States. Association for Computational Linguistics.
Timo Schick and Hinrich Schütze. 2021. Exploiting cloze-questions for few-shot text classification and natural language inference. In Proceedings of the 16th Conference of the European Chapter of the Asso- ciation for Computationll Linguistics: Main Volume, pages 255-269, Online. Association for Computa- tional Linguistics.
Martin Josifoski, Marija Sakota, Maxime Peyrard, and Robert West. 2023. Exploiting asymmetry for syn- thetic training data generation: SynthlE and the case of information extraction. arXiv preprint arXiv:2303.04132.
Torsten Scholak, Nathan Schucher, and Dzmitry Bah- danau. 2021. PICARD: Parsing incrementally for constrained ruto-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, Domini- can Republic. Association for Computational Lin- guistics.
Denny Vrandečié. 2012. Wikidata: new platform for collaborative data collection. In Proceedings of the 21 International Conference World Wide Web, WWW '12 Companion, pages 1063-1064, New York, NY, USA. Association for Computing Machinery.
Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. 1991. On multiple context-free gram- mars. Theoretical Computer Science, 88(2):191-229
Bailin Wang. Zi Wang, Xuezhi Wang. Yuan Cao, Rif A. Saurous, and Yoon Kim. 2023. Grammar prompting for domain specciii language generation with large language models.
Satoshi Sekine and Michael Collins. 2008.
Evalh:
Bracket scoring program.
Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016. Neural machine translation of rare words with subword units. Proceedings of the 54th Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pages 1715-1725, Berlin, Germany, Association for Computational Lin- guistics.
Ledell Wu, Fabio Petroni, Martin Josifoski, Sebastian Riedel, and Luke Zettlemoyer. 2020. Scalable zero- shot entity linking with dense entity retrieval. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6397-6401 Online. Association for Computa- tional Linguistics.
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 feot semantic parsers. In Proceedings of the 2021 Conference on Empirical Methods in Natu- ral Language Processing, pages 7699-7715, Online and Punta Cana, Dominican Republic, Association for Computational Linguistics.
Pengcheng Yin and Graham Neubig. 2017. A syntactic neural model for general-purpose code generation. In Proceedings of the 55th Anmual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 440-450, Vancouver, Canada. Association for Computational Linguisties.
Zhang, Houquan Zhou, and Zhenghua Li. 2020. Fast and accurate neural CRF constituency parsing, In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organi- zation.
Felix Stahlberg and Bill Byrne. 2019. On NMT search errors and model errors: Cat got your tongue? In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Lan- guage Processing (EMNLP-IJCNLL pages 3356- 3362, Hong Kong, China. Association for Computa- tional Linguistics.
Elias Stengel- Eskinn Kyle Rawlins, and Benjamin Van Durme. 2023. Zero and few-shot semantic parsing with ambiguous inputs.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux. Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro. Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023, Llama: Open and efficient foundation language models.
Roy Tromble and Jason Fisner. 2006. A fast finite-state relaxation method for enforcing global constraints sequence decoding. In Proceedings of the Hu- man Language Technology Conference of the NAACL, Main Conference, pages 423-430, New York City, USA. Association for Computational Linguisties.
Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015a. Gram- mar foreign language.
Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Nlya Sutskever, and Geoffrey Hinton. 2015b. Gram- mar foreign language. In Advances in Neural Information Processing Systems, volume 28, Curran Associates, Inc.

---

A Fine-tuning GCD
Expensive, Delicious, Boring Quality
Listing I: The abstract syntax of the Food grammar.
is worth considering whether to prefer fine-tuning or GCD to adapt LLMs to structured prediction tasks. Fine-tuning can be applied to either small model, such as T5 (Raffel et al., 2019), or directly large model, like LLaMA (Touvron et al., 2023). There are three crucial factors take into account:
B.1 Abstract Syntax vs. Concrete Syntax
Constrained decoding works by pruning the set of allowed tokens-id at each decoding step. This requires that both the grammar and the comple- tion engine work at the token-id level. Since the tokenization scheme LMs are usually different from each other, the grammar becomes dependent on the tokenization scheme the LM. This brings two challenges: (1) the grammar needs to be re- defined for each LM (tokenization scheme), and (2) the debugging of the grammar is difficult be- cause the grammar is defined the token-id level. We propose to decouple the grammar from the tok- enization scheme of the LM by defining an abstract grammar and a couple of concrete grammars. The abstract grammar is defined at the text level, which is human-reate readalee and independent of the tokeniza- tion scheme of the LM. The concrete grammars are defined at the token-id level, which are depen- dent on the tokenization scheme of the LM and work with the completion engine. Once abstract grammar is defined, the concrete grammars can be automatically translated from the abstract gram- mar. This similar to the process of compiling a high-level programming language to a low-level assembly language. The separation of the abstract grammar and the concrete grammar is implemented in GF. For example, the predication rule Pred. Comment ::= Item "is" Quality
1. availability of training data,
2. computational cost of fine-tuning, and
3. performance improvement.
Constrained decoding eliminates the need for train- ing data and incurs only the computational cost of running the LM, with small overhead coming from the incremental parser. Fine-tuning small model is affordable and currently represents the state-of- the-art (SOTA) approach for most structured pre- diction tasks when training data is available (De
Cao et al.. 2021; Jimenez Gutierrez et al., 2022). However, it necessitates a substantial amount of data. Although fine-tuning large model is ex- pensive, it is highly data-efficient (Brown et al., 2020). However, recent advancements in efficient fine-tuning of large models (Hu al., 2021) have significantly reduced the computational cost and hardware requirements. We view GCD as a rapid and cost-effective adaptation strategy that enables LMs to produce reliable structured outputs without the need for fine-tuning
B Grammatical Framework
Listing 2: BNF Notation
Grammatical Framework (GF) is programming language for multilingual grammar applications. is a special-purpose language for grammars, like YACC, Bison, Happy, BNFC, but not restricted programming languages. It is a functional pro- gramming language, like Haskell, Lisp, OCaml, SML, Scheme, but specialized to grammar writing. For example, the following is a GF grammar to generate simple English sentences about food:
now becomes two rules:
Pred Item -> Quality Comment
lin Pred item quality item ++ "is" quality.
Listing 3:
Grammatical Framework Notation
All that matters in linearization rule is that defines string a function of the variables that depends on. A GF grammar consists of two parts: abstract syntax and concrete syntax.Below Below the concrete syntax the aforementioned Food grammar:
abstract Food {
flags startcat Comment
cat
Comment Item ; Kind Quality
fun
Pred Item -> Quality -> Comment
concrete FoodEng of Food lincat
This, That Kind -> Item ;
Mod : Quality -> Kind -> Kind
Comment, Item, Kind, Quality = Str.
Wine, Cheese, Fish Kind ;
lin
Very Quality -> Quality
Pred item quality item + "is"
Fresh, Warm, Italian,
++ quality ;
}
This kind "this" ++ kind

---

That kind "that" kind Mod quality kind quality kind Wine "wine"
C IE Task Settings
We use the same KB as in (Josifoski et al., 2023), which contains 2.7M entities and 888 relations from the WikiData KG (Vrandečié, 2012). We use SynthIE-text dataset (Josifoski et al., 2023), synthetic dataset for the IE task generated from prompting GPT3.5 model. This dataset consists of 10K validation and 50K test samples. was shown to have a better quality than the widely used REBEL dataset (Huguet Cabot and Navigli, 2021).
Cheese "cheese".
Fish "fish"
Very quality "very" quality Fresh "fresh"
Warm "warm"
Italian "Italian"
Expensive = "expensive"
Delicious = "delicious"
Boring = "boring"
}
Listing 4: The concrete syntax of the Food grammar.
D ED Task Settings
And also the concrete syntax of the Food gram-
mar in Italian:
Dataset Preprocessing. Typically, solving the ED task requires contextual information. However, through our observations, we have noticed that the performance of Language Models (LMs) tends to degrade when exposed to long contexts. To miti- gate this issue, we have limited the left and right context surrounding the mention to only 10 tokens each.
concrete FoodIta of Food
lincat
Comment, Item, Kind, Quality str lin
Pred item quality item ++ "e"
quality
This kind "questa" kind
That kind "quel" kind Mod quality kind kind quality Wine "vino"
Cheese "formaggio"
Out of Knowledge Base Mention. It's important to note that some of these datasets contain men- tions that are not present in the knowledge base (YAGO (B) To ensure consistency and accuracy. filter out these mentions, exclusively utilizing the ones that available. We report the number of data points whose target entity is not in the knowl- edge base. These data points are filtered out in the experiments with input-independent grammar.
Fish "pesce"
Very quality "molto" quality
Fresh "fresco"
Warm "caldo"
Italian "italiano"
Expensive = "caro"
Delicious "delizioso"
Boring = "noioso"
}
Listing The concrete syntax of the Food grammar in Italian.
AIDA-CONLL: 0 out of 4485
B.2 Multilingual Grammars
ACE2004: 0 out of 257
A multilingual grammar a system with one ab- stract syntax and any number of concrete syntaxes. While GF was originally designed for machine translation, it happens to be well suited to han- dle multi-tokenizzaiinn.. Different large language models have different tokenizers. For the same sentence, their representations in token id space are different. This phenomenon is very similar to the multilingual grammar scenario, where the same abstract syntax tree can be linearized into different languages as shown in in the Food grammar.
AQUAINT: 4 out of 727
ClueWeb: 12 out of 11154
MSNBC: out 656
Wikipedia: 23 out of 6821
In the experiments with input-dependent gram- mar, also filter out the data points whose candi- date set empty.
B.3 Expressivity
AIDA-CONLL: 0 out of 4485
Grammatical Framework (GF)'s incremental parser, supports PMCFG (Parallel Multiple Context-Free Grammars). PMCFG lies between mildly context-sensitive and fully context-sensitive grammars (Seki et al., 1991).
ACE2004: 17 out of 257
AQUAINT: 24 out of 727
ClueWeb: 44 out of 114

---

MSNBC: 5 out of 656
is text and the output is a of triples in subject- collapsed format. A concrete example would be: Vettaikaaran (2009 film) was originally written in the Tamil language, with В. Babusivan as the screenwriter. >> [s] Vettaikaaran language of film or TV show [o] Tamil_ Lamil__anguage [r] screenwriter [o] B._- Babusivan [e]
Wikipedia: 7 out of 6821
UnssemMMentiontkkklnnnnNNDDDDDD 1 114 out of
10000
[r] original
Metrics. Many previous works (De Cao et al.. 2021; Ganea and Hofmann, 2017; Ayoola et al., 2022) report the micro-averaged Fl score from Ger- bil evaluation tool. In approach, always take the top-1 prediction as the final prediction. Since each mention is only associated with one target entity, the micro-averaged score is equivalent to the accuracy in this case (accuracy = precision = recall = F1) We report the accuracy as the evalua- tion metric for the ED task and didn't 't use Gerbil evaluation tool.
F.2 Entity Disambiguation
We show two prompt construction methods for en- tity disambiguation.
Prompt construction A. The instruction is Disambiguate the entity surrounded by [START_ENT] and [END_ENT] by giving the correct entity name in the knowledge base. We randomly select some demonstration examples from the training set. We use the following for- mat to represent the demonstration examples as a string: [input] -> [mention] [ [target entity] 1, where the input is a text, the mention is the entity mention surrounded by [START [NT] and [END_ENT], and the target entity is the entity name in the knowledge base. A concrete exam- ple of demo example representation would be: Eu rejects [START_ENT] German [END_ENT] call boycott British 1amb Peter Blackburn Brussels 1996 08 German [ Germany ] The final prompt is a concatcnation of the instruction and the demonstration examples. A full prompt with 2 demo examples would be:
E Prompt Construction
In this section, we provide more details on the prompt construction process. The prompt used in our experiments is composed of two parts:
1. instruction: short sentence that describes the task.
2. demonstration examples: set of examples that demonstrate the expected behavior of the model.
We observe that the performance of the model is sensitive to the wording of the instruction and the format of the demonstration examples. To find a good instruction and demonstration examples, we first manually construct a set of instructions and demonstration formats. Then, we randomly sample few demonstration examples from the training set and manually check whether the model solve the task with the given instruction and demonstration examples. This process helps us find a good instruction and demonstration format, thought probably not the best. Since our goal is not to find the best instruction and demonstration format, we didn't spend too much time on this process. Below, we provide more details on the prompt construction process for each task.
Disambiguate the entity surrounded by [START_ENT] and [END_ENT] by giving the correct entity name in the knowledge base: "Eu rejects [START_ENT] German [END_- ENT] call boycott British 1amb Peter Blackburn Brussels 1996 08" -> German Germany ]; 16 other items that were put up for auction by [START_ENT) Hendrix [END_- ENT] former girlfriend Kathy Etchingham >> Hendrix [ Jimi Hendrix ]; lead with well struck header in the seventh minute [START_ENT] Japan [END_ENT] then laid siege to the Syrian penalty area for most
E.1 Information Extraction
Prompt construction B. The instruction is: Disambiguate the entity surrounded by [START_ENT]] and [END_ENT] by giving the canonical entity name in the knowledge base:. The demonstration examples are in the
The instruction used is Extract the triples in subject-collapser format from texts below. The demonstration examples are in the following format: [input] -> [output], where the input

---

following format: [input] [mention]
The dollar weakened against most other major currencies
[target entityl 1, where the input is a text, the mention the entity mention surrounded by and the target entity is the canonical entity name in the knowl- edge base. A concrete example of demo ex- ample would be: "Eu rejects [START_ENT] German [END_ENT] call to boycott British 1amb Peter Blackburn Brussels 1996 08
( S ( NP-SBJ ( DT
The ) ( NN dollar
( VP ( VBD weakened
[START [START_ENT] and
) ( PP ( IN against ) ( NP ( RBS most (
JJ other ) ( JJ major ) ( NNS currencies
) ) ) 1, where the corresponding parse tree
is shown in Listing 6.
Listing parse tree with hierarchical indentation
-> German Canonical form Germany
S
] full prompt with demo examples would be: Disambiguate the entity surrounded by [START_ENT]] and [END_ENT] by giving the canonical entity name in the knowledge base: "Eu rejects [START_ENT] German [END_ENT] call to boycott British lamb Peter Blackburn Brussels 1996 08 -> German
( NP-SBJ
DT The )
NN dollar
( VP
VBD weakened )
PP
IN
against
( NP
Canonical form Germany 16 other items that were put up for auction by [START_ENT] Hendrix [END_ENT] s former girlfriend Kathy Etchingham -> Hendrix Canonical form [ Jimi Hendrix ] lead with a well struck header in the seventh minute [START_ENT] Japan [END_ENT] then laid siege to the Syrian penalty area for most ->
RBS most
JJ other
JJ major
NNS currencies
One variant the prompt is to provide a rea- soning chain with the demonstration examples. A concrete example would be:
Prompt used in each dataset We compare the performance of the two prompts in each dataset over the validation set. We select the prompt that performs the best in each dataset. The prompt used in each dataset is shown in Table 6.
"The constituency parse tree is: ( S ( NP-SBJ ( NN Bond ( NNS prices ( VP VBD were ) ADJP-PRD RB barely ( JJR higher
"S: This stands for Sentence, the top-level structure in the parse tree." " "NP-SBJ: This the subject noun phrase of the sentence, which is 'Bond prices'." "NN: This stands for Noun, Singular or Mass. In this case, the word 'Bond' falls into this category."
Dataset
Prompt
AIDA
Prompt
MSNBC
Prompt 2
AQUAINT
Prompt 2
ACE2004
Prompt 2
CWEB
Prompt
"NNS: This stands for Noun, Plural. The word 'prices' is an example of this."
WIKI
Prompt
Table Prompt used in each dataset
"VP: This stands for Verb Phrase, which in this case is 'were barely higher'."
"VBD: This stands for Verb, Past Tense. The word 'were' falls into this category." "ADJP-PRD: This stands for Adjective Phrase, used as predicate. The phrase 'barely higher' is an example of this." "RB: This stands for Adverb. The word 'barely' falls into this category." "JJR: This stands for Adjective, Comparative. The word 'higher' falls into this category."* "M
E.3 Constiutency Parsing
The instruction is: Perform constituency parsing on the provided sentences in accordance with the Penn TreeBank annotation guidelines.. The demonstration examples are in the following format: [input] -> [output], where the input a text and the output is the flattened constituency parse tree. A concrete example would be:

---

SynthlE-text
improvement over the unconstrained decoding ap- proach for LMs of all sizes. Compared with the results Table 7, the performance of the subject- collapsed linearization is indeed lower than the fully-expanded linearization.
Method
Precision
Recall
Fl
Few-shot Unconstrained
ILLMA-7B-SS (4 shols)
9.7
8.6
9.2
LLaMA-13B-S3 (4 shots)
6.7
12.5
8.7
LLaMA-33B-sc (4 shots)
10.6
20.6
14.0
Adding all relations to the prompt. With a maximum context length of 2048 tokens, it's not possible to add all the millions of entities to the prompt. However, we can add all the relations to the prompt, which is much smaller set (888 rela- tions). One may wonder if adding all the relations to the prompt would help the model learn the relation extraction task better. Because the model can copy the relation from the prompt and this may make the task casier. However, we find that adding all the relations to the prompt does not help the model to learn the relation extraction task better. Table 8 shows that adding all the relations to the prompt only brings small improvement over the
Few-shot Constrained
LLaMA-7B-se shots)
19.3
21.5
LLaMA-13BB 13B--c (4 shots)
26.4
30.5
28.3
LLaMA-33B-sc (4 shots)
31.3
36.2
33.6
Table 7: Results for eIE with subject-collapsed lin- carization.
SynthTE-text
Method
Precision Recall
Supervised GenlE T5-base-fe (Josifoski et al., 2022)
49.1
26.7
34.6
Few-shor Unconstrained
LLaMA-7B-fcR shots)
11.4
LLaMA-13B-IeR (4 shots)
10.8
17.5
13.4
LLaMA 33B faR (4 shots)
14.0
22.5
17.3
Vicuna 13B FeR shots)
12.5
16.7
14.3
baseline.
Fewsshot Construined
Constituency Parsing with Vicuna.
We also eval-
LLaMA
shots)
28.1
LLMMA-13--fR shots)
31.8
31.2
31.5
Method
Precision
Recall
Tag Accuracy
Validity
LLMMA-33B-fRR (4 shots)
36.4
34,8
35.6
Vicuna-13BB 13B-feR (4 shots)
40.3
23.8
29.9
Unconstrained
Vicuna-7B
13.5
12.7
27.8
42.2
Table 8: Results for cIE with all relations added to the prompt. feR stands for fully-expanded linearization with relations added the prompt.
Vicuna-13B
31.6
28.1
29.6
51.4
Constrained IIG Vicuna-7BB
17.4
16.3
30.5
54.3
Vicuna- 13B
30.8
27.7
33.4
56.1
Decoding Settings
Constrained IDG Vicuna-7B
35.6
31.9
41.4
100.0
We employ constrained beam search during our ex- periments, with a beam size of 2 and length penalty 1.0. Our choice of a small beam size is based on our observation that larger beam sizes do not yield significant improvement and may even result in de- creased performance. In contrast, a beam size of 2 proves to be sufficient for achieving good results while also being computationally efficient. When evaluating the generated outputs, we select the most probable non-empty generation as the output.
Vicuma-13B
51.6
44.4
42.4
100.0
Table 9: Constituency parsing results with Vicuna. The experiments setting is the same in Table 3.
uate the constrained decoding approach on the con- stituency parsing task with the instruction-tune model Vicuna. Table 9 shows Vicuna's perfor- mance is even worse than the LLaMA model.
H Latency
G Additional Experimental Results
Here's concise table comparing the latency of pure decoding to the additional delay introduced by grammar constraints.
G.1 Information Extraction
Subject-Collapsed Linearization. Subject- collapsed linearization is variant of linearization where the subject is collapsed into the object. It has the advantage of being more compact (token efficient) than the fully-expanded linearization, but it yields slightly lower performance, intuitively be- cause it's less explicit. Table 7 shows that the constrained decoding approach brings a significant
Latency for IE. We provide a measurement of la- tency for IE task in Figure 3 and Figure 4. We con- sider two large grammars, the WikiNER grammar and the REBEL grammar. The WikiNER gram- mar contains 279 K entities and 158 relations. The REBEL grammar contains 5.9 M entities and 857 relations. Given the grammar, we randomly pick the next token from the set of next allowed tokens

---

with the end-of-sentence token excluded to avoid early termination. The incremental parsing step is done on CPU and we do not use any optimization techniques such as multi sultiithreading.
the instruction. The generation the left is from Vicuna-13B and the generation the right is from LLaMA-13B. The majority of the erroneous output sequences contain unbalanced brackets and length missatch(missing words or extra words from the input sentence).
time complexity
Infertetiens
0.00
200
400
600
800
1000
preetix lengthiie taoken)
Figure 3: latency of WikiNER grammar
time complexity
Average
3.5
25-
V
2.0
1.5
1.
0.0
300
400
800
1000
pretol bengghhe talker))
Figure 4: latency of REBEL grammar
As shown in Figure 3s, the latency for WikiNER grammar (0.05s) comparable the latency of the LM on GPU. However, the latency for the REBEL grammar (0.5s) is significantly higher than the la- tency of the LM. We believe this can largely improved by using more appropriate incremental parser and leave it as future work.
I Error Examples of Constituency Parsing
Here we give examples of using LMs to perform CP in free-form generation setting. We show some output examples' of LLaMA-13B and Vicuna-13B CP Penn Treebank (PTB). We that while instruction-tuned LMs (Vicuna-13B) can generate scemingly reasonable parse trees, most of them are not correct. On the other hand, base LMs (LLaMA-13B) almost completely fail to follow
'Tee visualisation are made from https://chat. Imsys
org/

---

Hoddl
soota
our cilluann parningg surkerus Lofion Theustppdi aho sureeru words the iepat, No repeated words are all allowed the ouggut The brackets should be belonced.
Thar shouldluus Uhrauese words the input io regrated words are alloweed in sutpur. The bradiets should be balonced.
flannn passin
vaares pant ppesinne
period
The auppyye shid grodlns prices down init
1 iun-snu Err The merees ( seuuuppety wP (D0D 2 HP (nN grestise Mass (NDV RP down PRITMI that perfod
C4 (an-dau DI The moneae civts supply o 1971 1300 puiched 1 IN poosline) (AP d TMP (M
How the burtom offihee heap
now we "e ac bottonn ohe heap
[ (URS M NAPTUP (NN 1 heap I (VED ava H99h-1ee WBC a INP-TMIPNI teP (eG 101
neatoon
S an "san) the (ven-nan: trec bottone i of's HNs 1he 1 (VEN vrac is) mrre. TMP: IN (h (MP (Melbuuto io MMS heap 13333933
bottons INP
Figure 5: Example of 1 shot CP on PTB instance No.12 The golden parse tree is "( S (DVP--MM RB Now (NP-SBJ PRP we VP VBP 're PP-LOC-PRD IN at ) NP NP ( DT the ) NN bottom ) ) PP IN of ( NP ( DT the ) NN heap )) ) )" The generation from Vicuna- 13B correct, but it still looks like reasonable parse tree. The generation from LLaMA- 13B fails to follow the instruction.
Glew comiitoency parving ventercn belooe The es of hove numbhrr of words the input repeated words allowed surput. brackess balknardd
Give luancc persing for thr thwoentance, belon, the ourgut hould have thwoume nann as thpu repeated allowedie spoc The choukttshhoo Ialanead.
"he excees supply pucteed grootine prices down in that poriod
The excass supoly pusted goool prices down phried
F 2 wor supery 11 (oRn parted goooloen) prikas)) A sP Jownn 1 pest (IN ( thetl IN uNiuwidd 11103
cun 1 I ewsess) exppty purtortt MR goollnne now 111 ADVF (IP d 2 LV9-1ee (Nin) (KP/ Use.) perid)
Now the heap
Now bottorn hoop
115 SC (MN (182 TMP LI we MMP TMP IM 1 TMP | HMM-TMH
Hure everyy coneoraaiiooo wi the humnnr.
(SP (113)10)
TD ls better
Di better
Th+
Doth ane bad
Figure 6: Example of shot on PTB instance No.12 The golden parse tree is "( S (ADVP-TMP RB Now )
NP-SBJ PRP we ) ( VP VBP 're ( PP-LOC-PRD IN ) NP ( NP ( DT the ) NN bottom ( PP ( IN of NP ( DT the ) NN heap) ) ) J" The generation from Vicuna-133 13B looks reasonable, but its bracketing is actually unbalanced. The generation from [LLMA- fails to follow the instruction.

---

consthuency y pars 'g an the lopan. to reposted wordh alloowe the sutpurt The hrnccbens shocll be belanced
oupuu
condtranncy pansing tiriggteeet words an the ispen. Ho repaotedd worth are alloowed in serpust The bomeletts should bolanood
outpur
The pashed pookinw prices down that serked
The voon paoded paoliiw down in paried
115 INndaL (or The (:A eacees y IVl wapply 1 unO pusteed 1 HP greciine 10M5 period (113)
51 iisoau or The I vazees (KV supply 1 puotheeee RP (ss, geactiie MIMS ADMI
nP down
perlod
Nowreo ohe bonsee of heop
How we no octhe botcm the
It's pe (S0 now! (Bu(o) (nve MePs IMe (Vies tenrim
coces supply pusted gaooline prices dius perlod
the battom)))1 (VD0 (v20 TMP ves (NaP (NP)) IV the Wil h100
Figure 7: Example of 1 shot CP PTB instance No.12 The golden parse tree is "( S ADVP-TMP RB Now NP-SBJ( PRP we ) ( VP VBP 're ( (PP-LOC-PRD) IN at ) NP NP DT the ) NN bottom )) PP IN of NP DT the ( NN heap ) ) The generation from Vicuna- 13B valid tree structure, but is not the same the golden parse tree. The generation from LLaMA-13B fails to follow the instruction.
have words the hopat No reperted words are lowed surgut The braclees should be balanaed.
wo it' as trpor repeatedd worls are allwweele the ourpoc The rodortschoo ballanedd
The macner supply pusted grosane przze cown that panoo
The sccess cupaly pusted gooot no preces down parned
[ we-sa nr The morwen it superl EMP: (100 pueted MP nMl grodine MMUS (rkas)) )) ADVP Oi 8P Jownn 3 PP PPTMPPP ia (MP that2 (11)d
5 cun on the 1; eusees (M cxppty (Vt parteed (NP gooel [ prites LDDV ove: downn Then UNiin (NP) Uhat (hil p2r1
Now producers hops prices have hoberoo
now producors hope liee have bottom
SBJ Alhooe
( (VBDisee)
hrp bottoon
(IN (APP botionn (Nvteil CP-MMPCC (Miperidd) ))))))
The scuasa supol poaleed gesolinw prises that seriood
11
The escaos supoly pushed gasaline prices down thorpe
have botton
Now producers hope have bottom
The ecaeaa pralhedd goodliw prices downi thstt thutpprried
TD A butter
Both bed
Figure 8: Example of shot CP on PTB instance No.29 The golden parse tree is "( St ADVP-TMP RB Now )
NP-SBJ NNS producers ( VP VBP hope SBAR S NP-SBJ NNS prices VP VBP have ( VP VBN hit ) NP NN bottom ) ) The generation from Vicuna-133 has wrong words(some missing, some extra) and wrong bracketing. generation from L.AMA-I3BB fails follow the instruction.

---

Modila
Give conntitumna parning the seenonans belows The outtut should have samernmmer of words the inp it, No poaoeed worde are alowedinn the sutuue The brocketss nould be
turney carning for sa noe below. The cxtput ahoo id the same narr wo the ippus ko repootio wo it's are sllowed in the surpu The braciees should be
The supply pualned apselivve lev oricms dovninn period
The pooshedd guolinn prion dewn the preiod
is oin ssu or the aareess (ww supply (ee juns peokkeed (svi (ne0 guacline NAAS prlcos (ADVP (ADMP oiR down)) THP (NII) that) perloc))11111
is saan-su thee lau sean ss new mesu I sm (WeD gas ved a inn guodlioo (wWs (ADW breupe RP
tive (N
2 10000
Now proda tope prices have bottom
now roducers he pei hava het bodtue
It's prookoara) juu lapw)
supplly
pariod, producers
bettom 1 KiPv OT that (ilihas) V9D nove XPP TMP nit wnichhh pertod 300000
hove hit bottor.
The eotass supolyy pushed gasallicc prices dewn in portoo new producers hope prices
Ludior
5 better
Suth
Figure 9: Example of shot CP on PTB instance No.29 from another sampling The golden parse tree is "( S ADVP-TMP ( RB Now ) ( NP-SBJ ( NNS producers ) VP VBP hope ) SBAR ( S ( NP-SBJ ( NNS prices) ) VP ( VBP have ( VP VBN hit ) NP ( NN bottom) ) )) The generation from Vicuna-13B 13B has wrong words(some missing, some extra) and wrong bracketing. The generation from LLaMA-13B fails to follow the instruction.
Iimo-120
Ialanced
worrd theinpur repeated ward allowed outrutt braciats thould bullnoed.
The elcoss supply pushed gastiin arices downin photpo
supoly qusslins
115 (NP sau The I Levvenss iak supply (VE I'R parthee's (NP (10 goontine 12 pelcee (AD deaeem)) (Po mar 3 hi on thaa pewlent) 1111
(US CAP-SRU cof Tho jJ weunu I MM awwauss LP (VED aed HPI IMN excolinn) (1Ws 1
liess pr down
period 10003
The overall 2.0 Yo meneeee serous that out whhtt is owen worseus shatt nor tadking road and Hesvid Gundorii fi
The owerallo incresse
Itsc what
eacl fredland
the Netione Sxseciation iilen fecturees
energy the producer price nodeo ciil incressed by 0.3 %o Gondon tich vocae eotevam the Noatin aal escerialio of thrurrr
[15 MD SAL DT The Limmeelll CCT ( brrwoee (MB 9. /SAR (1RR ovtnare (NPIMMP
Whu 12
CUSCUP
(KMS
inurcsedd)
MP (PA/ DT thot eaclading food I axdl)) WN energ CVDD alll (eB mnvessed (MP-TH0 (aaP the produser CRNN-ee (iil
producer 1 MMS rice 113 LAAWR DJR ( what MMMSs VVEN even Ven womee)) (yen (1er Inei the IMM czoneriac) (neer havr Nathonnl))
(MNindes (110)) VV80 wild CD Gonder Richrdd INN INN ccomeriiat sen aill wr ME--0MmEE pan DT ( inrraateonal e Avsociation) on)) 3/2 (ombell ( (saNraar) (Ol ta
cald (wan shardt | (sea 119" sconomb.. 3/ wi) Nou 1 1S50 National S04 Avnaniativn (1Mot Mars bertooee y0003)
(MNSSer) Monutbetures)
A bottor
8 botter
Tke
Buth are bad
Figure 10: Example of shot CP on PTB instance No.86(long sentence) This is a long sentence. The golden
parse tree is "( SINV (STPC-2 S NP-SBJ DT The ) JJ overall ) ADJP ( CD 0.9 ( NN % ( NN increase
VP VBZ is ) ADJP-PPD ( JJ serious ) ( PP ( IN in ) NP ( PRP itself) ) CC but ) S SBAR-NOM-SBI
( WHNP-1 ( WP what ) S VP VBZ is ADJP-PRD RB even ) JJR worse ) VP ( VBZ is ) SBAR-PRU IN that ) ( S ( PP ( VBG excluding ) NP ( NN food CC and ) NN energy ) ) ) NP-SBJ ( DT the ) (NN producer) ) ( NN price) ) NN index ) ( ADVVP-MMP ( RB still) ) VP ( VBD increased ( PP-EXT ( IN by ) NP
CD 0.7 ( NN % ) ) ) VP VBD said) ) NP-SBJ NP NNP Gordon ( NNP Richards ) ) NP NP DT an NN economist ) PP-LOC IN at NP ( NP DT the NNP National NNP Association ) ) PP IN of ( NP NNP Manufacturers ) )))) ) The generation from Vicuna- 13B has wrong words(some missing, some extra) and wrong bracketing. The generation from LLaMA- 13B is not valid parse tree, e.g. the last constituent NNP doesn't tt have a corresponding word.


Reviews:
[{"review_id": "fHtxf8nZOU", "reviewer": "Reviewer_3Wr2", "summary": "", "questions": "Although one characteristic of this work is the ability to significantly improve the performance of large language models (LLMs) on structured prediction tasks without fine-tuning, do you think that a small amount of fine-tuning could further enhance the model's performance on such downstream tasks, surpassing previous supervised methods, with the help of output constraints based on structure?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for the positive review and the useful comments.\n\n> The baselines for various structured prediction tasks, especially the baselines for supervised methods, can be more comprehensive, allowing readers to have a better understanding of the performance of existing large-scale model methods based on GCD.\n\nWe agree that explicitly showing more baselines could emphasize our contribution. Since we rely on public datasets and standard evaluations, the results from previous works are directly comparable to ours, and adding more baselines to the camera-ready version will be straightforward.\n\n> The application of the Grammatical Framework (GF) in this work should be explained in more detail.\n\nThanks for this feedback. We will further flesh out Appendix B, where we strive to give all necessary background about GF.\n\n> As illustrated, the broader adoption of this approach is still limited by factors such as latency, task suitability, and compatibility with cloud-based large language models (LLMs).\n\nIndeed there are tradeoffs involved.\n- Latency: We will quantify this aspect in more detail in the camera-ready version by reporting the decoding speed (number of tokens per second) with vs. without grammar constraints. Here's a concise table comparing the latency of pure decoding to the additional delay introduced by grammar constraints.\n\n| Task/Condition | Latency per Token (ms) |\n| --- | --- |\n| llama-7b on A100 | 54  |\n| llama-33b on A100| 87  |\n| llama-65B on A100 | 136  |\n| ED_GCD_overhead  | 1 ± 0.004 |\n| CP_GCD_overhead | 4 ± 1 |\n| IE_GCD_overhead| 69 ± 2 |\n\n\n*Data for llama inference latency on A100 is taken from https://pytorch.org/blog/path-achieve-low-inference-latency/#results\n\n*GCD operates entirely on the CPU instead of the GPU. the above latency for GCD is measured with a consumer CPU\n\nAs shown in the table above, the added latency from GCD is minimal for the CP and ED tasks. For IE, GCD adds a modest additional latency that is inferior or roughly equal to the latency of pure decoding depending on the model used. The relative increase on latency becomes less noticeable when combined with high-performance large models. \n\n- Task suitability: Fig. 2 shows a small selection of NLP tasks that can be formulated in our framework, and there are many others, but indeed: users of GCD have to think about the grammar-based formalization, and for certain tasks this may be less straightforward than for others.\n- Compatibility with large cloud-based LLMs: GCD is indeed only applicable in scenarios where one is in control of the decoding algorithm, which is, e.g., not the case for OpenAI’s models. Luckily, the community is gaining access to ever more powerful open models (e.g., the LLaMA series), which will broaden the scope of our method.\n\n> do you think that a small amount of fine-tuning could further enhance the model's performance on such downstream tasks, surpassing previous supervised methods, with the help of output constraints based on structure?\n\nYes, we hypothesize that combining GCD with fine-tuning could improve performance further, as this combination could leverage both the structured guidance provided by the grammar and the more task-specific knowledge acquired during fine-tuning. Adding a fine-tuning step therefore constitutes an interesting future direction, but note that we intentionally didn’t go that route in the present paper: here, we are specifically interested in using grammar constraints to boost the performance of off-the-shelf LLMs without fine-tuning, which has the distinct advantage that specifying/modifying a grammar for an intended task is easy and fast, whereas fine-tuning can be cumbersome or even prohibitive for the largest available models, and would have to be repeated separately for each task. That said, for especially important tasks, investing into task-specific fine-tuning might still constitute a worthwhile additional investment, orthogonal to the decoding-time grammar constraints as proposed in our framework.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "This paper is well-written. The approach it proposes seems simple yet effective. It demonstrates how to formalize the outputs of various structured prediction tasks as formal grammars. The experimental results are strong in few-shot learning settings.", "reasons_to_reject": "I do not have strong reason to reject this paper. However, there are some points that can be improved in this paper:\n- The baselines for various structured prediction tasks, especially the baselines for supervised methods, can be more comprehensive, allowing readers to have a better understanding of the performance of existing large-scale model methods based on GCD.\n- The application of the Grammatical Framework (GF) in this work should be explained in more detail.\n- As illustrated, the broader adoption of this approach is still limited by factors such as latency, task suitability, and compatibility with cloud-based large language models (LLMs).", "questions_to_authors": "Although one characteristic of this work is the ability to significantly improve the performance of large language models (LLMs) on structured prediction tasks without fine-tuning, do you think that a small amount of fine-tuning could further enhance the model's performance on such downstream tasks, surpassing previous supervised methods, with the help of output constraints based on structure?", "paper_topic_and_main_contributions": "This paper presents a novel approach, Grammar-Constrained Decoding (GCD), to control the generation of large language models, ensuring that the output follows a given structure. It uses formal grammars to constrain the output of a language model according to the desired structure. The paper demonstrates how to formalize the outputs of various structured prediction tasks as formal grammars and how to use the Grammatical Framework (GF) as a completion engine to constrain the output of the language model according to the grammar. Unlike previous approaches with input-independent grammars (IIG), it further introduces input-dependent grammars (IDG) to solve tasks where the output space is not fixed but depends on the input.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UjvcIAAZq6", "reviewer": "Reviewer_w4y4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for the insightful and constructive feedback. We are glad the reviewer finds our contribution valuable, and we appreciate the time and effort they took to provide valuable comments and suggestions.\n\nWe agree that showing the value of GCD on more tasks is an exciting direction. For the purpose of this paper, given the length constraints, we preferred to focus on a judiciously selected set of three tasks, with representativeness and complementarity in mind:\n\n(1) Information Extraction (IE) requires millions of lexical constraints.\n\n(2) Entity Disambiguation (ED) was a priori expected to benefit from an input-dependent grammar.\n\n(3) Constituency Parsing (CP) requires the underlying LLM to implicitly represent syntactic structure, and requires a more complex output structure (recursive parse trees).\n\nWe thus believe these tasks demonstrate the generality and broad applicability of our method. Going beyond, one of our contributions is to show that numerous other NLP tasks can also be formulated as grammar-constrained natural language generation (Fig. 2), and we are looking forward to seeing the method applied to those as well as even more tasks, in our own team as well as elsewhere, using our publicly available code.\n\nFinally, thanks for recommending several relevant papers, which we will integrate in the camera-ready version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- informative study on constrained decoding to improve outcomes\n\n- results with both positive and negative results are instructive\n", "reasons_to_reject": "- size of contribution is modest, could easily extend to more tasks or compare to fine-tuning\n", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper suggests that we can improve LLM ICL accuracy significantly on structured NLP task by constraining the output to valid/reasonable/expected responses, and investigating such an approach on three tasks: closed IE, entity disambiguation, and constituency parsing.  For all three tasks, open-ended generation models are likely to perform poorly, and generally one would think fine-tuning necessary.  The authors find that constraining the output helps LLM accuracy in ALL cases.  In fact, for two out of three tasks, constraining the output (usually in an input-dependent way) is enough to get competitive quality... no fine-tuning is required.  Constituency parsing is the case where constrained output is not enough to generate reasonable quality.  Authors do not explore fine-tuned LMs as a contrast, but do contrast to SOTA supervised baselines.\n\nThis technique harkens back to the pre-chatGPT days, when researchers used output constraints to steer LLMs to do simple classification tasks (e.g., Sentiment analysis, GLUE) using patterns and verbalizers (PET and iPET, Schick and Schütze, 2021(a),(b)).  While this paper is cited, its relevance is not really considered.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "- line 11: n this work -> In this work.\n\n- line 489: Appendix ?? -> Appendix F"}, "extra_text": {"Missing_References": "Enforcing/sampling certain controlled outputs from LLMs (one of these is already cited, but this aspect is not mentioned in related work):\n\n- Timo Schick and Hinrich Schütze. 2021. Exploiting Cloze-Questions for Few-Shot Text Classification and Natural Language Inference. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pages 255–269, Online. Association for Computational Linguistics.\n\n- Timo Schick and Hinrich Schütze. 2021. It’s Not Just Size That Matters: Small Language Models Are Also Few-Shot Learners. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2339–2352, Online. Association for Computational Linguistics.\n\nRegarding controlled text generation:\n\n- Kevin Yang and Dan Klein. 2021. FUDGE: Controlled text generation with future discriminators. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 3511–3535, Online. Association for Computational Linguistics.\n\n- Afra Amini, Ryan Cotterell, John Hewitt, Clara Meister, and Tiago Pimentel. 2023. Generating Text from Language Models. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 6: Tutorial Abstracts), pages 27–31, Toronto, Canada. Association for Computational Linguistics."}}, {"review_id": "jAbJZwSwKU", "reviewer": "Reviewer_NQmR", "summary": "", "questions": "A. Line 303-305, the claim 'as long as the grammar is correct...' is very strong and vague. Justification or references on this claim should be provided.\n\nB. The term 'few-shot' learning might be ambiguous in the context of this paper. 'In-context' learning might better describe the proposed method which does not require fine-tuning.\n\nC.  What is the number of generation steps and number of failures in parsing required to generate a correct output?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for the positive and thoughtful feedback.\n\nUpon carefully reading the review, we believe that one clarification can address both of the reviewer’s two key comments:\n\n> What is the number of generation steps and number of failures in parsing required to generate a correct output?\n\n> the claim 'As long as the grammar is correct, the performance of GCD is guaranteed to be at least as good as the LM in free-form generation' is very strong and vague.\n\nIn order to address these comments, we’d like to clarify that, by design, GCD’s decoding algorithm doesn’t generate any strings that fail to parse (more precisely, it doesn’t even generate any partial strings that couldn’t be completed into a valid parse). Indeed, one could imagine a brute-force “propose-and-reject” method that keeps searching for strings until it finds a string that is compatible with the grammar at hand. Our method (GCD), on the contrary, works differently: at every decoding step, GCD only ever considers next-token candidates that could potentially lead to a valid parse (i.e., for which there is at least one parseable completion), leveraging the incremental parsing functionality of Grammatical Framework. This effectively serves to prune the (infinitely large) search tree explored during decoding by eagerly discarding paths that couldn’t possibly lead to a valid parse down the road.\n\nThis is also what we tried to express with our statement “As long as the grammar is correct, the performance of GCD is guaranteed to be at least as good as the LM in free-form generation”. As described above, GCD may be seen as pruning/filtering the search tree by restricting it to grammar-compatible token sequences. Therefore, on the one hand, in cases where the unconstrained LM happens to generate a grammar-compatible output, the grammar-constrained LM (GCD) generates precisely the same output. On the other hand, in cases where the unconstrained LM generates an output that is not grammar-compatible, said output is invalid and thus worse than what would be generated by the constrained LM (GCD). It is in this sense that we wrote GCD’s output is at least as good as that of an unconstrained LM.\n\nFinally, we thank the reviewer for the suggestion to use “in-context learning” rather than “few-shot learning”. We agree with the suggestion and will change the nomenclature in the camera-ready version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The method is effective and can be applied to a wide range of structured NLP tasks.", "reasons_to_reject": "As the authors pointed out in the Limitation section, the proposed method may be inefficient when the grammar is complex. To have a better understanding of the proposed method, quantitative analysis on this issue should be provided, e.g., the number of generation steps or number of failures in parsing required to generate a correct output.", "questions_to_authors": "A. Line 303-305, the claim 'as long as the grammar is correct...' is very strong and vague. Justification or references on this claim should be provided.\n\nB. The term 'few-shot' learning might be ambiguous in the context of this paper. 'In-context' learning might better describe the proposed method which does not require fine-tuning.\n\nC.  What is the number of generation steps and number of failures in parsing required to generate a correct output?", "paper_topic_and_main_contributions": "This paper shows that LMs with grammar constrained decoding (GCD) can solve many structured prediction problems in NLP. The authors propose 'input-dependent grammars' to adjust the grammars according to the input, thus they can constrain the output space with more flexibility and handle more structures of interest. Grammar constrained decoding is done by applying Grammatical Framework (Angelov 2009) to the constructed input-dependent grammars. Empirical results on closed information extraction and entity disambiguation using LLaMA and Vicuna show the effectiveness of the proposed method.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "1. Grammar Prompting for Domain-Specific Language Generation with Large Language Models, https://arxiv.org/pdf/2305.19234.pdf"}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "1. Line 11: n this work -> In this work\n2. The abbreviation cIE appears the first time in line 68 without its full term given.\n3. The citations for (de Cao et al. 2021) are misformatted.\n4. Line 254: There are 14 tasks in total instead of 16 in figure 2.\n5. Line 356: delete 'Figure' \n6. Line 383: triple based -> triple-based  \n7. Line 489: Appendix hyperlink is missing.  \n8. Footnote 1: capitalization"}}, {"review_id": "wvhlKd0uJ9", "reviewer": "Reviewer_N4GZ", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for the review and the positive feedback. We look forward to seeing the community make practical use of our framework.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Getting structured output from LLMs is an omnipresent problem in modern NLP. The paper's framing of using a grammar completion engine for validity and a LLM for plausibility is both intuitive, simple and, as demonstrated by the authors, useful.", "reasons_to_reject": "At this point in time, nothing major comes to mind regarding the negative aspects of this paper. The method is well described and empirical experiments and comparisons carried out, likely, fairly. I am not an expert in this area so it may be the case that this paper is not as novel as it appears.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper proposes a method for getting structured output from LLMs which is described formally and evaluated on 3 NLP tasks.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "- L011: Missing letter. The submitted abstract has this fixed."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers agree that the paper is well-written and presents a simple yet effective approach to a common problem in NLP, obtaining structured output from large language models. It formalizes the outputs of various structured prediction tasks as formal grammars. The proposed approach, combining a grammar completion engine for validity and an LLM for plausibility, is intuitive, simple, and demonstrated to be useful. It also shows strong experimental results demonstrated particularly in few-shot learning scenarios. The study provides informative insights into constrained decoding to improve outcomes. Results include both positive and negative findings, making them instructive. 

The demerits of the paper which are suggested improvements include the need for more comprehensive baselines for various structured prediction tasks, a more detailed explanation of the application of the Grammatical Framework (GF), and consideration of factors like latency, task suitability, and compatibility with cloud-based large language models (LLMs). There is a suggestion to explore whether a small amount of fine-tuning could further enhance the model's performance on downstream tasks, surpassing previous supervised methods


Reasons to Accept:
(1) The paper is well-written and presents a simple yet effective approach for formalizing the outputs of structured prediction tasks using formal grammars.
(2) It demonstrates the effectiveness of the proposed approach in few-shot learning settings, which is a valuable contribution.
(3) The paper provides informative insights into constrained decoding to improve outcomes and presents results with both positive and negative outcomes, which are instructive for the research community.

Reasons to Reject:
(1) While there are no strong reasons to reject the paper, there are areas that could be improved, including providing more comprehensive baselines for structured prediction tasks, explaining the application of the Grammatical Framework (GF) in more detail, and addressing the limitations related to factors like latency, task suitability, and compatibility with large language models (LLMs).
(2) The size of the contribution is considered modest, and the paper could potentially extend its scope to cover more tasks or compare its approach to fine-tuning for a broader understanding of its effectiveness.
(3) The proposed method's efficiency in handling complex grammars should be quantitatively analyzed, providing insights into issues like the number of generation steps or parsing failures required to generate correct outputs.

The authors seem to have written a clear rebuttal as well with one reviewer providing further comments.
Decision: Accept-Main