Algorithms, Heuristics and Learned Procedures

A learned procedure can improve guidance and still forfeit completeness, optimality, safety or termination unless the invariant carrying each guarantee remains explicit and enforced.

TLDR

A learned procedure does not inherit an algorithm's guarantees merely by imitating its outputs. Guarantees follow from stated assumptions, preserved invariants and a proof or enforcement mechanism.
The decisive variable is the learned component's authority: using a score to reorder work may preserve exactness, while using it to prune possibilities or commit actions can erase the original proof.
Hybrid systems can keep strong guarantees by retaining valid bounds, exhaustive fallback, formal verification, runtime shields or postcondition checks around learned guidance.
Neither explicit code nor learning guarantees correctness in an open world. An exact algorithm can still solve the wrong model, and a verified network remains verified only inside its stated domain.
Before replacing any procedural step, write a guarantee-transfer record that names the promise, its carrier, the altered invariant, the negative case and the control that restores it.

Imagine two route planners facing the same six-junction map. The first uses an explicit shortest-path algorithm. The second has watched thousands of successful journeys and learned which turn usually leads towards the destination. On familiar maps, the learned planner reaches an answer with fewer expansions. It looks as if it has learned the algorithm.

Now change one road. The road still appears on the map, but its cost has increased. The learned planner strongly favours the familiar branch. What happens next depends less on the quality of its score than on what the surrounding system lets that score do. If the score merely orders which junction an exact search examines first, the system can still find the true shortest path. If the score prunes the unfavoured branch, the optimal route may disappear before it is considered. If the score directly chooses every turn, even completeness can vanish: the vehicle may loop, stop or reach an unnecessarily costly destination.

The same learned judgement can be harmless guidance, a proof-breaking shortcut or the whole policy. That difference is the core of this paper. It explains why debates framed as “algorithms versus learning” usually miss the engineering question. The important question is: which invariant carries the promise, and does the learned component have permission to violate it?

Figure 1. A fast route becomes a false promise. The upper path costs 5 and the lower path costs 7. The learned preference is neither safe nor unsafe by itself. Its authority inside the search determines what can still be guaranteed. Numbers and routes are synthetic. Edge labels are costs.

Where the promise lives

An algorithm is often described as a recipe. That is useful until the recipe metaphor hides the conditions under which the result follows. Dijkstra's shortest-path procedure, for example, is not simply a familiar sequence of operations. Its correctness depends on a graph model, a cost assigned to each edge and conditions on those costs. Under the relevant assumptions, its invariant supports a claim about the path returned.[1]

A heuristic is different. It uses accessible information to guide search, prioritise a candidate or approximate a hard judgement. A heuristic can be explicit, such as straight-line distance, or learned from examples. It may be excellent without carrying the final proof. A learned procedure is broader still: it can estimate a value, rank alternatives, select a branch, imitate an algorithmic transition or act as a complete policy. “Learned” describes how parameters were obtained, not what authority the component has at runtime.

This yields two corrections. First, explicit code is not automatically correct. A bug, a false specification or an invalid input assumption can make a fully deterministic programme reliably wrong. Second, a learned component is not automatically beyond proof. A network can be formally verified over a bounded input set, constrained to discrete transitions or wrapped by a verifier whose own logic carries the required property.[9]

The carrier, not the label

A guarantee is a conditional statement. It has a domain, assumptions and a mechanism that makes the conclusion follow. “This search returns an optimal path” might depend on non-negative edge costs, a complete frontier, correct relaxation and a stopping rule. “This controller never enters an unsafe state” might depend on a temporal-logic specification, an adequate environment abstraction and a shield that vetoes unsafe actions. The words algorithm, heuristic and policy do not settle any of those obligations.

P ∧ I₁ ∧ I₂ ∧ … ∧ I_k ⇒ G P is the set of stated preconditions, each I is an invariant used by the proof, and G is the promised property. After replacing a component, the promise survives only if the new system still establishes every required invariant.

That expression is the paper's central rule. Suppose an original component R is replaced by a learned component L. Behavioural similarity between R and L on a test set is relevant evidence, but it does not prove that L preserves every invariant for every in-scope input. The system needs one of three stronger routes: prove the relevant property of L; enforce the property outside L; or keep a fallback that completes the original proof when L is uncertain or wrong.

