Elamur Research⌕
☰
home / papers / 2024 / Forest-of-Thought: Scaling Test-Time Compute for Enhancing LLM Reasoning

Forest-of-Thought: Scaling Test-Time Compute for Enhancing LLM Reasoning

Paper · 2024 · Zhenni Bi, Kai Han, Chuanjian Liu et al.

Summary

Prompting schemes such as Chain-of-Thought and Tree-of-Thought usually follow one reasoning attempt to its end. If that attempt goes wrong, the model rarely goes back to try other routes. The authors, from Huawei Noah's Ark Lab, propose Forest-of-Thought (FoT), a way to spend more inference-time compute without any training. FoT runs several independent reasoning trees, such as ToT or MCTSr, on an enhanced version of the input. Inside each tree, only the highest-scoring nodes are expanded. A tree that stops producing valid steps is pruned early, so only "activated" trees contribute answers. A dynamic self-correction step uses both immediate fixes and past errors to repair answers. A consensus-guided decision rule merges the answers and continues reasoning only when needed. The method is tested on Game of 24, GSM8K, MATH500 and AIME 2024. Accuracy rises steadily as more subtrees are activated. FoT lets mid-sized open models match or beat much stronger systems. This makes it a training-free option for improving mathematical reasoning.

Key points

  • On Game of 24, FoT with 8 activated subtrees solves 96.84% of puzzles. The baselines score lower: IO 10.22%, CoT 4.38%, ToT (b=5) 74.00%, BoT 82.40% and XoT 85.40%.
  • With Qwen2.5-Math-7B-Instruct as the base, FoT (n=8) raises scores as follows:
    • GSM8K: from 88.48 to 96.89
    • MATH500: from 82.60 to 86.20
    • AIME 2024: from 6.00 to 46.67
  • With QwQ-32B-preview as the base, FoT (n=4) reaches 97.33 on GSM8K, 91.20 on MATH500 and 53.33 on AIME 2024. These scores are above GPT-4o (92.90 / 76.60 / 9.30) and roughly equal to or slightly above rStar-Math with 64 samples (95.20 / 90.00 / 53.30).
  • On GSM8K, error rates fall as more subtrees are activated for Llama, Mistral and GLM models. This fits a test-time compute scaling trend.
  • FoT needs no backpropagation or fine-tuning. Code is announced at github.com/iamhankai/Forest-of-Thought.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢Huawei TechnologiesShenzhen · China75 works · 12,975 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputer Vision and Pattern Recognition · 2,869 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,320 worksReasoning · 1,426 works

Cite

Cite as Zhenni Bi, Kai Han, Chuanjian Liu, Yehui Tang and Yunhe Wang. 2024. Forest-of-Thought: Scaling Test-Time Compute for Enhancing LLM Reasoning. arXiv:2412.09078.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2412.09078 · arXiv 2412.09078

@misc{bi2024forest,
  title = {{Forest-of-Thought: Scaling Test-Time Compute for Enhancing LLM Reasoning}},
  author = {Zhenni Bi, Kai Han, Chuanjian Liu, Yehui Tang and Yunhe Wang},
  year = {2024},
  doi = {10.48550/arxiv.2412.09078},
  eprint = {2412.09078},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2412.09078}
}

References

