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

We sincerely appreciate your dedicated time and effort in reviewing and providing invaluable feedback. We also thank you for recognizing the novelty and the significance of our contributions. We provide a point-to-point reply below for the mentioned concerns and questions.

---

W1: The experiments are only conducted on the traditional text classification datasets. And these tasks are not difficult to current LLMs anymore. Instead, QA tasks or reasoning tasks can better reflect the quality of the ICL demonstrations. Also, the improvements may be more significant on these tasks since they are more challenging. If the method proposed performs well on more challenging datasets, which indicating the applicability as well as effectiveness on more diverse fields, I would re-consider my score.

Thank you for your encouraging comments! To explore our proposed HIDO's performance on more challenging tasks, we perform experiments to test our HIDO along with all baselines on two reasoning datasets HellaSwag and MMLU on two LLMs SciPhi and Llama3. We find that HIDO achieves consistently optimal performance across all settings. Most excitingly, we find that the HIDO can achieve more than 5% accuracy improvement on HellaSwag on SciPhi comapred with the runner-up baseline method, proving the effectiveness of our HIDO on challenging reasoning datasets.

---

W2: Explore how close is the HIDO compared with oracle on small number of demonstrations.

Since testing oracle demonstration order requires us to examine each possible order of $n$ demonstrations, which is $n!$ times. Therefore, we can only conduct experiment for up to 5 demonstrations. Please see the experiment resuls in below. HIDO achieves near-oracle results almost all datasets. These oracle comparisons validate that HIDO's ordering strategy genuinely improves performance rather than appearing effective due to weak baselines.

---

Q1: How long does it take for optimization? Overhead of this work and baselines should be analyzed further, such as time cost, the number of API queries, or the number of tokens, etc. Curves may be more clear and straightforward for users to get aware that how much overhead can achieve how good performance.

We test SciPhi LLM on varios datasets to benchmark the training time of our HIDO model (hyperparameters are aligned with the experiment setup in the main paper).

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.

---

W1: Statistical robustness is missing: results are reported as means plus\minus std but lack p-values or paired significance tests. Smaller gains could be noise.

We appreciate the reviewer's concern about statistical robustness. To address this, we conducted paired t-tests on our experimental data. For example, on the HellaSwag dataset with SciPhi LLM:

HIDO vs LocalE: t(2) = 7.571, p < 0.05, Cohen's d = 1.163

This represents a statistically significant improvement of 6.90 percentage points with a large effect size. Similar significant improvements were observed across dataset-model combinations.

---

W2, Q1: ICD-OVI depends on generated probes; if the LLM hallucinates, the metric may mislead. No analysis of probing reliability is provided, such as calibration analysis.

This is exactly why we propose the HIDO method. Because we have HIDO, we theoretically do not rely on the correctness of the labels of the probes (please see line 179-181). Specifically, we filter the probing samples with PVI threshold. When the sample PVI lower than the threshold, we consider the sample possibly incorrect and we use an approximation method delineated in line 187-189 to calculate the ICD-OVI score to guarantee preciseness. The significant performance gain of choosing demonstration orders based on our ICD-OVI metrics compared with GlobalE/LocalE shows the reliability of our ICD-OVI metric.

---

W3: Hyperparameter brittleness: choice of cluster count k appears dataset-specific (Fig. 3b), with no principled selection method beyond grid search.

We argue that although cluster count $k$ is data dependent, there is only four choices ($k=$2, 3, or 4) by design (please see Section ). Therefore, even if we conduct grid search, there will not be limited additional computational cost. Here, we take the chance to provide empirical advice on choosing number of clusters: according to extensive experiments, raising number of clusters from 3 to 4 does not provide significant performance gain. Hence, we recommend try the cluster being 2 as a first trial since it is most efficient. If the result does not match required performance, raise the number of clusters to three. The optimal performance will be acquired at this point in most cases.

---

W4, Q2: HIDO still requires many LLM calls per ICD-OVI estimate; no wall-clock times or API call counts are given, raising questions about practical feasibility.

We test SciPhi LLM on varios datasets to benchmark the training time of our HIDO model (hyperparameters are aligned with the experiment setup in the main paper).

---

W5, Q3: All experiments use ~150-shot prompts, whereas practical few-shot ICL typically uses much fewer examples. Although the focus of the paper is on many-shot ICL, it remains unclear whether HIDO’s gains persist at 8-32 shots, where ordering should matter more.

