Let U(x) count the clauses unsatisfied by assignment x. Basic GSAT evaluates every one-bit neighbour and chooses a flip producing the greatest reduction in U. If several flips tie, it samples among them. A zero-change move crosses flat ground; a negative improvement moves uphill. The local calculation can be perfectly correct while the path remains globally poor, because U records height but not the connectivity of lower regions.

A local minimum has no strictly better neighbour. A plateau is a connected set of equal-scoring assignments explored through sideways moves. Continuing across plateaux already improved GSAT, but a finite trajectory can encounter a plateau with rare exits or none reachable without first making U larger. Repeated restarts attack the problem globally by discarding the complete assignment. Noise attacks it locally by temporarily relaxing greed.

The authors compare three relaxation mechanisms under tuned parameters. Simulated annealing samples a variable and accepts an uphill move with a temperature-dependent probability. Random noise mixes greedy GSAT with a uniformly random variable flip. Mixed random walk also mixes with greed, but its random branch chooses only a variable appearing in an unsatisfied clause. That small restriction is the paper’s central causal proposal.

Calling these methods “noise” can obscure their structure. A random-walk flip is stochastic, yet it is not ignorant: the current residual formula filters the eligible variables. Every such move touches at least one failed constraint. It may break several satisfied clauses, and it is not guaranteed to improve the score, but it spends disruption at the active boundary between the current assignment and a solution.

The comparison concerns discovery, not proof. Each method can return a satisfying assignment whose clauses are independently checked. Exhausting restarts supplies no refutation. The study therefore asks which incomplete procedure finds witnesses faster on its test classes, not which decides SAT in general.

Annealing chooses a variable uniformly, computes δ, the increase in the number of unsatisfied clauses caused by flipping it, and always accepts δ≤0. If δ>0, it accepts with probability exp(−δ/T). At high temperature, even damaging moves are common. At low temperature, the chain behaves more greedily. The authors test constant temperatures and geometric cooling schedules.

Random noise retains GSAT’s best-flip branch with probability 1−p. With probability p it chooses uniformly from all variables. This eliminates the exponential acceptance calculation and gives every hypercube edge some chance, but many noisy flips can concern variables irrelevant to any current defect. A variable appearing only in already satisfied clauses cannot directly repair the residual set.

Mixed random walk uses the same probability gate but narrows the random branch. Construct the set of variables that occur in at least one unsatisfied clause, choose uniformly from that set and flip. The move is focused without being greedy. It does not calculate which variable repairs the selected clauses, and a chosen variable may actually break more clauses than it makes.

The baseline, basic GSAT, normally chooses a maximum-gain variable. If all moves are uphill it can technically choose the least bad one, but the authors say such forced uphill events are rare and ineffective. Their escape mechanisms make non-greedy disruption an explicit recurring policy rather than an accidental last resort.

Fair comparison requires tuning. The study varies MAX-FLIPS and MAX-TRIES, p for the two mixtures, temperature from 5 to 0 in steps of 0.05, and geometric cooling schedules. Only the best settings enter the tables. That protocol demonstrates each family near its tested optimum; it does not show that one universal setting dominates every distribution.

For SAT, energy is the number of unsatisfied clauses. A proposed flip that reduces or preserves energy is accepted. A flip increasing energy by δ is accepted with probability exp(−δ/T). At T=0 the uphill probability vanishes; at larger T it rises. The paper describes the zero-temperature resemblance to GSAT but notes a crucial difference: annealing proposes one random variable, whereas GSAT explicitly takes a best neighbour when one exists.

A cooling schedule begins hot and multiplies T by a factor below one. Early exploration can cross large barriers; late search settles. The intuitive physical analogy is attractive, but the empirical question is whether the schedule spends its flips at useful temperatures for the specific landscape. A theoretically elegant schedule can be badly matched to a bounded run.

