Hierarchical Demonstration Order Optimization for Many-shot In-Context Learning
Authors: Yinhan He
Wendy Zheng
Song Wang
Zaiyi Zheng
Yushun Dong
Yaochen Zhu
Jundong Li
Venue: NeurIPS 2025 poster ()
Keywords: in-context learning
demonstration order optimization
Primary area: applications
TL;DR: We propose an information-theoretical metric that helps determine the optimal order of demonstrations for in-context learning in large language models.

Abstract: In-Context Learning (ICL) is a technique where large language models (LLMs) leverage multiple demonstrations (i.e., examples) to perform tasks. With the recent expansion of LLM context windows, many-shot ICL (generally with more than 50 demonstrations) can lead to significant performance improvements on a variety of language tasks such as text classification and question answering. Nevertheless, ICL faces the issue of demonstration order instability (ICL-DOI), which means that performance varies significantly depending on the order of demonstrations. Moreover, ICL-DOI persists in many-shot ICL, validated by our thorough experimental investigation.
Current strategies for handling ICL-DOI are not applicable to many-shot ICL due to two critical challenges:  (1) Most existing methods assess demonstration order quality by first prompting the LLM, then using heuristic metrics based on the LLM's predictions. In the many-shot scenarios, these metrics without theoretical grounding become unreliable, where the LLMs struggle to effectively utilize information from long input contexts, making order distinctions less clear. The requirement to examine all orders for the large number of demonstrations is computationally infeasible due to the super-exponential complexity of the order space in many-shot ICL.  To tackle the first challenge, we design a demonstration order evaluation metric based on information theory for measuring order quality, which effectively quantifies the usable information gain of a given demonstration order. To address the second challenge, we propose a hierarchical demonstration order optimization method named \texttt{HIDO} that enables a more refined exploration of the order space, achieving high ICL performance without the need to evaluate all possible orders. 
Extensive experiments on multiple LLMs and real-world datasets demonstrate that our \texttt{HIDO} method consistently and efficiently outperforms other baselines. Our code project can be found at https://github.com/YinhanHe123/HIDO/.

Hierarchical Demonstration Order Optimization for Many-shot In-Context Learning
Yinhan He"
Wendy Zheng" University of Virginia Charlottesville, VA ncd9cf@virginia.. edu
Song Wang University of Central Florida Orlando, FL song wang@ucf.
University of Virginia Charlottesville, VA nee7ne@virginia.ed edu
Zaiyi Zheng University of Virginia Charlottesville, VA s ccffqvvrrginaa.cmmmmm edu
Yushun Dong Florida State University Tallahassee, FL yd24f0fsu.edd edu
Yaochen Zhu University of Virginia Charlottesvilll, VA ugp4gh@virginia. edu
Jundong Li University of Virginia Charlottesville, VA j j16gkvviginna.
Abstract
In-Context Learning (ICL) is a technique where large language models (LLMs) leverage multiple demonstrations (i.e., examples) to perform tasks. With the recent expansion of LLM context windows, many-shot ICL (generally with more than 50 demonstrations) can lead to significant performance improvements on a variety of language tasks such as text classification and question answering. Nevertheless, ICL faces the issue of demonstration order instability (ICL-DOI), which means that performance varies significantly depending on the order of demonstrations. Moreover, ICL-DOI persists many-shot ICL, validated by our thorough experimental investigation. Current strategies for handling ICL-DOI are not applicable many-shot ICI. due to two critical challenges: (1) Most existing methods assess demonstration order quality by first prompting the LLM, then using heuristic metrics based on the LLM's predictions. the many-shot scenarios, these metrics without theoretical grounding become unreliable, where the LLMs struggle to effectively utilize information from long input contexts, making order distinctions less clear. (2) The requirement to examine all orders for the large number demonstrations is computationally infeasible due to the super-exponential complexity of the order space in many-shot ICL. To tackle the first challenge, we design a demonstration order evaluation metric based on information theory for measuring order quality, which effectively quantifies the usable information gain of a given demonstration order. To address the second challenge, propose hierarchical demonstration order optimization method named HIDD that enables a more refined exploration of the order space, achieving high ICL performance without the need evaluate all possible orders. Extensive experiments on multiple LLMs and real-world datasets demonstrate that our HIDO method consistently and efficiently outperforms other baselines. Our code project can be found at https::///// //gp:::///htbbb../ com/ hwt.///anhnaeee////aaaa
These authors contributed equally to this work.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

LLM: LlaMa3
L.M: SciPhi
L.M:: Zephyr
0.90
0.70
0.8
Accuracy
Aceuracy
Accuracy
0.85
0.65
0.7
0.80
0.60
0.75
0.55
0.6
few
many
few
many
few
many
shot) (150 shot)
shot) (150 shot)
(10 shot) (150 shot)
Figure 1: Accuracy of many-shot ICL (150 shots) in green and few-shot ICL (10 shots) in blue dataset TREC. We randomly select demonstration orders and average the number of times the model predicts the correct answer for 256 queries. See more results in Appendix F33
Introduction
Large language models (LLMs) have demonstrated remarkable performance in few-shot In-Context Learning (ICL), where LLMs adapt to new tasks by incorporating demonstrations (examples) in
the input prompt without additional fine-tuming mueettnnng B g 47 Recent advances in research have vastly
expanded the context windows of LLMs, paving the way for many-shot ICL [1 [5 2 25]. This approach, typically involving more than 50 demonstrations, has achieved significant performance gains in various NLP tasks, including text classification (24] and question answering [16]. However, critical challenge
few-shot ICL demonstration order instability (ICL-DOI): the significant variance in ICL performance when the same set of demonstrations is arranged in different orders 21I. For instance, [2 claims that for a text classification task, different orders can cause performance to fluctuate dramatically, ranging from random guessing to 90% accuracy. Unfortunately. exploratory experiments (Fig. D show that the ICL-DOI phenomenon persists in many-shot ICL.
Several studies tackle the issue of ICL-DOI in few-shot scenarios. One thread of research design stabilization methods reduce ICL performance variance w.r.t. different demonstration orders 4 45
41 while others search for the optimal demonstration order that maximizes ICL performance 21
43
Although these proposed methods achieve satisfying performance under few-shot ICL, they cannot be easily adapted to many scenarios []] due to two fundamental challenges: (1) Lack of precise quality-measurin
19
metric: Current studies 21 21] assess order quality by examining LLM responses to sample queries with ordered demonstrations as context. These evaluations rely on heuristic properties like answer distribution diversity but suffer from subjective judgments. Additionally, LLMs exhibit primacy and recency bias, giving more attention to content at the beginning and end large context windows [1]] This creates a challenge in many-shot scenarios where numerous demonstrations in the middle cause only subtle performance differences, making difficult to compare different orders. (2) Infeasibility of evaluating all demonstration orders: Unlike few-shot ICL, it is infeasible to evaluate all demonstration orders in many-sho scenarios exhaustively. This is because, evaluating one demonstration order requires at least one LLM inference call, which is both costly and time consumin... Furthermore, the demonstration order space expands exper-exponentially (rd)) with the increase demonstration numbers.
In this paper, address the issue of ICL-DOI in many-shot ICL by searching for effective demon- stration order. Specifically, to tackle the first challenge, we introduce In-Context Demonstration Order V-information (ICD-OVI). This metric, grounded in information theory, measures how effectively an LLM, with a certain ordered demonstration as context, extracts usable information from query to infer its corresponding answer. To address the second challenge, we introduce a Hlerarchical Demonstration Order optimization (HIDO) framework that enables more refined exploration in the order space, thus achieving satisfactory performance without evaluating all possible orders.
We summarize our contributions follows: (1) Theoretically Justified Novel Metric: We introduce
a novel information-theene by the usable information extracted from a query, with the ordered demonstration as context, to infer its answer. (2) Fundamental Optimization Framework: Based our ICD-OVI demonstration order quality metric, we propose an efficient hierarchical demonstration order optimization framework termed HIDO for in-context learning with vast demonstration permutation spaces. (3) Extensive
metric, ICD-OVI, which evaluates the quality of a demonstration order

---

Empirical Evaluations: We conduct extensive experimental investigations on multiple LLMs and real-world datasets of various semantic scenarios, demonstrating the effectiveness and efficiency of our demonstration order optimization framework HIDO.
2 Preliminaries and Problem Definition
Notations. We denote a demonstration as == (q. a). where q is its query, and a is its answer. Throughout this work, follow existing literature [21] [3] by considering the query q multiple choice question and a as a single-token answer (c.g., "A," "B" or "C") indicating the choice. For example, in sentiment classification task, demonstration (q, a) might have query q "Please analyze the sentiment of this sentence: 'Jerry wins the game!' A. Positive; B. Negative" with corresponding answer transformation T that organizes the pair into a standard format: T(g. a) = "input: "q. "type: "a. Given that T; T (q;; a;) denotes the transformed text of the ith in-context demonstration, the demonstration set to be ordered is written as DD == {Tiji= where n is the number of demonstrations. Each demonstration is assumed i.i.d. samples drawn from an underlying input data distribution FF that we cannot directly access. We define т E S, as an order permutation function (S,, is the collection of all possible permutations), which maps the set {1...., n) bijectively to itself. We use [I) == T>(1) @ + T (n)) to represent concatenated demonstrations ordered by permutation т, where @ represents text concatenation. Finally, we denote (l9) as the LLM prediction (i.e., logits vector) when we prompt the LLM with query q.
"A." To transform (g, a) into text format for LLM input, we apply
Preliminaries. We first introduce the existing ICL demonstration order quality metrics, then provide the theoretical background for our proposed method. All existing metrics measure the demonstration order quality with important tool: set of probing samples D ((i,, az) ) (where m is the number of probing samples) generated by the same LLM that we perform ICL on. These probing samples mimic samples drawn from the inaccessible distribution F, thus providing insight into F.
The probing samples are generated two steps: (1) For a given order æ of demonstrations, we concatenate the demonstrations into (D) and prompt the LLM with this sequence to generate new samples that are similar to the demonstrations, which are called probing samples. (2) We repeat this process for all possible permutations of demonstration orders (I E S,). The complete set of probing samples D is then the collection of all samples generated across all permutations.
Existing Method 1: GlobalE. Given ordered demonstrations [I)),, GlobalE first calculates the frequency distribution of the LLM's predicted answers for queries in the probing samples with (D) as context: f 1 Σ; I[arg max (-IT(- @ 4.)]. Here, I[[- is the indicator function m that transforms an integer to its corresponding one-hot vector with length equal to the number of possible answers. GlobalE measures the diversity of answers by the distribution entropy Hx-f(X) Lu ct.al [2I] claim that answer diversity maintains high positive correlation with the accuracy of LLM predictions empirically. Therefore, demonstrations with higher GlobalE values are considered preferable.
Existing Method 2: LocalE. LocalE measures the average conditional entropy of an LLM's predic- tions (i.e., the logits vectors) when prompted with the ordered demonstrations and probing queries. It calculated as m Σ, (X (II),,, ).). Unlike GlobalE, which examines answer frequency distribution across all probing samples, LocalE focuses on the uncertainty in the model's predictions for individual samples. A higher LocalE value indicates that the LLM is less confident its pre- dictions, which helps prevent overconfidence and poor calibration. However, GlobalE and Local are heuristic metrics derived from empirical observations. They also do not utilize the answers from probing samples since they cannot verify the correctness of these answers.
Existing Method 3: PDO. Another metric is the probability distribution optimization (PDO) met- ric 43 This metric is designed based on the assumption that well-ordered in in-context examples should produce answer frequency distributions that match a prior distribution, which is believed to approximate the actual answer distribution. PDO measures demonstration quality by calculating the discrepancy between the answer frequency distribution produced by the LLM and the prior distribution, formally written as KI. ( Σ. P.. @ á:) (U)) In this formula, KL((-Il)) rep- resents the KI. divergence, and U is the hutenndetermined prior probability distribution (typically uniform distribution) over the answer space A. However, this approach has limitations because
3