Thank you for the insightful comment! We kindly note that this is a misunderstanding.

• Paper scope is explicitly many-shot ICL (>50 demonstrations): Our contribution targets the computational intractability of order optimization in many-shot scenarios where traditional methods fail due to n! complexity.
• Evaluating 8-32 shots misrepresents our core contribution and is analogous to critiquing distributed systems research for not testing single machines.
• Reviewer's assumption about order sensitivity is incorrect: Figure 1 demonstrates that many-shot ICL (150) exhibits comparable or greater order instability than few-shot (10), contradicting the claim that "ordering should matter more" at fewer shots. More demonstrations create more complex interdependencies, not fewer.
• 150 shots represents the frontier where our method is needed: At 8-32 shots, existing methods (GlobalE, LocalE, PDO) remain computationally feasible. Our HIDO framework specifically addresses the computational challenges that emerge in many-shot scenarios enabled by modern LLMs' expanded context windows (16K-1M+ tokens in Table 1).

---

W6: In the many-shot setup, it’s unclear how much of HIDO’s improvement stems from genuine ordering versus simple primacy/recency biases. There is no study on how position (especially middle demonstrations) influences performance.

Primacy/recency biases affect beginning/end positions most, but middle demonstrations still significantly impact performance. Our ablation study directly proves this: HIDO vs. HIDO-NIntra (Fig. 3a) provides a controlled comparison where both methods have identical inter-cluster arrangements—meaning the same demonstrations occupy the critical beginning and end positions. The only difference is the ordering of middle demonstrations within clusters (intra-cluster order). Despite identical primacy/recency positioning, HIDO consistently outperforms HIDO-NIntra across datasets, demonstrating that strategic ordering of middle demonstrations provides substantial gains beyond positional biases. This performance gap (e.g., ~2% on TREC) proves that our hierarchical optimization captures genuine semantic relationships rather than simply exploiting positional effects.

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.

---

Can you signpost the practical meaning of $f(\cdot|0)$ after equation (4) earlier for better reading experience?

Thank you so much for the invaluable suggestion! We will signpost the practical meaning of $f(\cdot|0)$ early after its first appearance.

---

In the remark from l202-206, does this mean you use a fixed set of generated qa pairs? Doesn't the set of answers A you need to test for depend on the observed $\hat{a}$ from the runs of $\Pi(D) + \hat{q}$?

No, the probing set is still $\Pi$ dependent. It's just when one calculate the Equ. (5), one can share the term $P_{LLM}$($\hat{a}i$ | \Pi(A) $$\oplus \emptyset) across different $i$s since $\Pi(A)\oplus\emptyset$ has nothing to do with $i$. However, when calculating P_{LLM}$$(\hat{a}i|\Pi(D)\oplus \hat{q}i), one have to recalculate for different $i$ since the condition of the probability relys on $i$.

---

Do you test an ablation of HIDO without ICD-OVI using one of the prior heuristic methods? How do we know the inter-intra alternating algo isn't the main contributor for performance?

Here, we test the HIDO with/without ICD-OVI metric on MPQA and TREC (we did not test on all adopted datasets in the main paper due to the limited time budget). The intra/inter cluster orders are randomly determined. From the following table, we observe that removing ICD-OVI causes the HIDO performance to degrade significantly. Additionally, there is less variance between experiment rounds, indicating that our metric offers more stable performance.

---

"the intra-cluster demonstrations share proximate embeddings, which significantly decreases ICL performance variance when demonstration orders vary" Makes sense, but how do you substantiate this?

To substantiate the claim that "the intra-cluster demonstrations share proximate embeddings and significantly decreases ICL performance variance when demonstration orders vary", 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.

---

How do you generate probing samples?

For a given demonstration order $\pi$, we concatenate the ordered demonstrations $\Pi(D)$ and prompt the LLM to generate new demonstrations (i.e., query-answer pairs) that mimic the original demonstration distribution

---

Do not use citet inline citations; provide full names for datasets in l293-296.

Thank you so much for the invaluable suggestions! We will revise the manuscript based on your suggestions.

We sincerely appreciate the time and effort you've dedicated to reviewing and providing invaluable feedback as well as recognizing our work as solving timely and significant problem, theoretically strong, and empirically effective.

