SEER : A Knapsack approach to Exemplar Selection for In-Context H ybrid QA (2023)

Abstract: Question answering over hybrid contexts is a complex task, which requires the combination of information extracted from unstructured texts and structured tables in various ways. Recently, In-Context Learning demonstrated significant performance advances for reasoning tasks. In this paradigm, a large language model performs predictions based on a small set of supporting exemplars. The performance of In-Context Learning depends heavily on the selection procedure of the supporting exemplars, particularly in the case of HybridQA, where considering the diversity of reasoning chains and the large size of the hybrid contexts becomes crucial. In this work, we present Selection of ExEmplars for hybrid Reasoning (SEER), a novel method for selecting a set of exemplars that is both representative and diverse. The key novelty of SEER is that it formulates exemplar selection as a Knapsack Integer Linear Program. The Knapsack framework provides the flexibility to incorporate diversity constraints that prioritize exemplars with desirable attributes, and capacity constraints that ensure that the prompt size respects the provided capacity budgets. The effectiveness of SEER is demonstrated on FinQA and TAT-QA, two real-world benchmarks for HybridQA, where it outperforms previous exemplar selection methods.

## introduction hybrid documents, which combine tables and text paragraphs, are prevalent in various industries such as finance, healthcare, and manufacturing. the development of question-answering systems capable of effectively handling these documents holds the potential to automate business processes and enhance accessibility to the information they contain. several benchmarks anchored in the financial domain have been introduced for hybrid question answering (hybridqa) @xcite @xcite . figure 1 presents an example from the finqa dataset. despite ongoing progress, current hybridqa models have yet to achieve human expert performance @xcite . recently, in-context learning (icl) with large language models (llms) has shown great performance on reasoning tasks. in this setting, a set of exemplars, i.e. training instances with their answers, are provided as part of the input prompt to assist llms in generating the correct answer. icl is an inference time technique that keeps the llms parameters frozen @xcite . the performance of icl depends heavily on the quality of the provided exemplar set @xcite . various strategies, ranging from random selection to similarity-based retrieval, have been proposed to tackle this problem @xcite @xcite . when selecting exemplars for hybridqa, special consideration must be given to the unique challenges of the task, including diverse reasoning chains, large context sizes @xcite , and the limited correlation between the question and its reasoning chain. in this work, we propose knapsack programs as a framework to model exemplar selection for icl. knapsacks are a family of integer linear programs that search an optimal subset of items under linear constraints @xcite . for a given test instance, a knapsack program is solved to obtain the optimal exemplar set. this expressive framework figure 1 : an instance of the finqa dataset @xcite ). text snippets of the text paragraphs are shown in the dashed box. ## related work in-context learning llms have shown the ability to perform a wide range of tasks with only a few exemplars provided as a prompt while keeping all the model parameters frozen @xcite . however, the performance is highly dependent on the quality of the provided exemplars @xcite . hence, several approaches have been explored for exemplar selection, including nearest neighbor search @xcite , reinforcement learning @xcite , clustering @xcite , search algorithms @xcite , and supervised learning @xcite . @xcite consider token capacity indirectly by constructing the largest possible prompt with the selected exemplars. in contrast to previous methods, we consider exemplar selection as an ilp knapsack program, which allows us to specify diversity-enhancing constraints, directly optimize the token capacity without simple heuristics, and leverage powerful solvers to find a performant exemplar selection. hybrid question answering @xcite introduced the task of hybridqa on opendomain wikipedia pages. later on, datasets based on real-world financial documents were introduced @xcite @xcite . previous work has focused on improving the retriever-generator framework @xcite @xcite . @xcite use few-shot chain-of-thoughts to solve the task of hybridqa. however, they focus on improving the prompt format, while our work focuses on selecting good exemplars. integer linear programming for nlp integer linear programming has been used in many nlp tasks (martins, 2014), including coreference resolution @xcite , sentence compression @xcite , dependency parsing @xcite , semantic role labeling @xcite , and translation @xcite . in this work, we introduce a novel application of ilp in nlp: exemplar selection for icl. furthermore, it is, to the best of our knowledge, the first time that the knapsack family of ilp programs is used in nlp. ## analysis how sensitive is seer to variations in constraint parameters α and β? we analyze seer's and seer gold 's sensitivity to different (α,β) value pairs. by increasing α, we encourage the selection of exemplars that share the predicted attributes of the test instance. conversely, increasing β promotes the inclusion of exemplars with different attributes, thus ensuring diversity and mitigating errors introduced by the constraint modules. we evaluate the ea and em on the dev set for the pairs (50,25), (75,0), (75,25), (100,0). the results, depicted in figure 6 , indicate that the difference in ea and em between the lowest and doskdehwd )lq4@xmath0ffxudf\ doskdehwd 7@xmath1 ([dfw0dwfk 6((5 6((5jrog figure 6: em and ea (%) for different pairs of (α/β) values. results averaged over 5 iterations on the dev set. ## conclusion this paper investigates the problem of exemplar selection for icl in hybridqa tasks. we propose ilp as a framework for exemplar selection and introduce seer, a novel method based on knapsack programs. while existing methods only focus on the high diversity of questions and how to solve them, seer explicitly tackles two other key challenges of hybridqa exemplar selection in the form of integer linear constraints. specifically, seer focuses on the following challenges, the low correlation between the problem's questions and attributes on one hand and the large context required to solve these problems through diversity and capacity constraints. diversity constraints enhance performance by selecting exemplars that share the same attributes as the test instance. capacity constraints provide fine-grained control to the end-user over the token budget allocated to the prompt, ensuring sufficient tokens to generate the desired output. this level of control is beneficial in overcoming the limitations of the backbone llm and dealing with financial constraints. evaluation on two financial hybridqa datasets shows that seer outperforms previous icl exemplar selection methods, especially under limited token capacity. for future research, we plan to explore additional attributes and seek ways to enhance the overall performance of the constraint modules. leveraging the flexibility of the knapsack framework, we intend to study the potential of incorporating constraints defined by end users, such as domain experts, to further refine exemplar selection. additionally, seer can be extended beyond the hybridqa setting to encompass other modalities like images and knowledge graphs, as well as other tasks, such as hybrid fact-checking @xcite , data-to-text generation @xcite , and multimodal fraud detection @xcite .