How can I minimize the number of answers that are relevant to a machine learning model?
You don't need to re-train on the fly. What you're looking for is an embedded feature selection algorithm, and even more precisely, one that minimizes the number of responses required.

I think this might be one of the rare cases where genetic and evolutionary approaches are the obviously correct choice.

Genetic Programming is a technique for finding models that are simply computer programs. You generate a bunch of computer programs at random, and then breed the "better" ones together. Repeating this process over time leads to highly optimized programs.

A nice feature of GP is that it is extremely flexible when picking what to optimize. So instead of "better" meaning just "more accurate", "better" can mean the sum of accuracy and $\frac{1}{\#answers\_used}$. The algorithm works the same way, and, with carefully chosen rewards, you may be able to get the best of both worlds.

There are lots of variations on this. I would probably start with a simple toolkit like EJC, and standard, boring, genetic programming.

There are specialized techniques for things like your problem too, but you'll probably get 80% of the benefit without needing to pursue them.