Same problem, different answer: testing AI solvers for hidden inconsistencies

Renumber the connection points in an electricity grid, and its physical requirements stay the same. Rotate a map of cities, and the distances between them remain unchanged. Yet a learned optimization model can respond to these alternative representations with meaningfully different predictions.

In an arXiv preprint submitted on November 6, Vineet Jagadeesan Nair, Stephen Peng and Arun Ravindran investigate this dependence on representation. Their study spans electricity-grid optimization, delivery routing and the selection of nonadjacent vertices in a graph. Its central distinction is between consistency and correctness: a model can score well on average while responding inconsistently to equivalent inputs, and making it consistent does not necessarily make it accurate.

Testing relationships between answers

The approach is called metamorphic testing. Instead of checking only whether one answer matches a reference, it asks how answers should correspond when the input changes in a controlled way.

For a grid, changing bus identifiers should merely change the corresponding output labels. Reordering rows in a table of power lines should not affect predicted generator settings. For routing, rotating or reflecting the coordinate square preserves distances. Other tests alter structure while preserving an exact relationship between solutions, such as adding a disconnected graph whose contribution can be evaluated separately.

These comparisons need safeguards. The researchers first check whether a transformation meets its mathematical eligibility conditions. They solve both versions with reference software, compare objective values after any known offset, and independently check constraints. Predictions are then mapped back into matching coordinates before comparison.

Even that is not enough to demand identical answers. Floating-point arithmetic introduces small differences, and some problems have several equally good solutions. The study therefore applies numerical thresholds and, for routing and independent sets, compares route lengths or set sizes rather than insisting on identical choices.

Grid models reveal implementation dependencies

The grid audit examines models that predict solutions to alternating-current optimal power flow: choosing generator outputs while meeting electrical demand and operating constraints.

Across five grids, GridSFM-Open violated each of 13 tested relations on at least one grid. Twelve relations produced discrepancies more than twice the relevant threshold. LUMINA-2M violated nine. GENCO initially failed all 13 under the single-precision rule, but higher-precision checks identified only eight relations as retaining structural discrepancies rather than round-off effects.

Randomly initialized versions showed nearly the same failure patterns. That means training is not required for these failures to occur; choices in the architecture and implementation can already make predictions depend on representation.

The researchers traced particular discrepancies to concrete mechanisms. Some GridSFM features used bus indices to assign signs or select reference nodes. Other operations depended on table-row positions. LUMINA passed messages along branches only in their stored direction, so reversing an otherwise equivalent branch representation changed its computation.

Patches and standardized input ordering removed selected discrepancies with model weights held fixed. But consistency repairs faced a separate test: did accuracy and constraint satisfaction remain within a declared 10% deterioration margin? No tested grid intervention established that result across every evaluated grid and measure. Failure to establish the margin is not, by itself, proof of degradation; it leaves the quality claim unresolved.

Small average errors can hide frequent changes

For the traveling salesman problem, the single-pass POMO model showed increasing sensitivity to map orientation. Rotation or reflection changed predicted tour lengths beyond the threshold on 12.7% of tested draws with 20 cities and 89.5% with 100 cities. Meanwhile, mean gaps from the certified optimum were only 0.023% and 0.348%, respectively.

Evaluating all eight square rotations and reflections addressed orientation dependence, but did not eliminate failures involving added coincident cities or inserted midpoints. Those tests required additional certificates because rounding distances to integers can invalidate an apparently harmless geometric modification.

For maximum independent set—selecting the largest group of vertices with no edges between them—DIFUSCO violated the disconnected-union relation on 35.6% of 250 draws. The researchers linked this to normalizing scores across all vertices, allowing a disconnected addition to influence the original graph. Normalizing within each connected component removed the tested padding and union violations while leaving all 250 untransformed predictions unchanged.

What the audit does not establish

This preprint supplies counterexamples for selected models, not a failure-rate estimate for learned optimization generally. Its reference guarantees also differ: the traveling-salesman and independent-set solvers certify global optima, while the grid solver finds local solutions and the vehicle-routing reference is heuristic.

Numerical calibration is empirical, not a universal error bound. Multiple optima further complicate interpreting grid discrepancies as solution errors. The practical conclusion is narrower than declaring these models unreliable: report representation consistency alongside accuracy, optimality and feasibility, and evaluate a repair’s solution quality separately from its success at removing a discrepancy.