The authors found no tested geometric schedule superior to the best constant temperature. Extremely slow cooling did not significantly reduce the average restart count. They suggest that most SAT work lies in satisfying the last few clauses, corresponding to a low-temperature tail where a geometric schedule changes little. This is an experimental interpretation, not a theorem about all SAT distributions.

Best temperature varied by problem class: 0.2 for the hard random formulae, 0.5 for planning and 0.15 for Boolean circuit synthesis. That variation is itself evidence against treating “temperature” as an intrinsic property of SAT. It is a control parameter coupling proposal scale, landscape and computational budget.

The paper counts a simulated-annealing flip only when the proposed change is accepted. Wall time and accepted moves nevertheless agree in the ranking of policies, which helps rule out a conclusion driven solely by implementation overhead. It does not equalise the number of evaluated proposals, an important detail for modern replication.

The mechanism is easy to implement and ensures that every one-bit edge is eventually possible. It also cleanly separates exploitation and exploration. The greedy branch uses the score of all neighbours; the noisy branch uses no clause information at all. This can break deterministic cycles and open an uphill route without maintaining temperature or a cooling clock.

Its weakness appears when the residual defect is sparse. Imagine a thousand-variable assignment with two unsatisfied three-literal clauses. At most six distinct variables occur in those clauses. A global random flip has probability no more than 6/1000 of touching one of them directly. The other 994 choices may alter already satisfied constraints while leaving both active defects untouched.

That calculation does not prove an irrelevant flip is useless. Changing a distant variable can prepare later moves or avoid breaking a clause during repair. The paper’s claim is statistical and comparative: focus gives each exploratory step a more immediate relationship to what remains wrong, and its advantage grew on their larger hard-random instances.

In Table 1, random noise improves on basic GSAT for formulae it solves, but neither noise nor annealing finds solutions for the three largest listed instances within the stated limits. On the circuit-synthesis set, random noise can actually degrade basic GSAT. A perturbation policy is not valuable merely because it is stochastic; it must match the residual structure.

The optimal tested p for both noise mixtures lies between 0.5 and 0.6 throughout the experiments. That is a strikingly large exploratory share, not a tiny occasional tremor. Yet it should be read as the best region within those parameter sweeps, machines and problem sets, not a timeless prescription.

The random branch begins by calculating a relevance set R(x): every variable appearing, positively or negatively, in at least one clause false under x. A uniform draw from R guarantees that the flipped variable participates in a current defect. The greedy branch still evaluates the entire formula, so exploitation remains global even while exploration is focused.

A variable in a false clause is not necessarily a good flip. A three-literal clause is false because all three literals currently have the wrong value, so flipping any member makes that clause true. Yet that variable can also be the sole true literal in several other clauses, making those clauses false. Focus guarantees at least one clause made; it does not control how many are broken.

This is precisely why walk is different from a greedy repair. It preserves uncertainty among eligible interventions. Variables whose immediate make-minus-break score looks poor can be chosen because the local score may be misleading about access to future basins. The residual set supplies direction without reinstating the ranking that caused the trap.

The probability gate creates two timescales. Greedy steps exploit the slope produced by clause count. Walk steps reconfigure the neighbourhood in a defect-related way. With p around one half in the reported tests, the solver alternates these roles frequently enough that “noise” becomes part of normal motion rather than an emergency after explicit trap detection.

The procedure need not label a state as a local minimum before walking. This matters because identifying plateau geometry could itself be costly, and a trajectory may benefit from disruption before it demonstrably stalls. The fixed mixture is memoryless: the same p applies whether the last ten moves improved or not.

Each instance has N variables, L clauses and three distinct literals per clause, with signs negated independently at probability one half. Around 1994, the authors place the difficult region near L≈4.3N, noting convergence towards 4.25 for larger N. A generator outside this transition can produce formulae so under- or over-constrained that strategy differences disappear.

