SailSearch: Agent-Assisted Discovery in Combinatorial Optimization
Authors: Dhriti Verma, Kanthi Sarpatwar, Vinicius Lima, Dzung Phan, Jayant Kalagnanam
Subjects: Artificial Intelligence (cs.AI)
arXiv: 2611.25087 [cs.AI] — Submitted 18 November 2026
DOI: https://doi.org/10.48550/arXiv.2611.25087
Overview
This paper presents SailSearch, a human-guided workflow for algorithmic research that pairs two language-model agents with researcher oversight, and reports results on two challenging combinatorial optimization problems: Market Split and maximum independent set (MIS). Against the backdrop of 2026's rapid maturation of agentic AI systems for scientific discovery, SailSearch demonstrates how LLM agents can be integrated into the algorithmic research loop to produce concrete, benchmark-level advances.
Market Split Results
For Market Split, SailSearch employs a randomized algorithm that searches across multiple lattice bases, dividing computation between enumeration and continued basis reduction. Across ten random seeds per instance, the method found the first reported CPU-only solutions to 18 of 33 previously open QOBLIB instances, solving 130 to 133 of the 156 benchmark instances per seed under a 24-hour cutoff on two CPU cores. These results underscore the value of agent-assisted exploration in navigating the large design space of basis reduction and enumeration strategies.
Maximum Independent Set Results
For MIS, the authors' generator encodes planted XOR constraints as graphs with certified optima. On seven instances ranging from 1,752 to 3,996 vertices, the best solutions returned by the tested solvers in eight-hour runs were 5 to 15 vertices below the optimum—revealing a persistent gap between certified optimal solutions and what current solvers can achieve within practical time budgets.
Significance
Together, these results illustrate two complementary contributions of agent-assisted algorithmic research: discovering novel solution strategies that close previously open benchmark gaps (Market Split), and constructing rigorously certified hard instances that expose the limits of current solvers (MIS). The human-guided, two-agent workflow offers a template for future AI-assisted algorithm discovery in combinatorial optimization and beyond.
via ArXiv AI