Published evidence

Classical shortest-path and heuristic-search work makes guarantees conditional on formal properties of the graph, costs, frontier and heuristic.[2][3] Neural verification, shielding and discrete neural reasoning show that learned systems can obtain bounded guarantees when those obligations are represented and checked explicitly.[8][15]

Figure 2. Where a guarantee lives. Proof, runtime enforcement and empirical evaluation support different claims. A learned system may use all three, but they should not be treated as interchangeable. Conceptual figure. No measured quantities.

Six promises that often get bundled together

A system can retain one guarantee and lose another. A learned branch selector may leave optimality intact while changing runtime unpredictably. A bounded-time policy may always terminate while sacrificing completeness. A formally safe controller may avoid prohibited states but still pursue a poor objective. The word “guaranteed” is therefore incomplete until the property is named.

Promise	Question answered	Typical carrier	Common way learning breaks it
Termination	Will the procedure stop?	Finite state, decreasing measure or resource bound	A policy loops or keeps generating new states
Completeness	Will it find a solution if one exists?	Exhaustive frontier and sound pruning	A learned filter drops the only viable branch
Optimality	Is the returned solution best under the model?	Admissible bounds, exact comparison and stopping rule	An estimate overstates a promising branch and enables early stopping
Approximation	How far from optimum can the result be?	Proven ratio or calibrated error envelope	Average validation error is mistaken for a worst-case bound
Safety or feasibility	Can a forbidden state or constraint violation occur?	Invariant, shield, validator or constrained action set	The model's own confidence becomes the safety test
Complexity	What resource growth is bounded?	Algorithmic analysis and bounded representation	Inference, retries or generated search depth is input dependent and unbounded

The useful engineering move is to split the bundle before choosing a mechanism. You may need guaranteed feasibility but only empirical quality. You may need a hard deadline but tolerate a non-optimal answer. You may need optimality on a well-defined subproblem while the surrounding task remains open-ended. Once the promise is decomposed, learning can be placed where it earns value without being asked to carry a proof it never received.

The argument in one passChart · flow

flowchart LR
  A["Where the promise lives"] --> B["One score, three authorities"]
  B --> C["Imitation is not implementation"]
  C --> D["Put learning inside the proof<br/>boundary"]
  D -. "re-test" .-> A
  classDef first fill:#0a1424,stroke:#087A98,stroke-width:2px,color:#e6f3ff
  classDef step fill:#0a1424,stroke:#3f7da0,stroke-width:1px,color:#e6f3ff
  class A first
  class B,C,D step

A structural route through Algorithms, Heuristics and Learned Procedures, from Where the promise lives to Choose the carrier before the learner. Reading use: follow the relation, then test it against the surrounding evidence and limits.

One score, three authorities

Return to the route planner. The learned model emits one number for each frontier node: lower means “examine this first”. Nothing about the number itself says whether it is a suggestion, a bound or a final decision. Yet those roles have radically different proof obligations.

Thought experiment: reorder, prune or commit

In the first version, the score only reorders work. The search still retains every reachable candidate and stops only under the original exact rule. A poor score wastes time, but it cannot hide a solution. In the second version, any candidate above a threshold is pruned. The model now makes a universal claim about every removed branch: none can contain a needed or better solution. In the third version, the highest-scoring action is executed directly and search ends. The model has become the policy.

Only one causal feature changed: the authority attached to the score. Moving a learned component from ordering to pruning is not a performance tuning change. It transfers a proof obligation. Moving it from pruning to commitment transfers even more: the score now determines the trajectory, stopping behaviour and reachable states.

Figure 3. The guarantee-generality frontier. Greater openness usually makes universal claims harder, but verified modules and runtime shields can lift a hybrid system above the empirical frontier. Position is illustrative, not a ranking of named systems. Conceptual figure. Axes are qualitative.

A* makes the transfer visible

A* search assigns each node a priority:

f(n) = g(n) + h(n), with h(n) ≤ h*(n) g(n) is the known cost from the start to node n. h(n) estimates the remaining cost. h*(n) is the true lowest remaining cost. When the required conditions hold, an admissible heuristic never overestimates that remainder, allowing the stopping rule to support optimality.[2]

Replace a hand-built admissible heuristic with a learned estimate. If the model overestimates the promising branch, an implementation that stops when it first removes the goal from the frontier can return a more expensive path. High average accuracy does not repair the broken inequality. The relevant question is whether every in-domain estimate respects the bound required by the proof.

Neural A* makes the attraction of this combination concrete by learning a guidance map for differentiable A* and evaluating the resulting optimality-efficiency trade-off.[11] That is a useful empirical design objective. It remains distinct from claiming that an unconstrained learned estimate has inherited the original admissibility proof.

One remedy is to retain an independently admissible upper envelope for the learned estimate. For non-negative path costs, a system can use max(0, min(h_learned, h_safe)), where h_safe is known not to exceed the true remaining cost. The model can still contribute when its estimate is lower, but it cannot overstate the safe bound. This may not deliver the fastest possible search, and constructing h_safe may itself be difficult. It illustrates the pattern: the learned component proposes efficiency; the envelope carries optimality.

A newer line of work attacks the same obligation during training. Cross-Entropy Admissibility treats heuristic learning as constrained optimisation and reports much stronger guidance than compressed pattern databases on the Rubik’s Cube. The important word is still near: empirical near-admissibility and sample-complexity bounds do not turn an unchecked network output into a universal proof. If optimality is non-negotiable, the runtime system must still enforce the bound or retain an exact certificate path.

Figure 4. One score, three authorities. Reordering can leave the proof-bearing frontier intact. Pruning requires a sound exclusion rule. Commitment turns the score into the trajectory policy. Conceptual intervention: the score is held fixed while its runtime authority changes.

The serious negative control: learning can preserve exactness

The preferred argument would be too strong if every learned substitution destroyed every guarantee. It does not. In branch-and-bound optimisation, a learned model can select which variable to branch on while valid relaxations, bounds and exhaustive bookkeeping remain responsible for proving optimality.[4] Gasse and colleagues trained a graph neural network to imitate strong branching inside an exact mixed-integer solver.[10] A bad branching choice can make the solver slow. It need not make the final certificate false, provided the learned choice does not alter sound pruning or the terminal proof.

Shielding offers the same lesson in control. A reinforcement-learning policy may propose actions, while a separately synthesised shield removes or corrects actions that would violate a temporal-logic safety specification.[8] The shield does not make the policy generally correct, and its own guarantee depends on the specification and environment abstraction. It shows where safety lives.

Other celebrated hybrids should be described with the same care. AlphaGo combined learned policy and value networks with tree search.[7] The architecture demonstrated extraordinary capability, but search plus learning does not by itself imply an exact guarantee that the selected move is globally optimal. The evidence and the claim must still match.

These cases are not compromises between “old” and “new” AI. They are compositional designs. The learned component handles a high-dimensional or expensive choice. The exact component retains the invariant. What matters is not whether learning appears in the system, but whether learning can erase the evidence needed to accept the result.

Imitation is not implementation

A learner can reproduce an algorithm's outputs on every training example without recovering the algorithm that generated them. A finite sample leaves many compatible rules. Some extend correctly to larger inputs, unusual topology or longer horizons. Others exploit regularities that vanish outside the sample. The training loss usually cannot distinguish them until the missing case arrives.

Pointer Networks made this possibility productive. They learned approximate solutions to geometric and combinatorial tasks from examples and demonstrated generalisation beyond some training lengths.[6] Later neural algorithmic reasoning work made the target more explicit: learn the execution of sorting, searching, dynamic programming and graph algorithms. The CLRS benchmark provided a common suite for studying those procedures and their generalisation challenges.[12]

The evidence is neither “neural networks cannot learn algorithms” nor “a successful test proves they have”. Causal regularisation has improved out-of-distribution performance on algorithmic tasks, including larger inputs, while still reporting a gap that the intervention aims to reduce.[13] Work without intermediate supervision also treats size extrapolation as a central challenge.[14] A discrete-state design has gone further, claiming correctness for its restricted learned computations because the architecture constrains trajectories to predefined states and the proof reasons over those transitions.[15]

