--- title: 'Tree of Thoughts' source: 'https://academia.sh/en/courses/prompt-engineering/tree-of-thought' course: 'Prompt Engineering' language: en updated: '2026-10-21T05:02:34+00:00' license: 'CC BY-SA 4.0' objectives: - 'Builds a tree of thoughts that splits a solution into steps and asks for several extensions at every step, and counts the generation calls and the selection calls separately.' - 'Measures the effect of the branching factor and the depth on the number of calls and the token cost: shows how calls grow as branching increases and where the gain stops.' - 'Compares the difference an added branch contributes with the difference between two runs of the same arrangement, and decides whether the difference is measurable.' - "Compares the tree's numbers with the previous lesson's self-consistency arrangement, in calls and in tokens separately." --- # Tree of Thoughts Measuring branching from the middle of a solution: on the same 48 fictional support tickets, the arrangement that asks for all thirty-two fault codes in a single prompt gives 0.4792 accuracy with 48 calls; the tree of thoughts, which splits the solution into steps and asks for several extensions at every step, falls to 0.0833 at branch 1, rises to 0.6250 at branch 3 and stops at branch 4. As branching goes from 3 to 4, accuracy slips by 0.0208 while the number of calls goes from 795 to 1086 and tokens from 43182 to 59835; since this difference is smaller than the 0.0417 difference between two runs of the same arrangement, it counts as unmeasured. The previous lesson ran the same prompt several times and voted on the responses. Self-consistency worked: the number a single response caught went up with the consensus of nine samples. But the generated solutions had one thing in common. Each was generated **independently from start to finish**; none saw where another went wrong. The first step of a solution was never held fixed while the second step was tried in several different directions, and a path going badly was never abandoned halfway. This lesson fills that gap. What is changed is again the text, but this time not a single prompt but **the arrangement of prompts**: instead of one long prompt, short prompts that each move the solution one step forward, and a rule that selects the branches to keep. What will be measured is what this gains and **how many calls** it costs. - **RT21.** The task is **fictional**: short support tickets are assigned a fault code with three components — area, symptom and degree. Four areas, four symptoms per area, two degrees; thirty-two codes in total. - **RT22.** What is called is a **simulator**; no request goes to a real model endpoint. The simulator keeps the form built in this curriculum's introductory course, with one difference: the option set is given from outside and each option is a **path**, whose score is summed from the cues of its components. - **RT23.** Seed **20260218**; the same prompt gives the same response on the same seed. Uncertainty is measured by **changing the seed**, and the second run of every arrangement is taken with 20260219. - **RT24.** In the ticket text the area cue is **weak** and the symptom cue is **strong**; also, every ticket mentions **a misleading area** whose cue is heavier than the cue of the correct area. This construction opens the place where the tree will be measured: the first step is taken with the weakest evidence. - **RT25.** The tree makes two kinds of calls. An **extension** call extends a path by one step and is repeated as many times as the number of branches; a **selection** call filters the candidates that accumulate down to the ones to keep. Both are counted. - **RT26.** The branching factor and the number of kept branches are held **equal**. The scale is small: at most four branches, at most three levels of depth. The criterion is **all three components being correct at once**. - **RT27.** The cost is written in three units: the **number of calls**, **tokens** and **failed calls**. Since the rate limit depends on the number of calls, branching multiplies failures too. ## Branching from the Middle of a Path The previous prompt is a single one and asks for everything at once: all thirty-two codes are written into the prompt, the ticket is added, a single response is expected. The changed arrangement splits the same job into three steps — first the **area**, then the **symptom** of that area, then the **degree** — and asks for several separate extensions at every step; a part of the accumulated candidates is kept, the rest is dropped. The first block builds the simulator, the fictional code tree and the first two levels of one ticket. ```python # SIMULATOR. This code does not call a real model endpoint; it is a language model # simulator written with the standard library. The tickets and the fault codes are FICTIONAL too. import math SEED, M32 = 20260218, 0xFFFFFFFF WINDOW = 240 # context window, tokens def rng(t): x = ((t ^ (t >> 16)) * 2246822507) & M32 x = ((x ^ (x >> 13)) * 3266489909) & M32 s = [(x ^ (x >> 16)) & M32] def next_value(): s[0] = (s[0] * 1664525 + 1013904223) & M32 return s[0] / 4294967296 return next_value def pick(u, w): t = 0.0 for i, x in enumerate(w): t += x if u < t: return i return len(w) - 1 def tokenize(text): # FICTIONAL tokenizer: a piece has at most five characters out = [] for piece in text.lower().replace(",", " , ").split(): while len(piece) > 5: out.append(piece[:5]) piece = piece[5:] out.append(piece) return out def trace_id(text): # depends on the prompt's content, independent of the run h = 2166136261 for c in text: h = ((h ^ ord(c)) * 16777619) & M32 return h AREAS = ["dagitim", "sayac", "abonelik", "saha"] SYMPTOMS = {"dagitim": ["kesinti", "basinc", "sizinti", "tikanma"], "sayac": ["endeks", "bozukluk", "degisim", "okuma"], "abonelik": ["tarife", "fatura", "odeme", "kayit"], "saha": ["randevu", "erisim", "malzeme", "gecikme"]} DEGREES = ["birinci", "ikinci"] AREA_WORD = {"dagitim": "sebeke", "sayac": "olcum", "abonelik": "sozlesme", "saha": "ekip"} TRAP_WORD = {"dagitim": "hatti", "sayac": "cihaz", "abonelik": "hesap", "saha": "servis"} SYMPTOM_WORD = {"kesinti": "akmiyor", "basinc": "zayif", "sizinti": "islak", "tikanma": "dolmus", "endeks": "rakam", "bozukluk": "calismiyor", "degisim": "yenisi", "okuma": "girilmemis", "tarife": "basamak", "fatura": "tutar", "odeme": "borcum", "kayit": "musteri", "randevu": "saatte", "erisim": "kapali", "malzeme": "parca", "gecikme": "bekliyor"} DEGREE_WORD = {"birinci": "acil", "ikinci": "normal"} AREA_CUE = {AREA_WORD[a][:5]: a for a in AREAS} # area cue, weak TRAP_CUE = {TRAP_WORD[a][:5]: a for a in AREAS} # misleading area cue, heavier SYMPTOM_CUE = {SYMPTOM_WORD[s][:5]: s for a in AREAS for s in SYMPTOMS[a]} DEGREE_CUE = {DEGREE_WORD[d][:5]: d for d in DEGREES} TICKETS = [] for i in range(48): r = rng(SEED + i) area = AREAS[int(r() * 4)] symptom = SYMPTOMS[area][int(r() * 4)] degree = DEGREES[int(r() * 2)] trap = AREAS[(AREAS.index(area) + 1 + int(r() * 3)) % 4] # the misleading area in the ticket if r() < 0.5: text = (f"{TRAP_WORD[trap]} icin kayit acilmisti ama sorun {AREA_WORD[area]} tarafinda , " f"{SYMPTOM_WORD[symptom]} durumu var , {DEGREE_WORD[degree]} bakilmasi gerekiyor") else: text = (f"{TRAP_WORD[trap]} uzerinden bildirdim , {AREA_WORD[area]} ile ilgili " f"{SYMPTOM_WORD[symptom]} diye yaziyor , {DEGREE_WORD[degree]} olarak degerlendirin") TICKETS.append({"id": 5001 + i, "text": text, "code": (area, symptom, degree)}) ALL_CODES = [(a, s, d) for a in AREAS for s in SYMPTOMS[a] for d in DEGREES] COUNTER = [0, 0, 0] # number of calls, tokens, failed calls def join_path(p): return " ".join(p) def extend_paths(path, k): # all options that extend the path by k components paths = [path] for _ in range(k): grown = [] for q in paths: grown += [q + (s,) for s in (AREAS if not q else SYMPTOMS[q[0]] if len(q) == 1 else DEGREES)] paths = grown return paths def call(prompt, options, seed=SEED, temperature=0.6): COUNTER[0] += 1 toks = tokenize(prompt) COUNTER[1] += len(toks) if len(toks) > WINDOW or COUNTER[0] % 37 == 0: COUNTER[2] += 1 return {"input": len(toks), "response": None} r = rng(seed ^ trace_id(prompt)) p = {k: 0.15 for k in options} for t in toks: for table, w in ((AREA_CUE, 1.0), (TRAP_CUE, 1.3), (SYMPTOM_CUE, 1.6), (DEGREE_CUE, 0.9)): h = table.get(t) if h is not None: for k in p: if h in k: # an option is a path; the score is summed from its components p[k] += w d = sorted(p, key=join_path) if temperature <= 0.0: k = max(d, key=lambda a: p[a]) else: e = [math.exp(p[a] / temperature) for a in d] k = d[pick(r(), [v / sum(e) for v in e])] COUNTER[1] += len(tokenize(join_path(k))) return {"input": len(toks), "response": k} def build_prompt(lead, options, text): return (lead + " secenekler : " + " , ".join(join_path(k) for k in options) + " . Talep : " + text) x = TICKETS[2] print(f"FICTIONAL: {len(TICKETS)} tickets, {len(ALL_CODES)} fault codes " f"(4 areas x 4 symptoms x 2 degrees)") print(f"ticket {x['id']}: {x['text']}") print(f"correct code: {join_path(x['code'])}") s = call(build_prompt("Talebe bir ariza kodu ata .", ALL_CODES, x["text"]), ALL_CODES) print(f"single call: input {s['input']} tokens, response '{join_path(s['response'])}'") first, candidates = extend_paths((), 1), [] print("\nthree separate extension calls at the first level:") for j in range(3): u = call(build_prompt("Cozum yolunu bir adim uzat .", first, x["text"]), first, SEED + j) print(f" candidate {j + 1}: {join_path(u['response'])} (input {u['input']} tokens)") if u["response"] not in candidates: candidates.append(u["response"]) print("the extension of each branch at the second level:") for p in candidates: se = extend_paths(p, 1) u = call(build_prompt("Cozum yolunu bir adim uzat .", se, x["text"]), se) print(f" {join_path(p)} -> {join_path(u['response'])}") ``` ``` FICTIONAL: 48 tickets, 32 fault codes (4 areas x 4 symptoms x 2 degrees) ticket 5003: hesap uzerinden bildirdim , olcum ile ilgili rakam diye yaziyor , acil olarak degerlendirin correct code: sayac endeks birinci single call: input 235 tokens, response 'sayac endeks birinci' three separate extension calls at the first level: candidate 1: abonelik (input 43 tokens) candidate 2: abonelik (input 43 tokens) candidate 3: sayac (input 43 tokens) the extension of each branch at the second level: abonelik -> abonelik kayit sayac -> sayac endeks ``` Two numbers are visible right away. Writing the thirty-two codes into the prompt raises the prompt to **235 tokens**; the context window is 240, so the single-prompt arrangement stands five tokens below the limit. Since the tree's prompt carries only the options of that level, it is **43 tokens**. This is the first gain of splitting. The bottom four lines show why branching is needed. The word "hesap" (account) in the ticket is the cue of the misleading area and is heavier than the word "olcum" (measurement), the cue of the correct area; so the first two extension calls say `abonelik` (billing), and the correct area `sayac` (meter) appears only on the third. A single-branch search would end here and, producing `abonelik kayit` at the second level, would go deeper on a path with no counterpart in the ticket. When the correct branch is kept, the second level gives `sayac endeks`, because the symptom cue is strong. **This is what the tree promises: a wrong first step taken with weak evidence can be taken back, as long as it is not the only step.** ## Branch, Depth and Number of Calls The second block builds the tree and puts six arrangements side by side: branching is raised to one, two, three and four, then branch is held at three and depth is lowered to one and two. The single call and the previous lesson's five-sample self-consistency also enter the table; the second run of every row is taken by changing the seed. ```python SPLIT = {1: (3,), 2: (2, 1), 3: (1, 1, 1)} # how many steps the path is split into def tree(x, branch, keep, depth, seed): paths = [()] for k in SPLIT[depth]: candidates = [] for p in paths: # generation: extend each branch `branch` times se = extend_paths(p, k) for j in range(min(branch, len(se))): s = call(build_prompt("Cozum yolunu bir adim uzat .", se, x), se, seed + j) if s["response"] is not None and s["response"] not in candidates: candidates.append(s["response"]) if not candidates: candidates = extend_paths(paths[0], k)[:1] if len(candidates) <= keep: paths = candidates # nothing to choose, no call is spent else: paths = [] for j in range(keep): # selection: filter the branches to keep s = call(build_prompt("En umut verici yollari sec .", candidates, x), candidates, seed + j) if s["response"] is not None and s["response"] not in paths: paths.append(s["response"]) paths = paths or candidates[:keep] s = call(build_prompt("Kalan yollardan birini kod olarak yaz .", paths, x), paths, seed) return s["response"] or paths[0] def single(x, k, seed): # k = 1 single call, k > 1 self-consistency counts = {} for j in range(k): s = call(build_prompt("Talebe bir ariza kodu ata .", ALL_CODES, x), ALL_CODES, seed + j) if s["response"] is not None: counts[s["response"]] = counts.get(s["response"], 0) + 1 return max(sorted(counts, key=join_path), key=lambda a: counts[a]) if counts else None def measure(f, seed): COUNTER[:] = [0, 0, 0] correct = 0 for x in TICKETS: correct += f(x["text"], seed) == x["code"] return {"accuracy": correct / len(TICKETS), "calls": COUNTER[0], "tok": COUNTER[1], "failed": COUNTER[2]} ARRANGEMENTS = [("single call", lambda x, t: single(x, 1, t)), ("self-consistency 5 samples", lambda x, t: single(x, 5, t)), ("tree branch 1 depth 3", lambda x, t: tree(x, 1, 1, 3, t)), ("tree branch 2 depth 3", lambda x, t: tree(x, 2, 2, 3, t)), ("tree branch 3 depth 3", lambda x, t: tree(x, 3, 3, 3, t)), ("tree branch 4 depth 3", lambda x, t: tree(x, 4, 4, 3, t)), ("tree branch 3 depth 1", lambda x, t: tree(x, 3, 3, 1, t)), ("tree branch 3 depth 2", lambda x, t: tree(x, 3, 3, 2, t))] print(f"{'prompt arrangement':<28}{'accuracy':>8}{'run2':>8}{'diff':>8}{'calls':>7}" f"{'tokens':>10}{'failed':>10}") for name, f in ARRANGEMENTS: A, B = measure(f, SEED), measure(f, SEED + 1) print(f"{name:<28}{A['accuracy']:>8.4f}{B['accuracy']:>8.4f}" f"{B['accuracy'] - A['accuracy']:>+8.4f}{A['calls']:>7d}{A['tok']:>10d}" f"{A['failed']:>10d}") ``` ``` prompt arrangement accuracy run2 diff calls tokens failed single call 0.4792 0.5208 +0.0417 48 11617 1 self-consistency 5 samples 0.7292 0.7708 +0.0417 240 58074 6 tree branch 1 depth 3 0.0833 0.2708 +0.1875 192 9776 5 tree branch 2 depth 3 0.4167 0.5417 +0.1250 506 26651 13 tree branch 3 depth 3 0.6250 0.5833 -0.0417 795 43182 21 tree branch 4 depth 3 0.6042 0.5833 -0.0208 1086 59835 29 tree branch 3 depth 1 0.6250 0.6250 +0.0000 192 37617 5 tree branch 3 depth 2 0.7292 0.7500 +0.0208 421 30650 11 ``` The third row is the harshest number of this lesson. Splitting the solution into three steps but **never branching** drops accuracy from 0.4792 to **0.0833**, and it does this with four times the calls. The reason was seen in the first block: a search that does not branch takes the first step with the weakest evidence and can never come back. In the single-prompt arrangement the three components were evaluated **together at the same score**, so the strong symptom cue could carry the weak area cue; splitting cut that carrying. **Splitting into steps is not an improvement by itself; its cost is certain, its gain is negative.** Branching takes this back. At branch two it is 0.4167, at branch three **0.6250**. Where the gain stops is visible at the fourth step: when branching is raised to four, accuracy **slips by 0.0208**, while the number of calls goes from 795 to **1086**, tokens from 43182 to **59835**, failed calls from 21 to **29**. The difference between two runs of the same arrangement is 0.0417 at branch three. Since the difference that the move from branch three to four contributes is smaller than this number, it **counts as unmeasured**: two hundred ninety-one calls and more than sixteen thousand tokens were spent on a change that cannot be shown. The last two rows are the depth axis and give the opposite result. When depth is lowered from three to two with the same number of branches, accuracy rises from 0.6250 to **0.7292** and calls fall from 795 to 421: when area and symptom are chosen together, the strong symptom cue can again carry the weak area cue. When depth falls to one, accuracy stays at 0.6250 and calls drop to **192**, but because the prompts carry all thirty-two options at once, tokens rise from 30650 to 37617. **The ranking by calls is not the ranking by tokens.** The second row of the table closes the lesson. The previous lesson's five-sample self-consistency gives **0.7292** — the same number as the best tree arrangement — and does it with **240 calls** instead of 421. In tokens the situation reverses: 58074 against 30650. The choice between the two techniques is not a ranking of superiority but **a choice of unit**; the only measurable thing the tree contributes on this task is that it reaches the same accuracy with fewer tokens. **A prompt changed without measuring is not an improvement but a guess**, and in this table half of the changed prompts were not an improvement. ## Summary - The tree of thoughts is not a single prompt but **an arrangement of prompts**: the solution is split into steps, several extensions are asked for at every step, a part of the candidates is kept. Extension and selection calls are counted together. - Splitting into steps without branching does harm: accuracy falls from 0.4792 to **0.0833**, calls go from 48 to 192. When the wrongly taken first step is the only step, it cannot be taken back. - Branching gains but saturates: from branch 1 to 3 accuracy rises **from 0.0833 to 0.6250**, at branch 4 it **slips by 0.0208**. Calls go from 192 to 1086, tokens from 9776 to 59835. - The difference of the move from branch three to four is **smaller than the 0.0417 difference** between two runs of the same arrangement; it counts as unmeasured and cannot be written as a gain. - Depth works in the opposite direction: using 2 instead of 3 raises accuracy to **0.7292** and lowers calls to 421. Self-consistency gives the same accuracy with **240 calls** and **58074 tokens**; the tree's 30650 tokens are cheap, its 421 calls expensive. ## Next Step These three techniques all worked in the same direction: the model was asked for **more steps**. Chain of thought had the steps written inside a single response, self-consistency had the same steps produced and voted on many times, the tree of thoughts put a selection rule between the steps. In all three the steps are **at the same level**: all of them move toward the detail of the solution. What went wrong in this lesson, though, was the detail itself; a misleading word spoiled the first step and all the later steps were built on that spoiled step. **Going up** before going down into the detail was never tried. Asking, before assigning a code to a ticket, which general rule that ticket falls under was an option at hand. The next lesson measures it: the prompt is split into two stages, the principle is asked first and then the solution, and how much the two-stage version moves accuracy compared with the one-stage version is printed side by side with how many tokens it adds.