Studying word order through iterative shuffling

Nikolay Malkin, Sameera Lanka, Pranav Goel, Nebojsa Jojic

Introduction

In Natural Language Processing (NLP), word order (syntax) is traditionally viewed as the primary carrier of meaning. Large Language Models (LLMs) are often praised for their ability to master these complex structural rules. However, the paper "Studying word order through iterative shuffling" by Malkin et al. (EMNLP 2021) challenges this assumption, suggesting that syntax may be largely redundant. By introducing a novel algorithm to reconstruct sentences from unordered "bags of words," the researchers demonstrate that the lexical content itself often provides sufficient information to recover the original meaning.

A visual metaphor for the 'bag of words' representation, where semantic content is preserved without explicit order.

The Problem: Redundancy vs. Ambiguity

Linguists have long debated the relative importance of word order versus lexical choice. While specific examples like "The cat chased the mouse" versus "The mouse chased the cat" show that order can flip meaning, such cases are relatively rare in natural corpora. Most sentences contain enough semantic constraints that only one or two permutations are logically coherent.

Semantic ambiguity: identical bags of words can produce opposite meanings depending on syntax.

The primary obstacle in proving this redundancy has been computational. Reconstructing a sentence from a random permutation is a search problem with an astronomical state space. Previous approaches, such as beam search, often fail because they are "greedy," making early mistakes that lead to ungrammatical dead ends.

Methodology: The IBIS Algorithm

The authors propose Inference by Iterative Shuffling (IBIS), a search algorithm that treats sentence reconstruction as a combinatorial optimization problem.

  1. TSP Analogy: The task is framed similarly to the Traveling Salesman Problem (TSP). If words are cities and the "distance" between them is the negative log-likelihood (NLL) of their sequence under a language model, the most probable sentence corresponds to the shortest path.
  2. k-opt Moves: IBIS employs $k$-opt moves, a technique from combinatorial optimization. Instead of moving single words, the algorithm "cuts" the sentence into $k$ spans and tries rearranging them. This allows the model to preserve and move coherent phrases (e.g., "in the beautiful garden") as single units.
  3. Heuristic Search: To manage complexity, IBIS uses an auxiliary graph to prioritize moves likely to decrease the total NLL under a black-box language model like GPT-2.

Key Findings

The researchers evaluated IBIS across various benchmarks, including the Penn Treebank (PTB) and the GLUE suite.

  • State-of-the-Art Performance: IBIS achieved a 50.0 BLEU score on PTB text linearization, significantly outperforming the previous state-of-the-art beam search (44.5 BLEU).
  • Meaning Recovery: For sentences under 30 words, human evaluators found that nearly half of the IBIS-reconstructed sentences maintained the same or similar meaning as the original.
  • GLUE Benchmarks: While BERT's performance drops significantly on randomly shuffled text, it recovers to near-baseline levels when the text is first reordered by IBIS. For instance, on the MNLI task, accuracy rose from 65.5% (shuffled) to 79.4% (IBIS-reordered), compared to the 83.7% baseline.
  • Likelihood Paradox: Interestingly, IBIS often found word orders that the language model rated as more likely than the original human-written sentences, suggesting that human communication is not always optimized for maximum likelihood.

Conclusion

The success of IBIS suggests that syntax may be a convention optimized for communicating "bags of concepts" over a linear channel. While word order is essential for resolving specific ambiguities, it is often predictable from the words themselves. This work opens new avenues for constrained text generation and provides a deeper understanding of how much information is truly encoded in the structure of our language.

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