Heuristic:Princeton nlp Tree of thought llm Duplicate Candidate Zeroing
| Knowledge Sources | |
|---|---|
| Domains | Optimization, Search_Algorithms, LLM_Reasoning |
| Last Updated | 2026-02-14 04:00 GMT |
Overview
Local deduplication strategy that assigns a score of 0 to duplicate candidate thoughts within a single BFS step, promoting diversity in the selected candidates.
Description
During each BFS step, the LLM may generate identical candidate thoughts (especially at lower temperatures or when the search space is constrained). The get_values() function maintains a local_value_cache dictionary within each evaluation call. If a candidate string y has already been seen and scored in the current step, the duplicate receives a score of 0 instead of being re-evaluated. This both saves an LLM call and ensures that the selection step favors diverse candidates over repeated identical ones.
Usage
This heuristic is active by default in every BFS step when using value-based evaluation (--method_evaluate value). It is most impactful when n_generate_sample is high (many samples per step) and temperature is low (more likely to produce duplicates). No configuration is needed — the behavior is hardcoded.
The Insight (Rule of Thumb)
- Action: Score duplicate candidates as 0 within each evaluation step using a local cache keyed by the candidate string.
- Value: Prevents the same candidate from occupying multiple selection slots, improving search diversity.
- Trade-off: A truly valuable repeated candidate will be penalized after its first occurrence. This is acceptable because keeping multiple identical candidates provides no new information to the search.
Reasoning
In tree search with sampling, generating n candidates can produce duplicates — the same arithmetic step or writing plan. If all duplicates received their true (high) score, greedy selection would pick the same candidate k times, wasting the beam width. By zeroing duplicates, the algorithm naturally diversifies the beam. The cost is negligible (a dictionary lookup), and the saved LLM calls compound across steps.
Code Evidence
Local deduplication from `src/tot/methods/bfs.py:16-26`:
def get_values(task, x, ys, n_evaluate_sample, cache_value=True):
values = []
local_value_cache = {}
for y in ys: # each partial output
if y in local_value_cache: # avoid duplicate candidates
value = 0
else:
value = get_value(task, x, y, n_evaluate_sample, cache_value=cache_value)
local_value_cache[y] = value
values.append(value)
return values