A finite constraint-satisfaction problem, or CSP, consists of variables, a finite domain for each variable and constraints that specify which joint assignments are allowed. In the binary case studied by Sabin and Freuder, each constraint relates a pair of variables. A timetable might give every class a time-slot domain and forbid two classes that share students from occupying the same slot. A map-colouring model gives every region a colour domain and requires adjacent regions to differ.

A solution assigns one value to every variable and satisfies every constraint. Backtracking search constructs a partial assignment. It chooses a variable, tries a value compatible with earlier choices and continues. If no value can extend the current prefix, it retracts a decision. The procedure is complete for a finite problem when it systematically explores all relevant alternatives, but completeness alone says nothing about how much of the search tree it will visit.

Inference attempts to remove alternatives that cannot participate in a solution, either before search or between decisions. The central local notion is arc consistency. A value a in the domain of X has support across a binary constraint with Y when at least one current value b of Y permits the pair (a,b). The directed arc X→Y is consistent when every current X-value has such support. A network is arc consistent when this holds in both directions for every constraint.

Arc consistency is sound pruning: deleting a value that lacks support cannot delete a complete solution. It is not complete reasoning: every value may have local support while no global assignment exists. An odd cycle of two-colour inequality constraints illustrates the gap. Each colour at each vertex is supported by the other colour at either neighbour, so arc consistency deletes nothing, although the triangle cannot be two-coloured.

For a directed arc X→Y, a revise operation considers every a in D(X). If no b in D(Y) satisfies the relation C(X,Y), it deletes a. A deletion can invalidate supports elsewhere, so an arc-consistency algorithm keeps revisiting affected arcs until nothing changes or some domain becomes empty. Empty means contradiction: no solution extends the current domains.

The asymmetry of a directed arc matters. Every value of X might have a witness in Y while a value of Y has none in X. A full binary network is arc consistent only after both directions have been checked. Different AC algorithms organise this bookkeeping differently, with different time and storage costs, but the semantic fixed point is the same when they enforce the same notion of consistency.

Consistency is relative to current domains. Assigning X=a can be represented by replacing D(X) with the singleton {a}. Values in neighbours then lose supports, which may cause more distant values to lose their only witnesses. Propagation is the repeated transmission of these consequences. Search and inference can therefore alternate: choose, propagate, detect failure or choose again.

It is tempting to reason monotonically from the set of values: fewer possibilities means fewer branches, therefore less search. That inference is valid only if the solver traverses comparable trees. A static ordering can preserve such a relationship. A dynamic heuristic that selects its next variable from current domain sizes may traverse a different tree after pruning. Soundness of the deletion and operational benefit of the deletion are separate propositions.

The experiment combines forward checking with dynamic domain-size ordering, often called fail first or minimum remaining values. At each node the heuristic prefers an unassigned variable with the fewest current values. The rationale is persuasive: a variable with few alternatives is more likely to expose a contradiction early, preventing a long excursion under a permissive choice.

Now apply arc consistency before the search. Some impossible values disappear. Every genuine solution remains. Yet the sizes and ties that the ordering heuristic observes have changed. A different variable may be chosen at the root; later deletions may produce another sequence of choices. The solver is no longer walking a trimmed version of the same tree. It is walking a different tree whose early decisions may be much less diagnostic.

The paper reports cases in which arc-consistency preprocessing made the subsequent ordered forward-checking search about an order of magnitude harder. Crucially, this comparison excludes the cost of preprocessing itself. The reversal is not merely that inference overhead exceeded saved search. Even if the preprocessing were free, the search phase alone could visit more work because the inference had disturbed its guide.

This is not a defect in arc consistency's logic. The removed values truly were impossible. It is a systems effect: a logically redundant value can still be operationally informative because its presence contributes to the domain-size pattern used for variable choice. Deleting it changes the measuring instrument. A heuristic consumes features of an intermediate representation, and sound simplification can alter those features.

When the authors use a fixed lexicographic ordering, the harmful effect disappears. That contrast is a causal clue. It isolates dynamic reordering as the route by which preprocessing changes the search, rather than suggesting that backtracking somehow benefits from trying impossible values.

After assigning X=a, forward checking visits every unassigned neighbour Y and removes Y-values inconsistent with a. If any Y-domain becomes empty, the branch fails immediately. Otherwise search chooses another variable. Forward checking therefore prevents a future variable from retaining a value that directly contradicts the current assignment.

