Tree of Thoughts

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.

# 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.

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.