Anywhere between 2+ years before start date to less than a year before start date. Probably the majority are around 18 months prior, but you can't really predict that with any certainty, nor can you realistically expect people will stick to published timelines.
Geisinger is notorious for being one of the first best programs to interview. Invitations for Sept-October interviews went out in August (just about 2-years prior to fellowship start). Cockerell isn't too far behind. Most don't start interviewing until after the ASDP meeting. I got the sense a lot of programs didn't do any interviews and just took internals.