Table 1 ranges from 100 variables and 430 clauses to 2,000 variables and 8,480 clauses. At 100 variables, all strategies have similar wall times. As N rises, mixed random walk separates dramatically. It reports solutions for every listed size; basic GSAT fails from 800 upward within the cutoff, while annealing and random noise fail on the largest three.

At 600 variables, basic GSAT averages about 30 million flips and 500 restarts, compared with about 242 thousand flips and one restart for walk. At 2,000 variables, walk averages about 23 million flips and 1.1 restarts. The important signature is not merely fewer operations: mixed walk is almost guaranteed to find a model on these selected satisfiable instances once a run begins.

The table’s R is average restarts before success. The authors use at least 100 random restarts per method and instance, increasing to 1,000 when more than 20 are needed. An asterisk means no solution after more than ten hours or 1,000 restarts. Such censoring must not be silently converted into an average runtime.

The paper emphasises that the ordering by flips matches the ordering by seconds, reducing concern that one C implementation simply has cheaper iterations. Hardware was an SGI Challenge with a 70 MHz MIPS R4400. These timings establish a historical experiment, not a fair race against current complete SAT solvers.

The planning formulae are difficult for basic GSAT because extremely deep local minima can encode assignments that satisfy nearly every individual clause while failing to represent any legal plan. Clause count rewards local consistency, but the remaining contradiction may require coordinated changes across time steps and state variables.

The paper’s vivid example is Towers of Hanoi. A near-assignment can behave as though a disc slips out from the bottom of a stack. Such a history satisfies many constraints yet differs profoundly from every legal solution. Repairing one clause in isolation can recreate another because the physical invariant is distributed across the encoding.

On the “Hanoi” and “huge” cases, basic GSAT fails within the limit. Mixed walk runs in 39 and 38 seconds respectively. The paper reports it at about one hundred times faster than annealing on the two largest problems and more than two hundred times faster than random noise. Its average restart counts, 2.6 and 1.1, also remain far below the alternatives.

The planning set uses a higher best annealing temperature, 0.5, than the random and circuit-synthesis sets. This is consistent with deeper barriers requiring more willingness to accept damage, although the paper’s tables cannot by themselves identify barrier depth as the unique cause.

Structured success answers a reasonable challenge to the random-formula experiment: perhaps focused walk only exploits quirks of the fixed-clause generator. Planning broadens external validity. It does not prove universality, because both domains are still translated into CNF and share the same clause-based residual representation.

In circuit synthesis, the formula asks for a logical circuit consistent with specified input-output behaviour. On five difficult randomly wired instances inherited from Kamath and colleagues, mixed walk and annealing both improve substantially on basic GSAT; walk is somewhat better. Random noise, however, does not improve and can degrade performance.

The authors then consider practical multiple-output structures such as adders and comparators, which contain no random component. GSAT with walk solves the listed instances from fractions of a second to several minutes. A then-fast complete Davis–Putnam variant solves only two of six within the cutoff, although the paper notes preliminary evidence that random variable permutations can improve complete search.

These comparisons are historically important because structure was often expected to favour systematic reasoning. The result shows that a local objective plus focused stochastic motion can exploit at least some highly organised encodings. It does not establish that incomplete search dominates systematic SAT on circuits generally.

Circuit diagnosis supplies a related but distinct task: encode test-pattern generation and find assignments revealing faults. Mixed walk again performs well compared with the complete procedure. A successful assignment is practically meaningful and directly checkable against the encoded circuit, preserving the asymmetric output contract of local SAT.

The lesson is narrower and more useful than “randomisation beats logic”. The residual clauses expose where a current circuit candidate disagrees with required behaviour. Focusing random choice on variables participating in those disagreements can be effective even when the formula was generated deterministically.

WSAT first samples one unsatisfied clause. It then chooses a variable from that clause, either uniformly or according to a greedy heuristic. Every flip therefore addresses a specifically sampled defect. The candidate set is at most the clause length: three variables for 3CNF: rather than the union of variables across all false clauses.