Recent theory is beginning to ask the right guarantee question directly. A 2026 preprint gives sufficient conditions under which message-passing graph neural networks can approximate certain algorithms on arbitrary input sizes and also derives impossibility results for tasks the standard architecture cannot learn.[17] A separate neural-compilation programme compares analytically compiled algorithmic networks with conventionally trained ones to expose gaps between expressivity, trainability and faithful mechanism.[16] These are stronger forms of evidence because they identify conditions, not merely scores.

Failure boundary

An explicit algorithm guarantees a property only relative to its formal model and correct inputs. Dijkstra can return the shortest route in a graph that omitted a road closure. A shield can enforce the wrong safety specification. A verified network can leave its verified input region. No procedural guarantee repairs a false world model by itself.

Thought experiment: the ninety-nine per cent copier

Suppose a policy copies the correct next step with 99 per cent accuracy on states drawn from expert demonstrations. A one-step test looks excellent. Now deploy it on a 100-step task. Under the deliberately generous assumption that errors are independent and do not alter later difficulty, the probability of an entirely correct trajectory is 0.99^100, about 36.6 per cent. That curve is only an illustration. Sequential learning can be worse because an early error changes which state appears next.

Imitation learning exposes this dependency. Future observations depend on previous actions, so fixed expert trajectories do not provide independent and identically distributed training states for the learner's own deployment trajectory. DAgger addresses the problem by gathering expert labels on states the learner actually visits.[5] It strengthens the learning process. It does not turn a finite learned policy into a universal proof of safe completion.

Figure 5. Trajectory reliability across horizon. The curves use the simplifying independence model p^T. Real policies can encounter correlated errors and self-induced distribution shift, so the figure is an intuition pump rather than a forecast. Illustrative calculation. No empirical deployment data.

What tests can establish

A test set can estimate performance on a specified sampling process. A stress suite can expose selected counterexamples. An out-of-distribution benchmark can challenge a known axis such as graph size. None of them silently quantifies every future input. The disciplined claim is therefore conditional: “on this population, under this sampling and uncertainty, the procedure achieved this result”.

This does not make empirical evidence weak. In open-world tasks, it may be the strongest evidence available. It becomes dangerous only when the system architecture treats it as a different kind of evidence. A 99.9 per cent historical pass rate can justify a release decision under an explicit risk model. It cannot serve as the sound pruning predicate for a branch that contains an irreversible harm unless the remaining risk is separately contained.

Open hypothesis

Systems will show a disproportionate rise in severe tail failures when a learned score is promoted from ordering to pruning or commitment without a corresponding change in proof, monitoring or recovery. The hypothesis can be tested by holding the model fixed and varying only its runtime authority under matched fault and distribution-shift scenarios.

How the claim changes under pressureChart · state

stateDiagram-v2
  [*] --> Claim
  state "The carrier, not the label" as Claim
  state "Six promises that often get<br/>bundled together" as Test
  state "Thought experiment: reorder,<br/>prune or commit" as Revision
  Claim --> Test: expose mechanism
  Test --> Decision: evidence survives
  Test --> Revision: rival survives
  Revision --> Claim: narrow or rebuild
  Decision --> [*]

The revision loop begins with The carrier, not the label and keeps counterexamples inside the reasoning path. Reading use: follow the relation, then test it against the surrounding evidence and limits.

Put learning inside the proof boundary

The design choice is not binary. Learning can sit at several depths inside a procedure. It can propose candidates for an exact evaluator, rank work that a complete process will eventually inspect, estimate a quantity within a certified envelope, choose among actions allowed by a shield, or execute directly. Each depth grants more semantic freedom and demands stronger evidence.

A useful default is to grant the learned component the least authority that captures its advantage. Language variation may require learned extraction, while arithmetic remains explicit. A learned branch score may reduce search, while valid bounds remain responsible for pruning. A policy may navigate ordinary states, while a runtime monitor owns the forbidden-state boundary. This is not an aesthetic preference for deterministic code. It is a way to keep the carrier of each consequential claim observable. The architecture should make that limit visible to operators and reviewers.