What it does not normally do is propagate between two still-unassigned variables. Suppose assigning X shrinks Y; that shrinkage may destroy the last support for values of Z under a Y–Z constraint. Forward checking leaves Z unchanged until Y or Z is assigned. The doomed branch can survive for several decisions, accumulating nodes before the contradiction becomes explicit.

Its appeal is economy. A limited check touches a smaller part of the network and can be implemented with modest bookkeeping. If most branches are easy or if full propagation rarely discovers anything beyond the immediate neighbours, stronger inference is overhead. This gives the second conventional belief examined by Sabin and Freuder: forward checking was often treated as the sensible ceiling for propagation during search.

The paper does not caricature this belief. More inference has a real cost, measured in constraint checks and machine time. A stronger procedure can perform fewer search nodes and still lose overall. The empirical question is whether the additional propagation is Relevant with a capital R: does it reduce the combined cost of inference and search on the instances under study?

At a search node, MAC selects a variable and branches on a value. The assignment makes that domain a singleton; an AC procedure then propagates until a fixed point. If some domain empties, the branch fails without deeper guessing. Otherwise the reduced network becomes the input to the next variable-ordering decision.

This is more work per node than forward checking. It can inspect arcs that FC would postpone or never inspect. But a search node is not a fixed-price unit. If stronger propagation detects contradiction high in the tree, it can eliminate many descendant nodes, their repeated checks and their associated memory traffic. Paying more once may prevent paying a little many times.

Sabin and Freuder report that MAC is often very cost-effective, particularly on difficult problem regions. Their comparison helped shift MAC from a counterproposal to a standard baseline in finite-domain constraint programming. Later algorithms improved the arc-consistency engine, support reuse, variable ordering and branching, but retained the central architecture: systematic search interleaved with propagation to a strong local fixed point.

The result is empirical, not a dominance theorem. On easy instances, FC may reach a solution before MAC recovers its propagation cost. On loose networks, extended propagation may delete nothing. On constraints whose support test is expensive, a raw count of search nodes is especially misleading. The right metric is the resource one actually cares about: often elapsed time and memory: under comparable implementations.

The two contradictions point in opposite directions only superficially. Preprocessing is not always good because it may damage ordering. Stronger maintenance is not always bad because it may improve failure detection. In both cases, the paper rejects component-wise accounting. The effect depends on when information is produced, how it changes decisions and what future work it avoids or creates.

Imagine a fixed variable order and a fixed value order. Sound preprocessing removes branches that cannot reach solutions. Under suitable comparable implementations, the remaining search is naturally embedded in the original tree. Here the subset intuition has teeth: deletion cannot introduce a new assignment sequence before an old one.

Dynamic ordering breaks the coupling. The algorithm recomputes which variable looks most constrained after every deletion. Two runs may choose different roots, different children and different points of failure. Their trees are not related by simple inclusion. A smaller state description can trigger a much larger explored tree because the solver's policy is itself a function of that description.

The same pattern appears beyond CSPs. Compiler optimisation can disrupt a branch predictor; feature cleaning can shift a learned classifier; memoisation can alter cache locality; adding a proof lemma can mislead a branching score. In each case a transformation preserves the extensional answer while changing the intensional route used to obtain it. Correctness invariants do not determine performance invariants.

Calling impossible values “irrelevant” therefore hides two meanings. They are irrelevant to the solution set. They may remain relevant to the behaviour of an algorithm that counts domain elements. This does not recommend retaining junk. It recommends either choosing a heuristic robust to the transformation, preserving the useful signal in another feature, or evaluating the transformed pipeline rather than certifying each step separately.

The preprocessing result gains force from comparing FC with AC+FC while measuring the FC search separately from preprocessing. If only total time were reported, extra AC work would be an obvious alternative explanation. Showing that the later search itself grows rules out that simple account. Replacing dynamic domain ordering with lexicographic ordering then tests the proposed interaction.

The MAC comparison requires another discipline. A reduced node count is not enough because MAC spends more within each node. Constraint checks offer one implementation-sensitive proxy; elapsed time incorporates more overhead but depends on hardware and code quality. Reporting both helps distinguish an algorithmic change from a counting artefact, though neither automatically transfers to a modern solver.

Random CSP generators vary at least the number of variables, domain size, constraint density and tightness: the proportion of disallowed value pairs. Difficulty tends to concentrate around transition regions rather than rise monotonically with either density or tightness. An algorithm can dominate in the hard band and lose on easy under- or over-constrained cases. A mean across all regimes can conceal the very phenomenon under study.

Fairness also requires the same instances, stopping rules and solution objective. A satisfiable instance ends when one solver finds its first solution; an unsatisfiable instance requires exhaustive proof. Variable and value tie-breaking can produce large variations. Paired comparisons and explicit seeds make the result auditable.

