- Rating
- 3
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes an ensemble method for combining assignments from different ML-based SAT solvers. Traditional ensemble methods combine outputs for each variable separately, which for SAT would often lead to a worse assignment violating many clauses. To preserve consistency, the proposed ensemble method considers relationships between variables. The proposed algorithm starts from an assignment derived with a quality-weighted voting rule (independent for each variable) or a low-energy assignment given by one of the agents. Local search is run to repair the assignment iteratively. Variables for which the individual agents are confident are protected softly.
When local search does not improve with single bit flips, whole blocks of variables are flipped simultaneously. The proposed mathematical framework guides how those blocks are selected. Specifically, initial agent predictions are used to group variables into Heider blocks. For two variables in the same block, all agents either agree that or . This guides larger flips in local search: variables in the same Heider block are all flipped simultaneously. Intuitively, this is because the agents agree that if is flipped, then should be flipped as well.
The paper evaluates the method on SAT formulas from SATLIB. As baselines, they use each individual solver, the solvers + a local search, a set of fixed fusion rules, and learning based ensemble methods. The proposed method achieves the highest solve rate, and the lowest PAR-10 score which suggests more reliable performance under the fixed search budget.
Critical strengths
- The problem setting is interesting. Ensemble methods are widely used in supervised learning. Combinatorial problems pose a unique challenge for ensemble methods: naively combining different solutions does not necessarily work well because of dependencies between the variables.
- The proposed mathematical framework for modeling dependencies between variables is elegant.
- The algorithm uses information from the agents to guide search softly, rather than treating some variables or blocks as fixed.
- The baselines are extensively evaluated. Per-model class reports the strongest individual agent after post-hoc local search, which is important to control for the effect of running local search on top of the agent solutions.
- The relevant mathematical definitions are explained reasonably well with illustrative examples.
Critical weaknesses
W1: The paper is easy to follow until Algorithm 1. I needed substantial time to go through it, and I feel like many parts there were not explained in the text or sometimes completely undefined. The individual comments are mostly minor, but together they reduce clarity significantly
- The pseudocode assumes familiarity with the local search framework on which it builds. It would be helpful to give a short high level overview to help understand the overall search procedure.
- cw is never defined verbally (I'm guessing it is clause weights). Since w and c already stand for other things, using cw can be confusing
- Similarly, u is never verbally defined.
- Algorithm 1 calls a clause weighted local search algorithm (WLS) but it is never explained what the input parameters of this algorithm stand for. cw is not updated in the pseudocode. Does WLS update it?
- "level A" is not defined
- Is "no improvement" measured after a single WLS call or globally? stall is also not initialized
W2: The blocks are based on exact agreement between agents. A single bad agent can mess up the block structure by preventing variables being placed in the same block. Moreover, the bound on the number of blocks grows exponentially in the number of agents
Questions for authors
Q1: What is meant by "The equivalence relation on "? The first is a relation on agents whereas the second one is on variables, so it is not clear what this notation means. Are the Heider blocks just the equivalence classes of ?
Q2: How often does Algorithm 1, line 2 go with best energy solution vs. the consensus solution?
Q3: The paper proposes this as an ensemble method for ML-based solvers. It seems like the proposed framework could combine assignments from incomplete classic solvers too. Is there a reason this is not considered?
Q4: How often are block flips actually happening? It would also be relevant to compare with randomly selected blocks to determine how much the Heider blocks help.
Thanks
Once again, we sincerely thank you for your valuable comments and requested experiments. We hope that our responses have adequately addressed all of your concerns. We would be happy to address any further questions or provide additional clarification regarding the novelty and contributions of our work.