PaperlayerView exact revision on arXiv

Source-linked AI summary

Symbolic Guidance for LLM Agents in Distributed Multiagent Coordination

Ben Rachmut, Ning Zhang, Yevgeniy Vorobeychik, William Yeoh

arXiv:2609.31963v1cs.AI

TL;DR

Reliable distributed coordination remains challenging for LLM agents, which can interpret imprecise instructions but lack built-in consistency mechanisms. This paper introduces SGT to vary symbolic guidance across coordination tasks and finds that intermediate guidance levels perform best, with outcomes depending on algorithm structure and task context.

  • Problem

    LLM agents can handle incomplete or ambiguous instructions, but they lack built-in mechanisms for consistent coordination, leaving their reliability in distributed coordination an open challenge.

    Source: §1 · p. 2

  • Method

    The paper introduces SGT, varying symbolic guidance from open-ended reasoning to strict algorithmic execution, and evaluates it across graph coordination tasks and objectives.

    Source: §1 · pp. 2–3

  • Results

    Intermediate autonomy levels yield the strongest gains, especially with heuristic algorithms; guidance effects are context-dependent, and global-search guidance typically yields little to no improvement.

    Source: §6.3 · pp. 14–15, §7 · p. 16

  • Takeaways & Limitations

    Coordination performance depends on balancing symbolic structure with LLM flexibility, particularly by using guidance drawn from simpler, interpretable heuristics.

    Source: §7 · p. 16

    The reported Distributed DFS results are not necessarily optimal because Code agents, like LLM agents, were limited to the same number of communication rounds rather than running to convergence.

    Source: §6.2 · p. 14

Abstract

from arXiv · show

Large language models (LLMs) are increasingly deployed as autonomous agents in multi-agent systems, yet their ability to reliably execute distributed coordination protocols remains poorly understood. While AgentsNet, a benchmark framework for distributed coordination among LLM agents, enables such coordination, granting full reasoning autonomy often leads to inconsistent or degraded performance in complex domains. We hypothesize that coordination can be improved by regulating agent autonomy through symbolic guidance derived from established algorithms. To investigate this, we introduce the \emph{Symbolic Guidance Taxonomy (SGT)}, which characterizes a spectrum of autonomy ranging from open-ended natural language reasoning to fully prescribed algorithmic execution, with intermediate levels providing partial pseudocode guidance. Our results show that intermediate autonomy levels consistently outperform both unguided agents and fully prescriptive specifications. These findings identify autonomy regulation as a key design principle for LLM-based distributed coordination.

1 Introduction

Distributed coordination requires globally coherent behavior from agents making local decisions with limited information and communication. The paper introduces SGT to study symbolic guidance, finding that its effects depend on task difficulty and the balance between structure and flexibility.

1 Introduction

  • Symbolic solvers offer rigor but depend on complete problem formulations, whereas LLM agents handle imprecise instructions but lack built-in coordination guarantees.The paper frames these as complementary strengths to combine.Source: §1 · p. 2
  • SGT places LLM agents on an autonomy spectrum from open-ended reasoning to strict algorithmic adherence, using symbolic guidance to regulate their autonomy.The framework is inspired by adjustable autonomy.Source: §1 · p. 2
  • The evaluation varies guidance and algorithmic structure across graph coloring, matching, and vertex cover, each with local and global objectives.It enables comparisons across LLM families, task types, and autonomy regimes.Source: §1 · pp. 2–3
  • Structured scaffolding improves coherence and stability on harder global objectives, while excessive prescription can reduce adaptability on simpler tasks.The balance between symbolic control and LLM autonomy is context-dependent rather than binary or monotonic.Source: §1 · p. 3
  • The paper identifies SGT, a unified evaluation framework, analysis of algorithm-guidance interactions, and empirical design principles as its contributions.The stated goal is actionable insight for deploying multiagent LLM systems in distributed environments.Source: §1 · p. 3

2 Background

The paper studies graph-based coordination through three benchmark domains and contrasts local heuristic algorithms with global distributed search. Local variants rely on neighborhood information, while global variants require network-wide coordination.

2 Background

  • Distributed coordination is modeled on graphs, with agents as vertices exchanging messages with neighbors to produce globally consistent outcomes.The background contrasts decentralized local heuristics with global search, which offers stronger optimality guarantees but requires more coordination and communication.Source: §2 · p. 3

