So I continue to read that constructs can be reduced by one size category by reducing its HD by 1/2.
As far as I can see I don't see this anywhere in any bestiary, but it is alluded to with the idea that increasing a creature's HD by 1/2 increases its size category.
So, after scouring the bestiaries, where it supposedly was, I'm curious as to where to find this.
I believe you want the Bestiary page on Monster Advancement, specifically
Step 1: Plan the Monster
When advancing a monster by adding racial HD, you should start by deciding what you want the monster to become. In most cases, this means merely a tougher, stronger version of an existing monster. Note the desired CR of the new monster. This is also the point at which you should decide whether the creature is going to increase in size. As a general rule, creatures whose Hit Dice increase by 50% or more should also increase in size, but GMs should feel free to ignore this rule if warranted by the individual creature or situation.
I don't think there is anything on reducing HD with a consequent change in size, but if there were it would look like "As a general rule, creatures whose HD decrease by 1/3 or more should also decrease in size, but etc etc." (A 1/2 increase is cancelled by a 1/3 decrease.)
But constructs get their power chiefly from magic, not size. So if your goal is just to give your construct fewer HD, go ahead and leave the size the same.
If your goal is specifically to create a smaller construct, apply the Young template (same page) as many times as necessary, making the changes it calls for (which as it happens do not involve HD adjustments). Don't apply it so many times that a stat hits zero (other than Constitution, for constructs).
Young Creature (CR –1)
Creatures with the young template are immature specimens of the base creature. You can also use this simple template to easily create a smaller variant of a monster. This template cannot be applied to creatures that increase in power through aging or feeding (such as dragons or barghests) or creatures that are Fine-sized.
Hope this helps.