Large Language Models are Demonstration Pre-Selectors for Themselves

Authors: Jiarui Jin, Yuwei Wu, Xiaoting He, Haoxuan Li, Weinan Zhang, Yiming Yang, Yong Yu, Jun Wang, Mengyue Yang
Primary area: foundation or frontier models, including LLMs
Keywords: Large Language Model, Demonstration Pre-Selection, In-Context Learning

Abstract:
In-context learning with large language models (LLMs) delivers strong few-shot performance by choosing few-shot demonstrations from the entire training dataset. However, previous few-shot in-context learning methods, which calculate similarity scores for choosing demonstrations, incur high computational costs by repeatedly retrieving large-scale datasets for each query. This is due to their failure to recognize that not all demonstrations are equally informative, and many less informative demonstrations can be inferred from a core set of highly informative ones. To this end, we propose FEEDER (FEw yet Essential Demonstration prE-selectoR), a novel \emph{pre-selection} framework that identifies a core subset of demonstrations containing the most informative examples. This subset, referred to as the FEEDER set, consists of demonstrations that capture both the ''sufficiency'' and ''necessity'' information to infer the entire dataset. Notice that FEEDER is selected before the few-shot in-context learning, enabling more efficient few-shot demonstrations choosing in a smaller set. To identify FEEDER, we propose a novel effective tree based algorithm. Once selected, it can replace the original dataset, leading to improved efficiency and prediction accuracy in few-shot in-context learning. Additionally, FEEDER also benefit fine-tuning LLMs, we propose a bi-level optimization method enabling more efficient training without sacrificing performance when datasets become smaller. 
Our experiments are on 6 text classification datasets, 1 reasoning dataset, and 1 semantic-parsing dataset, across 6 LLMs (ranging from 335M to 7B parameters), demonstrate that: (i) In few-shot inference, FEEDER achieves superior (or comparable) performance while utilizing only half the input training data. (ii) In fine-tuning, FEEDER significantly boosts the performance of LLMs.

Decision: reject
Reviewer scores: 6, 6, 3, 6

Reviews and discussion:
<thread>
creation date:
1730539915042

thread_type:
official_review

<thread_object>
creator: reviewer_cv5l

<content>
summary:
This paper presents FEEDER, a framework for improving in-context learning with large language models by pre-selecting a core subset of essential demonstrations. Through the concepts of "sufficiency" and "necessity," FEEDER effectively reduces dataset size, leading to enhanced efficiency in both few-shot inference and fine-tuning settings while maintaining or improving model performance.

strengths:
1. The paper introduces FEEDER, a demonstration pre-selector that optimizes in-context learning by identifying a core set of examples that capture "sufficiency" and "necessity." This subset enhances efficiency by reducing data size without sacrificing performance.
2.  Experiments on various datasets (text classification, reasoning, and semantic parsing) demonstrate the framework's effectiveness across multiple LLMs.

weaknesses:
1. The paper's explanations lack clarity and specificity in certain areas. For instance:
(1) When describing the poor demonstration of some examples, the authors provide general statements without detailing specific cases or examples. Adding concrete instances would help readers better understand and contextualize the problem. 
(2) The terms "sufficiency" and "necessity" lack clear definitions, which are essential for understanding the FEEDER framework.
2. Although the paper frequently emphasizes the tree-based approximation algorithm, the selection process remains time-consuming. It would be beneficial for the authors to include a comparison of computational efficiency, including time costs and accuracy, between FEEDER-selected samples and randomly selected samples of the same size in an in-context learning setting. This could help justify the trade-offs between computational efficiency and the benefits gained from the FEEDER method.
3. The paper lacks an in-depth analysis of certain observations from the experimental results. For example, Table 1 shows that some datasets perform better with larger sample sizes (i.e. n), while others achieve better results with fewer samples. It is unclear whether these discrepancies arise from dataset characteristics or other factors. 
4. The experimental results indicate that the FEEDER set and direct sample selection from the training set yield similar performance trends with respect to changes in n, which is inconsistent with the "necessity" mentioned by the authors. Given that FEEDER sets are meant to fulfill "necessity," it would be logical for performance to improve as the number of examples increases. However, this anticipated trend is not clearly reflected in the results. Further investigation into this issue is warranted, particularly to clarify why the FEEDER set’s performance does not show a clear improvement with increasing sample sizes.

