agent-sat is an autonomous AI agent system that takes a hands-on approach to solving weighted MaxSAT instances. What sets it apart is that it doesn’t rely on predefined algorithms — instead, the agent teaches itself new solving techniques through iterative experimentation and evaluation against a comprehensive benchmark suite. This approach has enabled it to discover and implement multiple effective strategies, some of which outperform competition benchmarks.
autonomous maxsat solving agent leveraging iterative self-improvement
At its core, agent-sat revolves around Claude Code, an AI agent that autonomously experiments with solver techniques to tackle weighted MaxSAT problems. The MaxSAT problem extends SAT (satisfiability) by associating weights with clauses and seeking assignments that maximize the sum of satisfied clause weights, a challenging combinatorial optimization task.
The system operates on a repository that acts as a shared knowledge base. The agent reads from an expert knowledge file (expert.md), maintains and expands a library of solver techniques, and runs experiments on a set of 229 benchmark instances from the 2024 MaxSAT Evaluation.
After each iteration, the agent commits improvements back to the repository. This version-controlled setup allows multiple agents to coordinate and build upon each other’s discoveries purely through git pull and push operations, without any explicit orchestration or direct communication.
This emergent collaboration model is particularly interesting because it avoids the complexity of distributed coordination frameworks while enabling collective progress.
The stack is primarily Python-based, centered on Claude Code for AI-driven experimentation and evaluation. The benchmarks and solver implementations are tightly integrated to allow rapid iteration and testing.
autonomous discovery of solver techniques and git-based multi-agent coordination
What distinguishes agent-sat is its ability to independently discover sophisticated MaxSAT solving methods. It has autonomously developed at least nine solver techniques, including core-guided search, clause-weighting local search (CWLS), tabu search, and an alternating CWLS+WalkSAT approach.
The solver techniques are not hardcoded but emerge from the agent’s iterative experimentation, guided by evaluation outcomes on benchmark instances. This setup blurs the line between a solver and a learning system, turning the MaxSAT problem into a playground for autonomous algorithmic innovation.
The coordination model is another highlight. Instead of a centralized orchestrator, multiple agents share their progress by pushing and pulling commits on the git repository. This simple yet effective pattern facilitates asynchronous collaboration and knowledge sharing, leveraging git’s version control features for state synchronization.
Benchmarks speak to the effectiveness of this approach:
- 220 out of 229 instances solved
- Matching competition best on 30 instances
- Outperforming competition best on 5 instances
- Solved one instance with no known prior solution (novel solve)
- Compressed solution storage from 1.7GB to 1.5MB
These results show the agent’s capacity not just to replicate known techniques but to push boundaries. For example, the cost improvements on benchmark instances like switchingactivity_74 (37.5% better) and comp07.lp (1778x improvement to optimal) highlight the practical gains.
The tradeoff is clear: while this system excels at research and exploration, the approach depends heavily on computationally expensive iterative experimentation and is inherently slower than hand-tuned solvers in production contexts. The complexity of the agent’s learning process and the reliance on git for coordination may not suit real-time or large-scale deployment.
quick start with python-sat and numpy dependencies
To get started, install the necessary Python dependencies as per the README:
# Launch on EC2 (handles everything: installs deps, clones repo,
# Install Python dependencies
pip install python-sat numpy
From here, the README and repository offer detailed documentation on running experiments, extending solver techniques, and understanding the evaluation framework.
verdict: a research-focused platform for autonomous solver innovation
agent-sat is a compelling example of autonomous AI applied to algorithm discovery and optimization. Its ability to self-discover solver techniques and coordinate multiple agents through git commits is a clever, low-overhead orchestration pattern worth understanding.
That said, its primary value lies in research and experimentation rather than production deployment. The iterative nature and computational cost of the approach mean it may not replace optimized MaxSAT solvers in latency-sensitive or large-scale environments.
For researchers and practitioners interested in autonomous AI, combinatorial optimization, and distributed agent coordination, agent-sat provides an insightful case study and a solid foundation to build upon. The codebase is relatively clean and documented, making it accessible for exploration and extension.
If you’re curious about AI agents that learn by doing and collaborate without explicit orchestration, agent-sat is worth a look.
Related Articles
- AgentGPT: building autonomous AI agents with a full-stack web platform — AgentGPT offers a full-stack solution to deploy autonomous AI agents in the browser using Next.js, FastAPI, and Langchai
- Hermes Agent: A self-improving AI agent with closed learning loops and multi-platform integration — Hermes Agent is a Python AI agent featuring closed learning loops, autonomous skill creation, multi-model support, and s
→ GitHub Repo: iliazintchenko/agent-sat ⭐ 178 · Python