W1: The paper assumes that reordering demonstrations within a cluster has little impact on performance (line 226), but provides no theoretical justification or empirical evidence to support this claim. This assumption is critical to the efficiency of the proposed method, and its validity remains unclear.

To test if reordering demonstrations with similar embeddings (i.e in the same cluster) causes smaller ICL performance change than reordering demonstrations with in different clusters, we perform the following experiments. First, we conduct HIDO on a set of demonstrations. Then, we randomly select a demonstration cluster generated by HIDO. Finally, we randomly select two samples within the cluster and swapped their positions in the optimized order. We generate demonstration orders following this procedure and evaluate for accuracy. We call this experiment IntraSwap. Additionally, we conduct a comparison experiment called InterSwap, where we randomly swap two samples in different clusters. These experiments both used LLaMa-7B-chat-hf on MMLU dataset. We find that the accuracy range for IntraSwap is 41.41% - 42.19%, but for InterSwap, it is between 40.23% - 42.19%. These results empirically proves our assumptions that reordering samples with similar embeddings does not impact the performance much.

W2: The effectiveness of grouping demonstrations with similar embeddings together is not rigorously examined. It is unclear whether placing similar demonstrations consecutively is indeed optimal, or whether interleaving them with demonstrations from other clusters could yield better results. The paper does not provide experimental comparisons between mixed and grouped orders.

To demonstrate the effectiveness of grouping demonstrations instead of mixing the demonstrations, we examine if interleaving demonstrations across clusters will yield better ICL performance through the following experiment design. First, we conduct the HIDO and find the optimal intra-cluster and inter-cluster demonstration orders. Then, according to the inter-cluster order, we pick from each cluster the top demonstration based on their respective intra-cluster order. We continue this process in round-robin style until all the demonstrations from all clusters are exhausted. The generated demonstration order is thus composed of interleaved demonstrations from different clusters. We test this experiment using LLaMa-7B-chat-hf on MMLU dataset. It achieves an accuracy of 41.02% whereas HIDO achieves 41.41%. The magnitude of the improvement is likely due to the same optimized order used in both experiments, but the higher accuracy for HIDO shows how grouping gives better performance than mixing

W2 (part 2): The impact of the choice of embedding model on the overall performance of HIDO is not explored, leaving potential sensitivity or robustness issues unaddressed.

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 text-embedding-3-small achieves the best performance in almost all datasets. We consider the reason why text-embedding-3-small achieves leading performance 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. 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.

W3: All selected datasets are text classification tasks, which represent a narrow range of application scenarios. Moreover, such tasks often achieve high accuracy even with few-shot settings, making the necessity and impact of many-shot approaches less compelling. As a result, the improvements brought by HIDO are less significant on already well-performing datasets such as AGNews, CR, and DBPedia.

We respectfully disagree with this characterization.

• While we format all tasks as multiple-choice questions for consistency, our selected datasets represent diverse semantic scenarios beyond simple text classification: AGNews, DBPedia are Topic classification datasets, CR, MR and SST-5 are sentiment analysis datasets with varying granularities. RTE and CB are textual entailment and natural language inference datasets. TREC is question type classification and MPQA is opinion polarity detection dataset. This diversity follows established ICL works ([24, 43] in paper) and ensures fair and comprehensive comparison with existing demonstration order methods.

• Regarding the "high accuracy with few-shot" concern: Our Figure 1 empirically demonstrates that many-shot ICL (150 demonstrations) significantly outperforms few-shot ICL (10 demonstrations) across all tested models - contradicting the claim that these tasks do not benefit from many-shot approaches. For instance, on TREC, many-shot ICL achieves ~85% accuracy compared to ~75% for few-shot across different models.

• To further address your concern, we conduct experiments on two datasets MMLU and HellaSwag, which are both language reasoning datasets that few-shot ICL suffer to provide effective performance. 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.

Q1: The supplementary material appears to be missing sections F.5 and F.6, which are referenced in the text.

We sincerely apologize for the compiling error, the two tables in F.5 and F.6 are compiled and displayed after the author checklist. The authors inadvertently cropped the files out. We will correct it, thank you for pointing that out.

• Example Samples (AGNews):

• Probing samples: | Iteration | Query | Label | |:---------:|:-----------------------------------------------------------------------------------------:|:----------:| | 1 | The new iPhone 12 Pro Max is expected to have a larger battery life than its predecessor. | technology |