CoT, ToT & Self-Consistency Prompting

Picture a release candidate with passing tests, a clear security scan, and an approved review. Policy allows an automatic merge only when all three facts hold. An assistant writes a convincing explanation but checks only the tests. What would reveal that omission before anything merges?

The last chapter used a compressed embedding index to put the right policy clause in context, including an auto-merge rule. Retrieval isn't the end: an assistant can still skip a condition, mishandle a check, or commit too early to one plan. The question isn't whether a model can produce a longer explanation; it's how much extra test-time compute buys a better decision under token, latency, and safety budgets. Start with one prompt-elicited chain of thought (CoT), compare several candidates with self-consistency, and move to an external Tree of Thoughts (ToT) search only when early choices can dead-end.

Start with a failure you can audit

Put those facts on one row: unit tests pass, the security scan is clear, and a reviewer has approved the diff. The policy permits auto-merge only when every field is true. A model can still skip a field or suggest a force-merge.

A useful outward artifact is a short decision record containing those facts, the checks applied, and the proposed action. It's smaller than an open-ended rationale and easy to compare against deterministic policy logic. It isn't raw chain of thought. It's a task-specific output contract that the application can validate.

All Python examples below run locally without model calls. Their candidate responses and evaluation numbers are invented test fixtures. They demonstrate controller behavior, not the accuracy of any prompting technique.

from dataclasses import dataclass

@dataclass(frozen=True)
class ReleaseCase:
    tests_passed: bool
    security_scan_clear: bool
    reviewer_approved: bool

def decision_record(case: ReleaseCase) -> dict[str, object]:
    checks = {
        "tests_passed": case.tests_passed,
        "security_scan_clear": case.security_scan_clear,
        "reviewer_approved": case.reviewer_approved,
    }
    if any(type(value) is not bool for value in checks.values()):
        raise ValueError("policy inputs must be trusted booleans")
    action = "merge_release" if all(checks.values()) else "manual_review"
    return {"checks": checks, "final_action": action}

record = decision_record(
    ReleaseCase(tests_passed=True, security_scan_clear=True, reviewer_approved=True)
)
for name, passed in record["checks"].items():
    print(f"{name}: {passed}")
print(f"final_action: {record['final_action']}")

tests_passed: True
security_scan_clear: True
reviewer_approved: True
final_action: merge_release

This code isn't an LLM. It's the oracle that your prompt variants must match. Define the output contract and scorer before increasing model compute.

Structured machine state belongs in code. Sampling five rationales over three known flags adds cost without new evidence. A model may help interpret unstructured evidence such as diff text or review comments, but its proposed checks still need validation against trusted sources. We use the small release policy because its correct answer is unambiguous, not because it needs a model.

If a required fact isn't in the prompt at all, a longer rationale can't invent it. The missing value has to come from the source system. That boundary leads to the typed tool request in the next lesson.

Chain-of-thought: give an intermediate result somewhere to go

A conventional decoder-only transformer applies its fixed stack of layers to predict the next token. A direct answer can still contain several generated tokens. A native reasoning model can also do substantial hidden reasoning before returning a short public answer, so answer length alone doesn't measure its inference work.

Intermediate tokens add sequential computation and new context for later predictions. Imagine calculating a subtotal before applying tax: writing the subtotal lets the next step use that value explicitly. With a KV cache, the decoder reuses earlier keys and values instead of recomputing the whole prefix. New tokens still require work through the model's layers, and attention costs depend on the retained context. There is no exact, context-independent K × fixed FLOPs cost formula for a complete response.

The generated text and its cached representations can act as a computational scratchpad. That scratchpad stores a proposed subtotal, not a verified one. An incorrect intermediate value can influence the answer; a later step can also correct it. Validation needs a separate check.

