Improving stochastic local search for uniform <scp><i>k</i>‐SAT</scp> by generating appropriate initial assignment
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
Abstract Stochastic local search (SLS) algorithms are well known for their ability to efficiently find models of random instances of the SAT problem, especially for uniform random k ‐SAT instances. Two processes affect most SLS solvers—the initial assignment of the variables and the heuristics that select which variable to flip. In the last few years, the work on generating the appropriate initial assignment has not been paid much attention or seen much progress, while most SLS solvers focused on the heuristic algorithm. The present work aims to improve SLS algorithms on uniform random k ‐SAT instances by developing effective methods for generating the initial assignment of variables in a controlled way. First, the allocation strategy introduced recently for 3‐SAT instances is extended to initialize the initial assignment on random k ‐SAT instances. Then a concept of an initial probability distribution of the clause‐to‐variable ratio of the instance is introduced to determine the parameters of the allocation strategy. This combined method is added to the beginning of six state‐of‐the‐art SLS algorithms in order to generate initial assignments of variables in a controlled way instead of generating them randomly, resulting in six extended SLS algorithms named WalkSATlm_E, DCCASat_E, Score 2 SAT_E, CSCCSat_E, Probsat_E, and Sparrow_E, respectively. They are then evaluated in terms of their capabilities and efficiency on uniform random k ‐SAT instance from the random track of SAT Competitions in 2016, 2017, and 2018. Experimental results show that these improved SLS solvers outperform their original performance, especially WalkSAT_E, Score 2 SAT_E, and CSCCSat_E outperform the winner of the random track of SAT competition in 2017. In addition, based on the initial probability distribution method, the present work proposes a parameter tuning and analysis of random 3‐SAT instances and provides an additional comparative analysis with the state‐of‐the‐art random SLS solvers based on large‐scale experiments.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it