one, keeping ai and graphics on separate threads might be a good idea. I'm not sure if you were pondering whether ai would drag down the graphics in your post, but threading (and an internal gameclock) would definitely help alleviate that problem if you are worried about it. Mmm. On rereading I discovered your actual meaning. However, physics is likely to still be a bigger problem than ai in this case, especially if you're designing for a modern system - collisions for that many models would be intense, to say the least!
two: given that, I don't see any reason why you couldn't, given an appropriately capable adaptive representation, use a finite-step but potentially infinite-resolution tesselation to scale an ai.
How about using a group-based tesselation? You set up your units or NPCs or what have you so that they are associated with one or more groups (ie platoon/adventurer party, army/town, etc), and then tesselate your ai in one of two ways:
a) maximize the individual ai of each unit
(ie give each unit as much of the pie as you can, iff it needs some ai)
b) set minimal ai to each and then maximize as many brains as possible.
(ie give each unit very basic abilities but give most of the power to one or two units)
b is how I'm thinking of doing a 3d rts unit ai system, so each unit can follow the leader, and the leader can figure out the best overall actions just as a commander might assign orders to his troops or a navigator might pathfind through the wilderness.
As usual, a mixing and matching would likely work best, so that in, say, a CRPG you might try to give monster parties the b treatment and villagers the a treatment
Graphical techniques could probably be used in other ways:
'hierachical rendering' or 'rendering planes' (depending on your visualization) are already pretty much used as I understand it, so that you have the overlord ai playing the game and all the wee little ones doing the day to day work with maybe some in between stuff
'radiosity' could put ai power into the areas where it's most needed (if you're good at designing metrics of need) [and yes, I am aware of radiosity's actual origin]
As to the HOW:
Take the set-min-and-maximize-some-units, for example. You use a pared-down NN-trained FSM as your 'basic' ai. Then you begin to maximize: first, use your tesselation metric to evaluate how much you can do, then bring in as much of the partially trained NN as you can for each group leader. In the limit, you might have a fully-functional NN using GA training to generate and discard its next course of action. Of course, I'm thinking in terms of Messiah-type tesselation, where you use an insanely detailed model to begin with (effectively an infinite-detail representation) and tesselate it back down.
so you might have
tesselate_ai(group_leader, avail_power, maximal_ai)
as a minimalist treatment of the idea. Choose your favourite technique for implementing - GAs & NNs are probably best-suited, since they're inherently adaptive.
If you could get this to work then you could also tesselate away from ai-ai conflicts (iff the player's not around!) by using a prediction algorithm to find the battle outcome. You'd have to be AWFULLY good to get it just right, though. In fact, if you can do that, then you probably don't need to build an ai at all. But I could be wrong there.
Also, you might implement it so that groups themselves are amorphous - with less power available, the tesselation would maximize the size of the groups, and in the infinite limit, every group would have a size of 1!
just some thoughts.