The paper is historically compact, and later work has refined experimental standards. Its lasting strength is the intervention logic: isolate preprocessing cost, alter ordering, compare limited with full look-ahead, and attend to problem hardness. The conclusions are conditional claims about coupled mechanisms, not slogans that AC is harmful or MAC always wins.

An inference has acquisition cost: support tests, queue operations, memory allocation and restoration on backtracking. It may have storage cost if justifications, residues or reduced domains are retained. Its benefit is counterfactual: search nodes, constraint checks or expensive external operations that would have occurred without it.

Calling an inference relevant because it is logically connected to the query is too weak. Arc-consistency deletions are logically valid and closely related to satisfiability, yet their effect on this solver can be negative. Operational relevance asks whether the information arrives at a useful time, reaches the decision rule in a useful form and avoids enough downstream cost.

This yields a simple inequality rather than a universal maxim. Stronger propagation is worthwhile when its marginal cost is smaller than the expected future work it avoids, including effects on ordering. The expectation is instance- and state-dependent. A modern solver can therefore adapt propagation strength, learn constraint weights, reuse supports or trigger expensive consistency only when cheaper signals predict a benefit.

The accounting also disciplines claims about intelligence. A system that derives more consequences is not automatically more intelligent if those consequences degrade action. Conversely, a system that spends more on one decision can be globally more economical. Intelligent resource use involves selecting representations and computations according to their influence on the whole trajectory.

The first result does not show that preprocessing usually hurts. It shows that sound preprocessing can hurt a particular dynamically ordered search, refuting an “at worst no harm” guarantee. Many instances benefit, and stronger preprocessing can be essential in structured applications. The proper lesson is to test the composition and understand feature interactions.

The second result does not show that MAC always beats FC. Its extra propagation can be wasted on easy or weakly connected problems. Implementations matter: a poor AC engine can obscure the architecture's value, while support caching and efficient trailing can improve it. Constraint arity and global-constraint propagators also change the comparison beyond the paper's binary setting.

Nor does arc consistency establish satisfiability. It proves that each value has local witnesses, possibly different witnesses that cannot coexist. Search or stronger reasoning remains necessary. MAC is complete because it is embedded in systematic backtracking, not because arc consistency alone has become globally decisive.

Finally, performance on random binary CSPs does not determine performance on every planning, scheduling, configuration or verification task. Real instances have structure, repeated subproblems, asymmetric checking costs and modelling choices. Random ensembles help expose phase-dependent behaviour; they are experimental instruments, not miniature versions of all applications.

These boundaries make the paper more useful, not less. A carefully scoped counterexample teaches where a proof obligation lies. Anyone claiming a universally helpful simplification must specify whether the search policy is fixed. Anyone claiming stronger reasoning is too expensive must compare total execution rather than cost per inference step.

A CSP solver has operational uncertainty represented by domains. A branch commits to one possibility; propagation revises the remaining possibilities; a heuristic reads that revised state to choose the next commitment. This is a compact perception–action loop in which the “perception” is internally computed rather than sensed from an environment.

Agency enters in a thin functional sense. The solver selects actions under resource limits, detects conflict and revises course. MAC appears more deliberative because it derives more consequences before the next choice. Yet the paper shows why deliberation cannot be judged by volume. The useful question is whether inference improves the policy's trajectory relative to its cost.

The preprocessing reversal also resembles an information hazard at the algorithmic level. The new information is true: some values are impossible: but its presentation destroys a proxy used by the decision rule. This is not evidence that truth is harmful in general. It is evidence that agents depend on interfaces between representation and policy. A good representation for correctness may not be a good sufficient statistic for control.

Nothing here supports phenomenal consciousness. Domains are data structures; “knowing” that a value has no support means a deletion rule has fired; “choice” means a deterministic or tie-broken branch selection. There is no report, affect, unified point of view or evidence of subjective experience. The relevance to consciousness research is architectural and contrastive: sophisticated self-regulation can be specified without invoking experience.

The paper therefore sharpens rather than blurs categories. Computational agency can include counterfactual inference, adaptive ordering and systematic recovery. Intelligence can include spending resources now to avoid worse futures. Consciousness remains a further explanatory target, not a decorative synonym for any process that maintains an internal model.

Every variable has domain {0,1,2}. A deterministic generator adds binary constraints and always permits one planted assignment, so the displayed instance is satisfiable. Other pairs are permitted according to the chosen tightness. The three solvers use identical minimum-domain ordering and ascending value order. They differ only in propagation: FC checks the newly assigned variable against future neighbours; AC+FC first reaches an arc-consistent root and then uses FC; MAC restores arc consistency after every decision.

