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.
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.
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.
- 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.
- 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.
- 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