questions:
1. Although the paper frequently emphasizes the tree-based approximation algorithm, the selection process remains time-consuming. It would be beneficial for the authors to include a comparison of computational efficiency, including time costs and accuracy, between FEEDER-selected samples and randomly selected samples of the same size in an in-context learning setting. This could help justify the trade-offs between computational efficiency and the benefits gained from the FEEDER method.
2. The paper lacks an in-depth analysis of certain observations from the experimental results. For example, Table 1 shows that some datasets perform better with larger sample sizes (i.e. n), while others achieve better results with fewer samples. It is unclear whether these discrepancies arise from dataset characteristics or other factors. 
3. The experimental results indicate that the FEEDER set and direct sample selection from the training set yield similar performance trends with respect to changes in n, which is inconsistent with the "necessity" mentioned by the authors. Given that FEEDER sets are meant to fulfill "necessity," it would be logical for performance to improve as the number of examples increases. However, this anticipated trend is not clearly reflected in the results. Further investigation into this issue is warranted, particularly to clarify why the FEEDER set’s performance does not show a clear improvement with increasing sample sizes.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730571787990

thread_type:
official_review

<thread_object>
creator: reviewer_rms6

<content>
summary:
This paper introduces a novel pre-selection framework called FEEDER, designed to identify a core subset of examples that exhibit the highest levels of "sufficiency" and "necessity." By using only this subset, FEEDER can effectively replace the original dataset, improving both efficiency and predictive accuracy in few-shot in-context learning.

strengths:
1. This paper presents a new metric system based on "sufficiency" and "necessity" to evaluate the importance of each example.
2. This paper proposes a tree-based search method to identify the core subset, which is novel to the existing literature.

weaknesses:
1. Even in the APPROXIMATION version presented in Section 4.2, achieving precise accuracy with terms like $1_{|W_{in}|}$ and $1_{|W_{out}|}$ in Equations 7 and 8 seems challenging. The current benchmark may very struggle to achieve 100% accuracy, raising questions about this method’s effectiveness and feasibility.

2. As the number of samples within each node grows, conducting few-shot tests on these samples becomes increasingly difficult. For instance, if the limit for few-shot samples is set to n=5, handling a node containing 1,000 samples would be problematic.

3. Most of the benchmarks used in this study, aside from GSM8k, are based on sentiment classification and linguistic analysis, which are proposed before 2018. These benchmarks are somewhat outdated and do not adequately represent the benchmarks currently prioritized by the research community.

4. Besides Llama 7B and Gemma-2 2B, the models tested are relatively outdated (before 2020) and have limited parameter sizes. This choice of models and benchmarks may reduce the impact and relevance of the paper’s conclusions for the present-day community.

questions:
N/A
</content>
</thread_object>

</thread>
<thread>
creation date:
1730688006483

thread_type:
official_review

<thread_object>
creator: reviewer_1pew

<content>
summary:
This paper addresses examples (a.k.a. demonstrations) selection for in-context learning (ICL) and Fine-tuning. The authors build on the hypothesis that a small set of highly informative examples can often encapsulate enough information to infer many less informative examples. This allows for the use of these smaller, more informative samples in ICL (or fine-tuning). The authors then propose a framework that defines "sufficient" and "necessary" samples for model prediction, where "sufficiency" implies that a sample enhances model prediction accuracy, and "necessity" means that a sample is required for the model to make correct predictions. The authors introduce a pre-selection framework to “select” necessary and sufficient samples from a training set (termed the "FEEDER set"), using a tree-based merging mechanism at each tree layer. Moreover, the authors propose a bi-level optimization method for fine-tuning based on FEEDER using a frozen LLM in the outer loop and optimizing LLM training in the inner loop.

