# A Neurosymbolic Fast and Slow Architecture for Graph Coloring

arXiv: https://arxiv.org/abs/2412.01752 · HTML: https://mlsanity.com/paper/2412.01752/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 2 Dec 2024.

## Builds on (most cited first, 13 of 13)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [SwiftSage: A Generative Agent with Fast and Slow Thinking for Complex Interactive Tasks](https://mlsanity.com/paper/2305.17390/) (2023)
- [On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks](https://mlsanity.com/paper/2402.08115/) (2024)
- [FollowBench: A Multi-level Fine-grained Constraints Following Benchmark for Large Language Models](https://mlsanity.com/paper/2310.20410/) (2023)
- [Can Large Language Models Reason and Plan?](https://mlsanity.com/paper/2403.04121/) (2024)
- [Thinking Fast and Slow in AI](https://mlsanity.com/paper/2010.06002/) (2020)
- [PiVe: Prompting with Iterative Verification Improving Graph-based Generative Capability of LLMs](https://mlsanity.com/paper/2305.12392/) (2023)

## Built on by (most cited first, 1 of 1)

- [Benchmarking graph construction by large language models for coherence-driven inference](https://mlsanity.com/paper/2502.13953/) (2025)

## Abstract (arXiv)

Constraint Satisfaction Problems (CSPs) present significant challenges to artificial intelligence due to their intricate constraints and the necessity for precise solutions. Existing symbolic solvers are often slow, and prior research has shown that Large Language Models (LLMs) alone struggle with CSPs because of their complexity. To bridge this gap, we build upon the existing SOFAI architecture (SOFAI_v1), which adapts Daniel Kahneman's ''Thinking, Fast and Slow'' cognitive model to AI. Our enhanced architecture, SOFAI_v2, integrates refined metacognitive governance mechanisms to improve adaptability across complex domains, specifically tailored here for solving the graph coloring problem, a specific type of CSP. SOFAI_v2 combines a fast System 1 (S1), leveraging LLMs, with a deliberative System 2 (S2), governed by a metacognition module. S1's initial solutions, often limited by constraint adherence issues, are improved through targeted feedback and examples from metacognition, aligning S1 more closely with CSP requirements. If S1 fails to resolve the problem, metacognition strategically invokes S2, ensuring accurate and reliable solutions. Our empirical results demonstrate that SOFAI_v2 achieves a 10.5% higher success rate and is up to 30% faster than a traditional symbolic solver in solving graph coloring problems.