SIGN: Schema-Induced Games for Naming

AI summary

Overview

Research area: Multi-agent AI systems and emergent communication, specifically how large language model (LLM) agents converge on shared naming conventions.

Technical level: Intermediate. The core idea is intuitive and the experiments are small-scale, but familiarity with LLM agents, tokenization, and basic game-theoretic simulation helps.

Scope: This paper introduces a lightweight, schema-constrained messaging protocol for a population naming game and measures whether that minimal structure speeds up and improves convention formation among LLM agents.

What This Paper Is About

When multiple LLM agents work together, they need to agree on names for things — variables, tasks, plan steps, entities. If each agent invents its own vocabulary, coordination breaks down. Prior work shows that shared conventions can emerge purely from interaction, and separately that structured output formats like JSON help LLM reliability, but nobody had tested whether a tiny structural constraint on messages could steer how conventions form. This paper asks whether imposing a minimal schema (a fixed @say {name: Ck} format) makes a simulated population of LLM agents reach agreement faster and more completely than free-form natural language.

Key Contributions

1. A new minimal-protocol naming game (SIGN) that places LLM agents in a population naming game and compares three conditions: unconstrained natural language (NL), natural language with a sliding memory window (NL-SW), and a schema-constrained condition requiring responses in the form @say {name: Ck}.
2. A concrete schema-induction algorithm with a regex parser, a single retry-with-reminder for non-compliant outputs, and a fallback to random valid names for persistent non-compliance — designed to be model-agnostic and low-overhead.
3. Empirical demonstration that structure alone drives convergence: schema induction produces up to 5.8× higher population agreement and roughly an order of magnitude fewer tokens to reach 50% agreement compared to unconstrained natural language, with the advantage persisting at 60% and 70% agreement thresholds.
4. Cross-model and mixed-population validation using Phi-3 Mini 4K Instruct, Llama 3.2 3B Instruct, and a heterogeneous 6/6 mixture — showing the schema benefit is not tied to a single model family.

Main Findings

• Schema substantially raises agreement: Under Phi-3, the schema condition reached population agreement around 0.6–0.65, versus peaks near 0.3 for NL-SW and below 0.2 for plain natural language — a 5.8× improvement in the best case.
• Faster convergence: Schema reached 50% agreement with roughly an order of magnitude fewer tokens than NL or NL-SW. At a 60% threshold, schema needed nearly two orders of magnitude fewer tokens than NL-SW, while NL never reached it. At 70%, only schema converged at all.
• Gains come from the schema, not from scale: Agreement was stable across N=12 and N=24 and only modestly changed from K=5 to K=10 memory, indicating the benefit is attributable to the schema rather than population size or memory depth.
• Higher adoption probability slightly hurts: Increasing the lose-shift probability α (0.5 → 0.75 → 0.9) slightly lowered final agreement for both NL-SW and schema, suggesting aggressive name-switching can be counterproductive.
• Schema reduces variance over time: Standard deviation of agreement narrowed as the run progressed, with schema at α=0.5 producing the most consistent outcomes.
• Model family matters but schema still wins: With Llama 3.2 3B Instruct, schema agreement rose to roughly 0.75–0.8 versus 0.65–0.7 for NL/NL-SW — overall higher than the Phi-3 runs at comparable model size, indicating family-specific dynamics.
• Robust to heterogeneous populations: In a mixed population of 6 Phi-3 and 6 Llama agents (capped at 100 rounds due to time limits), schema still produced clearly higher agreement than NL or NL-SW.

Methodology in Plain English

The setup is a classic naming game. A fixed pool of agents shares a small vocabulary of 12 possible names. Play proceeds in rounds: two agents are randomly paired, each sees its last few partner-only interactions (a memory window of size 5 or 10), and each produces a message. A decoder tries to extract the name the agent intended. If the two agents propose different names, one of them adopts the partner's name with probability α (the "lose-shift" probability).

Three variants were compared:

• NL: agents speak freely in natural language; the decoder tries to pull a valid name out of whatever they said.
• NL-SW: same, but proposals are conditioned on the agent's memory window.
• Schema: agents must reply in the exact form @say {name: Ck}. A regex parser extracts the name. If the reply doesn't match, the agent gets one retry with a reminder. If it still fails, the output is treated as random and marked non-compliant.

They ran populations of 12 and 24 agents over 300 rounds, with vocabulary size 12, memory windows of 5 and 10, and adoption probabilities of 0.5, 0.75, and 0.99, using three random seeds per configuration. The primary model was Phi-3 Mini 4K Instruct with fixed decoding parameters (max 32 new tokens, temperature 0.7, top-p 0.9, repeat penalty 1.1), with follow-up runs on Llama 3.2 3B Instruct and a mixed population. Tokens-to-convergence — the number of tokens generated before the population reached a given agreement level — was the efficiency metric.

Why This Matters

Impact on research: The paper isolates a single, cheap variable — message format — and shows it measurably steers emergent convention formation. This bridges two largely separate lines of work (emergent communication in multi-agent LLM societies and structured-output prompting) and suggests that protocol design, not just model capability, is a lever for coordination. It also offers a lightweight, reproducible testbed (code is public) for studying multi-agent language dynamics.

Real-world applications:

• Collaborative coding agents: multiple LLM agents editing a shared codebase need consistent naming for functions, variables, and files; a schema for identifier proposals could reduce merge conflicts and miscommunication.
• Distributed planning and task decomposition: agent swarms delegating subtasks benefit from a fixed message format for task labels, reducing ambiguous handoffs.
• Tool and API invocation: standardizing how agents name tools or parameters in a @call {tool: X}-style schema could reduce malformed calls and retries.
• Robotics and multi-robot coordination: heterogeneous robots with different underlying models could use a minimal shared naming schema to align on object or location references.

Industry relevance: As enterprises move from single-LLM pipelines to multi-agent orchestration frameworks, communication protocols become a practical bottleneck. This paper suggests that a one-line schema constraint — far cheaper than fine-tuning or heavy prompt engineering — can be a control knob for reliability and token cost. The token-efficiency gains are directly relevant to inference cost at scale, and the cross-vendor and mixed-model results matter for organizations deploying agents from multiple providers.

Future Directions

1. Does schema reduce response diversity? The authors flag the open question of whether schema-induced consistency narrows the range of agent outputs in ways that could hurt performance on open-ended tasks.
2. Scaling the experiments: testing larger populations, bigger lexicons, longer runs, and more than two model families in the mixed condition.
3. Alternative schema designs: exploring how different structural formats (richer JSON, nested templates, hierarchical tags) affect convergence, and whether there are diminishing or negative returns from more structure.
4. Beyond the naming game: determining whether the steering effect generalizes to other coordination problems such as negotiation, task allocation, or distributed planning.

Target Audience

This paper suits researchers and graduate students working on multi-agent LLM systems, emergent communication, and language evolution simulations. It is also useful for practitioners building agent orchestration frameworks who want an evidence-backed reason to standardize message formats. The small scale and clear methodology make it accessible to advanced undergraduates and to engineers without a deep theory background, though readers should be comfortable with LLM prompting and basic simulation concepts.

Authors’ 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.8x 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.