A case can also be made that the Khitomer Accords never required Starfleet to reduce its forces at all.
Admiral Cartwright seemed to think they did.
CARTWRIGHT: I must protest. To offer the Klingons a safe haven within Federation space is suicide. Klingons would become the alien trash of the galaxy. And if we dismantle the fleet [emphasis mine], we'd be defenceless before an aggressive species with a foothold on our territory. The opportunity here is to bring them to their knees. Then we'll be in a far better position to dictate terms.
He's not the only one.
CHANG: Tell me, Captain Kirk, would you be willing to give up Starfleet?
SPOCK: I believe the Captain feels that Starfleet's mission has always been one of peace.
It's possible that Chang is referring to Kirk's imminent retirement, but then Spock's statement would be a complete non-sequiter.
The dialogue in the film strongly indicates that Star Fleet is at least considering a reduction of it's military assets, and not just starbases near the Klingon border. Now I freely admit there is no proof that they did do this, nor that any specific ship type was affected, but in the absence of conflicting evidence it is as good an explanation as any as to the lack of Constitutions in later years