# AnswerQuest: A System for Generating Question-Answer Items from Multi-
Paragraph Documents

Melissa Roemmele† Deep Sidhpura◇ Steve DeNeefe† Ling Tsou†
SDL Research, Los Angeles, CA, USA
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

00footnotetext: ◇Current affiliation: eBay Inc., San Jose, CA, USA

One strategy for facilitating reading comprehension is to present information
in a question-and-answer format. We demo a system that integrates the tasks of
question answering (QA) and question generation (QG) in order to produce Q&A
items that convey the content of multi-paragraph documents. We report some
experiments for QA and QG that yield improvements on both tasks, and assess
how they interact to produce a list of Q&A items for a text. The demo is
accessible at qna.sdl.com.

##  1 Introduction

Automated reading comprehension is one of the current frontiers in AI and NLP
research, evidenced by the frequently changing state-of-the-art among
competing approaches on standard benchmark tasks (e.g. Wang et al., 2018).
These systems aim to reach the standard of human performance, but they also
have the potential to further enhance human reading comprehension. For
instance, many demonstrations of reading comprehension involve eliciting
answers to questions about a text. Meanwhile, educational research and
conventional writing advice indicate that structuring information in a
question-and-answer format can aid comprehension Knight (2010); Raphael
(1982). Accordingly, systems that present content in this format by
automatically generating and answering relevant questions may help users
better understand the content.

The two NLP tasks essential to this objective, question answering (QA) and
question generation (QG), have received a lot of attention in recent years.
Recent work has started to explore the intersection of QA and QG for the
purpose of enhancing performance on one or both tasks Sachan and Xing (2018);
Song et al. (2018); Tang et al. (2018); Yuan et al. (2017). Among application
interfaces that demo these tasks, most have focused on either one or the other
Kaisser (2008); Kumar et al. (2019). Krishna and Iyyer (2019) presented a
system that integrated these tasks to simulate a pedagogical approach to human
reading comprehension. In our work, we demo an end-to-end system that applies
QA and QG to multi-paragraph documents for the purpose of user content
understanding. The system generates a catalog of Q&A items that convey a
document’s content. This paper first presents some focused contributions to
the individual tasks of QA and QG. In particular, we examine the challenging
task of QA applied to multi-paragraph documents and show the impact of
incorporating a pre-trained text encoding model into an existing approach.
Additionally, we report a new set of results for QA that assesses
generalizability between datasets that are typically evaluated separately. For
QG, we demonstrate the benefit of data augmentation by seeding a model with
automatically generated questions, which produces more fluent and answerable
questions beyond a model that observes only the original human-authored data.
In combining the two tasks into a single pipeline, we show that the
information given by the generated Q&A items is relevant to the information
humans target when formulating questions about a text.

The demo is implemented as a web application in which users can automatically
generate Q&A pairs for any text they provide. The web application is available
at qna.sdl.com, and our code is at github.com/roemmele/answerquest.

##  2 Question Answering

###  2.1 Model Overview

Our demo implements extractive QA, where answers to questions are extracted
directly from some given reference text. State-of-the-art systems have
utilized a classification objective to predict indices of answer spans in the
text. This approach has achieved success when the reference text is limited to
a single paragraph Devlin et al. (2019). However, QA for multi-paragraph
documents has proven to be more difficult. Our system addresses this
challenging document-level QA task by adapting an existing method to
additionally leverage a pre-trained text encoding model.

Existing work on document-level QA has proposed a pipelined approach that
first applies a retrieval module to select the most relevant paragraphs from
the document, and then a reader module for extracting answers from the
retrieved paragraphs Chen et al. (2017); Yang et al. (2019). During training,
each of the retrieved paragraphs and the corresponding questions are observed
independently. To predict answers, the model scores candidate answer spans
within each of the paragraphs, ultimately predicting the one with the highest
score across all paragraphs. One problem is that the candidate answer scores
across paragraphs might not be comparable, since each paragraph-question pair
is treated as an independent training instance. To address this issue, Clark
and Gardner (2018) suggested a shared-normalization approach (which we refer
to here as BiDAF Shared-Norm) where paragraph-question pairs are still
processed independently, but answer probability scores are globally normalized
across the document. In their work, they selected the top-k most relevant
paragraphs for a given question using a TF-IDF heuristic. They then encoded
the question and these paragraphs into a neural architecture consisting of GRU
layers and a Bi-Directional Attention Flow (BiDAF) mechanism Seo et al.
(2017). On top of this model is a linear layer that predicts the start and end
token indices of the answer within a paragraph, using an adapted softmax
function with normalization across all top-k paragraphs for the question.

Another document-level QA system, RE3QA Hu et al. (2019), incorporated the
text encoding model BERT Devlin et al. (2019). BERT has been successfully used
for numerous reading comprehension tasks. In contrast to BiDAF Shared-Norm,
RE3QA combined paragraph retrieval and answer prediction into a single end-to-
end training process, applying BERT to both steps. Because it obtained
favorable results relative to the BiDAF Shared-Norm approach, we were curious
to assess the isolated impact of BERT specifically on the answer prediction
component of the pipeline. Therefore we adapted Clark and Gardner’s shared-
normalization approach by replacing their GRU BiDAF encoder with the BERT-
Base-Uncased encoder. Wang et al. (2019) used a similar approach for open-
domain QA, where answers are mined from the entirety of Wikipedia. We instead
evaluate QA with reference to a single document, for which the impact of BERT
on the shared-normalization approach has not yet been documented.

We refer to our model here as BERT Shared-Norm. To rank paragraph relevance to
a question, we rely on TF-IDF similarity. During training, we retrieved the
top k=4 paragraphs. The BERT Shared-Norm model consists of the BERT-Base-
Uncased pre-trained model, which encodes the paragraph and question in the
same manner as Devlin et al.’s paragraph-level QA model. The rest of our model
is the same as BiDAF Shared-Norm: the softmax output layer predicts the start
and end answer tokens and the same shared-normalization objective function is
applied during training. The model can predict that a question is
‘unanswerable’ by observing an index of 0 for the end token. During inference,
the highest-scoring answer span across paragraphs is predicted as the answer.
See Appendix A.1 for more details.

###  2.2 Dataset

Our QA experiments utilized the SQuAD Rajpurkar et al. (2016) and NewsQA
Trischler et al. (2017) datasets. SQuAD is derived from Wikipedia articles,
while NewsQA consists of CNN news articles. Both datasets were developed
through crowdsourcing tasks where participants authored questions and
identified their answers, resulting in text-question-answer items where each
answer is a span within the text. There are two versions of SQuAD. SQuAD-1.1
contains 87,599 train and 10,570 test items. SQuAD-2.0 contains an additional
42,720 train and 1,303 test items (a total of 130,319 and 11,873,
respectively), distinguished from SQuAD-1.1 by including questions that do not
have answers in the text. NewsQA contains 107,674 and 5,988 train and test
items, respectively. As with SQuAD-2.0, some of these questions are
unanswerable.111The SQuAD test items we use are actually the items from their
‘dev’ (development) set: rajpurkar.github.io/SQuAD-explorer. Their official
test set is withheld. The other published systems we compare against also
report evaluations on this dev set, so for simplicity we refer to it here as
the test set. Similarly, we use the dev NewsQA items as our held-out test set:
github.com/Maluuba/newsqa.

SQuAD questions pertain to a single paragraph. Paragraphs are grouped by
document and can be concatenated for document-level QA. There are on average
43 paragraphs per document. Paragraph boundaries are not explicit in the
NewsQA texts, so we treated each text as a multi-paragraph document by
splitting it into chunks of 300 tokens, resulting in 2.55 average paragraphs
per document.

###  2.3 Evaluation

####  2.3.1 Comparison with other Systems

We first evaluated our BERT Shared-Norm model on SQuAD-1.1 for comparison with
the BiDAF Shared-Norm and RE3QA results reported for this dataset. We used the
official SQuAD evaluation scripts provided by the website. For direct
comparison with BiDAF Shared-Norm, we replicated their setting of k=15 for
paragraph retrieval. Table 1 shows the results in terms of the exact match
(EM) and F1 accuracy of answers. We improve upon the result for BiDAF Shared-
Norm, demonstrating the beneficial impact of incorporating BERT into this
approach. The BERT-based RE3QA still outperforms our model, suggesting that
its other components outside the BERT encoding for answer prediction
additionally contribute to its success.

Model | EM | F1
---|---|---
BiDAF Shared-Norm | 64.08 | 72.37
RE3QA | 77.90 | 84.81
BERT Shared-Norm | 72.85 | 80.58
Table 1: QA results on SQuAD-1.1

####  2.3.2 Generalizability across Datasets

Our demo accepts any arbitrary text supplied by a user, and we ultimately aim
to produce informative Q&A items for varying content domains. State-of-the-art
QA systems have matched human-level performance on individual datasets like
SQuAD, but it is unclear how much this performance generalizes across
different datasets. As a narrow assessment of this issue, we examined the
generalizability between SQuAD and NewsQA by alternatively training and
evaluating BERT Shared-Norm on different combinations of these datasets.

Table 2 shows the results of this experiment. We trained three different BERT
Shared-Norm models on separate datasets: SQuAD-2.0, NewsQA, and SQuAD-2.0 \+
NewsQA combined (which we term MegaQA). We then evaluated each of these models
on the SQuAD-2.0 and NewsQA test sets. Note that the experiments in Section
2.3.1 were evaluated on SQuAD-1.1 for comparison with the other approaches.
Here, we only evaluate on SQuAD-2.0, which involves additionally predicting
when a question does not have an answer span in the document. For these
evaluations, consistent with training, we retrieved the top k=4 paragraphs
from each document for answer prediction.

Train Data | Test Data
---|---
SQuAD-2.0 | NewsQA
EM | F1 | EM | F1
SQuAD-2.0 | 71.37 | 74.65 | 40.88 | 48.67
NewsQA | 45.85 | 49.88 | 52.68 | 61.26
MegaQA | 70.29 | 73.55 | 53.85 | 62.46
Table 2: Generalizability of BERT Shared-Norm across datasets

