When Does the Move Algebra Guide Search? A Two-Certificate Calculus for Operator Non-Commutativity in Local Search

Local search evaluates the objective $f$ at neighboring states to decide where to move or restart. Can the move set itself help make those decisions? We measure how far apart two moves take a state when applied in opposite orders. This non-commutativity defect $\kappa$ needs no objective evaluations; its counterpart ${\kappa }_f$ compares $f$ at the two resulting states. We identify two conditions necessary to credit a gain to this signal. Under coupling, differences in $f$ track the geometric disagreement. Under non-redundancy, ${\kappa }_f$ cannot be recovered from the current and one-step neighbor values already available to standard local search. We test these conditions on three classes. On SAT, the signal is an exact function of one-step values. On TSP with 2-opt moves, $\kappa$ is constant across tours. Both conditions hold on NK landscapes, yet standard NK shows no speed-up: states near the optimum do not carry more signal than average states. On an engineered NK family that satisfies this additional condition, ${\kappa }_f$-weighted draws from a basin-balanced restart pool require about 40% fewer restarts than uniform draws and 10–19% fewer than an equal-evaluation random two-step control. These counts exclude pool-scoring cost. Two of the three pre-search conditions can be decided before search, identifying cases where a gain cannot be credited to new information from the move set.