Nodes and support checks are separate. A method may visit fewer nodes while performing more checks. The reversal finder scans later seeds for a case where the search phase of AC+FC visits more nodes than FC. Finding one demonstrates possibility in this laboratory, not the frequency or magnitude reported by the 1994 paper.

The embedded review uses an exhaustive independent oracle on 240 deterministic CSPs. It requires all three solvers to agree with the oracle on satisfiability, checks every returned assignment directly against all relation tables and verifies every MAC propagation fixed point for arc consistency. These tests validate this implementation; they do not reproduce the historical benchmark suite.

Start with a semantic contract. State what a domain value means, what counts as support and whether constraints are binary, n-ary or global. Prove or test that pruning preserves solutions. Correctness comes before speed, but correctness does not settle speed.

Next expose the policy interface. Record which features guide variable and value selection. If preprocessing modifies those features, compare roots and early branch sequences rather than looking only at total nodes. Preserve transformed and original feature values long enough to test which channel causes a change.

Instrument multiple costs. Count nodes, constraint checks, deletions, queue revisions, peak memory and elapsed time. For application constraints, use weighted costs when some checks call databases, simulations or humans. Publish paired distributions rather than only means, because heavy-tailed search can make averages fragile.

Stratify instances. Separate satisfiable from unsatisfiable cases, easy regions from transition regions, sparse from dense networks and random from structured applications. A solver portfolio can exploit conditional strengths without pretending one configuration dominates everywhere.

Finally, treat propagation strength as a policy variable. MAC is a powerful default, not a commandment. Modern systems can switch propagators, reuse residues, learn conflict weights or schedule expensive reasoning when state features predict a return. The paper's “contradiction” becomes a positive design principle: information processing is valuable through its effect on action, not by its mere quantity.

Review one: scholarship. The reconstruction preserves both target beliefs, the binary-CSP scope, support-based arc consistency, FC's limited look-ahead, dynamic domain-size ordering, the finding that AC preprocessing can enlarge the later search independently of its own cost, the fixed-order contrast, the explanation through heuristic disruption, MAC's full maintenance after decisions, the hard-region advantage and the total-cost notion of Relevance. It avoids treating a counterexample as an average-case law or MAC as universally dominant.

Review two: teaching and execution. Ten paper-specific SVGs have unique titles, descriptions, captions and source scopes; motion stops under reduced-motion preference. Twelve worked examples and twelve causal probes attach interventions to load-bearing claims. The laboratory separates nodes from checks, uses identical generated instances and ordering rules, exposes deterministic seeds and distinguishes a local demonstration from historical replication.

Evidence and AI-telltale review. Historical claims are tied to the primary paper and publisher metadata. Later status claims are described as subsequent reception rather than retrojected into 1994. No fabricated benchmark table or false exact parameter is supplied. Metaphors such as “fail first”, “wisdom” and “knowing” are translated back into domain sizes, support tests and branching rules.

Accessibility and responsive review. Every visual has an accessible title and description; colour is redundant with text, layout and shape; controls have visible labels; changing output uses a live region; tables scroll on narrow screens; grids collapse at 900 and 600 pixels. The audit compares solver answers with brute force, validates returned assignments and independently checks MAC fixed points.

Sabin and Freuder's first reversal is more unsettling than an overhead story. An overhead story says good inference can cost too much. Their result says a free, correct simplification can still make later search worse because it changes what the heuristic sees. The intermediate representation is part of the algorithm's control surface.

The second reversal completes the argument. Expensive reasoning at every node can be economical when it stops bad histories from forming. Local expense and global thrift coexist. A rational architecture must price the future it prevents, not merely the present operation it performs.

Together the results reject an additive picture in which one ranks propagation, ordering and branching separately, then combines the best component from each column. Components reshape one another's inputs. Solver design is closer to experimental ecology: alter one organism and the behaviour of the whole system may change.

The paper also gives a disciplined interpretation of bounded rationality. The solver cannot derive every global consequence cheaply, so it alternates limited inference with reversible commitments. The right amount of thought is contingent on state, topology, implementation and downstream choice. “Think more” and “simplify first” are both incomplete policies.

For consciousness research, the lesson is methodological. Complex, history-sensitive, apparently counterintuitive behaviour can arise from explicit interactions among data structures and decision rules. Explaining those interactions is necessary before proposing an experiential cause. The gap between function and phenomenology remains open and visible.