AI Glossary / Graphs and symbolic AI / Advanced

Dependency-directed backtracking

Definition

Dependency-directed backtracking is a search and reasoning approach that uses the dependencies behind a failure to decide which earlier assumptions or choices to reconsider. Instead of mechanically undoing the most recent choice, it traces the conflict to relevant decisions. This can avoid exploring alternatives that cannot resolve the identified problem.

What it means

A failed plan or configuration may depend on an early decision while several later decisions are irrelevant. Changing those later decisions wastes effort if the same underlying contradiction remains. Dependency information provides a reason to return to the choice that matters.
The dependencies are logical supports within a model: which assumptions, facts, and rules produced a conclusion or contradiction. The term covers a broader idea than one fixed algorithm. Conflict-directed backjumping is a related concrete technique in constraint solving. Systems differ in how they record explanations, retract conclusions, preserve unaffected work, and remember combinations that cannot succeed.

How it works

As a system makes assumptions and derives consequences, it records their justifications. When a contradiction appears, it examines those justifications to identify supporting choices. It then revises an implicated assumption and updates conclusions whose support no longer holds.
In a constraint-search implementation, a conflict explanation can identify earlier assignments responsible for exhausting a variable's legal values. Backjumping can skip intervening choices that are absent from that explanation. Learning a “nogood” can additionally record an incompatible assignment combination for later reuse.
These operations require sound bookkeeping. A jump must not discard a possible solution without justification, and a retained conclusion must still have valid support. Tracking explanations consumes time and memory, so fewer search branches do not automatically mean lower runtime.

Three practical examples

• Product configuration: A selected power supply conflicts with a required module. Choices about casing color and packaging do not fix that incompatibility. Dependency analysis can direct reconsideration toward the supply or module assumptions.
• Scheduling: A session's required room is unavailable during the chosen time slot. Adjusting an unrelated session's display title cannot help. A solver needs to identify which actual time, room, and resource constraints explain the failure.
• Symbolic analysis: A reasoning system derives inconsistent values from a set of hypothetical assumptions. Recorded justifications allow it to investigate which assumptions supported the conflicting conclusions, rather than restarting every inference from scratch.

Think of it this way

Imagine assembling furniture and discovering that an early bracket choice prevents the final shelf from fitting. Undoing the most recently attached decorative cap will not solve the problem. An assembly record that connects the shelf fit to the bracket helps identify the relevant decision. It still takes a correct record to justify what can remain assembled.

Worked example

Consider an invented configuration problem with four variables chosen in order: supply P, casing color C, label style L, and module M. P can be Standard or Heavy. C can be Blue or White. L can be Plain or Bold. M has the single allowed value HighPower because of a fixed requirement.
The compatibility constraint says that HighPower requires Heavy. Color and label style do not affect compatibility. Assume a simple search that checks this compatibility only when assigning M, without earlier propagation.
The solver first chooses Standard, Blue, Plain. At M, its only value fails. A chronological search may try Bold, then White with each label style, encountering the same module failure across four color-label combinations under Standard.
A dependency-aware explanation identifies P = Standard, the fixed module requirement, and the compatibility constraint as sufficient for the contradiction. C and L are irrelevant. The solver can return directly to P rather than trying their alternatives to repair this conflict.
Changing P to Heavy permits HighPower, and any of the four color-label combinations works. A suitable learned nogood can exclude P = Standard while the same fixed requirement and constraint remain in force.
This example demonstrates avoidable branches, not a universal speedup. A solver using early propagation could reject Standard sooner, and different dependency-directed methods may retract or reconstruct intermediate assignments differently.

Illustrative case study

Fictional Maple Configurations reviews a configurator that repeatedly fails near the end of a product setup. Its diagnostic trace shows many attempts to change cosmetic options even though the underlying issue is an incompatible electrical component selected earlier.
The team adds explanations linking compatibility failures to the relevant component assignments. It checks that cosmetic choices are truly absent from those constraints and that changed assumptions invalidate the appropriate derived conclusions.
The revised evaluation compares explored branches, explanation overhead, memory, and solution correctness on representative configurations. The team also changes the component requirement in a test to ensure an old nogood is not reused outside its valid context. This case is illustrative, not a reported deployment.

Common misconceptions and mistakes

“It always changes the last decision.” Its purpose is to use relevance rather than chronology alone.
“An implicated choice is permanently wrong.” It may be incompatible only with other current assumptions.
“Every skipped assignment is preserved.” Retention depends on the algorithm and valid support.
“Backjumping and learning are identical.” Jumping changes where search resumes; learning records reusable information.
“A smaller search tree guarantees faster execution.” Explanation management can add substantial overhead.

Business use

Use dependency explanations to make configuration and planning failures more actionable. Distinguish fixed requirements from changeable preferences, and show which combinations create the conflict. Avoid presenting a technical conflict explanation as proof that one individual input is inherently bad.
Evaluate the approach with both satisfiable and unsatisfiable cases. Test what happens when constraints change, because cached explanations and nogoods may need invalidation. Measure end-to-end performance and correctness, including bookkeeping costs and whether valid alternatives remain discoverable.

People also ask

Is it the same as ordinary backtracking?

No. Ordinary chronological backtracking revisits recent choices in order; dependency-directed methods use reasons for failure.

Does it eliminate difficult search?

No. It can reduce redundant work without removing the underlying problem's general difficulty.

Is it related to truth maintenance?

Yes. Managing justifications and revising dependent conclusions is central to that connection.

Check your understanding

Why cannot a different casing color fix the example?

Answer: Compatibility depends on the supply and module, not color.

What justifies rejecting Standard in this model?

Answer: The fixed HighPower requirement and the compatibility constraint together.

What must happen if that requirement changes?

Answer: Any learned conclusion depending on it must be reassessed.

Related terms

• Backjumping
• Conflict set
• Constraint satisfaction
• Justification
• Constraint propagation
• Backtracking
• nogood learning
• truth maintenance system

Learn next

Build a small configuration problem with two irrelevant choices between a cause and its detected conflict. Trace chronological search, then record a sound failure explanation and show which branches it allows the solver to skip.

More in Graphs and symbolic AI

• Demonic nondeterminism - Demonic nondeterminism is an interpretation of unspecified choice in which a required guarantee must withstand every permitted alternative, including...
• Dempster-Shafer theory - Dempster-Shafer theory, also called evidence theory or the theory of belief functions, is a mathematical framework for representing uncertain evidence.
• Dependency grammar - Dependency grammar is an approach to describing sentence structure through relationships between words, typically linking a head word to its dependents.
• Depth First Search - Depth First Search, usually abbreviated DFS, is a graph or tree traversal strategy that explores one branch as far as it can before returning to explore...
• Depth First Search on Edges - Depth First Search on Edges is a traversal that explores graph connections in depth-first order while tracking edges as the items to visit.
• Depth-limited search

Sources

Stallman and Sussman, Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis, MIT report abstract: https://dspace.mit.edu/entities/publication/83fbfa70-70f0-4170-b9b0-b7598e75c1a6 Russell and Norvig, Constraint Satisfaction Problems, backjumping, learning, and historical discussion: https://aima.eecs.berkeley.edu/2nd-ed/newchap05.pdf

Previous: Dependability state model Next: Dependency grammar