2.1 Benchmark Domains and Variants

  • Graph coloring, matching, and vertex cover each have local variants solvable from neighborhood information and global variants requiring network-wide consistency.The examples distinguish (∆+ 1)-coloring from 3-coloring, maximal from maximum matching, and minimal from minimum vertex cover.Source: §2.1 · p. 4

2.2 Algorithmic Approaches

  • The Maximal Independent Set (MIS) heuristic supplies local rules across all three domains, using priority ordering and neighborhood information.These MIS-based rules admit distributed algorithms running in O(log n) rounds, where n is the number of graph nodes.Source: §2.2 · p. 4
  • Distributed Depth-First Search (DFS) enforces a strict global order and backtracks on conflicts to find optimal colorings, matchings, or vertex covers.Its exhaustive search takes O(b^n) runtime, where b is the branching factor, and may be impractical at large scale.Source: §2.2 · p. 5

3 Related Work

Prior work established open-ended LLM coordination benchmarks and hybrid symbolic-neural coordination frameworks. This paper instead varies symbolic guidance provided to LLM agents, drawing on adjustable autonomy’s emphasis on intermediate control strategies.

3 Related Work

  • AgentsNet benchmarks open-ended LLM coordination by providing task descriptions and communication channels while leaving solution strategies to the agents.This work extends that platform to harder global variants, including 3-coloring, maximum matching, and minimum vertex cover.Source: §3 · p. 5
  • VL-DCOPs combine symbolic solvers and LLMs in hybrid roles, whereas this work varies the symbolic guidance given to LLM agents themselves.VL-DCOPs extend Distributed Constraint Optimization Problems, which model agents assigning variables to minimize shared constraint costs.Source: §3 · pp. 5–6
  • Adjustable autonomy studies how decision-making control shifts with context; earlier transfer-of-control work found intermediate strategies preserve local decision quality and global team coherence.The paper adapts this principle by treating symbolic instruction as varying degrees of autonomy.Source: §3 · p. 6

4 Symbolic Guidance Taxonomy

The Symbolic Guidance Taxonomy specifies which parts of a symbolic algorithm agents receive and how those parts are represented. It frames guidance as a spectrum of autonomy, from unguided reasoning to direct algorithm execution, with intermediate forms illustrated through a graph-coloring procedure.

4.1 Formal Definition

  • A guidance strategy maps selected parts of an algorithm and their encoding into the guidance block provided to each agent.Selection identifies which algorithm components are shared; encoding specifies their representation, such as pseudocode or natural-language description.Source: §4.1 · p. 7

4.2 Autonomy Spectrum of Agent Types

  • SGT ranges from maximized autonomy without symbolic guidance to fixed-protocol execution, with intermediate scaffolding leaving agents flexibility to fill in details.The spectrum includes unguided AgentsNet agents, guided LLM agent types, and a Code baseline that executes the algorithm without an LLM.Source: §4.2 · pp. 7–8, Figure 1 · p. 8
  • The guidance types reveal different algorithm components: function descriptions give natural-language helper behavior, function pseudocode gives helper implementations, and main pseudocode gives the main procedure while leaving helpers unspecified.Full-pseudocode agents receive the complete algorithm; the function-description agents retain flexibility over implementation.Source: §4.2 · pp. 7–8

4.3 Illustrative Example

  • The MIS coloring example varies guidance for a proposal step, from an ambiguous natural-language helper description to pseudocode or a high-level main-procedure directive.Full pseudocode includes the overall outline and helper function, leaving minimal room for interpretation.Source: §4.3 · pp. 8–9

5 Experimental Design

The experimental design varies symbolic guidance, algorithms, graph topologies, and LLM models across distributed coordination tasks. It uses a unified SSE metric to evaluate deviations from correctness or optimality.

Experimental Simulator

  • Experiments use the AgentsNet benchmark implementation, extended with global variants and systematic variation of symbolic guidance through SGT.The extension adds 3-coloring, maximum matching, and minimum vertex cover.Source: §5 · p. 9

Graph Topologies

  • The evaluation covers small-world, scale-free, and Delaunay graph families, spanning clustered, hub-dominated, and spatially local structures.Graphs are generated using the original benchmark code with NetworkX.Source: §5 · p. 9
  • Each topology contributes five graphs of 16 nodes, for 15 networks total, and experiments use 2D+1 synchronous message-passing rounds.D is the graph diameter; the same number of rounds is used across experiments to isolate the effect of symbolic guidance.Source: §5 · p. 9