This two-stage sample is not equivalent to choosing uniformly from the union. A variable appearing in several unsatisfied clauses can be reached through each one, so its marginal probability is higher. Under clause-first selection, current defect multiplicity becomes an implicit weight. Under GSAT’s p=1 walk, the maintained no-duplicates list gives each relevant variable equal probability.

The distinction surprised the authors in circuit diagnosis. GSAT with 100 per cent walk failed on those problems, while WSAT with random within-clause selection solved all of them. The result demonstrates how apparently tiny sampling details can define a different Markov chain and materially change search.

Tables 4 and 5 show substantial WSAT speed-ups over GSAT with walk on the reported circuit sets. For the 3-bit adder cases, times fall from 94.1 and 456.6 seconds to 1.0 and 0.7 seconds. Clause-first focus is therefore more than a terminological update in these experiments.

Greedy WSAT variants require specifying the within-clause score and tie rule. Later WalkSAT traditions often use break count, preferring variables that damage few satisfied clauses, with a noise probability selecting a random clause member. The 1994 text sketches the new algorithm and reports early data; it does not exhaust every modern variant.

Hansen and Jaumard had compared five MAX-SAT procedures: basic local search, two deterministic Johnson algorithms, simulated annealing and their steepest-ascent/mildest-descent method with a tabu-like memory. The last, called zsamd, was the strongest of that group. Selman, Kautz and Cohen repeat the principal random 3SAT experiments with GSAT plus walk.

For each problem size, fifty random formulae are generated and each is solved one hundred times from different initial assignments. The table reports the mean best and mean average residual counts. On the 500-variable, 5,000-clause cases, mixed walk’s best assignment leaves an average of 161.2 clauses unsatisfied and its run mean is 163.6. It consistently improves the listed alternatives.

The small gap between best and mean indicates stable outcomes across restarts, and the authors suggest the best values may be close to optimum. “May” is important: without a bound or complete optimisation proof, repeated convergence does not certify optimality. Many local basins can share the same suboptimal height.

MAX-SAT clarifies why a noisy move can be rational even when it temporarily lowers objective value. The run retains the best assignment seen, so exploration may damage the current state without losing the incumbent. State and memory now have separate roles: the current assignment can wander; the recorded best protects achieved value.

The extension also broadens the paper’s thesis. Defect-focused noise is not useful only because a perfect SAT witness terminates search. It can improve the quality of approximate solutions under an optimisation contract, provided evaluation records best-so-far performance and does not confuse it with a proof of optimality.

The formula has seven clauses over a, b, c and d. Every assignment and one-bit neighbour is enumerated, making the display an exact finite landscape rather than a suggestive animation. A teal ring marks the current state, green marks a satisfying assignment and gold marks one-bit neighbours.

For reproducibility, the laboratory uses a fixed numeric sequence instead of hidden randomness. On mixed policies, a sequence value below p activates noise or walk; otherwise the exact maximum-gain set is used. Global noise cycles through all variables. Mixed walk cycles through the union of variables in false clauses. WSAT cycles first through a false clause and then through its members.

The displayed gain is the decrease in unsatisfied clauses after a flip. A negative number is uphill. Focused eligibility does not imply positive gain, which is the mechanism’s essential distinction. Once a model is reached, the next button begins a new deterministic trajectory rather than damaging the verified witness.

Three exhaustive audits run on load. For all sixteen assignments, the greedy choice must belong to the full arg-max set; every focused candidate must occur in a currently unsatisfied clause; and every vertex labelled as a model must satisfy every original clause. These oracles test mechanism, not the paper’s historical timing claims.

Begin with the correct primary source: Bart Selman, Henry A. Kautz and Bram Cohen, AAAI-94 pages 337–343. The canon spreadsheet’s linked file AAAI94-008 is a different paper by Linda M. Wills and Janet L. Kolodner. The official source for this record is AAAI94-051. Correcting that mismatch prevents an apparently precise citation from grounding the wrong research.

