Search in machine reasoning means exploring possible solution states, actions or intermediate answers until the system finds a route that satisfies the goal. This is different from web search. Web search retrieves external documents. Solution search explores alternatives inside a problem space.
A language model can propose one likely continuation, but difficult problems often contain several plausible next steps. Search makes those alternatives explicit. The system can branch, score candidates, prune weak paths, backtrack from dead ends and use verification to decide which states deserve more computation.
This article explains search in Super Intelligence through state spaces, branching factor, depth-first search, breadth-first search, uniform-cost search, A*, beam search, best-first search, Monte Carlo tree search, backtracking, pruning, heuristics, Tree of Thoughts, verifier-guided search and tool-grounded search.
The 2023 Tree of Thoughts paper explored language-model problem solving through explicit search over intermediate states rather than one uninterrupted autoregressive trajectory. The broader concept is older than LLMs: search is a foundational idea in artificial intelligence, algorithms, planning, games and optimisation.
Previous: 036 — Planning. Planning defines the state, goal and actions. Search explores the possible routes through them.
The Hidden Transition: One Continuation Becomes a Search Space
A direct model generation chooses one token after another. A search system pauses and asks: what other candidate next states exist, and which ones should we explore?
For a maths proof, branches can be alternative lemmas. For scheduling, branches can be different assignments. For code repair, branches can be different patches. For planning, branches can be different actions.
The search system needs a representation of state, a way to generate successors, a scoring or cost function, a goal test and a resource budget.
State Space
The state space is the set of configurations the problem can occupy. A chess board is a state; a partially filled schedule is a state; a partially constructed proof can be a state.
Good state representation preserves what matters and discards irrelevant detail. A state that omits a hard constraint can make invalid branches look legal.
Initial State
Search starts from a known current state. If the initial state is wrong, the entire search tree can be irrelevant.
For an agent, initial state should come from observed environment data, not model imagination.
Goal Test
The goal test determines whether a state solves the problem. “Looks complete” is weak. “All classes assigned, no teacher conflicts, every room capacity satisfied” is strong.
A precise goal test prevents search from stopping on a polished but invalid candidate.
Successor Function
The successor function generates legal next states. In scheduling, assign one unscheduled class to a permitted slot. In a puzzle, make one valid move.
If the generator proposes illegal actions, the search wastes compute or requires later rejection.
Branching Factor
Branching factor is the number of possible next states from one state. Search cost grows rapidly when branching factor is large.
If each state has 10 successors, depth 6 can contain up to one million leaf paths before pruning. This is why heuristics and constraints matter.
Depth
Depth is the number of actions from the initial state. Deep search can solve long-horizon problems but consumes time and memory.
A high branching factor plus high depth produces combinatorial explosion.
Search Cost
A path can have cost: time, money, distance, risk, number of actions or a weighted combination.
Search algorithms differ partly in whether they ignore cost, accumulate cost or estimate future cost.
Breadth-First Search
Breadth-first search expands all states at depth 1 before depth 2, then depth 3. It is complete for finite branching and finds the shallowest solution when every action has equal cost.
Its weakness is memory. The frontier can grow exponentially because many states at the same depth must be stored.
Worked Breadth-First Example
A puzzle has start S. From S, actions lead to A, B and C. Each of those has three successors. If the goal is two moves away, breadth-first search will systematically find it after exploring depth 0, depth 1 and then depth 2.
This is sensible when shallow solutions are expected and memory is manageable.
Depth-First Search
Depth-first search follows one branch as far as possible before backtracking. It uses less memory because it stores mainly the current path and nearby alternatives.
It can waste time down a deep wrong branch and is not guaranteed to find the shallowest solution.
Worked Depth-First Example
If branch A contains a deep chain of 1,000 states with no solution while branch B has the goal after two moves, a depth-first ordering that chooses A first can perform badly.
Ordering and depth limits therefore matter.
Depth-Limited Search
Depth-limited search prevents unlimited descent by setting a maximum depth.
This protects compute but can miss a valid solution just beyond the limit.
Iterative Deepening
Iterative deepening runs depth-limited search repeatedly with increasing limits: depth 1, then 2, then 3.
It combines breadth-first completeness for shallow solutions with depth-first memory behaviour, at the cost of repeated exploration near the root.
Uniform-Cost Search
Uniform-cost search expands the frontier state with the lowest accumulated path cost rather than the shallowest depth.
This is appropriate when actions have different costs. A three-step route can be cheaper than a two-step route.
Dijkstra’s Algorithm
Dijkstra’s shortest-path algorithm is a special and highly important form of cost-based search over graphs with nonnegative edge weights.
A language model should not reinvent shortest-path arithmetic in prose when a graph algorithm can solve it exactly.
Best-First Search
Best-first search selects the state with the most promising evaluation score.
The score can be heuristic rather than exact path cost. This can accelerate search dramatically when the heuristic is informative.
Heuristic Function
A heuristic estimates how promising a state is or how far it is from the goal.
For route planning, straight-line distance can estimate remaining travel. For a proof, a model can estimate whether a partial derivation is useful. For scheduling, remaining conflicts can act as a heuristic.
Heuristics guide search but can be wrong.
A* Search
A* combines path cost g(n) with estimated remaining cost h(n): f(n) = g(n) + h(n).
With appropriate admissible heuristics, A* can find optimal solutions while exploring fewer states than uninformed search.
The principle is powerful for SI: combine what has already been spent with an estimate of what remains.
Admissible Heuristic
An admissible heuristic never overestimates the true remaining cost. This property supports A* optimality under standard conditions.
Language-model scores generally do not come with such guarantees, so LLM-guided search should not casually claim classical optimality.
Consistent Heuristic
A consistent heuristic respects a triangle-like relationship between neighbouring states and their step costs.
Consistency helps avoid repeated reopening of states in graph search.
Beam Search
Beam search keeps only the top k partial sequences at each step. It limits memory and compute by pruning the rest.
Language generation commonly uses beam search for sequence decoding, but reasoning beam search can score larger semantic steps.
A narrow beam can prune the eventual correct branch early; a wide beam costs more.
Beam Width
Beam width is the number of candidates retained. Increasing width improves coverage until additional candidates become redundant or too expensive.
Evaluate width against task success and cost rather than assuming bigger beams are always better.
Token-Level Beam Search Versus Thought-Level Search
Token-level beam search explores partial word sequences based largely on model probability. Thought-level search groups several tokens into a semantic step and scores the resulting state.
A high-probability sentence may be a poor reasoning move. Task-level evaluators can therefore outperform pure token likelihood for solution search.
Backtracking Search
Backtracking assigns a choice, checks constraints, then returns to an earlier choice when a contradiction appears.
Sudoku and scheduling are classic examples. Constraint checks prune impossible partial assignments before the entire candidate is built.
Constraint Propagation
When one choice reduces possibilities elsewhere, propagate the effect immediately.
If a tutor is assigned Monday 5 PM, remove that slot from every other class requiring the same tutor.
Propagation shrinks the search space before branching further.
Variable Ordering
In constraint problems, choose the next variable strategically. A common idea is to assign the most constrained variable first.
Resolving the hardest bottleneck early can reveal failure before the system spends time on easy choices.
Value Ordering
After choosing a variable, order its possible values. A good heuristic tries values likely to preserve flexibility for later choices.
This can reduce backtracking dramatically.
Duplicate State Detection
Different action sequences can reach the same state. If the search treats them as new every time, it wastes compute.
Hashing or canonical state representations allow the system to detect repeats.
Visited Sets
Graph search records states already explored. This prevents loops and redundant work.
For language-model reasoning, defining state equivalence can be difficult because two prose descriptions can mean the same thing.
Canonicalisation
Transform states into a standard representation before comparing them. Sort unordered facts, normalise units and use stable identifiers.
Canonicalisation makes duplicate detection more reliable.
Transposition Tables
Game-search systems cache previously evaluated positions because the same state can be reached through different move orders.
Agent reasoning can use the same principle: cache verified subproblems and state scores.
Minimax Search
In adversarial games, the value of a move depends on an opponent choosing responses. Minimax alternates between maximising our outcome and minimising it from the opponent’s perspective.
This is different from single-agent planning because another decision-maker actively resists.
Alpha–Beta Pruning
Alpha–beta pruning skips branches that cannot affect the final minimax decision given already known bounds.
It can search much deeper without changing the optimal minimax result under the same evaluation assumptions.
Monte Carlo Tree Search
Monte Carlo tree search, or MCTS, builds a search tree selectively using repeated simulation. It balances exploring uncertain actions and exploiting actions with strong estimated value.
MCTS became famous in game-playing systems because it can focus computation on promising regions of enormous state spaces.
Selection, Expansion, Simulation, Backpropagation
A common MCTS loop selects a node, expands a new action, simulates or evaluates the resulting state, then propagates the outcome back up the tree.
This “backpropagation” is not neural-network gradient backpropagation. It means updating search statistics along visited tree nodes.
Exploration Versus Exploitation in MCTS
The search should revisit actions that look strong while still testing alternatives that remain uncertain.
Too much exploitation locks into early estimates. Too much exploration wastes compute.
Search With Learned Value Functions
A neural network can estimate the value of a state or suggest promising actions, reducing the amount of brute-force search.
The search provides deliberation; the learned model provides heuristics. This hybrid pattern appears across modern AI.
Tree of Thoughts
Tree of Thoughts applies a similar idea to language reasoning: generate intermediate candidates, evaluate them and search over combinations.
The method makes backtracking and alternative exploration explicit instead of committing to one chain.
The important lesson is search structure, not the anthropomorphic word “thought”.
Self-Consistency as Leaf-Level Search
Generating many complete reasoning paths and voting over answers can be viewed as search over leaf solutions without exploring partial prefixes selectively.
It is simple and parallel but can waste compute finishing candidates that were already poor early on.
Prefix-Level Search
Prefix-level search evaluates partial reasoning before completion, allowing the system to stop weak candidates early and invest in stronger ones.
This can be more compute-efficient when partial-state evaluation is reliable.
Search Node Evaluation
A node can be scored by model probability, reward model, verifier, heuristic function, tool output or hard constraint check.
Composite scoring is common: reject hard violations first, then rank remaining states by estimated value.
Hard Pruning
Hard pruning removes states that provably cannot lead to valid solutions.
Examples: exceeded budget, violated capacity, contradictory equation, failed compiler check.
Hard pruning is safer than heuristic pruning because the reason for removal is objective under the specification.
Heuristic Pruning
Heuristic pruning removes low-scoring branches to control search size.
It can accidentally discard the correct solution. The pruning threshold should be evaluated on representative tasks.
Branch-and-Bound
Branch-and-bound tracks the best complete solution found and prunes partial branches whose optimistic bound cannot beat it.
This is powerful in optimisation when valid upper or lower bounds are available.
Search Budget
Every search needs limits: nodes expanded, tokens generated, tool calls, time or cost.
A system should report unresolved status when budget expires rather than fabricate completion.
Anytime Search
Anytime algorithms maintain a best-so-far solution and improve it as time permits.
This is useful for SI systems operating under variable deadlines.
Search Order Matters
Two algorithms exploring the same state space can have radically different cost depending on ordering.
Good heuristics are often more valuable than simply increasing the raw node budget.
Search Space Design Matters More Than Search Algorithm Alone
If the state representation includes impossible or irrelevant actions, every search algorithm wastes effort.
A narrower, well-designed action space can outperform a sophisticated search over a badly defined domain.
Search and Problem Decomposition
Decomposition can reduce one huge search into smaller searches with constrained interfaces.
But incorrect decomposition can remove global constraints, making local search solutions incompatible.
Search and Planning
Planning creates the formal or informal transition model. Search finds a path through it.
Some planners use specialised search algorithms; other plans are generated directly by models and verified afterward.
Search and Test-Time Compute
Article 034 framed runtime reasoning as resource allocation. Search is one major way to spend that budget.
Node expansion, candidate scoring and backtracking consume compute. Adaptive search invests more only when the problem remains unresolved.
Search and Tools
A search node can invoke external tools. Code-search branches run tests; research branches retrieve sources; planning branches query availability.
Tool outcomes become observations that update node value or legality.
Search and Retrieval: Keep the Words Separate
Document retrieval search asks “which external information is relevant?” Solution search asks “which possible internal path solves the problem?”
One SI task can contain both. A proof agent retrieves a theorem, then searches possible proof steps.
Worked Search Example: Small Scheduling Problem
Two tutors T1 and T2, two rooms A and B, three classes X, Y and Z. X requires T1, Y requires T2, Z can use either. Available slots are 4 PM and 5 PM. X and Y students overlap, so X and Y cannot share a time.
Initial state: nothing scheduled. Successor choices assign one class to a legal tutor-room-time combination.
A constraint-first search assigns X and Y early because their tutor and overlap constraints are tight. Z is flexible and can fill the remaining slot.
Trying Z first creates more branches because it can occupy many combinations. Variable ordering reduces search.
Worked Search Example: Code Repair
A function fails three tests. Candidate branches: fix boundary condition, change data type, alter loop termination.
Run tests after each patch. The boundary-condition patch fixes all failures; stop. There is no value in exploring dozens of unrelated rewrites once the acceptance criteria are met.
Worked Search Example: Mathematics
Problem: solve a nonlinear equation. Candidate strategies include algebraic factorisation, substitution and numerical root finding.
A search system can try symbolic factorisation first, verify candidate roots, and fall back to numerical methods if no closed form is found.
The strongest branch is chosen by correctness and task requirement, not by which explanation sounds longest.
Worked Search Example: Research
Question requires three facts. Branches search official documentation, academic papers and current news.
Each evidence branch closes when the required claim is supported. The synthesis node does not keep searching simply because more pages exist.
Search Failure: Branch Explosion
The generator proposes too many successors at every node. Search becomes computationally impossible.
Restrict actions using constraints, learned proposals or domain rules before increasing hardware.
Search Failure: Poor Heuristic
The heuristic consistently favours elegant but invalid plans.
Measure heuristic score against actual solution success and incorporate hard verification earlier.
Search Failure: Premature Pruning
The correct branch receives a low early score and is discarded.
Widen the beam, improve the evaluator or delay pruning until more evidence is available.
Search Failure: Repeated States
The agent loops through equivalent states described differently.
Canonicalise state and use visited-state detection.
Search Failure: Goal Test Too Weak
The planner stops when all activities have a time, but fails to check teacher conflicts.
Strengthen the goal test to include every hard constraint.
Search Failure: Goal Test Too Strong
The system requires every preference to be satisfied even when no such plan exists.
Separate hard constraints from soft preferences so feasible solutions remain reachable.
Search Failure: Reward Hacking
A candidate finds a way to score highly under the evaluator without actually solving the intended task.
Improve the objective and add independent checks. Search optimises whatever score you give it.
Search Failure: Correlated Candidates
Multiple language-model branches all start from the same mistaken assumption.
Increase diversity through alternative prompts, retrieved evidence, different models or explicit contradiction checks.
Search Failure: Expensive Verification
The verifier costs more than generating candidates.
Use cascades: cheap hard checks first, expensive model or human review only for survivors.
Completeness
A search algorithm is complete if it is guaranteed to find a solution when one exists under specified conditions.
LLM-guided heuristic search usually does not inherit completeness guarantees unless the underlying search preserves them.
Optimality
An optimal algorithm finds the best solution under a defined cost metric.
A model’s preference score does not establish optimality unless the algorithm and heuristic satisfy the required mathematical conditions.
Soundness
In formal reasoning, soundness means accepted solutions satisfy the rules.
Use formal verifiers where available instead of trusting a heuristic search score as proof.
Search Reproducibility
Stochastic search can produce different trees across runs. Record model version, random seeds, branching rules, evaluator and budget for reproducibility.
External tools can change, so exact replay may require snapshots of retrieved state.
Search Logging
Useful logs include node ID, parent ID, state summary, action, score, verifier result, reason for pruning and compute spent.
This supports debugging without exposing private internal chain-of-thought. Store operational state and evidence instead.
Search Visualisation
A tree or graph view can show where compute went, which branches failed and why the final solution won.
Visualisation is especially useful for planners and debugging agents.
Search Metrics
Measure solution rate, nodes expanded, depth, branching factor, time, tokens, verifier calls, best-so-far quality and optimality gap when known.
One benchmark score hides the efficiency profile.
Search Quality Versus Search Cost
Plot quality as a function of node budget. If gains stop after 20 expansions, a 200-node default wastes compute.
Different task classes can use different budgets.
A Search Failure Map
Level 1: wrong state representation. Level 2: missing legal action. Level 3: branching factor too high. Level 4: poor ordering. Level 5: weak heuristic. Level 6: premature pruning. Level 7: repeated states. Level 8: weak goal test. Level 9: verifier mismatch. Level 10: budget exhausted without useful escalation.
This eduKateSG map keeps search failures distinct from general “reasoning” failures.
A Practical Search Design Worksheet
Define initial state, goal test, legal actions, path cost, heuristic, duplicate-state rule, branch limit, depth limit, verifier, hard constraints, stopping rule and escalation route.
Then construct one case where direct generation works, one where search is needed, one where the correct branch starts with a low score and one where no valid solution exists.
Search is ready only when failure behaviour is tested as deliberately as success.
Independent Exercise 1: BFS or DFS?
The solution is expected at shallow depth but the tree is broad. Which uninformed strategy guarantees the shallowest solution under equal step cost?
Answer
Breadth-first search, although memory use can be high.
Independent Exercise 2: Cost
One path takes three steps costing 1 each; another takes two steps costing 5 each. Which is cheaper?
Answer
The three-step path costs 3; the two-step path costs 10. Step count and path cost are different.
Independent Exercise 3: A*
What two quantities does A* combine?
Answer
Accumulated path cost g(n) and estimated remaining cost h(n).
Independent Exercise 4: Beam Search
What risk comes from beam width 1?
Answer
It effectively becomes greedy search and can discard the correct branch after one locally attractive decision.
Independent Exercise 5: Duplicate States
Two reasoning paths reach the same verified state. Should both be expanded independently?
Answer
Usually no. Canonicalise and reuse the state unless path history itself matters to future legality or cost.
Independent Exercise 6: Hard Constraint
A schedule branch double-books a teacher. Should a language-model heuristic be asked whether to keep it?
Answer
No. Prune it deterministically because the hard constraint is violated.
Independent Exercise 7: Web Search Versus Solution Search
An agent looks up the current exchange rate, then explores three portfolio-allocation strategies. Which parts are which kind of search?
Answer
The exchange-rate lookup is information retrieval; exploring allocations is solution search.
Independent Exercise 8: Stopping
A formal checker verifies the required proof. Should search continue automatically for another 1,000 nodes?
Answer
No, unless the task also requests a shorter or better proof. The stated goal has been verified.
Search Frontiers
The frontier is the set of discovered states that have not yet been expanded. Different algorithms organise the frontier differently. Breadth-first search uses a queue, depth-first search uses a stack, uniform-cost search uses a priority queue ordered by path cost, and A* uses a priority based on path cost plus heuristic estimate.
This data-structure choice is not cosmetic. It determines which part of the state space receives compute next.
Open Set and Closed Set
Graph-search implementations often maintain an open set of frontier states and a closed or visited set of states already expanded.
A well-designed visited rule prevents cycles and repeated work. However, a state may need reopening if a cheaper path to it is discovered and the algorithm permits that possibility.
Path-Dependent State
Two routes can reach the same physical state with different cost, permissions or history. If that history affects future actions, the states are not truly equivalent.
For example, a travel itinerary reaching the same city with different remaining budget requires the budget to be part of state. Canonicalisation must not erase information relevant to the future.
State Abstraction
Search becomes cheaper when several detailed states can be represented by one abstract state without losing decision-relevant information.
An itinerary planner may treat many seat numbers as equivalent if seat identity does not affect later constraints. Abstraction reduces branching and memory.
The risk is over-abstraction: merge states that actually have different futures and the search can miss valid solutions.
Hierarchical Search
Search can occur at several levels. First choose a high-level route, then search the details inside each segment.
A travel planner may choose cities before selecting flights. A coding agent may choose an architecture before searching implementation variants.
Hierarchical search reduces the effective branching factor when the high-level decomposition is sound.
Macro-Actions
A macro-action packages several low-level actions into one reusable move. “Prepare verified report” might include retrieve, calculate and format.
Macros speed search by increasing the distance covered per branch, but they hide internal constraints. They should be used only when their preconditions and effects are well understood.
Search Over Decompositions
When the correct problem decomposition is unknown, the system can search alternative decompositions before solving.
One decomposition may split a maths problem by equations; another by geometric relationships. The system can test which produces solvable subproblems.
This adds a meta-search layer: search not only solutions, but representations of the problem.
Search Over Prompts
Some systems explore different prompts or instructions as candidate control policies. They evaluate which prompt produces better task performance.
Prompt search should use protected evaluations. Optimising on the exact final test set creates overfitting just as model training can.
Search Over Tools
An agent can search which tool route is best: calculator, code execution, database, browser or direct model reasoning.
Tool selection itself is a planning/search problem. Cheap deterministic tools should often be preferred when they can establish the answer exactly.
Search Over Models
A router can treat different models as actions: small fast model, specialised code model, large reasoning model.
The search objective may minimise cost while meeting a quality threshold. Model selection becomes part of system search rather than a permanent global choice.
Search and Retrieval-Augmented Generation
RAG contains retrieval search, but it can also include solution search. The system retrieves several passages, tries alternative evidence combinations, evaluates answer grounding and selects the best supported synthesis.
This is more complex than one top-k retrieval call and requires careful provenance so branches do not mix incompatible source versions.
Multi-Hop Search
Some questions require a sequence of facts where each answer determines the next query. Search proceeds through evidence states rather than one query-result list.
Example: identify a researcher, then their institution, then a policy published by that institution. Each hop depends on the previous result.
Multi-hop systems need stopping rules and entity verification because an early identity error compounds across hops.
Bidirectional Search
When both start and goal states are clearly known, search can proceed forward from the start and backward from the goal until the frontiers meet.
This can reduce effective depth dramatically in some problems.
It is less useful when the goal is vague or predecessor actions are difficult to enumerate.
Meet-in-the-Middle Reasoning
A broader version of bidirectional search solves part of a problem from each side and combines results.
Cryptographic algorithms and combinatorial problems use this idea. SI can apply similar structure when forward and backward constraints are both strong.
Backward Chaining
Start from the goal and ask what conditions would make it true. Then recursively search how to satisfy those preconditions.
This is natural for diagnostic and planning tasks: to publish, need approval; to get approval, need final fee and venue; to finalise venue, need availability.
Forward Chaining
Start from known facts and apply actions or rules whose preconditions are satisfied.
Forward chaining is useful when many possible consequences can be derived from current state. The search can stop when the target is reached.
Search With Dynamic Costs
Action cost can change during search. A flight price changes, a room becomes unavailable, an API call becomes rate-limited.
The system may need to update edge costs and replan. Algorithms designed for static graphs can become stale.
Incremental Search
Incremental algorithms reuse previous search work when the environment changes slightly instead of starting from scratch.
This is valuable for navigation, scheduling and agent plans where updates are frequent but local.
Real-Time Search
Some agents must act before a full search completes. Real-time search expands a limited horizon, chooses an action, observes the new state and continues.
This resembles rolling-horizon planning. The agent trades optimality for responsiveness.
Search Under Partial Observability
The true state may not be fully known. A robot cannot see behind an obstacle; a research agent does not know which unseen source contains the answer.
The state can include beliefs or probability distributions over possible worlds. Search then reasons about information-gathering actions as well as goal actions.
Information-Gathering Actions
Sometimes the best next step does not directly advance the goal; it reduces uncertainty. Ask the user, run a diagnostic, open a document or measure a sensor.
Search algorithms can assign value to these actions because better information improves later decisions.
Belief-State Search
In partially observable problems, one node can represent a set or distribution of possible states rather than one known state.
This is more expensive than ordinary search but captures uncertainty honestly.
Stochastic Transitions
An action can have several possible outcomes. Sending a request may succeed, fail or time out. A medical treatment can have probabilistic outcomes.
Search must consider expected consequences or risk criteria, not assume one deterministic next state.
Markov Decision Process Intuition
A Markov decision process represents states, actions, transition probabilities and rewards. Planning/search seeks a policy that chooses actions to maximise expected cumulative reward.
This framework underlies much reinforcement learning and formal decision theory.
Policy Versus Plan
A plan is often one action sequence. A policy maps many possible states to actions.
In uncertain environments, a policy is stronger because it specifies what to do after different outcomes.
Search and Reinforcement Learning
Reinforcement learning can learn policies or value functions that guide search. Search can also improve action choices beyond the learned policy at test time.
AlphaZero famously combined learned policy/value networks with MCTS, illustrating the power of training and search together.
Learned Heuristics
A model can be trained to estimate remaining cost, probability of success or branch value from state.
Learned heuristics can outperform hand-designed rules but lose classical guarantees when their errors are unbounded.
Heuristic Calibration
If a heuristic predicts 80% success for many branches, measure whether roughly 80% actually lead to success under the search protocol.
Calibration helps decide how aggressively to prune or allocate compute.
Search Diversification
A search can deliberately avoid putting all compute into similar branches. Diversity penalties or clustered candidate selection preserve alternative approaches.
This is useful when early scores are noisy and multiple solution families exist.
Novelty Search
Some optimisation problems reward behavioural novelty rather than direct objective improvement to escape local optima.
Novelty search can discover unexpected solutions, but it is risky when the objective has hard safety requirements.
Evolutionary Search
Evolutionary algorithms maintain a population of candidates, mutate or recombine them, score fitness and select survivors.
This is another way to explore large solution spaces without gradients. Code, prompts and designs can all be evolved under suitable fitness functions.
Genetic Programming
Programs themselves can be evolved as tree structures. Candidate programs mutate, recombine and are evaluated on tests.
The fitness function must resist overfitting to the visible test suite.
Local Search
Local search starts with one complete candidate and repeatedly modifies it to improve objective value.
Hill climbing is simple but can get stuck in local optima. Simulated annealing sometimes accepts worse moves early to explore more broadly.
Hill Climbing
Choose the best neighbouring candidate and repeat until no neighbour improves the score.
Efficient for smooth spaces, fragile when the landscape contains local maxima or plateaus.
Simulated Annealing
Accept some worse moves with a probability that decreases over time. This allows escape from local optima early while becoming more conservative later.
The temperature here is an optimisation parameter, conceptually related to exploration, not necessarily the same implementation as language-model sampling temperature.
Tabu Search
Tabu search keeps memory of recent moves or states to avoid cycling back into recently explored regions.
This illustrates a general SI principle: search improves when it remembers where it has already failed.
Search and Constraint Solvers
SAT, SMT and constraint-programming solvers use highly optimised search and propagation to satisfy formal constraints.
A language model can translate a natural-language problem into solver variables and constraints. The solver provides the exact search; the model provides the interface and explanation.
Search and Theorem Provers
Automated theorem provers search proof spaces using inference rules. Formal proof assistants verify each accepted step.
LLMs can propose tactics or lemmas, but formal systems remain stronger verifiers of proof validity.
Search and Databases
Database query optimisers search execution plans: index scan, join order, join algorithm and other choices.
This is a reminder that search is a general computational pattern far beyond “AI agents thinking”.
Search and Compilers
Compilers can search or optimise instruction schedules and register allocation under constraints.
SI systems can learn heuristics for these problems while deterministic compilers preserve correctness.
Search and Games
Games offer clear states, actions and outcomes, making them classic search laboratories.
Real-world agent tasks are harder because states are partially observed, rules change and rewards are ambiguous.
Search and Creativity
Creative generation can be viewed as search through candidate designs, melodies, layouts or phrases.
The evaluator is subjective, so diversity and human taste may matter more than formal optimality.
Search and Scientific Discovery
A research agent can search hypotheses, experiments and mathematical arguments. Candidate quality depends on evidence and experiment design, not only model scores.
Recent frontier systems increasingly combine generation, verification and iterative search for difficult scientific and mathematical work.
Search Safety Boundaries
Exploring a candidate action in a sandbox is different from executing it in the real world. Search should simulate or score dangerous branches without granting them external permissions.
Only the selected, authorised action should cross the execution boundary.
Search Completion Standard
A search system is complete when it defines state, legal actions, goal test, cost or value, duplicate handling, heuristic or ordering, verifier, resource budget and stopping rule. The task is complete only when the selected solution passes the required external or formal checks.
This standard makes search reproducible and diagnosable rather than a vague instruction to “explore alternatives”.
Independent Exercise 9: Bidirectional Search
When can bidirectional search help?
Answer
When start and goal states are well defined and it is practical to generate both successors and predecessors, allowing the two frontiers to meet.
Independent Exercise 10: Partial Observability
A robot cannot see whether a door is locked. What kind of action may be valuable before route planning continues?
Answer
An information-gathering action such as checking the lock or sensor state, because the true planning state is uncertain.
Independent Exercise 11: Local Search
A complete timetable is feasible but expensive. What search family can improve it through small swaps without rebuilding from scratch?
Answer
Local search or neighbourhood optimisation, provided every modification remains constraint-checked.
Independent Exercise 12: Solver Hybrid
A natural-language scheduling request contains exact capacity and time constraints. What is a strong architecture?
Answer
Use the model to interpret the request into formal constraints, a solver to search feasible schedules, and the model to explain the verified result.
Frequently Asked Questions About Search in SI
Is this the same as Google Search?
No. This article concerns search through possible solution states. Web search retrieves external information.
Why use search with an LLM?
Because one autoregressive path can commit early. Search explores alternatives, supports backtracking and allows verification before spending more compute.
What is a heuristic?
An estimate that guides which states are worth exploring first.
What is branching factor?
The number of successors generated from a state. Large branching factors create rapid combinatorial growth.
What is beam search?
A bounded search that keeps only the top k partial candidates at each stage.
What is MCTS?
Monte Carlo tree search selectively builds a tree using repeated selection, expansion, evaluation or simulation and value updates.
Can LLM search guarantee an optimal answer?
Not generally. Guarantees depend on the underlying algorithm, state representation, costs, heuristic properties and verifier.
When should search stop?
When the goal is verified, the budget is exhausted, no branch can improve the best solution, or unresolved uncertainty requires a different tool or human input.
Search Turns Reasoning Into Controlled Exploration
Search is what allows an SI system to consider more than one possible route. It can explore, compare, prune and backtrack rather than treating the first plausible continuation as destiny.
The value comes from structure: explicit state, legal actions, meaningful heuristics, hard constraints, reliable verifiers and stopping rules. Without those, more search merely creates more ways to be wrong.
Continue through the How Super Intelligence Works hub. Previous: 036 — Planning. Next planned: 038 — Verification.
Search Reality Check: The Search Space Is Part of the Model
An algorithm can search perfectly and still fail if the state space excludes the real solution. Missing actions, collapsed distinctions or an incorrect goal test create a problem no amount of additional search budget can repair. The search design itself therefore belongs to the evaluated system.
Before increasing depth, beam width or Monte Carlo simulations, ask whether the correct branch can be generated, whether the evaluator can recognise progress and whether the goal test captures the user’s actual requirement. Search earns its compute only after those foundations are sound.
Search Floor Margin
A production search system should preserve the winning path and the reasons major alternatives were rejected. This does not require exposing private chain-of-thought; state IDs, hard-constraint failures, verifier results, costs and tool evidence are enough to reproduce the operational decision. Search becomes trustworthy when the selected branch is not merely the branch that survived, but the branch whose acceptance conditions can be inspected.
The final search floor requires the system to preserve an unresolved status when no verified solution exists within the budget. Exhausting the frontier or compute allowance is a legitimate result; it is not permission to promote the best-looking failure into a solved task.
Continue to 038 — Verification: Checking Rather Than Merely Generating, or return to the How Super Intelligence Works hub.
