cs.CLSep 10, 2021

Studying word order through iterative shuffling

Authors: Esmeralda S. Whitammer, Sameera Lanka, Pranav Goel, Nebojsa Jojic

Organizations: Microsoft · University of Maryland · Microsoft Research

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.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Vocabulary shapes cross-lingual variation of word-order learnability in language models

    Mar 19, 2026Jonas Mayer Martins, Jaap Jumelet, Viola Priesemann +1Linguistic Typology

  2. Left-Branching Transformers Excel at Right-Branching Languages: Data Shapes Word Order Preferences in Language Models

    Aug 15, 2026Varvara Arzt, Allan Hanbury, Terra BlevinsMultilingual Language ModelsDecoder-Only Language Models