A* Decoding for Machine Translation in LLM s - SRPOL Participation in WMT 2025 (2025)

Abstract: SRPOL team submission to WMT2025 introduces innovative approach using A* (A-star) algorithm of decoding in EuroLLM which gives diverse set of translation hypotheses. Subsequent reranking by Comet-QE and NLLB chooses the best of the diversed hypotheses which gives significant improvement of translation quality. The A* algorithm can be applied to decoding in any LLMs or other translation models. The experiment shows that by using free, openly accessible MT models you can achieve translation quality of the best online translators and LLMs using just a PC under your desk.

## introduction the final stage of inference in language models is decoding, which involves generating text based on calculated token probabilities. the most commonly used approach is autoregressive decoding, which generates tokens sequentially based on the source text and the text produced thus far. there are three primary strategies for autoregressive decoding: greedy, beam, and sampling. each of them has its flaws that a* resolves. ## decoding strategies greedy decoding selects the most probable token at each step, prioritizing speed and simplicity but often producing suboptimal results due to its limited exploration of alternative paths. sampling introduces randomness by selecting tokens based on their probability distribution, but the generated hypotheses can be overly random, resulting in translations that are not always optimal. beam search maintains multiple highprobability sequences (beams) simultaneously, enhancing output quality at a modest computational cost proportional to the beam width. this algorithm has been widely used in machine translation. recent advances in large language models (llms) have demonstrated their superiority over traditional encoder-decoder transformers @xcite . however, because of their primary purpose, llms are designed for rapid text generation and not for quality-oriented beam search. beam search in llms takes much more time than in classic transformers. for example, from our experiments, the beam search using vllm foot_0 on eurollm-9b @xcite takes about 30 seconds to decode with beam of width 10 for just one sentence. within the same time, we can use sampling to generate as many as 800 diverse hypotheses, which later assessed by qe give great improvement over greedy decoding or beam search. in the following, we propose a novel a* decoding algorithm for llms that combines the speed of beam search in classic transformers with the diversity of sampling. ## a* decoding let's consider decoding as the process of searching for the optimal path within a tree of all possible sentences generated by a model, where the chosen path represents the best translation of the source sentence. typically, there are no clear criteria for evaluating the quality of the generated sequence, so we must rely on proxy metrics derived from available data to assess its quality. one of the most effective and straightforward proxy metrics is the average probability of all tokens generated. this metric guides the algorithm to select the most probable token at each step of the output generation listing 1: python-like pseudocode of the a* decoding process. the simplest approach, known as greedy decoding, follows this principle. however, the results of greedy decoding may be suboptimal, as it overlooks many potential paths. in contrast, a* decoding allows the algorithm to explore beyond just the most probable next token, selecting tokens that offer the potential for discovering a more probable path by the end of the process. a similar concept has already been explored for statistical machine translation (smt) with long paragraphs @xcite . ## reranking following the generation of a set of translation hypotheses using the above described algorithm, we select the optimal hypothesis through a modified noisy channel model reranking approach, as described by @xcite . this reranking method enhances machine translation by reordering candidate translations during the decoding process. it integrates three components: a direct translation model, p (t |s), which predicts the target sentence t given the source sentence s; a channel model, p (s|t ), which assesses the likelihood of the source sentence given the target; and a language model, p (t ), which evaluates the fluency of the target sentence. the algorithm ranks candidates by computing a weighted combination of these probabilities, ensuring the selection of the most accurate and fluent translation. the algorithm scores candidates using a weighted combination of these probabilities: • s(t |s)=p (t |s)+λ 1 log p (s|t )+λ 2 log p (t ) where λ 1 and λ 2 are tunable weights. top candidates from the direct model are reranked based on this score, prioritizing translations that balance fidelity to the source and fluency in the target. for our submission in wmt2025 we applied the following scoring: • p (t |s) -calculated by weighted sum of probabilities of eurollm-9b, nllb-3.3 (team et al., 2022) combined with unbabel/comet wmt23cometkiwi-da-xl score. (rei et al., 2020) • p (s|t ) -calculated by nllb-3.3. ## conclusions and future work we introduced a novel, high-speed decoding algorithm (a*) that generates hypotheses significantly faster than beam search in large language models (llms). this algorithm is adaptable to any language model. the application of noisy channel reranking enhances the quality of diverse generated candidates by up to 0.2 points on the metricx-24 scale. further application of quality estimation (qe) reranking yields an additional improvement of another 0.2 to 0.3 points. a* decoding algorithm flexibility enables a balance between quality and speed. due to its efficiency and adaptability for any language model, this method has potential for numerous practical applications. the proposed solution demonstrates high quality of eurollm models. the final results reflect a significant improvement over eurollm-9b translations, with a reduction of up to 0.5 points in metricx-24 and an increase of 1.5 points in comet, achieving quality comparable to leading large language models, even for non-european languages. due to time constraints prior to the wmt25 workshop, we were unable to explore postprocessing techniques or context-aware multisentence decoding. the results submitted represent the unrefined output of the method described in this paper. a* decoding is a new idea, and we intend to refine it through further research. the results presented at wmt25 could be enhanced by leveraging other llms models as a base model, incorporating alternative quality estimation methods, or utilizing improved language models for reranking.