LoopBench: Discovering Emergent Symmetry Breaking Strategies with LLM Swarms

The article introduces LoopBench, a benchmark to evaluate Large Language Models (LLMs) in distributed symmetry breaking and meta-cognitive reasoning tasks. The benchmark focuses on coloring odd cycle graphs with limited colors, where standard LLMs and classical heuristics struggle, but advanced reasoning models can devise strategies to escape deadlocks.

Details

The article presents LoopBench, a new benchmark designed to evaluate the ability of Large Language Models (LLMs) to coordinate in distributed systems and engage in meta-cognitive reasoning. The benchmark focuses on the task of coloring odd cycle graphs (such as C3, C5, C11) with a limited number of colors, where deterministic, non-communicating agents can get stuck in infinite loops. To address this, LoopBench implements a strategy passing mechanism as a form of consistent memory. The authors show that while standard LLMs and classical heuristics struggle with this task, more advanced reasoning models, such as O3, are able to devise strategies to escape the deadlocks. LoopBench offers a testbed for studying emergent distributed algorithms based on language-based reasoning, providing insights into the collective intelligence capabilities of LLM swarms.