Ankheg as a Dwarf Paladin mount

Question

When adjusting the HD of an Ankheg with the mount bonus; does it became a huge magical beast when it's HD count goes to 5 and above or is still just large?

Answer 1

No, it does not.

The larger sizes that creatures gain on advancement are only for when the DM “advances” the creature. Bonus HD, such as for being a paladin’s special mount or a druid’s animal companion, do not cause them. If you took the Leadership feat and had a creature as your cohort, which gained a share of XP and properly “leveled up,” then that might get those size increases, but even that’s uncertain.

Answer 2

Technically, bonus HD don't increase a creature's size…

The Hit Dice that the DM uses to advance a monster differ from bonus Hit Dice that a creature gains by virtue of being a paladin's special mount. The Paladin's Mount says that Bonus HD are

Extra eight-sided (d8) Hit Dice, each of which gains a Constitution modifier, as normal. Extra Hit Dice improve the mount’s base attack and base save bonuses. A special mount’s base attack bonus is equal to that of a cleric of a level equal to the mount’s HD. A mount has good Fortitude and Reflex saves (treat it as a character whose level equals the animal’s HD). The mount gains additional skill points or feats for bonus HD as normal for advancing a monster’s Hit Dice (see the Monster Manual). (Player's Handbook 45)

While the section Paladin's Mount directs the reader to the Monster Manual, there's no need to visit the Monster Manual at all as these rules for bonus HD tell the reader exactly the exceptions that are made to the normal rules for a creature that possesses these bonus HD.

(Keep in mind that the reader is directed to "see the Monster Manual" not for everything about advancing a creature by Hit Dice but, in context, for determining how "[t]he mount gains additional skill points or feats for bonus HD as normal for advancing a monster’s Hit Dice." The Player's Handbook isn't in a position to provide creatures' advancement schedules; it's up to the reader to determine, for example, when it gains 2 bonus HD how many skill points an ankheg (MM 14–15) gains and if it's eligible for a feat.)

In short, the creature that serves as the paladin's mount gains from its bonus HD additional maximum hp, an improved base attack bonus, improved saving throws, additional skill points, and additional feats. Nothing else. For example, the creature doesn't gain other benefits from gaining these bonus HD, like increased size (see Increasing Hit Dice on Monster Manual 291) or even the free ability score increase that's supposed to be gained at every 4 HD (see Ability Score Improvement on 291). Needless to say, this raises some unanswered questions—like Do bonus Hit Dice count toward a mount's poison or its other special abilities?—, but this is still pretty okay at least by 3.5 standards.

Because the term bonus HD is used in a nearly identical manner by the Druid's Animal Companion (PH 36), other sources tend to focus on that class feature, but its similarity to the bonus HD of a special mount can't be ignored: bonus HD do what they say they do. First, there's this Main FAQ exchange:

When you add Hit Dice to a druid’s (or ranger’s) animal companion as the master’s level goes up, does the animal get any bigger?…
An animal companion doesn’t get bigger when it adds extra Hit Dice for the master’s levels. The advancement entries for creatures, and the rules for advancing monsters, refer to unusually powerful specimens that are simply tougher (and perhaps bigger) than normal for their kinds. (14)

(I am unfamiliar with this ruling's provenance.) There's also Monster Manual author Skip Williams's Rules of the Game Web column "Animals (Part 4)" that on Bonus Hit Dice says

The animal companion gains extra Hit Dice as noted in the table on page 36 of the Player's Handbook. The companion gains the full benefit from increased Hit Dice, including increased base attack, base saves, skill points, and feats. The animal companion, however, does not increase in size (any more than you do when adding Hit Dice for your class levels).

Some folks—including me—sometimes have issues with both the Main FAQ and the Rules of the Game columns, but reading things this way provides a degree of consistency lacking in many of 3.5's rules. Finally, a reader may also want to see this question and this question.

So the rules point in this direction, the Main FAQ says what it says, one of the game's authors wants the rules to work this way, and this community largely agrees the rules work this way. Nonetheless, a reader may still disagree or a DM may want to experiment.

…And animal companions may be a problem if the DM rules that they do

In some campaigns it's probably perfectly okay if due to bonus HD a size increase can occur and—especially—ability score increases are gained. If the PCs are a cleric, a paladin, a rogue, and a sorcerer, they'll only see this issue arise with the paladin's special mount, and that's not a big deal. A paladin that stays paladin, in my experience, is the exception rather than the rule, and a paladin doesn't benefit from this ruling until level 5 then only in rare cases. (For instance, a typical paladin can't summon as a mount an ankheg.)

However, a DM may find it problematic to have ruled that bonus HD cause size increases if the campaign's important actors are druids or shamans (Oriental Adventures 22–4). A level 3 druid or shaman will master a Large wolf that possesses significant melee combat prowess. Already the game's most powerful class, druids are helped most by ruling that bonus HD trigger size increases, and—honestly—they don't need it. (At level 6, though, anyone that takes the feat Wild Cohort (Random Encounters Web column “Wild Life: Animal Companions for Any Character”) can realize a similar benefit under such a ruling; still, the druid's wolf remains forever tougher.) Compared to this ruling's impact on druids and shamans and others with animal companions, a paladin's special mount is only barely on the radar.

A tested compromise

In my campaigns, I use the house rule that bonus HD count toward ability score increases but follow the rule that says—or, at least, follow the rule that strongly implies—that bonus HD do not count toward size increases. Allowing ability score increases hasn't broken my campaigns, and it gives another layer of customization to the companion creature without me needing to worry about the overwhelming bonuses that come from increasing the companion creature's size.

---

Note: The premium edition Monster Manual (2012) stealth erratums without commentary the otyugh that's advanced to 15 Hit Dice (292) from its original Constitution score of 17 to 19, incorporating correctly the monster's ability score improvements due to its advanced Hit Dice. Good on it, I say. Also, this answer includes stat blocks for two ashworm mounts, the first without a size increase from bonus HD, the second with; the differences are mainly due to the level of customization allowed, but their different sizes are also significant.