Retrieval-Augmented Parsing for Complex Graphs by Exploiting Structure and Uncertainty
Authors: Zi Lin
Quan Yuan
Panupong Pasupat
Jeremiah Zhe Liu
Jingbo Shang
Venue: EMNLP 2023 Findings (2023)
Keywords: Uncertainty Quantification
Retrieval
Semantic Parsing
TL;DR: We present an effective retrieval augmentation method for parsing complex graph output which utilizes (1) structural similarity and (2) model uncertainty.

Abstract: Retrieval augmentation enhances generative language models by retrieving informative exemplars relevant for output prediction.
However, in realistic graph parsing problems where the output space is large and complex, classic retrieval methods based on input-sentence similarity can fail to identify the most informative exemplars that target graph elements the model is most struggling about, leading to suboptimal retrieval and compromised prediction under limited retrieval budget.
In this work, we improve retrieval-augmented parsing for complex graph problems by exploiting two unique sources of information (1) structural similarity and (2) model uncertainty.
We propose $\textit{\textbf{S}tructure-aware and \textbf{U}ncertainty-\textbf{G}uided \textbf{A}daptive \textbf{R}etrieval} \textbf{(SUGAR)} $ that first quantify the model uncertainty in graph prediction and identify its most uncertain subgraphs, and then retrieve exemplars based on their structural similarity with the identified uncertain subgraphs.
On a suite of real-world parsing benchmarks with non-trivial graph structure (SMCalflow and E-commerce), SUGAR exhibits a strong advantage over its classic counterparts that do not leverage structure or model uncertainty.

