The Amortization Ceiling: Why Learned Policies Do Not Replace Search in Constraint-Satisfaction Graph Generation

When a combinatorial objective is expensive to evaluate, a learned policy is meant to replace the evaluation: train once, decide cheaply thereafter. We study this amortization question in a controlled testbed: generate a graph whose five structural metrics (clustering, mean path length, modularity, spectral gap, degree assortativity) jointly fall within target tolerance bands, using degree-preserving edge swaps. True-metric evaluation is costly and the constraints are coupled. We benchmark eleven learned methods in thirteen configurations (imitation, value regression, policy gradients, generative flow networks, differentiable guidance, planning, a transplanted autoregressive architecture, and LLM-evolved heuristics), eleven under one unified protocol, against references at every level of the search hierarchy. Three findings follow. (1) No residual-free policy significantly beats random at any tolerance. A learner beats random only inside a narrow, protocol-sensitive niche (unimodal in tolerance tightness, concentrating on a locally computable binding constraint, and confined to small-to-mid sizes and the training family), and only for a learner that itself pays the per-decision measurement cost. (2) A ceiling: no learned method approaches true-metric greedy at any tightness or budget, and the best recovers under a quarter of the greedy-random gap on band average, at greedy's own cost. (3) The ceiling is structural: most candidate edits (96.7%) share their endpoint-degree view with another candidate, the failure localizes to assortativity, and the joint target space is thin, with a slice certified infeasible in advance by an unconditional spectral-modularity bound. A worst-case theorem shows that locally indistinguishable edits with provably different global effects exist, so bounded-radius scorers incur constant relative regret. Here, good moves are measured, not predicted; the certificate and the collision statistic are computable before any training. We distill the boundary into a testable binding-locality criterion: amortization can help to the extent that the binding constraint's increment is locally computable.