Agent-based imitation dynamics can yield efficiently compressed population-level vocabularies
Authors: Nathaniel Imel, Richard Futrell, Michael Franke, Noga Zaslavsky
Organizations: Department of Psychology, New York University · Department of Language Science, University of California, Irvine · Department of Linguistics, University of Tübingen
Natural languages have been argued to evolve under pressure to efficiently compress meanings into words by optimizing the Information Bottleneck (IB) complexity-accuracy tradeoff. However, the underlying social dynamics that could drive the optimization of a language's vocabulary towards efficiency remain largely unknown. In parallel, evolutionary game theory has been invoked to explain the emergence of language from rudimentary agent-level dynamics, but it has not yet been tested whether such an approach can lead to efficient compression in the IB sense. Here, we provide a unified model integrating evolutionary game theory with the IB framework and show how near-optimal compression can arise in a population through an independently motivated dynamic of imprecise strategy imitation in signaling games. We find that key parameters of the model -- namely, those that regulate precision in these games, as well as players' tendency to confuse similar states -- lead to constrained variation of the tradeoffs achieved by emergent vocabularies. Our results suggest that evolutionary game dynamics could potentially provide a mechanistic basis for the evolution of vocabularies with information-theoretically optimal and empirically attested properties.
Figures & tables
Figure 1: A. The IB communication model of Zaslavsky et al. (2018) , see Section 2.1 for details. B. Communication model unifying noisy sim-max games with the IB framework. We illustrate our model on a semantic domain similar to numerals, and depict states as cards with varying quantities of dots, and meanings as (conditional) belief distributions about these states. We denote the (symmetric) noisy perception and interpretation of states as p . C. The imprecise conditional imitation dynamic ( Franke and Correia, 2018 ) . See main text and Appendix A for details.
Figure 2: Emergent efficient semantic systems. A : Converged systems on the information plane, colored by the pragmatic standard of precision γ in the sim-max game. Circles denote systems evolved from our model, derived from Franke and Correia (2018) , abbreviated as FC18. See Movie 1 visualizing the dynamics on the plane. Gray circles mark the result of permuting the systems evolved from the FC18 dynamics (see Appendix D ). Gray triangles correspond to emergent systems evolved from a dynamic proposed in Nowak and Krakauer (1999) , abbreviated as NK99, which we consider as another baseline. B : Game pragmatic standard of precision ( γ , Equation 6 ) vs. efficiency loss ( ϵ , Equation 17 ) of converged systems. Mean scores for systems emerging from our model are depicted in blue while mean scores for permuted counterparts are in gray. Shaded regions correspond to the 95% confidence interval. The inset shows a zoomed-in view of the emergent systems’ scores only.
Figure 3: Sample of converged emergent systems and their optimal counterparts. A - C : 1-dimensional mode maps of converged system for γ=0.001,0.01,10 ( Equation 6 ). In each plot, the x -axis denotes the meaning space Xo={0,…,99} , the y -axis denotes probability S(w∣mo) , and lines are the modal word w (out of 100 possible words) used for each meaning mo=xo . The color of each line corresponds to the average meaning that the word is used to communicate, with black corresponding to x1 and bright orange corresponding to x100 . D - F : Mode maps for the optimal counterparts of the emergent systems in D - F , fitted by efficiency loss ϵ ( Equation 17 ). See Movie 2 for the evolution of the system in A .
Figure 4: Complexity (A), accuracy (B), population fitness (C), and efficiency loss (D), relative to game pragmatic standard of precision ( γ ) across discrete time step of simulated evolution. Lines in each plot show mean (with 95% CIs) across eight random seeds. Color corresponds to γ ( Equation 6 ).
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: The imprecise conditional imitation dynamic ( Franke and Correia, 2018 ) . The frequency of word w being used to communicate state xoim at the next time step grows in proportion to (i) the expected frequency of w given that xoim was observed by some (randomly sampled) imitating Sender, times (ii) the expected utility of this word relative to the population of Receivers. Likewise, the frequency of interpreting w as meaning x^oim grows in proportion to (i) the probability that x^oim is observed by a randomly sampled agent imitating a randomly sampled Receiver that actually realized x^a after receiving word w , times (ii) the expected utility of the interpretation x^oim given w . See Equations 11 , 12 , 13 , 14 , 15 and 16 for the details of these conditional expectations.
Notation
Interpretation
xa
actual state
xo
Sender’s observed state
xoim
an imitating Sender’s observed state
mo(xa)≡p(xa∣xo)
observation noise / belief state
p(mo)
communicative need distribution
w
signal
Appendix
Table 1: Mapping between our notation, Franke and Correia (2018) ’s notation, and Zaslavsky et al. (2018) ’s notation.
Figure 6: Monotonic relationship between γ and β .
Si,mw(t+1)←Sample from {Sp,mw(t)},Ri,wm(t+1)←Sample from {Rp,wm(t)}
Appendix
Algorithm 1 Evolutionary Dynamics for Signal-Object Associations
How do two agents invent a shared language from scratch? In a Lewis signaling game, a sender and receiver must coordinate on a code using only their interaction history. We study five memory architectures across varying channel configurations with LLM agents and find that memory architecture matters more than channel capacity. Agents with a persistent private notebook benefit from surplus channel capacity and avoid the high-capacity collapse seen in stateless agents, achieving the most reliable coordination (0.867±0.023 at capacity = 25). Stateless agents peak at moderate capacity and then degrade as the vocabulary grows beyond what a rolling context window can track The notebook externalizes learned conventions, freeing agents from having to re-derive codes each round. An information bottleneck-inspired argument predicts an optimal capacity equal to the number of objects. Instead, the bottleneck (capacity = 8) proves to be a fragility point, and surplus capacity is generally better. We show that channel capacity alone cannot predict coordination; memory architecture determines whether agents turn interaction history into stable conventions, and both dimensions are needed to understand how signals become language.
Yashar Talebirad, Eden Redman, Ali Parsaee +1
Alberta Machine Intelligence Institute, University of Alberta, Edmonton, Canada · Network for Applied Technology, Edmonton, Canada
The structure of naming systems in natural languages hinges on a trade-off between high informativeness and low complexity. Focusing on the domain of kinship naming, we analyze such trade-off while addressing simplifying assumptions of prior work, namely: (i) universal communicative need across languages, and (ii) optimal listeners. To that aim, we collect data from four different languages, and analyze how different communicative needs and variations in the listener model influence the informativeness--complexity trade-off. Adopting a referential game setup from emergent communication, we further show that trade-off optimality is not only theoretically achievable but also emerges empirically in learned communication systems.
Phong Le, Mees Lindeman, Raquel G. Alhama
University of St Andrews · Institute for Logic, Language and Computation; University of Amsterdam.
Dynamic vocabularies built on-the-fly via Lempel-Ziv-Welch (LZW) compression let a language model represent the same text in fewer tokens, but prior work shows that this efficiency comes at a cost to reasoning and perplexity. We show that this quality gap is not a fundamental price of compression but can be substantially closed through targeted improvements to the compression layer and LZW codec, without modifying the underlying pretrained language model. Our analysis reveals four key issues: (1) LZW's compression algorithm creates an implicit conflict between the input embedding and the output embedding, a tension that a single shared embedding cannot resolve; (2) naively applying RoPE to LZW-compressed sequences ignores that merged tokens can span multiple tokens; (3) merging certain tokens (notably digits) disproportionately hurts downstream accuracy; and (4) dynamic vocabularies introduce an inherent segmentation ambiguity that confounds standard evaluation. We address these through decoupled input/output dynamic embedding layer, size-aware RoPE positioning, and a modified LZW codec supporting selective merges and multi-view segmentations. Across four models, our recipe improves perplexity on every corpus we evaluated as well as mathematical reasoning accuracy, closing roughly half the quality gap between zip2zip and the uncompressed baseline at a similar compression ratio on general text. This represents a significant step toward lossless adaptive-vocabulary compression for language models.
Saibo Geng, Andrea Gentilini, Xinxian Ma +3
EPFL · Technical University of Munich · Zuse School ELIZA +1