In a Tree of Thoughts loop, how is backtracking implemented and how do you avoid re-expanding duplicate states?
answer
- the model keeps nothing between calls
- frontier as stack versus ranked level
- store the prefix, re-send it
- canonical key, not raw text
- expansions exceeding the predicted count
basics
~20 sThe tree lives in your orchestrator, not the model. A state is the stored thought prefix, so backtracking means popping the frontier to a parent and re-sending that prefix for its next untried child. Duplicates are suppressed by a visited set keyed on a canonical form of the state.
solid answer
~50 sBecause each model call is independent, there is nothing inside the model to rewind. Your loop keeps the tree: every node is a state — the accumulated thought prefix plus whatever structured form the task uses — with a pointer to its parent and a record of which children have been tried. The frontier is a stack for depth-first search or a ranked level for a beam. Backtracking is then a pure bookkeeping operation: pop back to the parent and re-send its prefix to generate or continue with the next child. A visited set matters because different orders of the same steps can reach the same partial state, and expanding it twice pays twice for an identical subtree. Key the set on a canonicalised state — normalise whitespace and casing, sort parts whose order is irrelevant, round numbers — rather than on the raw text, since free-form thoughts rarely repeat verbatim. The diagnostic is simple: if expansions exceed what width, branching and depth predict, you are expanding duplicates.
code
python · 24 linescanon = lambda s: tuple(sorted(s))
def dfs(root, expand, is_goal, max_depth):
stack = [(root, 0)]
visited = {canon(root)}
expansions = 0
while stack:
state, d = stack.pop()
if is_goal(state):
return state, expansions
if d == max_depth:
continue
expansions += 1
for child in reversed(expand(state)):
key = canon(child)
if key not in visited:
visited.add(key)
stack.append((child, d + 1))
return None, expansions
expand = lambda s: [s + (x,) for x in ("a", "b")]
is_goal = lambda s: sorted(s) == ["a", "b", "b"]
print(dfs((), expand, is_goal, max_depth=3))go deeper
Know that the tree is kept by your own code, not by the model, and that going back a step means re-sending the earlier prefix rather than asking the model to undo anything.
Explain the data structures: a stack for depth-first, a ranked level for a beam, per-node parent pointers and tried-children counts, and a visited set keyed on a canonical state.
Show how you would catch duplicate expansion in production — expansion counts against distinct canonical keys, compared with the arithmetic the configuration predicts — and design the state representation so the key is exact.
Own the call on whether the space is genuinely a graph and dedupe is warranted, and on where similarity-based dedupe crosses from a cost saving into a silent correctness risk.
## The tree is yours, not the model's A model call maps a prompt to a completion; it retains nothing across calls beyond what you put in the prompt. So in Tree of Thoughts every structural element — nodes, parents, children, the frontier, the visited set — is data in your orchestrator. This is the single most clarifying fact about the algorithm, and it makes backtracking unremarkable: there is no state to undo, only a different prefix to send. A node typically carries: the state itself (the thought prefix, or a compact structured description of where the reasoning stands), a parent reference, the depth, the score assigned when it was ranked, and the list of children already generated or tried. ## The frontier The frontier is the set of nodes eligible for expansion, and its data structure is what makes a search depth-first or breadth-first: - **Stack** — pop the most recent node, so the search drives downward. Backtracking is the stack popping past exhausted nodes on its own. - **Ranked level** — hold the surviving states of one depth, expand all of them, rank the candidates, replace the level. There is no backtracking here in the depth-first sense; the beam simply keeps alternatives alive laterally. - **Priority queue** — pop the best-scoring node anywhere in the tree, which mixes the two orders and allows returning to a promising node abandoned several levels ago. It needs states of differing depths to be comparable, which is a real constraint. ## Implementing backtracking Depth-first backtracking, concretely: expand a node, push its children, descend. On a dead end — a failed goal test, a contradiction, or the depth cap — do nothing more with that node; the stack automatically resumes at the nearest ancestor with children still unexpanded. To re-enter that ancestor's next child you re-send its stored prefix, which is why the prefix must be stored rather than reconstructed from the conversation. A crossword search that must undo one across answer and the three downs it constrained is one pop and one re-send, not four undo instructions to the model. Two bookkeeping details are easy to get wrong. First, never mutate a shared state object in place as you descend; children should be new values derived from the parent, or the parent will be corrupted when you come back to it. Second, record per-node how many children have been tried, so an ancestor revisited after a long descent does not re-generate candidates it already explored. ## The visited set Distinct paths often converge. In a route planner, visiting aisles A then B leaves you exactly where visiting B then A does; in a research search, two different orderings of the same sub-questions produce the same evidence set. Without dedupe, the search expands both and pays twice for the identical subtree below them. This is invisible in output quality and very visible on the bill. The hard part is the key. Raw thought text almost never repeats verbatim, so hashing it dedupes nothing. Options, in rising order of cost and risk: 1. **Structured state.** If the task has a real state — the filled cells of a grid, the set of aisles visited, the facts gathered — key on a canonical serialisation of that: sorted, normalised, numbers rounded. This is exact and cheap and is why representing state structurally rather than as prose is worth the effort. 2. **Normalised text.** Lowercase, collapse whitespace, strip filler. Catches near-verbatim repeats only. 3. **Similarity dedupe.** Embed the state and treat anything above a similarity threshold as visited. Catches paraphrase, but a badly chosen threshold silently discards genuinely distinct branches — which is a correctness bug, not a cost bug, and much harder to notice. ## Diagnosing the duplicate-expansion bug The symptom is arithmetic. A beamed run should expand about width x branching x depth candidates; if the counter reports meaningfully more, something is being expanded twice. Count expansions and count distinct canonical keys; the ratio between them is the waste. Logging each expansion with its parent identifier makes the converging paths visible directly. The same instrumentation answers the related question of whether the beam is holding duplicates — if several survivors share a canonical key, the beam is nominally wide and actually narrow. ## When to skip dedupe If paths genuinely cannot converge — each step consumes a distinct input and order is meaningful — a visited set is pure overhead and one more thing to get wrong. Say so rather than adding it reflexively. The judgement is whether the state space is a tree or really a graph drawn as a tree.
- Why does keying a visited set on raw thought text usually fail?Because generated prose is rarely identical twice, even when the underlying state is the same — wording, ordering and hedging all vary. The hash then differs and nothing is deduplicated. The fix is to key on a canonical form of the state the thought represents: a sorted, normalised serialisation of the structured facts, the filled cells, or the set of steps taken, which is one more reason to carry structured state alongside the prose.
- What goes wrong if you dedupe states by embedding similarity with a loose threshold?You start discarding branches that are genuinely different but phrased alike, which turns a cost optimisation into a correctness bug. The search silently loses coverage and the symptom looks like poor reasoning rather than a broken visited set. If you use similarity dedupe, calibrate the threshold against pairs you have labelled as same or different, and log every suppression so the losses can be audited.
- How would you detect duplicate expansion in a running system?Compare the expansion counter with the count of distinct canonical state keys; a gap between them is the waste, and its ratio is the overspend. Cross-check against the arithmetic prediction of width times branching times depth. Logging each expansion with its parent identifier shows the converging paths directly, and the same data reveals whether several beam survivors share a key, which means the beam is narrower than it looks.
saying these in an interview costs you the question
- Believing the model remembers the tree between calls
- Sending an instruction to make the model forget steps
- Hashing raw thought text as the visited key
- Mutating a shared state object while descending
- Adding a visited set where paths cannot converge