ZICQ
中 Log in / Sign up
Newsroom Agentic #SailSearch #AI Agents #Combinatorial Optimization #Market Split #Maximum Independent Set

SailSearch Finds CPU-Only Solutions for 18 Open Market Split Instances with Two AI Agents

Avatar of Mr.Xu

By Mr.Xu Compiled & Reviewed by Editorial

Published:

中文阅读 (Chinese) English Version
Co-reading Select any sentence in the article to highlight, annotate, or copy a quote card. Join discussion ↓

Summary:SailSearch introduces a human-guided algorithmic-research workflow driven by two language-model agents. For Market Split, it searches across multiple lattice bases and divides computation between enumeration and continued basis reduction. Under a 24-hour cutoff on two CPU cores with ten random seeds per instance, the preprint reports CPU-only solutions described as the first reported ones for 18 of 33 previously open QOBLIB instances, while individual seeds solve 130 to 133 of 156 benchmark inst


Core Findings

SailSearch is a combinatorial-optimization research workflow guided by humans and involving two language-model agents. Its strongest results concern Market Split: with a 24-hour cutoff on two CPU cores and ten random seeds per instance, the preprint reports CPU-only solutions described as the first reported ones for 18 of 33 previously open QOBLIB instances. Individual seeds solve between 130 and 133 of the 156 benchmark instances.

The reported solutions should not be interpreted as proofs of optimality. A 24-hour run primarily produces feasible incumbents: solving an instance means finding a candidate that satisfies the constraints, not proving that no better solution exists. Likewise, CPU-only means the authors are highlighting instances for which they report a CPU result without claiming that no GPU, mathematical, or other solution has ever existed.

Workflow and Technical Mechanism

The abstract confirms two language-model agents and human guidance, but it does not disclose the underlying models, their exact roles, their communication protocol, or their prompt templates. The most conservative engineering abstraction is that the agents participate in iterating over an algorithm or implementation, an executor runs the candidate on real benchmarks, humans adjust the research direction from intermediate results, and an external checker verifies feasibility. Whether the agents generate search code, derive mathematical ideas, or only handle implementation and diagnosis must be confirmed from the full paper and repository.

Multi-Basis Search for Market Split

Classical approaches to Market Split are closely connected to lattice-basis reduction and enumeration. A lattice basis defines the integer-coordinate geometry in which the search operates: enumeration looks for candidate partitions along the current structure, while continued basis reduction changes the basis so that later enumeration can explore more useful directions. Rather than relying on one basis, SailSearch searches across multiple bases, reducing the risk that one poorly chosen basis wastes the entire run.

This multi-basis strategy functions as a randomized portfolio. Each basis exposes a different enumeration direction, and continued reduction moves computation away from exhausted regions toward potentially more productive lattice space. It can improve the probability of finding a strong incumbent, but it does not turn the problem into a polynomial-time algorithm. Enumeration may still grow sharply with dimension and candidate-space size, while repeated basis reduction consumes additional CPU time.

Let E_b and R_b denote enumeration and reduction work for basis b. A rough work model is W ≈ Σ_b(E_b + R_b). With two cores and effective parallel efficiency η, ideal wall-clock time is approximately W/(2η); serial phases, process scheduling, and storage access make the realized time different. A 24-hour run on two cores has a nominal ceiling of 48 core-hours, but the abstract does not disclose actual CPU utilization, peak memory, or the work split between enumeration and reduction.

MIS Generation and Certified Optima

The MIS component plays a different role from Market Split. The authors encode combinatorial structures with XOR constraints as graphs and construct instances with known, certified optima. On seven instances with 1,752 to 3,996 vertices, the best solutions returned by the tested solvers after eight hours remain five to 15 vertices below the optimum.

These results mainly demonstrate that existing solvers still have a substantial optimality gap on particular XOR-derived graph structures. They do not show that SailSearch itself solved the MIS instances. A generator based on planted structure provides reliable ground truth, but it may also produce difficulty distributions unlike those found in real business graphs. The generator contribution and the algorithmic-discovery contribution therefore need separate evaluation.

Engineering Trade-offs