Finally, authors demonstrate that the FEEDER set, across six different classification tasks, reasoning and semantic-parsing datasets and six large language models (LLMs), consistently provides superior performance.

strengths:
Considering that LLMs are resource-intensive, selecting the most effective samples from a large training set is a reasonable approach to improve "efficiency and accuracy" in inference (for few-shot learning) and training (for fine-tuning). To find the right selector, the authors first define "necessary" and "sufficient" instances, extending these definitions to necessary and sufficient sets. Based on this concept, they define $D_{\text{FEEDER}}$ as a subset of $D_{\text{TRAIN}}$ that is both sufficient and necessary. A brute-force approach to find $D_{\text{FEEDER}}$ would be expensive, so the authors propose a tree-based merge technique that builds from the bottom up, merging examples into nodes based on their sufficient and necessary characteristics at each tree layer. They also claim that the approach has low complexity, yielding $D_{\text{FEEDER}}$ in a reasonable number of iterations. ICL evaluation results suggest that FEEDER is an effective pre-selector (or "compressor") of demonstrations and can benefit from various demonstration selectors. Additionally, for fine-tuning, the authors formulate sample selection as a bi-level optimization problem. In the outer layer, it identifies a “high-quality” sample set using a frozen LLM, while in the inner layer, it optimizes LLM training. In experimentation, authors show that FEEDER achieves improvements compared to fine-tuning with entire training set.

weaknesses:
While the paper’s motivation is reasonable and the argument flow is sound, there are some gaps in the authors' reasoning throughout. 

**Ambiguous Goal (Accuracy vs. Efficiency)**: It's unclear whether the authors are primarily focused on improving model accuracy or throughput (cost) with FEEDER. Throughout, they claim the approach improves efficiency and prediction accuracy, but for ICL, there is no evidence provided for how FEEDER enhances model efficiency. 

**Computation cost for FEEDER discovery**: The FEEDER discovery algorithm requires calling the LLM at each stage to assess the sufficiency relationship between datapoints in $\mathscr{W}_{k-1}$, which appears computationally expensive and potentially impractical. 

**Complexity and Scalability Concerns**: While the authors state that the FEEDER algorithm requires $O(K \log_2 |D_{\text{TRAIN}}|)$ iterations, each iteration involves comparing sufficient and necessary criteria between "every pair," resulting in an overall complexity of $O(K |D_{\text{TRAIN}}| \log_2 |D_{\text{TRAIN}}|)$.

questions:
Q1: In definitions 1 and 2, can  $(x_n, y_n)$ be $(x_m, y_m)$? In other words, can a sample be considered its own sufficient and necessary sample?

Q2: Since the ICL is limited to 5 to 10 examples, could author provide the results based on brute-force approach where we search across $plug$ and $unplug$ (as defined in Definition 1 and 2) for entire $D_\text{TRAIN}$
</content>
</thread_object>

</thread>
<thread>
creation date:
1730718952369

thread_type:
official_review

<thread_object>
creator: reviewer_y7ch

<content>
summary:
This paper proposes a demonstration pre-selection framework. Specifically, it considers both sufficiency and necessity conditions and introduces an approximate tree-based selection method. The author conducts extensive experimental validation under both in-context learning and fine-tuning settings.

strengths:
1. The paper is well written and easy to follow;
2. The idea of iterative optimization is reasonable;
3. The extension from instance level to set level and the approximation method based on transitivity are novel.

