SIGN: Schema Induced Games for Naming (Student Abstract)

Rongli Zhang, Herbert Woisetschläger

TL;DR

Large Language Model (LLM) agents often struggle to coordinate when communicating in open-ended natural language, leading to "linguistic drift" and inconsistent conventions. This paper introduces SIGN (Schema-Induced Games for Naming), demonstrating that enforcing a tiny bit of structure—a simple message schema—allows agents to reach consensus up to 5.8× more effectively and with an order of magnitude fewer tokens than unconstrained text.

What Problem Does This Paper Address?

In multi-agent systems (MAS), coordination is everything. If two LLM agents are collaborating on a coding task or a complex plan but use different names for the same variables or objects, the system fails. This is a modern version of the classic "Naming Game" in linguistics: how does a population of agents converge on a shared vocabulary?

While LLMs are great at following instructions, they are prone to verbosity and subtle variations in phrasing. In a decentralized population, these variations act as "noise" that prevents a stable convention from forming. The authors investigate whether a "lightweight schema"—a minimal structural requirement for messages—can act as a control knob to steer agents toward faster, more reliable agreement.

Methods

The researchers set up a naming game with populations of 12 and 24 agents (using the Phi-3 Mini 4K Instruct model). Agents are paired randomly over 300 rounds to agree on names for a fixed lexicon of items.

They compared three distinct communication conditions:

  1. Natural Language (NL): Agents talk freely; a decoder tries to extract the intended name.
  2. Natural Language Sliding Window (NL-SW): Agents have a memory ($K$) of their last few interactions with partners to guide their next proposal, but still use free-form text.
  3. Schema (SIGN): Agents are instructed to use a specific template: @say {name: Ck}. If an agent fails to use the format, they get one "retry" with a reminder. If they fail again, the system defaults to a random valid name to keep the game moving.

The experiment also varied the adoption probability ($\alpha$), which is the likelihood an agent will switch to their partner’s proposed name after a disagreement.

Datasets

As this is a simulation-based study on emergent behavior, the authors did not use a pre-existing external dataset. Instead, they utilized:

  • Synthetic Lexicons: A fixed set of $M=12$ names ($C_1, \dots, C_M$) that agents must learn to associate with objects.
  • Interaction Logs: The study generates its own data through the rounds of agent pairings, tracking agreement levels and token counts.

Key Insights and Ideas

  • Structure as an Inductive Bias: The schema acts as a "handle" for the agents. By reducing the "search space" of possible ways to say something, the schema provides a stable input for the agents' memory windows.
  • The "Control Knob" Effect: You don't need a complex, rigid protocol to improve coordination. A simple regex-parsable tag is enough to significantly shift the dynamics of the entire population.
  • Ambiguity Reduction: In pure natural language, an agent might say "I think we should call it X" or "Let's go with X." To an LLM's memory, these are different strings. The schema forces a uniform representation, making it much easier for agents to recognize patterns in their partners' behavior.
  • Token Efficiency: Coordination isn't just about if you reach agreement, but at what cost. Structured communication is vastly more "compressed" in terms of the information required to reach consensus.

Key Results

  • Higher Agreement: The Schema condition reached agreement levels of 0.6–0.65, whereas the NL-SW baseline peaked near 0.3, and pure NL stayed below 0.2.
  • Massive Speedup: The Schema condition achieved 50% population agreement using an order of magnitude fewer tokens than the natural language alternatives.
  • Scalability: Agreement remained stable when the population size doubled from 12 to 24 agents, suggesting the schema-induced benefit isn't just a fluke of small groups.
  • Consistency: Using a schema at a moderate adoption probability ($\alpha = 0.5$) produced the most consistent outcomes with the lowest standard deviation across different runs.

Limitations and Future Work

The authors acknowledge several areas for further exploration:

  • Model Diversity: The study focused on the Phi-3 Mini model. It remains to be seen if larger models (like GPT-4 or Llama 3) exhibit the same reliance on schemas or if they are "smart" enough to coordinate in pure NL.
  • Task Complexity: The naming game is a relatively simple coordination task. Future work could test if these schemas help in more complex scenarios, like hierarchical planning or multi-step reasoning.
  • Schema Flexibility: The current schema is very rigid. The authors suggest investigating "softer" or partially flexible schemas that might allow for more expressive communication while still maintaining the coordination benefits.
  • Lexicon Scaling: The experiments used a small lexicon ($M=12$). Testing how schemas perform as the vocabulary grows to hundreds or thousands of terms is a logical next step.

Summary updated

Abstract

Real-world AI systems are tackling increasingly complex problems, often through interactions among Large Language Model (LLM) agents. When these agents develop inconsistent conventions, coordination can break down. Applications such as collaborative coding and distributed planning therefore require reliable, consistent communication, and scalability is a central concern as systems grow. We introduce Schema-Induced Games for Naming (SIGN), a naming game that examines how lightweight structure can steer convention formation. We compare schema-induced communication to unconstrained natural language and find faster convergence with up to 5.8× higher agreement. These results suggest that minimal structure can act as a simple control knob for efficient multi-agent coordination, pointing toward broader applications beyond the naming game.
BibTeX
@inproceedings{zhang2026sign,
  author = {Rongli Zhang and Herbert Woisetschläger},
  title = {{SIGN: Schema Induced Games for Naming (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2026},
  doi = {10.1609/aaai.v40i48.42307},
}
Figure