The results reveal a generalizability problem, where the model trained on
SQuAD-2.0 fails to perform as well on NewsQA and vice-versa, presumably due to
their domain difference (Wikipedia vs. Newswire). However, combining the
datasets with the MegaQA model generalizes well to both. Related to this,
Talmor and Berant (2019) found combining multiple datasets from different
domains to be advantageous for BERT-based reading comprehension models. Based
on these results, the BERT Shared-Norm MegaQA model is currently integrated
into our demo.

##  3 Question Generation

###  3.1 Model Overview

We follow the same paradigm of much recent work on QG, which has applied
encoder-decoder (i.e. sequence-to-sequence) models to text-question pairs Du
et al. (2017); Duan et al. (2017); Scialom et al. (2019); Song et al. (2018);
Zhao et al. (2018). Similar to Scialom et al., we utilize the Transformer
architecture for the encoder and decoder layers of the model, and enhance the
decoder with a copy mechanism. The encoder input is a single sentence and the
decoder output is a question, where the input sentence contains the answer to
the question. Following the standard procedure for sequence-to-sequence model
training, we used the cross-entropy of the output question tokens as the loss
function. When generating questions, we use a beam size of 5. See Appendix A.2
for further details.

###  3.2 Dataset

We trained and evaluated the model on SQuAD and NewsQA concatenated, the same
datasets used for the QA experiments. Our QG model aims to produce questions
whose answers are contained in their corresponding input texts, so we only
included SQuAD-1.1 items and answerable NewsQA items (this excluded 32,764
NewsQA items from the train and test sets). For each paragraph-question-answer
item, we sentence-segmented the paragraph, isolated the sentence with the
answer span, and inserted special tokens into the sentence ($<$ANSWER$>$ and
$<$/ANSWER$>$) designating the start and end of the span. These answer-
annotated sentences were the model inputs and the aligned questions were the
target outputs. We applied Byte-Pair-Encoding (BPE) tokenization Sennrich et
al. (2016) to the inputs and targets (see Appendix A.2). We used the same
train-test dataset splits as the QA experiments, allocating a small subset of
training items to a validation set for hyperparameter tuning. Overall the
train, validation, and test sets consisted of 160,876, 3,281, and 14,910
sentence-question pairs, respectively.

###  3.3 Data Augmentation Experiments

We examined three different versions of the model described in 3.1,
differentiated by their training inputs. The purpose of this experiment was to
assess using the output of a rule-based QG system as a means of augmenting the
training data. We specifically evaluated the three configurations below:

Standard: In this model, no data augmentation was applied. We trained the
model directly on the SQuAD/NewsQA items described in 3.2.

RuleMimic: This model observed only the automatically generated augmentation
data, without the original data. The source of the augmentation data was the
QG system by Heilman and Smith (2010)222Code at
cs.cmu.edu/$\sim$ark/mheilman/questions. This system applies linguistic rule-
based transformations (i.e. clause simplification, verb decomposition,
subject-auxiliary inversion, and wh-movement) to convert a sentence into a
question answered by the sentence, then scores the fluency of the question
using a statistical model. Du et al. (2017) found favorable results for a
neural sequence-to-sequence approach relative to this rule-based system, but
we were curious about its use as a strategy for augmenting our training data.
We anticipated that a neural model could learn to ‘mimic’ the system’s generic
transformation rules by observing its inputs and outputs. Thus, we applied the
system to the raw paragraphs in the SQuAD/NewsQA training set, which resulted
in 1,531,233 questions, each aligned with a sentence. We then followed the
same steps described in 3.2 to tokenize the sentence and mark the answer span.
The training set for this model consisted only of these automatically
generated questions (1,500,610 train items with 30,623 used for validation),
with no human-authored questions.

Augmented: This model observed both the original data seen by the Standard
model and the augmentation data seen by the RuleMimic model, via a two-stage
fine-tuning process. After training the RuleMimic model, we used its
parameters to initialize another model, then fine-tuned this new model on the
Standard model dataset. The hypothesis behind this approach is that it can
simulate linguistic rules underlying question formulation, while also
capturing the more abstractive features of human questions that are harder to
derive using deterministic syntactic and lexical transformations.

###  3.4 Evaluation

Many QG systems are evaluated using BLEU or similar metrics that reward
overall token overlap between generated and human-authored questions. However,
Nema and Khapra (2018) argue that these metrics are ill-suited for QG. In
particular, comparatively fluent questions with the same answer could have few
tokens in common. Moreover, certain tokens within a question have far more
impact than others on its perceived quality. They encourage alternative
metrics that focus instead on the ‘answerability’ of questions. Guided by
this, we conducted both automated and human ratings-based evaluations in order
to assess the answerability of our QG output. Because our demo performs
extractive QA, our evaluations focus on whether questions are answerable
relative to the input text from which the question is generated.

####  3.4.1 Automated Evaluation

Some work has utilized automated QA as a scoring metric for QG systems, based
on the rationale that a QA system’s ability to predict correct answers to
generated questions indicate how well the questions are formulated to elicit
these answers Duan et al. (2017); Zhang and Bansal (2019). Following this
idea, we generated questions for sentence inputs in the SQuAD/NewsQA test set.
As with the training inputs, these inputs were derived by annotating the
answer span of the corresponding human-authored question for the paragraph,
and isolating the sentence containing that span. We then provided each
generated question and corresponding paragraph to the BERT Shared-Norm MegaQA
model described in Section 2. The results for each QG model in terms of answer
F1 accuracy are shown in Table 3, compared alongside the result for human-
authored questions.

As shown, the questions generated by the RuleMimic model are much better at
eliciting the designated answers than the Standard model questions, indicating
that observing the rule-generated questions alone is impactful. Additionally,
the Augmented model generates more answerable questions than the RuleMimic
model, showing the usefulness of combining rule-generated questions with
human-authored questions as a data augmentation strategy.

Model | F1
---|---
Standard | 0.354
RuleMimic | 0.503
Augmented | 0.551
Human | 0.718
Table 3: Accuracy of QA system on QG output

####  3.4.2 Human Evaluation

Model |  Rating |  Answer Present
---|---|---
Standard |  2.813 |  0.225
RuleMimic |  2.934 |  0.381
Augmented |  3.140 |  0.399
Human |  3.776 |  0.793
Table 4: Human assessment of QG output

We also elicited human judgments for a subset of the same generated questions.
Participants were recruited from an internal team of linguists as well as
Amazon Mechanical Turk (AMT). We selected questions corresponding to 175
inputs. Table 5 in the appendix shows examples of these items. Participants
read the input sentence in its paragraph context, then observed all four
questions associated with the input (one generated by each of the three models
plus the corresponding human-authored question). The presentation order of the
questions for a given paragraph was randomized. Participants rated the fluency
and answerability of questions on a scale of 1-4 based on the following
statements:

1: Question is completely ungrammatical. It’s impossible to know what this
question is asking.

2: Question is mostly grammatical, but it doesn’t fully make sense. It’s not
clear what this question is asking.

3: Question is strangely worded, vague, or contains errors. However, I can
make a guess about what the question is asking.

4: Question is clearly worded. I understand what this question is asking.

If the participant indicated that the question was answerable by rating it a 3
or 4, they were then asked if the answer to the question was contained in the
paragraph. If they indicated ‘yes’, they were asked to verify this by
selecting all text spans in the paragraph that qualified as correct answers to
the question. Based on this, we scored a question as having an ‘answer
present’ if it was marked as being answerable and if at least one of the
participant-selected answer spans was the same one the question was
conditioned upon when generated (signifying that the question actually
elicited the answer the model observed in the input). 41 participants assessed
a total of 1,560 paragraph-question items, with each item being rated by at
least two participants (see Appendix A.3 for inter-rater reliability
statistics). We averaged the scores for the same questions across
participants. Table 4 shows the mean ratings and answer presence for each set
of generated questions including the Human questions. In terms of ratings, the
results follow the same pattern as the automated evaluation: the RuleMimic
questions are rated higher than the Standard questions, and the Augmented
questions are rated higher than the RuleMimic questions. All sets of generated
questions are rated much lower than the Human questions. The models are
ordered the same in terms of answer presence, though the difference between
the RuleMimic and Augmented models is slight. Overall these results again show
the benefit of augmenting the training data with automatically generated
questions. Accordingly, our demo currently runs the Augmented model.

##  4 Generating Q&A Pairs

We combined our best-performing QG and QA models into a system that takes a
text as input and returns a list of Q&A pairs. Our web demo illustrates this
system (see Appendix A.4 for details).

For our evaluations in Section 3, the QG models observed annotated answer
spans upon which the generated questions were conditioned. However, these
annotations are obviously not available by default for any arbitrary text.
Consequently, after splitting the text into sentences, we automatically
identify syntactic chunks and named entities as candidate answers to questions
(see Appendix A.5 for details). For each candidate answer in a sentence, we
produce an input consisting of that sentence annotated with that span. We also
include sentences with no answer annotations as inputs, since they are not
formally required by the model. We provide all inputs for a given sentence to
the Augmented QG model to get a list of questions that can be passed to the QA
component. Note that even though some of the questions are already associated
with annotated answers, we still apply QA as an additional means of verifying
their answerability, and defer to the QA-predicted answer. To prepare the QA
inputs, for each sentence-question item, we extend the sentence to include the
sentences immediately preceding and following it, so each question becomes
aligned with a 3-sentence passage. This enables the QA system to possibly
retrieve additional context beyond the sentence that it may deem as part of
the answer span. We provide these passage-question pairs to the BERT Shared-
Norm MegaQA model, then retain output items for which answers are found. We
reduce the redundancy of items by filtering those with duplicate questions or
answers, as well as items where the question and answer concatenated share 60%
or more of the same tokens. In these cases, we only retain the item with the
highest QG probability.

###  4.1 Human Evaluation

Figure 1: Human accuracy on target questions before and after observing
generated Q&A pairs

