Language model search can spend less on predictable steps

When a language model explores several reasoning paths, does every step need the same search effort? If candidate steps are already similar, expanding each one equally may spend computation on repeated possibilities.

The paper asks whether the search can estimate that similarity early and allocate fewer expansions where they are less likely to add variety.

UAA estimates how similar candidate reasoning steps are, then uses that uncertainty to prune candidates and limit their expansions.

The authors compared confidence-guided Beam Search with and without UAA on GSM8K, a test of mathematical problem solving, using Llama3.1-8B-Instruct. Accuracy counted exact matches after majority voting across reasoning paths.

With UAA, accuracy shifted from 89.17% to 88.00%, while average token use fell from 3.12k to 2.58k and whole-tree generation time from 53.32 to 34.23 seconds.

This comparison supports a bounded efficiency gain with a modest accuracy decrease in that setup.

A separate component comparison found that budgeting alone saved more tokens than pruning alone, while the combined setting used the fewest tokens among the tested conditions and kept accuracy close to the base result.

The analysis depends on assumptions, including that similarity between sibling actions predicts similarity among later continuations. It does not guarantee that pruning preserves a correct path, and it does not determine the method’s parameter settings.