PACE: Partial-state Amortized Constraint Editing for Neural Combinatorial Optimization

We propose PACE, Partial-state Amortized Constraint Editing, which treats task-native feasible partial states as the common semantic object for neural combinatorial optimization, unifying edit learning, constraint-preserving editing, anytime closure, and test-time scaling across routing and graph combinatorial optimization. Existing neural combinatorial optimization methods expose complementary strengths: constructive and adaptive expansion solvers keep meaningful partial solutions but couple them to serial or method-specific growth, while global prediction, diffusion, masked reconstruction, and complete-solution refinement provide scalable guidance yet often refine heatmaps, noisy solutions, reconstruction targets, or perturbed full outputs. These semantics make learning, search, and test-time scaling act on the same state object. PACE learns amortized constraint editing by ranking candidate edits conditioned on the current feasible partial state; a constraint-preserving transition $\Gamma_I$ commits only edits that preserve legal continuation and extendability; and task-native closure $\mathrm{Comp}_I$ maps any extendable intermediate feasible partial state to a task-terminal feasible output. Budgeted refinement then spends extra inference-time compute through deeper edit steps, additional refinement rounds, or broader candidate sets along the same trajectory. We instantiate these semantics across TSP, ATSP, CVRP, MIS, MVC, MCL, and MCut, covering edge-oriented routing and node-oriented graph combinatorial optimization. Theoretical guarantees are structural rather than optimality claims, covering task-wise soundness, constructive completion, state-space closure in the extendable subset, terminal feasible completion at any editing depth, and elite-pool nondegradation. Empirically, PACE is competitive and budget-controllable, including ATSP-500 at 0.247\% Drop, MIS RB-[800-1200] at 2.00\%, and MVC at 0.07\%.