Better than logarithmic returns to reasoning?

When does thinking harder (or longer) pay off?

Lots of phenomena turn out to have logarithmic returns: to get an improvement, you double effort or resources put in, but then to get the same improvement you have to double inputs again and again and so on. Equivalently, input costs are exponential in output quality¹. You can probably think of some examples.

I want to know: is ‘extra reasoning compute’ like this? (Or, under what conditions and by what means can you beat this?) I’m especially interested in this question as applied to deliberate exploration and experiment design.

Said another way, from a given decision-context, without making extra observations or gathering extra data, what are the optimal marginal returns to ‘thinking harder’² about what to do next?

Intuitively, if I have a second to come up with a plan, it might be weak, five minutes and it might be somewhat reasonable, a day and it’ll be better, a year (full time!) and I’ve reached very diminishing returns. Presumably a century in my ivory tower would be barely better. I’d usually do better trying to get more data.

Is this even a sensible question, or is ‘improvement in reasoning output’ far too vague to get traction here?

That’s the question; below some first thoughts toward an answer.

Simple model: repeated sampling/best of k

If you have a proposal generator, and you can choose between proposals, a simple approach to getting better generations is:

• sample a large number, k, of proposals

• (try to) evaluate and pick the best one

(This is actually the best strategy you could take if you can only add parallel compute, but there might be strictly better approaches if you can add serial³.)

Even assuming you can unerringly pick the best one, this strategy turns out to have logarithmically-bounded expected value for many underlying distributions of proposals⁴. In fact, for a normally-distributed proposal generator, you even get the slightly worse square root of logarithmic growth⁵.

You can in principle sidestep this if your proposal generator has sufficiently heavy-tailed proposal distribution, and you can reliably ex ante distinguish better from worse at the tails.

Another simple model: widely distributed ‘promise’ of lines of inquiry

Suppose you have various lines of inquiry to spend thinking time on. The best you can do is:

• start thinking on the most promising lines

• spend additional thinking on successively less promising lines

(This assumes you can somewhat reliably distinguish promise.)

If their ‘quality’ or ‘promise’ ranges over many orders of magnitude, then even if you get to accumulate insights additively⁶, you’ll actually make only bounded progress⁷ towards a theoretical ‘best possible’ - this is worse than logarithmic, though looks qualitatively similar over a substantial range of effort.

But why would the promise of lines of inquiry range over many orders of magnitude? We might say, ‘in practice, it often seems to’, and there are some theoretical reasons to expect this. You ‘pick low hanging fruit’ earliest, and face diminishing returns later. But to a large extent this model assumes the conclusion.

Other rougher gestures

Search depth

Often to find approximate solutions to problems, we might employ search over a tree-like structure. This emerges very naturally for planning over time, for example, where branching options (whether choice or chance) at each chosen time interval give rise to a tree of possible plans. (Compare Monte Carlo tree search.)

If gains are roughly uniform in search depth, this gives rise to logarithmic returns to further search. With excellent heuristics, you might be able to prune large fractions of the tree - this gives you a kinder exponent, but still an exponential space to search.

When (if at all) are gains over search depth dependably growing, rather than uniform at best? Alternatively, when can uniform (or better) gains be reliably achieved by expanding the search strictly less than exponentially?

Modelling chaos

Chaotic systems are characterised by sensitivity to initial conditions: dynamics where measurement or specification errors compound exponentially.

So, to forecast at a given precision and probabilistic resolution, it takes exponentially tighter initial specification precision to forecast marginal incremental time depth. (This is why in practice we only ever successfully forecast chaotic systems like weather at quite coarse precision or short horizon.)

Specification precision doesn’t exactly map to having extra compute, but it feels close. And marginal incremental time depth doesn’t necessarily correspond uniformly to ‘goodness of plan’.

Combinatorial search

If there’s some space of ingredients or components which can be combined for possible insight, the size of the search space is exponential⁸ in the number of components in a proposed combination. So if, among good plans at each scale, gains are proportional to the number of components in the plan (and there are similarly many good plans at each scale), you get logarithmic returns to searching longer.

Something similar applies if the design possibilities benefit from combining already-discovered structures in a hierarchy, for example if emergent features of subcomponents unlock new levels of effectiveness in a combined design (molecules, peptides, proteins, organelles, cells, ...).

But the assumption of roughly uniform gains over scales like this is carrying some weight here.

1. Notably this means that, unless you have an exponentially growing source of inputs to counteract it, there’s a practical upper limit to growing the output, because you can only double so many times. And with an exponentially-growing input, you can get a modest, linear improvement to output.

2. i.e. computing for longer or computing more parallel. Parallel can’t be better than serial in returns to total compute, so I’m mainly interested in the more generous serial case. For parallel, it’s easier to bound because the algorithm space is more constrained (’sample many in parallel, choose best’ is the best you can do asymptotically).

3. Intuitively you can ‘reason deeper’ with extra serial compute, which might look like recursing further down a search tree. You can also take proposals and try to refine or improve rather than just throwing them out and trying again from scratch.

4. Proof. Suppose the generator produces proposals with quality X. All we assume is that the distribution of X has a moment-generating function (this is not true of all distributions, in particular heavy-tailed distributions may not have a MGF). Denote k individual samples as X_i. Note first by Jensen’s inequality that:

\(e^{t \Bbb E \left[ \max_i X_i \right]} \le \Bbb E e^{t \left[ \max_i X_i \right]} = \Bbb E \max_i e^{t X_i} \)

i.e. the exponential of the expected maximum in question is bounded by the expected maximum of the exponentials. But a max of positive terms is bounded by the sum:

\(\Bbb E \max_i e^{t X_i} \le \Bbb E \sum_i e^{t X_i} = k \Bbb E e^{t X}\)

(writing X for a representative single sample.) But that’s just k times the moment-generating function (which we assumed exists). So for all positive t,

\(\Bbb E \left[ \max_i X_i \right] \le \frac {\ln k + \ln MGF(t)} t\)

So (fixing any t, or minimising over t) we see at most logarithmic growth in k.

5. Take the proof of the general case for an arbitrary distribution with a moment-generating function. Substitute the normal moment-generating function

\(MGF(t) = e^{\frac {\sigma^2 t^2} 2}\)

so that

\(\Bbb E \left[ \max_i X_i \right] \le \frac {\ln k} t + \frac {\sigma^2 t} 2\)

Minimising over (positive) t,

\( \Bbb E \left[ \max_i X_i \right] \le \sigma \sqrt {2 \ln k}\)

6. Perhaps the insights literally combine into an overall improved proposal, or perhaps less promising lines of inquiry provide fallback or robustness benefits in case the earlier ones fail in practice.

7. Qualities might be evenly spread over e.g 1, 1/10, 1/100, 1/1000, ... or more generally 1, 1/r, 1/r^2, .... Then the sum of your efforts is geometric, gradually approaching

\(\frac r {r-1}\)

8. Or more than exponential if the order or configuration matters!