Order-Independence Without Fine Tuning
Authors: Reid McIlroy-Young
Katrina Brown
Conlan Olson
Linjun Zhang
Cynthia Dwork
Venue: NeurIPS 2024 poster (2024)
Keywords: LLMs
Multiple Choice Questions
Transformers
Positional Encodings
Modified Attention Mask
Primary area: generative_models
TL;DR: We present the Set-Based Prompting method which *guarantees* any LLM's outputs will be unaffected by reordering.

Abstract: The development of generative language models that can create long and coherent textual outputs via autoregression has lead to a proliferation of uses and a corresponding sweep of analyses as researches work to determine the limitations of this new paradigm. Unlike humans, these '*Large Language Models*' (LLMs) are highly sensitive to small changes in their inputs, leading to unwanted inconsistency in their behavior. One problematic inconsistency when LLMs are used to answer multiple-choice questions or analyze multiple inputs is *order dependency*: the output of an LLM can (and often does) change significantly when sub-sequences are swapped, despite both orderings being semantically identical. In this paper we present , a technique that *guarantees* the output of an LLM will not have order dependence on a specified set of sub-sequences. We show that this method *provably* eliminates order dependency, and that it can be applied to *any* transformer-based LLM to enable text generation that is unaffected by re-orderings. Delving into the implications of our method, we show that, despite our inputs being out of distribution, the impact on expected accuracy is small, where the expectation is over the order of uniformly chosen shuffling of the candidate responses, and usually significantly less in practice. Thus, can be used as a '*dropped-in*' method on fully trained models. Finally, we discuss how our method's success suggests that other strong guarantees can be obtained on LLM performance via modifying the input representations.

