EXPLORA : Efficient Exemplar Subset Selection for Complex Reasoning (2024)

Abstract: Answering reasoning-based complex questions over text and hybrid sources, including tables, is a challenging task. Recent advances in large language models (LLMs) have enabled in-context learning (ICL), allowing LLMs to acquire proficiency in a specific task using only a few demonstration samples (exemplars). A critical challenge in ICL is the selection of optimal exemplars, which can be either task-specific (static) or test-example-specific (dynamic). Static exemplars provide faster inference times and increased robustness across a distribution of test examples. In this paper, we propose an algorithm for static exemplar subset selection for complex reasoning tasks. We introduce EXPLORA, a novel exploration method designed to estimate the parameters of the scoring function, which evaluates exemplar subsets without incorporating confidence information. EXPLORA significantly reduces the number of LLM calls to ~11% of those required by state-of-the-art methods and achieves a substantial performance improvement of 12.24%. We open-source our code and data (https://github.com/kiranpurohit/EXPLORA).

## introduction answering complex questions that require multistep reasoning @xcite @xcite @xcite over structured and unstructured sources is an active research area with applications in finance, law, fact-checking and healthcare @xcite . unlike fine-tuning task-specific models @xcite @xcite @xcite , recent advances in large language models (llms) have paved the way for new approaches that employ in-context learning (icl) @xcite to solve complex reasoning problems. this approach focuses on choosing a small number of demonstration examples to be used as input prompts to llms. an effective way to tackle complex reasoning problems is to use chain-of-thought (cot) prompting, which adds hand-crafted natural language rationales as stepwise solutions to the prompts, resulting in the triplet (input, rationale, output) @xcite . in this work, we refer to this triplet as an exemplar. a limitation of the cot-based method for reasoning tasks is the tedious and non-scalable manual effort required in selecting the rationales or exemplars @xcite @xcite . to address these limitations, both static and dynamic approaches for automatic exemplar selection have been proposed @xcite @xcite . some approaches require annotated data and training of multiple models for exemplar selection @xcite . dynamic exemplar selection methods often involve additional computational costs because they select exemplars during query time, necessitating extensive query encoding and dynamic exploration of the search space. in contrast, static exemplar selection pre-selects a small subset of exemplars, which are used during llm inference. prior exemplar selection methods do not capture interactions between the exemplars in the selected set @xcite . additionally, current static selection approaches @xcite are characterized by a large number of llm calls, which are computationally expensive. in this work, we propose explora, a novel static exemplar subset selection method that selects multiple low-loss exemplar subsets (overview in figure 1 ). our method is designed based on two hypotheses: (1) an effective exemplar selection algorithm for icl should model the end-to-end icl process, and (2) prompt generators (refer sec-tion 3.1), which generate prompts using multiple exemplar subsets can be used to enhance the effectiveness of static icl predictors for complex reasoning tasks. following these hypotheses, we model the problem of static exemplar selection for in-context complex reasoning (iccr) tasks as a novel top-l exemplar subset-selection problem. we use a linear model of similarity with validation examples for modeling the loss incurred by exemplar subsets. we propose a novel sampling-based bandit algorithm for simultaneously estimating the parameters of the loss model and identifying the top-l exemplar subsets, while incurring a low number of calls to the llm (which corresponds to a low sample complexity of the bandit algorithm). our approach implicitly captures the interactions between the exemplars in the subset by scoring subsets. we conduct extensive experiments across multiple reasoning-based qa tasks. our results indicate that explora outperform both static and dynamic exemplar selection baselines by 12.24% and 45.45% respectively ( ## related work while many existing techniques for complex reasoning tasks involve fine-tuning of specialized models @xcite @xcite , these approaches require access to the model parameters. recent developments in language models have introduced few-shot prompting approaches @xcite through icl @xcite @xcite and cot in complex reasoning tasks @xcite @xcite @xcite . however, a major drawback of these approaches is the need for manual selection of exemplars, which is tedious and non-scalable. moreover, icl is sensitive to the sample order @xcite , dataset, task, and models @xcite , making optimal exemplar selection essential for stable task performance. exemplar-selection for icl: several automated exemplar selection methods have been proposed to eliminate the need for manual selection. these include reinforcement learning-based approaches @xcite , determinantal point processes @xcite , low rank approximation (dq-lore) @xcite and constrained optimization @xcite , which are effective for reasoning tasks. additionally, alternative learning-free methods for diverse exemplar selection, such as similarity-based @xcite , complexity-based @xcite and mmr @xcite have also been proposed. however, existing dynamic exemplar selection methods incur additional computational costs during inference. to address this, a small, representative set of exemplars can be selected for icl. unlike coreset selection methods @xcite , which rely on gradient-based model updates for traditional deep learning, icl performs the target tasks without any parameter updates. to the best of our knowledge, there has been very little research in this area, with the closest work being lens @xcite . however, lens relies on llm's output probabilities and thus cannot be extended to black-box llms. in this work, we propose a novel and robust approach for static exemplar selection that is applicable to black-box and also other open language models. ## explora: model-based exploration for exemplar subset selection in black-box models, we cannot access the parameters of the llms or compute the gradient of the loss with respect to these parameters. additionally, intermediate representations or generative probability scores from llms cannot be utilized for scoring exemplar subsets. to overcome these challenges, we introduce a novel approach to effectively select exemplar subsets without relying on the parameters of the llms. section 3.1 formally describes the scorer figure 1: overview of explora: initially, set u is randomly selected from set u. in each iteration, parameters of the scoring function σ(α, .) are computed by minimizing a loss function. σ guides the selection of the subset from u \ u with the lowest loss, which is then used to update u . this iterative updating process ensures u maintains low-loss subsets, leading to a more accurate estimation of α in subsequent iterations. ## experimental setup we answer the following research questions. rq i. can explora a static exemplar selection approach achieve competitive performance compared to the state-of-the-art? ## conclusion in this work, we propose an efficient and robust task level exemplar subset selection method that identifies highly informative exemplar subsets. the proposed method saves resources by reducing the number of llm calls, in contrast to the current state-of-the-art. we also observe that the exemplars obtained using smaller llms can be well transferred to larger llms. explora outperforms existing static and dynamic exemplar selection methods. in future, we plan to further explore hybrid exemplar selection and the impact of exemplars for tasks involving complex reasoning.