Formal expressivity results support the importance of intermediate computation, with qualifications. Merrill and Sabharwal study specific transformer models under precision and normalization assumptions. Their polynomial-step construction captures polynomial-time computation; some claimed separations from direct prediction rely on unproved complexity-class separations.^{[1]Reference 1The Expressive Power of Transformers with Chain of Thoughthttps://arxiv.org/abs/2310.07923} This doesn't establish that a trained model will discover the required algorithm or that longer CoT makes arbitrary constraint satisfaction tractable.

Wei et al. established few-shot CoT by placing worked intermediate steps in prompt exemplars. On GSM8K (a grade-school math benchmark), PaLM 540B rose from 17.9% with standard direct prompting to 56.9% with eight CoT exemplars.^{[2]Reference 2Chain-of-Thought Prompting Elicits Reasoning in Large Language Models.https://arxiv.org/abs/2201.11903} Kojima et al. showed that the zero-shot trigger "Let's think step by step" could elicit multi-step reasoning without exemplars.^{[3]Reference 3Large Language Models are Zero-Shot Reasoners.https://arxiv.org/abs/2205.11916}

Those papers describe tools to evaluate, not a universal law. On your endpoint and task, a visible scratchpad might help, do nothing, or add latency. Meincke et al.'s June 2025 GPQA Diamond study compared prompts on eight models, with 25 trials per question and condition. The study found modest average improvements for non-reasoning models and marginal benefits for reasoning models at increased time cost.^{[4]Reference 4Prompting Science Report 2: The Decreasing Value of Chain of Thought in Promptinghttps://arxiv.org/abs/2506.07142} Those historical results aren't measurements of current endpoints.

Zheng et al. documented the "curse of CoT" on nine pattern-based in-context-learning datasets across 16 models, where CoT variants underperformed direct answering.^{[5]Reference 5The Curse of CoT: On the Limitations of Chain-of-Thought in In-Context Learning.https://arxiv.org/abs/2504.05081} That finding doesn't make direct answers universally better either. Compare both on representative held-out cases.

When a task has sequential sub-dependencies, least-to-most prompting first decomposes the problem into sub-questions, then answers them in order, passing earlier answers into later prompts.^{[6]Reference 6Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelshttps://arxiv.org/abs/2205.10625} For a release summary, one stage might identify changed components and another map those components to required checks. This avoids maintaining alternative branches, but adds sequential calls and can propagate an incorrect intermediate answer.

Keep four reasoning artifacts separate

The word reasoning now covers several different artifacts. Mixing them creates false audit claims and brittle integrations, so name the artifact before deciding what it proves.

Provider disclosure rules and API surfaces differ. Checked October 10, 2026: OpenAI's API documentation says raw reasoning tokens aren't exposed, although supported models can return an opt-in reasoning summary. Internal tokens occupy context space and are billed as output; an output limit can be reached before any visible answer appears.^{[7]Reference 7Reasoning modelshttps://developers.openai.com/api/docs/guides/reasoning}

Anthropic now documents adaptive thinking separately from legacy manual budget_tokens. Its configuration table marks manual mode deprecated on Opus and Sonnet 4.6; the Opus 4.7 and 4.8 rows reject it. Check the exact model's row rather than inferring support from its version number.^{[8]Reference 8Troubleshooting thinkinghttps://platform.claude.com/docs/en/build-with-claude/thinking-troubleshooting} In adaptive mode, thinking.type selects the mode and effort controls work across the response. Returned thinking under display: "summarized" is a summary, and the standard display settings don't expose raw CoT.^{[9]Reference 9Thinkinghttps://platform.claude.com/docs/en/build-with-claude/thinking}

Recheck provider documentation when you integrate. Don't write controller logic that assumes every model returns a visible scratchpad or that one thinking API works across Claude generations.

This distinction changes the build-versus-buy decision. An external CoT, voting, or tree-search controller gives you explicit sample and search state, but generated rationales still aren't guaranteed to be faithful.

A native reasoning model owns more of the internal inference process, while its controls, visibility, and accounting follow the provider contract. Put both behind the same task-level evaluator and compare outcomes, latency, token use, and parse failures.

Ask for reviewable task artifacts at the workflow boundary rather than text that claims to reveal private internal reasoning:

Use only the supplied release facts and policy rules.
Return:
1. required_checks: each policy predicate with pass/fail
2. final_action: one allowed action enum
3. operator_message: one sentence

Facts:
- tests_passed: true
- security_scan_clear: true
- reviewer_approved: true

Policy:
- merge_release is allowed only when tests pass,
  the security scan is clear, and review approval exists.
- Otherwise return manual_review. These are the only allowed actions.

The required checks make a missed predicate observable. They still aren't proof of faithful hidden cognition. Turpin et al. showed that CoT explanations can rationalize outputs influenced by hidden biasing features without mentioning those features.^{[10]Reference 10Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Promptinghttps://arxiv.org/abs/2305.04388} Log inputs, actions, validations, and outcomes; don't treat eloquent reasoning text or a provider summary as an audit guarantee.

from dataclasses import dataclass

@dataclass(frozen=True)
class Candidate:
    name: str
    checks: dict[str, bool]
    final_action: str

expected_checks = {
    "tests_passed": True,
    "security_scan_clear": True,
    "reviewer_approved": True,
}
expected_action = "merge_release"
candidates = [
    Candidate("missing_check", {"tests_passed": True}, "manual_review"),
    Candidate("wrong_value", {**expected_checks, "security_scan_clear": False}, "merge_release"),
    Candidate("complete_record", expected_checks, "merge_release"),
]

for candidate in candidates:
    coverage = len(candidate.checks.keys() & expected_checks.keys()) / len(expected_checks)
    checks_ok = (candidate.checks.keys() == expected_checks.keys()
                 and all(type(value) is bool and value is expected_checks[name]
                         for name, value in candidate.checks.items()))
    action_ok = candidate.final_action == expected_action
    print(f"{candidate.name}: coverage={coverage:.0%}, checks_ok={checks_ok}, action_ok={action_ok}")

missing_check: coverage=33%, checks_ok=False, action_ok=False
wrong_value: coverage=100%, checks_ok=False, action_ok=True
complete_record: coverage=100%, checks_ok=True, action_ok=True

The wrong-value fixture has every field and the expected action, yet misstates the security scan. Field coverage alone would miss that defect. These hand-written records test the scorer; comparing them says nothing about whether direct or CoT prompting performs better.

Zero-shot or few-shot?

Zero-shot CoT asks for intermediate steps without supplying a worked example. Few-shot CoT demonstrates solved examples and their steps. These examples can steer both step granularity and output shape, but they don't enforce either. A schema example alone is few-shot formatting, not necessarily CoT. Neither approach guarantees valid output. Native structured output can enforce supported schema constraints, but can't establish that the field values are true.

For a fair comparison, keep the policy, target facts, and requested output identical; vary only the worked example. This prompt requests a concise policy explanation and decision record, not disclosure of private internal reasoning.

example = """Example:
facts: tests_passed=true, security_scan_clear=false, reviewer_approved=true
policy_check: the scan failed, so the all-three condition is false.
required_checks: tests_passed=true, security_scan_clear=false, reviewer_approved=true
final_action: manual_review"""

policy = "merge_release requires all three checks true; otherwise manual_review."
instruction = "Give a short policy_check, required_checks, and final_action."
case = "facts: tests_passed=true, security_scan_clear=true, reviewer_approved=true"
zero_shot = f"Policy: {policy}\n{instruction}\n{case}"
few_shot = f"Policy: {policy}\n{instruction}\n{example}\n\nNow evaluate:\n{case}"

print(few_shot)

Policy: merge_release requires all three checks true; otherwise manual_review.
Give a short policy_check, required_checks, and final_action.
Example:
facts: tests_passed=true, security_scan_clear=false, reviewer_approved=true
policy_check: the scan failed, so the all-three condition is false.
required_checks: tests_passed=true, security_scan_clear=false, reviewer_approved=true
final_action: manual_review

Now evaluate:
facts: tests_passed=true, security_scan_clear=true, reviewer_approved=true

Stable formatting solves parsing, not sampling variance. A well-shaped candidate can still choose the wrong action.

Self-consistency: sample answers, then vote

One greedy candidate can commit to an incorrect intermediate result and carry it forward. It can also correct itself; a slip doesn't permanently lock every later token into failure. Self-consistency samples several solution paths and chooses the most frequent extracted answer.^{[11]Reference 11Self-Consistency Improves Chain of Thought Reasoning in Language Models.https://arxiv.org/abs/2203.11171}

The useful hypothesis is that different valid paths converge on the same answer while errors spread across alternatives. That hypothesis can fail when a common misconception dominates. Formally, an answer distribution can marginalize over reasoning trajectories $r$:

$P(y \mid x) = \sum_{r} P(y, r \mid x) = \sum_{r} P(y \mid r, x) P(r \mid x)$

Enumerating the full sum is impractical. Self-consistency instead samples trajectories and selects the most frequent extracted answer: a plurality, which needn't exceed half the samples. Temperature and truncation change the sampled distribution, so these counts don't exactly integrate the unmodified model distribution. Independently drawn samples can still repeat the same systematic mistake. The vote operates on answers, not on whose rationale sounds best.

Suppose five outputs contain three variants of merge_release, one manual_review, and one unknown action. Canonicalizing the spellings gives the leading action three votes. Our controller uses all five attempts in the denominator: 3 / 5 = 0.60. A threshold of 0.60 accepts that candidate; a threshold of 0.80 abstains. This conservative rejection policy is our application choice, not a requirement of the original self-consistency method.

Let $y_i$ be the final text from sample $i$, and let $c(y_i)$ map that text to an allowed action or reject it as invalid. With $N$ total samples, the winning action and its share are:

$\hat{a} = \arg\max_a \sum_{i=1}^{N} \mathbf{1}[c(y_i)=a], \qquad s = \frac{1}{N}\sum_{i=1}^{N}\mathbf{1}[c(y_i)=\hat{a}]$

For $N>0$, the denominator remains $N$, even when some outputs fail to parse. The indicator is 1 for a vote matching the action and 0 otherwise. Emit $\hat{a}$ only when the winner is unique and $s$ meets a configured threshold $\tau$; otherwise abstain. An empty batch also abstains.

To obtain varied candidates, use supported stochastic decoding controls, often a nonzero temperature. Some reasoning endpoints restrict sampling parameters; don't assume a temperature override is accepted. The earlier Decoding Algorithms lesson explains that control. Keep supported settings fixed in your experiment and log them with the sample count. Duplicating one response doesn't create another independent sample, and low temperature alone isn't a universal reproducibility guarantee.

In the paper's PaLM-540B setting, 40 independently sampled outputs per run raised GSM8K accuracy from 56.5% with greedy CoT to 74.4% with self-consistency, a 17.9 percentage-point gain.^{[11]Reference 11Self-Consistency Improves Chain of Thought Reasoning in Language Models.https://arxiv.org/abs/2203.11171} The baseline differs slightly from Wei et al.'s earlier 56.9% because this is a separate experimental setup. That result belongs to its model, prompts, sampling setup, and benchmark. Five samples here aren't expected to reproduce it.

Wang et al. also observed that the share of samples agreeing with the aggregated answer correlated with GSM8K accuracy. That's a research observation, not a calibrated confidence score. Treat agreement as a vote statistic you threshold, then still run ordinary policy checks.

Normalize before counting

For this toy controller, each input is just a final-action string. Map an explicit allowlist of harmless variants to one action and reject everything else. For structured responses, schema-check first and extract final_action; don't search a whole rationale for an action substring. Keep aliases specific to the same policy meaning.

from collections import Counter

ALIASES = {
    "merge release": "merge_release",
    "merge_release": "merge_release",
    "auto merge approved change": "merge_release",
    "manual review": "manual_review",
    "manual_review": "manual_review",
}

def canonicalize(text: str) -> str | None:
    normalized = " ".join(text.casefold().replace("-", " ").split())
    return ALIASES.get(normalized)

samples = [
    "Merge release",
    "merge_release",
    "Auto merge approved change",
    "manual review",
    "force merge immediately",
]
votes = Counter(action for text in samples if (action := canonicalize(text)))
winner = votes.most_common(1)[0][0] if votes else None

print(f"accepted_samples: {sum(votes.values())}/{len(samples)}")
print(f"votes: {dict(votes)}")
print(f"winner: {winner}")

accepted_samples: 4/5
votes: {'merge_release': 3, 'manual_review': 1}
winner: merge_release

A leading answer can still lack support

A 2 to 2 tie, zero accepted outputs, or a narrow plurality with many rejected outputs shouldn't silently become an automated action. Add an abstention rule.

Our winning share uses every sampled output, including parse failures. Return abstain separately from manual_review: the first means sampling didn't select an answer; the second is a substantive policy recommendation. The application may route either to a human, but evaluation mustn't count abstention as a correct policy answer.

from collections import Counter
import math

def decide(samples: list[str], minimum_share: float = 0.6) -> str:
    if type(minimum_share) not in (int, float) or not 0.5 < minimum_share <= 1 or not math.isfinite(minimum_share):
        raise ValueError("minimum_share must be finite and in (0.5, 1]")
    if not isinstance(samples, list) or any(not isinstance(text, str) for text in samples):
        raise ValueError("samples must be a list of strings")
    counts = Counter(action for text in samples if (action := canonicalize(text)))
    if not counts:
        return "abstain"
    ranked = counts.most_common(2)
    winner, count = ranked[0]
    share = count / len(samples)
    tied = len(ranked) > 1 and ranked[0][1] == ranked[1][1]
    if tied or share < minimum_share:
        return "abstain"
    return winner

strong = ["Merge release", "merge_release", "Auto merge approved change", "manual_review", "force"]
split = ["merge_release", "merge_release", "manual_review", "manual_review"]
mostly_rejected = ["merge_release", "merge_release", "force", "hold", "unknown"]

print(f"strong_vote: {decide(strong)}")
print(f"higher_threshold: {decide(strong, minimum_share=0.8)}")
print(f"split_vote: {decide(split)}")
print(f"mostly_rejected_vote: {decide(mostly_rejected)}")
print(f"empty_batch: {decide([])}")

strong_vote: merge_release
higher_threshold: abstain
split_vote: abstain
mostly_rejected_vote: abstain
empty_batch: abstain

Measure gains against call cost

Before collecting model outputs, test the controller on a small fixture set. Each invented case has five final-action strings. Two additions matter: every sample can repeat the same wrong answer, and weak support can cause abstention even when the first sample was correct. The same decide() function scores every case.

fixtures = {
    "approved_clean_release": {
        "expected": "merge_release",
        "samples": ["manual_review", "merge_release", "merge_release", "merge_release", "force"],
    },
    "scan_failed": {
        "expected": "manual_review",
        "samples": ["manual_review", "manual_review", "force", "manual_review", "hold"],
    },
    "review_missing": {
        "expected": "manual_review",
        "samples": ["merge_release", "manual_review", "manual_review", "manual_review", "merge_release"],
    },
    "shared_wrong_assumption": {
        "expected": "manual_review",
        "samples": ["merge_release"] * 5,
    },
    "weak_support": {
        "expected": "manual_review",
        "samples": ["manual_review", "force", "hold", "merge_release", "unknown"],
    },
}

single_correct = 0
vote_correct = 0
abstentions = 0
for name, item in fixtures.items():
    winner = decide(item["samples"])
    single_correct += canonicalize(item["samples"][0]) == item["expected"]
    vote_correct += winner == item["expected"]
    abstentions += winner == "abstain"
    print(f"{name}: {winner}")

total = len(fixtures)
print(f"single_trace_accuracy: {single_correct / total:.0%}")
print(f"vote_5_accuracy: {vote_correct / total:.0%}")
print(f"abstentions: {abstentions}/{total}")
print(f"required_samples_if_collected: single={total}, vote_5={total * 5}")

approved_clean_release: merge_release
scan_failed: manual_review
review_missing: manual_review
shared_wrong_assumption: merge_release
weak_support: abstain
single_trace_accuracy: 40%
vote_5_accuracy: 60%
abstentions: 1/5
required_samples_if_collected: single=5, vote_5=25

The apparent accuracy gain is built into these invented responses, not measured from a model. The unanimously wrong case also shows why the vote can't authorize a merge: trusted policy checks must still reject it. For a real comparison, collect samples on the same held-out cases, count abstentions separately, repeat stochastic trials, and measure token usage and latency. Multiple samples can run concurrently, but they still consume generation work.

Tree-of-thoughts: search when branches can dead-end

Voting helps when independent paths tend to converge on the same short answer. It doesn't deliberately revisit an earlier choice. Tree-of-Thoughts (ToT) represents partial solutions as search states, then generates alternatives, evaluates those states, and preserves only branches worth extending.^{[12]Reference 12Tree of Thoughts: Deliberate Problem Solving with Large Language Models.https://arxiv.org/abs/2305.10601}

Yao et al. evaluated ToT on tasks built for planning and search. A beam width is the number of partial states retained after each scoring step. On Game of 24 with GPT-4, ToT with beam width 5 solved 74% of tasks, while CoT solved 4.0% and CoT self-consistency with 100 samples solved 9.0%.^{[12]Reference 12Tree of Thoughts: Deliberate Problem Solving with Large Language Models.https://arxiv.org/abs/2305.10601} This particular search setup outperformed answer voting. Those aggregate rates don't establish that every sampled path encountered the same trap, and they don't predict current-model performance.

The narrower conclusion isn't "use trees everywhere." When a problem has verifiable partial states and meaningful backtracking, search can recover from a bad early move.

The ToT framework structures problem-solving into four explicit steps:

1. Thought decomposition: breaking the problem into discrete intermediate states $s$ (such as an arithmetic move, a plan paragraph, or a code function stub).
2. Thought generation: proposing $k$ candidate next thoughts from state $s$.
3. State evaluation: querying the model or a programmatic validator to score each candidate state (such as classifying viability into sure, maybe, or impossible).
4. Search controller: maintaining the active frontier in an external orchestration loop using Breadth-First Search (BFS) with beam pruning or Depth-First Search (DFS) with backtracking.

Beyond tree branching, Graph-of-Thoughts (GoT) represents generated thoughts and their dependencies as a graph rather than requiring every state to have one parent.^{[13]Reference 13Graph of Thoughts: Solving Elaborate Problems with Large Language Modelshttps://arxiv.org/abs/2308.09687} Two useful operations are:

1. Thought aggregation: combining outputs from separate independent paths (such as joining an API security analysis from one branch with performance profiling from another).
2. Thought refinement: generating a new candidate from an earlier candidate and feedback. A critique doesn't guarantee that the revision improves.

Aggregating two generated claims doesn't make either claim reliable; the combined result still needs evaluation.

Serving costs depend on how the controller expands its frontier. Concurrent branches require more active sequence state; shared-prefix caching can reduce repeated prefill work where supported, but changed history still needs computation. Sequentially dependent calls add round-trips and latency. Bound expansion, measure endpoint behavior, and use the product's latency gate to decide whether a search can run interactively or needs a background workflow. Neither a particular caching algorithm nor background execution is a requirement of ToT.

Use a problem that actually needs branching

The release conjunction doesn't need a tree, and missing scan results can't be filled in by exploring imagined facts. Switch to Game of 24 to isolate what branching contributes: combine 4, 5, 6, and 7 with arithmetic, using each input exactly once, to reach 24.

One successful path is 6 - 4 = 2, then 5 + 7 = 12, then 2 * 12 = 24. A state contains the remaining values and the expressions that produced them. Each move consumes two values and replaces them with one result. Reaching 24 early isn't enough if other inputs remain unused.

In ToT, a model proposes and scores partial solutions while an external controller maintains the frontier. The next solver replaces both model roles with exhaustive arithmetic enumeration. It teaches state expansion and gives us a correctness oracle; it isn't an LLM or a reproduction of the ToT benchmark.

from collections import deque
from fractions import Fraction
from itertools import combinations

def combine(left: tuple[Fraction, str], right: tuple[Fraction, str]) -> list[tuple[Fraction, str]]:
    a, a_expr = left
    b, b_expr = right
    outcomes = [
        (a + b, f"({a_expr} + {b_expr})"),
        (a - b, f"({a_expr} - {b_expr})"),
        (b - a, f"({b_expr} - {a_expr})"),
        (a * b, f"({a_expr} * {b_expr})"),
    ]
    if b:
        outcomes.append((a / b, f"({a_expr} / {b_expr})"))
    if a:
        outcomes.append((b / a, f"({b_expr} / {a_expr})"))
    return outcomes

def solve_24(numbers: list[int], max_states: int = 10000) -> dict:
    if not isinstance(numbers, list) or not 1 <= len(numbers) <= 4 or any(type(number) is not int for number in numbers):
        raise ValueError("supply one to four integer values")
    if type(max_states) is not int or max_states < 1:
        raise ValueError("max_states must be a positive integer")
    frontier = deque([[(Fraction(number), str(number)) for number in numbers]])
    visited = set()
    examined = 0
    while frontier:
        state = frontier.popleft()
        key = tuple(sorted(value for value, expression in state))
        if key in visited:
            continue
        if examined >= max_states:
            return {"status": "budget_exhausted", "expression": None}
        visited.add(key)
        examined += 1
        if len(state) == 1 and state[0][0] == 24:
            return {"status": "solved", "expression": state[0][1]}
        for i, j in combinations(range(len(state)), 2):
            remainder = [item for k, item in enumerate(state) if k not in (i, j)]
            frontier.extend([remainder + [result] for result in combine(state[i], state[j])])
    return {"status": "no_solution", "expression": None}

solution = solve_24([4, 5, 6, 7])
print(f"status: {solution['status']}")
print(f"expression: {solution['expression']}")
print(f"one_state_budget: {solve_24([4, 5, 6, 7], max_states=1)['status']}")

status: solved
expression: ((6 - 4) * (5 + 7))
one_state_budget: budget_exhausted

Fraction avoids floating-point rounding in the arithmetic check. States with the same remaining value multiset have the same future arithmetic possibilities, so the solver keeps one representative. The budget counts distinct states, including the initial state; duplicates don't consume it. Exhausting the queue proves no solution under these operations; hitting max_states with an unexamined distinct state only means the search stopped before answering.

Enumeration constructs legal moves by design. If a model proposes the next state instead, don't trust its remaining-number list. Starting with 4, 5, 6, 7, the claim 6 * 4 = 24, remaining=[24] discards 5 and 7. A goal check alone would accept that fabricated solution. Recompute the transition from the host's current state before applying a heuristic score:

def legal_transition(current, left, right, operator, claimed_remaining) -> bool:
    remaining = [Fraction(value) for value in current]
    a, b = Fraction(left), Fraction(right)
    try:
        remaining.remove(a)
        remaining.remove(b)  # Each operand consumes a separate occurrence.
    except ValueError:
        return False
    if operator == "+":
        result = a + b
    elif operator == "-":
        result = a - b
    elif operator == "*":
        result = a * b
    elif operator == "/" and b != 0:
        result = a / b
    else:
        return False
    return sorted(remaining + [result]) == sorted(Fraction(v) for v in claimed_remaining)

start = [4, 5, 6, 7]
print("dropped inputs legal:", legal_transition(start, 6, 4, "*", [24]))
print("dead-end move legal:", legal_transition(start, 6, 4, "*", [24, 5, 7]))
print("valid-branch move legal:", legal_transition(start, 5, 7, "+", [12, 4, 6]))
print("reused single 4 legal:", legal_transition(start, 4, 4, "+", [8, 5, 6, 7]))

dropped inputs legal: False
dead-end move legal: True
valid-branch move legal: True
reused single 4 legal: False

The helper assumes parsed numeric inputs and an allowlisted operator; it never executes a model-written expression. It checks one transition's arithmetic and conservation, not whether a solution exists below it. The legal [24, 5, 7] state can still be a dead end. A full controller must retain the admitted transition lineage from the original inputs; an isolated [24] claim isn't enough to establish a solution.

Pruning is a source of failure

An LLM evaluator isn't an arithmetic oracle. If it scores an apparently simple but dead branch above a non-obvious solvable branch, an aggressive beam can remove the answer before expansion.

branches = [
    {"move": "6 * 4 = 24 first", "remaining": [24, 5, 7], "weak_score": 0.95},
    {"move": "5 + 7 = 12 first", "remaining": [12, 4, 6], "weak_score": 0.40},
    {"move": "7 - 5 = 2 first", "remaining": [2, 4, 6], "weak_score": 0.35},
]
for branch in branches:
    result = solve_24(branch["remaining"])
    if result["status"] == "budget_exhausted":
        raise RuntimeError("oracle budget too small")
    branch["solvable"] = result["status"] == "solved"
    branch["exact_score"] = float(branch["solvable"])

def keep_one(score_name: str) -> dict[str, object]:
    return max(branches, key=lambda branch: branch[score_name])

weak_choice = keep_one("weak_score")
exact_choice = keep_one("exact_score")
print(f"weak_evaluator_keeps_solution: {weak_choice['solvable']}")
print(f"exact_evaluator_keeps_solution: {exact_choice['solvable']}")
print(f"risk: beam_width_1 can prune the valid branch")

weak_evaluator_keeps_solution: False
exact_evaluator_keeps_solution: True
risk: beam_width_1 can prune the valid branch

The weak scores are invented. The exact scores are computed by solving each remaining arithmetic problem, which can be expensive. Checking that one move is legal is cheaper than proving that a complete solution exists below it. Real search tasks need that distinction when choosing validators or a separately evaluated scorer.

The production implications are concrete. Keep ToT for tasks with real branch structure, not ordinary classification. Prefer deterministic validators when a partial state can be checked in code. Measure solver recall at each beam width alongside final successes, then cap expansions and latency before an open-ended search reaches users.

Search can revisit a bad choice only if the controller retained an alternative or supports backtracking. A pruned beam doesn't recover a discarded branch automatically. Expansion increases compute; its latency impact also depends on concurrency and which calls depend on earlier results.

Native reasoning models and reinforcement learning

The original few-shot CoT work used exemplars without changing model weights. Reasoning-oriented post-training can instead teach intermediate problem-solving behavior. OpenAI's 2024 o1 announcement describes reinforcement learning, without publishing a complete training recipe.^{[14]Reference 14Learning to reason with LLMshttps://openai.com/index/learning-to-reason-with-llms/} DeepSeek's 2025 R1 report gives a concrete rule-reward example; its R1-Zero variant starts RL without a preceding SFT stage, while R1 combines SFT and RL stages.^{[15]Reference 15DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learninghttps://arxiv.org/abs/2501.12948} These are historical training examples, not a list of current recommended endpoints.

The shift to verifiable rewards

SFT can teach imitation of human-written, model-generated, or distilled solutions. Its quality depends on its data and objective; it doesn't impose a proved ceiling at human reasoning ability. RLVR adds an outcome-based training signal where a verifier can judge answers or executions. Examples include checking a mathematical final answer, executing code tests, or checking a formal proof.

A verifier is only as good as what it checks. Passing a finite test suite doesn't prove program correctness, and matching a boxed answer doesn't validate every step in a derivation. Deterministic rewards can still be gamed. Anthropic's 2025 coding-RL study deliberately exposed vulnerable training environments and observed models learning to exploit them.^{[16]Reference 16From shortcuts to sabotage: natural emergent misalignment from reward hackinghttps://www.anthropic.com/research/emergent-misalignment-reward-hacking} RLVR doesn't automatically eliminate sycophancy or other unwanted behavior.

Algorithms such as GRPO optimize sampled outputs against their reward signal. Rewarding correct outcomes can encourage intermediate computation when it helps. It doesn't establish that every intermediate claim is true, that longer outputs always earn more reward, or that trained reasoning is always hidden.

Emergent backtracking and test-time scaling

DeepSeek reports R1-Zero developing behaviors such as reflection and exploring alternatives. Those observations motivate testing for:

• Self-correction: identifying an arithmetic slip or policy contradiction and writing corrective tokens ("Wait, that contradicts check 2... let me recalculate").
• Emergent backtracking: recognizing an unproductive branch and shifting to an alternate algebraic substitution or proof approach.
• Sanity checking: re-verifying edge cases before generating the final answer.

Snell et al. studied iterative revisions and verifier-guided search using capability-fine-tuned PaLM 2 models on MATH. Difficulty-aware allocation improved compute efficiency, and extra inference computation could beat a roughly 14× larger model in some matched-compute settings.^{[17]Reference 17Scaling LLM Test-Time Compute Optimally Can Be More Effective Than Scaling Model Parameters.https://arxiv.org/abs/2408.03314} The result depends on question difficulty and the pretraining-to-inference workload. It isn't a universal log-linear law or evidence that an arbitrary 2,000-token scratchpad beats a model ten times larger.

Three failure modes of extended reasoning

Even with native reasoning, extended test-time computation introduces distinct vulnerabilities:

1. Unfaithful rationalization: a textual rationale isn't an execution trace of neural activations. Turpin et al. found that biasing features could affect answers without appearing in the generated explanation.^{[10]Reference 10Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Promptinghttps://arxiv.org/abs/2305.04388} That study concerns prompted explanations; don't infer a quantified failure rate for every native reasoning model from it.
2. Extra cost without task gain: the GPQA study and pattern-based ICL study give specific examples where explicit CoT adds cost with limited gains or worse accuracy.^{[4]Reference 4Prompting Science Report 2: The Decreasing Value of Chain of Thought in Promptinghttps://arxiv.org/abs/2506.07142[5]Reference 5The Curse of CoT: On the Limitations of Chain-of-Thought in In-Context Learning.https://arxiv.org/abs/2504.05081} They don't show that every formatting or retrieval task suffers the same degradation.
3. Budget exhaustion and incomplete answers: internal reasoning uses generation and context budget. OpenAI documents that an exhausted output limit can end a response before a visible answer.^{[7]Reference 7Reasoning modelshttps://developers.openai.com/api/docs/guides/reasoning} Handle incomplete results as unfinished work; don't promote a partial rationale into an action.

Choose compute with an eval gate

Direct prompting, one trace, voting, and tree search aren't maturity levels. They are candidates with different accuracy and serving cost. Start with the cheapest candidate, then promote a more expensive strategy through an eval gate only when held-out results require it. Track p95 latency, the time under which 95% of requests finish, alongside quality. Snell et al. found that the best test-time allocation can depend on problem difficulty, so a fixed extra-sample budget isn't automatically optimal.^{[17]Reference 17Scaling LLM Test-Time Compute Optimally Can Be More Effective Than Scaling Model Parameters.https://arxiv.org/abs/2408.03314}

The following numbers are invented to exercise the selection rule. They are not measured endpoint latencies or evidence that voting beats direct prompting.

import math

results = [
    {"strategy": "direct", "accuracy": 0.76, "p95_ms": 190, "calls": 1},
    {"strategy": "single_trace", "accuracy": 0.84, "p95_ms": 360, "calls": 1},
    {"strategy": "vote_5", "accuracy": 0.94, "p95_ms": 740, "calls": 5},
    {"strategy": "tree_search", "accuracy": 0.96, "p95_ms": 1840, "calls": 14},
]

minimum_accuracy = 0.90
latency_budget_ms = 900

def eligible_result(row: dict) -> bool:
    if not isinstance(row, dict):
        return False
    accuracy, latency, calls = row.get("accuracy"), row.get("p95_ms"), row.get("calls")
    return (
        isinstance(row.get("strategy"), str) and bool(row["strategy"].strip())
        and type(accuracy) in (int, float) and 0 <= accuracy <= 1 and math.isfinite(accuracy)
        and type(latency) in (int, float) and 0 < latency <= latency_budget_ms and math.isfinite(latency)
        and type(calls) is int and calls > 0
        and accuracy >= minimum_accuracy
    )

eligible = [
    row for row in results
    if eligible_result(row)
]
selected = min(eligible, key=lambda row: (row["calls"], row["p95_ms"]), default=None)

for row in results:
    print(f"{row['strategy']}: accuracy={row['accuracy']:.0%}, p95_ms={row['p95_ms']}, calls={row['calls']}")
print(f"selected: {selected['strategy'] if selected else 'none'}")

direct: accuracy=76%, p95_ms=190, calls=1
single_trace: accuracy=84%, p95_ms=360, calls=1
vote_5: accuracy=94%, p95_ms=740, calls=5
tree_search: accuracy=96%, p95_ms=1840, calls=14
selected: vote_5

The gate rejects missing, non-finite, or out-of-domain measurements and invalid call counts. It uses call count as a simple tie-breaker, not as a dollar-cost estimate. Calls with different prompt lengths, reasoning budgets, or models can cost very different amounts. If no strategy clears the gate, return none; don't silently relax the requirements. For a real system, keep a table with:

Try a candidate with impossible measurements. These two comparisons alone would let it through:

invalid = {"strategy": "bad_receipt", "accuracy": float("inf"), "p95_ms": -1, "calls": 1}
naive_accepts = invalid["accuracy"] >= minimum_accuracy and invalid["p95_ms"] <= latency_budget_ms
print(f"two_comparisons_accept: {naive_accepts}")
print(f"validated_gate_accepts: {eligible_result(invalid)}")
print(f"missing_metric_accepts: {eligible_result({'strategy': 'incomplete', 'calls': 1})}")

two_comparisons_accept: True
validated_gate_accepts: False
missing_metric_accepts: False

Compare strategies on the same held-out cases and report uncertainty around success rates. Five correct examples aren't a dependable 100% success estimate. For release recommendations, separately measure unsafe approvals on blocked cases; an average accuracy threshold mustn't replace authorization.

When not to use CoT (or heavier search)

Use this checklist before you promote scaffolding or multi-sample voting:

Adding a visible CoT scaffold can add tokens and latency without a useful accuracy gain.^{[4]Reference 4Prompting Science Report 2: The Decreasing Value of Chain of Thought in Promptinghttps://arxiv.org/abs/2506.07142} Treat that prompt as another experimental arm, not as a required wrapper around every reasoning endpoint.

Where reasoning ends and tools begin

All runnable experiments above operate on provided facts or deterministic state. A real release decision requires current CI status, security scan output, and review state from source systems. Reasoning alone can't obtain those observations.

ReAct interleaves reasoning traces and task-specific actions so new observations can update the next decision.^{[18]Reference 18ReAct: Synergizing Reasoning and Acting in Language Models.https://arxiv.org/abs/2210.03629} This loop doesn't require raw private reasoning. It needs a validated action request, a controlled execution result, and a bounded next decision:

Need: security scan status is not present in supplied facts.
Next action request: get_security_scan(run_id="ci-1482")
Runtime responsibility: validate authorization, execute call, log result.
Next decision: apply policy only after observation is returned.

The next lesson implements that action boundary with typed function calls, schemas, errors, and safe execution.

Try to break the controller

Before changing each fixture, predict the result. Then run the relevant cell.

1. Replace all five samples for scan_failed with merge_release. Does a unanimous vote become safe?
2. Run solve_24([4, 5, 6, 7], max_states=1). Does its result prove the puzzle is unsolvable?
3. Lower latency_budget_ms to 100 in the release-gate example. What should ship?
4. Set one candidate's accuracy to float("inf") and p95 to -1. Would a simple two-comparison gate mistakenly accept it? What does eligible_result() do?

The first change produces a unanimous wrong recommendation: agreement can't override the failed scan. With a one-state budget, the solver returns budget_exhausted, not no_solution; it hasn't reached an answer. A 100 ms latency budget selects none, because no row meets both constraints. Infinite accuracy and negative latency would satisfy a simple two-comparison gate, but the validated gate rejects both. These are different failures: incorrect evidence use, unfinished search, no eligible strategy, and invalid measurements.