How to measure the optimality of word or gesture order with respect to the principle of swap distance minimization
Authors: Ramon Ferrer-i-Cancho
Organizations: Quantitative, Mathematical and Computational Linguistics Research Group (LQMC), Departament de Ciències de la Computació, Universitat Politècnica de Catalunya, Campus Nord, Edifici Omega, Jordi Girona Salgado 1-3, 08034 Barcelona, Catalonia, Spain
The structure of all the permutations of a sequence can be represented as a permutohedron, a graph where vertices are permutations and two vertices are linked if a swap of adjacent elements in the permutation of one of the vertices produces the permutation of the other vertex. It has been hypothesized that word orders in languages minimize the swap distance in the permutohedron: given a source order, word orders that are closer in the permutohedron should be less costly and thus more likely. Here we explain how to measure the degree of optimality of word order variation with respect to swap distance minimization. We illustrate the power of our novel mathematical framework by examining spontaneous gestures produced by speakers from four languages (two SVO languages and two VSO languages, which represent two linguistic families). We show that crosslinguistic gestures are at least 77% optimal. It is unlikely that the multiple times where crosslinguistic gestures hit optimality are due to chance. We establish the theoretical foundations for research on the optimality of word or gesture order with respect to swap distance minimization in communication systems. Finally, we introduce the quadratic assignment problem (QAP) into language research as an umbrella for multiple optimization problems and, accordingly, postulate a general principle of optimal assignment that unifies various linguistic principles including swap distance minimization.
Figures & tables
Figure 1: The permutohedron of order 3. Vertices are labeled with all the possible permutations of SOV.
Figure 2: Hasse diagrams (blue arrows) of four total orders of vertices of the permutohedron. Every Hasse diagram describes an arrangement of probabilities on the permutohedron. Vertices are labeled with numbers from 1 to 6 in clockwise sense starting from the left-most vertex. Near each vertex, we show the probability of the vertex. πi stands for the i -th largest probability. A blue arrow from vertex i to vertex j indicates that pi≥pj . Black lines indicate edges of the permutohedron (only edges that are not hidden by a blue arrow are visible). (a) A Hasse diagram that minimizes ⟨d⟩ and ⟨d∣1⟩ . (b) A symmetric Hasse diagram that also minimizes ⟨d⟩ and ⟨d∣1⟩ . (c) A Hasse diagram that minimizes ⟨d∣1⟩ but not ⟨d⟩ . (d) A symmetric Hasse diagram that also minimizes ⟨d∣1⟩ but not ⟨d⟩ .
Figure 3: (a) The frequency of the six possible orders of S, O and V produced by speakers of Tagalog in unconventional gesturing experiments under the non-reversible condition [ 14 ] . (b) An optimal assignment of the frequencies in (a).
Figure 4: Probability assigments to vertices of the permutohedron. Black numbers indicate vertex labels while red numbers indicate probabilities. (a) A probability assignment to vertices of the permutohedron without probability ties. (b) A probability assignment to vertices of the permutohedron with probability ties. (c) The directed graph (blue arcs) of the vertex relation induced by the probability assignment in (a). A blue arrow from vertex i to vertex j indicates that pi≥pj . Black lines indicate edges of the permutohedron (only edges that are not hidden by a blue arrow are visible). (d) The Hasse diagram of the previous directed graph following the same conventions as in (c).
Figure 5: The total preorder of vertices of the permutohedron (blue arrows) induced by the minimization of ⟨d∣1⟩ . Vertices are labeled with numbers from 1 to 6 in a clockwise sense. A blue arrow from vertex i to vertex j indicates that pi≥pj . Black lines indicate edges of the permutohedron (only edges that are not hidden by a blue arrow are visible). (a) The total preorder as a directed graph. Self-edges resulting from reflexivity are omitted for simplicity. (b) A Hasse diagram of the previous graph. As the directed graph that defines the total preorder has cycles, the transitive reduction may not be unique [ 28 ] , and then we show only one of the Hasse diagrams (Appendix C ).
Figure 6: Arrangements with four non-zero probability orders (vertices with non-zero probability are marked in red). (a) The non-zero probability orders are contiguous, namely they form a path. (b) The non-zero probability orders are not contiguous.
T(m)
m
non-reversible
reversible
any
1
0
0
0
2
0
0
0
3
1
1
2
4
2
3
5
5
1
0
1
Table 1: The distribution of m , the number of non-zero probability orders in each ensemble (non-reversible, reversible or any). T(m) is the number of m non-zero probability orders in members of an ensemble.
Figure 7: The average swap distance ( ⟨d⟩ ) as a function of the random baseline ( ⟨d⟩r ) in crosslinguistic gestures. The dashed line is a control line to indicate identity, i.e. ⟨d⟩=⟨d⟩r . Points below the control line satisfy ⟨d⟩<⟨d⟩r . Color point indicates the language of the participants. Point shape indicates the reversibility condition.
Reversibility
Language
F
m
Sˉ
πo
po(m)
⟨d⟩min
⟨d⟩
⟨d⟩r
⟨d⟩max
Ω
reversible
English
121
4
0.37
0.033
0.033
0.41
0.47
0.67
1.5
0.78
Russian
103
3
0.57
0.1
0.1
0.64
0.7
1.02
1.5
0.85
Irish
82
4
0.54
0.033
0.033
0.62
0.62
0.97
1.5
1
Tagalog
82
4
0.61
0.033
0.033
0.74
0.74
1.1
1.5
1
non-reversible
English
119
4
0.6
0.033
0.033
0.71
0.74
1.08
1.5
0.91
Russian
117
3
0.54
0.1
0.1
0.59
0.59
0.97
1.5
1
Table 2: Summary of the statistical information by reversibility condition and participant’s language: F (the total frequency), m (the number of non-zero probability orders), Sˉ (the dominance index), πo (the probability that a random permutation is optimal), po(m) (the probability that a random permutation is optimal assuming no probability ties among the m non-zero probability orders), ⟨d⟩min (the minimum value of ⟨d⟩ over all permutations), ⟨d⟩ (the average swap distance), ⟨d⟩r (the expected value of ⟨d⟩ in a random permutation), ⟨d⟩max (the maximum value of ⟨d⟩ ) and Ω (the optimality of ⟨d⟩ ).
Figure 8: The distribution of gesture orders in each combination of language and reversibility condition. Languages are sorted by dominant order: SVO on the left (English and Russian) and VSO on the right (Irish and Tagalog).
Figure 9: The Hasse diagram of induced from acceptability ratings in Malayalam (blue) on the permutohedron (black). A blue arrow from vertex i to vertex j indicates that pi≥pj where pi is the acceptability rating of vertex i . The acceptability rating each order is shown near each vertex.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 10: Ωmin , a tight lower bound of Ω , when m , the number of non-zero probability orders, is 2 .
Figure 11: Ωmin ( Eq. A21 ) as a function of π1 and π2 . Red circles are used to indicate the corners of the triangle at (1/3,1/3) , (1/2,1/2) and (1,0) . Within the triangle, Ωmin was calculated by scanning exhaustively with a step of 10−3 for both variables.
Figure 12: The permutohedron of order 3. Vertices are labeled with consecutive numbers in a clockwise sense.
m
po(m)
pc(m)
1
1
1
2
2/5
2/5
3
1/10
3/10
4
1/30
2/5
5
1/60
1
6
1/60
1
Appendix
Table 3: po(m) , the probability that random arrangement is optimal assuming that there are no probability ties among the m non-zero probability orders ( Eq. 16 ), and pc(m) , the probability that a random arrangement is contiguous when the number non-zero probability orders is m ( Eq. A39 ).
Figure 13: Distinct ways of arranging m non-zero probability orders on the permutohedron ( m=3 on the left and m=4 on the right). The orders with non-zero probability are marked in red. (a) A contiguous arrangement where the multiset of swap distances is {1,1,2} . (b) A contiguous arrangement where the multiset of swap distances is {1,1,1,2,2,3} . (c) A non-contiguous arrangement where the multiset of swap distances is {1,2,3} . (d) A non-contiguous arrangement where the multiset of swap distances is {1,1,2,2,2,3} . (e) A non-contiguous arrangement where the multiset of swap distances is {2,2,2} . (f) Another non-contiguous arrangement where the multiset of swap distances is {1,1,2,2,3,3} .
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
Languages of the world vary concerning the order of subject, object and verb. The most frequent dominant orders are SOV and SVO, and researchers have tailored models to this fact. However, there are still languages whose dominant order does not conform to these expectations or even lack a dominant order. Here we show that across linguistic families and macroareas, word order variation within languages is shaped by the principle of swap distance minimization even when the dominant order is not SOV/SVO and even when a dominant order is lacking.
Jairo Rios-El-Yazidi, Ramon Ferrer-i-Cancho
Quantitative, Mathematical and Computational Linguistics Research Group, Department of Computer Science, Universitat Polit`ecnica de Catalunya, 08034 Barcelona, Catalonia (Spain)
Why do some languages like Czech permit free word order, while others like English do not? We address this question by pretraining transformer language models on a spectrum of synthetic word-order variants of natural languages. We observe that greater word-order irregularity consistently raises model surprisal, indicating reduced learnability. Sentence reversal, however, affects learnability only weakly. A coarse distinction of free- (e.g., Czech and Finnish) and fixed-word-order languages (e.g., English and French) does not explain cross-lingual variation. Instead, the structure of the word and subword vocabulary strongly predicts the model surprisal. Overall, vocabulary structure emerges as a key driver of computational word-order learnability across languages.
Jonas Mayer Martins, Jaap Jumelet, Viola Priesemann +1
University of Göttingen, Germany · University of Groningen, Netherlands · MPI for Dynamics and Self-Organization, Germany
We systematically compare word order preferences in decoder-only language models across 192 artificial languages and typologically diverse natural languages. On artificial languages, models exhibit a left-branching preference that aligns with neither natural language universals nor human word order learning biases. On natural languages, monolingual models show no clear base word order bias at small scales, but as data grows, a preference for right-branching subject-verb-object (SVO) languages emerges while SOV falls behind despite being the most frequent order cross-linguistically. This SVO advantage extends to multilingual models and correlates with language resource level and data quality rather than word order. Thus, the same architecture exhibits opposite preferences on artificial and natural languages, establishing that word order biases observed in practice are data-driven. Since highly-resourced languages are overwhelmingly SVO, these biases risk gradually reducing word order diversity, particularly in languages that productively use multiple word orders, with the widespread adoption of LLMs.
Varvara Arzt, Allan Hanbury, Terra Blevins
Faculty of Informatics, TU Wien · Khoury College of Computer Sciences, Northeastern University