A Tree-of-Thoughts to Broaden Multi-step Reasoning across Languages

Leonardo Ranaldi, Giulia Pucci, Federico Ranaldi, Elena Sofia Ruzzetti, Fabio Massimo ZanzottoNAACL 2024 · DOI

TL;DR

This paper introduces Cross-lingual Tree-of-Thoughts (Cross-ToT), a novel prompting method that enables Large Language Models (LLMs) to perform multi-step reasoning in multiple languages simultaneously. By aligning reasoning paths across languages, Cross-ToT significantly improves performance on cross-lingual tasks, addressing the current English-centric limitation of LLM reasoning.

What Problem Does This Paper Address?

Chain-of-Thought (CoT) prompting has been a breakthrough in enhancing LLMs' reasoning capabilities, allowing them to break down complex problems into intermediate steps. However, this advancement is largely confined to English due to the imbalanced distribution of pre-training data. This linguistic barrier prevents LLMs from generalizing their impressive reasoning skills to other languages, creating a significant gap in their applicability. Existing methods to bridge this gap often involve multi-step prompting or translation, which can be cumbersome and less effective than a unified, zero-shot approach.

Methods

The core innovation is Cross-lingual Tree-of-Thoughts (Cross-ToT). Inspired by the Tree-of-Thoughts (ToT) approach, Cross-ToT elicits LLMs to generate multiple, parallel reasoning paths in different languages. These paths are not independent; they are designed to converge towards a single, final solution. The key idea is that by having these parallel "thoughts" interact and align, the model implicitly grasps the relationships between languages, leading to a more robust and self-consistent reasoning process. This is achieved through a single, unified prompt that encourages collaborative reasoning across languages.

Datasets

The authors evaluated their method on several multilingual benchmarks:

  • Multilingual Grade School Math (MGSM): An extension of GSM8K, translated into 11 languages, for arithmetic reasoning.
  • Cross-lingual Natural Language Inference (XNLI): A dataset for natural language inference across 15 languages.
  • Cross-lingual Paraphrase Adversaries Scrambling (PAWS-X): A dataset for paraphrase identification in seven languages.
  • Cross-lingual Choice of Plausible Alternatives (XCOPA): A dataset for causal commonsense reasoning across 11 languages.

Key Insights and Ideas

  • Cross-lingual reasoning is achievable with a unified prompt: Cross-ToT demonstrates that LLMs can perform complex multi-step reasoning across multiple languages simultaneously using a single prompt, bypassing the need for sequential translation or multi-stage prompting.
  • English as a "pivot" language can boost performance: The presence of an English reasoning path within the Cross-ToT framework significantly enhances performance, especially in high-resource contexts. This suggests that a strong, well-represented language can act as a beneficial anchor for cross-lingual reasoning.
  • Self-consistency is key: The "Tree-of-Thoughts" aspect, where multiple reasoning paths interact, promotes self-consistency. This allows for the correction of mistaken paths and ensures that the final answer is derived from a more robust and coherent reasoning process.
  • Language resource availability matters: While integrating more languages generally improves performance, the impact is more pronounced for high-resource languages. Low-resource languages may see less benefit or even a decrease in performance if not handled carefully.

Key Results

Cross-ToT consistently outperforms existing prompting methods across various tasks and languages. For instance, on the MGSM benchmark, Cross-ToT achieved an average accuracy of 80.6%, significantly higher than previous methods like Qin et al.'s Cross-CoT (76.6%) and Shi et al.'s Native-CoT (23.7%). Similar improvements were observed in language understanding tasks like XNLI and PAWS-X, and commonsense reasoning tasks like XCOPA. The introduction of English into the prompt also led to notable performance gains, as seen in Figure 2 and Table 4.

Limitations and Future Work

The authors acknowledge several limitations:

  • Limited language coverage: Tests were conducted on 16 languages, which is a small fraction of the world's languages. Future work should explore a broader range of languages and investigate how to construct effective prompts in diverse linguistic contexts.
  • Model dependency: The study primarily used GPT-3.5. Future research should assess the generality of Cross-ToT across different LLM architectures, including smaller models.
  • Cost constraints: The use of OpenAI's API and evaluation benchmarks imposed limitations on the scale of experiments.

Future work includes:

  • Incorporating smaller-scale language models (SLMs) and exploring techniques to align reasoning between LLMs and SLMs.
  • Enhancing cross-lingual reasoning capabilities by leveraging language structure and foundational NLP principles.
  • Investigating the impact of in-context learning (ICL) with Cross-ToT.
  • Exploring the performance of Cross-ToT on models with fewer parameters, as current results suggest potential challenges for these models.

Summary updated

BibTeX
@inproceedings{ranaldi2024tree,
  author = {Leonardo Ranaldi and Giulia Pucci and Federico Ranaldi and Elena Sofia Ruzzetti and Fabio Massimo Zanzotto},
  title = {{A Tree-of-Thoughts to Broaden Multi-step Reasoning across Languages}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2024},
  doi = {10.18653/v1/2024.findings-naacl.78},
}
Figure