If the filter sponge is loosing the shape / collapsing on itself it would probably be time.
If the filter pad/floss stuff has no more shape, falling apart, then it is time.
What I normally do is either
squeeze the dirty one into the new one and add the new one to the filter and add the old one on the substrate below the intake and out flow. This positions it where it can still feed the BB. Leave it in the tank for a month.
Or the other way around, and leave the new filter media in the tank under the inflow for a month
add the new sponge to the filter, with the old one on top, which depends how much room you have.