We used our system to generate Q&A pairs for ten texts from the SQuAD test
set. Appendix Table 6 shows an example of a generated Q&A list for one text.
We conducted an evaluation of the informativeness of these pairs with 38 AMT
participants. In the first stage of the evaluation, participants were shown
only the title of one text (e.g. “Tesla”) and the human-authored SQuAD
questions (no answers) corresponding to the text. Without referencing any
material, they were asked to answer these target questions or respond with “X”
for questions they couldn’t answer. Because no generated Q&A pairs were shown
to participants during this stage, the accuracy of their answers indicated
their prior mental knowledge of the information in the text. In the second
stage, the generated Q&A pairs for the same text were revealed to them and
they answered the same target questions again. Participants never observed the
original text itself. The logic of this design is that the more questions
people could correctly answer in the second stage relative to the first, the
more informative the generated Q&A list could be deemed. The ratio of
generated Q&A pairs to target questions per text varied from 1 to 2.4 (e.g.
ratio = 2 for a text with 30 generated pairs and 15 target questions). Figure
1 shows the percentage of target questions participants answered correctly
before and after observing the Q&A list, grouped by ratio. The overall
difference in these conditions (14.74% vs. 50.26%) shows that the generated
items were partially informative for answering the target questions,
signifying that the system does highlight some of the same content people ask
questions about. However, accuracy did not markedly improve as participants
saw more items (50.18% for the lower ratio vs. 50.38% for the higher ratio),
suggesting that the information coverage of the items could be improved. See
Appendix A.6 for more details about this evaluation.

##  5 Conclusion and Future Work

In this paper, we present a system that automatically produces Q&A pairs for
multi-paragraph documents. We report some novel experiments for QA and QG that
motivate techniques for improving these tasks. We show that combining these
components can produce informative Q&A items. Our future work will focus on
more advanced modeling of information structure in documents. For example, the
ideal design of Q&A items varies by domain (e.g. news stories vs. financial
reports vs. opinion editorials), and items should target the content readers
find most substantial in each domain.

## References

  * Chen et al. (2017) Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. 2017.  Reading Wikipedia to answer open-domain questions.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1870–1879, Vancouver, Canada. Association for Computational Linguistics.
  * Clark and Gardner (2018) Christopher Clark and Matt Gardner. 2018.  Simple and effective multi-paragraph reading comprehension.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 845–855, Melbourne, Australia. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Du et al. (2017) Xinya Du, Junru Shao, and Claire Cardie. 2017.  Learning to ask: Neural question generation for reading comprehension.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1342–1352, Vancouver, Canada. Association for Computational Linguistics.
  * Duan et al. (2017) Nan Duan, Duyu Tang, Peng Chen, and Ming Zhou. 2017.  Question generation for question answering.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 866–874, Copenhagen, Denmark. Association for Computational Linguistics.
  * Heilman and Smith (2010) Michael Heilman and Noah A. Smith. 2010.  Good question! statistical ranking for question generation.  In _Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics_ , pages 609–617, Los Angeles, California. Association for Computational Linguistics.
  * Hu et al. (2019) Minghao Hu, Yuxing Peng, Zhen Huang, and Dongsheng Li. 2019.  Retrieve, read, rerank: Towards end-to-end multi-document reading comprehension.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 2285–2295, Florence, Italy. Association for Computational Linguistics.
  * Kaisser (2008) Michael Kaisser. 2008.  The QuALiM question answering demo: Supplementing answers with paragraphs drawn from Wikipedia.  In _Proceedings of the ACL-08: HLT Demo Session_ , pages 32–35, Columbus, Ohio. Association for Computational Linguistics.
  * Klein et al. (2017) Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander M. Rush. 2017\.  OpenNMT: Open-source toolkit for neural machine translation.  In _Proc. ACL_.
  * Knight (2010) Chris Knight. 2010.  Question & answer article template.
  * Krishna and Iyyer (2019) Kalpesh Krishna and Mohit Iyyer. 2019.  Generating question-answer hierarchies.  In _Association for Computational Linguistics_.
  * Kumar et al. (2019) Vishwajeet Kumar, Sivaanandh Muneeswaran, Ganesh Ramakrishnan, and Yuan-Fang Li. 2019.  Paraqg: A system for generating questions and answers from paragraphs.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP): System Demonstrations_ , pages 175–180.
  * Nema and Khapra (2018) Preksha Nema and Mitesh M Khapra. 2018.  Towards a better metric for evaluating question generation systems.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3950–3959.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  SQuAD: 100,000+ questions for machine comprehension of text.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 2383–2392, Austin, Texas. Association for Computational Linguistics.
  * Raphael (1982) Taffy E Raphael. 1982.  Improving question-answering performance through instruction.  _Reading education report; no. 32_.
  * Robertson et al. (2009) Stephen Robertson, Hugo Zaragoza, et al. 2009.  The probabilistic relevance framework: Bm25 and beyond.  _Foundations and Trends® in Information Retrieval_ , 3(4):333–389.
  * Sachan and Xing (2018) Mrinmaya Sachan and Eric Xing. 2018.  Self-training for jointly learning to ask and answer questions.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 629–640, New Orleans, Louisiana. Association for Computational Linguistics.
  * Scialom et al. (2019) Thomas Scialom, Benjamin Piwowarski, and Jacopo Staiano. 2019.  Self-attention architectures for answer-agnostic neural question generation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 6027–6032.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725.
  * Seo et al. (2017) Min Joon Seo, Aniruddha Kembhavi, Ali Farhadi, and Hannaneh Hajishirzi. 2017.  Bidirectional attention flow for machine comprehension.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_.
  * Song et al. (2018) Linfeng Song, Zhiguo Wang, Wael Hamza, Yue Zhang, and Daniel Gildea. 2018.  Leveraging context information for natural question generation.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 569–574, New Orleans, Louisiana. Association for Computational Linguistics.
  * Talmor and Berant (2019) Alon Talmor and Jonathan Berant. 2019.  MultiQA: An empirical investigation of generalization and transfer in reading comprehension.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4911–4921, Florence, Italy. Association for Computational Linguistics.
  * Tang et al. (2018) Duyu Tang, Nan Duan, Zhao Yan, Zhirui Zhang, Yibo Sun, Shujie Liu, Yuanhua Lv, and Ming Zhou. 2018.  Learning to collaborate for question answering and asking.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1564–1574, New Orleans, Louisiana. Association for Computational Linguistics.
  * Trischler et al. (2017) Adam Trischler, Tong Wang, Xingdi Yuan, Justin Harris, Alessandro Sordoni, Philip Bachman, and Kaheer Suleman. 2017.  NewsQA: A machine comprehension dataset.  In _Proceedings of the 2nd Workshop on Representation Learning for NLP_ , pages 191–200, Vancouver, Canada. Association for Computational Linguistics.
  * Wang et al. (2018) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. 2018.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 353–355, Brussels, Belgium. Association for Computational Linguistics.
  * Wang et al. (2019) Zhiguo Wang, Patrick Ng, Xiaofei Ma, Ramesh Nallapati, and Bing Xiang. 2019.  Multi-passage bert: A globally normalized bert model for open-domain question answering.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 5881–5885.
  * Yang et al. (2019) Wei Yang, Yuqing Xie, Aileen Lin, Xingyu Li, Luchen Tan, Kun Xiong, Ming Li, and Jimmy Lin. 2019.  End-to-end open-domain question answering with BERTserini.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations)_ , pages 72–77, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Yuan et al. (2017) Xingdi Yuan, Tong Wang, Caglar Gulcehre, Alessandro Sordoni, Philip Bachman, Saizheng Zhang, Sandeep Subramanian, and Adam Trischler. 2017.  Machine comprehension by text-to-text neural question generation.  In _Proceedings of the 2nd Workshop on Representation Learning for NLP_ , pages 15–25, Vancouver, Canada. Association for Computational Linguistics.
  * Zhang and Bansal (2019) Shiyue Zhang and Mohit Bansal. 2019.  Addressing semantic drift in question generation for semi-supervised question answering.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 2495–2509.
  * Zhao et al. (2018) Yao Zhao, Xiaochuan Ni, Yuanyuan Ding, and Qifa Ke. 2018.  Paragraph-level neural question generation with maxout pointer and gated self-attention networks.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3901–3910, Brussels, Belgium. Association for Computational Linguistics.

##  Appendix A Appendices

###  A.1 QA Model Details

The TF-IDF method for ranking paragraph relevance to the question specifically
uses the BM-25 ranker333pypi.org/project/rank-bm25 Robertson et al. (2009). We
implemented the QA model in PyTorch using the HuggingFace Transformers
library444huggingface.co/transformers. As described in Section 2.1, we use the
pre-trained BERT-Base-Uncased model, which has 12 layers, 768 nodes per layer,
12 heads per layer, and 110M parameters overall. The maximum sequence length
for BERT-Base-Uncased is 384 tokens (including both paragraph and question
tokens combined), so we truncated paragraphs when this total was exceeded. The
output layer consists of a 384 x 2 matrix whose dimensions correspond to token
indices for the start and end of the answer span. We trained the model in
parallel across 4 Nvidia Tesla V100 GPUs with a paragraph-question batch size
of 48 with gradient accumulation at step 1 (12 paragraph-question pairs per
GPU, which was the maximum size a single V100 GPU could accommodate).
Following Devlin et al.’s BERT-based fine-tuning procedure for paragraph-level
QA, the model was trained for 3 epochs and a learning rate of 3e-5 using Adam
optimization.

###  A.2 QG Model Details

We used OpenNMT-py555github.com/OpenNMT/OpenNMT-py Klein et al. (2017) for
implementation of the QG model. For BPE tokenization, we use the OpenAI GPT-2
tokenizer implemented by the HuggingFace transformers library cited above. The
vocabulary included all tokens observed in the training data. The Transformer
encoder and decoder each consist of 4 layers with 2048 nodes and 8 heads each.
We include position encodings on the token embeddings and a copy attention
layer in the decoder. We used a training batch size of 4096 tokens,
normalizing gradients over tokens and computing gradients based on 4 batches.
We trained for a maximum of 100,000 steps and validated every 200 steps, with
early stopping after one round of no improvement in validation loss. We
applied the other hyperparameter settings recommended for training transformer
sequence-to-sequence models on the OpenNMT-py website666opennmt.net/OpenNMT-
py/FAQ.html#how-do-i-use-the-transformer-model. This included Adam
optimization with $\beta_{1}$ = 0.998, gradient re-normalization for norms
exceeding 0, Glorot uniform parameter initialization, 0.1 dropout probability,
noam decay, 8000 warmup steps for decay, learning rate = 2, and label
smoothing $\epsilon$ = 0.

