As neural language models approach human performance on NLP benchmark tasks, their advances are widely seen as evidence of an increasingly complex understanding of syntax. This view rests upon a hypothesis that has not yet been empirically tested: that word order encodes meaning essential to performing these tasks. We refute this hypothesis in many cases: in the GLUE suite and in various genres of English text, the words in a sentence or phrase can rarely be permuted to form a phrase carrying substantially different information. Our surprising result relies on inference by iterative shuffling (IBIS), a novel, efficient procedure that finds the ordering of a bag of words having the highest likelihood under a fixed language model. IBIS can use any black-box model without additional training and is superior to existing word ordering algorithms. Coalescing our findings, we discuss how shuffling inference procedures such as IBIS can benefit language modeling and constrained generation.
Figures & tables
Figure 1: Which word order is more likely?
Figure 2: Above: IBIS iteratively infers the word order that has lowest negative log-likelihood (left column) under GPT-2. At each step, the sentence is cut into pieces, which are then rearranged. After several such k -opt moves , the original order is found. Below: Reconstructions of the same sentence using algorithms from prior work.
Figure 3: One IBIS search step: The edge weights in the left graph are negative log-likelihoods from GPT-2 Small conditioned on previous context in the current best sentence, “mouse chased cat” (thick blue path). A candidate 4-opt move that decreases the tour weight (dashed red path) is proposed and scored by the LM, yielding the graph on the right. Because the new NLL is lower than the old NLL, the move is accepted.
Base LM
Inference
BLEU
NLL
LSTM
BS-512 +g
44.5
–
GPT-2 Small
BS-512
42.4
5.60
GPT-2 Small
BS-512 +g
45.4
5.48
GPT-2 Small
BS-1024
44.0
5.52
GPT-2 Small
BS-1024 +g
47.1
5.43
GPT-2 Small
IBIS
50.0
5.19
Table 1: BLEU scores of PTB sentences ordered by beam search and shuffling algorithms. NLL is negative log-likelihood per word under GPT-2 Small, averaged over test examples. First row is from Schmaltz et al. (2016) ; +g denotes search with future costs. ∗ Batch size 64, patience 256 was used for GPT-2 XL.
Figure 4: The NLL/word on PTB sentences (defined as in Table 1 ) as a function of the number of k -opt batches, with and without the IBIS heuristic. IBIS tends to converge faster than an unguided k -opt search and stabilizes at lower NLL, yet both reach lower NLL than the computationally comparable beam search baseline (BS-1024+ g ).
Base LM
IBIS output
Distil- GPT-2
Ibises, all mud and crustaceans, usually feed as a group, have long downcurved bills, usually probing for food items.
GPT-2 Small
Ibises, all mud crustaceans, usually as a group, have long downcurved bills, usually probing for food items and feed.
GPT-2 Medium
Ibises as a group usually have long downcurved bills, usually probing for feed, mud, crustaceans, and all food items.
GPT-2 Large
Ibises usually feed as a group, usually have long, downcurved bills, all probing for food items, mud and crustaceans.
GPT-2 XL
Ibises usually feed as a group, and all have long, downcurved bills, probing for food items, usually mud crustaceans.
original
Ibises all have long, downcurved bills, and usually feed as a group, probing mud for food items, usually crustaceans.
Table 2: The words of a sentence from Wikipedia ordered by the IBIS algorithm with five base LMs.
I was just there again in April and bragged to my friends about how great it was and we were all horribly disappointed.
just bragged to all my friends about how great it was in April and we were there again and I was horribly disappointed.
Mao Zedong’s philosophical essay furthered Marx and Lenin’s thesis and suggested that all existence is the result of contradiction.
Marx and Lenin’s philosophical essay suggested and furthered Mao Zedong’s thesis that all existence is the result of contradiction.
We introduce a longevity feature to the classical optimal dividend problem by adding a constraint on the time of ruin of the firm.
We introduce the classical problem of the optimal ruin of a firm by adding longevity to the feature time constraint on a dividend.
Table 3: Examples of original and IBIS-reconstructed sentences from Yelp, Wikipedia, and arXiv (top to bottom). More examples are shown in Table 8 .
(no punct.)
Yelp
Wiki
arXiv
Length
BLEU
PR
BLEU
PR
BLEU
PR
5–9
81.5
0.94
77.4
0.91
75.0
0.91
10–19
69.5
0.91
67.4
0.90
51.6
0.80
20–29
51.3
0.97
51.9
0.96
37.0
0.79
30–39
35.7
1.04
38.8
1.01
27.2
0.79
40–49
24.7
1.01
31.4
1.07
23.1
0.82
Table 4: Comparison of original and IBIS-inferred orders of punctuationless sentences (above) and spans between punctuation (below) of different lengths. We report BLEU score and ratio of perplexities (PR). A PR less than 1 indicates that IBIS reaches lower NLL per word than the original text.
perplexity
token acc %
π
n
latent
top
rand
latent
top
rand
acc %
1
30.1
38.1
100.0
2
30.5
31.7
49.4
38.1
38.0
31.3
98.5
3
31.4
34.2
72.9
37.5
37.5
25.4
96.4
4
32.2
36.2
97.0
37.3
37.2
21.8
94.0
5
33.2
39.3
123.5
36.9
36.7
18.1
90.9
Table 5: Perplexity and accuracy of next-word predictions of GPT-2 Small, conditioned on the bag of the previous n words B and 50−n tokens of earlier context C . The last column is the frequency with which the true order of the n previous words is the most likely under the posterior p(π∣C,B) .
entailment
paraphrase
CoLA
MNLI-m/mm
QNLI
RTE
MRPC
QQP
STS-B
SST-2
WNLI
MCC
acc %
acc %
acc %
F1 / acc %
F1 / acc %
ρP / ρS
acc %
acc %
original
58.2
83.7 / 84.1
90.7
64.8
88.0 / 83.6
90.6 / 87.3
88.3 / 88.1
91.9
39.4
random
0.4
65.5 / 65.4
74.8
56.5
81.8 / 73.1
74.2 / 72.3
82.1 / 82.0
80.7
54.3
IBIS
39.2
79.4 / 79.8
86.4
64.8
86.1 / 81.0
88.9 / 84.4
87.8 / 87.5
86.0
40.3
Table 6: Standard metrics of finetuned BERT models (mean of 32 random seeds) on the GLUE benchmark tasks, evaluated on raw validation data, data with randomly ordered words, and data with word order inferred by IBIS.
Fairy in techniques for coronavirus vaccine has been confirmed by research.
The mouse was hungry. It started feeding itself by taking UndergroundMISC’s engineered growth cheese assay . Now the mouse is still hungry.
The cat was hungry. Someone picked up the mouse and chased the cat away from it . Now the cat is still hungry.
The cat liked mice. His appetite for sweet treats was a little more intense . Now the cat hates mice.
The Dragon King has reached out to the court at the request of a judge with the Magic Kingdom . The Minister of Magic declined to comment.
Table 7: Constrained generation using IBIS variants (Appendix B ): sentences were forced to begin or end with the underlined spans and to contain the bold words in any order; all other words were generated by the model.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: IBIS example code usage.
Figure 6: Number of IBIS search steps and number of accepted k -opt moves plotted with sentence length (in words) in the PTB dataset.
Let’s make a bet: winner owes loser 50 dollars.
Let’s make a bet: loser owes winner 50 dollars.
The mouse chases the cat.
The cat chases the mouse.
Thoughts without content are empty, intuitions without concepts are blind.
Thoughts without content are empty, intuitions without concepts are blind.
Experience without theory is blind, but theory without experience is mere intellectual play.
Appendix
Table 8: Miscellaneous original sentences and the rearrangements of their bags of words inferred by IBIS under GPT-2.
12 11 10 9 8 7 6 5 4 3 2 1
−4−3−2−1 0 1 2 3 4 5 6 7
Fairy in techniques for coronavirus vaccine has been confirmed by research.
In the aftermath of the storm , humans and hippos , penguins , dolphins, and the dinosaurs were forced into the streets by the hive mind of the Internet.
See the full video for a long list of physicists and Mars ’ history as well as insights to the origins of bubbles .
Drones, drugs , climate change : the search for answers to nothing.
Appendix
Table 9: Examples of constrained generation using IBIS endowed with a word replacement step. Underlined words are a fixed initial context, while the bold words are required to appear anywhere in the text, in some order. The base LM was Distil-GPT-2; a slight relaxation of greedy ascent is employed.
The cat was hungry. Someone picked up the mouse and chased the cat away from it . Now the cat is still hungry.
The mouse was hungry. It started feeding itself by taking UndergroundMISC’s engineered growth cheese assay . Now the mouse is still hungry.
The cat liked mice. His appetite for sweet treats was a little more intense . Now the cat hates mice.
The world just had a cat and a dog fight . Now the cat isn’t hungry anymore.
The cat and the mouse were both hungry. Although they oversee the animal kingdom, their predators eat more . Now only one of them is hungry.
I thought I could find my future and fix it , but everyone was running in panic .
The announcement of the student strike is expected to be welcomed by many of us . Students across Canada are rejoicing.
Appendix
Table 10: Examples of reverse generation with an IBIS variant. Just as in Table 9 , the underlined tokens are fixed and the bold tokens are required to appear.
Figure 7: Annotators’ ratings of similarity between original and reordered sentences (§ D ).
Why do some languages like Czech permit free word order, while others like English do not? We address this question by pretraining transformer language models on a spectrum of synthetic word-order variants of natural languages. We observe that greater word-order irregularity consistently raises model surprisal, indicating reduced learnability. Sentence reversal, however, affects learnability only weakly. A coarse distinction of free- (e.g., Czech and Finnish) and fixed-word-order languages (e.g., English and French) does not explain cross-lingual variation. Instead, the structure of the word and subword vocabulary strongly predicts the model surprisal. Overall, vocabulary structure emerges as a key driver of computational word-order learnability across languages.
Jonas Mayer Martins, Jaap Jumelet, Viola Priesemann +1
University of Göttingen, Germany · University of Groningen, Netherlands · MPI for Dynamics and Self-Organization, Germany
We systematically compare word order preferences in decoder-only language models across 192 artificial languages and typologically diverse natural languages. On artificial languages, models exhibit a left-branching preference that aligns with neither natural language universals nor human word order learning biases. On natural languages, monolingual models show no clear base word order bias at small scales, but as data grows, a preference for right-branching subject-verb-object (SVO) languages emerges while SOV falls behind despite being the most frequent order cross-linguistically. This SVO advantage extends to multilingual models and correlates with language resource level and data quality rather than word order. Thus, the same architecture exhibits opposite preferences on artificial and natural languages, establishing that word order biases observed in practice are data-driven. Since highly-resourced languages are overwhelmingly SVO, these biases risk gradually reducing word order diversity, particularly in languages that productively use multiple word orders, with the widespread adoption of LLMs.
Varvara Arzt, Allan Hanbury, Terra Blevins
Faculty of Informatics, TU Wien · Khoury College of Computer Sciences, Northeastern University
Large audio-language models (LALMs) are often used in tasks that involve reasoning over ordered options. An open question is whether their predictions are influenced by the order of answer choices, which would indicate a form of position bias and undermine their reliability. In this paper, we identify and analyze this problem in LALMs. We demonstrate that no model is immune to this bias through extensive experiments on six LALMs across three widely used benchmarks and their spoken counterparts. Shuffling the order of answer options can cause performance fluctuations of up to 24% and even change model rankings, raising concerns about the reliability of current evaluation practices. We also study permutation-based strategies and show that they can mitigate bias in most cases. Our work represents the first systematic investigation of this issue in LALMs, and we hope it raises awareness and motivates further research in this direction.