Studying word order through iterative shuffling

Nikolay Malkin, Sameera Lanka, Pranav Goel, Nebojsa Jojic

Abstract

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.

Introduction: Does Word Order Actually Matter?

In linguistics and NLP, a long-standing debate centers on how much syntax—the rules governing word order—actually contributes to meaning. It is often assumed that a model’s high performance on language tasks proves a deep "understanding" of syntax. However, an alternative hypothesis suggests that many benchmarks can be solved primarily through vocabulary (the "bag of words") without strict reliance on order.

The 'bag of words' problem: identical sets of words can sometimes form multiple valid sentences with different meanings, though the authors argue this is rare in practice.

Testing this hypothesis has historically been computationally difficult. Scrambling a 20-word sentence results in $20!$ possible permutations. Previous methods, such as beam search, often fail to find the optimal ordering, frequently producing ungrammatical results. Without a reliable way to find the most likely ordering for a given bag of words, researchers could not definitively determine if the original meaning was preserved or if the syntax was truly essential.

Methodology: Inference by Iterative Shuffling (IBIS)

To address this, the authors introduce IBIS (Inference by Iterative Shuffling). Unlike traditional left-to-right generation, IBIS begins with a random permutation of words and iteratively refines the sequence.

  • The TSP Connection: The authors demonstrate that finding the most likely word order is mathematically equivalent to the Traveling Salesman Problem (TSP). In this framework, words act as "cities," and the "distance" between them is defined by the negative log-likelihood (NLL) assigned by a language model, such as GPT-2.
  • $k$-opt Moves: IBIS utilizes $k$-opt moves—a technique borrowed from combinatorial optimization—to cut the sentence into spans and rearrange them to maximize the total probability.
  • Black-Box Flexibility: A key advantage of IBIS is its flexibility; it functions as a black-box tool compatible with any pre-trained language model without requiring additional training or specialized heuristics.

Empirical Analysis and Datasets

The study evaluates IBIS across diverse datasets to test the "permutability" of English:

  • Penn Treebank (PTB): Used for standard text linearization tasks (reconstructing sentences from bags of words).
  • GLUE Benchmark: Used to determine if Natural Language Understanding (NLU) tasks, such as sentiment analysis or entailment, truly require word order.
  • Genre-Specific Corpora: Wikipedia, Yelp, and arXiv were analyzed to see how writing style affects word order redundancy.

Key Insights: Syntax as Redundancy

The central finding is that for most English sentences, the specific choice of words is so restrictive that only one natural-sounding arrangement typically exists. Consequently, word order is often redundant.

The paper reveals a subtle loophole in NLP evaluation: if a model is powerful enough to infer the original order from a scrambled bag of words, it can still perform the task successfully. This suggests that benchmarks like GLUE may be measuring vocabulary-based inference rather than pure syntactic understanding. Interestingly, the researchers found that technical text (arXiv) is easier to permute into different high-probability sequences than informal text (Yelp), likely due to the rigid relationships between scientific terms versus the flexible nature of common vocabulary.

Results and Performance

IBIS achieves state-of-the-art results in text linearization and task recovery:

  • Linearization Accuracy: Using GPT-2 Small, IBIS reached a 50.0 BLEU score on the PTB dataset, significantly outperforming beam search baselines.
  • Recovering GLUE Performance: While scrambling input words initially caused performance to drop, using IBIS to "un-scramble" the words before processing them with BERT recovered 95-97% of the original accuracy on tasks like entailment and similarity.
  • Likelihood vs. Truth: IBIS frequently identifies word orders with a higher likelihood under GPT-2 than the original human-written sentences, indicating a model preference for "normative" or average syntax.

Conclusion and Future Work

While these results are striking for English—a word-order-prominent language—the authors note that "synthetic" languages with freer word order and complex morphology (like Russian or Warlpiri) may yield different results.

Future applications for IBIS include training models on unordered data to focus on content over stylistic surface features. Additionally, IBIS shows promise for constrained generation, where models must incorporate specific keywords or adhere to structural constraints like rhyme schemes while maintaining high linguistic probability.

Summary updated

Abstract

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.
BibTeX
@inproceedings{malkin2021studying,
  author = {Nikolay Malkin and Sameera Lanka and Pranav Goel and Nebojsa Jojic},
  title = {{Studying word order through iterative shuffling}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=3YPMj8nHreP},
}
Figure