###  A.3 QG Evaluation Details

The sentence inputs for the evaluated questions were randomly sampled after
filtering for those inside paragraphs longer than 500 characters, to ensure
participants could efficiently complete the evaluation. AMT workers were paid
$7 for their participation in this evaluation, with the expected time
commitment of about 35 minutes.

The Cohen’s kappa inter-rater agreement on the fluency/answerability ratings
of 1-4 was 0.422, indicating moderate agreement. The kappa for answer presence
in the paragraph was 0.465, also indicating moderate agreement.

###  A.4 System Implementation Details

The system UI is implemented using React JS with Bootstrap CSS for styling.
Figure 2 shows a screenshot of the interface. The QA and QG functionalities
run as web services implemented using Flask.

As an additional feature of the UI, users have the option to obtain answers to
their own custom questions. They supply the question via a text box. The QA
system receives the entire document text as input along with the question. We
enforce paragraph boundaries by splitting the document into non-overlapping
paragraphs of 300 tokens, and then apply the BERT Shared-Norm MegaQA model
with top k=4 for paragraph retrieval777Section 2.3.1 reported the result for
k=15, but k=4 performs only slightly lower (71.21 EM and 78.89 F1 vs. 72.85
and 80.58, respectively) with significantly higher efficiency.. If the model
predicts the answer is not in the text, the user sees a message indicating
this.

###  A.5 Candidate Answers for QG

We use the spaCy888spacy.io library to extract all named entities and noun
chunks. Additionally, we extract all dependency parse subtrees whose head is
labeled as one of the following: clausal complement (xcomp), attribute (attr),
prepositional modified (prep), object (obj), indirect object (iobj), flat
multiword expression (flat), fixed multiword expression (fixed), clausal
subject (csubj), clausal complement (ccomp), adjectival clause (acl), and
conjunct (conj). All extracted chunks are annotated as answer spans.

###  A.6 Q&A List Evaluation

We truncated each of the ten SQuAD documents to its first three paragraphs.
There were on average 334.5 tokens per truncated document. For each document
we selected all SQuAD questions corresponding to the first three paragraphs as
the list of target questions participants were prompted to answer. There were
on average 16.2 target questions per truncated document. We provided the
truncated document to the system to generate a list of Q&A items. As described
in Section 4.1, the ratio of generated Q&A items per target questions varied
from 1 to 2.4 with an average of 1.66, resulting in an overall average of 26.3
generated items per document.

Each of the 38 AMT participants answered the target questions for a single
document, so approximately four participants answered each unique list of
target questions. They were paid $8 for their participation, with the expected
time commitment of around 30 minutes. The instructions emphasized that they
should not use any external information to answer the questions other than the
reference Q&A list (which was only used when participants answered the
questions for the second time). They were told their participation would not
be judged based on the number of questions correctly answered. Participants
were not informed that the reference Q&A items were automatically generated.

Because all answers were provided as free text and there could be some token
variation in correct answers for the same question (e.g. “Parliament of the
United Kingdom” vs. “UK Parliament”), we used a fuzzy metric for judging
answers as correct. We counted a participant answer as correct if it had at
least one token in common with the answer given in the SQuAD dataset. This is
a permissive threshold that can yield false positives (e.g. “300 years” vs.
“500 years”), but because it was consistently applied across both stages of
the evaluation (i.e. before and after observing the Q&A list), we deemed it
sufficient for quantifying the relative impact of the generated items in the
‘after’ condition.

Figure 2: Screenshot of UI with generated Q&A pairs for the displayed document Input Sentence | Model |  Output Question
---|---|---
By far the most famous work of Norman art is the $<$ANSWER$>$ Bayeux Tapestry $<$/ANSWER$>$, which is not a tapestry but a work of embroidery. | Standard |  What is the name of the work of Norman art?
RuleMimic |  What is not a tapestry but a work of embroidery?
Augmented |  What is the most famous work of Norman art?
Human |  What is Norman art’s most well known piece?
Later in life, Tesla made claims concerning a ”teleforce” weapon after studying the $<$ANSWER$>$ Van de Graaff generator $<$/ANSWER$>$. | Standard |  What was the name of the weapon that studying the Teslaforce?
RuleMimic |  What did Tesla make claims concerning a ”teleforce” weapon after studying?
Augmented |  What did Tesla study?
Human |  What was he studying that gave him the teleforce weapon idea?
The Super Bowl 50 Host Committee has vowed to be “the most giving Super Bowl ever”, and will dedicate $<$ANSWER$>$ 25 percent $<$/ANSWER$>$ of all money it raises for philanthropic causes in the Bay Area. | Standard |  How much of the Super Bowl raises?
RuleMimic |  What will the Super Bowl 50 Host Committee dedicate it raises for philanthropic causes in the Bay Area?
Augmented |  What is the Super Bowl 50 Host Committee?
Human |  How many will the host committee dedicate to local charities?
In 1899, John Jacob Astor IV invested $100,000 for Tesla to further $<$ANSWER$>$ develop and produce a new lighting system $<$/ANSWER$>$. | Standard |  What did Jacob Astor IV do?
RuleMimic |  What did John Jacob Astor IV invest $100,000 for in 1899?
Augmented |  Why did Jacob Astor IV invest $100,000?
Human |  What did Astor expect the money be used for?
Most influential among these was the definition of Turing machines by Alan Turing in $<$ANSWER$>$ 1936 $<$/ANSWER$>$, which turned out to be a very robust and flexible simplification of a computer. | Standard |  When was the definition of the definition of Turing?
RuleMimic |  When turned out to be a very robust and flexible simplification of a computer?
Augmented |  When did Alan Turing write machines?
Human |  In what year was the Alan Turing’s definitional model of a computing device received?
In addition to the $<$ANSWER$>$ Vince Lombardi $<$/ANSWER$>$ Trophy that all Super Bowl champions receive, the winner of Super Bowl 50 will also receive a large, 18-karat gold-plated “50”. | Standard |  What is the name of the Super Bowl?
RuleMimic |  Who will the winner of Super Bowl 50 also receive a large in addition to the Vince Lombardi Trophy that all Super Bowl champions receive?
Augmented |  Who wrote the Super Bowl 50?
Human |  Who is the trophy given to the Super Bowl champion named for?
In 1874, Tesla evaded being drafted into the Austro-Hungarian Army in Smiljan by running away to $<$ANSWER$>$ Tomingaj $<$/ANSWER$>$, near Gračac. | Standard |  What was the name of Tesla’s Army in 1874?
RuleMimic |  Who was near Gračac?
Augmented |  Where did Tesla travel to?
Human |  Where did Tesla run to avoid the army draft?
Table 5: Examples of questions produced by each evaluated QG model for the
given input sentences Q: What is separate from the combustion products?
A: working fluid |  Q: Where was the water supply for driving waterels?
A: factories
---|---
Q: What is solar power?
A: Non-combustion heat sources |  Q: What did the mine provide?
A: water supply
Q: What is the ideal thermodynamic cycle used for?
A: to analyze this process |  Q: Where was it employed?
A: draining mine workings
Q: What is heated and transforms into steam?
A: water |  Q: Where was the storage reservoir?
A: above the wheel
Q: Why is mechanical work done?
A: When expanded through pistons or turbines |  Q: What was passed over the wheel?
A: Water
Q: What is then condensed and pumped back into the boiler?
A: reduced-pressure steam |  Q: When was the first railway journey?
A: 21 February 1804
Q: Who invented the first commercially true engine?
A: Thomas Newcomen |  Q: Where was the train?
A: along the tramway from the Pen-y-darren ironworks, near Merthyr Tydfil to
Abercynon in south Wales
Q: What could generate power?
A: atmospheric engine |  Q: What was built by Richard Trevithick?
A: The first full-scale working railway steam locomotive
Q: Who proposed the piston pump?
A: Papin |  Q: The design incorporated a number of what?
A: important innovations that included using high-pressure steam which reduced
the weight of the engine and increased its efficiency
Q: What happened to Newcomen’s engine?
A: relatively inefficient |  Q: What did England become the leading centre for?
A: experimentation and development of steam locomotives
Q: What was the engine used for?
A: pumping water |  Q: Where was the railways colliery?
A: north-east England
Q: What was the vacuum worked by?
A: condensing steam under a piston within a cylinder |  Q: Who visited the Newcastle area in 1804?
A: Trevithick
Q: What was the reason for draining waterelswheels?
A: providing a reusable water supply |
Table 6: Generated Q&A list for the first three paragraphs of the SQuAD
document titled “Steam engine”


# Solving Data-centric Tasks using Large Language Models