Worked example one: the matched search laboratory

The laboratory below uses the graph from the opening case. All edge costs are non-negative. The upper path has cost 5; the lower path has cost 7. Dijkstra supplies the matched exact reference. The safe A* heuristic is an admissible lower bound. The learned estimate is intentionally wrong on the upper branch. The hybrid clamps that estimate to the safe bound before search.

The negative case is not “machine learning fails”. It is more precise: unbounded learned estimates can violate the condition that made the A* stopping rule optimal. The positive case is equally important: the same estimate can remain useful inside an envelope, and a learned tie-breaker can change visit order without changing the exact priority.

Figure 6. Matched search laboratory

Adjust the learned estimate for branches A and B. Run all methods, then select a row to display its path. The graph, costs and stopping rule remain fixed.

Learned estimate on A branch20

Learned estimate on B branch0

Expected default: Dijkstra, safe A* and the bounded hybrid return cost 5. Unbounded learned A* returns cost 7.

Assumptions: finite graph, non-negative costs, goal accepted when popped, and the safe heuristic values are valid lower bounds.

Method	Path	Cost	Nodes popped	Result against exact reference	Guarantee carrier
Dijkstra	S → A → C → D → G	5	S, A, B, C, E, D, G	matches optimum	non-negative costs and exact frontier
Safe A*	S → A → C → D → G	5	S, A, C, D, G	matches optimum	admissible heuristic and A* stopping rule
Unbounded learned A*	S → B → E → G	7	S, B, E, G	suboptimal by 2	no enforced admissibility bound
Bounded learned hybrid	S → A → C → D → G	5	S, B, E, A, C, D, G	matches optimum	independent admissible envelope
Learned tie-break within Dijkstra	S → A → C → D → G	5	S, B, A, E, C, D, G	matches optimum	exact cost priority; learning breaks ties only

View the executable core and expected assertions

// The browser runs this same search core without external libraries.
const exact = search({priority: (n, g) => g});
const learned = search({priority: (n, g) => g + hLearned(n)});
const hybrid = search({
  priority: (n, g) => g + Math.max(0, Math.min(hLearned(n), hSafe(n)))
});

console.assert(exact.cost === 5, "Exact reference should cost 5");
console.assert(hybrid.cost === exact.cost, "Bounded learned guidance should preserve optimum");
console.assert(learned.cost === 7, "Default adversarial estimate should expose the negative case");

Interactive artefact. The positive and negative cases differ only in how the learned estimate is bounded or authorised. The code operates entirely on synthetic data and remains usable as a static explanation when JavaScript is disabled.

The laboratory demonstrates a narrow claim, not a universal recipe. A safe lower bound may be unavailable for a perception-rich problem. Clamping can discard much of the learner's speed advantage. A learned estimate can also alter tie behaviour, memory use or runtime without affecting path cost. Those are reasons to state the target guarantee precisely, not reasons to collapse all evidence into one accuracy number.

Worked example two: a learned incident queue inside a deterministic service envelope

Consider an operations team handling service incidents. Each incoming case contains free text, customer impact, affected product, elapsed time and system signals. A learned model can rank cases by expected urgency and route them towards specialists. The language and interaction patterns are difficult to express as a compact rule set, so learning adds real value.

The operating promise, however, is not merely “high-risk cases tend to appear near the top”. Suppose the process requires three properties: every priority-one incident must be acknowledged within fifteen minutes; no accepted case may wait more than four hours; and a case may close only after the required evidence and an authorised resolution decision exist. Those properties have different carriers.

A scheduler can reserve deadline lanes, compute age directly and apply a no-starvation rule. A closure service can check evidence state and authority. The learned score then orders cases inside the remaining eligible set. If the model ranks a case badly, efficiency and prioritisation quality suffer. The deadlines and closure predicate can still hold. If the model is allowed to hide cases below a score, reset their age, or mark them complete, the service promises now depend on the model's unseen tail behaviour.

Worked scenario

The incident queue is a production-shaped synthetic scenario. The times make the invariants concrete; they are not reported results or recommendations for a particular organisation. Local service objectives, legal duties, case volumes and recovery options must determine the real thresholds.