Algorithm Choices

  • Local variants use MIS guidance, while global variants use either MIS or Distributed DFS guidance.Local tasks are (∆+1)-coloring, maximal matching, and minimal vertex cover; global tasks are 3-coloring, maximum matching, and minimum vertex cover.Source: §5 · p. 10

LLM Models

  • Three models are tested: Llama-3.1-8B Instruct, Qwen-2.5-7B Instruct, and Gemini-2.5 Flash.The first two are served locally via Ollama; Gemini is accessed via OpenRouter and is identified by AgentsNet as Pareto-optimal in accuracy-cost trade-offs.Source: §5 · p. 10

Evaluation Metrics

  • A unified Sum of Squared Error metric captures deviations from correctness or optimality across the three domains.The supplied design passages define local coloring, matching, and vertex-cover errors using invalid edges or vertices.Source: §5 · p. 10

6 Experimental Results

Across coordination settings, intermediate, function-based guidance often performs best, but outcomes depend on the model and algorithm. Local heuristic guidance shows clearer benefits than guidance for global search, where results are mixed.

6.1 Local Coordination Problems

  • Locally, function-based guidance performs best for coloring and maximal matching, while guidance makes little difference to feasible minimal vertex-cover instances.Llama guidance significantly beats AgentsNet, Qwen shows no significant separation, and some guided settings fall below AgentsNet.Source: §6.1 · pp. 12–13

6.2 Global Coordination Problems

  • With global MIS, Gemini function-pseudocode agents perform best in 3-coloring and maximum matching, while function-description agents lead in minimum vertex cover.Gemini outperforms Llama and Qwen across the three domains; Llama guidance generally improves on AgentsNet, while Qwen shows no statistical difference.Source: §6.2 · p. 13
  • The Code agent has non-zero error on global MIS tasks because MIS does not guarantee optimal solutions when global coordination is required.Unlike local MIS variants, the global tasks require optimal solutions, which the algorithm does not guarantee.Source: §6.2 · p. 13
  • With Distributed DFS, guidance has no benefit for Gemini 3-coloring, but function-description helps maximum matching and full pseudocode helps minimum vertex cover.Some Gemini agent types outperform the round-limited Code baseline; its usual optimality guarantee does not apply when communication rounds are restricted.Source: §6.2 · p. 14

6.3 Discussion

  • Gemini is more consistent at leveraging symbolic structure, and the effects of guidance depend jointly on the model, algorithm, and guidance form.Gemini shows lower errors and more stable performance across guidance levels than the other tested models.Source: §6.3 · p. 14

6.2 Global Coordination Problems

  • In most experimental settings, function-description and function-pseudocode agents with intermediate autonomy are most effective.Table 1 consolidates Gemini-2.5 results across tasks and algorithms; its caption identifies the reported measure as mean ln(1 + SSE) ± SEM.Source: §6.2 · p. 14, Table 1 · p. 15

6.3 Discussion

  • Across algorithms, local heuristic scaffolds more often help, whereas Distributed DFS guidance yields mixed results and often no statistically significant differences.Detailed guidance can help or hinder on Distributed DFS tasks; for local MIS heuristics, excessive procedural detail can degrade performance.Source: §6.3 · pp. 14–15

7 Conclusions

The paper introduces SGT as a way to characterize and regulate autonomy in LLM-based multiagent coordination. Its experiments find that intermediate guidance often works best, especially when derived from heuristic algorithms, while global-search guidance typically offers little improvement.

7 Conclusions

  • SGT frames symbolic guidance as a controllable mechanism for positioning LLM agents along an autonomy continuum.The framework analyzes how symbolic structure shapes intelligence and coordination in multiagent systems.Source: §7 · p. 16
  • The evaluation spans graph coloring, matching, and vertex cover, comparing six LLM agent types and local heuristics with global distributed search.The experiments examine how symbolic representation and autonomy interact with coordination quality.Source: §7 · p. 16
  • Coordination performance does not improve monotonically with more guidance or greater autonomy; intermediate autonomy yields the strongest gains, mainly with heuristic algorithms.Guidance based on global search typically produces little to no improvement.Source: §7 · p. 16
  • The authors propose extending SGT to mixed-autonomy teams and developing guidance that adjusts autonomy as tasks and coordination demands change.The proposed future work would let agents operate at different autonomy levels based on role or local context.Source: §7 · p. 16
Loading 2609.31963v1…