Shraddha Barke1, Christian Poelitz2, Carina Suzana Negreanu2, Benjamin Zorn2,
José Cambronero2,
Andrew D. Gordon2, Vu Le2, Elnaz Nouri2, Nadia Polikarpova1, Advait Sarkar2,
Brian Slininger2, Neil Toronto2,
Jack Williams2 1{sbarke<EMAIL_ADDRESS>
2{cpoelitz, cnegreanu, Ben.Zorn, jcambronero, adg, levu, Elnaz.Nouri, advait,
brslinin, neil.toronto<EMAIL_ADDRESS>
###### Abstract

Large language models (LLMs) are rapidly replacing help forums like
StackOverflow, and are especially helpful for non-professional programmers and
end users. These users are often interested in _data-centric tasks_ , such as
spreadsheet manipulation and data wrangling, which are hard to solve if the
intent is only communicated using a natural-language description, without
including the data. But how do we decide how much data and which data to
include in the prompt?

This paper makes two contributions towards answering this question. First, we
create a dataset of real-world NL-to-code tasks manipulating tabular data,
mined from StackOverflow posts. Second, we introduce a _cluster-then-select_
prompting technique, which adds the most representative rows from the input
data to the LLM prompt. Our experiments show that LLM performance is indeed
sensitive to the amount of data passed in the prompt, and that for tasks with
a lot of syntactic variation in the input table, our cluster-then-select
technique outperforms a random selection baseline.

Solving Data-centric Tasks using Large Language Models

Shraddha Barke1, Christian Poelitz2, Carina Suzana Negreanu2, Benjamin Zorn2,
José Cambronero2, Andrew D. Gordon2, Vu Le2, Elnaz Nouri2, Nadia Polikarpova1,
Advait Sarkar2, Brian Slininger2, Neil Toronto2, Jack Williams2 1{sbarke,
<EMAIL_ADDRESS>2{cpoelitz, cnegreanu, Ben.Zorn, jcambronero, adg,
levu, Elnaz.Nouri, advait, brslinin, neil.toronto,
<EMAIL_ADDRESS>

##  1 Introduction

Code-generating large language models (LLMs) promise to empower end users
interested in _data-centric tasks_ , ranging from string manipulations in
spreadsheets to data cleaning and analysis in computational notebooks. For
example, consider the following task on tabular data: given a column with
_full names_ , generate a new column with _user names_ , by combining the
first initial and last name, in lowercase. This task can be solved by a Pandas
program that: 1) splits the full name into a list of strings, 2) extracts the
first and last string from the list, 3) converts both to lowercase and joins
the first letter of one string to the other. The challenge in generating this
program is that data rows often have varied formats, _e.g._ most rows only
have two names ("John Smith"), but some have multiple middle names ("Jake L
Woodhall", "Jo Anna Emily Gray"). If an LLM prompt does not include any data
or only includes rows with two names, the LLM is more likely to generate a
program that does not generalize (_e.g._ one that extracts the last name as
the _second_ element of the list instead of _last_).

In this paper, we focus on solving such tasks that involve multi-step
computations on the input columns to generate additional columns. Towards this
goal, we mine StackOverflow to construct a new dataset, dubbed SofSet, of
data-centric tasks, equipped with a natural-language query and a small input
table. Using this dataset, we conduct experiments on generating Pandas
programs using GPT-4 and an open-source alternative CodeLlama, with the goal
of analysizing LLMs’ sensitivity to the amount of input data provided in the
prompt.

Unlike input tables in StackOverflow posts, real-world data tables are often
large, hence sending the entire table to the LLM is likely impractical,
expensive, or detrimental to performance. _How do we best convey the structure
of a large input table to the LLM?_ To address this question, we propose a
_cluster-then-select_ prompting technique that clusters input rows based on
their syntactic structure and then selects representative rows from each
cluster; _e.g._ in our “user name” example, the technique would include a row
for each number of middle names. To evaluate this technique, we perform
experiments on SofSet augmented with larger input tables extracted from
Kaggle.

In summary, this paper contributes:

  * •

a real-world dataset of complex tasks for evaluating data-centric code
generation;

  * •

a _cluster-then-select_ technique for selecting rows to prompt with, from
large input tables;

  * •

an analysis that shows LLMs are sensitive to the data quantity, choice and
position of rows.

##  2 Related work

Large language models for tabular data Code-generating LLMs like Codex Chen et
al. (2021) and PaLM Chowdhery et al. (2022) have been fine-tuned for code-
specific tasks and adapted for data-centric domains like SQL Trummer (2022);
Rajkumar et al. (2022). Li et al. (2020) investigate the ability of language
models like BERT to perform entity matching on tabular data. Narayan et al.
(2022) use GPT-3 for data cleaning, error detection and entity matching tasks.
Hegselmann et al. (2023) focus on tabular classification tasks and investigate
parameter-efficient tuning of LLMs.

Prompting for data-centric tasks In this paper, we ask the question: how does
data context impact code generation for data-centric tasks? Previous works
have explored prompting with data: Jain et al. (2022) provide both input and
expected output tables (which might not be available in a realistic setting).
Gemmell and Dalton (2023) prompt with transformed tables after filtering out
rows that are not relevant for their question-answering tasks. Hegselmann et
al. (2023) serialize data tables into a textual representation for tabular
classification tasks. Yin et al. (2022) focuses on data-centric tasks in
computational notebooks. These works focus on prompting for data analysis,
classification and wrangling tasks (in-place data transformations) whereas we
focus on multi-step data manipulation. We propose a new _cluster-then-select_
prompting technique that clusters the input data and adds representative rows
to the prompt.

##  3 The SofSet Dataset

We collect a new dataset fashioned from real-world data-centric tasks from
StackOverflow (SofSet). We sample tasks deterministically from the highest
rated posts with the tag "ExcelFormulas" in StackOverflow (as of March 2022).
These tasks are representative of real problems spreadsheet users face
frequently since they correspond to the highest-rated posts. We manually check
that the posts are genuine tasks and also remove post identifiers for
anonymization. This gives us a total of 201 tasks.

###  3.1 Dataset Annotation

Each datapoint in our dataset is annotated with a concise textual query, a
data input (column-major-flat table), an expected correct output (extra
columns), a pandas solution and metadata. We manually write the textual
queries, summarising the original verbose StackOverflow question. Each query
is annotated and verified by at least 3 internal annotators. For the data
input, we use the table from the original StackOverflow post (if available),
and add extra rows and corner cases until we have at least 10 rows. As the NL
query and tabular data are not verbatim copies from StackOverflow and we have
a different target language (Pandas instead of Excel Formulas), the evaluation
data should not be present in the training data. We choose Pandas as the
target language since LLMs are especially good at generating Python but our
methods and dataset are programming-language agnostic.

###  3.2 Dataset Properties

_What makes our dataset different from existing ones?_ First, our dataset
consists of complex data-centric tasks with several input columns. Prior
python datasets like Hendrycks et al. (2021); Chen et al. (2021) are not data-
centric. Second, our dataset is larger than existing data-centric datasets,
Jigsaw Jain et al. (2022) and CERT Zan et al. (2022). Jigsaw has 79 unique
tasks (median of 7 data rows) and CERT has 100 unique tasks (median of 3
rows). Our dataset has 201 unique tasks, with a median of 10 rows. The Spider
dataset Yu et al. (2018) is a text-to-SQL dataset which focuses on relational
query tasks whereas we focus on fine-grained data wrangling and manipulation
tasks. Finally, we propose a _taxonomy_ of data-centric tasks, classifying
them into data-independent (ind), data-dependent (dep), and external-dependent
(ext), based on the data required to produce a solution.

Data-independent tasks These tasks can be solved using the query alone without
any data access. An example is the query "create a new column that includes
only the first 5 characters from Filename".

Data-dependent tasks These tasks cannot be solved using the query alone: the
model needs access to the input table. For example, the query "create a new
column with the number of days between the two date columns" requires data
access to identify the correct column names and date format, both absent from
the query.

External-dependent tasks These tasks can only be solved with external world
knowledge in addition to data access. The query "create a new column that
counts how many US holidays are between the dates in Start Date and End Date",
requires the model to know about US holidays.

Following this taxonomy, SofSet consists of 126 ind tasks, 44 dep tasks and 31
ext tasks. These tasks span diverse domains including string manipulation,
date and time, math, address, and complex conditionals among others.

###  3.3 Cluster-then-select prompting technique

To solve tasks on large tables, we propose a _cluster-then-select_ technique
which prompts the model with a representative sample of the input data. In
order to capture the syntactic variation in the input data, we rely on an
existing tool Padhi et al. (2018), which takes as input a set of strings and
synthesizes a small set of regular expressions (regexes), such that each input
string matches one of the regexes. In our “user name” example from the
introduction, it would synthesize separate regexes for rows with zero, one,
and two middle names. These regexes are then used to cluster the input
strings, and we select some number of rows from each cluster.

If the input table only has one column, selecting $n$ representative rows
based on the clustering results is trivial: simply pick one row each from the
top-$n$ most populous clusters. In cases where the input contains more than
one column, they may be clustered differently. We then select $n$ rows that
together cover as many strings as possible across all the columns. We frame
this as a _weighted maximal coverage problem_ max , which can be solved
approximately in a greedy manner. In each iteration, the algorithm selects the
rows whose elements maximize cluster coverage.

Kaggle-augmented dataset In order to evaluate our _cluster-then-select_
technique on larger datasets, we expand the 44 data-dependent tasks by adding
more rows from open-source Kaggle datasets kag , bringing the total to 1000.
We first identify the specific data domains in the original SofSet rows (such
as names, numbers, address, date, time etc) and then source comparable open-
source datasets from Kaggle of the same domain. We then post-process the
Kaggle data to maintain the original rows format, while also introducing
greater variation which increases the number of data clusters. 62% of our dep
tasks have at least 2 clusters and we have tasks with up to 10 clusters. Since
the Kaggle data is post-processed and is not tied to the task query in any
way, it is unlikely to bias the LLM evaluation by being part of the training
data. This larger dataset allows for a thorough evaluation, better mirroring
real-world conditions.

##  4 Evaluation of data-centric tasks

Figure 1: pass@$k$ with (a) no-data, (b) first-row, and (c) ten-rows passed to
the model. The leftmost group of bars represent pass@k with all classes
followed by separate pass@k for ind, dep and ext tasks.

We perform an analysis of the role of data on model performance in data-
centric tasks. We first use the original SofSet dataset to examine three data
regimes with increasing amounts of data: (a) no-data (b) first-row and (c)
ten-rows and the taxonomy of task classes of increasing difficulty in terms of
data required: ind, dep and ext. We then use Kaggle-augmented dep tasks to
compare our _cluster-then-select_ technique (which selects representative rows
from the top-n most dense clusters) against a random baseline (which selects
random rows from the input). For each data setting, we construct a prompt
which contains the task query and selected rows as a pandas dataframe to
generate code using GPT-4. Correctness is reported based on whether the code
produces the expected output in terms of pass@$k$, the probability that at
least one of k samples of generated code produces the correct output Chen et
al. (2021).

Does model performance vary with the amount of data passed for different task
classes? Figure 1 shows the impact of the amount of data on LLM performance,
first for the entire dataset and then split by task classes. We see a larger
drop in performance with reduced (and no) data on dep (and ext) tasks compared
to ind tasks. Specifically, the performance gap (pass@5) between first-row and
no-data regimes is larger for the dep and ext classes (33.8% and 83.5% resp)
compared to only 7.1% for ind tasks. The fact that there is any performance
drop for ind tasks indicates that having data helps the model even when the
problem can be solved independently of data. In the absence of data, almost no
ext task is solved (pass@1) but performance improves when a single row is
passed.

Is our cluster-then-select technique effective on larger input tables?

Figure 2: pass@$k$ for 39% (17 out of 44) dep tasks (with more than two
clusters) with no-data, random selection (random-n), representative selection
(represent-n) and pass@1 with greedy sampling for full-data (1000 rows).
Completions are evaluated on 1000 rows.

We evaluate our _cluster-then-select_ technique on Kaggle-augmented dep tasks
(with 1000 rows) since we expect to see the benefit of our approach more
clearly on tasks dependent on data. In order to do so, we compare our
representative selection strategy against _random_ selection where the rows
are randomly selected from the input table. Among dep tasks, we further only
focus on 17 (out of 44) that have input columns with at least three clusters,
since with two clusters or fewer we don’t expect to see much difference
between the representative and random samples. We also evaluate against two
baselines: no-data (0 rows) and full-data (all 1000 rows). We run random
selection experiments five times.

Figure 3 shows that the model performs best with 10 most representative rows
added to the prompt (pass@5 for represent-10 = 0.32). Representative selection
performs slightly better than random for the same number of rows.
Specifically, represent-1 and represent-10 outperform random-1 and random-10
by 8% and 6% resp. In addition, random selection has _high variance_ ,
especially for a small number of rows (_e.g._ pass@$1$ for random-1 varies
from 0.20 to 0.31 across the five runs), which is not surprising, since the
random strategy might select rows from different clusters or from the same
one. Thus, while random selection gives comparable results on average, our
cluster-then-select technique offers a more consistent approach to provide the
model a representative sample of the data. Further, the low pass@k for our no-
data baseline suggests that our dataset was not part of the training data, as
then the model would likely perform well even without data input. We note that
while we evaluate on 1000 rows, the same cluster-then-select technique could
easily scale to datasets with over 100K rows without much overhead.

Does the position of data rows in the prompt also affect performance? For the
full-data baseline, we used a longer-context version of GPT-4 (32k) with
temperature 0 (_greedy selection to eliminate variance in the generations_)
for the same 17 dep tasks. The right side of Figure 2 shows pass@$1$ for this
setting with ten runs: we permute the 1000 rows in the dataframe ten times, in
order to measure the sensitivity of the model to row positioning. We observe a
high variance in pass@$1$ values, ranging from 0.20 to 0.32 with an average of
0.26. This shows that the position of rows in the dataframe influences
completions quality, which aligns with previous findings about positional
biases in prompts Liu et al. (2023). Surprisingly, the full-data setting
(irrespective of row ordering) performs worse than selecting one random row in
some cases (pass@$1$ for one random row ranges from 0.12 to 0.27 with an
average of 0.20). 111Experiments with all dep tasks on GPT-4 are in Figure 3
and CodeLlama experiments are Figure 6, Figure 7, Figure 8.

##  5 Conclusion and Future Work

Our work highlights the importance of data for code generation on data-centric
tasks and proposes a new dataset for evaluation of data-centric tasks. We show
that providing even one data row to the model boosts performance compared to a
no-data baseline. Since providing the entire input data is often infeasible,
we propose a _cluster-then-select_ prompting technique that selects
representative rows from the data to be added to the prompt. While randomly
selecting rows also performs well, for data with a high degree of syntactic
variation, it is more beneficial to add representative rows to the prompt. For
future work, handling a broader problem space (_e.g._ , multi-table inputs,
hierarchical table inputs) raises interesting challenges.

##  6 Limitations

We discuss the limitations of our work in terms of the SofSet dataset, the
cluster-then-select prompting technique and the models used for evaluation.
Although starting from actual user-specified problems gives our results
greater alignment with real spreadsheet user problems, the form that such
queries take pose some potential limitations to our analysis. Users usually
only show relevant columns of data in their queries when in actuality there
might be many more unrelated columns in real spreadsheets. We have seen good
results applying LLMs to spreadsheets with many columns that are extraneous to
the query but we do not perform a rigorous evaluation of the same.
Furthermore, since we have collected only English queries from StackOverflow,
our results may not generalize to other languages.

Since we draw our conclusions from the generations produced by the GPT-4
model, future models might invalidate our conclusions. Furthermore access to
models such as GPT-4 cannot be taken for granted and the costs of running our
evaluation are considerable. Even open source models like CodeLlama require
available GPU resources to evaluate.

Finally, our cluster-then-select prompting technique is based on the regular
expression synthesis algorithm from Padhi et al. (2018). Given that the
clusters for the input data columns are defined by the specificity of this
regex synthesis, using a different synthesis algorithm could potentially
result in a different set of clusters.

##  7 Broader Research Impact

To the best of our knowledge, research on prompting large language models to
solve data-centric tasks with tabular data is infrequent, despite the
considerable importance of such scenarios. Solving the problem of how to help
LLM reason over large amounts of data is essential to the future of assisted
decision making. Generating multi-step programs that require reasoning is the
beginning of this journey and to make progress the community needs challenging
real-world datasets to evaluate on. By releasing our new dataset, sharing the
analysis results of our experiments and releasing our prototype
tool222discussed in Appendix C, we offer valuable benchmarks and a baseline to
the wider research community which promises to encourage further exploration.

##  8 Ethics Statement

There are broad ethical impacts resulting from the creation of AI models that
attempt to generate code solutions from natural language descriptions and
these are discussed in detail in previous papers including Codex Chen et al.
(2021), AlphaCode Li et al. (2022), and PaLM Chowdhery et al. (2022). These
impacts include over-reliance, misalignment between what the user expressed
and what they intended, potential for bias and under/over representation in
the model results, economic impacts, the potential for privacy and security
risks, and even environmental considerations. All of these considerations also
apply to the work described here. Our focus is to highlight how the presence
of data improves the performance of these models but it is important to note
that the quality of the data used in the prompt will impact whether the
resulting generation exhibits bias, exposes private data, etc. We explore the
overall impact of providing data as part of the prompt but do not conduct a
more focused analysis of determining how bias in the prompt data might
influence the resulting code generation, a task we leave for future work.

There is the question of the sources of data and of consent to use the data in
the manner exhibited in this paper. We have reviewed each of the datasets we
have included in this paper to ensure that our use is compatible with the
intent of the authors and publishers. Our datasets have also been reviewed by
our institution’s ethics board to review that this is an ethical use.

We are wary of using the word "understand" in this paper. It has been
correctly argued that language models do not really "understand" language in
the sense of connecting language’s syntactic content with the semantics of the
physical world Bender and Koller (2020); Webson and Pavlick (2022). There have
long been critics of the use of such terms in AI research Agre et al. (1997).
Nonetheless, large language models have shown themselves in certain situations
to be capable of the syntactic manipulation of language which in humans we
take to be commonsense evidence of understanding. This is the less contentious
manner in which we use the word. Thus our intention in using the word is not
to claim that models can connect data with real-world concepts, but rather
that the model can manipulate language about data in a useful manner, where
"useful" is defined by our quantitative benchmarks.

This paper does not directly contribute to a tool built on the assumed
capabilities of language models to understand data, but nonetheless, it is
motivated by their potential applications in such tools. These tools may be
deployed in many data applications such as databases, spreadsheets, and
business intelligence applications. Depending on the audience of the tool,
various interaction design concerns arise. Explainability of the model is a
key consideration, and the tool should offer decision support to evaluate
mispredictions and potential next steps Sarkar (2022). Previous research of
non-experts using inference driven tools for data manipulation has shown the
importance of tool design in the critical appreciation of the model and its
limitations, and in the potential cost of errors Williams et al. (2020);
Sarkar et al. (2015). As an exploratory paper without a concrete application,
we do not encounter these issues, but the project has nonetheless been
reviewed by our institution’s ethics board.

## References

  * (1) Kaggle datasets.
  * (2) Maximum coverage problem.
  * Agre et al. (1997) Philip E Agre et al. 1997.  Lessons learned in trying to reform AI.  _Social science, technical systems, and cooperative work: Beyond the Great Divide_ , 131.
  * Bender and Koller (2020) Emily M Bender and Alexander Koller. 2020.  Climbing towards nlu: On meaning, form, and understanding in the age of data.  In _Proceedings of the 58th annual meeting of the association for computational linguistics_ , pages 5185–5198.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. 2021.  Evaluating large language models trained on code.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek B Rao, Parker Barnes, Yi Tay, Noam M. Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Benton C. Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier García, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Oliveira Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Díaz, Orhan Firat, Michele Catasta, Jason Wei, Kathleen S. Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. 2022.  Palm: Scaling language modeling with pathways.  _ArXiv_ , abs/2204.02311.
  * Droettboom et al. (2022) Michael Droettboom, Roman Yurchak, Hood Chatham, Dexter Chua, Gyeongjae Choi, Marc Abramowitz, casatir, Jan Max Meyer, Jason Stafford, Madhur Tandon, Michael Greminger, Grimmer Kang, Chris Trevino, Wei Ouyang, Joe Marshall, Adam Seering, Nicolas Ollinger, Ondřej Staněk, Sergio, Teon L Brooks, Jay Harris, Alexey Ignatiev, Seungmin Kim, Paul m. p. P., jcaesar, Carol Willing, Cyrille Bogaert, Dorian Pula, Frithjof, and Michael Jurasovic. 2022.  Pyodide: A Python distribution for WebAssembly (0.19.0).
  * Gemmell and Dalton (2023) Carlos Gemmell and Jeffrey Dalton. 2023.  Generate, transform, answer: Question specific tool synthesis for tabular data.  _arXiv preprint arXiv:2303.10138_.
  * Hegselmann et al. (2023) Stefan Hegselmann, Alejandro Buendia, Hunter Lang, Monica Agrawal, Xiaoyi Jiang, and David Sontag. 2023.  Tabllm: Few-shot classification of tabular data with large language models.  In _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_ , volume 206 of _Proceedings of Machine Learning Research_ , pages 5549–5581. PMLR.
  * Hendrycks et al. (2021) Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Xiaodong Song, and Jacob Steinhardt. 2021.  Measuring coding challenge competence with apps.  _ArXiv_ , abs/2105.09938.
  * Jain et al. (2022) Naman Jain, Skanda Vaidyanath, Arun Iyer, Nagarajan Natarajan, Suresh Parthasarathy, Sriram Rajamani, and Rahul Sharma. 2022.  Jigsaw: Large language models meet program synthesis.  In _International Conference on Software Engineering (ICSE)_.
  * Li et al. (2022) Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. 2022.  Competition-level code generation with alphacode.  _arXiv preprint arXiv:2203.07814_.
  * Li et al. (2020) Yuliang Li, Jinfeng Li, Yoshihiko Suhara, AnHai Doan, and Wang-Chiew Tan. 2020.  Deep entity matching with pre-trained language models.  _arXiv preprint arXiv:2004.00584_.
  * Liu et al. (2023) Nelson F. Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. 2023.  Lost in the middle: How language models use long contexts.
  * Narayan et al. (2022) Avanika Narayan, Ines Chami, Laurel Orr, and Christopher Ré. 2022.  Can foundation models wrangle your data?  _arXiv preprint arXiv:2205.09911_.
  * Padhi et al. (2018) Saswat Padhi, Prateek Jain, Daniel Perelman, Oleksandr Polozov, Sumit Gulwani, and Todd Millstein. 2018.  Flashprofile: a framework for synthesizing data profiles.  _Proceedings of the ACM on Programming Languages_ , 2(OOPSLA):1–28.
  * Rajkumar et al. (2022) Nitarshan Rajkumar, Raymond Li, and Dzmitry Bahdanau. 2022.  Evaluating the text-to-sql capabilities of large language models.  _ArXiv_ , abs/2204.00498.
  * Roziere et al. (2023) Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al. 2023.  Code llama: Open foundation models for code.  _arXiv preprint arXiv:2308.12950_.
  * Sarkar (2022) Advait Sarkar. 2022.  Is explainable AI a race against model complexity?  _arXiv preprint arXiv:2205.10119_.
  * Sarkar et al. (2015) Advait Sarkar, Mateja Jamnik, Alan F Blackwell, and Martin Spott. 2015.  Interactive visual machine learning in spreadsheets.  In _2015 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC)_ , pages 159–163. IEEE.
  * Trummer (2022) Immanuel Trummer. 2022.  Codexdb: Generating code for processing sql queries using gpt-3 codex.  _ArXiv_ , abs/2204.08941.
  * Webson and Pavlick (2022) Albert Webson and Ellie Pavlick. 2022.  Do prompt-based models really understand the meaning of their prompts? In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2300–2344, Seattle, United States. Association for Computational Linguistics.
  * Williams et al. (2020) Jack Williams, Carina Negreanu, Andrew D Gordon, and Advait Sarkar. 2020.  Understanding and inferring units in spreadsheets.  In _2020 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC)_ , pages 1–9. IEEE Computer Society.
  * Yin et al. (2022) Pengcheng Yin, Wen-Ding Li, Kefan Xiao, Abhishek Rao, Yeming Wen, Kensen Shi, Joshua Howland, Paige Bailey, Michele Catasta, Henryk Michalewski, et al. 2022\.  Natural language to code generation in interactive data science notebooks.  _arXiv preprint arXiv:2212.09248_.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir R. Radev. 2018.  Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 - November 4, 2018_ , pages 3911–3921. Association for Computational Linguistics.
  * Zan et al. (2022) Daoguang Zan, Bei Chen, Dejian Yang, Zeqi Lin, Minsu Kim, Bei Guan, Yongji Wang, Weizhu Chen, and Jian-Guang Lou. 2022.  Cert: Continual pre-training on sketches for library-oriented code generation.  _ArXiv_ , abs/2206.06888.

