acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Local search evaluates the objective 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 needs no objective evaluations; its counterpart compares at the two resulting states. We identify two conditions necessary to credit a gain to this signal. Under coupling, differences in track the geometric disagreement. Under non-redundancy, 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, 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, -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.

Primary area:
reinforcement learning
Keywords:
local search, non-commutativity, combinatorial optimization, operator interactions, search heuristics, restart strategies, NK landscapes, SAT, traveling salesman problem

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_53kPOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper examines the question of whether there is any information to be gained by looking at the non-commutativity of actions in a local search. The paper describes one artificial example where a signal can be used to improve the move selection. The bulk of the paper is "definitional" type theorems, which result from the definitions themselves, and dont create much new insight.

The main weakness of the paper is its not clear that there is anything to be gained in practice from this exploration. The example used is contrived, and even some of the other examples discussed are odd. The paper itself is not very accessible, being weak on consistent notation, and using many concepts without introducing them.

Critical strengths

The paper investigates a general question about local search: whether non-commutativity of local moves exposes some usable structure that can be exploited in a local search.

Critical weaknesses

The examples used in the paper are all quite artificial, or none of the new mechanisms provide any worth. Without a realistic local search problem that can benefit from the approach there is no discernible advantage from the approach.

Overall Algorithm 1 is an algorithm built to take advantage of the theorems of the paper, but without an non-artificial local search problem that has the required behaviour its hard to argue for its value.

The paper is poorly presented, with lack of definition of much terminology.

l.22. What are NK landscapes?

l.48. What is UCDS?

l.187. Make the pair (i,j) explicit in the definition.

l.210. Its not clear at all what is the purpose of this paragraph. First d_k and f_k are not defined! Please rewrite to make this clearly defined and understandable.

l.258. What is a basin, presumably a subset of X where a one step greedymove policy leads to the same local minima (or plateau). Please define it.

l.277. The measure DX is too tersely defined to be understood. Does the move always result in a difference of 2 (if the edges are considered undirected, or b - a + 1 (if they are considered directed)

l.294. Even here the NK problem is not fully introduced.

l.307. Is their interest on problems with random tables?

Questions for authors

l.134. The approach assumes a function dX, cant we perform local search without such a notion (we just need \Sigma)? Or can we use simple dX where dx(x1,x2) = 0 iff x1 == x2 and 1 otherwise?

l.323. This definition of "Clause-based moves" seems bizarre, and only introduced so that we simply dont have \kappa = 0, which is the case for variable flip moves (the moves actually used by WalkSAT etc). Is their any existing local search SAT approach using such moves, please add a reference.

Reviewer_94pWOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the impact of the asymmetry between a sequence of local moves and how this information can influence a restart strategy. It proves some theoretical results on this measure and show that a small black-box testcase benefits from it. The paper is not a great fit for the conference. The practical value of the results is not demonstrated.

Critical strengths

Some theoretical results on the value of measuring asymmetries in local serach

Critical weaknesses

Not that impactful and poor match for the conference

Questions for authors

N/A

Reviewer_zhU7OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper consider local search and asks whether investigating non-commutativity of move operators can provide useful information. It focuses on four aspects of non-commutativity over four problems (TSP, SAT, NK, and block NK). The paper provides an algorithm UCDS-Core which attempts to utilise the findings. An experimental comparison with other methods is given.

In overall, this is a well written paper. However, I fail to see the significance of the results: It is clear that the results will depend strongly on the class of fitness functions considered, and the set of move operators. Do the results provide any insights beyond the problem instances that were studied? I would have preferred a paper which showed deeper results for a single problem class.

The research question of the paper is perhaps too general: It seems quite clear that considering impact of two moves can provide some information. The question is how this information is used. Can we derive new algorithms with provable speedup compared to the baseline local search algorithms?

When comparing algorithms, Figure 2 reports the number of restarts. It would be more conventional and informative to see the the number of function evaluations used to reach the optimum.

Critical strengths

The paper is well written.

Critical weaknesses

The authors have not clearly laid out the significance of the work.

Questions for authors

If the results have significance beyond the problem instances considered, please explain why.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.