AI Glossary / Graphs and symbolic AI / Intermediate
Trail
Definition
A trail is a record of reversible changes made during a search or computation, used to restore an earlier state when backtracking. In Prolog implementations, it records variable bindings and other supported assignments that may need to be undone.
What it means
A search process often makes a tentative choice, derives consequences and then discovers that the choice fails. Before trying an alternative, it must remove the consequences that belong only to the failed branch.
A trail supports that restoration without necessarily copying the entire state at every choice. It records enough information about relevant changes for the implementation to undo them later. In simple variable binding, that may mean remembering which variable must become unbound again; other reversible updates may require an old value as well.
This is the logic-programming and backtracking meaning. Graph theory also uses trail for a walk that does not repeat edges, while an audit trail records activity for review. Those are different concepts despite the shared name.
How it works
When the search creates a choice point, it can record the current position in the trail. Subsequent reversible changes are added as required by the implementation. If the branch fails, the engine works backward through the changes made after that marker and restores the earlier state.
Nested choices require distinct restoration boundaries. Backtracking out of an inner branch should undo its changes while retaining bindings established before that branch. Backtracking farther may undo those earlier bindings too.
Real engines optimize this process. They need not record every assignment when another memory-management mechanism can safely discard the affected data. The trail is also not a universal transaction log: file output, external messages and other side effects are not automatically reversed merely because logical search backtracks. The supported restoration rules must be understood explicitly.
Three practical examples
- A Prolog query tries one candidate value, fails a later condition and restores bindings before exploring the next candidate.
- A constraint solver records domain changes made under a tentative assignment so they can be reversed when that branch is rejected.
- A teaching search engine uses a stack of old values and choice-point markers to compare restoration with full-state copying.
Think of it this way
Think of writing reversible edits on a notepad, with a bookmark showing where a trial began. If the trial fails, you undo edits backward until you reach that bookmark.
The analogy explains restoration order and scope. It does not imply that an actual engine stores human-readable descriptions, or that every action can be undone. Sending a message outside the program cannot be recalled just by erasing a note in memory.
Worked example
Restoring the correct branch boundary
Consider an invented search with variables X and Y initially unbound. At outer choice point P, the trail marker is zero. The branch binds X to red and records a reversible change. It then creates inner choice point Q, whose marker is one.
The inner branch binds Y to blue, making two recorded changes in this simplified model. A later condition fails. Restoring to Q undoes the Y binding only: X remains red and Y becomes unbound. The next inner alternative can bind Y to green while still using X = red.
If all inner alternatives fail and the search returns to P, restoration also undoes X. Both variables are then unbound before the next outer alternative. This illustrates the logical restoration requirements, not the exact number or layout of entries used by a particular Prolog implementation.
Illustrative case study
Fictional case: Cedar Rules develops a small allocation solver. During a trial branch, it updates a shared availability structure. On failure it resets the chosen variable but forgets a derived availability change, causing the next branch to reject a valid option.
The team defines which changes belong to each choice point and adds restoration records for the mutable state it controls. Tests inspect the state immediately before a choice and immediately after backtracking to it. A second test checks nested choices so an inner rollback does not erase valid outer assumptions.
The team also moves external notifications out of speculative branches. The case illustrates state restoration and side-effect boundaries; it does not claim that all programming-language runtimes use the same trailing mechanism.
Common misconceptions and mistakes
- A trail is the complete search tree. It records restoration information for relevant changes, not necessarily every visited state.
- Backtracking undoes every effect. Ordinary external side effects require their own handling and may not be reversible.
- Restoring an inner choice should clear all bindings. It must preserve bindings that were already established at that choice point.
Business use
Trailing matters when an AI solver explores alternatives using mutable state. Correct restoration prevents one failed attempt from contaminating later attempts, which can otherwise create subtle missing-solution or incorrect-solution errors.
For teams integrating a solver, clarify which state is managed by the engine and which belongs to application code or external systems. Verify restoration across nested choices and failure paths. Evaluate memory and runtime under realistic search depth; a trail saves some copying work but is not free.
People also ask
Is a trail the same as a call stack?
No. A call stack records execution contexts; a trail records changes that may need reversal, although both can participate in backtracking.
Must a trail store every previous state?
No. It typically stores enough information to undo changes rather than full snapshots.
Does Prolog backtracking remove printed output?
Ordinary printed output remains. Logical variable restoration should not be confused with undoing external effects.
Check your understanding
X is bound before choice point Q. Y is bound after Q. The search backtracks only to Q. Which binding should be undone?
Answer: Y's binding should be undone, while X's earlier binding remains. A farther backtrack may later undo X as well.
Related terms
- Unification
- Constraint propagation
- Backtracking
- choice point
- variable binding
- Prolog
- reversible state
Learn next
Read backtracking and unification. Trace a two-level search with two tentative variables, writing down the trail marker at each choice. Check which changes survive each possible rollback.
More in Graphs and symbolic AI
- Total Turing Test - The total Turing Test is an expanded behavioral test that includes perceptual and physical interaction as well as conversation.
- Tournament - A tournament is a directed graph with exactly one directed edge between each pair of distinct vertices.
- Tractability - Tractability describes whether a computational problem can be solved with manageable resources.
- Training curve - A training curve plots a model's measured performance against progress through training, such as optimization steps or epochs.
- Transient failure - A transient failure is a temporary malfunction that disrupts an observation or operation without necessarily leaving the component permanently broken.
- Transition kernel - A transition kernel specifies a probability distribution over possible next states for each current state.
Sources
SWI-Prolog reference manual, system memory areas and the trail stack: https://www.swi-prolog.org/pldoc/man?section=limits
SWI-Prolog developer explanation of ordinary and assignment trail entries: https://swi-prolog.discourse.group/t/how-does-setarg-3-works-with-backtracking/8668
Relevant official documentation and the developer's explanation were read. The marker-based worked example is an original simplified model, not a claim about exact runtime memory layout or an executed Prolog trace.
Previous: Tragedy of the commons Next: Train/validation/test split