Studying word order through iterative shuffling (2021)

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 is a model's understanding of syntax a precondition for its understanding of natural language? recent work on large language models @xcite @xcite has made this a popular hypothesis. yet, models that consume only bag-of-words features but rival those that understand syntax have surprised researchers time and again @xcite . new concerns have emerged that natural language understanding benchmarks may not be challenging enough to make sentence structure relevant @xcite . syntax is an essential aspect of language @xcite . sentence structure can be quite important: two sentences with very different meanings may use the same set of words (fig. 1 ). but how much does syntax, as realized in word order, matter in typical english text? given the words that make the scared mouse chased the hungry cat. the hungry cat chased the scared mouse. up a sentence, but not their order, is the order usually recoverable? if so, word order rarely encodes more information than is found in the bag of words. in the past, linguists could not have answered this question empirically. manually ordering words into sentences is too laborious, and when there are multiple orders that satisfy grammatical constraints, one needs a way to choose among them. with the power of large language models, we can reduce this question to a computational one and resolve both issues: given the bag of words, find the word order that is most likely under a trained lm. to make this search tractable, we develop inference by iterative shuffling (ibis), a procedure inspired by techniques in combinatorial optimization, that is superior to existing approaches to this problem. armed with ibis, we answer the question above statistically and explore the implications. first, we measure how often sentences and phrases are permutable in text of various genres. next, we analyze the effect of word order on the glue suite @xcite and on the task of autoregressive language modeling. randomly reordering input words drops the performance of models on nearly all tasks, but when we infer the order with the aid of a pretrained lm, this drop is small or absent. thus, nlp pipelines can effectively consume bags of words as input, and order carries much less meaning than we might imagine. we conclude with the implications of our results for language modeling. a computationally feasible search for word order clears a path for models that focus on content, rather than syntax, enabling a range of constrained generation applications. exterior is complemented by the beautiful ::: the period furniture housed inside. 88.0 restored in 1967, the beautiful exterior is complemented by the fine period furniture housed inside. beam search (64) without future costs 116.9 is complemented by the beautiful exterior in the fine period furniture housed inside.restored 1967, beam search (64) with future costs 110.9 restored exterior is complemented by the beautiful furniture housed in the fine 1967, period inside. 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 -opt moves, the original order is found. below: reconstructions of the same sentence using algorithms from prior work. ## text linearization by iterative shuffling ibis is motivated by a need not only to generate text from left to right when inferring the most likely word order under a base lm, but to reason over an entire sentence and permute spans or words. the bottom of fig. 2 shows some of the fail- beam search without future costs is unable to reason that the capitalized word is unlikely to occur in the middle of a text and should come first. beam search with future costs suffers from the same inability to 'plan ahead': by the end of the sentence, the algorithm begins to fail as it is left with a set of words that cannot be arranged coherently. however, some long spans that appear in the original sentence are generated, such as "is complemented by the" and "the fine period furniture housed inside". the ibis algorithm, which we will now describe, enables reasoning over the entire text to excise and recombine such coherent spans. such operations were introduced by @xcite in the context of the tsp on graphs. recall that a tour of a weighted directed graph is a closed path that visits each vertex exactly once. a -opt move on a tour is the operation of removing edges and inserting new edges to create a new tour. many heuristic algorithms for solving the tsp -finding the tour of lowest total weight -use -opt moves as the core search step; a maximum @xmath0. there is a precise equivalence between text linearization and the tsp on graphs when the base language model is a bigram model. suppose that the likelihood of a string has a factorization ## experiments: ibis we show that ibis achieves a new state of the art in text linearization using a black-box lm. following @xcite , we evaluate on section 23 of the penn treebank (ptb) dataset of wall street journal articles @xcite . ## experiments: (im)permutability using the ibis algorithm, we analyze the importance of word order in english text of different genres. we use three publicly available corpora covering different domains of textual expression: yelp: about 560k yelp reviews, commonly used as a text classification benchmark. 4 wiki: 2m wikipedia articles @xcite ). 5 arxiv: 1.7m scientific preprint abstracts @xcite 6 filtered to remove t e x. ibis can be applied to any bag of tokens, including punctuation marks, as shown in fig. 2 and to simply investigate how long a phrase needs to be before it becomes possible to find significant rearrangements with higher likelihoods, we limit our analysis to text spans of two kinds: sentences that contain no punctuation and spans of text between two consecutive punctuation marks. we sample 1000 such sentences and spans from each of the three domains with lengths (in words) falling into each of several buckets ( we analyze the reconstructions automatically using bleu scores and via human evaluation. results and discussion. 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. ## experiments: (dis)order in nlp tasks in this section we answer the question: how well could language models perform on standard nlp tasks if they were not given access to word order? ## conclusion and future work we have shown that word order in an english sentence encodes surprisingly little information in addition to that contained in the bag of words. nlp models such as bert and gpt-2 depend on order when creating representations of text, because they were trained on ordered words, but at the same time do not strictly need it, since their understanding of syntax -and the compressed world knowledge that 9 the metrics for sts-b are correlations, not accuracy. they hold -are sufficient to infer word order. it would be interesting to use techniques such as ibis to study investigate humans' capacities for syntax, both productive and receptive. are sentences with unlikely word order -as measured by a language model -more likely to lead to confusion (as in the first and last rows of a bolder conjecture states that many aspects of english syntax can be explained by optimality for language modeling. if, for a corpus of unordered sentences, we jointly infer a most likely word order for each example and a language model that fits these orders, do the inferred orders recover true english syntax, or at least a syntax satisfying known cross-lingual universals? if so, we would be led to vastly generalize the main claims of @xcite and @xcite . an iterative ordering algorithm like ibis is an essential step towards answering such questions. 10 our work can guide and motivate research into combining long-range dependencies in the evolution of content -vocabulary constraints such as sentiment, global story arcs, rules of rhyme and meter, etc. -with models like gpt-2 that are capable of generating and scoring text. as we discuss in appendix b, variants of ibis can be used for a wide variety of such constrained generation tasks by making some of the words in the bag latent and sampling them in concert with -opt moves: generating text from keywords, constraining text to a fixed length, composing poetry, and others where beam search is inefficient ( thus, ibis is an attractive, flexible alternative to beam search in generative language models. it may find applications well beyond word ordering. annotation process. all three human annotators ( §4) have english as their native or first language and are at least college-graduated. they were all compensated at the rate of us$15 per hour. they were made aware that the first of the two sentences they are shown is from english wikipedia while the second sentence is a reordering that need not be grammatical. we share the full set of instructions given to help them do the rating task in fig. 8 .