---

the prior distribution of probing samples' answers may not accurately reflect the actual input data distribution. This discrepancy has led to debates about the effectiveness of the PDO metric.
Theoretical Foundation: V- usable information. Our design of ICL demonstration order metric
is inspired by information theory, specifically V-usable information 42 17.. widely recognized information-theorete metric measuring the amount of information an ML model f can capture from
input queries random variable (r.v.) Q to predict their corresponding answers v. A. Specifically, for a predictive family V (i.e., the set of a model's 's all possible parameter configurations), the V-usable information defined as Hy(A) (A(Q)) where
Hv(A Q) inf B(ne)==l- log2 f-14)).
JEV
Hy(A inf IE ((ga))>)-- logg f( [(-10]]
SEV
Here, F is the input data distribution, f(119) is the predicted answer distribution given query q, and f(110) represents the model's prediction without seeing the query (using only prior knowledge). (y(A))) and (A(0) measures the expected log-loss of the optimal predictor in the family V when it has access to the query and when it does not have access to the query, respectively. Therefore, this metric, Hy(A 0) (AlQ))) quantifies how much additional information about the answer the model can extract when it sees the query compared to when it does not. This metric has multiple advantages: (1) Interpretable: It measures information amount (in units of "bits") that model with predictive family V can capture from Q to predict A, which is easily human-comprehensiie (2) Computationally Viable: Although the data distribution F is not accessible, the usuulble information can be efficiently approximated by Monte Carlo with a theoretical precision guarantee 42] (3)
Empirically Effective: the metric is empirically proven with a high correlation with the correctness of the predicted answer [17] [4, (38). Note that the (-).) is similar in format compared with entropy H (+), however, existing work proves that using entropy (-) will lose the advantage (2) and (3) for
the V-usable information 42
38
Problem Definition. Here, we formulate the in-context learning demonstration order optimization task as finding the order that minimizes the distribution discrepancy between the LLM output and the original input. Specifically, we have the following definition:
Definition 1. For a demonstration data distribution F, where each data sample is in the shape of (query, answer), given n demonstrations i.i.d. drawn from F, denoted as D. we aim find the demonstration order it of the n demonstrations such that the answer prediction distribution produced by LLM approximates F (measured by " "KL divergence (5)"), i.e.
min (PPMMM((III + (+)))
3 In-Context Demonstration Order V-usable Information
Before introducing our proposed HIDO framework, we first present novel evaluation metric called In-Context Demonstration Order U-Uslele Information (ICD-OVI). Unlike existing heuristic metrics such as GlobalE (21). LocalE 21.. and PDO 443. our ICD-OVI is grounded in information theory and measures how effectively an LLM extracts useful information from queries to predict their answers when given a specific demonstration order. Previous metrics rely primarily on empirical observations and often lack theoretical justification, making them less reliable for many-shot ICL scenarios. In these scenarios, similar demonstration orders produce only subtle differences in LLM performance, resulting in very similar metric values that make it difficult to distinguish quality between different orders. Our approach addresses this limitation by providing a citommation-thoreee metric that quantifies exactly how much demonstration order helps the LLM learn from inputs.
3.1 Intuition and Definition
The key intuition behind ICD-OVI is simple: the optimal demonstration order should help the LLMs extract maximum information from queries to produce correct answers. Our metric quantifies this information extraction capability. ICD-OVI measures the usable information that an I.I. can capture from ordered demonstrations (TD). First, we follow the theory of yuusable information and define the predictive family corresponding the ordered demonstrations as
Vn == (PuMM(|II @ gg]g e Q=} U (PLLM(119)19 e 2z}.
(3)
4

---

This represents all possible LLM configurations achievable with the given ordered demonstrations as context. Here, 2,= is the of all possible queries from the data distribution, and the second term of is included to ensure Vn satisfies the technical requirements of valid predictive family [42]. With the predictive family Vn, we follow the theory of V- -ssablle information derive the in-context demonstration order V-usable information, i.e., ICD-OVI, as (see full derivation in Appendix D):
ICD-OVI- = ((q.a)~-[1oog, (I @ q) log2 PlzM(a/I((A) @ 0)],
where II(AA) is the concatenation of all answers in the order of т. Equ. [ captures the difference between the model's ability (1) to predict answers when seeing both the ordered demonstrations and the query (first term); and (2) to predict answers without seeing any queries (second term). Essentially, this equation quantifies the expected information the LLMs can capture from a query for prediction with the ordered demonstrations as context.
3.2 Practical Implementation
Since cannot directly access the data distribution F, approximate ICD-OVI using probing samples D generated by the LLM. They effectively mimic samples that are drawn from F. Formally,
ICD-OVIS RJ
loga PliM(a([I((D) @ q:) - logg PaLM( ITAA) @ 0)]
(S)
However, this approximation involves LLM-generated labels (a) from probing samples, which may be incorrect and introduce bias. To address this, use technique from V-usable information theory called the point-wise V-usable information threshold (PVI threshold, denoted as T).
Denoting (g.a) as the probability subtraction in Equ. 5 for single probing sample, the PVI threshold helps us determine if the label of probing sample (ÿ. â) is reliable: (1) (V) 2 T, the label à is highly likely correct; (2) If PVI(g.)) т, the label à is possibly incorrect. Prior work [9 20 show empirically that this threshold effectively separates correct from incorrect labels across various datasets and LLMs. Hence, when calculating ICD-OVI with Equ. 5 we keep the original term for probing samples with reliable labels â. For unreliable labels, we replace the term single, potentially incorrect answer. we call the above computation procedure for a probing sample as point-wise ICD-OVI (PICD-OVI), our ICD-OVI is the average of PICD-OVIs across all probing samples.
with its expectation over all possible labels to avoid relying
3.3 Theoretical Properties
The ICD-OVI enjoys properties summarized in the following theorem (see proof in Appendix Theorem 1. Given LLM and demonstrations D drawn from data distribution F, for any two ordered demonstrations II, (D) and (D). under mild conditions, if ICD-OVI(II,D)) > ICD-OVI(II2(D)) then the LLM achieves better performance with IT (D) as context than with (D) when predicting answers for queries drawn from F.
This theorem establishes that our metric correctly identifies better-performing demonstration orders, providing theoretical justification for its use in optimizing ICL performance. Our ICD-OVI is the first innommtiiontthoreee metric for evaluating ICL demonstration orders, and inherits the beneficial properties of V-usable information theory. We conduct extensive experiments in Section to demonstrate the effectiveness of the ICD-OVI metrics.
Remark. Although each probing sample (q. â) seems to require two separate LLM inference calls (one for IID) @ q and another for II(AA) @ (), we optimize this process. For given demonstration order, the term Pi probing samples. This optimization ensures that ICD-OVI's computational complexity remains comparable to traditional heuristic metrics despite its theoretical advantages.
@ 0) only needs to be computed once and can be reused across all
4 Methodology
Our HIDO, shown F first clusters the embeddings of the input demonstration texts and then performs & iterations of hierarchical order optimizations. In each iteration, the process first determines
5

---

Many prompt 22
LLM emb. space
Inter-cluster Order Optimization
Q: When was the pe invented? A: NUM
Q Whene ThE arn Wall Al
Last Intra Orders
All Seher. Orders
Q. What the baiking poie? NUM
Q: What is the copital of Itoly? A: LOC
Q. What Japen's carrrro ENTY
Q: Where the Biffel Tower? A: LOC
Q: Who invented the telephone? HUM
*
Q: Whet platulytiusct at BESC
EEG OVE
refive
Where Wall
Zopuris wery?
Q: Who discovered penicilin? A: HUM
What the boiling point? NUM
Intra-cluster Order Optimization
Where the Great Well? LOC
Random Initialize an Order
Shuffled Orders
Iotre,
Ster.
Opt. Inter, Order
What Canada's copitel? LOCOC
pe invented?
L.
Q: What photosynthesis? BESC
2. Q What the copital of Italy? A: LOC
repestedly shufffi 50%
TCD--OV
3 Q Where is the Eiffel Tower? LOC
Q: What Japan's currency? A: ENTY
#. Q: What is Jopon's currency? A: ENTY
What Sppan' our memoooo EVIr
cppied They
Q: How tall Mount Everest?
m. q What sphotcowethessc DESC
What i plonsarmhess BEsc
Figure 2: Overview of our proposed HIDO framework.
the near-optimal order within each demonstration cluster. Then, while maintaining these intra-cluster orders, it searches for the most effective order of the clusters themselves. This alternating focus on intra- and inter-cluster optimization may be iterated multiple rounds during which the probing samples are imporved (see detailed rationale in Section 4.4) to achieve more accurate assessment of the demonstration order quality using ICD-OVI.
4.1 Demonstration Clustering
Clustering demonstrations dramatically reduce the permutation space, allowing for more efficient search of the optimal order. Additionally, as the demonstrations within the same cluster are ap- proximate in embedding space, varying demonstration orders cause less ICL performance variance. Thus, we apply K-means algorithm 23 to the text embeddings of the demonstrations. These text embeddings are generated using the text embeddings API from [28]. We limit the number of clusters to be small (typically no more than four), as a larger number would cause a combinatorial explosion during HIDO's inter-cluster order optimization stage, where all possible orders are evaluated.
4.2 Intra-cluster Order Optimization
In Section 4.1 we restrict the cluster number to be small, which implies that demonstrations within one cluster, despite sharing similar LLM embeddings, can be large in quantity (c.g.. 30 intra- cluster samples). Nevertheless, the intra-cluster demonstrations share proximate embeddings, which significantly decreases ICL performance variance when demonstration orders vary. This allows a less thorough order search while still achieving satisfactory precision. Hence, we design intra-cluster demonstration order exploration strategy as follows (see the lower right hand side of Fig. 2 we first randomly generate a demonstration order, then in each iteration, we explore its "neighborhood" by randomly flipping 10% of its positions, which ensures variation between selected orders while constraining exploration within radius of the original order, as measured by rank correlations (I3)
Theorem 2. Randomly flipping K entries from a sequence of length N keeps the rank correlation within a range characterized by the lower bound 1 - 6 E (a: ax)1-=) (N2 -1) 1) and upper bound The upper bound achieved with extremely low probubility of K! when the perturbed
sequence is identical to the original sequence. (see proof in Appendix E
We evaluate each candidate intra-cluster order's quality using the ICD-OVI metric with a probing set generated by the examined LLM. We generate the probing samples with input demonstrations as context in three steps: We start with the top k (a predefined hyperparameter) effective intra-cluster orders for the target cluster from the previous optimization iteration. For each of these i intra-cluster order, we expand them to i distinct orders for the entire set of the demonstrations by combining: (i) The optimal inter-cluster order from the previous iteration (fixed); (ii) The optimal intra-cluster orders for all other clusters from the previous iteration (fixed); (iii) The current candidate intra-cluster order for the larget cluster being optimized. The & distinct ordered demonstrations differ only in the order of demonstrations within the target cluster. We prompt the L.LM with each ordered demonstrations to generate i different probing sample sets. All probing samples collectively serve the probing sample

---

Table Metadata of the LLMs tested. "Lan. models", "Con. window" indicates the language models, and context window size.
Lan. models
GPT-3.5T
GPT4oM
SciPhi
Zephyr 32,768
LlaMa3 1,048,576
Con. window
16,385
128,000
32,768
Max output
4,096
16,384
n/a 7B
n/a
n/a
Model size
175B
n/a
7B
set to evaluate the candidate intra-cluster order using the ICD-OVI metric. By using probing samples derived from previous top-performing orders, we achieve more robust candidate order evaluation.
4.3 Inter-cluster Order Optimization
Having obtained the near-optimal demonstration orders within each cluster, we now find the optimal order of the clusters themselves. As we have limited the number of clusters (typically no more than four), it becomes feasible evaluate all possible cluster orders, as illustrated upper right hand side of the Fig. 2 Similar to the intra-cluster optimization process, we generate probing set to evaluate each possible inter-cluster order with ICD-OVI metric. However, in this case, we employ all possible inter-cluster orders, while fixing the optimal intra-cluster demonstration orders obtained from the previous iteration. Specifically, we first consider all possible permutations of cluster orders, then prompt the LLM with this complete set of ordered demonstrations (combining the inter-cluster order being evaluated and the fixed optimal intra-cluster orders) to generate a probing set. This approach allows us to comprehensively assess different cluster arrangements while leveraging the optimized intra-cluster orders, potentially leading to a globally optimized demonstration order.
4.4 Dynamic Update of the Score Function
We perform multiple rounds of intra- and inter-cluster optimization, during which the score function (ICD-OVI) is refined through updated probing sets (see the upper and lower right hand side of Fig, 2 higher-quality probing set reduces distribution discrepancy between probing and input data samples, enabling more precise ICD-OVI estimation. This further improves accuracy in identifying effective demonstration orders for answer prediction.
The procedure is separately introduced in the Section 4.2 and Section 4.3 therefore, we briefly conclude it as follows. In each iteration in-context demonstration order optimization, we cache the top & intra-cluster demonstration orders for all clusters. For intra-cluster optimization in the subsequent iteration, we apply the cached top intra-cluster demonstration orders for the cluster being optimized, while maintaining the optimal intra-cluster orders from the previous iteration for all other clusters. We combine these with the optimal inter-cluster order from the previous iteration to generate new probing sets. For inter-cluster optimization, we consider all possible cluster arrangements. For each arrangement, we apply the optimal intra-cluster demonstration orders obtained from the previous iteration to generate probing sets for evaluating each inter-cluster arrangement. By iteratively refining our probing sets for both intra-cluster and inter-cluster optimizations, we improve the evaluation accuracy progressively, leading to optimized orders over time.
Experiments
first introduce our experimental setup. Then, we answer the following research questions about proposed hierachical demonstration order optimization method HIDD via extensive experiments: RQ1: How does HIDO perform compared to existing demonstration order optimization methods across different datasets and language models? RQ2: What is the impact of each key component in HIDD on its overall performance? RQ3: How sensitive is HIDO to its main hyperparameters such as the number of clusters and the maximum number of optimization iterations?
5.1 Experiment Setup
Here, we introduce the various settings for our experimental evaluation.
7

---

Table 2: Performance of HIDO vs. baselines across datasets (best results in bold).
AGNews
CB
CR
DBPedia
MPQA
MR
RTE
SST-5
TREC
GlobalF 87.24 46.43
93.36
95.70 90.76
93.62
81.90 om 54.56
77.47
LocalE 89.06 a. 46.43 + cas 93.10 = an 95.83 + un 89.97 + 93.49 = 80.86 + c 52.60 = a 78.65 # am
GPT-3.5T
PDO 89.32 48.21
93.23
96.22 89.97
93.62
80.60 + 53.65 + 76.69
HIDO 89,45 a. 51.19 + 94.27 = ..2 97.92 91.02 - 6: 94.27 = mu 81.90 - 54.95 = 82.29 =
GlobalE
83.07
55.95
93.36
92.19.......
87.50
92.71
85.16
53.39
83.33
LocalE
84.77 + 55.95 + 93.36 = am 92. 86.33
1.. 92.32
2:2 85.55 129 53.26 + 84,11 +
GPT-4oM
PDO 85.03 55.36
92.84
92..9....9..
81.64
92.84
85,42
1/0 52. 86
84.51
HIDO
85.81 + am 56.55 +: 1.0 93.36 + PM 92.84 m 86.85 + 93.23 + a. 86.33 use 56.64 #: 86.59
GlobalE
85.29 us 92.26 + 91.67
96.09
83.59
93.88
83.72
54.69 + 76.17
LocalF.
86.59 am 92.26 4: mm 92.32 + ... 96.22 ws: 85.16 + 93.88 # am 83.98 a. 55.08 # 76.69 1
SciPhi
PDO
86.07 + 92.26
91.02
96.09
84.77
94.01
83.72
54.69 #: 76.17
HIDO
86.98 a. 90.48 + 1. 92.71 .... 96.88 ... 87.50 + cM 94.27 = .. 85.94 cm 57.16 = 80.47 0.7
GlobalF:
89.71 a 77.38 + 93.23
94.66
86.07
94.40
82
50.00 + 84.38
LocalE
88.15 am 73.21 4: cm 93.10 + 1. 96.22 cm 86.98 + 94.66 + am 82.55 ca 48.18 # 81,90
Zephyr
PDO
88.80 + 77.38 + 93.23 3 94.66
86.07 + 93. 10 am 81.51
50.00 + 84.38
HIDO 89.32 = cm 78.57 + 1.9 94.01 = .. 97.27 w.. 87.76 ... 94.79
a. 82.55 137 50.78 = :m 86.46 1.4
GlobalE
80.34 = 94.64 + 85.94 93.49
58.20
92.84
82.42
39.19 = 72.92
LocalE:
83.72 u.3 91.67 + 1m 85.68 = mm 93.23 A. 54.82 + 1a. 90.49 = am 82.81 1.0 40.36 = a. 73.18 cm
LlaMa3
PDO
77.73 = 94.64 + 85.16 93.49
52.21 + 91.02
82.94
39.19 = 72.92
HIDO
86.20 2. 94.64 + 1.0 87.24 2.0 94.27 1.30 63.80 + 1.- 93.49 a. 83.07 cos 40.62 = mm 77.34 am
Baselines: (1) GlobalE: Randomly select 24 orders and measure the entropy of the frequency distribution of the prediction labels probing datasets (21 (2) LocalE: Analogously to [21],
randomly select 24 demonstration orders and calculate the average entropy of their predicted logits given by LLM. (3) Probability Distribution Ordering (PDO) 43 Calculates the score function of a demonstration order as the KL divergence between the frequency distribution of the prediction labels generated by the LLM on probing datasets and the uniform distribution as the prior distribution.
Datasets: We adopt nine text classification datasets: AG's News Corpus (AGNews) 46
| Commit-
mentBank (CB) (7), Customer Review (CR) (11). DBPedia Ontology Classification (DBPedia) [46), Multi persp-PPrrseective Question Answering (MPQA) [39,, Movie Review (MR) [30, Recognizing Textual Entailment (RTE) (6). Stanford Sentiment Treebank-5 (SST-5) (34] and Text REtrieval Conference Question Classification (TREC) 377 They cover various semantic scenarios, including sentiment classification and textual emtailment. We sub-sample 256 instances from each dataset due budget constraints.
Large Language Models: We adopt 19" [27] from OpenAI, SScPPhi-Mistral-7BB22222 [33], "Zephyr-7b-beta" [36] and "LlaMa-3-8B- 1048k" [32] from HuggingFace. We select those OpenAl models due to their affordability and the HuggingFace models due to their large context windows.
[26] and H-PT-44o-ini-2024--2
5.2 Effectiveness of HIDO
In this section, aim to answer RQ1. In Table we measure the accuracy of the output demon- stration orders produced by HIDO and the baselines on various datasets and LLMs. We observe that HIDO achieves the highest prediction accuracy in most settings, proving the effectiveness of our framework. Notably, our method can achieve significant performance leads in GPT-3.5T on CB (51.19) (51.19)) GPT-4oM on SST-5 (56.64%), SeiPhi on TREC (80.47%), and LlaMa3 on MPQA (63.80%). Additionally, we make the following observations from Table (1) Model-agnostic: HIDO achieves the best performance on both large and small LLMs, implying that our framework is model agnostic; it can be used on different models and find relatively high-performing orders.
8

---

HIDO Variant
HIDO Original
MPQA
TREC
87
+6.5%
+1.7%
+3.8%
+3.3%
86
Accuracy (%)
85
Accuracy (%)
84
80
80
83
75
75
82
81
70
70
80
NC
ND
Ninter
NIntra
# of Clusters
Max Iterations
(a) HTDO vs. variants using Zephyr Trec.
(b) Parameter analysis of HIDO using Sciphi on Trec.
Figure Combined results ablation study and parameter analysis.
(2) Low variance: In general, HIDO has a smaller variation performance on most dataset model combinations in contrast to that of the baselines, especially in GPT-3.5T on CB (2. (2.73%), GPT-4oM on DBPedia (0.81 %), and SciPhi on TREC (0.78%). This indicates that HIDO can consistently find the order that gives the best performance. (3) Runner-up on non-optimal datasets: In those cases that HIDO does not perform the best, the results are still comparable to best-performing baseline.
5.3 Ablation Study
We address RQ2 by examining four variants of our HIDO: (1) HIDO-NC: tests the utility of clustering by randomly assigning samples to clusters. We maintain the same number of clusters and demon- strations per cluster in the original model. (2) HIDO-NIntra: randomly selects demonstration orders within clusters while keeping all other components the same. (3) HIDO-NInter randomly
selects inter-cluster order after intra-cluster optimization as the optimal inter-cluster order. (4) HIDO-ND: removes the dynamic update scheme for the score function. It outputs the best demon- stration order after iteration. From Fig. (a). observe that removing each component causes performance degradation. Specifically, we have the following observations: (1) HIDO-NC has the largest difference, indicating that grouping the samples based on distance allows HIDO to find the best order while maintaining efficiency. (2) HIDO-ND has relatively small increase, which implies that HIDO is able to find the best order within small number optimization iterations. (3) HIDO-NInter and HIDO-NIntra have similar impacts on the performance. This highlights the significance of our method in finding the best order. See more results Appendix F22
5.4 Parameter Sensitivity
Here, we address RQ3. Although our model has numerous hyperparameters, we focus our analysis on two we consider most significant: the number of clusters and the maximum number optimization iterations 7. Fig- (b) illustrates our model's performance with varying k and / on the TREC and MPQA datasets using the Sciphi model. We observe that performance improves as increases, indicating that more iterations of HIDO tend to produce netter-performing demonstration orders. Regarding the number of clusters, we find that performance peaks at k: for MPQA and i 3 for TREC. This suggests that different datasets require specific cluster numbers for best performance.
6 Related Work
Many-Shot In-Context Learning. With the expanded context window of developed LLMs, the models can process larger number of demonstrations within single prompt. resulting in further research observing the effect of large number of demonstrations (i.e. more than 50) on ICL 12
2,25). 15] develop a long-range language model EVALM that achieves higher accuracy when using many shot ICL; however, the model cannot maintain the same performance consistently, indicating that ICL-DOI still exists. Some emprirical results from ①1 provides early evidence for many-shot demonstration order sensitivity by showing how one order that gives the best performance on one subset of dataset can perform poorly on different subset of the same original dataset.

---

Optimization Techniques for Vast Permutation Spaces. Finding optimal orderings in large permu- tation spaces is not unique to ICL. This problem has been studied in various domains. Traditional approaches like simulated annealing [14] and genetic algorithms 35 are applied to similar combina- torial optimization problems. However, these methods often struggle with the scale of permutations encountered in ICL scenarios. Recent work in combinatorial optimization introduces hierarchical
and decomposition- bbasd approaches to tackle large-scale permutation problems [TO] [22 29]. For in-
stance, [29] proposes hierarchical optimization framework for solving large-scale traveling salesman problems, demonstrating the effectiveness of dividing the problem into manageable sub-problems. Enlightened by those ideas, tackle specific challenges of ICL demonstration ordering.
7
Conclusion
We take the initial step on demonstration order instability in many-shot in-context learning. We first propose score function, ICD-OVI, with solid information theoretical foundation for evaluating demonstration orders. We subsequently design efficient hicrarchical optimization framework HIDO that navigates the vast permutation space while maintaining computational fcasibility. Extensive experiments verify that HIDO achieves significant performance gains across diverse tasks. Our fformationn-heoretee approach provides both theoretical guarantees and practical benefits, opening new avenues for unleashing ICL performance.
8 Acknowledgments
This work is supported in part by the National Science Foundation (NSF) under grants IIS-2006844, NS-224 222-22,,,,, 113-2331315, CNS-2154962, BCS-2228534, and CMMI-2411244 the Office of Naval Research (ONR) under grant N000142412636, and the Commonwealth Cyber Initiative (CCT) under grant VV-1Q25-004.
References
[1] R. Agarwal, A. Singh, L. Zhang, B. Bohnet, L. Rosias, S. Chan, B. Zhang, A. Anand, Z. Abbas,
A. Nova, et al. Many-shot in-context learning. NeurIPS, 2024.
[2] A. Bertsch, M. Ivgi, U. Alon, J. Berant, M. Gormley, and G. Neubig. In-context learning with long-context models: An in-depth exploration. arXiv, 2024.
[3] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, Shyam,
G. Sastry, A. Askell, et al. Language models are few-shot learners. NeurlPS, 2020.
[4] L. Chen, H. Wang, Y. Deng, W.C. C. Kwan, Z. Wang, and K.-F. Wong. Towards robust personalized dialogue generation via order-insensitive representation regularization. In Findings of ACL, 2023.
[5] Csiszár. I-divergence geometry of probability distributions and minimization problems. Ann. Probab., 1975.
[6] I. Dagan, O. Glickman, and B. Magnini. The pascal recognising textual entailment challenge. In Machine learning challenges workshop, 2005.
[7] M.-C. De Marneffe, M. Simons, and J. Tonhauser. The commitmentbank: Investigating projection naturally occurring discourse. In proceedings of Sinn und Bedeutung, 2019.
[8] Q Dong, L. Li, D. Dai, C. Zheng, J. Ma, R. Li, H. Xia, J. Xu, Z. Wu, B. Chang, et al. A survey on in-context learning. In EMNLP, 2024.
[9] K. Ethayarajh, Y. Choi, and S. Swayamdipta. Understanding dataset difficulty with v-usable information. In JCML, 2022.
[10] S. T. Goh, Bo, S. Gopalakrishnan, and Lau. Techniques to enhance a qubo solver for permutation-bai based combinatorial optimization. In GECCO, 2022.
10

---

[11] M. Hu and B. Liu. Mining and summarizing customer reviews. In SIGKDD, 2004.
[12] Y. Jiang, J. A. Irvin, J. H. Wang. M. A. Chaudhry, J. H. Chen, and A. Y. Ng. Many-shot in- context learning in multimodal foundation models. In JCML Workshop on In- In-Context Learning, 2024.
[13] M. G. Kendall. Rank correlation methods. 1948.
[14] S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi. Optimization by simulated annealing. science, 1983.
[15] M. Li, S. Gong, Feng, Y. Xu, Zhang, 7. Wu, and L., Kong. In-context learning with many demonstration examples. arXiv, 2023.
[16] T. Li, X. Ma, A. Zhuang, Y. Gu, Y. Su, and W. Chen. Few-shot in-context learning knowledge base question answering. In ACL, 2023.
[17] Y. T. Lin, A. Papangelis, S. Kim, S. Lee, D. Hazarika, M. Namazifar, D. Jin, Y. Liu, and D. Hakkani-Tun Selective in-context data augmentation for intent detection using pointwise v-information. In EACL, 2023.
[18] N. Liu, K. Lin, Hewitt, A. Paranjape, M. Bevilacqua, Petroni, and P. Liang. Lost in the middle: How language models use long contexts. TACL, 2024.
[19] Y. Liu, J. Liu, X. Shi, Q. Cheng, and W. Lu. Let's learn step by step: Enhancing in-context learning ability with curriculum learning. arXiv, 2024.
[20] S. Lu, S. Chen, Y. Li, D. Bitterman, G. K. Savova, and I. Gurevych. Measuring pointwise v-usable information mn-ontext-ly. In Findings of EMNLP, 2023.
[21] Y. Lu, M. Bartolo, A. Moore, S. Riedel, and P. Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In ACL. 2022.
[22] Luo, X. Lin, Liu, Q Zhang, and Z. Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. NeurlPS, 2023.
[23] J. B. McQueen. Some methods of classification and analysis of multivariate observations. In Proc. of 5th Berkeley Symposium on Math. Stat. and Prob., 1967.
[24] S. Min, M. Lewis, L. Zettlemoyer, and H. Hajishirzi. Metaicl: Learning to learn in context. In NAACI, 2022.
[25] S. Moayedpour, A. Corrochano-Navaroo F. Sahneh, S. Noroozizadeh, A. Koetter, J. Vymetal, L. Kogler-Anele, P. Mas, Y. Jangjou, S. Li, al. Many-shot in-context learning for molecular inverse design. arXiv, 2024.
[26] OpenAl. Gpt-3.5-turb--0225 https://openai. com com
2024. Available at httpps://ppnai
[27] OpenAL. Gpt-4o-mini-2024--7--999 https://openall com 2024. Available at https:// apenai.com
[28] OpenAL. New embedding models and API updates. 2024.
https://openai.com cot.maii..omiiieex.
new-embedaing-modellss www.dd--addd----ueeaeaa-aa apgd-api-uun
[29] X. Pan, Y. Jin, Y. Ding, M. Feng, L.. Zhao, I.. Song, and Bian. H-tsp: Hierarchically solving the large-scale traveling salesman problem. In AAAI, 2023.
[30] B. Pang and I.. Lee. Seeing stars: exploiting class relationships for sentiment categorization with respect to rating scales. In ACI., 2005.
[31] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L.. Antiga, et al. Pytoreh: An imperative style, high-performance deep learning library. NeurIPS, 2019.
11

---

[32] L. Pekelis, M. Feil, F. Moret, M. Huang, and T. Peng. Llama 3 gradient: A series of long context models, 2024.
[33] SciPhi. Sciphi-mistral-7D-32k, https://hugginggacee 2024. Available at https:// huggingface.co
[34] R. Socher, A. Perelygin, J. Wu, J. Chuang, C. D. Manning, A. Y. Ng and C. Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In EMNLP, 2013.
[35] M. Tomassini. A survey of genetic algorithms. Annu. Rev. Comput. Phys. II1, 1995.
[36] L. Tunstall, E. E. Beeching, N. Lambert, N. Rajani, K. Rasul, Y. Belkada, S. Huang,
L. Von Werra, Fourrier, N. Habib, et al. Zephyr: Direct distillation of Im alignment. In COLM.
[37] E. M. Voorhees and D. M. Tice. Building a question answering test collection. In SIGIR, 2000.
[38] Z. Wang, C. Li, Z. Yang, Q. Liu, Y. Hao, X. Chen, D. Chu, and D. Sui. Analyzing chain- of-thought prompting in black-box large language models via estimated v-information. In LREC-COLING 2024.
[39] Wiebe, T. Wilson, and C. Cardie. Annotating expressions of opinions and emotions in language. Lang. Resour. Eval., 2005.
[40] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, al. Transformers: State-of-ther thrtt-rrrrtttt natural language processing. In EMNLP, 2020.
[41] Y. Xiang, H. Yan, L. Gui, and Y. He. Addressing order sensitivity of in-context demonstration examples causal language models. Findings of ACL, 2024.
[42] Y. Xu, S. Zhao, Song, R. Stewart, and S. Ermon. theory of usable information under computational constraints. In ICLR, 2020.
[43] Z. Xu, D. Cohen, B. Wang, and V. Srikumar. In-context example ordering guided by label distributions. In Findings of NAACL, 2024.
[44] W. Yang, W. Tan, H. Zhang, and B. Yan. Maximizing v-information for pre-training superior foundation models. arXiv, 2024.
[45] K. Zhang, A. Lv, Y. Chen, H. Ha, T. Xu, and R. Yan. Batch-icl: Effective, efficient, and order-agnostic in-context learning. In Findings of ACL, 2024.
[46] X. Zhang, J. Zhao, and Y. LeCun. Character-level convolutinaa networks for text classification. NeurlPS, 2015.
[47] W. X. Zhao, K. Zhou, J. Li, T. Tang. X. Wang. Y. Hou, Y. Min, B. Zhang, J. Zhang, Z. Dong, al. A survey of large language models, arXiv, 2023.
12

---

NeurIPS Paper Checklist
Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:[Yes)
Justification: The abstract and introduction accurately describe the paper's contributions: (1) introducing
information-theorrticc metric (ICD-OVI) for evaluating demonstra- tion order quality, and (2) developing a hierarchical optimization framework (HIDO) for many-shot in-context learning. These claims supported by the theoretical analysis and experimental results presented in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
The paper includes a dedicated "LLimitations" section that acknowledges key limitations including: clustering complexity, computational costs of the dynamic update mechanism, instability factors LLMs that may affect results, and potential noise in probing set generation.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
13

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes].
Justification: The paper provides complete theoretical proofs in Appendix for the main theoretical results, including Theorem 1 (relationship between ICD-OVI and demonstration order performance) and Theorem 2 (rank correlation bounds when randomly flipping entries). All assumptions are clearly stated before each theorem.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes].
Justification: The paper provides detailed methodology in Section 4, along with experi- mental settings in Section 5.1 that specify datasets, models, metries, and baselines. The hyperparameters and implementation details are provided, and the code will is released at the specified repository link in abstract.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
14

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes].
Justification: The paper states that code will be made available at the specified GitHub repository link: "htips:/anonnymous. httpr//ooouuoooo.ciiceneceeee www.sscccccc//HiD-BDDDEEE The datasets used are all publicly available standard benchmarks in the field (AGNews, CB, CR, etc.).
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /nips.ccc/pullc//guui
Cooe/ubmeeeeeeeee setibbmmmssiinnii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes].
Justification: Section 5.1 provides details the experimental setup, including datasets used, models evaluated, and baselines. Section 5.3 and Figure discuss parameter sensitivity analysis. The methods section (Section 4) describes how the hyperparameters are set and how they affect performance.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]..
15

---

Justification: Table reports the standard deviation (variance) along with the mean for all experimental results. The ablation studies (Figure also include performance differences to show the significance of each component's 8 contribution to the overall approach.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes].
Justification: While the paper mentions the models used (including their parameters and context window sizes in Table 1), it does not provide specific details about the computational resources required for experiments, such as GPU types, memory requirements, or execution times.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes].
Justification: The research complies with the NeurlPS Code of Ethics. It uses publicly available datasets and models, does not involve human subjects, does not promote harmful applications, and discusses broader impacts in Appendix.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
16

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes].
Justification: The paper includes a "Broader Impact" section in the Appendix that discusses both positive impacts (enhancing Al applications in education, healthcare, and research) and potential negative impacts (reinforcing biases, increasing compute requirements, and widening capability gaps).
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deg.lymemmm of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA].
Justification: The paper does not introduce high-risk models or datasets that would require safeguards. It presents optimization method for existing models rather than releasing new models or datasets that could be misused.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
17

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes).
Justification: While the paper cites the sources of datasets and models used, does not explicitly mention the licenses or terms of use for these assets. The paper should include this information for completeness.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes].
Justification: The code provided at the repository link, and the method itself is thoroughly documented the paper. The ICD-OVI metric and HIDO framework are described in detail with algorithms and implementation specifies.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots. if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification: The research does not involve crowdsourcing human subjects. All experi- ments are computational and use existing datasets and models.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
18

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA].
Justification: The research does involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [Yes].
The paper clearly describes the use of LLMs (GPT-3.5- GPT-4o- Mini, SciPhi- Mistral,, Zephyr. and LlaMa-3) as they are integral to the research. Table lists all models with their details, and Section 5.1 explains how they were used in experiments.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy pattps://neurbe http//uuris..cco/oofeeeeeeeeeeee /tt.:/onferenccee2255//////////e for what should or should be described.
19

