Hierarchical Demonstration Order Optimization for Many-shot In-Context Learning

We sincerely appreciate the time and efforts you've dedicated to reviewing and providing invaluable feedback to enhance the quality of this paper. We provide a point-to-point reply below for the mentioned concerns and questions.

Weaknesses

1. (Experiment) Additional validations out of text classifications are needed.

We reuse the experiment results from above as another reviewer had the same request. Here, we present the results of HIDO and all baseline methods on two new datasets: HellaSwag and MMLU. Once again, HIDO generally achieves the best or second-best accuracy when using various LLMs for these datasets. Notably, when using SciPhi on HellaSwag, HIDO outperforms the second-best method, PDO, with a 7.425% improvement. However, we observe that accuracy for both datasets is generally low when using Zephyr and Llama3, in contrast to SciPhi, suggesting that these two LLMs are not well-suited for the tasks these datasets are designed to evaluate.

We sincerely appreciate your dedicated time and effort in reviewing and providing invaluable feedback. We provide a point-to-point reply below to clarify certain misunderstandings and provide responses to the mentioned concerns and questions.

Weaknesses

1. (Experiment) add two baselines.

Here, we present the results of two baseline methods, IGDemo and RetrievalDemo, alongside HIDO for comparison. Overall, HIDO consistently achieves the best or second-best performance across all datasets and LLMs, highlighting its superiority over the baselines. For instance, when using LlaMa3 on TREC, HIDO outperforms RetrievalDemo (the second-best method) by 8.2%. Similarly, when using Zephyr on DBPedia, HIDO shows an 3.13% improvement over RetrievalDemo. Combined with earlier comparisons to other baselines, these results demonstrate that HIDO achieves superior performance across diverse datasets and LLMs.

2. (Experiment) experiment on newer tasks/datasets e.g., MMLU HellaSwag outside of the text classifications are necessary.

Here, we present the results of HIDO and all baseline methods on two new datasets: HellaSwag and MMLU. Once again, HIDO generally achieves the best or second-best accuracy when using various LLMs for these datasets. Notably, when using SciPhi on HellaSwag, HIDO outperforms the second-best method, PDO, with a 7.425% improvement. However, we observe that accuracy for both datasets is generally low when using Zephyr and Llama3, in contrast to SciPhi, suggesting that these two LLMs are not well-suited for the tasks these datasets are designed to evaluate.

Dear Reviewer obmS,

As we approach the rebuttal deadline (within one day), we kindly request you to review our responses to your concerns regarding submission #3256. If you find that we have adequately addressed your comments, we would appreciate your consideration in uplifting the evaluation scores accordingly.

Thank you for your time and consideration.

Best regards, Authors of submission 3256

4. Order is query dependent, ICL/RAG works order examples to LLM inference with long contexts, a simple “similarity based reordering” is cheap.

Although the order is query dependent, this is not in scope of this work. In our work, we assume that all the demonstration(q,a) pairs and prompting sentences are fixed. and we find the optimal demonstration order. One may always first find the optimal prompting sentences and demonstrations and then utilize our HIDO algorithm to improve many-shot ICL performance.

References

[1] Lu, Y., Bartolo, M., Moore, A., Riedel, S., & Stenetorp, P. (2022, May). Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (pp. 8086-8098).

[2] Xu, Z., Cohen, D., Wang, B., & Srikumar, V. (2024, June). In-Context Example Ordering Guided by Label Distributions. In Findings of the Association for Computational Linguistics: NAACL 2024 (pp. 2623-2640).

[3] Zhang, K., Lv, A., Chen, Y., Ha, H., Xu, T., & Yan, R. (2024). Batch-icl: Effective, efficient, and order-agnostic in-context learning. arXiv preprint arXiv:2401.06469.

7. Edit the manuscript in section 3 according to the listed suggestions.

Thank you so much for pointing out the lack of density issue of the section 3. We will improve it by providing more background knowledge and rearranging some non-significant contents to the appendix.

6. No need for LLM-generated probing samples, since we already need to label a lot for many-shot learning.

When calculating ICD-OVI metric, we are approximating $E(q,a)$. Probing samples can be dynamically generated to focus on regions of the distribution that are most informative for order evaluation. This targeted sampling can potentially achieve better estimation precision than uniform sampling from manual validation data.

5. No statistically significant difference in performance in vast majority of experiments.

