Solution Space Topology Guides CMTS Search

• URL: http://arxiv.org/abs/2511.01701v1
• Date: Mon, 03 Nov 2025 16:09:00 GMT
• Title: Solution Space Topology Guides CMTS Search
• Authors: Mirco A. Mannucci,
• Abstract summary: Prior work applied topological features to guide Monte Carlo Tree Search (MCTS) in puzzle solving.<n>We identify the root cause: grid topology is constant across all instances.<n>We build this via compatibility graphs where nodes are $(cell, color)$ pairs and edges represent compatible assignments.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fundamental question in search-guided AI: what topology should guide Monte Carlo Tree Search (MCTS) in puzzle solving? Prior work applied topological features to guide MCTS in ARC-style tasks using grid topology -- the Laplacian spectral properties of cell connectivity -- and found no benefit. We identify the root cause: grid topology is constant across all instances. We propose measuring \emph{solution space topology} instead: the structure of valid color assignments constrained by detected pattern rules. We build this via compatibility graphs where nodes are $(cell, color)$ pairs and edges represent compatible assignments under pattern constraints. Our method: (1) detect pattern rules automatically with 100\% accuracy on 5 types, (2) construct compatibility graphs encoding solution space structure, (3) extract topological features (algebraic connectivity, rigidity, color structure) that vary with task difficulty, (4) integrate these features into MCTS node selection via sibling-normalized scores. We provide formal definitions, a rigorous selection formula, and comprehensive ablations showing that algebraic connectivity is the dominant signal. The work demonstrates that topology matters for search -- but only the \emph{right} topology. For puzzle solving, this is solution space structure, not problem space structure.

Related papers

• OFA-MAS: One-for-All Multi-Agent System Topology Design based on Mixture-of-Experts Graph Generative Models [57.94189874119267]
  Multi-Agent Systems (MAS) offer a powerful paradigm for solving complex problems.<n>Current graph learning-based design methodologies often adhere to a "one-for-one" paradigm.<n>We propose OFA-TAD, a one-for-all framework that generates adaptive collaboration graphs for any task described in natural language.
  arXiv  Detail & Related papers  (2026-01-19T12:23:44Z)
• Typed Topological Structures Of Datasets [0.0]
  A datatset $X$ on $R2$ is a finite topological space.<n>In this article, we develop a special set of types and its related typed topology on a dataset $X$.<n>Such structures provide a platform for new algorithms for problems such as calculating convex hull, holes, clustering and anomaly detection.
  arXiv  Detail & Related papers  (2025-08-19T17:14:13Z)
• Functional Matching of Logic Subgraphs: Beyond Structural Isomorphism [13.064477057274226]
  Subgraph matching is foundational for numerous Electronic Design Automation (EDA) applications.<n>We introduce the concept of functional subgraph matching, a novel approach that identifies whether a given logic function is implicitly present within a larger circuit.
  arXiv  Detail & Related papers  (2025-05-28T05:31:49Z)
• GMapLatent: Geometric Mapping in Latent Space [51.317738404571514]
  Cross-domain generative models based on encoder-decoder AI architectures have attracted much attention in generating realistic images.<n>We introduce a canonical latent space representation based on geometric mapping to align the cross-domain latent spaces in a rigorous and precise manner.<n>Experiments on gray-scale and color images validate the efficiency, efficacy and applicability of GMapLatent.
  arXiv  Detail & Related papers  (2025-03-30T12:02:36Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• The decomposition of the higher-order homology embedding constructed from the $k$-Laplacian [5.076419064097734]
  The null space of the $k$-th order Laplacian $mathbfmathcal L_k$ encodes the non-trivial topology of a manifold or a network. We propose an algorithm to factorize the homology embedding into subspaces corresponding to a manifold's simplest topological components.
  arXiv  Detail & Related papers  (2021-07-23T00:40:01Z)
• Inter-GPS: Interpretable Geometry Problem Solving with Formal Language and Symbolic Reasoning [123.06420835072225]
  We construct a new large-scale benchmark, Geometry3K, consisting of 3,002 geometry problems with dense annotation in formal language. We propose a novel geometry solving approach with formal language and symbolic reasoning, called Interpretable Geometry Problem solver (Inter-GPS) Inter-GPS incorporates theorem knowledge as conditional rules and performs symbolic reasoning step by step.
  arXiv  Detail & Related papers  (2021-05-10T07:46:55Z)
• Adaptive Linear Span Network for Object Skeleton Detection [56.78705071830965]
  We propose adaptive linear span network (AdaLSN) to automatically configure and integrate scale-aware features for object skeleton detection. AdaLSN substantiates its versatility by achieving significantly higher accuracy and latency trade-off. It also demonstrates general applicability to image-to-mask tasks such as edge detection and road extraction.
  arXiv  Detail & Related papers  (2020-11-08T12:51:14Z)
• DOTS: Decoupling Operation and Topology in Differentiable Architecture Search [115.89211594258573]
  Differentiable Architecture Search (DARTS) has attracted extensive attention due to its efficiency in searching for cell structures. We propose to Decouple the Operation and Topology Search (DOTS) to make an explicit topology search.
  arXiv  Detail & Related papers  (2020-10-02T13:00:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.