---

Appendix
A Limitations
In this work, several limitations exist that should be acknowledged for balanced understanding of the results and methodology. First, while the Hierarchical Demonstration Order Optimization (HIDO) framework effectively reduces the search space for many-shot in-context learning (ICL), its reliance on clustering introduces an additional layer of complexity that may not always generalize well to all datasets or language models. The clustering process itself, especially with a limited number of clusters, may not capture intricate interdependencies between demonstrations. Furthermore, although the dynamic update mechanism improves the accuracy of the score function, also increases the overall computational cost, particularly when applied to very large datasets or when running a high number of optimization iterations.
Additionally, the current framework assumes that performance improvements arise primarily from the optimized demonstration order, but factors such as the inherent instability of large language models (LLMs) across varying contexts might also contribute to observed fluctuations. Finally, the probing set generation step introduces potential noise, and while the system attempts mitigate this through iterative updates, inaccuracies in probing may still affect the final demonstration order selection.
B Broader Impact
This work on Hierarchical Demonstration Order Optimization (HIDO) for many-shot in-context learning has significant potential societal implications. Positively, by improving the performance and reliability of large language models across diverse domains, HIDO could enhance Al applica- tions in education, healthcare, and scientific research, making these systems effective for users without extensive prompt engineering expertise. However, potential negative impacts include reinforcing existing biases training data through optimized demonstration orders, increasing compute requirements for determining optimal orderings (raising environmental and resource accessibility concerns), and potentially widening capability gaps between organizations with resources to implement such optimization techniques and those without. As many-shot in-context learning becomes more widely deployed, careful consideration should be given monitoring how optimization techniques like HIDO affect faimess, bias, and resource distribution in Al systems.
accessible and
C Licenses for existing assets
Datasets:
AGNews publicly available for research use.
CB released under MIT License.
CR
publicly available for research use.
DBPedia
46
available under Creative Commons Semibution-ShareAlle License.
MPQA
39
available under GNU General Public License.
MR
30
publicly available for research use.
RTE
publicly available for research use.
SST-5
released under Stanford CoreNLP License.
TREC
37
released under Creative Commons Attribution 4.0 license.
Models:
GPT-3.5-Turbo and GPT-4o-Mini
26
used under the OpenAl API Terms of Use.
SciPhi-Mistral-7B-333 33 released under Apache 2.0 License.
Zephyr-7b-beta [36]: Cite Huggingface [14], released under MIT License.
1048k 332 released under Llama 3 Community License.
20

