# Neurosymbolic Discovery of Algebraic Graph Constructions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 17 references that are in the map.
- First posted on arXiv 8 Aug 2026.

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

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [The SAT+CAS Method for Combinatorial Search with Applications to Best Matrices](https://mlsanity.com/paper/1907.04987/) (2019)

## Abstract (arXiv)

There are several methods for searching for graphs with prescribed properties, such as SAT solvers and specialized generators. These methods return the result as raw data: an adjacency matrix or a string encoding. The raw data certifies that the graph exists, but it does not reveal any structural properties of the graph. We ask whether one can automatically discover a short algebraic description if only this raw data is provided. We look for a description such as a Cayley graph Cay(Gamma, S) or a lexicographic product C5[K3]. We address this question with a neurosymbolic approach. We propose an agent that runs on a general-purpose large language model with no fine-tuning or per-target training. The model interleaves reasoning with calls to the computer algebra system SageMath: it analyzes the target graph, proposes and tests candidate constructions, and revises them until the output matches the target. The agent communicates with SageMath through a Model Context Protocol (MCP) server, which we release as a general-purpose bridge. Whether a construction matches the target is checked by a single exact isomorphism test, and therefore rests on the symbolic side and not on the model. We test the approach on a benchmark of 100 highly symmetric graphs, namely two-orbit graphs on up to 25 vertices; the benchmark was fixed in advance. Our agent could find verified algebraic constructions for all of them, without falling back to raw encodings. A strong template-enumeration baseline reaches only about 20%, and a catalog lookup could not identify any of these graphs. However, construction quality declines when symmetry is removed. As a concrete application, we identify the smallest known counterexample to the Bernhart-Kainen dispersability conjecture, a 16-vertex graph that enumeration found as raw data. For this graph, our agent found an explicit algebraic construction.