Recourse on Borrowed Time: Counterfactuals that Survive a Model Update

Recourse has to respect what a person can actually change: age and sex are fixed, income moves only one way, employment type is categorical. The methods that honour such constraints exactly are mixed-integer programs, and we examine how their recommendations fare when the model changes. The leading exact method asks only that the decision flip, and it shows: under its shipped validity threshold a third of its counterfactuals sit exactly on the decision boundary, and only about half survive an ordinary retrain of the deployed classifier. That threshold is a parameter, and raising it repairs both, at the cost of a mixed-integer solve per individual. We introduce PACER, which obtains the same guarantee at gradient cost. It compiles a dataset's metadata into a symbolic rule base, projects every gradient step onto it, and optimises to a confidence margin the user sets. Plausibility comes from a sum–product network distilled into a differentiable surrogate: the exact circuit scores every result while the surrogate only supplies the search direction. PACER is the only gradient-based method in our study whose counterfactuals are fully actionable on all three benchmarks, and it keeps $0.96$–$1.00$ of them valid after a model update, at full coverage, in one to two seconds each. We report what this costs as well as what it buys, and release a harness that reproduces the exact baseline's published numbers cell for cell.