As the LLM models are tremendously capable and mature products, improving their performance with a high margin is unrealistic. We claim that our paper’s performance improvement is sufficient for claiming statistical significance. This claim can be proved by multiple recent ICL optimization works. For instance, Lu et al.[1] showed performance improvements of 2-3% on text classification tasks. Similarly, Xu et al.[2] demonstrated improvements of 1-4% across various datasets. Zhang et al.[3] achieved gains of 2-5% in accuracy. Our method's improvement margins (3-6% across different tasks) are comparable to or exceed these recent works, supporting the statistical significance of our results.

3. What is $logP_{LLM}(a|\Pi(\mathcal{A})\oplus \emptyset)$? Will this stuff make gibberish? Why not an empirical distribution on true training examples?

In the table above, we demonstrate that $\log P_{LLM}(a|\Pi(\mathcal{A})\oplus \emptyset)$ produces meaningful results rather than gibberish. For three datasets, AGNews, MPQA, and TREC, we provide an example prompt that includes only the labels of the demonstrations and the top 10 possible tokens for the next token prediction. The token lists contain multiple dataset labels, indicating that the LLM is generating relevant and useful information. Moreover, while the first token is always '\n', we focus on the logit values for the dataset labels and select the highest among them, ensuring the output remains valid even if another token has the highest overall value.

For the reason why we utilize probing set but not the query-answer pairs directly from the input training demonstration data distribution, please consult the answer for weakness 6.

2. KL divergence can substitute V-information.

We can not directly compute the KL divergence written in Eq 1, since the real label of probing set is unknown. For the reason we utilize probing set but not the query-answer pairs directly from the input demonstration data distribution, please consult the answer for weakness 6.

We sincerely appreciate your dedicated time and effort in reviewing and providing invaluable feedback. Here, we provide a point-to-point reply below for the mentioned concerns and questions.

Weaknesses

1. Why are PDO and GlobalE different? PDO is different from GlobalE. For example, we have two samples, which produce the logit vector $[0.2, 0.5, 0.3]$ and $[0.3, 0.3, 0.4]$. Then, we know the frequency vector is $([0,1,0]+[0,0,1])/2=[0,1/2,1/2]$. GlobalE is its entropy, which is $-1/2\log1/2-1/2\log1/2=0.693147$. For PDO, we calculate the average KL divergence by $KL([0.2,0.5,0.3]||[1/3,1/3,1/3])=0.2\log (0.2 * 3)+0.5*\log (0.5 * 3)+0.3*\log (0.3 * 3)=0.0299486$. For LocalE, it is the average entropy of the probability $-([0.2*\log(0.2)+0.5\log(0.5)+0.3\log(0.3)]+[0.3\log(0.3)+0.3\log(0.3)+0.4\log(0.4)])/2=-0.46003$.

Dear Reviewer TJTc,

As we approach the rebuttal deadline (within one day), we kindly request you to review our responses to your concerns regarding submission #3256. If you find that we have adequately addressed your comments, we would appreciate your consideration in uplifting the evaluation scores accordingly.

Thank you for your time and consideration.

Best regards, Authors of submission 3256

Dear Reviewer TJTc,

Thank you for your thorough review of manuscript #3256. We have carefully addressed all points raised in your evaluation. If you find them useful, we respectfully request that you raise your evaluation score, as we think the evaluation "1: strongly reject" does not faithfully reveal the quality of our work.

Sincerely,

Authors of submission 3256

References

[1] Agarwal, R., Singh, A., Zhang, L. M., Bohnet, B., Rosias, L., Chan, S., ... & Larochelle, H. (2024). Many-shot in-context learning. arXiv preprint arXiv:2404.11018.

[2] Xu, Y., Zhao, S., Song, J., Stewart, R., & Ermon, S. A Theory of Usable Information under Computational Constraints. In International Conference on Learning Representations.

Questions

1. clarify optimal ignorance assumption.

A: We apologize for the typo. Here, the "optimal ignorance" indicates "optional ignorance" in [2]. The optional ignorance is a the condition that a function set $V\subset \Omega=\{f:X\cup \{\emptyset\}\rightarrow P(Y)\}$ needs to satisfy such that it becomes a predictive family, which is the premise that usable $V$-information can be applied. Officially, it is defined as $\forall f \in V, \forall L \in range(f), \exists f'\in V s.t., \forall x\in X, f'[x]=L, f'[\emptyset]=P.$ It intuitively means that if one agent want, it may ignore any side information $x$. In our work, we intentionally compose the $V_{\Pi}$ such that it is a valid predictive family. By doing so, the ICD-OVI may be designed upon the predictive family $V_{\Pi}$.

