The AI doesn't build relations doing quest, they obviously must start with high relations with notables or accrue is very quickly from security - so they essentially don't need relation, as I said.
0 relations gives you +1 slot, same faction gives you +1 slot. Owned fief gives another +1 (or did) have to check when I get home.
But like I said, two of those cheats (spawn troops and free +1 slot) are really easy to disable and test. Just try it and see what happens for yourself. Spoiler: they'll still show up repeatedly with new armies.
Because they have a lot more parties than the ones in their armies. And those parties are lead by more nobles than just those on the map. And those nobles have a lot more troops than the ones in field.
Seriously. The kingdom strength number shows how many they have and 15,000 is completely normal, meaning you could kill ten armies in a row and they'd still have enough for an eleventh. And a twelfth. And a thirteenth. And even if you kill 15,000 they will still have more because notables constantly produce more troops, who get recruited and now notables no longer have to level-up the recruits*, they just randomly produce high-tier ones, so now the AI armies have fewer recruits. And players asked for fewer recruits/more nobles in enemy armies, it wasn't just TW going off on their own.
Does it make the game grindy? Yeah, it does. You have to basically kill 150-200 per day just to overcome a mid game kingdom's natural spawn rate through its notables. That's a small army every three or four days, or a big one every eight or nine. To actually drain their manpower you need the AI to help. But none of that is changed if you take away free spawn troops and it barely changes in the case of removing their +1 recruiting slot, because they still have the natural +3 from same faction and owned fief and indifferent relations bonuses.
Its not way less that 20% its between 15-20% I think depending on the NPC. I've seen the rulers comeback with 40 guys who usually have 200 in their army. Unless that's just for rulers.
If they own even one settlement there is no way to see what they spawn with. Their party will spawn inside after the noble comes off cooldown and the troops are drawn from the garrison without any indication on the map like with recruiting from notables.
Rulers weren't an exception the last time I looked, but Mexico mentioned he wanted their parties to be scarier in the map.
*Before I'm misunderstood: the troops in parties, garrisons, etc. still need to be leveled up. That part hasn't changed. What has changed is that available men to be recruited (i.e. still in slot) were previously leveled-up over time, with some influence from the notable's power. Basically, every notable would produce a full rack of the lowest-tier troops, going right from left. After their rack filled, the right-most troop would gain a tier, then the one next to him, then the next, and the next after until the notable's entire rack was up-tiered and the process repeated itself. But in a live game, there would always be nobles coming around taking the first two slots, leading them to be almost always recruits, while the right-most slots (hardest to get) were generally tier 4 and the middle were -- well, somewhere between those two.