SailSearch: Agent-Assisted Discovery in Combinatorial Optimization
Source
arxiv.org
Author
Dhriti Verma, Kanthi Sarpatwar, Vinicius Lima, Dzung Phan, Jayant Kalagnanam
Date
Why it matters
Shows a human-guided two-agent workflow producing new results on open optimization benchmarks, a concrete data point on where agent-assisted research already beats prior CPU-only solvers.
Key takeaways · AI-distilled
For Market Split, the human-guided two-AI agentAn AI system that doesn't just answer once but works toward a goal in a loop — taking actions, reading the results, and deciding what to do next.Full definition → workflow produced a randomized algorithm that searches across multiple lattice bases, dividing computation between enumeration and continued basis reduction.
Across ten random seeds per instance, that algorithm found the first reported CPU-only solutions to 18 of 33 previously open QOBLIB instances and solved 130 to 133 of 156 benchmarkA standard public test set for comparing AI models — the shared scoreboards behind every "model X beats model Y" claim.Full definition → instances per seed, with a 24-hour cutoff on two CPU cores.
For maximum independent set, the authors built a generator that encodes planted XOR constraints as graphs with certified optima. On seven instances of 1,752 to 3,996 vertices, the tested solvers' best eight-hour results fell 5 to 15 vertices short of the optimum.
Terms in this piece · Glossary
AI agent — An AI system that doesn't just answer once but works toward a goal in a loop — taking actions, reading the results, and deciding what to do next.
benchmark — A standard public test set for comparing AI models — the shared scoreboards behind every "model X beats model Y" claim.