Retrieval-Angmented Parsing for Complex Graphs by Exploiting Structure and Uncertainty
Zi Lin
Quan Yuan
Panupong Pasupat
UC San Diego
Google Research
Google Research
1zi@ucsd. edu
yquanêgoogle.c com
ppasupatégoogle.co com
Jeremiah Liutt
Jingbo Shang
Google Research & Harvard University jereliu@google.. com
UC San Diego
jshang@ucsd. edu
Abstract
input similarity alone may not be effective in iden- tifying the most informative exemplars for aiding graph prediction. As an example mentioned in Qiu et al. (2022), for the test input "Schedule a meeting with my manager", it is more similar to example "Schedule meeting with Alex" than "Who is my manager", while the latter one contains an impor- tant action for searching org chart which is also required by the test input.
Retrieval augmentation enhances generative language models by retrieving informative ex- emplars relevant for output prediction. How- ever, in realistic graph parsing problems where the output space is large and complex, clas- sic retrieval methods based on input-sentence similarity can fail to identify the most infor- mative exemplars that target graph elements the model is most struggling about, leading suboptimal retrieval and compromised pre- diction under limited retrieval budget. In this parsing
In this paper, we explore effective approaches to improve the generalization performance of retrieval-augmented LLMs for parsing complex graphs. Specifically, we consider exploiting two sources of information uniquely available to this problem: (1) structural similarity between output subgraphs, and (2) model uncertainty graph com- ponent prediction. The motivations behind our ap- proach are two empirical investigations on LLM graph parsing (presented in Section 3): (a) Inade- quacy of
work, we improve for complex graph problems by exploiting two unique sources of information (1) structural similarity and (2) model uncertainty. We pro- pose Structure-and aware and Uncertainty Guided Adaptive Retrieval (SUGAR) R) that first quantify the model uncertainty in graph prediction and identify its most uncertain subgraphs, and then retrieve exemplars based on their structural sim- ilarity with identified uncertain subgraphs. On suite of real-world parsing benchmarks with non-trivial graph structure (SMCalflow and B-commerce), SUGAR exhibits a strong advantage over its classic counterparts that do not leverage structure or model uncertainty.
retrieval (Section 3. 3.1.. When output graphs exhibit non-trivial structure, the exemplars retrieved based on sequence similar- ity is less effective than those based on graph simi- larity, even when the similarity is computed with respect to the gold output graphs 1, (b) LLM uncer- tainty correlates with performance (Section 3.2). We conduct a exploratory study of the quality of LLM uncertainty as an indicator of its generaliza- tion performance in graph prediction, and identified monotonic between model uncertainty v.s. accu- racy for node and edge prediction (Figure 2). This implies that model uncertainty can serve an ef- fective signal for identifying the subgraphs that the model is struggling to predict, thereby helping the retrieval algorithm to efficiency identify the most effective examplars for aiding model prediction, especially when the output graph is large.
1 Introduction
Large language models (LLMs) have demonstrated remarkable capabilities as effective few-shot learn- ers (Brown et al., 2020). Recently, new learning paradigm called in-context learning has been de- veloped. Under this paradigm, the model is given a prompt including test inputs and few related exemplars, and can generate outputs directly with- out updating its parameters. A typical approach to obtaining these exemplars is to retrieve training ex- amples similar to the test input (Pasupat et al., 2021; Gupta et al., 2022). However, for realistic parsing tasks with large output graphs and non-trivial struc- ture (e.g., dialogue-oriented semantic parsing), the
Based on the above observations, we propose
'This is in contrast to carlier work where sequence simi- larity is already sufficient for simple sentences with shallow output structures (c.g.. TOPS) (Zemlyanskiy et al., 2022)
Co-senior authors. Work done at Google.

---

Retrieval
Retrieved Exemplars Uncertain Subgraphs
[6 ( D (x. x
Structure-sware Retrioval
Uncertain Construction
(( (1 K.
Vu. ... Pae]
Confident
Candidate Pool
Graph Uncortainty Quantrication
END
START
Prodiction Ittration
Input
LLM Generator
Prediction @ Iteration
2--1
Iterative Prompts
Parsing Generation
Figure I: An overview of Structure-awand and Uncertainty-Guinn Guided Adaptive Retrieval (SUGAR). At each iteration i, the model prediction ij will go through a retrieval process consisting of three steps (red squared ones): (1) graph uncertainty quantification that measures the model's uncertainty predicting structured output yi structure level (Section 1.1.1y; (2) uncertain subgraph construction that gets collection of uncertain subgraphs Di, based on uncertainty scores of ys (Section 4.1 (3) structure-aware retrieval that retrieves structurally similar exemplars targeting at ii, (Section 4.1.3). Note that iteration the exemplars are retrieved by input similarity since there is no model prediction yet.
sub-
Structure-awart and Uncertainty- Guided Adaptive Retrieval (SUGAR), a retrieval-augmenned LLM inference framework for complex graph parsing that incorporates both structural similarity and model uncertainty into retrieval procedure (Sec- tion 4). Operating in an iterative manner, SUGAR first identifies uncertainty regions in the model's graph prediction from the previous iteration, and adaptively retrieves exemplars based on their graph similarity with the identified uncertainty subgraphs (Figure 1, Section 4). In this way, SUGAR is able to better target model weaknesses in structural pre- diction by retrieving the most informative exem- plars, which appears to be especially valuable in the setting of large and complex output graphs given limited retrieval budget.
Related Work
Retrieval-Augmennee Parsing, Sequence-to- sequence (seq2seq) models have achieved state- of-the-art performance on many natural language processing tasks including complex parsing, e.g., dialogue-oriented semantic parsing and meaning representation parsing (Vinyals et al., 2015; Xu et al., 2020; Cui al., 2022; Lin al., 2022b,a). The general approach is to treat the output struc- ture as a sequence and fine-tune a seq2seq model to learn the mapping between input sentences and output structures. To reduce the reliance on large- scaled annotated data, several work augment the input with retrieved exemplars from the training data, with different strategy select exemplars.
For unsupervised retrieval, Pasupat et al. (2021) and Gupta al. (2022) retrieve exemplars with similar input encodings from a pre-trained neural encoder. Zemlyanskiy et al. (2022) retrieves ex- emplars for which the input and output (from the preliminary prediction) has high TF-IDF similar- ity with the sample input. The above work mainly focused fine-tuning settings. For supervised trieval, Rubin al. (2022) suggest to use language models themselves to label examples that can serve as good prompts, and train a prompt retriever from this signal. In this work, we focus on unsupervised retrievers that do not rely on additional training data beyond the candidate pool they retrieve from.
On a suite of real-world complex graph parsing benchmarks (i.e., SMCalFlow and Ecommerce), SUGAR exhibits distinct strength over its clas- sic counterparts that do not leverage uncertainty structure, bringing clear performance improve- ment over the base model across iterations even when other vetrieval-augmentation methods be- come counterproductive (Section 5). Further in- depth analysis revealed the interesting role of ex- emplar quality on model uncertainty, the effective- ness of uncertainty as an early-stoppin signal for retrieval iterations, and verifies the effectiveness of structural retrieval in improving model confidence (Section 2)
Iterative Retrieval. While LLMs can generate coherent outputs via single-time retrieval-based augmentation, they often fall short in addressing more complex tasks. To address this, there have been various attempts to retrieve exemplars more than one time. Most the work focused on ad-
'Open-source code may he found at https://github con/ htt///ool//uccrraittyyyo

---

MTOP
SMCalFlow
Ecommerce
Metric
Similarity
StoO
EM
SMATCH
StoO
EM
SMATCH
StoO
EM
SMATCH
USE
Input
68.64
44.60
87.08
48.38
24.20
68.59
45.79
5.10
66.53
BM25
Input
57.08
41.40
84.34
51.33
24.20
72.78
47.21
8.40
69.64
BM25
Output 87.47
50.90
94.09
71.93
48.10
89.03
51.09
8.00
69.74
SMATCH
Output 90.09
50.50
94.10
80.16
53.80
92.03
60.45
7.30
72.88
Table Evaluation results for in-context learning with 10 exemplars retrieved based on different similarity functions. StoO means average SMATCH to oracle which measures the graph overlapping between gold output and retrieved outputs; EM means exact match rate.
dressing long-form outputs such as long-form ques- tion answering tasks (Fan al., 2019; Stelmakh al., 2022). The basic idea is decomposing com- plex question into several easier sub-questions, and iteratievely retrieving relevant information from knowledge agents for each sub-quesitons (Press et al., 2022: Yao et al., 2022: Khot et al., 2022). Based on this line of work, FLARE (Jiang et al., 2023) further proposes to actively retrieving when the sub-answer contains low-confident tokens.
semantic parsing tasks with output structures from simple complex, including (1) MTOP (Li et al., 2021): : user intent slot filling dataset which can be simplified as a sequence labeling task; (2) SM- CalFFlww (Andreas et al., 2020): a dataset of se- mantically detailed annotations of task-oriented natural dialogues, which can be taken as a tree parsing task; (3) Redwoods-Fcommee merce for short) (Oepen et al., 2002): dataset of annotated meaning representation (outputs are di- rected acyclic graphs) based on English Resource Grammar (Flickinger et al., 2014) 4), which is DAG parsing task.
(Ecom-
However, iterative retrieval for parsing complex structured outputs is less explored. The core chal- lenge lies in the non-sequential nature of the output structure such as tree or graph, which means it can- not be simply decomposed sequentially. In this work, we aim at addressing complex parsing tasks, and target progressively improving model's pre- diction by iteratively retrieving relevant examplars for model's 's uncertain sub-structures. As we will show in Section 3, this can not be achieved without incorporating structure and uncertainty.
The evaluation results are shown in Table We can observe gaps between standard retrieval (based on input similarity) versus oracle retrieval (based on output similarity). finding that aligns with Qiu et al. (2022). Furthermore, the output structure gets more complex (from MTOP to Ecommerce), it becomes more important have exemplars that are similar in output structure, compared to just input similarity or sequence-level output similarity. This is because sequence-level similarity metrics only consider token overlapping, and ignore syntactic or semantic relationships in the output structure. As output becomes more complex, these similar- ity metrics less likely to find structural simi- lar exemplars. Therefore, it is important to have a structure-awand retriever for complex parsing tasks.
3 Motivations
this section, we present two ablation studics which serve as motivations for our methods.
3.1 Structural Similarity Matters
The first question is what retrieve. Here study how different similarity functions perform on different semantic parsing tasks, which is under in-context learning settings using GPT3.5 with 10 exemplars in the prompt.
3.2 Model Uncertainty Matters
However, retrieving exemplars based structural sim- ilarity can have several challenges. First, in the initial settings we do not have access to gold output structures. This can be solved by getting some pre- liminary prediction using retrievals with similar in- puts as proposed in Zemlyanskiy al. (2022). Sec- ond, retrieving similar outputs based on the entire structures can be ineffective and may introduce un- wanted noise. Given the emerging challenges, we are investigating if is possible to measure struc-
Specifically, we test input sentence similarity us- ing Universal Sentence Encoder (USE) (Cer et al., 2018) and BM25 (Schutze al., 2008), and out- put similarity using BM25 and SMATCH (Cai and Knight, 2013). Note that SMATCH the only metric that considers structural similarity beyond simple token overlapping in the output (more de- tails in Appendix A). We choose three different

---

1.0
Algorithm I Retrieval-anggmente Inference with SUGAR
Nodeltppe Accrasies
Precompute:
Examplar pool P = {( H-)
Subgraph pool Pg = (t))( b (Sec. 4.1.3)
Input:
Test input
0.001
8,590
1.000 3,000
1.000
Output:
Node/fidge Probabilttes
Final graph prediction d
Figure 2: Correlations between model probabilities and performance for node/edge prediction
Initialize:
En base retriever(a)
Initial retrieval. b Initial prediction.
Go = IJMM( Ho)
# Iterative retrieval with early stopping.
for i E max iter] do # Graph uncertainty quantification (Sec. 4.1.1).
tural similarity only necessary sub- stu-strrut.res. If so, which part to retrieve? Our hypothesis is that we can retrieve only when model is uncertain about some sub-structure predictions, which are very likely to be flawed.
{po
Confidence-based early stopping.
if Pv. > canf_threshood Ve then
return Ø--1
Construct uncertainty subgraphs (Sec. 4.1.2).
To validate our hypothesis, study analyzes LLM's 's behavior in predicting struc- ture components in terms of model uncertainty. Specifically, we explore the correlation between model probability and performance for in-context learning model (more details can be found in Ap- pendix B). As shown in Figure 2, high model prob- ability generally corresponds to high performance and vice versa. Our study confirms that model un- certainty is effective for detecting prediction errors. This means that we can retrieve structurally similar exemplars targeting on these uncertain substruc- tures, which can help to address the flawed parts in the prediction.
second ablation
{th } = get uncertain subgraph( (paa)) # Structure-aware retrieval (Sec. 4.1.3).
for Uia E {0n
Esh structure wwareee_wwwrrreeee rewrre_rerrieval(@..... Px))
E,.add(Esx)
#
prediction.
9. LLM(z, E,, 1-11)
on preliminary predictions is at step i (the retrieval process in Figure 1), which includes three steps: (1) graph uncertainty quantification for Ús (Section 4.1.1); 1); (2) uncertain subgraph construction, i.e., Dix (Section 4. 4.1.2); ;); (3) structure-aware retrieval for gia (Section 4.1.3). The retrieval process is operated in an iterative manner, which enables progressive improvement for model's prediction by iteratively retrieve exemplars based on model's predictive un- certainty from the previous turn (Section 4.2).
4 SUGAR: Structure-aware and Uncertainty-Cuudded Adaptive Retrieval
This section describes details of SUGAR for pars- ing complex structures. Typically, the output struc- ture a semantic graph that is rooted, directed, acyclic and labeled (Opitz, 2023).
4.1 Retrieval Process
4.1.1 Graph Uncertainty Quantification
Problem Formulation. We aim to solve a graph parsing problem that maps from natural lan- guage utterance x to a target graph representation G (N, E), where N is the set of nodes and E N x N is the set of edges. For seq2seq mod- els, G represented as a lincarized graph string y. Following Lin al. (2023), we adopt PEN- MAN annotation (Kasper, 1989) to linearize all graph structures in this work, which is a serializa- tion format for the directed, rooted graphs used to encode semantic dependencies (details for graph linearization can be found in Appendix C).
Recent year witnessed the success of applying seq2seq models graph parsing tasks, where the outputs are compositionally structured (e.g.. graph or a tree). However, these seq2seq ap- proaches pose a technical challenge in properly quantifying the model uncertainty for graph predic- tion. This is because the autoregressive seq2seq probability is not well-suited for describing model uncertainty in predicting elements substructures of the output graph, where the probabilistic graphi- cal model (PGM) more suitable formalism. To address this issue, leverage Graph Autoregres- sive Process (GAP) proposed by Lin et (2023) to allow the correspondence between seq2seq out- put probability to PGM probability, i.e., assigning
Figure shows an overview of SUGAR and Al- gorithm 1 summarizes the detailed process. In Section 4, we illustrate the retrieval process based

---

model probability for a node or edge on the graph. Specifically, given an input sequence a and out- put sequence = y192 yN that refers to graph (N, E). GAP can map the token-level autore- gressive distribution
send v
9
wzong & p=0 p=0.9539
p=o 9919
p=0.8541
ARG1
A8G2
ABG3
BV p=0.9453
ABG1
9384
9989
3992
pcon
pcon
generic eatity p=0.42 .4733
p=0 .995
p=0 .975
aV p.0.9986
Uncertain Subgraph
p-0.9994
p(ylx) II p(uslbe))))
pronoun 9
pronoun 4 9994
pc0. 9974
to graphical model likelihood
Figure 3: An example for uncertain subgraph (e 0.8, d 2) in prediction for input sentence "You send the wrong camcorder" (Ecommerce). The dotted squared one is the uncertain subgraph, where the red squared node and red fonted edge refer to uncertain elements, and the rest parts are their neighbor contexts.
pG] II p(u) pa()),
vEG
= II p(a| pa(n), x) II p(e) x) nCN
where p(o pa(v), x) the conditional probability for graph elements e with respect to their parents pa(v) in G.
D.'s 's as the query (with the uncertain element v masked out) to retrieve structurally similar exem- plars.
4.1.2 Uncertain Subgraph Construction
consider the typical set- ting where there is retrieval candidates pool P = {( vo) which are pairs of input sentences 2, and output graphs ye. To perform structure-aware retrieval, we first prepare subgraph retrieval pool Pg where Sa(we) = {ucy} is the set of all depth-d subgraphs of ye- Then, at inference time, given every uncertain subgraph ua(v), we retrieve {ue o bes' C Pg based on their graph similarity with ud(v), which eventually leads the set of exemplars {xx,, }e) that will be used for the surieval-augmenteel inference.
Specifically,
To leverage uncertainty in the model prediction p(G[z) for efficient retrieval, we consider the con- cept of uncertain subgraph which is a subgraph that contains:
Sa(ee.
Uncertain element. We consider a graph ele- ment v E G to be uncertain if its probability p(v) pa(u), .r) is below a certain threshold
Relatively neighbors. Given a un- certain element and subgraph sa(v) that surrounds and with maximum depth d. We define the Silatively-confider neighbors of as the subset (u(v) C (1(v) whose probability is above a certain threshold e.
Practical Implementation. In this work, we con- sider the SMATCH metric (Cai and Knight, 2013) for computing graph similarity. Given a query graph with Ng nodes and l candidate graphs with N. nodes each, the time complexity of the graph matching algorithm is O(k Ng * Ne). In prac- tice, the size of N₂ is controlled by d, and lo can be significantly reduced by first pre-filter the candi- date pool using a fast heuristic metric (e.g., atom similarity)
As shown, by coupling the uncertain element v with its relatively-confident graph neighbor ca(u), uncertain subgraphs 9. = {w} U ca(u) provides the retrieval algorithm fine- fine-grained and contextu- alized information about model uncertainty in the prediction of graph elements (see Figure for an example). In practice, to limit the size of uncertain subgraphs and keep the cost of structural similar- ity computation within a feasible range, we set a parameter to control the maximum depth of un- certain subgraphs S..
4.2 Improve Parsing Performance with Uncertainty-aware Iterative Retrieval
4.1.3 Structure-aware Retrieval
Due to its uncertainty-awan nature, SUGAR intro- duced in Section 4.1 be applied iteratively
To identify informative graph exemplars that best address the model uncertainty in predicting graph elements, we leverage the uncertain graph intro- duced above and consider retrieval policy using
Inn our experiment, we choose d = 3 and retrieve based on 1,000 candidate graph ponl, and our exception time is around 5 iterations per seconds.

---

model prediction, by continuously retrieving new exemplars address model uncertainty in the pre- vious iteration until model reached a satisfactory level of confidence. This is analogous to the itera- tive refinement approaches in the recent literature where a model's 's initial generation can improved by additional self-correction steps (Reid and Neu- big. 2022; Schick et al., 2023; Welleck al., 2023; Jiang et al., 2023).
2018), and (3) BM25 (Robertson et al., 2009). Re- call that these retrievers will only be used to initial- ize the first round of SUGAR prediction, and not used in subsequent iterations (Algorithm 1). Baselines. Due to the iterative nature of SUGAR, prediction results are comparable to base retrievers mentioned above using the same total number of exemplars. For example, base retriever using 8 ex- emplars is comparable SUGAR at iteration (5 base exemplars plus iterative exemplars). How- ever, due to the sequence limitation, it unfeasible to add large number of exemplars in one prompt. which makes it impossible to get results for base retrievers using more than 10 exemplars. This also highlights the advantage of iterative retrieval as it can get rid of sequence length limitation. Another benefit is that it can get the model's intermediate results towards the final optimal prediction, and more exemplars are added concentrate on these intermediate results' weak parts.
In the experiment (Section 6.2), we study model performance under different retrieval and refine- ment strategies, validating that incorporating struc- ture and uncertainty information are both important for improving parsing performance under iterative refinement.
5 Experiments
5.1 Datasets & Model Settings
Datasets, In this paper, we use two complex seman- tic parsing datasets, including dialogue-oriented se- mantic parsing and graph-based grammar parsing.
We also consider two iterative variant of baselines that is based on output similarity: GandRiter (Zemlyanskiy et al., 2022) that retrieves examplars based BM25 with both input sentence and predicted graphs (weight a=0.5)*, and also Oracle that retrieves examplars based on graph sim- ilarity with gold subgraphs. Further details about settings of model, candidate pool and prompts can be found in Appendix D, and Appendix E reports additional supplementary studies on much smaller models T5 (Raffel et al., 2020) for out-of-domain and lew-resource settings.
SMCalFlow. SMCalFlow (Andreas et al., 2020) is a large corpus of semantically de- tailed annotations of task-oriented natural dia- logues. The annotation uses dataflow compu- tational graphs, composed of rich set of both general and application specific functions, to represent user requests as rich compositional expressions.
Redwoods-Ecomment (Ecommerce). The LinGO Redwoods Treebank is a collec- tion of hand-annotated corpora for an En- glish grammar consisting of more then 20 datasets (Oepen et al., 2002). We choose the Ecommerce subset of Redwoods which consists of email messages composed by the online customers. The graph output of this subset is sufficiently complex, and is consid- cred out-of-distribution compared to the stan- dard training split of Redwoods based on Wall Street Journal (Lin et al., 2022b).
5.2 Results
The evaluation results are shown in Figure 4. As shown, SUGAR progressively improves the model prediction across iterations, even in the setting where its iterative counterparts becomes counterproductive (e.g, Base=BM2,5 on Ecom- merce). Specifically, SUGAR significantly outper- forms its base retrievers with the same retrieval budget (Base@8), improving the base retriever CASPERuse and BM by 26.61% % and 20.36% respectively in absolute percentage on SMCalflow. and 17.58% and 12.37% respectively in absolute percentage Ecommerce.
Models & Base Retrievers. We choose GPT3.5 deext-davinci-00:3 Ouyang et al., 2022) as our large language models for in-context Icarning set- tings. To initialize SUGAR prediction, we con- sider three choices of base retrievers be used for initializing SUGAR prediction: (1) Random, (2) CASPER (Pasupat et al., 2021) that is based on Universal Sentence Encoder (USE) (Cer et al.,
Appendix F, to understand if the benefit of SUGAR is orthogonal to base model choice, and cannot be surpassed by simply upgrading model
'In ablation analysis Section 6.2, we also consider variant of GandR that incorporates model uncertainty.

---

SMCa
Base Base-Random Random
Base=CASPERusc
1a55-BBM4
Oracle
60
SMATCH
-2
SMATCHH
15
GandRow
Basegs
10
Base@8
23
50
Ecommerce
Bas Random
CASPECA
Base BBM
Oracl
70
SMATCH
SMATCCH
SMAAT22
GandRay
-3
Base@3
Base@é
72
15
Iters
Figure 4: In-context learning results. B and Base@8 refer to retrieving 5 and 8 exemplars by base retriever. Since iterative retrieval will add additional exemplars per iteration, Base@8 is comparable to results at iter 1.
model architecture, we conduct the following two sets of experiments: (1) comparison between SUGAR and its baseline variants based on older variants GPT models (e-g., text-davinci-002) which differ in training method. (2) comparison of baseline methods under GPT-4 v.s. SUGAR under GPT-3.5. The experimental results have shown that SUGAR successfully improves all LLMS in terms of exact match and graph similarities. Furthermore, SUGAR with GPT3.5 also works better than GPT4 using base retriever. This concretely shows method provides non-trivial improvement beyond what can be achieved by simply upgrading archi- tecture.
tainty quality is to measure its calibration perfor- mance, i.e., whether the model's predictive uncer- tainty is indicative of the predictive error, e.g., ex- pected calibration error (ECE; Naeini et al., 2015). Based on ECE, Lin positional Expected Calibration Error (CECE) to measures the difference in expectation between the model's predictive performance on graph elements and their actual match to the gold graph, which can better reflect model's behavior in predicting graph structures. Table 3 reports the CECE results (based on all graph elements, nodes, and edges).
(2023) propose Com-
We can find that the calibration for random base retriever is consistently worse than BM2s and CASPER indicating that the relatively- confident neighbors in uncertain subgraphs for ran- dom retriever might fail to capture accurate texts for iterative retrieval. This also indicates that improving L.LMs' calibration can be a fruitful venue for improving retrieval-bate data augmen- tation.
Table 2 shows some exemplars (sentence inputs) from different retrievers. We can find that com- pared to other retrievers, SUGAR can accurately retrieve exemplars that closely align with the un- certain parts of the model prediction, which is sig- nificant in addressing the uncertainties that are in- herent in the model inference, thereby refining the model's prediction.
6.2 Uncertainty as Early Stopping Signal
6 Analysis: the Role of Uncertainty
Given that the parsing generation in Figure 1 edit previous model prediction is zero-shot pro- cess, i.e., the LLM has not been provided with any examples to improve model prediction each step. thus the model has a tendency to keep making edits to predictions from previous iterations, even if they are already accurate. At this stage, uncertainty be- comes significant signal for stopping the iteration process.
6.1 Uncertainty Quality Matters
We notice that SUGAR does not work very well on the random base retriever, and this might be due to the relatively poor uncertainty quality of the random base retriever in comparison to the other two base retrievers. To validate our hypothesis, we further evaluate the uncertainty quality of the three base retrievers.
Specifically, SUGAR will terminate the iteration retrieval process and return the last model predic-
common approach to evaluate model's uncer-

---

User Input
Retriever
Exemplar User Input
CASPER
time my meeting on thrrsday?
What meeting have hour.
BMg
Please extend appuiniment by hall' of
GandR
Please extend uppointment by half' an hour.
SUGAR
Fine, then put me down as on vacation starting this second until April
CASPER
Schedule appuiniment for the dentist at 2pm tomorow.
BM2
Dentist appointment is when'
get dentist appointment
GandR
Dentist appuintment is when?
SUGAR
actually can you remove that
CASPER
have events tomorrow?
BMg
sunference week?
what do have next week that's not a party
GandR
have work conference
SUGAR
Do have anything else scheduled hesides Work and Hustle
CASPER
posipone it to the wednesday
BMgs
today morning meet
leave early from today
GandR
today momning mect
SUGAR
need mechanics appointment today after 4pm
CASPER
Delete my meeting on Saturday
BMg
Take out my d'clock break lomormm
Delete o' clock with simon and the pauls
GandR
Take out my o' clock break lomorrow
SUGAR
Could you please Accept my date with Sam
Table 2: Exemplars from different retriever on SMCalflow development set. Highlighted text refers to uncertain parts.
CRCFg 4.
CRCCN
CECFg
6.3
Uncertainty across Retrieval Iterations
BMg
0.2617
0.2252
0,3008
Two additional interesting questions could be (1) what type of graph requires more iterations? and
SMCalFlow
CASPER
0.2602
0,2288
0,2943
Random
0,3747
0.3253
0.4297
BM
0,1594
0.1119
0,2092
(2) how does uncertainty evolve across different retrieval iterations?
Ecommerce
CASPER
0,1677
0.1250
0.2131
Random
0,2000
0.1499
0.2543
We first explore the correlation between number of iterations and graph complexity and report the results in Table 5 (base retriever is CASPERuse). As we expected, graph of higher complexity typi- cally demands greater number of iterations before achieving a satisfactory level.
Table 3: Compositional ECE for different base retrievers SMCalflow and Ecommerce under in-context leamn- ing settings.
BMgs
CASPER
Dataset
Tter
GandR
GandR
GandR
GandR
We then visualize some graphs at different iter- ations and explore the progression of uncertainty levels (see details in Appendix G). Generally, we notice that an uncertain graph elements will be- come less uncertain as iterations progress. How- ever, we also observe occasional fluctuations in the uncertainty, which can trigger instability in neigh- boring contexts. This means that as uncertain el- ements become certain, the contexts around them may lose some degree of confidence. We reserve further exploration of this phenomenon for future work, which we believe is promising direction for understanding LLMs' calibration in complex structure generation.
@
71.89
72.97
76.06
77.28
SMCalFlow
71.83
72.89
75.46
76.77
@3
71.06
72.53
74.81
76.68
@ 68.35
69.01
66.37
66.76
Ecommerce
@2
61.56
68.41
66.34
@
61.60
67.73
65.10
65.86
Table 4: Results of GandRiter baseline in iterative re- trieval with without model uncertainty as the signal for iteration stop. Means using uncertainty.
tion once satisfactory level of confidence has been achieved. Additionally, we incorporate model un- certainty stopping signal for the GandR baseline (Table 4), and we consistently observe an improvement compared to the baseline that doesn't utilize uncertainty as a stopping signal. This fur- ther validates the crucial role of uncertainty in the iterative retrieval process.
Conclusions
In this work, we present Structural-aware and Uncertainty-Guudde Adaptive Retrieval (SUGAR), a new retrieval-augmented parsing framework us-

---

Dataset
#iter
#Node
#Edgee
Degree
Depth
Limitations
12.53
11.53
1.38
7.05
This work focuses on advanced inference proce- dures to improve -aumeeted LLMs for complex graph parsing problems. The work is lim- ited in two aspects due to the nature of LLM setup:
SMCalFlow
2
13.16
12.16
1.43
7.39
3
16.04
15.04
1.80
9.70
1 12.68
12.53
1.89
3.32
Ecommerce
14.63
14.51
1.94
3.61
3
14.92
14,80
1.94
3.65
(1) our evaluation has focused on the in-context learning setting where the LLM is not fine-tuned on domain-specific data. Although standard setting of modern LLMs, it is still of scientific interest to understand the interplay between parameter finetum- ing and the effectiveness of surrival-augmenntn procedures, which we leave for future work. (2) This work has focused on GPT3.5 which was one of the strongest and openly available LLMss at the time of the writing. As the behavior of LLM can be impacted by its pretraining procedures, it is also of interest to generalize this study wider class of LLMs. (3) Finally, the graph similarity metric considered in this work (i.e., SMATCH) has a com- putational complexity quadratic in graph size. The current work mitigates the issue by restricting its attention to degree-d subgraphs, with the caveat of limiting SUGAR's 's ability to reason about similarity in the global graph structure. Therefore identify- ing practical and more computationally efficient structure similarity metrics can further improve the scalability of the SUGAR approach.
Table 5: Correlations between number of required it- erations verses graph complexity, including number of nodes/edges (#Node/#Edge), average node degrees and graph depth (length of the longest path), where base retriever is CASPER-USE.
ing LLMs for complex graphs. This work deepens models
the current practice of for complex structures by incorporating informa- tion related to the model's uncertainty of graph component prediction and structural similarity of output subgraphs. Experimental results on two complex seq2seq semantic parsing tasks, i.e., SM- CalFlow and E-commerce, have demonstrated the practical effectiveness of the proposed approach in the modern setting of graph parsing with pre- trained LLMs.
Our future work includes considering more ad- vantage graph similarity metric beyond SMATCH (c.g., incorporates additional similarity metric be- tween the space of node and edge properties), and also larger scale and more fine-grained evaluation on graph parsing benchmarks with distinct proper- ties (e.g., long-tai generalization, graph of specific families) to further elucidate in what setting is the graph similarity most effective. Furthermore, it is also of interest to study the generalization of this approach to a broader class of modern program synthesis problems, e.g., code generation.
References
Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan DeLoach, Leah Dorner, Jason Eisner, Hao Fang, Alan Guo, David Hall, Kristin Hayes, Kellie Hill, Diana Ho, Wendy Iwaszuk, Smriti Jha. Dan Klein, Jayant Krishnamurthy, Theo Lanman, Percy Liang, Christopher H. Lin, Nlya Lintsbakh, Andy Mc- Goverm Aleksandr Nisnevich, Adam Pauls, Dmitrij Petters, Brent Read, Dan Roth, Subhro Roy, Jesse Rusak, Beth Short, Div Slomin, Ben Snyder, Stephon Striplin, Yu Su, Zachary Tellman, Sam Thomson, An- drei Vorobev, Izabela Witoszko, Jason Wolfe, Abby Wray, Yuchen Zhang, and Alexander Zotov. 2020. Task-oriented dialogue dataflow synthesis. Trans- actions of the Association for Computational Linguis- tics, 8:556-571.
Acknowledgement
Our work is sponsored in part by National Sci- ence Foundation Convergence Accelerator under award OIA-2040727 as well as generous gifts from Google, Adobe, and Teradata. Any opinions, findings, and conclusions or recommendations ex- pressed herein are those of the authors and should not be interpreted as necessarily representing the views, either expressed or implied, of the U.S. Gov- ernment. The U.S. Government is authorized to reproduce and distribute reprints for government purposes not withstanding any copyright annota- tion hercon. We thank Deepak Ramachandran for helpful discussion.
Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Kochn, Martha Palmer, and Nathan Schneider. 2013. Abstract Meaning Representation for sembanking. In Proceedings of the 7th Linguistic Annotation Workshop and Interoperabiliry with Dis- course, pages 178-186, Sofia, Bulgaria. Association for Computational Linguistics.

---

Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901.
approach for solving complex tasks. arxiv preprint arXiv:2210.02406
Haoran Li, Abhinav Arora, Shuohui Chen, Anchit Gupta, Sonal Gupta, and Yashar Mehdad. 2021. MTOP: A comprehensive multilingual task-oriented semantic parsing benchmark. In Proceedings of the 16th Conference of the European Chapter of the Asso- ciation for Computational Linguistics: Main Volume. pages 2950-200 2962. Online. Association for Computa- tional Linguistics.
Shu Cai and Kevin Knight. 2013. Smatch: an evaluation metric for semantic feature structures. In Proceed- ings of the 51st Annual Meeting of the Association for Computational Linguisties (Volume 2: Short Pa- pers), pages 748-752, Sofia, Bulgaria, Association for Computational Linguistics.
7i Lin, Jeremiah Liu, and Jingho Shang. 2022a. Neural- symbolic inference for robust autoregressive graph parsing via compositional uncertainty quantification. In Proceedings of the 2022 Conference on Empiri- cal Methods in Natural Language Processing, pages 4759 4776, Abu Dhabi, United Arab Emirates. As- sociation for Computational Linguisties.
Daniel Cer, Yinfci Yang, Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St John, Noah Constant, Mario Guajardo-Cespedder Steve Yuan, Chris Tar, al. 2018. Universal sentence encoder. arXiv preprint 1rXiv:1803.1111:
Ruixiang Cui, Rahul Aralikatte, Heather Lent, and Daniel Hershcovich. 2022. Compositional gener- alization multilingual semantic parsing over Wiki- data. Transactions of the Association for Computa- fional Linguistics, 10:937-955.
Zi Lin, Jeremiah Zhe Liu, and Jingbo Shang. 2022b. To- wards collaborative neural-symbolic graph semantic parsing via uncertainty. In Findings of the Associa- tion for Compulational Linguistics: ACL 2022, pages 4160-4173. Dublin, Ireland. Association for Compu- tational Linguistics.
Angela Fan, Yacine Jemnite, Ethan Perez, David Grang- ier, Jason Weston, and Michael Auli. 2019. ELI5: Long form question answering. In Proceedings of the 57th Anmual Meeting of the Association for Com- putational Linguistics, pages 3558-3567, Florence. Italy, Association for Computational Linguistics.
Zi Lin, Du Phan, Panupong Pasupat, Jeremiah Zhe Liu, and Jingbo Shang. 2023. On compositional uncer- tainty quantification for seq2seq graph parsing. In The Eleventh International Conference on Learning Representations.
Dan Flickinger, Emily M. Bender, and Stephan Oepen. 2014. Towards an encyclopedia of compositional semantics: Documenting the interface of the English Resource Grammar. In Proceedings of the Ninth In- ternational Conference on Language Resources and Evaluation (LREC"14) 14), pages 875-881, 1, Reykjavik, Iceland. European Language Resources Association (ELRA).
Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. 2015. Obtaining well calibrated proba- bilities using bayesian binning. In Proceedings of the AAAI conference on artificial intelligence, volume 29.
Stephan Oepen, Kristina Toutanova, Stuart Shieber. Christopher Manning, Dan Flickinger, and Thorsten Brants. 2002. The LinGO redwoods treebank: Mo- tivation and preliminary applications. In COLING 2002: The 17th International Conference on Compu- tational Linguistics: Project Notes.
Vivek Gupta, Akshat Shrivastava, Adithya Sagar, Armen Aghajanyan, and Denis Savenkov. 2022.
RetroNLU: Retrieval augmented task-oriented se- mantic parsing. In Proceedings of the 4th Work- shop NLP for Conversational Al, pages 184-196, Dublin, Ireland. Association for Computational Lin- guistics.
Juri Opitz. 2023. SMATCH++: Standardized and ex- tended evaluation of semantic graphs. In Findings of the Association for Computational Linguistics: EACL 2023, pages 1595-1607, Dubrovnik. Croatia. Association for Computational Linguistics.
Zhenghao Jiang, Frank F Xu, Luyu Gao, Zhiqing Sun, Qian Liu, Jane Dwivedi-Yuu Yu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023. Ac- tive retrieval augmented generation. arXiv preprint arXiv:2305.06983
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022. Training language models to follow instruc- tions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744.
Robert Kasper. 1989. flexible interface for link- ing applications to penman's 's sentence generator. In Speech and Natural Language: Proceedings of Workshop Held at Philadelphia, Pennsylvania, Febru- ary 21-23, 1989.
Panupong Pasupat, Yuan Zhang, and Kelvin Guu. 2021. Controllable semantic parsing via retrieval augmen- tation. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 7683-7698, Online and Punta Cana, Domini- can Republic. Association for Computational Lin- guistics.
Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sab- harwal, 2022. Decompased prompting: A modular

---

Ofrr Press. Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A Smith, and Mike Lewis. 2022. Measuring and narrowing the compositionality gap in language models. arXiv preprint arX::22200033350
Sean Welleck, Ximing Lu, Peter West, Faeze Brah- man, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. 2023. Generating sequences by learning to self-correct. In The Eleventh International Confer- ence on Learning Representations.
Linlu Qiu, Peter Shaw, Panupong Pasupat, Tianze Shi, Jonathan Herzig, Emily Pitler, Fei Sha, and Kristina Toutanova. 2022. Evaluating the impact of model scale for compositional generalization in semantic parsing. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 9157-9177 Abu Dhabi, United Arab Emirates. Association for Computational Linguisties.
Donggin Xu, Junhui Li, Muhua Zhu, Min Zhang, and Guodong Zhou. 2020. Improving AMR parsing with requence-to-seqqenee pre-training. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2501- 2511. Online. Association for Computational Lin- guistics.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2022. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.0362.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. 2020. Exploring the limits of transfer learning with unified text-to-text trans- former. The Journal of Machine Learning Research, 21(1):5485-555)
Yury Zemlyanskiy, Michiel de Jong. Joshua Ainslie, Panupong Pasupat, Peter Shaw, Linlu Qiu, Sumit Sanghai, and Fei Sha. 2022. Generate-and-retrieve: Use your predictions to improve retrieval for se- mantic parsing. In Proceedings of the 29th Inter- national Conference on Computational Linguistics, Gyeongju, Republic of Korea. In- ternational Committee on Computational Linguistics.
Machel Reid and Graham Neubig. 2022. Learning to model editing processes. Findings of the Associ- ation for Computational Linguistics: EMNLP 2022, pages 3822-3832, Abu Dhabi, United Arab Emirates. Association for Computational Linguisties.
pages
Stephen Robertson, Hugo Zaragoza, al. 2009. The probabilistic relevance framework: Bm25 and be- yond. Foundations and Trends in Information Re- trieval, 3(4):333-389
A Graph Matching Algorithm in SMATCH
In general, finding the largest common subgraph is a well-known computationally intractable prob- lem in graph theory. However, for graph parsing problems where graphs have labels and a simple tree-like structure, some efficient heuristics are proposed to approximate the best match by hill- climbing algorithm (Cai and Knight, 2013). The initial match is modified iteratively to optimize the total number of matches with a predefined number of iterations (default value set to 5). This algorithm is very efficient and effective, it was also used to calculate the SMATCH score in Cai and Knight (2013).
Ohad Rubin, Jonathan Herzig, and Jonathan Berant. 2022. Learning to retrieve prompts for in-context learning. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, pages 2655-2671, Seattle, United States. Association for Computational Linguistics.
Timo Schick, Jane A. Yu, Zhenghao Jiang, Fabio Petroni, Patrick Lewis, Gautier Izacard, Qingfei You, Christoforos Nalmpantis, Edouard Grave, and Sebas- tian Riedel. 2023. PEER: A collaborative language model. In The Eleventh International Conference on Learning Representations.
Hinrich Schutze, Christopher D Manning, and Prab- hakar Raghavan. 2008. Introduction to information retrieval. Cambridge University Press.
B Model Calibration
To explore the model calibration for parsing com- plex graph structure under in-context learning set- tings, we plot histgrams to how the correlation be- tween model probability and performance. Specif- ically, we use base retrievers USE-input, BM25- input and Random, and test them for GPT3.5's in- context learning settings on SMCalflow and Ecom- merce respectively. Results are shown in Figure 5, As can be seen from figures, the model is generally calibrated, i.c., high probability generally corre- sponds to high performance and vice versa. Our
Ivan Stelmakh, Yi Luan, Bhuwan Dhingra, and Ming- Wei Chang. 2022. ASQA: Factoid questions meet long-form answers. In Proceedings of the 2022 Con- ference on Empirical Methods in Natural Language Processing, pages 8273 8288, Abu Dhabi, United Arab Emirates. Association for Computational Lin- guistics.
Oriol Vinyals, & ukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015. Gram- mar foreign language. In Advances in Neural Information Processing Systems, volume 28, Curran Associates, Inc.

---

1.0
1.0
Nodo Accuracie
Nodelldge Accuracies
0.8
0.8
0.6
0.6
0.4
0.4
5.000 0.576 0.615
0.227
0.936 0.922 0.907 0.893
6.907
0.998
0.899 1.000
0.009
0.341 0.444
5.60
0.74 0.545 0.214
0.966
0.978
0.990 0.95 0.90
NodwFdge ProbabilRies
Nodw//dgg Probabiiitee
(a) Random (SMCalflow)
(b) Random (Ecommerce)
1.0
1.0
NodoERge Accuracis
Nodelddge Accuracies
0.8
0.8
0.6
0.4-
0.4
0.2
0.00L
0.783 0.979
L,000
0.2
9,12
0.991 9.909 Probablittes
NodwEEgge Probabiliies
(c) USE-input (SMCalflow)
(d) USE-input (Ecommerce)
Nooe/Enge Accurscies
Nooe/Ldge liccurscies
0.8
0.4
0.2
0.957
0.699
Node/dge Probabilitee
Node/Ecge Probabiittie
(e) BM25- AM25-inpul (SMCalflow)
BM25 BM25-input (Ecommerce)
Figure 5: Correlations between model probabilities and performance for node/edge prediction on SMCalFlow and Ecommerce using different retrieval strategies.
study confirms that model uncertainty is effective for detecting prediction errors. This means that we retrieve structurally similar exemplars targeting these uncertain substructures, which can help to address the flawed parts in the prediction.
D Detailed Experiment Settings
Parameter Settings For the uncertain threshold considering that at the initial stage, the model's s predictions are relatively weak, we set warm up schedule for Specifically, <1 0.5, 62 0.8, 6g 0.9. We set subgraph max depth 3. For each model prediction, the number of uncertain subgraphs = 3, and we will retrieve exemplars for each uncertain subgraph.
C Graph Linearization
We use PENMAN notation for graph lincarzation, which is originally called Sentence Plan Notation in the PENMAN project (Kasper, 1989). PEN- MAN serialization format for the directed, rooted graphs used encode semantic dependen- cies, mostly notably in the Abstract Meaning Rep- resentation (AMR) framework (Banarescu et al., 2013). looks similar to Lisp's S-Expression in using parentheses to indicate nested structures.
Models For in-context learning settings, con- sidering the impressive performance achieved by GPT3.5 (Ouyang et al., 2022), we test our meth- ods on text text-davince -003. For fine-tuning set- tings, we choose T5 (Raffel et al., 2020) as our pre- trained model, which is pre-trained sequence-to- sequence Transformer model that has been widely used in many NLP applications. We use the open- sourced T5X which is new and improved imple- mentation of T5 codebase in JAX and Flax. Specif- ically, we use the official pretrained T5-Large (770 million parameters).
To make PENMAN notation compatible with the seq2seq learning, adopted variable-free ver- sion of PENMAN which was first proposed in Lin al. (2022b). Table 6 shows some variable-free PENMAN lincarized examples for the two seman- tic parsing datasets we adopt in our experiments.
chttps://githhi com http:://gghtttboooooooollrreeeee

---

Datasets
Inputs
Outputs
start findEvent
:ARG1
SMCalflw
User: What Tuesday my planning meeting?
:ARGI ( EventSpec name "planning"
:start Timespec :weekday "tuesday"
__ship___caus
:ARG1 pron
:BV-of ( pronoun_q )
Ecommerce
You shipped the wrong
:ARG2 (_item_n_off
:BV-of ( __the_g
:ARG1-of (wwrong___with)
Table 6: Examples for variable-free PENMAN linearized graph Ecommerce and SMCalflow (task details can be found in Section 5. Here carg means corresponding spans the sentence.
Training Data For in-context learning, access the model through paid API and there is a limitation for sequence length, we sample subset of 1,000 test examples from each datasets for test set. For SMCalFlow, we only consider first- turn dialogue in order to reduce sequence length. The candidate pool for SMCalflow is set of 2,000 examples sampled from the standard training set. The candidate pool for Ecommerce is the standard development set (1.7K examples).
Prompt Exemplars from Base Retriever
Let's translate sentence Input Into a structured output.
Input: can't Find anywhere.
output: neg :ARG1 [ __con __can_v_nodal JARGT (_find_v_] JARGT
pron :BV-oF prooneuug :RGG pron
[pronaun_q ) :ARGT-of loc_nonsp :ARE2 ( place_n :BV-of Lanyy ) )
Input: I haven't received it yet.
output:
Figure 6: Prompt example contains exemplars from base retriever.
For fine-tuning settings, the training data for SM- CalFlow a set of 2,000 examples sampled from the standard training set, which also serves as the candidate pool for retrieval, and the test set is the standard development set (15K examples). The training set for Ecommerce is the Redwoods' in- domain dataset on Wall Street Journal (34K ex- amples), the test set and candidate pool are the standard test and development set of Ecommerce (I.IK and 1.7 examples respectively).
baseline retrievers: (1) CASPER using Universal Sentence Encoder (CASPER-USE: Pasupat et al., 2021); (2) GandR considering input and output sim- ilarity using BM25 with weight 0.5 (Zemlyan- skiy et al., 2022).
The evaluation results are reported in Table 7. As can be seen, other retreivers that do not con- sider structural similarity all fail on these two com- plex parsing tasks, i.c., perform even worse than base model without retrieval, while SUGAR can persistently improve base model on both datasets. Specifically, SUGAR achieves error reduction rate as 6.72% and 9.45% on SMCalflow and Ecom- merce respectively, and improves exact match rate by 2.72% and 8.38% respectively.
Prompt Design There are two prompts adopted in the in-context settings using GPT3.5. The first one contains exemplars from the base retriever to generate the preliminary prediction at the initial stage (prompt shown in Figure 6). The second one contains exemplars from uncertainty-guided retrieval and incorporates the prediction from the previous step (prompt shown in Figure 7).
F Results with Other LLMs
The results of SUGAR with text-davinci-On -002 and GPT4 are shown in Table 9. We can see that:
E Fine-tuning Results
(1) SUGAR successfully improves all LLMs in terms of exact match and graph similarities. Note that SUGAR Iter is comparable to BM25@8 given the same number of exemplars, and SUGAR Iter and Iter 3 can further improve the results without increasing the general sequence length of the prompt; (2) SUGAR with GPT3.5 also works better than GPT4 using base retriever. This con-
We conduct supplementry evaluation for fine- tuning settings, where we focus on low-resource (SMCalFlow) and out-of-domain (Ecommerve) set- tings?. Specifically, we compare SUGAR with two
hhttps: //api. openai. com/v1 /completions "Since the cost of fine-tuning is higher, we only need one iteration for fine-tuning settings.

---

SMCalFlow
Ecommerce
Name
Retriever
EM
Precision
Recall
SMATCH
EM
Precision
Recall
SMATCH
Base
60.29
83.70
86.59
85.12
51.44
92.75
94.15
93.44
GandR
BM25
56.20
82.53
84.78
83.12
48.93
92.15
93.53
92.83
CASPERusE
USE
55.84
82.55
84.30
83.42
49.53
92.40
93.68
93.03
SUGAR
SMATCH
61.93
85.19
87.26
86.12
55,75
93.95
94.16
94.06
Oracle
SMATCH
64.18
86.46
88.38
87.39
56.73
94.08
94.48
94.28
Table 7: Fine-tuning results. EM means exact match rate. Precision and recall are based on graph element triples.
Prompt Exemplars from Iterative Retrieval
node pron from the first to second iteration in the second example (the probability decreases from 0.9381 to 0.8746). We reserve this observation for further exploration in future work, which we believe is promising direction for understanding LLMs' calibration in complex structure generation.
Ter's rix model output outpute based on some examples
you
yet?
output: _.reeeive.v. v_1 :ARG) pron :B pronoun_e
:Byrof __the_g :ARG1-of corpound
:ARG2 nared :BV-of proper_g :carg Sienens } scorg :ARGI-of __ve____1)
Input: haven't received it yet.
outpute:
__receive.x_1 pron :BV-of prooooun. ) :ARG2 pron :8v-of pronoun_q :ARG1-of _yet_r
output:
Figure 7: Prompt example contains exemplars from iterative retriever.
cretely shows method provides non-trivial im- provement beyond what can be achieved by simply upgrading architecture. We will experiment with SUGAR+GPT4 future work (cannot do it right now due to API limitations).
Model
Retriever
EM
SMATCH
GPT-4
BM25@8
33.20
78.21
text-davinci-O01
BM25@8
27.00
73.28
text-davinci- -000
SUGAR Iter
43.30
83.06
text-davinci-002
SUGAR Iter
52.70
83.76
text-davinci-002
SUGAR Iter
53.50
84.42
Table 9: SUGAR with text-davinci-002 and GPT4
on SMCalflow task.
G Sample Graph Prediction Visualizations
Some sample graph prediction visualizations on Ecommerce dataser using CASPER-USE are shown in Table 8. We can observe that as itera- tion goes, the confidence scores of uncertain graph elements generally increase and the number of un- certain graph elements generally decreases.
However, we also observe occasional fluctua- tions in the uncertainty, which can trigger insta- bility neighboring contexts. For example, the

---

Sentence
have received two shipments from you for one order.
Iterl
Gelrer lncemtaaiio werkheryula
FEMU
L. Porion Dkeip
Iter2
Iter3 Sentence
I need the instruction about returning goods and repayment.
AMM
LANE
2001
JE1 aod
ABCS
DF
Iterl
Iter2
MCC
LAME
dnd
ABGI VORTONNN
D'
pol (1NES
Iter3
METTAO Kalk LUS0IIIII
proh aprrac:

---

Sentence
You sent me the wrong camcorder!
BY
Iterl
Le CORBORRRRIOI
Iter2
PORCIONNUSS
Iter3
Table 8: Sample graph prediction visualizations for iterative progression. Red refers to uncertain graph elements and blue refers to confident neighbor contexts.


Reviews:
[{"review_id": "RRseTTzFbq", "reviewer": "Reviewer_yeis", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "Dear Reviewer yeis,\n\nWe really appreciate your comments. We hope our following point-to-point response can address your concerns.\n\n1. *Evaluation can be more rigorous across various tasks.*\n- We evaluate different aspects of model behavior under a variety of controlled settings across two tasks of varying complexity in terms of linguistic diversity and complexity of the output, including\n    - **Retrieval performance:** As measured by similarity to gold graph (StoO in Table 1) and case study of retrieved examples (Table 2).\n    - **Model calibration:** As measured by correlations between model probabilities and performance (Figure 2), and compositional ECE (Table 3).\n    - **Final prediction performance**: as measured by sequence exact match and graph similarity (EM and SMATCH in Table 1 and Figure 4)\n- Understandably, there are always spaces for further improvement of our evaluations, and we will value any suggestions on the specific aspects of the evaluation for improvement.\n\n2. *Computational complexity needs to be reduced across the abord esp. given the context of graph parsing problems.*\n- Yes, computational complexity is especially important for graph parsing problems. As can be seen in Section 4.1.3 (line 345-354), we have proposed a practical implementation with (1) retrieval based on uncertain subgraphs and (2) pre-filtering for the candidate pool to reduce complexity. We have included a detailed discussion of the theoretical complexity in this section.\n- Also please note that the framework we proposed is general and independent of specific algorithmic implementations. Although we selected relatively classic algorithms (SMATCH) in this work to ensure consistency with the literature, the proposed framework can always benefit from more advanced algorithms in the future.\n\n3. *The evaluation of the proposed approach has focused on the in-context learning setting where the LLM is not fine-tuned on domain-specific data.*\n- Thanks for this question. In fact, we have also investigated the performance of SUGAR in the fine-tuning settings (see Appendix D&E), where we find that SUGAR can also improve the performance of the base model and outperform other retrievers (GandR and CASPER_USE) on both SMCalflow and Ecommerce datasets.\n\n4. *The choice of LLM itself is can have implications when upgraded to more latest architectures (beyond GPT 3.5). (behavior of LLM can be impacted by its pre-training procedures and generalization with wider class of LLMs can be an open question)*\n- We adopt two LLMs in the paper, one is GPT3.5 (text-davinci-003) for in-context learning setting (Section 5.1), and the other is T5 for fine-tuning setting (Appendix D&E), and both can achieve performance improvements. Unfortunately, OpenAI API does not support token-level probabilities for models beyond GPT3.5, which makes it not possible to experiment with uncertainty-based methods with GPT-4.\n- Alternatively, to answer the reviewer's question regarding the impact of the base pre-trained model on method performance, we conducted the following two sets of experiments: (1) a comparison between SUGAR and its baseline variants based on older variants of GPT models (e.g., text-davinci-002) which differ in training method. (2) comparison of baseline methods under GPT-4 v.s. SUGAR under GPT-3.5, to understand if the benefit of SUGAR is orthogonal to base model choice, and cannot be surpassed by simply upgrading model model architecture.\n- All the results are summarized as follows (using base retriever BM25 for SMCaflow task):\n\n| Model            | Retriever    | EM        | Precision | Recall    | SMATCH    |\n|------------------|--------------|-----------|-----------|-----------|-----------|\n| GPT-4            | BM25@8       | 33.20     | 74.57     | 82.22     | 78.21     |\n|                  |              |           |           |           |           |\n| text-davinci-002 | BM25@8       | 27.00     | 68.74     | 78.46     | 73.28     |\n| text-davinci-002 | SUGAR Iter 1 | **43.30** | **78.94** | **87.63** | **83.06** |\n| text-davinci-002 | SUGAR Iter 2 | **52.70** | **79.58** | **88.40** | **83.76** |\n| text-davinci-002 | SUGAR Iter 3 | **53.50** | **79.95** | **89.41** | **84.42** |\n|                  |              |           |           |           |           |\n| text-davinci-003 | BM25@8       | 31.80     | 71.28     | 81.69     | 76.13     |\n| text-davinci-003 | SUGAR Iter 1 | **49.80** | **80.48** | **90.93** | **85.38** |\n| text-davinci-003 | SUGAR Iter 2 | **56.00** | **81.91** | **92.00** | **86.67** |\n| text-davinci-003 | SUGAR Iter 3 | **59.10** | **83.37** | **92.28** | **87.60** |\n|                  |              |           |           |           |           |\n| T5               | GandR@3      | 56.20     | 82.53     | 84.78     | 83.12     |\n| T5               | CASPER_USE@3 | 55.84     | 82.55     | 84.30     | 83.42     |\n| T5               | SUGAR@3      | **61.93** | **85.19** | **87.26** | **86.12** |\n\n- As can be seen from the table:\n    - SUGAR successfully improves all LLMs in terms of exact match and graph similarities. Note that SUGAR Iter 1 is comparable to BM25@8 given the same number of exemplars, and SUGAR Iter 2 and Iter 3 can further improve the results without increasing the general sequence length of the prompt. \n    - SUGAR with GPT3.5 also works better than GPT4 using base retriever. This concretely shows our method provides non-trivial improvement beyond what can be achieved by simply upgrading architecture. We will experiment with SUGAR+GPT4 in future work (cannot do it right now due to API limitations).\n    - For fine-tuning since the training process is expensive compared to in-context learning, we only do one round of retrieval, and it can consistently outperform other retrievers.\n\n5. *Clarity around assumptions on distribution of the data being representative or not-representative of the retrieved exemplars may help.*\n- Regarding the data distribution of the retrieval candidate pool and the test data, we make the standard assumptions that the distribution of the retrieval candidate pool is representative of the distribution of the test data (within the same domain), which is adapted in many retrieval related work ([Pasupat et al.](https://doi.org/10.18653/v1/2021.emnlp-main.607), 2021; [Gupta et al.](https://doi.org/10.18653/v1/2022.nlp4convai-1.15), 2022; [Zemlyanskiy et al.](https://aclanthology.org/2022.coling-1.438), 2022).\n\n6. *Details around computational complexity & cost of the retrieval process or the overall complexity of the approach can help.*\n- Please refer to discussion in point 2.", "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": "1.\tThe research idea of the paper is interesting (leverages both structural similarity and model uncertainty).\n2.\tPaper is crisp, well-structured and detailed.\n3.\t", "reasons_to_reject": "1.\tEvaluation can be more rigorous across various tasks. \n2.\tComputational complexity needs to be reduced across the abord esp. given the context of graph parsing problems.\n3.\tThe evaluation of the proposed approach has focused on the in-context learning setting where the LLM is not fine-tuned on domain-specific data.\n4.\tThe choice of LLM itself is can have implications when upgraded to more latest architectures (beyond GPT 3.5). (behavior of LLM can be impacted by its pre-training procedures and generalization with wider class of LLMs can be an open question)\n5.\tClarity around assumptions on distribution of the data being representative or not-representative of the retrieved exemplars may help. \n6.\tDetails around computational complexity & cost of the retrieval process or the overall complexity of the approach can help.\n", "questions_to_authors": "", "paper_topic_and_main_contributions": "Authors of this paper propose a novel approach called Structure-aware and Uncertainty-Guided Adaptive Retrieval (SUGAR) that leverages both structural similarity and model uncertainty to improve retrieval-augmented parsing for complex graph problems. It works towards refining the model’s prediction through exemplars retrieval that closely align with the uncertain parts of the model prediction. They apply the solution on two real-world complex graph parsing benchmarks showing that SUGAR outperforms their classical counterparts that do not leverage uncertainty or structure.", "excitement": 4, "reproducibility": 3, "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": "EKX3keco7e", "reviewer": "Reviewer_GY72", "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": "Dear reviewer GY72,\n\nWe hope our response can address your concerns.\n\n**Regarding $y_c$ and $v$:**\n- $y_c$: candidate graphs in the candidate pool, which is used for retrieving the exemplars. $y_c$ is a gold graph, not a generated graph.\n- $v$: the uncertain graph element from the preliminary prediction, e.g., the red square in Figure 3.\n\nWe will include a more detailed explanation in the caption of Figure 3 to make it more understandable.\n\n**Intuitive description of the retrieval process:**\n\nThe overview of the retrieval process is shown in Figure 1, which includes the following steps:\n- **Graph uncertainty quantification for preliminary prediction (Section 4.1.1):** We will quantify the uncertainty of graph element $v$ based on the prediction using a base retriever (a retriever that only considers input sentence similarity). This step can help us to locate the uncertain parts of the generated graph.\n- **Uncertain subgraph construction (Section 4.1.2):** An uncertain subgraph (dotted square in Figure 3), which includes uncertain element $v$ (red square in Figure 3) and relatively confident neighbors (blue square in Figure 3), will serve as a query in the retrieval process. The intuition is that, given the model is relatively calibrated, the uncertain parts are likely to be incorrect, and the relatively confident neighbors are likely to be correct, so **we can utilize the uncertain subgraph to retrieve a similar gold subgraph that can help the model to address the uncertain parts**. Considering uncertain subgraphs instead of the entire graph can also reduce the computational complexity of structural similarity measurement.\n- **Structural-aware Retrieval (Section 4.1.3)**: To identify informative graph exemplars that best address the model uncertainty in predicting graph elements, **we leverage the uncertain subgraph mentioned above and consider a retrieval policy using uncertain subgraph as a query and retrieve structurally similar exemplars in candidate pool consisting of candidate graphs $y_c$**. The motivation for using structural similarity has been illustrated in Section 3.1, where we have shown that for complex parsing problems, exemplars that are similar in structure can help more for in-context learning compared to exemplars similar in input sentences or similar in output sequence (e.g., using BM25).\n\nThe above process can be operated in an iterative manner to progressively improve the generation performance.", "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": "Conducting research work demonstrates that relying solely on input text for knowledge retrieval is not reasonable in the semantic parsing task. I think this point is important\n", "reasons_to_reject": "you should give a detailed description of Figure 3\nline 333-line 343, what is the difference between yc and v, and how to do the retrieve, using uncertain subgraph to....?\nplease give an intuitive description of the retrieval process. If the yc is the generated graph, using an uncertain subgraph to retrieve the generated graph, I am not sure if this method is right or wrong", "questions_to_authors": "", "paper_topic_and_main_contributions": "topic: retrieval-augmented LLM\nmain contribution: \n1) Conducting research work demonstrates that relying solely on input text for knowledge retrieval is not reasonable in the semantic parsing task.\n2) Introduce the SUGAR method as a solution to overcome the previous limitation.", "excitement": 3, "reproducibility": 3, "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": "8J1uimJMqF", "reviewer": "Reviewer_Gxdf", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Dear Reviewer Gxdf,\n\nWe really appreciate your comments. We hope our following point-to-point response can address your concerns.\n1. *It is not shown whether GAP is significantly better than the confidence of the graph element for the confidence estimation. An ablation study should be included.*\n- GAP is the first probabilistic framework that can map sequence-level probabilities to graph-level probabilities for quantifying a seq2seq model’s structural uncertainty on graph elements. Given that we need to consider structural uncertainty in our problem settings, GAP is the only framework we can adopt for uncertainty quantification at the graph level.\n- To address your concern, we further conduct an ablation study using only token-level uncertainty and retrieve uncertain sub-sequence of the output using token-level similarity BM25, following similar settings as SUGAR. This setting is the same as FLARE without considering any structural information (so we termed it FLARE here). The results on SMCalflow at the first iteration are shown as follows:\n| Model  | EM        | Precision | Recall    | SMATCH    |\n|--------|-----------|-----------|-----------|-----------|\n| BM25@8 | 31.80     | 71.28     | 81.69     | 76.13     |\n| FLARE  | 32.70     | 74.54     | 82.18     | 78.17     |\n| SUGAR  | **49.80** | **80.48** | **90.93** | **85.38** |\n- As shown in the table, FLARE works slightly better than baseline model BM25@8 using the same number of retrieved exemplars but works much worse than SUGAR. This is because those uncertain sub-sequences do not necessarily correspond to a meaningful sub-graph structure, and will be difficult for a retriever to find an informative candidate, e.g., for a graph (tree) prediction as:\n```\n    A\n   / \\\n  B   C\n / \\\nD   E\n```\n- which is linearized as A(B(D,**E**),C). If the uncertain graph element is **E**, for SUGAR, the uncertain subgraph is B(D,**E**), while for FLARE, the uncertain sub-sequence is (D,**E**),C, which are all leave nodes that have no direct dependencies to form an informative context for retrieval. \n\n2. *Using uncertainty for the retrieval decision or iterative retrieval are not novel ideas. FLARE, which was also cited, is an example.*\n- The paper focuses on the joint exploitation of two sources of information: (1) structural similarity; (2) structural uncertainty.\n- FLARE is a concurrent work to ours, and is a reduced variant of our work. It only considers token-level similarity (BM25) and token-level uncertainty (FLARE = SUGAR without structural information), which is fine for question-answering tasks (where the output is naturally a sequence). However, for parsing complex structured outputs, simply considering token-level information is behind satisfaction (as shown in Table 1). Furthermore, in the above ablation study, we have shown that FLARE could fail to retrieve informative graphs compared to SUGAR. As a result, FLARE can be less effective than SUGAR in exploiting structured information for graph problem domains.\n\n3. *As LLM is used, generative multi-hop retrieval methods could be more effective than the proposed method. It is uncertain whether this would be the most effective approach on top of LLMs.*\n- Thanks for this question. Indeed, [generative multi-hop retrieval (GMR)](https://aclanthology.org/2022.emnlp-main.92/) bears some similarities to our work in that it performs iterative retrieval, and the retrieval function itself relies on LLM. While GMR can be a powerful method for non-structured problems (e.g., QA) with LLM, it is less suitable for the current setting we focus on (i.e., unsupervised retrieval in graph problem domain). The main reasons are two: (1) to the knowledge of the authors, the retrieval model $p_{LLM}$ (candidate graph | query graph) that GMR relies on needs to be trained; (2) similar to FLARE, GMR is also not designed to exploit structural information, which can be less effective for graph parsing problems.\n- Thanks again for mentioning this relevant work, we will include generative multi-hop retrieval as a related work in Section 2 and include the above discussion.", "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": "They showed the proposed iterative retrieval approach's effectiveness both quantitatively and qualitatively.\nThe approach is suitable especially for the semantic parsing, which is with different properties compared to general iterative retrievals. Using GAP for the uncertainty estimation and SMATH as the metric look proper decisions.", "reasons_to_reject": "1. It is not shown whether GAP is significantly better than the confidence of the graph element for the confidence estimation. An ablation study should be included.\n2. Using uncertainty for the retrieval decision or iterative retrieval are not novel ideas. FLARE, which was also cited, is an example.\n3. As LLM is used, generative multi-hop retrieval methods could be more effective than the proposed method. It is uncertain whether this would be the most effective approach on top of LLMs.", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper is about retrieval augmented semantic parsing using LLM. It uses iterative retrieval, where each iteration conducts uncertainty estimation and uses the neighbors of the uncertain nodes as the input for the additional retrieval.\nFor the uncertainty estimation, Graph Autoregressive Process (GAP) is used instead of just the confidence of the graph element.\nSMATCH is used as the semantic retrieval evaluation metric.\n\nThey showed the proposed iterative retrieval approach's effectiveness both quantitatively and qualitatively.\n\nSome issues are:\n1. It is not shown whether GAP is significantly better than the confidence of the graph element for the confidence estimation. An ablation study should be included.\n2. Using uncertainty for the retrieval decision or iterative retrieval are not novel ideas. FLARE, which was also cited, is an example.\n3. As LLM is used, generative multi-hop retrieval methods could be more effective than the proposed method. It is uncertain whether this would be the most effective approach on top of LLMs.", "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": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a hybrid method to improve graph-based parsing in realistic contexts. A number of experimental choices could be explained and motivated better. However, the proposal is considered valid and the task relevant.
Decision: Accept-Findings