Code is available at [github.com/reidmcy/set-based-prompting](https://github.com/reidmcy/set-based-prompting.).

Order-Independence Without Fine Tuning
Reid Mcllroy-Your Department Computer Science Harvard University
Katrina Brown Department of Computer Science Harvard University
Conlan Olson Department of Computer Science Columbia University
Linjun Zhang
Department of Statistics Rutgers University
Cynthia Dwork
Department of Computer Science Harvard University
Abstract
The development of generative language models that can create long and coherent textual outputs via autoregression has lead to a proliferation uses and corresponding sweep of analyses researches work to determine the limitations this new paradigm. Unlike humans, these LLarge Language Models' (LLMs) are highly sensitive small changes in their inputs, leading to unwanted inconsistency in their behavior. One problematic inconsistency when LLMs are used to answer multiple-choice questions tiple inputs is order dependency: the output of an LLM can (and often docs) change significantly when sub-sequences orderings being semantically identical. In this paper we present Set-Based Prompting, technique that guarantees the output of an LLM will not have order dependence on a specified set of sub-sequences. We show that this method provably eliminates order dependency, and that it can be applied any transformer- LLM to enable text generation that is unaffected by re-orderings. Delving into the implications of our method, we show that, despite our inputs being out of distribution, the impact on expected accuracy is small, where the expectation is over the order of uniformly chosen shuffling of the candidate responses, and usually significantly less in practice. Thus, Set-Basod Prompting can be used as a 'dropped-in' mothod on fully trained models. Finally, we discuss how our method's ' success suggests that other strong guarantees can be obtained on LLM performance via modifying the input representations.
analyze mul-
swapped, despite both
Code is available at github. cow.//eiiincc///tt-aeeeee prompting.
1 Introduction
Recent advances in machine learning have led to a paradigm shift, as new training methods, which rely massive scale datasets to create general purpose 'base models', outperform specialized single purpose models (Achiam et al., 2023; Radford et al., 2019). A particularly notable development is in natural language processing, where self-supervised learning has led to a cornucopia of transformer based models that can string together multiple next.
Corresponding author reidncyOseas harvard.
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

a) Llama 2, 7B Default Order
b) Llama 2, 7B Reversed Order
c) Llama 2, 7B Set- Bas-Based Prompting
The pitch of sound mostly related to its
The pitch of sound mostly related to its
The pitch of a sound mostly related to its
"intensity" "
"speed" "mpplituee"
"speed"
"frequency"
"amplitude"
"a "amplitude" "speed"
"frequency" "intensity")
frequeney" "intensity"
Answer: frequency Ø
Answer: implitude g
Answer: frequency Ø
Illusratioo of order dependency in Llama 2, 7B. Using the order provided by (Measuring Massive Multilask Language Understanding) (MMLU) (Hendrycks et al., 2020) Laama 2 gets the question correct as seen in a), but if the order is reversed for the questions Llama 2, 7B predictions the wrong answer. In c) we use Set-Based Prompting to remove the ordering of the answers and Llama 2, 7B once again gets the question correct.
Figure 1:
token predictions, via autoregression, to generate coherent text that approximates a human response. These generated responses are not human and exhibit non-human behavioral quirks due to the limitations of the transformer based LLM architecture. Some of these, like the inability to reason about letters, are due to the choice of tokenization (the process of converting text into a sequence of numbers that can be used as an imput) which breaks words into multiple character chunks (McCoy et al., 2023), while others like the Lost Middle Phenomenon are limitations of the training data (N. F. Liu et al., 2024). The solutions to these limitations are known (An et al., 2024), although often impractical (Sutton, 2019).
There are other limitations of LLMs that appear be fundamental the design of LLMs. One pernicious issue is the order dependency problem. This is the phenomenon where the output an LLM can be significantly altered by changing the order of inputs, even when the re-ordering should have identical response; see figure 1 for example. This order dependency problem is well studied for multiple choice questions (Pezeshkpour al., 2023; Zheng et al., 2024), but can happen on any task.
Having systems that make or aid in decision making that are sensitive factors of the input that are orthogonal to the goals of the operators presents significant concerns. Consider an LLM that reads medical papers and summarizes them to doctor (Van Veen al., 2024). If shuffling the papers changes the summary can the doctor trust the model's responses? Additionally, order dependency presents algorithmic fairness concerns, such as in case where LLM being used to compare candidates has slight bias for the first candidate (Adian Liusie, 2024; Li et al., 2023).
In this paper we present a solution to the order dependency problem. Our method Set-Based Prompting solves this problem by removing the ordering information from the inputs to the LLM, for a specified set of sub-seguences. We refer to this as prompting to emphasize that our method does not modify the underlying model, it only changes the input. These sub-sequences of multiple tokens are (from the model's perspective) run in parallel, leading to the output being agnostic as to the ordering of the sub-sequences". We show that our method guarantees the parallel treatment of sub-sequences for arbitrary transformer based LLMs. We then test it on a variety of models on multiple choice question tasks and show that while parallel sub-sequences can impact performance, the impact is usually within that caused by re-ordering the sub-sequences when run without our method. We also discuss how the success of Based Prompting suggests many future potential contributions.
We sometimes refer to these perallel sub-sequences to emphasize that order information has been removed, have set of sub-sequences instead of a list.
2

---

2 Related Works
Multiple choice questions (MCQs) serve as an important task format in the evaluation of large language models (LLMs). Previous work has shown that modern LLMs are vulncrable to re-ordering of options in MCQs. Pezeshkpour et al., 2023 identify inherent 'positional bias' in the MCQ selting, where LLMs prefer to select options in specific positions as answers, and propose reordering the options lo position the most likely candidates in specifie locations within the sub-sequence. This viable in the case where both the prior positional bias and the correct answers are known a priori, but not necessarily in more general settings. Zheng et al., 2024 identifies a slightly different problem of 'token bias', wherein LLMs prefer to select specific option IDs A/B/C/D as answers. They propose estimating prior token bias via label-free, inferenco- option IDs from the overall prediction distribution. Adian Liusie, 2024 likewise identifies positional bias the setting of pairwise comparisons of natural language generation, and suggests debiasing using estimates of prior positional bias derived from observing comparison oulcomes for a subset of candidates. These methods all assume the existence of set of comparable samples with which to estimate prior ordering biases. Other work looking at how modifying word choice affects the model's outputs (Salewaki et al., 2024) show that this issue extends beyond deeerddepen,,ncc, but this matches how humans answer questions (Tjuatja et al., 2023) so should be less unintuitive for non-experts.
debiasing method, which separates the model's prior bias for
There is also an example of this order-dependence being used to probe the training data of LLMs. Oren ct al., 2023 shows that the ordering of questions in the training data affects the ordering during inference, allowing for detection of training data contamination.
One implication of this MCQ order-dependence is that it makes the relative comparisons of the performance of different models on benchmarks such as MMLU less reliable, as different. evaluation runs may employ different MCQ orderings within the test sets (Alzahrani et al., 2024).
3 Set-Based Prompting
To provably ensure order-independence we introduce Set-Based Prompting, an elegant 2- 2-pronged modification to the model at inference time touching, respectively, the al attention mask and the positional encoding. As these areas are not usually considered to be variable, this pushes the model slightly out of distribution. Furthermore, we hypothesize that some output quality degradation may occur since in the inder-independent case there is both less computation and less information, as no tokens in the set of parallel sequences can attend to tokens in other parallel sequences. However, we hypothesize that base models are robust to minor changes, and output coherence will not be noticcably impaired. In fact, to see the impact of our methods requires many queries. We begin with a review of the attention mechanism's 's attention mask and the positional encoding system used in transformer- LLMs. Then we will show how we can use a non-triangular mask combined, logether with a modified positional encoding our two prongs to make the attention block unable to determine the order of sub-sequences. This results in completely removing all the ordering information between sub-sequences, making the model's outputs perfectly order invariant.
3.1 Background
Attention Mask. The attention mechanism is a means of taking in an arbitrary number of imputs and attending to them in a weighted manner. This allows for longer sequences to be input and processed into single output. When processing text, the attention mechanism is used on each input token in turn, creating an embodding for cach token scparately.
In practice, we say the tokens can see all other tokens in the input, but when generating text the tokens in the input are usually treated as if they are the next to be generated and future lokens are masked output. This is seen in LLMs including GPT-2 (Radford et al., 2019) and Llama (Touvron, Lavril, et al., 2023) with their self-attention mechanism, wherein the outputs for certain position in sequence are based only on the known outputs at
3

---

Peder-Dependart Prompting
Set- Based Prompting
J
the
0
aptly
0
0
1 2 aptly
1
0
quicc
1
1
0
0
0
= 3 quick
1
1
0
0
0
Light
1
light
0
0
reddy
reddy
brown
brown
fox
1
5 Tox
1
p(s.) 1) pls, 2) p0 3) pls, ple. 5) pls, 7)
P(s. 13 p(S.2 p(i,3) p(i, ptF p(t,
p(s,5)
X = the, aptly, quick, Light, roddy, browm, fox
X,
12o,
(aptly,, quick
Liight, reddy, brown 1), tox
Xarart
Xnnd
Figure 2: Visualization of the differences between order-dependant prompting (left) and Set- Prompting (right). Our input is the prompt 'the aptly quick light reddy brown for' and "aptly quick" is in parallel to 'light reddy brown'. Each row represents a query to an attention block (we treat cach word as token), with the index of the qucry given by i. X and X, give the set of values over which the query is attonding. p(i.j) is the vector-valued positional encoding which is added to the word's embedding. The center of the diagram is the attention mask M,
previous positions and not on future positions. This is implemented by multiplying the inputs by mask vector that is for all future tokens. When these mask vectors are stacked (for parallel computation), they form a triangular matrix, the attention mask matrix for that input. Figure 2 shows this attention mask for sequence of 7 tokens.
Positional Encoding. Different language models use different methods of representing the position of imput tokens within a sequence. The original transformer introduced by Vaswani et al., 2017 proposed absolute positional embeddings. which involves assigning a specific value vector at each time step, or position, and then adding element- wemeet-wise those values to the token embedding. This is the positional encoding method used models such as GPT-2.
In contrast, most state the art LLMs including lama2/3, and PaLM (Anil et al., 2023), rotary positional embeddings (RoPF) as introduced by Su, Lu, al., 2023, which encode absolute positional information with a rotation matrix and naturally incorporate explicit relative position dependency in the self-attention formulation.
3.2 Provable Order-Independence via Set-Based Prompting
We now describe Set-Based Prompting our technique for modifying the positional encoding to provide parallel (order-free) representation of sequences of text, and prove that it ensures order-independence
Set-Based Prompting can be applied to both absolute and RoPE embeddings, on both GPT-2 and Llama2/3 models. In the absolute embedding case, the same value is addod to the token embedding for each token located in the same position in the parallel representation of the input text. Likewise in RoPE, absolute positional information the same for two tokens in the same "location" within parallel sequences, and token within a parallel sequence retains relative positional dependency with other tokens within the same parallel sequence.
3.3 Methodology and Thcoretical Guarantees
Consider the Attention block with positional encoding (Ferrando et al., 2024; Kobayashi et al., 2021; Su, Ahmed, al., 2024) for singlo-headed attention the attention mechanism maps multiple vectors into a single vector in a differential way. We start with a fixed query vector æ; which we give as input column vector, X = (.1...., .r,] RRdx is the sequence of all n inputs that will be mapped to a single vector, and M is the attention mask, an lower triangular matrix. The attention operator is defined follows.
"e drop the bias, heads and skip connections for brevity, see appendix for the complete formulation

---

(T;,
Σ
Mijais (Wv (z, + p(i.))))
(1)
mxEx
[1
ii
a Wo (Wx (a, + p(i,
Mij 10 else
aig:
aig := softmax myex
where Wo (query), WK (key), and Wy (value) are d x d matrices, with d being the internal dimensions of the matrices. p(i,j) is the vector-valued positional encoding for the token at position j relative to position é; note that if it is absolute (GPT-2) then p is only a function of j, while if relative (RoPE) it is a function of i-j.
Recall that o; is fixed. Equation (1) can therefore be considered to be a weighted sum over all columns of X, where the jth column is weighted by Oz.j and where M prevents future tokens from having any weight.
Since addition is commulalive,, the order in which the individual xy are provided is lost, except as provided by p(i.j), which includes the order information both for the scaling (as,)) and the unscaled vector (æ; + p(i, j)). The attention mask M also functionally encodes positional information when attention blocks are applied in series since 'utture' æy are masked out and do not contribute to the sum.
Thus, to prove that Set-Based Prompting is order-independent, it suffices to show that the positional encoding (p(i.j)) and attention mask (M) are unaffected by re-ordering by an arbitrary permutation of the parallel sub-sequences. Let S be the (unordered!) set of parallel sub-sequences, S (s1,.... .5} with Ek= |sx| = n. We start by defining the indices cach token (subscript) and which sequences the tokens are members of (superseript), with x indicating a token is a member of no sub-sequences. The lokens before the parallel sub-sequences are treated identically as in the normal case, and we denote them by start = 1ef....,,__1 where r is the lowest index in the parallel sub-sequences. The tokens after the parallel sub-sequences can be described similarly Xend = [a (............................... , , where is the greatest index in the parallel sub-sequences and m is the final index. Note that m staarl + (p- (p-r) r) + Xendl, where | the length of sequence of vectors.
Then, for parallel sub-sequence representation there is no ordering on 8y E S, because we reset the subscripts (positional indices) at the beginning of each sub-sequence. We have simply indexed the sub-sequences for convenience.
we say that 8n |af...., 2 Note that in our input
By writing it this way we can directly input it into the ATTN(#, X,, M) function with X, = =X start a $1 o... o Se o Xend, where a is concatenation. If we do this we will obtain order independence since p(i,j) and M.,, only use the indices of the tokens, so they are unaffected by ordering of the sub-sequences.
To show how j) and M.j (the unmodified M) are order independent we need to consider the three possible cases for the input vector xæ: 1) æ; is before the sub-sequences, 2) æ; is in the sub-sequences, and 3) a, is after the sub-sequences. The first case is straightforward since æ. E X start. The output is unaffected by the ordering of S all sub-sequence tokens are masked out by M,j; i <r.. r.
The second case is where of E Sy with r sisp. p. In this case if we naively evaluate ATTN("Ş X,, .M) we will get result that unaffected by the ordering of S, but the activations will be further from the training distribution than necessary, resulting in lowered performance as discussed Section 4.3. Note that for any at E Xs, p(i,j) and (i.j) are only affected by the positional index j (instead of k).
Finally, in the third case where x. E Xend, the same argument as the sccond case applics. The input vector at can 'see' all previous tokens, but their positional indexing unchanged under re-orderings of S. Thus in all three cases we have sub-sequence order independence.
5

---

3.3.1 Attention Mask
While the above method is sufficient for sub-sequence order independence, if used in practice the generated representations encountered by the Iearned weight matrices (Wy and (Wk) will be far from the training distribution in both case 2 and case 3 encounter. In case this is due to input vectors attending sub-sequences starting at index i = 2 the first token of sub-sequence 1 (æx) would have non-zero weight. on 4 lokens, three of which would have the positional encoding training, the model would never see multiple weights with the same positional encoding particularly multiple positional encodings that match the input token. Note that when used in an LLM ATTN() is applied sequentially, 3, the results are less severe since the positional encoding multiplicity only occurs for set of previous tokens, it docs not occur for the input token.
sub-sequences' inputs, e.g, if there were three
2. In
even minor errors can be amplified. For case
We can mitigate some of the issues by modifying the attention mask (i,)), making it so that case 2 tokens do not encounter out of distribution inputs. To do this we define a new attention mask M that also takes in the sub-sequences index each along with positional index of each token (at 20,, etc), while still retaining the sub-sequence order independence we want. With this notation, when & f * we have that at and an are in the same parallel sub-sequence.
Mij
if k
1
if S i and k if i and k 0 if j S i and f = 0 else
Mij
if l: 0
M
(2)
Mij
ff
O
else
Equation 2 still maintains order independence since it only differs from Maj when i + and in that case does not depend on the values of i or j.
we still retain order independence because ATTN(= X,, M does not change under re-orderings of the labels, only considers equality or absence of labels. See Section 4.3 for results when we don't do this masking.
we consider (T X,, M
This modified attention mask means that only tokens in case 3 see out training distribution representations, and that tokens will 'see' multiple other tokens at the same index.
This yields the following theorem.
Theorem 1 Given M as in Equation (2), far any permutation function T on the for the attention mechanism,
indices I....,f of the sub-queries S = so that applying т the blocks of column vectors corresponding to the W-th paral- lr........... X Xstart ([0] ,........... ......... [x] .......... [x] (() ....I} o Xend- Then
lel sub-sequences transforms X, Xstart o
Xend to
ATTN(()) X,, M,.) AT (M)) ,'', M
(3)
and
ATTN( X,, M X,, AATN(E,,. X,,M
(4)
Performance
While Set-Based Prompting is guaranteed to produce order independent results, we still need test what other impacts it has on the generated text. To this end, we collected four different LLM families (GPT-2 (Radford et al., 2019), Llama 2 (Touvron, Martin, et al, 2023),

---

0.6 Oreercng Effect
0.6
Erdering Effect
0.55 Botaata
00.5
0.44
0.4
0.3
0.7
0.2
0.0
76 Chat
0.0
76. Chat
Char
Opeak1
Liama
1iams Mistral
Openkd
Llams
Mistral
(a) Modified CSQA results for each model
(b) Modified MMLU results for each model
Figure 3: Per model accuracy on two different datasets, blue bars (left three) indicate runs done without our method and green with Set-Based Prompting The blue bars are constructed by rumning the test twice, once with the normal ordering and once with the reversed ordering. Worst of and Best answer or only one ordering answered correctly, respectively. While Best of 1 indicates that the normal ordering led correct answers. As Set-Based Prompting invariant to reordering so we only show one bar for all orderings.
count when both orderings lead to an correct
Llama 3 (AI@Mela, 2024), and Mistral (Jiang et al., 2023)) to conduct our experiments (see figure for the list of models). Due to our method modifying the internals of the model, each family requires a custom implementation of the inference code, meaning we can test all models in family, but adding new families time consuming. Our implementation for inputting parallel sub-sequences is implemented like the special tokens already commonly usod by most LLMs, with three special 'tokens' (start-parallel suw--uuuseeuenee and end-pare and-parallel) that are removed during inference, allowing for Set-Based Prompting to be added in cxisting workflows directly.
For lesting we used two slandard test sets CommonsenseQA (CSQA) (Talmor et al., 2019) and (Measuring Massive Multitask Language Understanding) (MMLU) (Hendrycks et al., 2020); these were chosen because they are multiple choice question sets that allow us to use the multiple options as the parallel sub-sequences.
As we want the runs with and without Set- Based Prompting to be similar we modified the prompting for both datasets. Instead of using numbers letters before cach option quote the options in double quotes (") and scparate them with space. This allows for the parallel qucries to have the exact same set of tokens as the non-parallel querics. Of note, implement the normal 1-shot evaluation for these lests that looks at the probability of each answer being generated, and that this slightly reduces the accuracy of the models from prompling with numbers or letters, so we label the methods 'modified CSQA' and 'modified MMLU to differentiate our results. As we are concerned with the relative performance of our method, not in benchmarking the models, we believe this gives us results that are close the existing literature.
the greatest value the selected answer. We do observe
4.1 CommonSenseQA
As we are concerned with reducing the variation of models under reordering, we examine both the accuracy under the default ordering, and the potential accuracy under reordering. In Figure 3a we examine our model's accuracy on CSQA, both with and without Set-Based Prompting. For the order dependent results we run CSQA twice and divide the answers into 4 sets (as in a confusion matrix): questions that both orderings get correct are counted and added to the Worst of 2 count, while questions that only one gets correct are also added to the Best of 2 bar, with the ones the normal ordering got correct used for Best of 1. The counts are then divided by the total number of questions (9741) to give the mean accuracy. Thus, the range of the blue bars can be considered to be the possible range of accuracies under two possible orderings per question. Note that if the models understood the text the difference between orderings would be minuscule; the difference between just two orderings being large shows that the specific models are fundamentally incapable of solving multiple choice questions, they merely approximate good response in expectation.

---

6.42 lasse troepting
Saaut Regenseccation
Kaliii ballond hondin
Aouel From
0,30
ron
0.25
0.3
6.35 16
75 Chat 235
Llama
135 Oht
Llama
0.0 7B
76 Crot 139
158 Chat
Inst.
Llang
Llano
Figure 4: MMLU results for subset of mod- els across all possible permutations (4!) of the ordering of the options, with the accuracy under Set-Based Prompting indicated with a diamond. Dots are ordered by accuracy with in each model's 'ss results, boxes show the quar- tiles across the different ordering.
Figure 5: Accuracy per model on MMLU, with error bars showing the variation in accu- racy under two orderings. The conditions are unmodified model, only the positional encod- ing p(i.j) modified, only the attention mask M. modified, and Set-Based Prompting
When examine our method we see (1) that all ordering produce the same result, and (2) that the accuracy within that the variation of order dependent queries for all models except Llama 3, 8B Instruct. This result suggest that Set-Based Prompting is not adding additional information into the model, instead it is removing a dimension of variation. We discuss some hypotheses for how method impacts the response generation in section 5,
4.2 Measuring Massive Multitask Language Understanding
Figure 3b shows the same analysis as in section 4.1 but for MMLU (Hendrycks et al., 2020). We see similar results to CSQA, but with lower accuracy the more complex MMLU.
To further explore the impact of reordering on outputs we ran all possible permutations of MMLU option orderings through subset of our models. In Figure 4 we see that for all Llama models Set-Based Prompting above or within the inter-quartile range of the 24 samples. We do see that in Llama 3 our method is bad as the worst ordering, but it is still within the range orderings.
4.3 Ablations
Partial Implementations. While we have a proof as to why both the the positional encoding and attention mask need to be modified, the transformer models are large enough that empirical observations are wanted to confirm the theory. We tested variations of Set-Based Prompting where only the attention mask the positional encoding was modified to mask the positional information. Figure 5 shows the variation between normal ordering and reverse ordering of question options for the first 20 sets of questions in MMLU (ordered alphabetically). Interestingly, modifying the attention mask reduces variation much more than the positional encoding, although the effect varies significantly between models.
Enumerated Options. We ran a subset (first 20) of MMLU with the option numbers re-added, this lead to improvement on all orderings. Note that adding numbers to inputs encoded with Set-Based Prompting implicitly removes the guarantee of order independence as there an ordering implied by the numbers. See figure 10 in the appendix for this result.
Chain of Thought. We implemented simple chain of thought prompt ("A: Let's think step by step") for the first 20 MMLU question sets. This lets us determine if the effects of Set-Based Prompting are limited to inputs near the end of the input sequence and check if an alternative prompting method would change the results. This method produced moderate uplift performance for both order dependent and order independent, cases, note that this experiment was once and not tuned. See figure 11 in the appendix for this result.
8

---

Eransle Zrderrnng
of
Bact
0.8
20.6
0.4
GFT-2
76
78 Chat
158
135 C301
35
89 Inss.
SpenAT
Podel
Pesition of Decument with the Arsver
(a) Sentiment classification task with in-context learning. The model was provided with sam- ples with labels, then asked to classify the fifth. Samples orderings changed betwen bars.
(b) Accuracy on extracting a pieces of information from 10 documents. 0 parallel batches is the fully order dependent model, with others being different splilting locations.
4.4 Other Tests
In Context Learning (Sentiment Analysis). We implemented sentiment classification task with context learning. The model was provided with 4 samples with labels, then asked to classify fifth. The dataset is Financial Phrase Bank Malo et al., 2014 all statements are finance related and classification is positive or negative. To look at the effects of ordering the model performance we always had three samples with the same label and 1 with the other label, with the different label always being first or last. See figure 6a for the impacts of different orderings the final classification task accuracy. Our experiment shows that Set-Based Prompting applied to the examples often improves performance over even the Best of 2 case.
Long-Context Information Retrieval. We implemented the long-context information retrieval task described in the paper by Liu et al. N. F. Liu et al., 2024. To do this, we generated 10 document sequences with the answer hidden one of them. Then we moved where the answer was located from the first to the last document and observed the retrieval accuracy. We used the same templates and dataset as Liu et al. for this. To test the effects of Set-Based Prompting we ran the documents in parallel, either all 10, 5 groups (2,2,2,2), four groups (3,3,3,1) or two groups (5,5). When running the sets docunents in parallel there two opposing forces affecting the accuracy: (1) parallelism, naturally, reduces order-dependencee, which helps accuracy; (2) at the same time, the intervention moves the inputs farther out of distribution, reducing accuracy. Figure 6b shows the results of this experiment. Our experiment suggests that limited intervention is a sort 'sweet spot'. The existence of 'sweet spot' suggests that our method can be used to evaluate the robustness of the model's learned manifold, since we now have a subtle measure of model sensitivity to perturbations.
Extended Context Window. We checked if method allows for the context window to be functionally extended since the total number of tokens, is less than m, the maximum positional index. Text generated where was greater than the context window of the model maintains coherence when run, see the appendix section 6.12 for an example.
Discussion
Understanding why Set-Based Prompting works at all, without needing additional training, will require further research. We hope that adding Set-Based Prompting during training will reduce the impact on performance. As shown in Section 4, for all tested models Bet-Based Prompting does not cause the model performance to degrade to unusable state, although, as noted in Section 1, order dependency raises significant bias and reliability concerns.
We hepoth three mechanisms of action for Set-Based Prompting to negatively impact L.LM's performance. First,, Set-Based Prompting reduces the total amount of computation, thus reducing the model's ability to 'do work' leading to lower accuracy. Second, Based

---

Prompting reduces the information available for some tokens, specifically those in the parallel sub-sequence, i.e., when the LLM is processing the second option it can see the first so can make more nuanced embedding. Finally, Set-Based Prompting leads to out of distribution token embeddings. The out of distribution impact is suggested by the difference in impact on instruction tuned models, compared to their base models. For example, in Figure 3b we see that for Llama 3, Set-Based Prompting performance is almost identical between the instruct and base models, while the instruct performs significantly better on best-of-2. This suggests that Set-Based Prompting is moving the input embeddings such that they are 'outside of the fine-tuning, but the base model is robust enough to still understand them. These modifications to the model's output may also be mitigated by including examples of Set-Based Prompting inputs during training or fine-tuning but additional work will be needed to determine this. Notably we also see hints of this when examining the model outputs under our methods; Set- Prompting makes fine-tuned models appear closer to the non-fine-tnnd models, in particular Set-Based Prompting tends to make the fine-tuned models more verbose. We believe that each of these mechanisms can be tested, allowing for more details to be revealed about the inner workings of language models, and hopefully build towards reducing biases and increasing robustness of these systems.
5.1 Further Explorations
In this paper we present and evaluate a small change to the input representation. Our results suggest that larger changes may not only be possible, but may not require significant training overhead. We chose not to study fine-tuning as we believe that showing that our method is 'drop-in' is a significantly more powerful result than one that requires additional training. A next step would be to evaluate how to fine-tune models be more receptive to this mothod, possibly even including the training as part of base-model construction. Additionally, we chose to study the smallest possible version of this effect, a single parallel sub-sequence per prompt. Further study is merited to determine if more complex sub-sequence relationships can be input without significant degradation. In particular, we hypothesize that a version of this method that treats the input text as directed graph of tokens (instead of linear sequence) would be possible, i.e., allow nested parallel sub-sequences, supporting cycles will likely require training. This is a representation already used for graphs (Ju et al., 2024; Wang et al., 2020) and is the natural representation for transformers. This type of representation would allow for inputs that much more closely reprosent how humans are provided text, e.g-, consider a class's syllabus, it is often a series of unordered sets of articles to road. Devclopogg techniques that allow for reasoning about human behavior be translatable to LLMs will greatly improve their utility to non-experts.
5.2 Towards Metadata in LLM Inputs
The empirical results in section 4.2 show that, while the positional encoding is used by LLMs, they can nonetheless 'understand" inputs where the positional encoding is modified. This suggests that LLMs are generally robust to minor changes in the token embeddings, with the positional encoding being the only currently implemented example. This is an entirely unexplored area of rescarch. If we consider the positional encoding as Icarned type of metadata, then other types of metadata could be added to tokens by simply adding new vectors during training to the token embeddings, just as we do with positional encodings. Adding additional metadata to each loken would allow for 'out-of-band' signals that are added to input texts. Consider, for example, lagging each token with a vector that encodes the privilege level of the token, allowing for the implementation of instruction hierarchies (Wallace et al., 2024) that are encoded per token, instead of contextually by tags. Another, example of the utility of adding token metadata is in typography. Many digital texts have bold, underlines, italics, etc.; each of these could have associated vector during training, allowing the LLM to 'scc' the text more clcarly. Instruction hicrarchies and typography are just two possible uses of complex LLM inputs, and we believe that many more are possible, allowing for LLMs that can interact with the world's details and not just simple linear text.
As the usage of LLMS becomes more systemic, operators will need to be able to encode more complex representations and have guarantees on the LLMs' behavior. We believe that this work presents development towards that goal.
10

---

Acknowledgments
This research is funded in part by the Alfred P. Sloan Foundation, the Crystal Ball," " (with O. Reingold), G-2020-13941, 2020, and NSF CAREER
and
References
[1] Josh Achiam et al. "Gpt-4 technical report". Tn: arxiv preprint arXin:2303.0877 (2023)
(cit. on p. 1).
[2] Mark J. F. Gales Adian Liusie Potsawee Manakul. LLM Comparative Assessmend:
Zero-shot NLG Evaluation through Pairwise Comparisons using Large Language Models.
2024. arXiv: 2307.07889 [cs.CL] CL] (cit. on pp. 2, 3)-
3 Al@Meta. "Llama Model Card". In: (2024). URL: https: http//ggttuu..t/ com meta-
1lama/laam3/bblala bblp//////lbbb/bb// httpa////booo/ma///a/aaaa hito/mann/MDDLLLI MODDLL_ARDD... CARD md (cit. on p. 7).
44 Norah Alzahrani et al. When Benchmarks are Targets: Revealing the Sensitivity of
Large Language Model Leaderboards. Feb. 1, 2024. arXiv: 2402. 01781 [cs]. URL: http://arxis: org/ httg/bb//2402. 01781 (visited 02/08/2020 (cit. on p. 3).
5 Shengnan An et al. "Make Your LLM Fully Utilize the Context". In: arXiv preprint XrXi::2404. 16811 (2024) (cit. on p. 2).
[6] Rohan Anil et al. "Palm 2 technical report". In: arXiv preprint arXin:2305.104000 (2023) (cit, on p. 4).
[7] Javier Ferrando et al. "A Primer on the Inner Workings of Transformer baseed Language Models". In: ariiv preprint arXiv:205 00208 (2024) (cit. on pp- 4, 14).
8) Dan Hendrycks et al. "Measuring Massive Multitask Language Understanding". In: International Conference on Learning Representations 2020 (cit. on pp. 2, 7, 8).
99 Albert Q Jiang et al. "Mistral 7B". In: arXiv preprint Xrv: 06825 (2023) (cit.
p. 7).
[10] Wei Ju et al. "A comprehensive survey on deep graph representation learning". In: Neural Networks (2024), p. 106207 (cit. on p. 10).
[11] Nikita Kitaev al. "Reformer: The efficient transformer". In: arXie preprint ar arXiv:2001.0445. (2020) (cit. on p. 13).
[12] Goro Kobayashi et al. "Incorporating residual and normalization layers into analysis of masked language models". In: arXie preprint arXiv:2109.01 07152 (2021) (cit. on pp. 4, 13, 14).
[13] Yingji Li et al. "A survey on fairness in large language models". In: arXiv preprint arXiv:2308. 10149 (2023) (cit. on p. 2).
[14] Nelson F Liu et al. "Lost in the middle: How language models use long contexts". In: Transactions of the Association for Computational Linguistics 12 (2024), pp. 157 173
(cit. on pp. 2, 9).
[15] Pekka Malo et al. "Good debt or bad debt: Detecting semantic orientations in economic texts". In: Journal of the Association for Information Science and Technology 65.4
(2014), pp. 782-796 (cit. on p. 9).
[16] R Thomas McCoy et al. "Embers autoregression: Understanding large language mod- els through the problem they are trained to solve". In: ar preprint ar arxv:33309. Xiw:2309.13638 (2023) (cit. on p. 2).
[17] Tsendsuren Munkhdalai et al. Leave No Contert Behind: Efficient Infinite Content Transformers with Infini-attention. 2024. arXiv: 2404. 07143 [cs CLJ (cit. p. 20).
[18] Yonatan Oren et al. "Proving test set contamination in black box language models".
In: arx preprint arXiv:2310. 17623 (2023) (cit. on 3).
[19] Niki Parmar et al. "Image transformer". In: International conference machine learning. PMLR. 2018, pp. 4053-4064 (cit. on p. 13).
[20] Pouya Pezeshkpour et al. Targe Language Models Sensitivity to The Order of Options in Multiple- Choice Questions. Aug. 22, 2023. DOI: 10. 48550/ arxiv. 2308 11483. arXiv: 2308. 1 11483(18 [cs]. URL: http: tttp:://are //arxiv...vv.////////i httaa/aww...gaaa///////aaaaa arg/abs/2308 11483 (visited on 04/03/2024) (cit. on pp. 2, 3).
11

---

[21] Alec Radford et al. "Language models are unsupervised multitask learners". In: OpenAl blog 1.8 (2019), p. 9 (cit. on pp. 1, 3, 6).
[22] Leonard Salewski et al. "In-Context Impersonation Reveals Large Language Models' Strengths and Biases". In: Advances in Neural Information Processing Systems 36
(2024) (cit. on p. 3).
[23] Jianlin Su, Murtadha Ahmed, et al. "Roformer: Enhanced transformer with rotary position embedding". In: Neurocomputing 568 (2024), p. 127063 (cit. on pp. 4, 14).
[24] Jianlin Su, Yu Lu, et al. RoFormer: Enhanced Transformer with Rolary Position Embedding. 2023. arXiv: 2104. 09864 [cs.CI, (cit. on p. 4).
[25] Richard Sutton. "The bitter lesson". In: Incomplete Ideas (blog) 13.1 (2019); p. 38
(cit. on p. 2).
[26] Alon Talmor et al. "CommonsenseQA:: A Question Answering Challenge Targeting Commonsense Knowledge". In: Proceedings of the 2019 Conference of the North American Chopter of the Association for Computational Linguisties: Human Language Technologies, Volume 1 (Long and Short Papers). 2019, pp. 4149-4155 (cit. on p. 7). [27] Lindia Tjuatja et al. "Do Ilms exhibit human- response biases? a case study in survey design". In: arXiv preprint rxXi:2311.04006 (2023) (cit. p. 3).
[28] Hugo Touvron, Thibaut Lavril, al. "Llama: Open and efficient foundation language models". In: Xrx preprint or Xrxiv:2302. 18971 (2023) (cit. on p. 3).
[29] Hugo Touvron, Louis Martin, et al. "Ilama 2: Open foundation and fine-tuned chat models". In: arXie preprint arXiv:2307.092:
(2023) (cit. on p. 6).
[30] Dave Van Veen et al. "Adapted large language models can outperform medical experts in clinical text summarization" ". In: Nature Medicine (2024), pp. (cit. on p. 2).
[31] Ashish Vaswani et al. "Attention is all you need". In: Advances in neural information processing systems 30 (2017) (cit. on pp. 4, 13).
[32] Eric Wallace et al. "The Instruction Hierarchy: Training LLMs to Prioritize Privileged Instructions". In: arXiv preprint arXiv:2404.13200 (2024) (cit. on p. 10).
[33] Guangtao Wang et al. "Multi-hop attention graph neural network". In: arXiv preprint
arXiv:2009, 14332 (2020) (cit. on p. 10).
(34] Chujie Zheng et al. Large Language Models Are Not Robust Mulliple Choice Selectors. Feb. 21, 2024. DOI: 10. 48550/ arXiv. 2309. 03882. arXiv: 2309. 03882 [cs]. URL: http:// //apxv//axvv.../ wwrrii.org//..e.. hrgg/ab//2309 03882 (visited on 04/03/2024 (cit. on pp. 2, 3).
12

---

Appendix
6.1 Code Release
Full code for our experiments is available as part of the final paper relcase. The code is released under the MIT license. The code can be found at this URL: https://githus
6.2 Compute Resources
Most of our results were done on a single Nvidia A100 GPU with 80GB of memory, running one model, thus the lack of 70B model results. Each run for table 3b took about 12 hours per model, with larger models taking slightly longer.
6.3 Computational Complexity
The computational complexity of our method is slightly lower than that of the normal attention mechanism. This is due to removal of clements from the attention mask, which reduces the number of key-value computations. This reduction is thus proportional to the number of parallel sequences and the length of these sequences. The reduction is thus minor for most uses, but could be significant for large numbers of parallel sequences very long subsequences.
6.4 Full Attention Formulation
The formulation of atlention presented in section 3.3 has the relevant components for this work, but does not represent the altention mechanism as used most language models, since the development of multi-headed attention (Vaswani et al., 2017). Again this version is based on that presented in Kobayashi et al., 2021 with the attention mask made explicit and the vectors reordered to make the types work.
The attention mechanism with multiple heads, and bias is:
multi-ATTN(E;; (z; X,M) ATTN (x,, X, X,M) ATTN' X,M)
(5)
ATTN" (z, M) = Σ
Mi (W/bb) (z, + p(i.j)))
(6)
æ,EX
Mij [1 if
else
T WTbb (W (x, p(i,))))
a softmax mxEX
Vd
where the superscript. h gives the index of the head, is the concatenation operator, and by (query), 6y (key), and by (value) are the bias terms each head. Note also that when used in model the attention mechanism is likely to be used with skip connection
y = multi-ATTN(( X, MMM + I;
(8)
and/or normalization. None of these listed changes affect the proof of presented in section 3.3, with the possible exception of the normalization which could in theory include positional information, but in all four model families we evaluated did not.
We also do not consider sparse attention mask patterns (Parmar et al., 2018), some of which dependant on the token values (Kitaev et al., 2020).
13

---

Table 1: Models used in this analysis divided by family.
Organization
Model Name
Parameters (B)
Finc-tuned
Basc Model
OpenAl
GPT-2
1.5
No
Meta
Llama-2-7b
7
No
Meta
-lama-2-7b-
7
Yes
Llama-2-70
Meta
Llama-2-13b
13
No
Meta
13
Yes
Llama-2-25
Meta
Meta-Llama-3-88
No
Meta
Meta-Lllama-3-8--Instte
Yes
Meta-Llame -3-8B
Mistral
Kistral-7B-IIstrrutt-y
yes
Mistral-7B-vo.
6.5
Model Details
6.6
Alternative Proof
Below is an alternative proof of the main result using a different method. Note that the nolation slightly differs from that used in the main proof
Consider the Attention block with positional encoding (Ferrando et al., 2024; Kobayashi et al., 2021; Su, Ahmed, et al., 2024) for multi-headed attention We take a sequence n input vectors {x
RRD written compactly as an input matrix X [æri... : RDx= where each æ, is a column of X (also token). For an input feature Tj, we denote the feature
matrix after incorporating the positional encoding matrix as X P.j _
;...;;"!! a.1
The self-attention layer with L heads, attention mask matrix M, and parameters = {M, (M,[(Qm:) Km, kn))m= (each M, Qm, Km and Vn are D matrices) takes X as input and outputs a D x n matrix. In vector form, the j-th column is
Attno(X) X)₂ = 2. + Σ Σ
Maso (1Qm2ij K Kmm Smapgldy (055)) Vmantlor -j- [m].
(9)
m== 5'E|n]
where is the activation function, usually taken as the soft-max function.
In the standard decoder-only transformers, M is lower triangle matrix with M, 1 for all j 2 j', and otherwise. Such an M functionally encodes positional information when attention blocks done in series since "future" æy are masked out and do not contribute to the computation. In this case
M Σ
Attng X); F. +
( ==1
Σ
((Qmi K Vma je [n],
which computes Attno(X), based on the weighted sunmation of all previous tokens æy for j' E (I,,, with weights given by a((Qmai, Km 3
plid"))))))
We now propose to modify the matrix M to make the transformers order independent. Specifically, let us first assume there are sub-sequences, with indices sets bo ......, by, b such that Ub U G...U6441 = [n]. Suppose we now want the model invariant with respect to the order of bi...., bi, that is, we want the AttnO(X) (X) output to be unaffected by re-orderings of bi...., by in X.
To achiove this, our proposed Multidimensional Attention Mask sets Mjs' = 0 for all j bi U...uu Ub and j' & bxg) and j' $ j, where À [m] (0.1...., is the membership function such that X()) = k if and only if E by. This makes sure that each sub-sequence cannot see other sub-sequences.
addition, we take positional encodings p(j.j') that depend
We drop the bias and output for brevity, appendix for the complete formulation
14

---

only on the relative order between i and the rank of j within bxC). As a result, the positional encoding for 2j only depends on its rank within the subsequence way, and does not rely on other subsequences at all.
Let TR. Dxx R Dxn be arbitrary permutation function that permutes the column blocks in X indexed by {bi, bb.,,b.... bt). We have the following theorem.
Theorem 2 Suppose we define M as above. For any permutation function that permutes the columns blocks in X indexed by {b1, be....,bii bi). (X) defined in (9) will be invoriant to this order change:
T(Attna( (X)) Attno(r(X)).
This implies that for any j E bi+1,
Attno(X) (X); = Attno(+(X)),
The proof of Theorem 2 can be found in Section 6.7 below. This theorem shows that by re-indexing the positional encoding and modifying the attention mask, the output of the attention block becomes independent of the ordering of the sub-sequences.
6.7 Additional Proof Details
Proof of Proposition 2:
As any permutation can be written the composition of pairwise permutations, in the following, we prove the result for pairwise permutations. More specifically, suppose we consider that permutes the columns indexed by by and by in X, and obtain X.
Recall that M is defined by letting Mjs = for all j' & bxo) and j S j. We then have for j E [x]
Attno(X), =3, Σ
Σ
My K Kmxzj Kmzffis")) Vm Vinzslis
m=1 j'E/n]
=I, Σ
Σ
a(Qmm K Kmatfiid) )) Vmzzllid
m=
In the following, we discuss three cases separately: j E by Ub j bo U b14 and j & bo Ub U U Ub441.
Case 1: j be Ubg Without loss of generality, assume k < k. Then when j E be.
Attns(X), =(x; + +P;)+ +
Σ
a((2m + Pp), K,, 2 p(1n") ) Vn
m=1 j' Bb =b
implying
L
(Attnn(()), =0+() + P+1) +
Σ
Σ
a((Qm K a oithi")) Vmnetlis
('E m=
Lb
and the right-hand side equals to Attno(r(X))
When j E bg.
Attno (X) =r,
Σ
Σ
a1Qma K
j'El Ubb
implying
r(Attng(X)) =I+(j) + P+6) +
Σ
a((Qmati Kmztthis" Vimzzplis))
m=1 (tb
15

---

and the right-hand side equals to Attno (xtn)(t(X));
Case 2: j bo U b141- When j E bo, we have
Attno (X), =1; Σ
Σ
a(1Qma K Kmagghd'y Vn x ppiis
m=1 J'El''S
(T
When j E bit1, we have
Attn =z +
Σ
Σ
o(1QmI K Kmazitnn V znliii
j' (1)
= AAttno (T)n))((X)))))
Case 3: j & bu U Ub Ubg Ubtt1. We have
Attno Ax) =3 +
E
d1Qmis Monne,KKeeppp Kmazliss V) (
m=1 yell Ubbb)
implying
L
7(Attng (X)) =(((1) + Pr() +
Σ
Σ
a1Qm K Kmozffil 2
m=
j'El'' Ubb)
and the right-hand side equals to Attno(r(X)
16

---

Question Ordering
0.5
Default Ordering
Modified CSQA Accuracy
Set-Based Prompting
Reversed Ordering
0.4
0.3
0.2
0.1
0.0
GPT-2
7B
Chat
13B
Chat
8B
Inst.
7B Inst.
OpenAI
Llama
Llama 3 Mistral
Model
Figure 7: CSQA accuracy for each model with the normal ordering, reversed ordering, and Set-Based Prompting applied to the options.
Question Ordering
Modified Modified MMLU Accuracy
0.4
Default Ordering
Set-Based Prompting
Reversed Ordering
0.3
0.2
0.1
0.0
GPT-2
7B
7B Chat
13B
13B Chat
8B
8B Inst. 7B Inst.
OpenAI
Llama
Llama
Mistral
Model
Figure 8: MMLU accuracy for each model with the normal ordering, reversed ordering, and Set-Based Prompting applied the options.
6.8
Additional Plots
Figures and show the same data as 3a and 3b respectively, but with the different orderings accuracy's explicitly included. Figure 9 similarly shows the same data as figure 5.
6.9 Impact of Enumeration
Figure 10 shows the effects of adding numbers to the questions during input. Note, this removal of order independence for our method as the numbers implicitly encode positioning. We see that this improves performance across the board. We believe this is due to the models being trained with numbers multiple choice questions.
17

---

Question Ordering
Modified NLLU Accuracy
reversed
only parallel atiention
only parallet attention. reversed
paraltel, position
only. parallel position reversed
0.2
order indopendent
0.1
78
78 Chat
138
138 Chat
88
88 Inst.
OpenAI
Llana 2 Model
Llana 3
Figure 9: MMLU accuracy for sub set of models with the normal ordering, reversed ordering, accuracy when only the positional encoding p(t,j) modified, accuracy when only the positional encoding p(i,j) j) is modified reverse ordering, when only the attention mask M modifiod, when only the attention mask M is modified reverse ordering and Sct-Based Prompting applied to the options.
Ordering Effect Worst
0.6
Best
Modified MMLU Accuracy
0.5
Best
Set-Based Prompting
0.4
0.3
0.2
0.1
0.0
GPT-2
7B
Chat
13B
13B Chat
8B Inst.
OpenAI
Llama 2 Model
Llama
Figure 10: Run of the first 20 MMLU questions (our test for Figure 4) with the numbers added, formatting identical to figure 3a.
6.10
Chain of Thought Prompting
6.11
Implementation
We conduct all experimental testing on huggingface models. We perform the greedy decoding with the temperature O, and apply the zero-shot prompting in all experiments. These hugging- face models already accept 2D attention masks input to the forward() call, which accepts an attention mask and positional encoding as input and outputs a single generated output token. This 2D attention mask support is detailed in tor cor/4d-masks We make a few modifications to these model instance objects in order to enable model instances to accept 2D attention masks input to the generate() call, which accepts an attention mask and positional encoding and outputs a sequence of generated outpul tokens. The modifications to Llama and Mistral model instances identical.
co/ //olog// ppoeda-
few additional minor modifications are required for GPT-2 model instances. On the GPT-2, Llama, and Mistral model architectures, override the model instances' func-
18

---

Ordering Effect
Worst of 2
0.5
Best of
Modified MMLU Accuracy
Best of
Set- Bet-Based Prompting
0.4
0.3
0.2
0.1
0.0
GPT-2
7B
7B Chat
13B
13B Chat
8B
8B Inst.
OpenAI
Llama 2
Llama
Model
Figure 11: Run of the first 20 MMLU questions (our test set for Figure 4) with chain of thought prompting, formatting identical figure 3a.
tion _update_model model kwargs for generation(). The function implementation remains the same, with the exception that if the function called with 2D attention mask, the 2D attention mask is converted to 1D attention mask to be passed to subsequent forward calls. When generate() is called with a 2D attention mask, it passes that 2D mask to the first. forward() call to generate the first token. After each call to forward, the function _pddtte model kwargs for generation() defines the attention mask and position ids be passed to the next forward() call. On second or later calls to forward, 1D attention mask passed, where attention is paid all non-padding tokens in the input prompt and all tokens generated thus far. For the Ilama/miste position id is defined to consist of a vector containing only the next integer following the largest position id in the previous position id vector.
models, on subsequent calls, the subsequent
For example, suppose the input consists of the tokens A,B,C,D, where tokens B and C should be processed in parallel.
We would define the initial attention mask to be
0
0
0
1
0
1
0
1
0 1
1
1
and the initial position ids to be [1,2,2,3].
These values are passed to the first forward() call. On the next call to forward, we pass attention mask [1,1,1,1,1] and [[4]] On the third call to forward, pass attention mask [1,1,1,1,1,1]] and position ids [[5]], and so on. The second generated token will attend to all original imput tokens and the first generated token, and will utilize previously computed keys/values such that it views tokens and C as though they were still processed parallel.
On the GPT-2 instances, we override two additional functions. First, we override the attn' function of the GPTAttention object in each hidden layer. If 2D attention mask is passed, then a'tt'' skips generating a causal mask and uses the passed attention mask instead. This modification unnecessary for Llama, which was already modified pass a 2D atlention mask through all the layers. Second, we override the function 'prepare inpuls for generation: By default, this function regenerates position ids both position ids and an attention mask are passed to generate(). Since want to be able to pass custom position ids, modify
19

---

the function to allow both the unmodified position ids and attention mask to be passed to subsequent forward calls.
6.12 Extending Context Window
One limitation of LLMs is their finite context windows. Existing work trics to circumvent this issue through techniques that require additional pretraining or and fine-tuning. In particular, Munkhdalai et al., 2024 proposes a new attention technique dubbed Infiniaatentionn that scales LLMs to infinitely long imputs with bounded memory. This method, however, requires continual pre-training and fine-tuning, whereas we present Set-Based Prompling as a drop-in method of significantly increasing the context window when subsets of the text can be processed in parallel.
Due to Set-Based Prompting changing the positional encoding, inputs that exceed the trained context window of the model can be used since only the longest sub-sequence contributes to the positional encoding of the final input token. Thus, can input longer sequences than the model was designed for. We tested this by inputting sequences of 6,000 tokens into Llama 2 7B, and the model was able to correctly summarize the input, while the same input put sequentially produces garbled text. See below for an example.
For 6018 loken input of the Wikipedia article for a recent disaster Llama 7B output:
its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its its
itt
its
its its its its its its its its its its its its its its its its its its
When the text was broken by header and fed in parallel the output was:
On March 26, 2024, the Francis Scott Key Bridge in Baltimore, Maryland collapsed after being struck by the container ship Dali. Two people were rescued from the water, and six maintenance workers were reported missing and presumed dead. The bridge was a continuous truss structure that was fracture critical, meaning it had no redundancy against failure of any particular part. The collision destroyed the southwest main truss pier, causing the central and south spans to collapse. The ship's emergency generators provided power to the propulsion system, but not to the electrical systems. The investigation is being led by the National Transportation Safety Board, with support from the Federal Bureau of Investigation, the U. S. Coast Guard, and the Maryland Department of Transportation. The ship's s crew was accounted for, and no serious injuries were reported. The disaster has raised questions about the safety of larger ships passing
Further work should determine whether this drop-in extended context window method comes at the cost of output quality degradation, relative to methods like Infini-attention.
20

---

NeurIPS Paper Checklist
1. 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 are based on the results we present in the main body of the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We present a proof our results including a discussion the required assumptions for it to hold.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assump- tions and a complete (and correct) proof?
Answer:
[Yes]
Justification: We provide a proof of our main result in the paper.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that it affects the main claims and/or or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Full code and datasets are provided with the paper allowing for complete reproduction of the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Full code and datasets are provided with the paper allowing for complete reproduction of the results.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper tests on a standard benchmark so the test details are well known and based on the literature.
7. Experiment Statistical Significance
Question: Docs the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? [Yes]
Answer:
Justification: Much of our results is a discussion variability.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
21

---

Answer: [Yes]
Justification: While our main result is theoretical, we provide details on our testing compute resources in section 6.2 of the appendix.
9. Code Of Ethics
Question: Does the rescarch conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Ys]
Justification: Our results do new data or human subjects, and we believe method will reduce bias in LLMs.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts the work performed?
Answer: [Yes]
Justification: Our work motivated by observations of biases in LLMs, and discuss how our method will impact these.
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
We do not release model dataset.
12. Licenses for existing assets
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: We cite the datasets used and respect their licenses.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the asscts?
Answer:
[Yss]
Justification: Our code is documented and released with the paper.
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 to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: We do not have human subjects.
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 (TRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We do not have human subjects.
22


Reviews:
[{"review_id": "KUty5Yk6UD", "reviewer": "Reviewer_bKgM", "summary": "The paper aims to address an issue within large language models (LLMs): their sensitivity to the order of input sequences, known as order dependency. This problem causes LLMs to produce inconsistent outputs when the order of semantically identical inputs is changed. \n\n### Key Contributions:\n1. **Set-Based Prompting Technique**: The authors propose a novel technique called Set-Based Prompting, which ensures that the output of an LLM is invariant to the order of a specified set of sub-sequences. This method modifies the input representation by removing the order information from the inputs.\n  \n2. **Theoretical Guarantees**: The paper provides theoretical proofs demonstrating that Set-Based Prompting eliminates order dependency for any transformer-based LLM.\n\n3. **Empirical Evaluation**: The authors test their method on multiple LLMs, including GPT-2, Llama 2, Llama 3, and Mistral, using tasks like multiple-choice questions from the CommonSenseQA and MMLU datasets. They show that while Set-Based Prompting can slightly impact performance, it generally maintains accuracy within acceptable bounds and eliminates the variation caused by different orderings.\n------------------------------------------------------------------------\nThank you for your replies and I raised my score accordingly.", "questions": "What will be the  benchmark performance under chain of thought prompting of this method compared to default chain-of-thought prompting baseline?", "limitations": "See more details in Weaknesses section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "### Strengths\n\n- **Theoretical Rigor**: The paper includes rigorous theoretical proofs that validate the effectiveness of Set-Based Prompting in eliminating order dependency.\n- **Empirical Validation**: The extensive empirical evaluation on multiple models (GPT-2, Llama 2, Llama 3, and Mistral) on two datasets (CommonSenseQA and MMLU) demonstrates the robustness and applicability of the method.", "weaknesses": "### Weaknesses\n\n#### Implementation Complexity\n- **Engineering Trick Perception**: The method may be perceived as an engineering workaround rather than a fundamental advancement. It requires users to input sub-sequence information, which can be seen as an additional burden and may limit the method's practical applicability. Providing a more automated or integrated approach could make the technique more user-friendly.\n\n#### Limited Improvement in Performance\n- **Marginal Accuracy Gains**: While the method ensures order independence, the actual improvement in model performance (accuracy) is limited. The results show that Set-Based Prompting maintains accuracy within the variation caused by different orderings but does not significantly enhance it. Highlighting specific scenarios where this method offers substantial performance gains could strengthen the paper's impact.\n\n#### Dependency on User Input\n- **Manual Sub-Sequence Specification**: The requirement for users to specify sub-sequences manually can be a significant limitation. This dependency on user input reduces the method's usability and scalability, particularly for large datasets or applications where manual specification is impractical. Exploring ways to automate the identification of sub-sequences would be a valuable enhancement.\n\n#### Evaluation Scope\n- **Limited Dataset Variety**: The evaluation is primarily conducted on multiple-choice question datasets (CommonSenseQA and MMLU). While these are standard benchmarks, the scope of evaluation could be broadened.\n\n#### Theoretical vs. Practical Benefits\n- **Practical Utility of Theoretical Guarantees**: While the theoretical guarantees are robust, the practical benefits might not be as compelling if the accuracy remains within the range of existing variations. Providing more concrete examples or case studies where order independence significantly improves real-world applications could make the practical utility of the method more apparent.\n\n#### Misleading Paper Title\n- **Title Naming Concerns**: I do not think that the proposed method is kind of \"prompting\" paper. It does change the internal implementation of LLMs instead of simply \"prompting\" them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to go over the paper and provide some useful feedback.\n\n# Relevancy\n\nOrder dependency is an important open problem in the LLM NLP literature [1,2,3,4].  Known motivations include increasing model robustness [4] and reducing ordering biases [2].  To these we add applications from algorithmic fairness. To our knowledge, we are the first to obtain a theoretically rigorous solution.  Moreover, we demonstrate that our solution incurs essentially no cost in accuracy. The robustness problem is a major concern for LLMs, and that they may only know the answer in one ordering [5] suggests that the models are not learning semantically useful representations. Having a method that forces the LLM to answer without using ordering means we can better evaluate LLMs.\n\nTo make the fairness concerns more concrete, consider a system that uses an LLM to compare essays. This system will likely be biased towards preferring the earlier essays (thanks to the Lost Middle Phenomenon). So if the essays are provided in alphabetical order the system will likely be biased against Chinese writers due to their names more often being later in the (English) alphabet. Making systems that don’t have these subtle biases is an important part making deployment of LLMs possible in the real world.\n\n# Additional Comments\n\nThe reviewer raises many other points in their review and we address them here.\n\n## Engineering Trick Perception\n\nMost methods that interact with LLM internals are simple engineering tricks, since the systems are complex, and simple linear methods mean the interventions are well understood. For example, the recent Golden Gate Claude [6] is implemented as a simple linear addition to the model’s activations, and the added vector is learned via a single hidden layer autoencoder. More generally, linear probes are very common in the explainable AI literature and many works have been published about them.  Thus, there is a strong tradition in deep learning using simple methods to enhance precision. Our technique, too, is a simple intervention; moreover, it enjoys a rigorous correctness proof.  \n\nSee Sub-Sequence Specification below for discussion of how our method can be easily integrated into existing workflows.\n\n## Accuracy Gains\n\nWe do not expect this method to improve accuracy. Our goal is reducing variance and information leakage. We are not providing additional information or additional “thinking time”, we are removing a cognitive defect from the LLM. The results shown in this paper greatly exceeded our hopes, it is very rare to find an intervention that doesn’t completely destroy the model’s performance. So we were hoping to get near the bottom of the error bars, not even fully within the range for all models. We think that this method having such a minor impact is in and of itself something that the community should be aware of, as we discuss a little bit in section 5, reviewer gPKU commented on this also.\n\n## Sub-Sequence Specification\n\nWe have implemented a method to input parallel sub-sequences that works like the special tokens already commonly used by most LLMs. Our system is implemented with three special “tokens”, a start parallel (`
`), new sub-sequence (`
`), and an end of parallel (`
`). During inference our tokenizer does the splitting itself. This should be a simple addition to any tokenizer. The main difficulty for us was verifying there was no accidental information leakage. Making a nicer interface made the analysis much easier, as we simply ignore the parallel tokens during “normal” runs!\n\nThe main results in the paper are all done with automated extraction of the parallel sequences, we expect automating the insertion of parallel sub-sequences to be straightforward as many LLM inputs are already constructed via concatenation of strings.\n\n## Limited Dataset Variety\n\nWe also have conducted two non-multiple choice question tasks at the request of the other reviewers. We have implemented a few-shot sentiment analysis task on which our method often outperforms the baseline, and a needle-in-a-haystack test where we match the performance of the baseline. Please see the general response for more details. These two new results will also be added to the paper.\n\n_Please see the global response for more details._\n\n## Theoretical Guarantees\n\nTheoretical guarantees are few and far between in this exciting literature.  In our case, they lead to elegant solutions to a real-life problem, if the model is not robust to our method then it is likely not robust enough in the real world. As we discuss in the Relevancy section there are many areas where raw performance is traded for lower variance. Note, also that we only look at un-fine tuned models, we expect fine-tuning to significantly reduce the performance gap, if the models are robust.\n\n## Title Naming Concerns\n\nWe agree that the name can be improved! Thank you for pointing this out.  Our current revised candidate name is __Order Independent Input Representations__ . We are happy to discuss this more during the discussion period.\n\n## Chain of Thought Prompting\n\nIn response to the reviewer’s suggestion we implemented a simple chain of thought prompt  (“A: Let's think step by step”) for the first 20 MMLU question sets. We were happy to see that the results match the other MMLU results from the paper, with chain-of-thought providing a moderate uplift on performance for both order dependent and order independent cases! This was our first run with chain of thought, with no tuning. We have added the plot to the general response PDF and will include it in the paper, along with the code and data.\n \n# Final Thoughts\n\nThank you and if there are any more questions we will try to answer them during the discussion period.\n\n# Citations\n\n_Please see global response_", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZanMPq7HBn", "reviewer": "Reviewer_gPKU", "summary": "The paper addresses the problem of order dependency in Large Language Models (LLMs), which causes inconsistency in outputs when the order of semantically identical sub-sequences is changed. The authors propose a technique that eliminates order dependency in transformer-based LLMs. The method is both theoretically sound and experimentally validated, showing minimal impact on accuracy despite the inputs being out of distribution. The technique can be seamlessly integrated into fully trained models. The paper also explores the potential of enhancing LLMs by incorporating metadata information similar to positional encoding.", "questions": "- What is the impact of not enumerating the candidate answers (e.g., using A, B, C, D) versus simply using “”? This aspect does not appear to be addressed in the main text.\n- Regarding Figure 3, the proposed method seems to perform better than the worst-case scenario. However, if the goal is to achieve the highest score, it appears that the order-dependent method might still be preferable. Can the authors elaborate on this?\n- Why do the results differ in llama3? A more detailed explanation would help clarify this variation.\n\nThis paper presents a significant advancement in addressing order dependency in LLMs. The method is both theoretically and experimentally robust, providing a practical solution with minimal performance trade-offs. The clear writing and innovative approach, particularly in Section 5.2, add to the paper’s strengths. Addressing the questions and clarifying the identified points would further enhance the paper. Overall, this work is a valuable contribution to the field and is strongly recommended for acceptance.\n\n[edit: I increase my rating to Very Strong Accept, see my comment on author's rebuttal for justification]", "limitations": "Limitations are adressed in the paper", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The proposed method elegantly and effectively addresses the order dependency issue in LLMs with only a minor performance drop.\n- The method is supported by thorough experimental evaluation and theoretical guarantees, adding to its credibility.\n- The paper is well-written, clearly explaining the methodology and its implications.\n- Section 5.2 introduces an innovative idea of improving LLMs by using metadata information in a manner akin to positional encoding, which opens up exciting new avenues for research.", "weaknesses": "The review does not identify any significant weaknesses in the paper. However, there are a few points of clarification needed, as outlined in the Questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the kind review and we are very glad to see other people are excited by the directions this work suggests. As the other reviewers posed many questions, we have some more results to show in the general rebuttal document.\n\n# Question Responses\n\n## Impact of Enumeration\n\nWe didn’t test with the questions numbered in the paper since that leaks positional information. We did some testing to see what quoting methods worked best, notably finding that no quoting has significant degradation across all models and conditions. We re-ran the first 20 MMLU questions (our test set for Figure 4) with the numbers added. This does improve performance across the board. We believe this is due to the models being trained with numbers on multiple choice questions. The order-independent results were within the error bars as in the other tests, but it’s harder to interpret those results as there is positional information leakage. To see the figure please look at the PDF for the main response.\n\n## Figure 3\n\nYes, without fine-tuning our method is likely to slightly underperform non-parallel inputs, but as we and others have shown the order dependent  method leads to a significant increase in variance under reordering changes. Our technique reduces variance. \n\nTo make the bias reduction concerns more concrete, consider a system that uses an LLM to compare essays. This system will likely be biased towards preferring the earlier essays (thanks to the Lost Middle Phenomenon). So if the essays are provided in alphabetical order the system will likely be biased against Chinese writers due to their names more often being later in the (English) alphabet. Making systems that don’t have these subtle biases is an important part making deployment of LLMs possible in the real world.\n\n## Llama3\n\nWe found the lower performance on Llama3 very interesting too. We hypothesize that this is due to Llama3 being overtrained relative to Llama2, making it more sensitive to out of distribution inputs. Interestingly, qualitatively we observed that our method also tends to make the chat fine-tuned models behave more like their base models (less terse responses was the main quantitative observation), suggesting that the fine-tuning was also partially interfered with by our method, resulting in the model responding like its base under our method. We think this suggests some methods for evaluating the robustness of trained models, and will add some discussion of these results to the main paper.\n\n# Final Thoughts\n\nThank you for your comments and new experiment suggestion. If there are any more questions we will try to answer them during the discussion period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PJHjfHV63w", "reviewer": "Reviewer_CaKN", "summary": "State-of-the-art language models (LMs) are now used to perform tasks (such as, e.g., question answering) with no fine-tuning; these models are fed the question and target options in their context, and their next-token distribution is then used to select an answer from this set of options.\nLM outputs, however, are known to vary significantly based on the order in which these options are fed to it.\nThis paper proposes set-based prompting, a method to make LMs invariant to such option reorderings.\nIn short, the method feeds all options to a transformer model “in parallel” by modifying their position indexes to start from the same value, and by masking the attention so that options cannot attend to each other.\nIn practice, this makes the model run slightly out of distribution, as tokens presented to the model after the QA options will be able to attend to multiple tokens with the exact same position (as the multiple options are assigned this equivalent position indexes).\nThe paper has experiments on two tasks, question answering and language understanding.", "questions": "I don't have any specific questions. But as a suggestion, I think the stacked box plots in Figs 3 and 5 are quite hard to read. It would likely be easier to read them if the different conditions were presented as separate bars.", "limitations": "The authors mention that their solution will make models run slightly out of distribution. Expanding on this point could be interesting, maybe discussing possible ways to mitigate this issue, such as fine-tuning models.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 1, "strengths": "The paper presents a simple solution to a well known problem in NLP.\n\nThe paper runs experiments with a reasonable number of language model families: gpt-2, llama2, llama3, and mistral.", "weaknesses": "In my opinion, this paper presents what is a relatively simple solution as being more complex than it is. (To be clear, I think this simplicity is one of the solution’s positive aspects, and not a negative aspect. Its presentation, however, could be considerably simpler.) Further, the proof of order invariance is sold as an important contribution, but it is also relatively straightforward. Since the methodological/theoretical contributions of this paper are relatively minor, though, I would expect it to have more experiments to confirm its efficacy. The paper, however, only presents two experiments, which are not very comprehensive in assessing the method's performance. More details below.\n\n* The paper’s contribution is a simple (yet potentially efficient) method to make LMs invariant to prompt ordering. This solution amounts to reindexing token positions and slightly changing the model’s attention mask. However, the paper takes almost 6 pages to present this relatively simple solution.\n* The paper only runs experiments on two tasks, and with one dataset each. This is not a comprehensive evaluation. The paper could run experiments with other tasks. Specifically, analysing the performance of this method on long-context information retrieval, as in Liu et al. (2024) could be interesting.\n* In-context learning is another important setting in which models are susceptible to input order variation. However, the paper only focuses its experiments on zero-shot experiments.\n\nLiu et al. (2024). Lost in the middle: How language models use long contexts\n\n\n\n\n------------\n\nEdit after author responses:\n\nI thank the authors for their response, and apologise for only replying to it after the discussion deadline. While I still think that some aspects of the paper could be significantly improved, e.g., simplifying the presentation, the newly added experiments make the paper's evaluation much more comprehensible, so I am raising my scores (from 3 to 5). The experiments showing the performance degradation on the long-context experiment are quite interesting (even if they present negative results), and experiments with ICL show another important setting for which this method can be useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time in reading our paper and providing some useful questions.\n\n# Relevancy\n\nOrder dependency is an important open problem in the LLM NLP literature [1,2,3,4].  Known motivations include increasing model robustness and reducing ordering biases.  To these we add applications from algorithmic fairness. To our knowledge, we are the first to obtain a theoretically validated solution. Moreover, we demonstrate that our solution incurs essentially no cost in accuracy. The robustness problem is a major concern for LLMs and that they may only know the answer in one ordering [5] suggests that the models are not learning useful representations. Having a method that forces the LLM to answer without using ordering means we can better evaluate LLMs which will affect all LLM evaluations.\n\n# Methodological Elegance\n\nThat the method seems obvious in hindsight is a strength, not a weakness!  This elegant solution allows for implementation by adding only three new “tokens” to the tokenizer’s dictionary. We will endeavor to increase clarity, and any suggestions for where to focus our attention are enthusiastically welcomed.\n\n# Experimental Scope\n\nInspired by [1,2,3,4],  we tested our method across multiple LLM implementations with the 57 subject MMLU as our main target. We also spent considerable time and effort examining which components of our intervention were required in practice: our original hypothesis was that we would also need to modify the padding so that the different sub-sequences were aligned, but we found that this was not needed. We also showed that our method allows for expanding the context window of the model (Sec 4.3), but as that follows directly from the positional encoding formulation we did not emphasize this result.\n\nThe reviewer suggests two non-multiple choice question tasks. We have implemented both of them and plots showing our results are available in the main response PDF.\n\n## Long-Context Information Retrieval\n\nWe implemented the long-context information retrieval task described in the paper by Liu et al. [6]. To do this, we generated 10 document sequences with the answer hidden in one of them. Then we moved where the answer was located from the first to the last document and observed the retrieval accuracy. We used the same templates and dataset as Liu et al. for this. To test the effects of our method we ran the documents in parallel, either all 10, 5 groups (2,2,2,2), four groups (3,3,3,1) or two groups (5,5). When running the sets of documents in parallel there are two opposing forces affecting the accuracy: (1) parallelism, naturally, reduces order-dependence, which helps accuracy; (2) at the same time, the intervention moves the inputs farther out of distribution, reducing accuracy.  Our plot suggests that limited intervention is a sort of “sweet spot.”  More interestingly, this suggests that our method can be used to evaluate the robustness of the model’s learned manifold.  This is an exciting new direction.  Thanks again!  We will include more details along with the data in the code release in the final paper.\n\n## In-Context Learning\n\nIn response to the reviewer’s suggestions, we implemented a sentiment classification task with in context learning.  The model was provided with 4 samples with labels, then asked to classify the fifth. The dataset is Financial Phrase Bank [7] so all statements are finance related and the model is attempting to classify them as positive or negative. To look at the effects of ordering on the model performance we always had three samples with the same label and 1 with the other label, with the different label always being first or last. When we ran this test, the in-context learning improved over the 1 shot test, showing that the models are using the examples.\n\nWe found that putting the examples in parallel often improves the accuracy over the non-parallel case, or is as good. This was a very strong showing by our method and we thank the reviewer for suggesting it! The plot can be seen in the main response PDF. We will include the plot and details of the test in the paper along with releasing the code. \nBar plots\n\nWe have redone them as separate bars, see main response PDF, and will update the paper with the new style for all plots.\n\n# Discussion of fine-tuning\n\nWe briefly discussed fine-tuning in section 5.1, but mostly to say we did not examine it. We agree that fine-tuning is the likely best way to mitigate the accuracy degradation. We will add more to the discussion on this. If there are other areas we can improve the discussion on please let us know and we can discuss them during the decision period.\n\n# Citations\n\n[1] Alzahrani, N., Alyahya, H.A., Alnumay, Y., Alrashed, S., Alsubaie, S., Almushaykeh, Y., Mirza, F., Alotaibi, N., Altwairesh, N., Alowisheq, A., Bari, M.S., Khan, H., 2024. When Benchmarks are Targets: Revealing the Sensitivity of Large Language Model Leaderboards.\n\n[2] Chen, X., Chi, R.A., Wang, X., Zhou, D., 2024. Premise Order Matters in Reasoning with Large Language Models. https://doi.org/10.48550/arXiv.2402.08939\n\n[3] Pezeshkpour, P., Hruschka, E., 2023. Large Language Models Sensitivity to The Order of Options in Multiple-Choice Questions. https://doi.org/10.48550/arXiv.2308.11483\n\n[4] Zheng, C., Zhou, H., Meng, F., Zhou, J., Huang, M., 2023. Large Language Models Are Not Robust Multiple Choice Selectors. http://arxiv.org/abs/2309.03882\n\n[5] Oren, Y., Meister, N., Chatterji, N.S., Ladhak, F. and Hashimoto, T., Proving Test Set Contamination in Black-Box Language Models. In The Twelfth International Conference on Learning Representations.\n\n[6] Liu et al. (2024). Lost in the middle: How language models use long contexts\n\n[7] Malo, P., Sinha, A., Takala, P., Korhonen, P.J. and Wallenius, J., 2013. Good debt or bad debt: Detecting semantic orientations in economic texts. CoRR abs/1307.5336. URL: http://arxiv. org/abs/1307.5336.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their thoughtful comments and are glad that everyone appreciates that we have obtained the first rigorously proven solution to an open problem – achieving order-independence – in NLP. Our solution is conceptually intuitive, and while the proof requires careful attention, it aligns well with this intuition.

Attached hereto are the plots associated with the 4 additional experiments the reviewers mentioned. All four show that our method is well within the range suggested by the original experiments, indicating that our method is robust to variations in task as well as in model family. Notably, our method outperforms the best-of-two results for the non-parallel inputs on the few shot learning test.  We provide additional, more tailored, responses to each interviewer individually.

# Relationship to the Literature

The order-dependency problem is well studied in the literature [1,2,3,4]. Prior work focuses on the robustness implications, as a model’s high sensitivity to input orderings mean that tests cannot be trusted to fully represent the model’s underlying understanding of the world. In this paper we add a new motivation for solving this problem: the fairness concerns raised by order dependency  (for example, alphabetical ordering of candidates may lead to discrimination against individuals with Chinese names). Both these concerns are significant to the field; our method is the first to completely solve them, and our solution provably will always work. There has also been further work on the order dependency problem since this paper was submitted, one of the top cited papers out of ICLR this year looked at how order dependency reveals a lack of robustness in models [5], specifically they were interested in looking for training set contamination as the cause.

# Solution Elegance

Our method requires two interventions to the input representation, proving that these have the required effects takes a few pages since we prove our results for the general case of all transformer based LLMs. We took significant effort to make the methods clear and easy to understand and we are happy to see that our results have the property of seeming obvious in hindsight. Our implementation seeks to make our methodology easy to use, and our code release implements the system as a modification to the tokenizer, meaning that we simply add three special tokens (start, break, end) to our texts to make sub-sequences order independent.

# Limited Dataset Variety

Our paper is addressing works highlighting the order dependency problem in multiple choice questions as those are the most common benchmarks for LLMs, so we focused our efforts on providing a broad set of models. Additionally MMLU tests a broad range of tasks (math, law, general knowledge), we reported only the top level numbers due to space constraints, but it is often broken down into the 57 different tests.

We also showed that our method allows for expanding the context window without any additional training (see Sec 4.3), as this paper was primarily focused on addressing the problems on the same terms as the other works in the literature; we only mention this briefly. We will add more details in the final paper on the expanded context window results. 

# Figures

The attached PDF has 4 figures. Note that for all figures we will provide code and data release. We focused on the Llama and gpt-2 models for these analyses. If the reviewers have any questions we will seek to address them in the discussion period. 

## Fig 1, Chain of Thought Prompting

We implemented a simple chain of thought prompt  (“A: Let's think step by step”) for the first 20 MMLU question sets. We were happy to see that the results match the other MMLU results from the paper, with chain-of-thought providing a moderate uplift on performance for both order dependent and order independent cases! This was our first run with chain of thought, with no tuning.

## Fig 2,  Impact of Enumeration

We re-ran the first 20 MMLU questions (our test set for Figure 4) with the numbers added. This shows improved performance across the board. We believe this is due to the models being trained with numbers on multiple choice questions. 

## Fig 3, Long-Context Information Retrieval

Accuracy on extracting the correct pieces of information from a set of 10 documents. The 0 parallel batches case is the fully order dependent model, with others being different splitting locations for the parallel batches. Note that order dependent model shows the characteristic reduction in performance for documents further from the start. While the less order dependent inputs perform as well or better than the worst case for the order dependent inputs. The fully order independent inputs lead to significant degradation, as that is a full 10 parallel inputs. We hypothesize that this is due to the inputs being too far out of distribution. For this analysis we looked at Llama 3 8B Instruct as the non-instruct models struggled with this task.

## Fig 4, In-Context Learning

We implemented a sentiment classification task with in-context learning. The model was provided with 4 samples with labels, then asked to classify the fifth. The dataset is the Financial Phrase Bank [7] and with model attempting to classify them as positive or negative. To look at the effects of ordering on the model performance we always had three samples with the same label and 1 with the other label, with the different label always being first or last. When we ran this test, the in-context learning improved over the 1 shot test, showing that the models are using the examples. We did 4 batches of 100 questions, varying the valence of the 3 samples and the valence of the sample.

We found that putting the examples in parallel often improves the accuracy over the non-parallel case, or is as good. This was a very strong showing by our method and we thank the reviewer for suggesting it!

# Citations

See CaKN response for citations.

Meta-review: This paper proposes a post-training method that makes an LLM robust to order variation in setups, such as multiple-choice questions, in which order should not affect its behaviour. The method is simple and theoretically justified.

The reviewers agreed that the problem is interesting and the perspective novel, but saw the method as more of an "engineering hack" whose general practical applicability is limited. They found moreover the method presentation and justification excessively complicated.

Still, after a lively discussion, all reviewers essentially agreed that the topic and approach are worth being disseminated.
Decision: Accept (poster)