Language model search can spend less on predictable steps
Cette page n’a pas encore de traduction vérifiée. La version anglaise est affichée. Lire la version anglaise
En termes simples
Language models can explore several possible reasoning paths, but search often gives each step the same amount of effort. This paper introduces a training-free way to spend less effort when the next choices look similar.
The method estimates how different candidate steps are, keeps the strongest candidates when they look alike, and gives them fewer next steps to explore. In one math-reasoning test, it used fewer tokens and generated the search tree faster, with slightly lower accuracy than the comparison search.
La recherche
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.
Analyse
Détails
- Auteurs de l’article original
- Jianguo Huang, Zhiyi Lyu, Fuxiang Zhang, Yanchen Deng, Deheng Ye
- Soumis à arXiv
- Licence
- CC BY 4.0