28 references, 14 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
  2. Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021b.
  3. AI-MO. Aime 2024. Ding, R., Zhang, C., Wang, L., Xu, Y., Ma, M., Zhang, https://huggingface.co/datasets/AI-MO/aimo-validation-aime, ↗
  4. W., Qin, S., Rajmohan, S., Lin, Q., and Zhang, 2024. Accessed: 2025-01-29. D. Everything of thoughts: Defying the law of Amabile, T. M. A Theoretical Framework, pp. 65–96. penrose triangle for thought generation, 2024. URL Springer New York, New York, NY, 1983. ISBN 978-1-https://arxiv.org/abs/2311.… find
  5. Besta, M., Blach, N., Kubicek, A., Gerstenberger, Flower, L. A cognitive process theory of writing. Compo-R., Podstawski, M., Gianinazzi, L., Gajda, J., sition and communication, 1981. Lehmann, T., Niewiadomski, H., Nyczyk, P., and GLM, T., :, Zeng, A., Xu, B., Wang, B., Zhang, C., Yin, Hoefler, T.… find
  6. Guan, X., Zhang, L. L., Liu, Y., Shang, N., Sun, Y., Zhu, Y., Yang, F., and Yang, M. rstar-math: Small llms can master math reasoning with self-evolved deep thinking, 2025. URL https://arxiv.org/abs/2501.04519. ↗
  7. Morris, J. X., Singh, C., Rush, A. M., Gao, J., and Deng, Y. Tree prompting: Efficient task adaptation without fine-tuning. 2023. URL https://arxiv.org/abs/2310.14034. ↗
  8. Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. Measuring mathematical problem solving with the math dataset. 2021a. URL https://arxiv.org/abs/2103.03874. ↗
  9. Nguyen, H. H., Liu, Y., Zhang, C., Zhang, T., and Yu, P. S. Cof-cot: Enhancing large language models with coarse-to-fine chain-of-thought prompting for multi-domain nlu tasks. 2023. URL https://arxiv.org/abs/2310.14623. ↗
  10. Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. Measuring mathematical problem solving with the math dataset, 2021b. URL https://arxiv.org/abs/2103.03874. ↗
  11. Ning, X., Lin, Z., Zhou, Z., Wang, Z., Yang, H., and Wang, Y. Skeleton-of-thought: Large language models can do parallel decoding. Proceedings ENLSP-III, 2023. find
  12. Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., de las Casas, D., Bressand, F., Lengyel, G., Lample, G., Saulnier, L., Lavaud, L. R., Lachaux, M.-A., Stock, P., Scao, T. L., Lavril, T., Wang, T., Lacroix, T., and Sayed, W. E. Mistral 7b. 2023. URL https://arxiv.org/abs/2310.… ↗
  13. Sel, B., Al-Tawaha, A., Khattar, V., Jia, R., and Jin, M. Algorithm of thoughts: Enhancing exploration of ideas in large language models. 2024. URL https://arxiv.org/abs/2308.10379. ↗
  14. OpenAI. Openai o1 system card. 2024. Accessed: 2024-9-12.
  15. Simon, H. A. The Architecture of Complexity, pp. 457–476. Springer US, Boston, MA, 1991. ISBN 978-1-4899-0718-9. doi: 10.1007/978-1-4899-0718-9 31. URL https://doi.org/10.1007/978-1-4899-0718-9_31. — [doi:10.1007/978-1-4899-0718-9](https://doi.org/10.1007/978-1-4899-0718-9) ↗
  16. Kahneman, D. Thinking, Fast and Slow. Harvard Library e-reader collection. Farrar, Straus and Giroux, 2011. ISBN 9780141033570. URL Snell, C., Lee, J., Xu, K., and Kumar, A. Scaling llm test-https://books.google.com.hk/books?id=AV9x8XakdV0C. time compute optimally can be more effective than scaling…
  17. Li, C., Liang, J., Zeng, A., Chen, X., Hausman, K., Sadigh, D., Levine, S., Fei-Fei, L., Xia, F., and Ichter, B. Chain of code: Reasoning with a language model-augmented code emulator. 2024. URL https://arxiv.org/abs/2312.04474. — [arXiv:2312.04474](https://arxiv.org/abs/2312.04474) ↗
  18. Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971, 2023.
  19. Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let’s verify step by step, 2023. URL https://arxiv.org/abs/2305.20050. ↗
  20. Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., Narang, S., Chowdhery, A., and Zhou, D. Self-consistency improves chain of thought reasoning in language models. 2023. URL https://arxiv.org/abs/2203.11171. ↗
  21. Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, L., Wiegreffe, S., Alon, U., Dziri, N., Prabhumoye, S., Yang, Y., Gupta, S., Majumder, B. P., Hermann, K., Welleck, S., Yazdanbakhsh, A., and Clark, P. Self-refine: Iterative refinement with self-feedback, 2023. URL https://arxiv.org/abs/2303.176… ↗
  22. Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35: 24824–24837, 2022.
  23. Yang, L., Yu, Z., Zhang, T., Cao, S., Xu, M., Zhang, W., Gonzalez, J. E., and Cui, B. Buffer of thoughts: Thought-augmented reasoning with large language models. 2024. URL https://arxiv.org/abs/2406.04271. ↗
  24. Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024. find
  25. Zhang, D., Huang, X., Zhou, D., Li, Y., and Ouyang, W. Accessing gpt-4 level mathematical olympiad solutions via monte carlo tree self-refine with llama-3 8b. 2024. URL https://arxiv.org/abs/2406.07394. ↗
  26. Zhang, Z., Zhang, A., Li, M., and Smola, A. Automatic chain of thought prompting in large language models. 2022. URL https://arxiv.org/abs/2210.03493. ↗
  27. Zhao, R., Li, X., Joty, S., Qin, C., and Bing, L. Verify-and-edit: A knowledge-enhanced chain-of-thought framework. 2023. URL https://arxiv.org/abs/2305.03268. ↗
  28. Zhou, D., Schärli, N., Hou, L., Wei, J., Scales, N., Wang, X., Schuurmans, D., Cui, C., Bousquet, O., Le, Q., and Chi, E. Least-to-most prompting enables complex reasoning in large language models. 2023. URL https://arxiv.org/abs/2205.10625. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bi-2024-forest-thought-scaling-test-time/