Definition
Plain language
The property that adding one more item helps a lot when you have little and barely helps once you already have a lot — diminishing returns.
As stated in the literature
A set-function property where marginal gain decreases as the set grows; if an objective is submodular, a greedy algorithm is provably within about 63% of optimal (Nemhauser et al., 1978), which InfoTree exploits to make rollout selection near-optimal.
Also called: submodular
Why it matters: When a goal has this diminishing-returns shape, a simple greedy approach is provably close to the best possible, so you get good results without an expensive search.
For example, the first water station you place along a hiking trail helps thirsty hikers a lot, but the tenth one in the same area adds very little.
Heard on the show
“It's called submodularity.”Episode 162 — The Empty-Lake Proof: Why More Rollouts Stop Helping Reasoning Models