weaknesses:
1. Lack of experiments with larger-scale models. For example, the  original metrics on GSM8k is quite low. Although Section 5.3 mentions this issue, the scale of the models used in the corresponding experiments is still too small. The performance of few-shot selection for larger-scale models may differ from that of smaller models, and it is uncertain whether this method can be scaled up to larger models.
2. Regarding sufficiency and necessity, more ablation studies are needed to prove that both aspects are important.
3. In the implementation of tree construction, the different design choices of merging nodes among adjacent layers requires more experimental comparisons.

questions:
Please see the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732796242186

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Responses to all reviewewrs

comment:
We first summarize our response and the results of additional suggested experiments here. We have also responded to the specific concerns of each reviewer as individual comments below.

All reviewers agree that our idea is interesting and we would like to further clarify our contributions as follows.
1. FEEDER serves as a demonstration pre-selector designed to identify a subset of informative samples from the training dataset. Importantly, our FEEDER operates in an "once-for-all" manner: once constructed, it can serve any test data point without requiring additional computations. 
2. To address the high computational cost of computing a FEEDER set, we designed an efficient tree-based approximation algorithm. This algorithm reduces computational overhead by selectively removing "unnecessary" parts of the dataset while preserving the "sufficiency" of the remaining part. Our empirical results further support the efficiency of this approach, showing that limiting the tree depth to two (i.e., the number of iterations $K=1$) and running the algorithm for a single round (i.e., the number of rounds $R=1$) can reduce the training dataset size by nearly 20% (see Figure 4), meanwhile improving the few-shot performance (see Tables 1, 2, 3) and the fine-tuning performance (see Table 4). 

We then summarize the results of the suggested experiments as follows.
1. We appreciate the valuable suggestions from reviewers Y7CH and RMS6 to apply FEEDER to larger models to strengthen our paper. In response, we conducted additional experiments with FEEDER applied to Llama 3 (8B), a recently proposed and powerful LLM, on the GSM8K and SMCALFlow datasets. The results, presented in Table 3, demonstrate that FEEDER performs effectively when integrated with advanced LLMs.
2. In response to reviewers 1pew, RMS6, and CVSL, we have provided more detailed results on the time complexity of varying the number of iterations $K$ and the number of rounds $R$ in FEEDER, as presented in Appendix A10. Our empricial results in Tables 1, 2, 3 and 4 demonstrate that FEEDER achieves strong performance with a limited tree depth of two and a single round of running our approximation algorithm. 
3. As suggested by reviewers Y7CH and CSVL, we incorporated the following additional ablations as baselines to strengthen our in-depth analysis: (i) employing a random strategy as the pre-selector to evaluate the effectiveness of our method compared to a baseline with no informed selection (see Table 11, Appendix 9.1), and (ii) examining the impact of tree depth in our approximation algorithm to better understand its influence on performance and efficiency (see Figures 8 and 9, Appendices 9.2 and 10.1).


These new experiments demonstrate that our approximation algorithm significantly reduces the time complexity while simultaneously enhancing the performances of powerful LLMs. This underscores the advantageous trade-off between computational efficiency and improved model effectiveness achieved by our approach. 

For your convenience, all modifications in the updated PDF are highlighted in blue color.


[1] https://ai.meta.com/blog/meta-llama-3/
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes FEEDER to address examples selection for LLM in-context learning (ICL) and finetuning. The method is motivated by the hypothesis that a small set of highly informative examples can encapsulate enough information to infer many less informative examples. This is then used to define and select the sufficient and necessary samples for model prediction. The authors present a pre-selection framework for extracting essential samples from a training set, termed as FEEDER set, utilizing a tree-based merging mechanism, and propose a bi-level optimization approach for fine-tuning FEEDER and LLM training. All reviewers agreed the method is reasonable and addresses an important research problem. However, more than one reviewer found the experiments are not convincing enough, and a more detailed ablation study is required. At the end of the rebuttal, there were neither unanimous reviews nor strong recommendations for acceptance, and thus this paper can not be accepted by ICLR in its current version.