What about NOT (CategoryID IN %@)?
NOT (CategoryID IN %@)
How about using NONE?
NONE
[NSPredicate predicateWithFormat:@"NONE CategoryID IN %@", parentIDs];