Recreate random 3CNF with documented N, L, clause-length, sign probability, duplicate policy and density. Establish satisfiability independently with a complete solver, because local-search non-discovery cannot classify instances. Report how satisfiable cases were selected near the transition and preserve censored failures rather than averaging them away.

For every strategy, record the full parameter grid and total proposal budget. Annealing counts accepted flips in the paper; also report considered proposals. For mixtures, state whether variable occurrence lists are deduplicated. For WSAT, distinguish uniform clause sampling, uniform within-clause sampling, greedy scoring and tie rules. Publish independent seeds.

Measure wall time, proposals, accepted flips, restarts, success probability and the distribution of time-to-witness. Historical tables give means; modern work should add quantiles and confidence intervals because randomised runtimes can have heavy tails. Fixing one “lucky” seed creates a demonstration, not an estimate.

Replicate each problem class separately. Random 3CNF, planning, synthesis, diagnosis and MAX-SAT have different residual structures and best parameters. A policy’s average across them can conceal reversals, such as global random noise helping hard-random formulae yet degrading the circuit-synthesis set.

Finally, compare against modern baselines only with explicit framing. The 1994 complete solver, compiler and hardware are historically informative. Contemporary CDCL, stochastic local search and hybrid solvers answer a different performance question. A faithful replication and a present-day benchmark can coexist, but their conclusions must not be merged.

Review one: fidelity and evidence. This reconstruction preserves complete-assignment local search, unsatisfied-clause energy, sideways and uphill motion, the three escape families, parameter tuning, constant versus geometric temperature, the hard-random transition, planning minima, circuit synthesis and diagnosis, WSAT’s two-stage sampling, MAX-SAT incumbents and the incomplete failure contract. Numerical claims are tied to the 1994 tables rather than presented as current records.

Review two: teaching and implementation. Ten paper-specific SVGs make plateau escape, policy information, annealing acceptance, global dilution, the p gate, scaling, impossible plans, circuit products, sampling multiplicity and incumbents visible. Twelve worked examples and twelve causal probes isolate mechanisms. The laboratory enumerates the complete small state space and names three exact oracles.

Source-integrity review. Author order and pagination follow the paper itself: Bart Selman, Henry A. Kautz and Bram Cohen, 337–343. The canon’s author order and AAAI94-008 URL were checked against the scan and corrected here to AAAI94-051. The wrong link is documented instead of silently used.

Accessibility and responsive review. Every SVG includes a unique title, description, caption and source scope. Labels and geometry carry meaning in addition to colour. Motion stops under reduced-motion preference. Controls are labelled; outcomes use text and a live region; grids collapse at 900 and 600 pixels; the evidence table scrolls on narrow screens.

Mixed random walk supplies a compact model of bounded intervention. The system exploits a scalar objective, but it does not mistake that objective for complete knowledge of the landscape. It uses present failures to constrain experimentation while tolerating immediate loss.

The focused move is not intelligent because it predicts a successful future. It is intelligent in a weaker operational sense: uncertainty is allocated where constraints currently fail. The distinction between relevance and desirability protects the mechanism from a common error: assuming that attention must already know the answer.

WSAT adds another lesson. Sampling order is part of representation. A set of relevant variables erases how often each variable participates in failure; clause-first selection preserves that multiplicity. Two algorithms described casually as “flip a variable in an unsatisfied clause” can therefore behave differently.

The experiments also resist a universal recipe. Best temperature changes across domains, noise can hurt an easy structured set, and the strongest advantage appears as random instances grow. Competence is an interaction among objective, neighbourhood, proposal distribution, stopping rule and problem generator.

These mechanisms model search policy, not phenomenal awareness. They show how a bounded agent can combine exploitation with relevant exploration and verify a discovered witness. Nothing in stochastic focus, successful SAT search or adaptive-looking trajectories establishes consciousness.