Figure 3: pass@$k$ for dep tasks with no-data, and n=1, 5 and 10 rows passed
to the model, using random (random-n), representative selection (represent-n).
The completions are evaluated on 1000 rows.

##  Appendix A Community Data License Agreement - Permissive - Version 2.0

This is the Community Data License Agreement - Permissive, Version 2.0 (the
"agreement"). Data Provider(s) and Data Recipient(s) agree as follows:

###  A.1 Provision of the Data

  * •

A Data Recipient may use, modify, and share the Data made available by Data
Provider(s) under this agreement if that Data Recipient follows the terms of
this agreement.

  * •

This agreement does not impose any restriction on a Data Recipient’s use,
modification, or sharing of any portions of the Data that are in the public
domain or that may be used, modified, or shared under any other legal
exception or limitation.

###  A.2 Conditions for Sharing Data

  * •

A Data Recipient may share Data, with or without modifications, so long as the
Data Recipient makes available the text of this agreement with the shared
Data.

###  A.3 No Restrictions on Results

  * •

This agreement does not impose any restriction or obligations with respect to
the use, modification, or sharing of Results.

###  A.4 No Warranty; Limitation of Liability

  * •

All Data Recipients receive the Data subject to the following terms:

THE DATA IS PROVIDED ON AN "AS IS" BASIS, WITHOUT REPRESENTATIONS, WARRANTIES
OR CONDITIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED INCLUDING, WITHOUT
LIMITATION, ANY WARRANTIES OR CONDITIONS OF TITLE, NON-INFRINGEMENT,
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

