The Hazards of Fancy Backtracking

Andrew B. BakerAAAI 1994

Introduction

In the domain of Constraint Satisfaction Problems (CSPs)—which encompass tasks ranging from Sudoku to complex industrial scheduling—the standard approach to finding a solution is "backtracking." When a search hits a dead end, it retreats to the most recent decision and tries an alternative. However, standard backtracking is often inefficient because it erases valid work along with the mistakes.

To address this, "intelligent" backtracking algorithms like Dynamic Backtracking (DB) were developed. DB aims to jump directly to the source of a conflict without wiping out intervening assignments. Paradoxically, researchers observed that these "smarter" algorithms often performed significantly worse—sometimes exponentially so—than their simpler counterparts on standard benchmarks. Andrew Baker’s research investigates this phenomenon, identifying a critical interaction between search heuristics and state preservation.

The Problem: Why "Smart" Search Fails

The core issue lies in how these algorithms handle "junk" data. In standard Depth-First Search (DFS), retreating from a conflict clears the slate. In Dynamic Backtracking, the algorithm attempts to preserve intermediate work. Baker discovered that this preserved work often breaks the search heuristics—the "rules of thumb" used to decide which variable to assign next.

When DB keeps an old assignment whose original logical justification has vanished, it "pollutes" the search state. This leads to a "branching illusion" where the algorithm effectively forces the search to branch on variables prematurely, potentially doubling the remaining search space repeatedly and leading to an exponential slowdown.

Methodology and Datasets

Baker performed a head-to-head comparison of three techniques:

  1. Chronological Backtracking (DFS): The standard "undo the last move" approach.
  2. Backjumping: A version that jumps to the conflict source but still erases intervening work.
  3. Dynamic Backtracking (DB): The version that preserves intermediate assignments.

The study utilized randomly generated 3-SAT problems at the "crossover point" (a clause-to-variable ratio of approximately 4.24), where problems are most difficult to solve. Experiments scaled from 10 to 60 variables, using 100 satisfiable and 100 unsatisfiable instances for each size.

Key Results: The Exponential Explosion

The initial quantitative results were startling. As the number of variables increased, the performance of Dynamic Backtracking degraded at an alarming rate compared to standard DFS.

Initial performance comparison showing the exponential explosion of Dynamic Backtracking assignments compared to DFS and Backjumping.

As shown in the data, at 60 variables, standard DFS required an average of only 709 assignments. In contrast, Dynamic Backtracking required a staggering 212,596 assignments for the same problems. The "intelligent" algorithm was outsmarting itself by clinging to irrelevant data that misled its heuristics.

The Solution: Selective Erasure

Baker proposed a simple but effective fix: "undoing unit propagation." This modification forces the algorithm to erase a variable's value if the logical reason for that value (the "nogood") is deleted. By selectively erasing assignments when their justification disappears, the search state remains "clean," allowing heuristics to function effectively.

Performance comparison after implementing the proposed fix, showing Dynamic Backtracking's recovery and slight edge over DFS.

With this modification, the performance gap vanished. For the same 60-variable problems, the modified Dynamic Backtracking dropped from over 200,000 assignments to just 672, making it slightly more efficient than standard DFS.

Conclusion and Future Directions

The "hazard" identified by Baker is not a failure of logic, but a toxic interaction between clever backtracking and clever heuristics. While logically sound, keeping intermediate work is heuristically disastrous if that work is no longer justified.

Future work may explore how this principle applies to non-Boolean problems, where justifications are less binary. Baker suggests potential "thresholding" techniques—deleting values only when they lose a certain percentage of their supporting constraints—or utilizing newer "partial-order dynamic backtracking" methods to maintain search efficiency without falling into the "junk work" trap.

Summary updated

BibTeX
@inproceedings{baker1994hazards,
  author = {Andrew B. Baker},
  title = {{The Hazards of Fancy Backtracking}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure