Сначала надо определиться, а что-же вы понимаете под термином "сложность модели"?
Потому что "сложности" , действительно, бывают разные - как минимум "структурная" и "вычислительная". Но походе, вы их малость перепутали.
Возьмем ваш пример с Random Forest - увеличение количества сплитов не есть увеличение структурной сложности модели. Точно так-же, как и добавление новой переменной к нелинейной регрессионной модели заданного порядка не ведет к увеличению структурной сложности модели. А вот изменение - например - квадратичной модели на кубическую - ведет к изменению и структурной сложности и - как следствие - вычислительной.
Eсли это себе ясно представить, то становиться понятным, что введение нового признака в рамках одной модели - есть действие, результат которого влияет на "качество модели" (кстати, тоже требует определения, но предположим, что вы имеете ввиду "точность"). И структура тут вообще ни при чем. А изменение структуры модели с квадратичной на кубическую может привести к аналогичному увеличению точности модели даже без добавления новых переменных.
Простой