NO DATA PROVIDER SHALL HAVE ANY LIABILITY FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING WITHOUT
LIMITATION LOST PROFITS), HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
OTHERWISE) ARISING IN ANY WAY OUT OF THE DATA OR RESULTS, EVEN IF ADVISED OF
THE POSSIBILITY OF SUCH DAMAGES.

###  A.5 Definitions

  * •

"Data" means the material received by a Data Recipient under this agreement.

  * •

"Data Provider" means any person who is the source of Data provided under this
agreement and in reliance on a Data Recipient’s agreement to its terms.

  * •

"Data Recipient" means any person who receives Data directly or indirectly
from a Data Provider and agrees to the terms of this agreement.

  * •

"Results" means any outcome obtained by computational analysis of Data,
including for example machine learning models and models’ insights.

##  Appendix B Software License Agreement

MIT License

All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

##  Appendix C Our Prototype Tool

Figure 4: Our tool transforms an input table and a user query into a list of
valid completions. The input data is used to extract the selected rows $R$.
The resulting rows and query are used to construct a prompt which is fed to a
code synthesis LLM, such as GPT-4 or CodeLlama, generating multiple possible
completions. The outputs of these completions are then validated and the first
$k$ valid completions (along with the outputs) are returned. Figure 5: An
example run, with the input table $T$ and query $Q$. The tool extracts the
four most representative rows $R$ and uses them, along with the query $Q$, to
create a prompt to pass to the model. The first valid completion is used to
create an output column, which is shown to the user.

This section explains the workflow of our system using a running example in
Fig. 5. In this example, there is an input table full names and wants to
create a new column with user names, by concatenating the first initial and
the last name and converting them to lowercase.

The high-level workflow of our tool is depicted in Fig. 4 and formalized in
Algorithm 1.

Algorithm 1 Inference Algorithm

1:Explicit: user query $Q$, input table $T$, cardinality $k$. Implicit:
completion limit $k_{max}$ (with $k\leq k_{max})$, number $n$ of rows to be
selected.

2:Pair of lists $(C,O)$, with $|C|=|O|\leq k$, of unique completions and their
corresponding outputs.

3:procedure Infer($Q,T,k$)

4: $M\leftarrow\textsc{Cluster}(T)$ $\triangleright$ map elements into
clusters

5: $R\leftarrow\textsc{Select}(T,n,M)$ $\triangleright$ select $n$ most
representative rows from $T$

6: $P\leftarrow\textsc{Prompt}($$Q$$,R)$ $\triangleright$ prompt creation

7: $B,C,O\leftarrow k_{max},[],[]$ $\triangleright$ initialize budget, caches

8: while $B>0\wedge|C|<k$ do

9: $c\leftarrow\textsc{$\textsc{Llm}$}(P)$ $\triangleright$ sample completion

10: $B\leftarrow B-1$ $\triangleright$ decrement budget

11: $o\leftarrow\textsc{Exec}(c,T)$ $\triangleright$ execute against $T$

12: if $\textsc{Validate}(o)\land(c\notin C)$ then

13: $C\leftarrow C+[c]$ $\triangleright$ append completion to $C$

14: $O\leftarrow O+[o]$ $\triangleright$ append output to $O$

15: return $(C,O)$

The tool takes as input a user query $Q$ expressed in natural language, user
input table $T$ as a Pandas dataframe, and the target cardinality $k$ of
distinct completions to generate. To ensure termination within a reasonable
time, we set a limit $k_{max}$ on the number of calls to Llm ($k_{max}=8k$).
For our running example, $k$ is 1, $Q$ is “create a new column in lowercase
that concatenates the first initial and the last name.”, and $T$ is
Data({"Names":["John Smith", "Jack Will Anders", ...]}). At a high-level, the
algorithm first clusters the data in $T$ based on automatically synthesized
regular expressions and stores them in a map $M$ (line 2). It then extracts
_representative rows_ of the table using Select (line 3); combines the query
$Q$ and the rows $R$ to create a prompt $P$ using prompt (line 5); and then
queries Llm repeatedly using this prompt until the target completions are
reached or we exceed the budget of calls (lines 7-13). Each completion $c$
(line 8) is executed on the input table (line 10) using an exec procedure, and
if the completion is new and its output $o$ satisfies a Validate procedure,
the two are accumulated in $C$ and $O$. The lists of completions and outputs
are returned to the user (line 14). We now describe the key steps of the
algorithm in more detail.

Cluster Consider the input table $T$ in Fig. 5. As is common in data-centric
tasks, different rows have slightly format: some only have first and last
name, while others have one or two middle names, and some last names are
hyphenated. It is important to capture this syntactic variation in the prompt,
to make sure that the solution generalizes to all rows (or as many rows as
possible). For example, if the LLM were only exposed to rows with two names,
it could attempt to extract the last name as the suffix _after the first
space_ , which would not generalize to rows with more than two names. To
capture such syntactic variation, are rely on an existing tool FlashProfile
Padhi et al. (2018), which takes as input a set of strings and synthesizes a
set of regular expressions (regexes) from a restricted class, such that each
input string matches one of the regexes. In our running example, FlashProfile
would synthesize four regexes: [A-Z][a-z]+[$\textbackslash\textbackslash$s]
[A-Z][a-z]+, which matches rows with just two proper-case names,
[A-Z][a-z]+[$\textbackslash\textbackslash$s] [A-Z][a-z]+-[A-Z][a-z]+, which
matches rows with dashed last names, and two more (for three and four names,
respectively). Then, the output of FlashProfile can be used to cluster input
strings.

