On normal speed, I've seen the decay rate for my city-state relations vary from 1 to 2.5 (without the social policy modifier).
I think it is based on how nice I am to all the other city states, but haven't really figured out the exact formula. Is it based on their personality (Friendly, Hostile, Neutral, or Irrational)? Does pledging to protect them help?
Best Answer
The default rate is 1/turn, for hostile city states it is 1.5/turn.
It can be reduced by 25% with the patronage social policy and by 50% with the Greek unique ability.
Another factor is the social policy "United Front" from the Order tree, it increases the rate of decay for other players by 33% (thanks to Raven Dreamer).
If you conquer too many city states they will band together to defend against you (you'll get a notification about that). At this point, influence with non-hostile city states will decay 100% faster. Curiously, influence with hostile city states decays at the usual rate, so they are actually cheaper then. Beware that you don't need to attack many city states to trigger this event, 2 city states on normal size/Prince triggered it already. (Thanks to Sean)
I've checked some other factors using FireTuner, and neither map size, difficulty level nor current era seem to influence the decay rate.