2. Why Theorem 2 is only limited to demonstrations within a cluster?

Theorem 2 theoretically applies to the entire demonstration set, but applying it globally is computationally infeasible due to the massive permutation search space. Instead, we apply it within clusters where demonstrations are semantically similar and LLM performance variance is lower. This allows efficient optimization within clusters while maintaining precision. For inter-cluster ordering, we exhaustively evaluate all possible cluster permutations since the number of clusters is small.

3. (Experiment) Sensitivity of HIDO w.r.t. embedding

Here, we demonstrate the performance of HIDO using three different embedding models: text-embedding-3-small from OpenAI and NV-Embed-v2 and stella_en_1.5B_v5 from HuggingFace. We observe that there is a rather large variance between the performance of each embedding model within a dataset, which is especially evident in TREC with a range of 10.16%. A major difference between the three models is that text-embedding-3-small has an embedding dimension of 1536, whereas NV-Embed-v2 and stella_en_1.5B_v5 has an embedding dimension of 4096 and 8192, respectively. Thus, as we only use text embeddings during clustering, having a lower embedding dimensions creates clearer boundaries between different demonstrations, allowing for similar demonstrations to be clustered together. A higher embedding dimension could create noise and allow overfitting, which is undesirable.

4. Intra-cluster items have near embeddings, but not necessarily gives lower variance.

To determine whether closer embeddings lead to lower variance, we determine intra-cluster embedding variance by calculating the standard deviation of the distances between each demonstration embedding and its cluster center for each cluster, then averaging these standard deviations. Additionally, we examine the accuracy standard deviation from a table further down that looks into the sensitivity of HIDO across different embedding models. Here, the table shows that, in general, the mean standard deviation of embeddings correlates with accuracy variance: as embedding variance decreases, accuracy variance also decreases. For example, in the AGNews dataset, the embedding and accuracy standard deviations are smallest for "text-embedding-3-small," second smallest for "stella_en_1.5B_v5," and largest for "NV-Embed-v2." This indicates that closer intra-cluster embeddings can lead to more stable model performance.

3. (Experiment) Computation-Performance Trade-offs

We vary the number of the clusters and present the computation-performance trade-off table for three datasets: AGNews, MPQA, and TREC. From the table, we witness that the computation cost increases superlinearly as the cluster numbers increases, showing that the cluster number is an important hyperparameter for the model's computation cost. Fortunately, by using a relatively small number of clusters (which keeps HIDO's computational cost comparable to the baselines shown in Table 1), we achieved state-of-the-art performance across all datasets. This demonstrates that HIDO can deliver superior results efficiently.

2. Why don’t you use 2000 shot?

We do not experiment with 2000 shot since

• Restricted budget: Considering that current LLMs supporting context windows as long as that of 2000 demonstrations are charged and the limited budget, we are not able to explore our HIDO with 2000 demonstrations. However, we will perform experiments as soon as it is accessible in the future.
• Current shot number is sufficient: According to Agarwal et. al. [1], many-shot in-context learning (ICL) is defined as ICL with more than fifty demonstrations. Therefore, our experiments, where we adopt 50 to 150 demonstrations, is sufficient to research on the behavior of many-shot ICL.

We sincerely appreciate the time and efforts you've dedicated to reviewing and providing invaluable feedback to enhance the quality of this paper. We provide a point-to-point reply below for the mentioned concerns and questions.

Weaknesses

1. The assumption that “the demonstration order optimized for answer prediction also works well for sample generation.” Lacks support.

We respectfully disagree that this assumption lacks support. Our paper provides both quantitative and qualitative evidence supporting the assumption:

• Quantitative Evidence: As shown in Appendix C.3, the $l_2$ distance between demonstration embeddings and generated probing set embeddings consistently decreases as the order optimization improves. This trend is observed across multiple models (LlaMa3, SciPhi, Zephyr) and datasets. This fact effectively supports our assumption.
• Qualitative Evidence: Appendix C.5 provides extensive examples showing that probing sets generated using optimized orders exhibit: (2.a) Increased semantic richness and specificity; (2.b) Better adherence to dataset-specific formats; (2.c) More accurate labeling; (2.d) Greater diversity in generated samples.

Dear Reviewer 9taG,

As we approach the rebuttal deadline (within one day), we kindly request you to review our responses to your concerns regarding submission #3256. If you find that we have adequately addressed your comments, we would appreciate your consideration in uplifting the evaluation scores accordingly.

Thank you for your time and consideration.

Best regards, Authors of submission 3256