Select If the input table has only one column, like in our running example,
selecting representative rows based on the clustering results is trivial:
given the budget of $n$ rows to be included into the signature, simply pick
one row each from at most $n$ largest clusters. In Fig. 5, assuming our budget
is $n=5$, we pick one row from each of the four clusters generated by
FlashProfile (depicted with different colors), leading to four representative
rows. In case the input contains more than one column, FlashProfile might
cluster different columns differently. In this case we would like to select
$n$ rows that together cover as many strings as possible across all the
columns. We frame this as a _weighted maximal coverage problem_ — a well-known
NP-complete problem max  that can be solved approximately using the greedy
algorithm described in Algorithm 2. The algorithm takes as input the table
$T$, a map $M$ from the rows of the table to the set of clusters covered by
the element in each column of the row. It also takes as input the row budget
$n$. The algorithm iterates over all the rows in $T$ not already in $R$ (line
3) and in each iteration selects the row whose elements maximize the size of
the clusters covered (line 4), adding this row to $R$.

Algorithm 2 Rows Coverage Algorithm Select

1:procedure Select($T$, $n$, $M$)

2: while $\left|R\right|$ < $n$ do

3: for $r\in T_{r}\wedge r\notin R$ do

4:
$\textsc{best}\leftarrow\textbf{argmax}(\sum\left\\{\,\left|c_{i}\right|{\mbox{s.t.\
}}c_{i}\in M[r]\,\right\\})$ $\triangleright$ greedily increase coverage

5: $R\leftarrow R\cup\textsc{best}$ return $R$

Prompt Prompt creation procedure Prompt creates a textual prompt by
concatenating the NL query and the representative rows of $T$. The selected
rows $R$ are in the form of a Pandas dataframe. A concrete example of the
resulting prompt is shown in Fig. 5.

Llm The completion procedure Llm queries GPT-4 (or another code-generating
model), passing the prompt $P$ and predefined stop sequences. We use stop
sequences that we have found to allow the LLM to generate at least one
solution while typically not using the entire token budget. Note that the LLM
needs to produce multiple completions, because it will filter out invalid
completions, which are not considered at all. A naive approach would be to
request a single completion, validate it, and repeat the process until $k$
distinct valid completions are obtained; this, however, requires sending the
prompt to the LLM every time, which incurs a monetary cost. An alternative
approach is to _batch_ the completions, _i.e._ request some number $b$ of
completions in parallel; if the batch size $b$ is too large, however, this
also incurs unnecessary cost, since we are requesting more output tokens than
we need.

Further details are available in Appendix D.4.

Exec The procedure Exec turns each LLM completion into a stand-alone
executable program and runs it to obtain the final output $o$. There are two
main challenges to be addressed in this step. First, LLM completions do not
have a consistent way of identifying the final output: for example, the last
line of the completion might be an expression that computes the output, or an
assignment to a “result” variable, or a print statement. So our tool uses a
predefined set of rewrite rules, which we developed by analyzing the patterns
in completions. The second challenge is that executing arbitrary LLM-generated
code poses a security risk; for this reason, we execute completions in a
sandbox. Further details are available in Appendix D.5.

Validate Finally, the procedure Validate checks that the output value $o$ is a
dataframe with the right dimensions. The completions that executed without
runtime errors during Exec and passed the output validation are deemed _valid_
and are presented to the user. Further details are available in Appendix D.6.

##  Appendix D Experimental Setup

###  D.1 Evaluation Parameters

We report all results with GPT-4 as the LLM with a temperature of 0.5. We also
do a performance comparison for no-data, first-row and full-data regimes and
the different selection strategies with CodeLlama Roziere et al. (2023) as the
LLM.

###  D.2 Evaluation Metrics

The probability that at least one of $k$ inferred outputs is correct is called
pass@$k$ Chen et al. (2021). More formally, pass@$k$ is the probability that
with a sample of $k$ code completions, at least one is correct. To measure
this probability empirically for each datapoint, we compute up to $m$ valid
programs by sampling from GPT-4 or CodeLlama. We count the number $s$ of
correct completions, and hence compute an estimate of pass@$k$ as
$1-\binom{m-s}{k}/\binom{m}{k}$ Chen et al. (2021). By computing $m>k$
completions the estimate has lower variance than by simply computing $k$
completions. Each pass@$k$ on a whole dataset is the average of pass@$k$ over
all its datapoints. All evaluation results are averaged over tasks, computing
$m$ valid completions to estimate pass@$k$ or pass@$k$($X$%). In practice, we
set $m=20*k$ when we report results for $k=1$ or $k=5$.

Figure 6: pass@$k$ (CodeLlama) with (a) no-data, (b) first-row, and (c) full-
data (10 rows) passed to the model. The leftmost group of bars represent
pass@k with all classes followed by separate pass@k for ind, dep and ext
tasks. Smaller models have a huge performance drop. But the trend of
performance improving with the amount of data passed to the model is seen.
Figure 7: pass@$k$ (CodeLlama) for dep tasks with no-data, and n=1 and 5 rows
passed to the model, using random (random-n) selection, representative
selection (represent-n) and full-data (1000 rows). Completions are evaluated
on 1000 rows. Figure 8: pass@$k$ (CodeLlama) for 17 out of 44 dep tasks (more
than two clusters) with no-data, random selection (random-n) and
representative selection (represent-n). Completions are evaluated on 1000
rows.

###  D.3 Prompt Template

For each task, we generate prompts according to the data regimes and selection
strategies as described above. Below is an example prompt for the query
"Create a new column with the difference in hours, minutes and seconds between
the two timestamps in the format HH:MM:SS" with one selected row:

⬇

# Python 3

import pandas as pd

df = pd.DataFrame()

df[’Start’] = [’2/22/2015 1:06:20 PM’]

df[’End’] = [’2/23/2015 3:08:20 PM’]

# Create a new column with the difference

in hours, minutes and seconds between the

two timestamps in the format HH:MM:SS"

###  D.4 Completions Generation

_Parallelization._ For efficiency, we request multiple completions from GPT-4
per iteration in Alg.1. To try to minimize both inference time and the load on
OpenAI’s servers, we adapt the batch size to an estimate of the probability
that the next completion is valid. The batch size used in each iteration is
$n=\min\left(\lceil r/p\rceil,B,L\right)$, where $r=k-|C|$ is the number of
valid completions still to obtain, $B$ is the remaining completion budget, and
$L$ is a parallelization limit enforced by the ChatGPT API. The probability
estimate $p$ is updated after each iteration by counting the number of valid
and invalid completions in that iteration’s batch.

Since pass@$k$ is calculated only from valid completions, it is not influenced
by either parallelization or batch size adaptation. We additionally report the
average "pool" size (valid and invalid completions) to measure the cost of
retrieving valid completions using the above approach in all our experiments.

_Stop sequences._ The most effective stop sequence we found that allows GPT-4
to generate at least one solution while not usually using the entire token
budget is a blank line followed by a line comment; i.e. \n\n#. Further, to
keep GPT-4 from generating what appears to be the rest of a forum post after a
code snippet, we also use the stop sequence </code>.

_Completion cleanup._ Having forum posts apparently in GPT-4’s training data
means some completions would raise SyntaxError exceptions when executed due to
formatting artifacts, and therefore be invalid. Instead, to make the most of
the completion budget, we replace formatting artifacts. In particular, we
replace HTML escape sequences such as < and " with Python operators
and delimiters. Cleanup additionally removes unnecessary whitespace, blank
lines and comments, and truncates completions at \n# when it appears after
executable code.

###  D.5 Execution of Completions

_Rewriting._ Completions returned by GPT-4 do not clearly indicate which
variables or expressions are intended to be the answer to a query. This must
be inferred from the shape of the code. We found that an effective way to
identify and expose the likely answer is to search backwards to find the last
unindented (i.e. top-level) statement that has one of a few forms, and rewrite
the completion so that its last statement is an assignment to a fresh
identifier $var_{out}$. The statement forms and rewrites are

  * •

$var$ = $expr$: append the statement $var_{out}$ = $var$ to the completion

  * •

$var$[$expr_{i}$] = $expr$: append the statement $var_{out}$ = $var$ to the
completion

  * •

print($expr$, …): replace this statement and the rest of the completion with
$var_{out}$ = $expr$

  * •

$expr$: replace this statement and the rest of the completion with $var_{out}$
= $expr$

Rewriting also inserts import statements for common libraries (e.g. import
numpy as np). The rewritten completion is appended to the code that defines
the input dataframe to create a completed program. The completed program and
the output variable name $var_{out}$ are sent to a sandbox for execution.

_Sandboxing._ Because of security risks inherent in running the LLM-generated
code, we run completed programs in a sandbox. Our sandbox is a JavaScript web
service that runs Python programs in Pyodide Droettboom et al. (2022), a
Python distribution for WebAssembly. While Python programs running in Pyodide
have access to the host’s network resources, they at least are isolated from
other host resources including its filesystem, offering some level of
protection from malicious or accidentally harmful completions. After running
the code, the sandbox returns the value of $var_{out}$.

###  D.6 Validation of Completions

For a completion to be considered a correct solution in the calculation of
pass@$k$, its actual output must match the expected output. Matching cannot be
the same as equality and still conform to a reasonable notion of correctness;
for example, the natural breakdown of a solution might generate intermediate
columns in the actual output that are not in the expected output. The actual
output is allowed to vary from the expected output in the following ways and
still match the expected output:

  1. 1.

Extra columns

  2. 2.

Different column order

  3. 3.

Different column headers

  4. 4.

Number expected; actual is a number within small relative error (default 0.01)

  5. 5.

Number expected; actual is a string that parses as a number within small
relative error

  6. 6.

Boolean expected; actual is number 0 or 1

  7. 7.

Boolean expected; actual is a string that represents a truth value

  8. 8.

String expected; actual is a string that differs only in case

Allowed string truth value representations, allowed relative error, and
whether string matching is case-sensitive are (optionally) overridden per data
point as appropriate.