Figure 7. Learned ranking inside a deadline envelope. The ranker contributes semantic judgement while deadlines, no-starvation and closure remain explicit process invariants. Production-shaped synthetic architecture. Times described in the text are illustrative.

The guarantee-transfer record

A model card describes a model. A workflow diagram shows where components connect. Neither necessarily preserves why a procedural promise survived a substitution. For any consequential replacement, create a small guarantee-transfer record. Its unit is one claim about one decision boundary, not the entire application.

Start with the exact promise. “More accurate” is not a guarantee. “Every eligible case is eventually examined” is. Record the formal or operational domain, including what is excluded. Name the current carrier: proof, bound, finite enumeration, validator, shield, approval, monitor or postcondition. Then describe the learned component's authority in verbs: rank, estimate, prune, stop, write, close or execute.

The most important field is the changed invariant. If a learned heuristic can overestimate, note that admissibility is no longer established. If a classifier can remove a case from a queue, note that completeness or no-starvation now depends on its recall tail. If a generated plan can repeat a write after an unknown outcome, note that idempotency and state reconciliation have left the runtime. This language prevents a system-level promise from being smuggled through a component-level score.

Next state how the promise is recovered. The recovery can be a proof of the learned component, an exact fallback, a conservative envelope, an external veto, a bounded action set or independent verification of the final state. It must be executable or reviewable. “The prompt tells the model not to” is guidance, not enforcement. “The model was 99.8 per cent accurate” is evaluation, not a worst-case exclusion rule.

Finally, write the counterexample before deployment. Name an input that violates the learner's likely shortcut, a distribution shift that changes the decision surface, and a dependency failure that makes outcome unknown. Record what the system must do in each case. A promise that cannot survive its named negative case has not transferred.

Practitioner synthesis

The guarantee-transfer record is the paper's original operational instrument. It combines formal proof obligations with release evidence and runtime control. It should be versioned whenever the model, threshold, tool contract, state representation, fallback or action authority changes.

Figure 8. Guarantee-transfer record. The record forces a substitution to identify the precise proof step it changes, the control that restores the promise and the negative case that could retire the claim. Original practitioner instrument. Fields are generic; examples in the paper are synthetic.

Record field	Required question	Acceptable evidence	Weak substitute to reject
Promise	What exact property is claimed?	Named termination, completeness, bound, feasibility or safety statement	“Reliable”, “intelligent” or “production ready”
Domain	Where does the claim apply?	Input constraints, state model, cost assumptions and exclusions	A broad use-case label
Carrier	What makes the claim follow?	Proof, sound bound, shield, validator, exhaustive fallback or postcondition	Model confidence or prompt instruction
Authority	What may the learned component change?	Explicit verbs and reachable effects	“Assists the workflow”
Negative case	Which counterexample tests the invariant?	Executable fixture, fault injection or formal countermodel	More random happy-path samples
Runtime response	What happens when evidence is absent?	Fallback, abstention, stop, review, reconcile or compensate	Blind retry or fluent explanation
Expiry	What change invalidates the evidence?	Model, schema, population, policy, state or fallback change trigger	Annual review regardless of change

Guarantees can weaken without becoming meaningless

The transfer decision is not always “preserved” or “lost”. A universal guarantee can become a bounded approximation guarantee, a high-probability statement or a distribution-specific service claim. That weakening can be rational. A route planner might trade exact optimality for a proven maximum detour. A controller might guarantee constraint satisfaction while offering only empirical progress towards the goal. A queue might guarantee deadlines for a protected class while measuring ranking quality for the remainder.

The wording must track the evidence. A worst-case bound applies to every input in its domain. A probabilistic bound quantifies randomness under stated assumptions. A confidence interval estimates an unknown population quantity from sampled data. Calibration asks whether events assigned probability p occur about that often on a defined population. These are not stylistic variants of “the model is usually right”. They answer different questions and fail under different changes.

Randomised algorithms are a useful counterexample to the idea that only deterministic procedures can be rigorous. Their guarantees may be probabilistic because the randomness is represented in the analysis. A learned procedure can also support a probabilistic claim when the data-generating assumptions, sampling process, error event and confidence statement are explicit. What it cannot do is inherit a worst-case promise from the algorithm it imitated while reporting only average test performance.