---

We have added this license information in Section 5.1 and ensured proper attribution throughout the paper. All assets are used in accordance with their respective licenses and terms of use.
D Complete Development of ICD-OVI Metric
Enlightened by V-usable information, our ICD-OVI, measures the usable information that LLM can capture from ordered demonstrations [I)... First, we define the predictive family corresponding to the ordered demonstrations (I) as
Vu ( (D) @ g)la E @r} (Pusa--aalle E 2r),
(6)
where 2p represents the set of all possible queries in the sample space of input demonstrations' data distribution P. and (Paa gg 2p} is added to satisfy the optimal ignorance requirement for predictive family [42]. Then, ICD-OVI, the information that the model can capture from [T),, can be defined as the expected information the model with predictive family Vn can capture from query random variable (r.v.) Q for predicting label r.v. A, i.c.
ICD-OVI = vn (A) Hvn (AIQ),
inf Ena-d[- log f f(0[(a)] inf Bq.awol-log log f(g feVn
SeVn
= -l PLIM (TA) <b 0) log2 (a) @ 4)),
where II(A) + T( an(1)) The third equation follows the definition of in-context V.
information from Eq. (20). Practically, denoting PiLM(a) == ( we may approximate the Eq. 7 with the probing samples generated by LLM with
1 E log, P (a) + log2 PiLM (ā)).
(8)
D
However, Eq. 8 Sinvolves the LLM-generated labels âs for the probing samples, which can be factually incorrect. Utilizing those incorrect labels may lead to bias in the computation ICD-OVI. Fortunately, the theory of V-usable information [9] 20 provide effective tool called point-wise V-informationn threshold (PVI threshold) which assists deciding if one generated sample label is reliable. Here, PVI is defined as
PVI
((D) = log, PLLM(( + g) + log, PLLM @ g). (Q.6)
(9)
By Eq. the ICD-OVI is the mean of PVIs for all probing samples D. Built upon PVI, the PVI threshold is a scalar characterizing the likelihood of the correctness the sample label. Specifically, when the PVI of probing sample (ğ. â) is smaller than constant т, the label à is possibly incorrect; otherwise, the label à is highly likely to be correct for query q. Actually, the fact of the existence of PVI threshold is extensively validated by [9] and [20] in multiple LLMs and datasets of various semantic scenarios.
With the aid of the PVI threshold, we can address the potential bias caused by incorrect L.M-- generated labels. Specifically, for a probing sample (ÿ, â). we first calculate its PVI; if it is higher than a predefined V-information threshold then we adopt the PVI of the sample (ÿ. à) into the ICD-OVI calculation of ordered demonstrations II(D)) Otherwise, we relax the PVI to its expectation for labels set {ala E AAJ. i.c.
II(D) EPVI -E -PIIA- (g.4)
(a) logz P.l.A (a) + Pl log, P (a)
(10)
Conclusively, by denoting point-wise ICD-OVI (PICD-OVI) as PICD-OVI ((D)) (Q.4) (IV[ 2 PVI + T(PVI <T)EPVI
(11)
our ICD-OVI can be approximated as
ICD-OVI(U(())) ~ Mgg.y PICD-OVI
(12)
D
Thus, proposed ICD-OVI can effectively estimate the V-usable information despite noisy labels.
21

---

E Theorems and Proofs
Lemma 1. Let ( Ind Ei=1 Ij logæ, at be defined for 2t 0, with the constraint
El= Tt c, where < 1 Then:
1. f reaches its minimum when all 2; are equal, i.e., 2, for all i.
2. f reaches its maximum when one 24 equals and the rest are zero.
Proof. We will use the method of Lagrange multipliers.
Let g(f))...,, Tn) = Di= c = be our constraint. The Lagrangian is:
LII En A)
Σ I2 log oq
A 2
21 - c)
1=1
We set the partial derivatives zero:
log Ij + =
for i ,,...,
0x.
ØT.
32 -C 0 Σ i=1
0X
From
0L 8ag
get:
24
This shows that all z; are equal at the critical points.
Minimum Point: When all 24 are equal, let x; = for all i. The function value is:
f( C 9) log
Maximum Point: Consider æ1 = and v, 0 for > 1. The function value is:
f(c, Ol..,,0...00 0) = clog
To show that ........ f(c,0, .,, 0), need to prove:
clog n
< eloge
This is equivalent to fracen < c, which is true for > 1 and e 0. Therefore, have shown that the minimum occurs when all x; S. and the maximum occurs when one I; = c and the rest are zero.
Theorem 1 We assume that given LLM, probing sample (ğ,û) and an ordered demonstration text II(D).
When PVP 2 then à = a", where the a" is the ground-trath label corresponding to the generated query
The LLM predict the label à with the highest probability when query by with 1I(D) as its context, i.e., (() @ q) = arg max4eA P(a[I((D) e @).
Assume that for any two ordered demonstration texts [T) and I2(D), the @ 0) for all a E A.
PLLM (a)I()))) + 0) PLLM
Without loss of generalizabilliy, for any two ordered demonstrations II and II (D), there We additionally assume that when PVIlI()
{ <65) such that (())TT;(D) @ )) > 1
(q.0)
<
22

