Is backmarking the same as memoization?

It shares the idea of reusing computation, but refers to particular bookkeeping techniques for consistency checks during constraint search.

Can it work with backjumping?

Yes. Research has studied combinations because they address different sources of search cost.

Does it require machine learning?

No. It is a search optimization based on recorded checks and assignment changes.

AI Glossary / Graphs and symbolic AI / Intermediate

Backmarking

Definition

Backmarking is a constraint-search technique that remembers information from earlier compatibility checks so that the solver can avoid repeating checks whose results remain valid. It reduces redundant work during backtracking without changing the constraints or which complete assignments count as solutions.

What it means

In a search tree, the solver can revisit a variable and candidate value after changing another part of the partial assignment. A naive implementation may repeat every earlier consistency check, even when the assignments relevant to a particular check have not changed.

Backmarking keeps enough information about previous successes or failures to recognize some of this repetition. If a candidate still conflicts with an unchanged earlier assignment, the solver can reject it again without redoing the same constraint test. Previously successful checks can also be reused when their supporting context remains intact.

This is different from backjumping. Backjumping changes where search returns after a dead end; backmarking changes which compatibility tests need to be repeated. The techniques can be combined, but one should not be used as a synonym for the other.

How it works

The solver tracks consistency-check results and the assignment history relevant to them. Classical presentations use markers that summarize where a candidate failed and which earlier assignments have changed since it was last considered.

On revisiting a candidate, the solver compares those markers with the current search context. A remembered failure remains decisive only if the assignments responsible for it still hold. A remembered success can avoid repeated testing only where the relevant earlier assignments remain unchanged. When the context changes, the corresponding checks must be performed again or otherwise justified.

The exact bookkeeping depends on the algorithm and constraint representation. The important principle is conditional reuse, not permanent caching of “good” and “bad” values. Memory and bookkeeping have a cost, so the method is especially interesting when repeated constraint tests are expensive enough for avoiding them to matter.

Three practical examples

A product configurator avoids repeating a component compatibility lookup after only an unrelated packaging choice changes.
A timetable solver reuses an unchanged pairwise room-conflict result while exploring alternative values elsewhere in the schedule.
A teaching solver records consistency checks during a small puzzle search to show how repeated visits can require less repeated computation.

Think of it this way

Think of an inspector keeping notes that say, “These two selected parts do not fit together.” If only the box color changes, there is no need to repeat that fit check. If one part changes, the note may no longer apply.

The limit is that a computer must track the exact conditions supporting reuse. A vague memory that something failed earlier is insufficient. Reusing a result after its conditions change can incorrectly reject a valid configuration.

Worked example

Reusing a failure only while it applies

Consider variables A, B and C, assigned in that order. A and C take values 1 or 2, while B selects red or blue. The constraint is A ≠ C; B is unrelated to it.

With A = 1 and B = red, testing C = 1 fails because it equals A. Record that the failure depends on A = 1. If another part of the search later revisits C = 1 with A still 1 but B now blue, the same failure remains valid. Repeating the A-versus-C test adds no new information.

If search changes A to 2, however, the old failure cannot be reused. C = 1 now satisfies A ≠ C. The remembered result was about the pair of assignments, not a permanent statement that C = 1 is illegal.

A full backmarking algorithm organizes this reuse with markers and search bookkeeping.

Illustrative case study

Fictional case: Alder Kits uses a configurator whose compatibility tests consult a detailed engineering table. The solver repeatedly reaches the same component pair after changing accessories that do not affect compatibility.

The developers add backmarking information and instrument the number of actual compatibility tests. They also test cases where an earlier component changes, ensuring that stale results are not reused. A small reference solver provides a comparison for the valid configurations returned.

The team treats fewer repeated checks as a computational improvement, not a relaxation of engineering requirements. It measures total runtime as well, because maintaining the extra information can offset some savings when individual checks are cheap.

Common misconceptions and mistakes

A rejected value should remain rejected for the entire search. Its rejection may depend on assignments that later change.
Backmarking automatically jumps to the cause of a conflict. Choosing the return point is the role of backjumping or other search control.
Caching every result without dependencies is enough. Valid reuse requires knowing when the result still applies.
Fewer constraint checks always means lower runtime. Bookkeeping and memory access also consume resources.
The technique changes the solution space. Correct backmarking avoids repeated work while preserving the original problem.

Business use

Backmarking is relevant to configuration and allocation systems that perform many repeated compatibility tests. Its practical value depends on the cost of the checks, how often relevant assignments stay unchanged and the overhead of maintaining the reuse information.

When evaluating a solver, examine both performance and correctness under changing assignments. If constraints themselves can change during operation, establish when stored results must be invalidated. A cached compatibility judgment from an earlier product-rule version should not silently govern a revised catalog.

Check your understanding

A candidate failed because of A = 1. The solver changes only unrelated B and revisits the candidate. Later it changes A to 2. In which case can the old failure be reused?

Answer: It can be reused while A = 1 still holds and the relevant constraint is unchanged. Changing A requires reconsidering the check.

Related terms

Backjumping
Constraint satisfaction
Memoization
Backtracking
consistency check
dependency tracking
constraint recording
cache invalidation

Learn next

Trace a tiny search and write down every pairwise constraint test. Mark tests repeated with exactly the same relevant assignments. Then change one earlier assignment and identify which recorded results become unusable. Compare this exercise with backjumping, where the main question is which earlier decision to revisit.

Backjumping

Sources

Russell and Norvig, Constraint Satisfaction Problems chapter, describes backmarking as reuse of consistent and inconsistent pairwise assignments: https://aima.cs.berkeley.edu/newchap05.pdf

Dechter and Frost, Backtracking Algorithms for Constraint Satisfaction Problems, author-hosted overview: https://ics.uci.edu/~dechter/publications/r54.html

The assignment example and fictional configurator case are original illustrations of conditional result reuse.

Previous: Backjumping Next: Backoff