Selective operation is often the honest middle ground. Let the learned component act only on cases for which the required evidence is present, the action is reversible and an observed risk bound is acceptable. Route the rest to exact fallback or review. Coverage and risk must then be reported together. A system handling 70 per cent of cases at a tightly measured error rate is not equivalent to one handling 99 per cent at a looser rate, even when their aggregate accuracy happens to match.

Composition creates obligations that no component owns alone

Component guarantees do not simply add. An admissible heuristic paired with an incorrect stopping rule can still yield a wrong result. A verified network called on an out-of-domain input has crossed its proof boundary. A shield that constrains individual actions may not prevent an unsafe cumulative sequence if the specification omits history. An exact planner can generate a valid plan that an unreliable executor only partially performs.

The composed claim therefore needs interface invariants. The state supplied to a learned component must mean what its evidence assumes. The value returned must be interpreted according to its contract. The consumer must not promote a ranking score into a bound or a probability into authority. State versions, units, missing-value semantics and terminal conditions are part of the proof boundary, even when they look like ordinary integration details.

Independence matters too. Asking a second model from the same family to agree with the first does not necessarily create a separate guarantee carrier. Both may share training data, representation limits and the same misleading context. A deterministic postcondition read from the authoritative system is stronger evidence of an effect than a model's fluent confirmation. A sound constraint solver is stronger evidence of feasibility than another generated explanation. The relevant question is not how many components agree, but whether the checking mechanism can fail for the same reason.

This is why learned critics and self-consistency are valuable but limited. They can detect some errors, improve average quality and surface uncertainty. Unless their coverage is itself established for the target property, they are additional empirical procedures. They should not be drawn in an architecture diagram as if the word “verifier” converted agreement into proof.

Guarantee debt

When a team replaces a proof-bearing step, notices that the old invariant no longer follows, but continues to describe the system with the old promise, it incurs guarantee debt. The debt is not model error. It is the gap between the public or operational claim and the evidence the new architecture can actually produce.

Four features make that debt dangerous: the learned component has broad authority, failure is difficult to observe, consequences are hard to reverse, and the affected population can change faster than evaluation. A low-authority ranker with rapid human correction may carry little debt. A model that silently prunes rare medical, financial or safety cases can carry substantial debt even with an excellent average score.

The transfer record turns the debt into a decision. The owner may restore the invariant, weaken the claim, narrow the domain or explicitly accept an empirical operating risk with monitoring and rollback. Any of those can be legitimate. Leaving the original guarantee in presentations while its carrier has disappeared is not.

Audit the design twice: remove the model and list the promises the remaining system can still demonstrate; then let the model produce its worst plausible in-domain output and trace what prevents acceptance. The first pass locates capability. The second tests whether assurance is independent. Without clear answers, the architecture relies on reputation, not a transfer argument.

Three release patterns

Guidance with exact fallback is appropriate when a learned score can save work but all candidates can still be retained or recovered. Measure efficiency and timeout behaviour, while the original exact rule remains the carrier of correctness.

Bounded learned estimation is appropriate when a model predicts a quantity used by a proof-bearing procedure and an independent envelope can constrain the estimate. Test the envelope itself, boundary cases and the cost of conservative fallback.

Direct learned policy with containment is appropriate when the task is too open for a useful exact procedure. Do not pretend that a universal task guarantee remains. Instead constrain reachable actions, make uncertainty observable, preserve stop and escalation states, monitor outcomes and keep irreversible effects behind independent authority.

Compact glossary

Algorithm: an explicit procedure over represented states. Any guarantee remains conditional on its specification and assumptions.

Heuristic: information used to guide or approximate a decision without necessarily carrying the final proof.

Learned procedure: a runtime transformation or policy whose parameters were inferred from data or interaction.

Invariant: a property maintained through relevant transitions and used to establish a later claim.

Admissible heuristic: in shortest-path search, an estimate that does not overstate the true remaining cost under the stated model.

Verifier or shield: an independently specified mechanism that checks or restricts proposed behaviour.

Completeness: the property that a procedure will find a solution when one exists in its formal search domain.