SailSearch's main advantage is placing language models inside a research loop with external computational feedback. The models do not need to calculate thousands of lattice coordinates directly. They can propose and revise search strategies, while deterministic solvers perform the numerical work and external constraint checkers provide a correctness backstop. This division is more auditable than asking a model to emit a final combinatorial-optimization answer.

The costs are equally important. Human guidance can correct a weak search direction, but it introduces an unquantified intervention budget and weakens fully automated reproducibility. CPU-only execution lowers the hardware barrier, yet a 24-hour run still represents substantial aggregate compute. The paper does not report model-call counts, token consumption, API expense, or per-iteration latency. Multi-basis search trades additional repeated work for reduced sensitivity to an unlucky seed, while continued reduction and enumeration compete for the same resources, making scheduling policy a direct determinant of effective search depth.

Memory usage is also absent from the abstract. Lattice search generally avoids the GPU-memory demands of large-model inference, but that does not make its memory footprint negligible. High-dimensional bases, enumeration queues, and parallel processes can still create substantial pressure.

Benchmark Validity

The evaluation has three clear strengths: QOBLIB is an external public benchmark, the 18 previously open instances provide a meaningful novelty signal, and the fixed two-core, 24-hour budget and ten random seeds make the reported protocol comparatively reproducible.

Several critical facts remain unavailable. The abstract does not list absolute objective values, optimality gaps, feasibility-proof status, comparison solvers, CPU model, compiler and lattice-library configuration, or matched-compute ablations between two agents, one agent, agent-free program synthesis, and random program search. It is therefore impossible to attribute the results cleanly to language-model reasoning rather than randomized multi-basis search, long CPU budgets, or human intervention.

A credible reproduction should include at least three baselines: a classical Market Split solver under the same core-hour budget, random program or random multi-basis search with identical seeds and core-hours, and the complete dual-agent workflow. Every run should record the incumbent value, feasibility status, proof status, and instance-level timeline. The priority implied by first reported also requires an independent audit of QOBLIB status records rather than reliance on the paper's own claim.

For MIS, the evaluation should add graphs with different planted ratios, constraint densities, and random baselines. Seven instances are enough to expose a solver gap, but not enough to establish that the generator represents real MIS, scheduling, or biological-network workloads.

Deployment Guidance

  1. Pin a reproducible environment. Record model versions, temperature, system prompts, agent transcripts, seeds, CPU model, compiler and math-library versions, lattice-reduction implementation, timeout policy, and code-commit hashes.
  2. Use an independent verifier. Check every Market Split partition against the original constraints and verify that each MIS candidate is genuinely independent. Do not rely solely on feasibility claims produced by the agent or solver.
  3. Preserve recoverable search state. Log each basis, reduction version, enumeration node, objective value, and proof status so long runs can resume and so feasible incumbents remain distinguishable from proven optima.
  4. Isolate agent-generated code. Sandbox file, network, and process permissions, pin dependencies, and separate code execution from result analysis and final integration.
  5. Operate as an anytime solver. Continuously persist validated incumbents outside the agent context and maintain a timeout fallback. Without certificates, do not present heuristic results as exact answers.
  6. Run matched-budget ablations. Compare agent-free, single-agent, dual-agent, and purely random multi-basis variants on internal instances to test whether agents actually improve solution quality per CPU-hour.

Bottom Line

The most important signal from SailSearch is not that language models understand combinatorial optimization in the abstract. It is that agent-mediated algorithm discovery can use external code execution and benchmark feedback to turn modest CPU budgets into feasible solutions for previously open instances. The current evidence still positions the system as a research prototype rather than a validated autonomous optimizer or optimality prover.


Source: ArXiv AI (cs.AI) (2026-11-20)

— END —

Tags: #SailSearch #AI Agents #Combinatorial Optimization #Market Split #Maximum Independent Set

Editorial & Fact-Checking Note: This article is compiled from primary research, official release documentation, and source papers by the ZICQ Newsroom pipeline with automated entity verification and human editorial review. If you notice any technical inaccuracy, please submit a correction via our corrections policy or email our editorial desk directly.

What's your take on this story?
🚀 Explore & Submit Works

Community Comments

Loading live comments and annotations…