---

The a" is the second most probable label given by the LLM when prompted by query á with any ordered demonstration context II( iee. (I q) arg (M (D)) ① q); we write (D) 2 q) = X where 0 S X S
i E {1,2}.
By symmetry. we only consider the case A < 22. In this case, we assume that 2 À < < + 8 (6 is a constant) such that
(A1e) log d1c (1 X1e) log (1 X1c) <eloge- (2 X1)e.
(13)
Meanwhile, we require X2 A > (1 Iog(n-2) (1 -11).
With the assumptions above, if
PICD-OVI (1) (d.a) > PICID-VV'la(D)
(14)
(9.a)
then we have
PVI PV (q.a)) (q.a)))
(15)
Therefore, i is more performant demonstration order than (D) ie, Eq. 15 establish for any probing sample (q, a), then
ICD-OVI(LL(D)) > ICD-OVI(L2(D)).
(16)
Proof. First, in the case that PV P [I(D)
(0.4) T. by Assumption we have a'. Therefore, we have
PICD-OVI IID) P() n) P(a)[((A)) @ 0) PVI PVI
(17)
q.a
Eq. 17 enforces the establishment of Eq. 15
Next, in the where PVI (Q.4) 7, with Assumption 3, it suffices to prove that (Aie log diel 2
D22e log Azel gives rise to
} c log >ic+ (I-)) log z, Fa, 2 A log d En, -1,,; log x, + ra (18)
Now, by utilizing the Assumption 5, we claim that Eq. 18 establish, thus the theorem proved.
To prove Eq.
18 we start from the known incquivality
A 2 > (1
log (n 2) (1 A1)-
(19)
For simplicity, represent λ22 \1 as A in the following texts. We rewrite the Eq. 19 as
1 + 1/e log e -(1---c----00- ((1-A)) 2/2 + -1-h0 (1-X1),
log (n - 2) 1 e(log log 2) + (e log E(2 -Ai))
(20)
loge
1
+ (1-
A1)
+ log (n 2)
log (n 2)
log (n 2)
By Assumption 5, we substitute terms appears in Eq.
20 with left hand side (LHS) of Eq. 13 and
log [1 \ιel > log [[1 A1)e], further relax the bound as
log AiE
loge
1 1 A
A >\1 log (n - -2)
log (n - (1 A1) + log (n - 2)
log [(1 A1)e]
log (n 2)
1
<log (n 2) (-)x log diE + e lloge [(1 --1)e] log (n ( 2) - (1 - --Alee log [(1 A1)c - -c..
(21)
By multipling e log (n - 2) to both sides of the inequivality, we have
cog (Aic) log Dlog (n 2)](1 A1 A)c A1)c (1>x1) - - (22)
Eq.
22 is equivalent to
(1 - \1 A)e
- log +
log n
(1 (1-A1)elog' (1 A1)E--
E 0.
(23)
23

---

-006
0.06
61
0.15
02
0.6
08
0.6
0.4
06
-0.00
8
0.15
-03
Figure 4: Illuestration of the observation Eq. 24 and Equ 25 The red, orange, and blue curves are log x, log cæ and log z (where n = 6 and 0.2), respectively. It is clear that x log S log cr between point E and A: x logæ S log 1 er between point E and B.
Now, we observe that since \ + A = A2 < 1, thus (A1 + AJe < Therefore
(A1 + A)e log (Λı A)E S logeel E(A1 + A)e.
(24)
Here, the log is the slope of the linear function composed by (0, 0) and (e, elgge) Analogously, we have
A1 log
1 11
e (1 - -
< log
(25)
e
2
n 2 2 n-
By substituting the terms RHS of Equ 24 and Equ and Equ 25 further relax our incquivality
25 appeared in Equ
23 with the LHS of Equ
24
A)c 1 - \ A 6)
log (A1 A)c (A1 +1)++(1-
11
(26)
(1- An)elog (1 x1)e + (1 - <) log 1 >
We now rearrange the Eq. 26 and substitute λ₁ + A with A2, we have
-Ayc log d (1 A1)clog (1 -11ee>> A1
(27)
- (AzE) log (A2c) - (1 X2) --2 <) - (1 - c) log (1 c).
observe that, by Lemma] I. we have that
= (1 22) 1 A2 E),
min
(n
7 2
(28)
max
- log (1 - A1) log (1 \1E)
In other words,
Exs, log 1i = -(1 Ao log 1 X2 c)2
max (#1....fn-2))
2 Ex,,=(1->)) log 1; = -(1 A ) log (1 A1E).
(29)
min (Z 2)
Besides. it is direct to show that
(1 - e) log (1 e) S xa, log 2a, Fa, S 0,
(30)
24

---

i..,
-(1
log (1 -e) ) 2 Fa, log ra,i 2 0,
(31)
Hence, we rewrite the Eq. 27 to
Die log Aiel
min (x1n0Fu
( log min (2a, 1ag
(32)
((22c) log (Azc)l
max (21)..)---2)
( log anl + max (aa log r..2/
Therefore, are able write that
Are log Are+ =1,,; log vi ae 2 which is exactly Eq. 18
Age log 2 (1-))( ta (33)
L
Theorem 2. Randomly flipping entries from a sequence of length N will always keep the rank correlation within a range characterized by the lower bound 1 - Σm= (a; -1ki)=a(+)))(((C /N and upper bound Here a; is the original position index of the i-th perturbed element. The lower bound is achieved with a probability of I/K! when the perturbed sequence is the reverse of the original sequence. The upper bound is achieved with probability of 1/K! when the perturbed sequence is identical to the original sequence.
To prove the above theorem, first present the lemma:
Lemma 2. Given a list of N integers {ai, a2:..., aN} with a < a441, 1 1,20,,,11,,.... 1,2,...,, and its
N
random perturbation {ai, az....., . Ay.. the maximum value of Σ (a: -a,)² is achieved by reversing the list, i.e., at aN+1-i-
1=1
Proof. To prove that the maximum value of the sum:
N
S
Σ a. - a²)²
achieved by reversing the list {aī Ji=1, we need to show that this arrangement maximizes the squared differences between the original list {a and the perturbed list {a? /i where oy the perturbed element in the i-th position.
1.
We know that
a < 02 < ... ON-
Considering the sum S = Σm (a, )2 each term in this sum is of the form (a; - a;)², which measures how far apart a; and a; are. Thus, maximize the sum, we need to maximize each individual squared difference (a; )²
The largest possible difference between any two elements of the list {a occurs when the largest element aN paired with the smallest element a the second largest element aN is paired with the second smallest element 42 and so on. other words, the maximum possible difference occurs when of ax+1-; for all i. This arrangement is precisely the reverse of the original list.
To prove that reversing the list maximizes the sum, we propose to prove that when swapping any two elements in the perturbed list, the sum will always decrease. Suppose we swap two elements a and a (with p < a, without loss of generality) in the reversed list. Before the swap, the contributions to the sum from the two positions are:
-,,)), - + (a, a²)²
After swapping af and ay the new contributions become:
(a, o,,²² + (ag a
The change the sum, AS, the difference between these two expressions:
AS ((ap a² (a,, -,;)²) ((ap a²) + (ag a;)
25

---

We expand these terms as follows:
Before the swap:
(ap - ap)) + - -ug) = (ap -N+11ppp + (ag - UN+1-9)
After the swap:
(ap - -g) + (ag - -07)² (ap aN+1-g)2 (ag aN+11p)
Because a, dg and the list is ordered, swapping two elements in the reversed list decreases the squared differences, leading to a decrease the sum S. Thus, reversing the list maximizes the absolute differences (a, aj for all and any deviation from the reversed order will result in smaller sum.
With this lemma, now we prove Theorem 2.
Proof. Given two ranking sequences { and {s, [s the Spearman's 's rank correlation coeffi- cient is represented as follows:
N Σ (s; - s
(34)
N(N2-1
In our case, one ranking sequence is obtained by perturbing K elements in another ranking sequence. Denote the selected elements as {a: and the elements after perturbation as {a; )
according to Lemma 2, we know the maximum value of Σ (a--a;) )²)² is achieved when of aK+1-i- ==1 For other elements that are not perturbed satisfy that their d; equals 0. Therefore, the Spearman's rank correlation coefficient reaches the minimum value:
6 Σ (a; ak+1-;)²
Pain
N(N2 - 1)
(35)
Similarly, the maximum value is Pmax when the perturbed sequence is exactly the same as the original sequence. Since each perturbation has an equal probability, and there are different perturbations, we know the probabilities are both 1/K!
Supplementary Experiments
F1
Implementation Details
Our conduct experiments using system equipped with four NVIDIA A100 80GB PCIe GPUs. The system ran NVIDIA driver version 550.54. and CUDA 12.4. We implement the project with Python, mainly relying on the PyTorrch [1 and Transformers 40 packages for the implementation.
F.2 Ablation Experiment Results
Please see the supplementary ablation experiment results in Fig. 5 from those results with the main paper.
We have consistent observations
F33 Accuracy difference between few-shot (10 shots) and many-shot (150) ICL
We want to confirm that ICL-DOI still exists in many shot ICL. Thus, randomly select orders with 10 150 demonstrations and measure the model accuracy. The following figures present the distribution of model performance under few-shot and many-shot settings various datasets.
26

---

100
+2.2%
+0.0%
+2.0%
90
+1. 5%
+2.4%
+3.3%
Avcuracy (%)
+1.8%
+2.7%
+6.3%
70
+6.3%
82
C78
CT7
d6
mpl
mps
mp
13.5
140
11
15
12
(8) HIDOO v.s. HIDO-NC
100
+0.8% +0.
+0.6%
+1.1%
Aceuracy (%)
90
+1.9%
+4.3% +2.0%
+1.2%
+1.7%
+1.0%
+5.3%
+8.0 +8.6%
70
+-1 29%
038
C17
d8
dz
mpl
mps
mp
E3.5
140
01
18
(b) HIDO v.s. HIDO-ND
+0.3% +1.1%
+0.1%
+0.3%
90
+1.5%
+2.0% +1.2%
+3.8%
Accuracy (%)
+4.5%
4%
70
+14.5%
ds
dz
mpl
mps
mpH
13.5
140
11
18
(c) IIIDO v.s. HIDO-NInter
100
+0.3% +2.2%
+2.0%
+0.3%
90
+1.0%
+5.3%
+2.0%
+3.3%
1..9%
Accuracy
+8.4%
+3.6%
60
d8
mpl
mps mpp2
13.5
146
11
15
(d) HIDO v.s. HIDO-NIntra
Figure 5: The performance of our proposed HIDO and its variants tested with different LLMs on various datasets. The first one or two characters indicate the dataset (i.e. 't' represents TREC and 'mp' represents 'MPQA'). The remaining characters represent the model (i.e. 'z' represents Zephyr and '3,5' represents GPT-3.5T).
27

---

LlaMa3
SciPhi
Zephyr
0.900
0.875
Accuracy
0.8
Accuracy
0.8
Accuracy
0.850
0.7
0.7
0.825
0.6
0.800
10
150
10
150
10
150
Num. of Shots
Num. of Shots
Num. of Shots
Figure 6: AGNews. Many shot ICL generally improves the best model accuracy (i.e. increases maximum accuracy), which causes the range to be larger.
LlaMa3
SciPhi
Zephyr
0.95
1.0
8
0.95
Accuracy
0.90
Accuracy
Accuracy
0.8
0.90
0.6
0.85
0.85
0.4
0.80
0.80
10
150
150 Num. of Shots
Num. of Shots
Num. of Shots
Figure 7: CB. Here, the figure shows that many shot learning causes model performance to degrade. This could be a result of CB having less test samples (56 samples compared to 256 samples for other datasets). Regardless, there is large variance in the results, indicating demonstration order instability.
LlaMa3
SciPhi
Zephyr
0.94
0.94
0.9
0.92
Accuracy
Accuracy
Accuracy
0.92
0.8
0.90
0.90
0.88
0.7
0.86
0.88
10
150
150
150 Num. of Shots
Num. of Shots
Num. of Shots
Figure 8: CR. SciPhi and Zephyr exhibit wider variance in accuracy. In Zephyr, there is an extremely low outlier, emphasizing the importance order on model performance.
28

---

LlaMa3
SciPhi
Zephyr
1.0
Accuracy
0.8
Accuracy
Accuracy
0.9
0.8
0.8
10
150
10
150
10 150
Num. of Shots
Num. of Shots
Num. of Shots
Figure 9: DBPedia. Many shot learning improved model performance for all models; however, for LlaMa3, the variance becomes smaller but stays the Taking a look at DBPedia, the samples in general give more context in comparison to the others, which suggests that LlaMa3 is better at retaining and exploiting the information given from the demonstrations when completing the task of interest.
increases for the other models.
LlaMa3
SciPhi
Zephyr
0.875
0.875
Accuracy
Accuracy
0.850
Accuracy
0.850
0.6
0.825
0.825
0.800
0,800
0.5
0.775
150
10
150
10
150
Num. of Shots
Num. of Shots
Num. of Shots
Figure 10: MPQA. Again, many shot ICL improved model accuracy, but also caused the variance to increase in general. LlaMa3 especially exhibits the problem of ICL-DOI with over 25% difference between the best and worst accuracy.
LlaMa3
SciPhi
Zephyr
0.95
0.94
0.94
Accuracy
Accuracy
Accuracy
0.90
0.92
0.92
0.90
0.85
0.90
0.88
10
150
150
150
Num. of Shots
Num. of Shots
Num. of Shots
Figure 11: MR. Model performance only improved for LlaMa3, but the other two models illustrate wider variance. For SciPhi and Zephyr, the model performance under the few-shot and many shot settings is comparable, but in many-shot, the worst accurcy is much lower than that of few-shot performance.
29

---

LlaMa3
SciPhi
Zephyr
0.90
0.70
Accuracy
Accuracy
Accuracy
0.65
0.7
0.80
0.60
0.75
0.55
0.6
10
150
150 Num. of Shots
Num. of Shots
Num. of Shots
Figure 12: TREC. Increasing the number of demonstrations increased average accuracy for all models, and the variance did not improve much, other than for LlaMa3. LlaMa3 has billion paramters, compared to only 7 billion for the other two models, which means that it has more capability to learn and retain information. This can potentially be the reason for its superior performance against the other two LLMs.
F4 Quantitative Analysis of Generated Probing Sets
In the method development, we assume that the demonstration order optimized for answer prediction can also be used for sample generation. Since each additional iteration of HIDO optimizes the order such that it can achieve higher accuracy, the probing set from the inter-cluster optimization round is generated from the current optimized order. Thus, we can compare the probing set to the original demonstrations, which should be of high quality. Ideally, as the number of iterations increases (i.e. order becomes more optimized), of the probing set increases). The following figures measure the average L2 norm between the demonstration embeddings and the probing set embeddings generated by various LLMs on different datascts. In general, the experiments support the assumption, presenting negative trend between iterations and distance.
distance between two should decrease (i.e. the quality
30

---

LlaMa3
Zephyr
1.362
1.34
1.345
1.360
1.33
1.358
1,340
Distance
Distanse
Distuae
L356
1,335
1.354
1.31
1.352
1,330
1.350
1,30
Num. Iterations
Num. Iterations
Num. Iterations
Figure 13: AGNews. Embedding distance for both LlaMa3 and Zephyr consistently decrease as the number of iterations increase; however, Zephyr reaches its optimal three iterations, and additional iterations will cause the resulting order to deviate, as indicated by the spike at the fourth iteration. SciPhi has peak at three iterations but decreases after that point.
LiaMa3
SciPhi
Zophyr
1.285
1.26
1.280
1.26
Disiance
1,270
Distanoe
1.25
1.24
1,260
1.255
1.24
1.23
1.250
4
2
Nom. of Iterationn
Num. Iterationn
Nom. of Iteratonns
Figure 14: CR. Similar the previous figure, the probing sets generated by LlaMa3 and Zephyr consistently drop, and SciPhi displays peak and then a major drop in embedding distance. The figures suggest that after some iterations (i.e. as the order becomes more optimal), the LLM can generate samples close to the original text.
LlaMa3
SciPhi
Zephyr
1.370
1.37
1.385
1.369
1.36
Distanve
1.380
Distance
1.368
Distonce
1.375
1,366
1.33
1.370
1.365
1.32
1.31
Num. Iterationn
Num. of Iteeationn
Num. of Itcrations
Figure 15: DBPedia. All models demonstrate negative trend between distance and iteration. The figure for SeiPhi displays a plateau between the second and third iteration, which could imply that the probing set (i.e. the actual text) the semantics did not change much.
31

---

IJaMa3
SciPhi
Zophyr
1.34
1,330
1.33
1.325
1.28
1.320
Distance
1.32
Distnnee
Distnnee
126
1.315
1.31
1,310
1.30
1.305
1.22
Num. of Dtemttonss
Num. of Iterations
Num. Iterations
Figure 16: MPQA. The figures in general demonstrate negative trend. For SciPhi, the distance increases first then drops after the second iteration. However, the difference relatively small, about 0.05 difference, indicating that the generated samples are similar to the demonstrations.
LiaMa3
SciPhi
Zophyr
1.225
1.22
1.220
1.215
1.21
1.195
Disianee
1.210
Distunce
1.20
Distunce
1.190
1.205
1.19
1.185
1.200
1.18
1.175
Num. Iteratices
Num. of Iterations
Num. of Iterations
Figure 17: MR. For LlaMa3, the distance peaks iteration two and iteration four, but generally decreases. This could be due to HIDO trying to find the best order in the neighborhood space but selecting one that does perform well; however, it is able to find the best order the end.
LlaMa3
SciPhi
Zophy:
1.356
1.3600
1,365
1.354
1.360
1.3550
1.352
1,355
Ditunce
Distance
1.3525
Distange
1.500
1,350
1,3500
1.345
1.348
1.3475
1.340
1.346
1.3450
1.335
1.344
1.3425
1.330
Num. of Ilreatios
Num. of Ttrrations
Num. of lierationns
Figure 18: TREC. Like before, the genearl trend is negative in all the figures. However, the plots for SciPhi and Zephy both have a peak but drops in the next iteration, which indicates that the model diverges from the optimial and corrects itself.
32


Reviews:
[{"review_id": "OwBZ8naIft", "reviewer": "Reviewer_ctYV", "summary": "This paper investigates the challenge of demonstration order sensitivity in many-shot in-context learning with large language models, highlighting both the lack of theoretically grounded evaluation metrics and the computational intractability of searching optimal orders as the number of examples increases. To address these issues, the authors propose an information-theoretic metric, ICD-OVI, and introduce HIDO, a hierarchical optimization framework that first clusters demonstrations and then optimizes the order in two stages:\n1.\tby refining the order within each cluster (intra-cluster optimization), \n2.\tby determining the optimal sequence of the clusters themselves (inter-cluster optimization).", "questions": "1. The supplementary material appears to be missing sections F.5 and F.6, which are referenced in the text.\n2. See Weakness.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1.\tStrong Theoretical Foundation: The paper provides detailed theoretical analysis and proofs to support the proposed information-theoretic metric (ICD-OVI), which ensures the soundness and feasibility of the evaluation scheme. This theoretical rigor enhances the quality and credibility of the work.\n2.\tEmpirical Improvements Over Baselines: The proposed method consistently outperforms all baseline approaches across various datasets and models, demonstrating its effectiveness and robustness in practice.\n3.\tTimely and Significant Problem Focus: The paper addresses the important and increasingly relevant problem of many-shot in-context learning, particularly as the number of demonstrations grows in modern LLMs.\n\nWeakness:\n1. 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.\n2. 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. Additionally, the impact of the choice of embedding model on the overall performance of HIDO is not explored, leaving potential sensitivity or robustness issues unaddressed.\n3. 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.", "was_revised": true, "final_justification": "My major concerns are all addressed by the authors during the rebuttal. Therefore, I raise my evaluation score.", "rebuttal": "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.\n\n> 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.\n\nTo 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.\n\n> 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. \n\nTo 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\n\n> 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.\n\nHere, 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. \n\n\n|        |                        | AGNews           | MPQA             | TREC             |\n|--------|------------------------|------------------|------------------|------------------|\n| SciPhi | NV-Embed-v2            | 84.38 ± 2.07     | _84.90 ± 1.37_   | 70.31 ± 4.50     |\n|        | stella_en_1.5B_v5      | **87.76 ± 0.60** | 84.24 ± 1.37     | _73.18 ± 7.58_   |\n|        | text-embedding-3-small | _86.98 ± 0.45_   | **87.50 ± 0.78** | **80.47 ± 0.78** |\n\n> 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.\n\nWe respectfully disagree with this characterization. \n- 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, \nCR, MR and SST-5 are sentiment analysis datasets with varying granularities.\nRTE and CB are textual entailment and natural language inference datasets. \nTREC is question type classification\nand 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.\n\n- 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.\n\n- 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.\n\n\n\n|        |         |     HellaSwag    |       MMLU       |\n|:------:|:-------:|:----------------:|:----------------:|\n| SciPhi | GlobalE |   50.39 ± 5.41   |   55.86 ± 0.78   |\n|        |  LocalE |   48.96 ± 5.72   |   56.77 ± 2.15   |\n|        |   PDO   |   50.39 ± 5.41   |   55.86 ± 0.78   |\n|        |   HIDO  | **55.86 ± 6.14** | **57.03 ± 2.56** |\n| Llama3 | GlobalE |   27.73 ± 0.00   |   41.15 ± 2.15   |\n|        |  LocalE |   28.26 ± 0.23   |   41.41 ± 1.03   |\n|        |   PDO   |   27.73 ± 0.00   |   41.15 ± 2.15   |\n|        |   HIDO  | **28.39 ± 0.60** | **42.45 ± 1.19** |\n\n\n> Q1: The supplementary material appears to be missing sections F.5 and F.6, which are referenced in the text.\n\nWe 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. \n\n- Example Samples (AGNews):\n\n|                                                                                                                         Query                                                                                                                         |    Label   |\n|:-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------:|:----------:|\n| Apple Extends iTunes to Europe. \"The EU iTunes Music Store retains the same features and per-song price of 99 euro cents, established in June for customers in UK, Germany and France.\"                                                               | technology |\n| Microsoft Introduces Fingerprint Recognition. \"Microsoft rolled out an updated line of input devices, including its first fingerprint-recognition products. A mouse and keyboard with built-in fingerprint readers, along with a stand-alone reader \" | technology |\n| Justice Department Cracks Down On Spammers. It disrupted a network allegedly used to illegally share copyrighted files and is making a series of arrests against purveyors of spam.                                                                   | technology |\n\n- Probing samples: \n| Iteration |                                           Query                                           |    Label   |\n|:---------:|:-----------------------------------------------------------------------------------------:|:----------:|\n|     1     | The new iPhone 12 Pro Max is expected to have a larger battery life than its predecessor. | technology |"}, {"review_id": "FhVyS3svcj", "reviewer": "Reviewer_AYQ8", "summary": "In-context learning (ICL) suffers from demonstration order instability (DOI) when many samples are provided. Methods to handle ICLDOI break down in long-context models (ie., 50 in-context demonstrations) because of imprecision in quality and super-exponential growth of demonstration order space with length.\n\nThe authors introduce an information-theoretic metric for ICL demonstration order, an optimization technique along it, and an empirical evaluation of the efficacy of their method at ICL ordering.\n\nThe three prior methods they assess are GlobalE, LocalE, and PDO, which use predicted answer diversity, samplewise uncertainty, and distributional alignment of outputs respectively. The authors propose an algorithm HIDO, with V-usable information-based metric, for example selection instead. \n\nHIDO performs cluster-based topic selection in the embedding space, and then intra-cluster ordering using ICD-OVI. The clusters themselves are then ordered again using ICD-OVI. This process can be repeated many times to convergence.\n\nAcross all test datasets HIDO outperforms the baselines on most models, though in several cases this improvement is modest, within overlapping error bars. Over the course of runs on MPQA and TREC, HIDO converges toward a more performant demonstration order over iterations.", "questions": "I was struggling to follow how to interpret what $f(\\cdot|0)$ means practically until the explanation after equation 4, which slowed me down a lot on p3/4. Maybe can you signpost the practical meaning of this case earlier? This is a more general gripe with theory-heavy papers which spill lots of ink leading up to actually very simple and intuitive methods\n\nIn 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}$?\n\nDo you test an ablation of HIDO without ICD-OCI using one of the prior heuristic methods? How do we know the inter-intra alternating algo isn't the main contributor for performance?\n\n> the intra-cluster demonstrations share proximate embeddings, which\nsignificantly decreases ICL performance variance when demonstration orders vary\n\nMakes sense, but how do you substantiate this?\n\nHow do you generate probing samples?\n\nNitpicks:\n\nPlease do not use citet inline citations without referring to authors. For example, on line 101 replace \"[24] claim\" with \"Lu et al. [24] claim\"\n\nPlease provide full names for datasets in l293-296", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strong theoretical motivation.\nMostly clear *explanation* of this motivation (though I have some small gripes in the questions).\nClearly defined metrics.\n\nSolid experiments demonstrate that this technique is a valuable contribution.\n\nRelatively poor explanation of the implementation details, in particular how probing samples are produced. (See question)\n\nOverall, I learned something from this paper and am convinced that it's worth publishing.", "was_revised": true, "final_justification": "The authors answered my questions. I remain inclined to accept.", "rebuttal": "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.\n\n----\n> Can you signpost the practical meaning of $f(\\cdot|0)$ after equation (4) earlier for better reading experience? \n\nThank you so much for the invaluable suggestion! We will signpost the practical meaning of $f(\\cdot|0)$ early after its first appearance.\n\n---- \n\n> 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}$?\n\nNo, 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$.\n\n----\n\n> 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?\n\nHere, 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.\n\n|              |     MPQA     |     TREC     |\n|:------------:|:------------:|:------------:|\n|     HIDO     | 87.50 ± 0.78 | 80.47 ± 0.78 |\n| HIDO-NICD-OVI | 83.46 ± 1.19 | 79.69 ± 1.95 |\n\n----\n\n> \"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?\n\nTo 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.\n\n|        |                        |          | AGNews |  MPQA  |  TREC  |\n|:------:|:----------------------:|----------|:------:|:------:|:------:|\n| SciPhi |       NV-Embed-v2      | Acc. std |  2.07  |  1.37  |  4.50  |\n|        |                        | Emb. std | 0.0519 | 0.0481 | 0.0572 |\n|        |    stella_en_1.5B_v5   | Acc. std |  0.60  |  1.37  |  7.58  |\n|        |                        | Emb. std | 0.0446 | 0.0501 | 0.0399 |\n|        | text-embedding-3-small | Acc. std |  0.45  |  0.78  |  0.78  |\n|        |                        | Emb. std | 0.0277 | 0.0414 | 0.0266 |\n\n----\n\n> How do you generate probing samples?\n\nFor 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\n\n----\n\n> Do not use citet inline citations; provide full names for datasets in l293-296.\n\nThank you so much for the invaluable suggestions! We will revise the manuscript based on your suggestions."}, {"review_id": "uJXkaRJMVT", "reviewer": "Reviewer_YPNN", "summary": "This paper tackles order sensitivity in many-shot ICL. The authors introduce an information-theoretic metric that measures how much usable query-answer information a given order provides, and a hierarchical search algorithm, HIDO, which clusters examples, performs intra-cluster flips, then inter-cluster permutations to efficiently find high-scoring orders. Experiments on five LLMs and nine benchmarks show consistent accuracy gains and reduced variance compared to several heuristic baselines.", "questions": "1. How reliable is ICD-OVI when the LLM hallucinations dominate probe generation? Any calibration analysis?  \n3. What are the actual compute costs for running HIDO on $n=150$?  \n3. Does HIDO improve performance in 8--16 shot or 32 shot settings typical of few-shot ICL?", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths \n\n- The paper formulates a principled ordering metric (ICD-OVI) grounded in usable information, marking the first such theoretical score for demonstration ordering. \n- HIDO’s hierarchical search works on $n\\approx150$ by combining clustering with local and global swap steps, converging in a small number of iterations.  \n- Comprehensive evaluation across five models (16K–1M context) and nine datasets, including ablations on iteration count and cluster size.  \n- The method demonstrates low-variance orderings, tightening performance distributions.\n\n---\n\nWeaknesses  \n- Statistical robustness is missing: results are reported as means$\\pm$std but lack p-values or paired significance tests. Smaller gains could be noise.  \n-  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.  \n-  Hyperparameter brittleness: choice of cluster count $k$ appears dataset-specific (Fig. 3b), with no principled selection method beyond grid search.  \n- 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.  \n- 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.\n- 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.", "was_revised": true, "final_justification": "The rebuttal addressed some points by adding statistical significance tests, clarifying ICD-OVI’s handling of potentially incorrect probes, giving practical guidelines for cluster count selection, and explaining the role of intra-cluster ordering beyond primacy/recency biases. These clarifications improve the paper’s technical transparency.\n\n### Resolved issues\n- Provided paired significance tests showing improvements are statistically meaningful.\n- Clarified how ICD-OVI mitigates probe hallucination through filtering and approximation.\n- Offered empirical guidance for choosing cluster counts and showed that middle-ordering effects matter.\n\n### Remaining concerns\n- Practicality: method still requires substantial LLM calls and compute, with limited discussion of runtime feasibility.\n- Sensitivity: performance depends on dataset-specific hyperparameters without a principled automatic selection method.\n- Scope: evaluation is limited to many-shot (150) settings; impact in more common few-shot (8–32) scenarios remains unexplored, leaving uncertainty about broader applicability.\n\nWhile the method is interesting and well-motivated for many-shot ordering, these unresolved concerns reduce my confidence in its general utility.", "rebuttal": "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.\n\n----\n\n> 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.\n\nWe appreciate the reviewer's concern about statistical robustness. \nTo address this, we conducted paired t-tests on our experimental \ndata. For example, on the HellaSwag dataset with SciPhi LLM:\n\nHIDO vs LocalE: t(2) = 7.571, p < 0.05, Cohen's d = 1.163\n\nThis represents a statistically significant improvement of 6.90 \npercentage points with a large effect size. Similar significant \nimprovements were observed across dataset-model combinations.\n\n----\n\n> 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.\n\nThis 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. \n\n\n----\n\n> W3: Hyperparameter brittleness: choice of cluster count k appears dataset-specific (Fig. 3b), with no principled selection method beyond grid search.\n\n\nWe 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. \n\n---\n\n> 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.\n\nWe 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).\n\n| Dataset |   Time  |\n|:-------:|:-------:|\n|  AGNews | 1668.43 |\n|   MPQA  | 1269.96 |\n|   TREC  | 2160.13 |\n\n----\n\n> 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.\n\nThank you for the insightful comment! We kindly note that this is a misunderstanding.\n- 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. \n- Evaluating 8-32 shots misrepresents our core contribution and is analogous to critiquing distributed systems research for not testing single machines.\n- 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.\n- 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).\n\n----\n\n> 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.\n\nPrimacy/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."}, {"review_id": "JN8re6wO2H", "reviewer": "Reviewer_MaoD", "summary": "Many-shot in-context learning (ICL) demonstrates significant improvements on many tasks but the order of the demonstration affects the performance, causing instability, i.e., ICL-DOI. This paper points out two challenges that current ICL strategies towards ICL-DOI can not handle well. First, current methods use heuristic metrics according to predictions of LLMs to evaluate the quality of the demonstrations, but LLMs always struggle in long-context scenarios and such metrics are not that reliable or precise. Second, it is infeasible to enumerating all orders. \n\nAccordingly, this paper designs  an evaluation metric, ICD-OVI, quantifying the information gain of a certain order against the first challenge. Besides, this paper proposes HIDO allowing for refined exploration of the order space, getting rid of evaluation on all orders while achieving high performance. Experiments show that HIDO outperforms relevant baselines and this paper also open source the code.", "questions": "* 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.\n* See weaknesses part. Basically, cost analysis, experiments on more difficult tasks, the distance to the oracle bound should be incorporated. I would re-consider my ratings if my concerns can be solved well.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n* The code is open source for better reproduction.\n* This paper is well-written. The motivation is very clear, from ICL to better many-shot ICL, from challenges to solutions. The variation does exist and the corresponding evidences are given clearly (Figure 1). \n* The method combining inter- and intra- relations among the clusters is innovative.\n* Extensive experiments show the effectiveness of HIDO compared with other baselines.\n### Weaknesses\n* 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.\n* Since the order optimized by HIDO can be optimal or sub-optimal, I'm curious about how close to the oracle bound HIDO can achieve. Given that searching the whole order space for each case is infeasible, maybe a few samples like 20, 50, 100, can be investigate. If the performance is close to the oracle performance, the results can be more convincing.", "was_revised": true, "final_justification": "I have read authors' responses and I decide to keep my score of borderline accept since after rebuttal. Though the method performs well on simple tasks and close to oracle results, on more difficult tasks, the method is not that stable. However, the method combining inter- and intra- relations among the clusters is innovative, which may provide some novel ideas to the community.", "rebuttal": "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.\n\n----\n\n> 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.\n\n\nThank 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.\n\n|        |         |     HellaSwag    |       MMLU       |\n|:------:|:-------:|:----------------:|:----------------:|\n| SciPhi | GlobalE |   50.39 ± 5.41   |   55.86 ± 0.78   |\n|        |  LocalE |   48.96 ± 5.72   |   56.77 ± 2.15   |\n|        |   PDO   |   50.39 ± 5.41   |   55.86 ± 0.78   |\n|        |   HIDO  | **55.86 ± 6.14** | **57.03 ± 2.56** |\n| Llama3 | GlobalE |   27.73 ± 0.00   |   41.15 ± 2.15   |\n|        |  LocalE |   28.26 ± 0.23   |   41.41 ± 1.03   |\n|        |   PDO   |   27.73 ± 0.00   |   41.15 ± 2.15   |\n|        |   HIDO  | **28.39 ± 0.60** | **42.45 ± 1.19** |\n\n----\n\n> W2: Explore how close is the HIDO compared with oracle on small number of demonstrations.\n\nSince 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. \n\n|        |Num. Demons.| Max   |     HIDO     |\n|:------:|:----------:|:-----:|:------------:|\n| AGNews |      4     | 87.50 | 86.20 ± 0.45 |\n|        |      5     | 87.50 | 85.55 ± 0.39 |\n|  MPQA  |      4     | 87.50 | 86.72 ± 0.78 |\n|        |      5     | 87.11 | 84.24 ± 0.60 |\n|  TREC  |      4     | 30.86 | 21.88 ± 0.00 |\n|        |      5     | 68.36 | 51.43 ± 4.88 |\n\n----\n\n> 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.\n\nWe 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).\n\n| Dataset |   Time  |\n|:-------:|:-------:|\n|  AGNews | 1668.43 |\n|   MPQA  | 1269.96 |\n|   TREC  | 2160.13 |"}]

Author rebuttal:

Meta-review: This paper studies demonstration order instability (ICL-DOI) in many-shot ICL and the inapplicability of current strategies (unreliable heuristic metrics, computationally infeasible order checks). The authors propose an info-theory-based order evaluation metric (for the first challenge) and hierarchical HIDO method (for the second) to optimize many-shot ICL demonstration order. The authors and reviewers had thorough rebuttal discussions, and finally, the 3/4 reviewers converged to consistently accept this paper. After reading the paper & discussions, I think this paper is generally acceptable for publication in NeurIPS this year.
Decision: Accept (poster)