Distribution shift: a change between the cases supporting empirical evidence and those encountered in use.

The evidence conversationChart · sequence

sequenceDiagram
  participant Q as Question
  participant M as Mechanism
  participant E as Evidence
  participant D as Decision
  Q->>M: Where the promise lives
  M->>E: The carrier, not the label
  E-->>M: compare rival explanations
  E->>D: Choose the carrier before the learner
  D-->>Q: revise scope or act

Question, mechanism, evidence and decision exchange the burdens developed in Algorithms, Heuristics and Learned Procedures. Reading use: follow the relation, then test it against the surrounding evidence and limits.

Choose the carrier before the learner

An algorithm is not trustworthy because it is written by hand, and a learned procedure is not untrustworthy because it was fitted from data. The meaningful distinction is evidential. An explicit procedure can expose invariants that support a conditional proof. A learned procedure can discover guidance that no concise rule captures. The architecture should let each do the work for which its evidence is suited.

The decisive design move is to separate guidance from exclusion, and exclusion from commitment. A learned score that merely changes order can improve efficiency while exactness remains elsewhere. The same score used to prune must justify why discarded possibilities cannot matter. Used as a policy, it needs containment, monitoring and recovery rather than borrowed language about the algorithm it once imitated.

So write the promise first. Name its domain. Point to the proof, bound, shield, verifier or fallback that carries it. Then give the learner as much authority as the evidence supports. When explicit procedure becomes inferred policy, the guarantee does not travel automatically. It must be transferred deliberately, rebuilt elsewhere or honestly withdrawn.

References

Dijkstra, E. W. (1959). A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1, 269-271.
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
Pohl, I. (1970). Heuristic Search Viewed as Path Finding in a Graph. Artificial Intelligence, 1(3-4), 193-204.
Land, A. H., & Doig, A. G. (1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28(3), 497-520.
Ross, S., Gordon, G. J., & Bagnell, J. A. (2011). A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning. Proceedings of Machine Learning Research, 15, 627-635.
Vinyals, O., Fortunato, M., & Jaitly, N. (2015). Pointer Networks. Advances in Neural Information Processing Systems, 28.
Silver, D. et al. (2016). Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, 529, 484-489.
Alshiekh, M., Bloem, R., Ehlers, R., Könighofer, B., Niekum, S., & Topcu, U. (2018). Safe Reinforcement Learning via Shielding. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1).
Katz, G., Barrett, C., Dill, D., Julian, K., & Kochenderfer, M. (2017). Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. Computer Aided Verification, 97-117.
Gasse, M., Chételat, D., Ferroni, N., Charlin, L., & Lodi, A. (2019). Exact Combinatorial Optimization with Graph Convolutional Neural Networks. Advances in Neural Information Processing Systems, 32.
Yonetani, R., Taniai, T., Barekatain, M., Nishimura, M., & Kanezaki, A. (2021). Path Planning using Neural A* Search. Proceedings of Machine Learning Research, 139, 12029-12039.
Veličković, P. et al. (2022). The CLRS Algorithmic Reasoning Benchmark. Proceedings of Machine Learning Research, 162, 22084-22102.
Bevilacqua, B. et al. (2023). Neural Algorithmic Reasoning with Causal Regularisation. arXiv:2302.10258.
Rodionov, G., & Prokhorenkova, L. (2023). Neural Algorithmic Reasoning Without Intermediate Supervision. Advances in Neural Information Processing Systems, 36.
Rodionov, G., & Prokhorenkova, L. (2024). Discrete Neural Algorithmic Reasoning. arXiv:2402.11628.
Saldyt, L., & Kambhampati, S. (2025). Mind The Gap: Quantifying Mechanistic Gaps in Algorithmic Reasoning via Neural Compilation. arXiv:2505.18623.
Wittig, S. et al. (2026). Which Algorithms Can Graph Neural Networks Learn?. arXiv:2602.13106.
Futuhi, E., & Sturtevant, N. R. (2026). Learning Admissible Heuristics for A*: Theory and Practice. Recent primary research on constrained heuristic learning, near-admissibility and generalisation bounds; cited without treating empirical near-admissibility as a universal runtime guarantee.