A Neurosymbolic Fast and Slow Architecture for Graph Coloring

Published in Twelfth Annual Conference on Advances in Cognitive Systems (ACS), 2025

SOFAI-v2 combines fast LLM search with strict metacognitive checking and symbolic fallback to solve fixed-k graph coloring under exact constraint requirements.

Why it matters

Constraint satisfaction problems require strict constraint adherence, but LLM-only solving is often unreliable on exactness requirements, while symbolic search can be slow.
This work focuses on graph coloring in fixed-k decision form, where correctness is directly verifiable and supports systematic iterative guidance.
The fast/slow setup addresses the practical gap between LLM speed and adaptability versus symbolic correctness on hard constraint-heavy instances.

What we did

Introduced SOFAI-v2, extending SOFAI-v1 with iterative metacognitive governance over a fast solver (S1) and a slow fallback (S2).
S1 = Mistral-7B proposes candidate colorings; the metacognition module verifies each output with a polynomial-time correctness score based on edge conflicts.
When incorrect, metacognition generates template-based feedback listing conflicting adjacent vertex pairs, and can add guiding examples with episodic-memory context for the next S1 attempt.
If no improvement is observed after 5 iterations (or the score remains below threshold), the controller invokes S2 = DSATUR with backtracking.
Under a strict 200-second per-instance budget, evaluation reports a 10.5% higher success rate and up to 30% faster solving versus a traditional symbolic baseline, on instances up to 50 vertices.

SOFAI-v2 architecture with metacognitive verification, iterative S1 feedback, and fallback to S2 DSATUR with backtracking. — Figure 1. SOFAI-v2's metacognitive controller verifies S1, iterates with feedback, and escalates to S2 when needed.

The architecture diagram clarifies how verification and fallback are wired into the loop.

How it works

S1 proposes a k-coloring (or NOT SOLVABLE) from a structured DIMACS prompt.
Metacognition computes a constraint-adherence score by checking edge conflicts; only perfect adherence is accepted.
If incorrect, metacognition generates template feedback listing conflicting adjacent vertex pairs.
The controller can add simplified subgraph examples and retrieve similar past instances from episodic memory.
If progress stalls across iterations, metacognition invokes S2 (DSATUR with backtracking) as fallback.

Figure 2a showing impact of metacognitive feedback iterations on solvable graph-coloring instances. — Figure 2. Iterative metacognitive feedback improves S1 success across solvable (a), unsolvable (b), and mixed (c) settings.

Figure 2b showing impact of metacognitive feedback iterations on unsolvable graph-coloring instances. — Figure 2. Iterative metacognitive feedback improves S1 success across solvable (a), unsolvable (b), and mixed (c) settings.

The iteration plot shows why multiple feedback rounds matter, not just a single retry.

Key contributions

A SOFAI-v2 control loop coupling LLM proposals with polynomial-time verification and feedback.
An episodic-memory retrieval mechanism to condition S1 with similar solved instances.
An empirical study showing improved success rate and time efficiency versus S1, S2, and SOFAI-v1 baselines.
An analysis of how iterative feedback rounds change success behavior across graph-size and solvability regimes.

Graph Size	m(100,0) [%]				m(0,100) [%]				m(50,50) [%]
Graph Size	S1	S2	SOFAI-v1	SOFAI-v2	S1	S2	SOFAI-v1	SOFAI-v2	S1	S2	SOFAI-v1	SOFAI-v2
5	9.41	100	100	100	75	100	100	100	45.36	100	100	100
10	0	100	100	100	60.38	100	100	100	39.39	100	100	100
15	0	80	80	80	37.50	77.08	89.58	93.75	17.65	77.45	83.33	84.31
20	0	5	5	7.29	45.65	4.35	47.83	76.09	22.58	3.06	24.73	38.95
30	0	0	0	0	54.17	0	62.50	72.92	28.89	0	33.71	38.89
40	0	0	0	0	33.33	0	47.37	47.37	17.43	0	24.55	24.77
50	0	0	0	0	3.85	0	3.85	53.85	2.11	0	2.11	27.72

Table 2. Success-rate breakdown showing where SOFAI-v2 gains appear as size and solvability mix become harder.

The success-rate table makes the gains most visible on larger, mixed, and unsat-heavy settings.

Recommended citation: Vedant Khandelwal, Vishal Pallagani, Biplav Srivastava, and Francesca Rossi. (2025). "A Neurosymbolic Fast and Slow Architecture for Graph Coloring." Twelfth Annual Conference on Advances in Cognitive Systems (ACS).
Download Paper | Download Slides