G2C-MT: Graph-Guided Context Selection for Document-Level Machine Translation

1 Introduction

High-quality document-level machine translation requires more than accurate sentence-level translation. It also needs the preservation of discourse phenomena, including lexical consistency and coreference resolution. Capturing long-range dependencies is therefore essential. Although recent advances in LLMs have shown success in handling long contexts [Liu et al., 2023; Chen et al., 2023; Gao et al., 2025], translating an entire document in a single pass often leads to issues such as sentence omissions or context dilution [Wang et al., 2025]. Moreover, exposing the model to the whole document context is inefficient, since the decoding cost of LLMs increases quadratically with the length of the input text. To address this issue, recent studies have employed retrievalbased and graph-based strategies to select prior translated paragraphs as context. Retrieval-based methods select historical translations according to semantic similarity to mitigate long-range dependencies [Wang et al., 2025]. However, these methods often fail to preserve explicit discourse structures, as they treat sentences as an unstructured collection. Similarly, existing graph-based methods depend on expensive edge relation definitions via LLM-based relation classification, and they are usually limited to selecting firstorder neighbors as historical context [Dutta et al., 2025; Pham et al., 2025]. This restriction prevents them from capturing deep and multi-hop discourse paths that define the global document structure.

∗Work done at Trip.com Group.

To overcome the above problem, we propose G2C-MT, a novel Graph-Guided Context for Machine Translation framework. Unlike retrieving sentences in isolation or relying on expensive graph construction processes, we model the document's discourse structure as a weighted directed acyclic graph (DAG) using a lightweight graph construction procedure. Specifically, each paragraph serves as a node, while edges denote the relationship between paragraphs. These relationships are quantified through a fusion score that derived from semantic similarity, sequential adjacency, and lexical overlap. This rich metric enables our framework to model the document as a graph with complex semantic relations rather than a simple linear chain.

Based on the constructed discourse graph, we apply a graph-driven method to select historical context for document-level translation dynamically. Specifically, when translating one target paragraph, we perform a backward and biased random walk starting from the corresponding node. Then, we identify a related context path, which is composed of previous paragraphs along with their translations. Unlike previous approaches that restrict context to immediate neighbors [Dutta et al., 2025], we guide the traversal with two complementary signals: local edge weights that encode semantic and lexical relevance, and a global signal that encourages traversing nodes that can generate longer and richer discourse chains. This design enables the model to select a single, structured context path that captures long-range, non-linear dependencies while remaining computationally efficient. The selected path is subsequently formatted into a discourse-aware prompt, enabling the model to exploit structured contextual information without processing the entire text. Moreover, since the traversal is probabilistic rather than deterministic, G2C-MT naturally supports multi-path sampling. By exploring multiple plausible discourse paths and aggregating the resulting translations, the framework can improve robustness in the presence of discourse-level ambiguity Our main contributions are as follows:

• We propose G2C-MT, a novel framework that models document context as a DAG, which can be built in a lightweight way. The graph can capture non-linear discourse dependencies effectively by modeling semantic and sequential correlations.
• We design a biased random walk mechanism that explicitly favors deeper context paths containing richer discourse information. Meanwhile, this probabilistic traversal can inherently support multi-path sampling, which can enhance robustness when the target paragraph involves discourse ambiguities.
• We conduct extensive experiments on various document-level translation benchmarks using LLMs of different scales. Our method outperforms strong baselines in both translation quality and coherence. Further analysis confirms the effectiveness of our graph-guided approach in capturing long-range dependencies.

2 Methodology

As illustrated in Figure 1 and Algorithm 1, the overall pipeline of our method can be divided into the following three stages:

1. Directed Discourse Graph Construction, which treats
2. each paragraph as a node and builds edges between paragraphs considering their multi-dimensional relevance.
3. Depth-Biased Context Sampling, a stochastic process to backtrack previously translated paragraphs and favor deeper context paths.
4. Path-Based Contextual Generation, which formats these context paths as the discourse information to prompt LLMs.

2.1 Directed Discourse Graph Construction

We model the source document D = {x1, x2, . . . , xN} as a weighted directed acyclic graph G = (V,E) firstly. The directed edge eij connects a target node vi to a previous node vj where j < i. Note that future translation yi (where i > j) are unavailable at step j, which is consistent with a human translating the document sentence by sentence. This definition of directed edges can also avoid the appearance of cyclic graphs, thus reducing complexity during traversing.

The weight wij of edge eij quantifies the relevance of paragraph xj to xi, calculated by a fusion of three discourserelated factors:

where α, β, and γ are coefficients, that sum to 1 to balance each factor. The specific definitions are as follows:

Semantic Relevance (Ssem). Global coherence relies on thematic consistency. We map each paragraph xi into a dense vector space via a pre-trained embedding model, denoted as hi. Then we compute the cosine similarity between these vectors. To prevent the graph from being too dense and introducing extra noise, we introduce a threshold τsem to truncate those edges with low correlation:

Sequential Adjacency (Sseq). The paragraph being translated is most closely related to its adjacent paragraphs. For example, in dialogue questionnaires or background introductions, adjacent contextual information is essential for reference resolution and for preserving logical coherence. Therefore, an adjacent edge is naturally introduced and assigned a fixed weight:

where I(·) is the indicator function. This guarantees that the local context is always considered a candidate.

Keyword Overlap (Skey). Semantic-based retrieval may miss some paragraphs that contain overlapping keywords but have low semantic similarity. These omissions may lead to inconsistency in the translation of terms, such as some proper nouns. We alleviate this problem by introducing Skey(i, j) of keyword overlap. Specifically, Ki denotes the set of top-K keywords in xi extracted via TF-IDF. Then we calculate the lexical score through the degree of keyword overlap:

where Kij = Ki ∩ Kj denotes the intersection of keywords, and ψ(t, x) represents the TF-IDF score of term t in paragraph x.

2.2 Depth-Biased Context Path Sampling

Once the discourse graph is built, we can backtrack the context path, starting from the given target paragraph xi. The backtrack strategy is also important. The most straightforward method is greedy search, which always selects the neighbor node with the highest weight. However, we find that this method sometimes terminates prematurely, or tends to select some nodes with certain types of edges ,such as repeatedly traversing edges with highly similar semantics, resulting in redundancy. To address this, we propose a sampling strategy to balance the edge relevance with the depth of context path to exploit global structural information.

Depth Heuristic

We introduce a concept of Depth Heuristic to estimate the informational richness of a context node. The Depth Heuristic ϕ(vj) represents the longest path backtracked from node vj. We argue that this backtrace depth represents how much historical translation context can be provided from a given node vi. Specifically, we can efficiently calculate ϕ(vj) via dynamic programming.

where ϕ(vstart) = 1 and B(vj) denotes the set of backward neighbors of vj .

Probabilistic Sampling

We apply the random walk mechanism for context selection to construct the path Pi = (vp1 , vp2 , . . . , vpL ), starting from the target vp1 = vi. Given the current node vcurr, the walker transitions to a previous node vnext, which is sampled from its neighborhood N(vcurr) defined above. The transition probability is as follows:

where Z is the partition function for normalization, and the term (ϕ(vnext) + 1)λ introduces a bias towards deeper structures. The hyperparameter λ ≥ 0 affects the strength of the deep bias. When λ = 0, the traversal process degrades to a standard random walk based on edge weights. Increasing λ will favor nodes with higher depth, which encourages the retrieval of long-range context.

2.3 Path-Based Contextual Generation

After completing the traversal, we can employ this sampled discourse path Pi for in-context learning by prompting LLMs. We reverse the path to restore the natural document order, and the final prompt Ii is constructed as follows:

where I denotes the translation instruction and ⊕ represents string concatenation. The pair (xk, yk) denotes the previous source paragraph and its translation corresponding to the node vk.

Multi-Path Sampling. Since our method is based on a random walk, each traversal can yield a different context path. We can sample K independent context paths {P (1) i , . . . ,P (K) i } for the target paragraph xi and then generate K candidate translations {y(1) i , . . . , y(K) i } accordingly. The final translation can be determined via a majority voting mechanism or by selecting the candidate with the lowest perplexity. In this paper, we cluster the K candidates via kmeans and select the representative candidate closest to the cluster centroid, which also proves to be a simple yet effective strategy.

Complexity Analysis. The time cost of graph construction primarily lies in embedding computation and TF-IDF keyword matching, leading to an overall time complexity of O(N 2 ). In practice, this is a one-time cost of <10 s per typical document (e.g., N ≈ 200 sentences on a single CPU), and each random walk completes in milliseconds. At inference time, G2C-MT requires exactly N LLM calls for N paragraphs-the same as the Window-Based baseline-since graph construction and the walk are pre-processing steps that do not invoke the LLM. Moreover, paragraphs below the similarity cutoff τsem are pruned, making the graph sparse.

3 Experiments

3.1 Experimental Setup

Datasets We evaluate our models on two standard benchmark test sets for DocMT. One of them is the SAP test set. Derived from the WAT 2020 and 2021 shared tasks, the set contains documents in the IT domain. For this test set, experiments are conducted on six translation directions: English↔Vietnamese, English↔Chinese, and English↔Indonesian. The sentences are organized

Algorithm 1 G2C-MT: Graph-Guided Contextual Translation

1: Input: Source Document D = {x1, . . . , xN}, LLMM 2: Output: Translated Document Y 3: Stage 1: Directed Discourse Graph Construction 4: Initialize G = (V,E) with nodes V = {1, . . . ,N} 5: for i = 1 to N do 6: for j = 1 to i - 1 do 7: Calc weight wij via semantic/seq/keyword scores 8: if wij > 0 then 9: Add edge (i, j) to E with weight wij 10: end if 11: end for 12: end for 13: Stage 2: Depth Heuristic Calculation 14: Compute ϕ(v) for all v ∈ V via dynamic programming 15: Stage 3: Path-Based Generation 16: Y ← ∅ 17: for i = 1 to N do 18: Sample path Pback from xi on G 19: Pctx ←Reverse(Pback \ {xi}) 20: Construct prompt Ii using Pctx and xi 21: yi ←M(Ii) 22: Append yi to Y 23: end for 24: Return Y

into separate documents, comprising approximately 2,000 sentences per direction. We also employ the tst2017 test set from the IWSLT 2017 translation task, comprising parallel TED talk documents. For this test set, we evaluate on the following eight translation directions: English↔Chinese, English↔French, English↔German, and English↔Japanese. Each translation direction consists of 10 to 12 sentence-aligned parallel documents, totaling approximately 1,500 sentences. In both benchmarks, each document paragraph consists of a single sentence; thus each graph node corresponds to one sentence.

Baselines We compare our model against the following baselines:

• Sentence: Each segment is translated independently any contextual information.
• Window-Based: A fixed-size sliding window of preceding sentences is used as context for translating the current sentence.
• Semantic-Based: Context paragraphs are selected based on embedding-based semantic similarity to the source paragraph.
• GRAFT [Dutta et al., 2025]: A multi-agent framework for DocMT. The framework first determines the most relevant context paragraph and then extracts key alignment information, such as pronouns, entities, and phrases, to aid document-level translation.
• DelTA [Wang et al., 2025]: An agentic framework aimed at translation consistency, featuring a multi-level memory architecture responsible for proper nouns, summaries, and variable-term contexts.

Settings For the backbone translation models, we utilize the APIs for Gemini-2.5-Flash-lite, DeepSeek-v3-0324, Qwen-2.5-72B-Instruct and Qwen3-235B-A22B-Instruct. To ensure reproducibility and deterministic outputs, we set the decoding temperature to 0 for all LLMs. For Graph Construction, we employ text-embedding-3-small provided by OpenAI for the semantic edge calculation (Ssem). The semantic similarity threshold τsem is empirically set to 0.6. The hyperparameters governing edge weight contribution are set to α = 0.2 (semantic), β = 0.3 (sequential), and γ = 0.5 (keyword), prioritizing lexical overlap and semantic coherence based on performance on the validation set. We verify term importance using TF-IDF, where each paragraph is treated as a document to compute the IDF within the scope of the source text. For the Biased RandomWalk, we set the path depth bias λ = 2.0 to encourage the selection of deeper context nodes. The maximum context path length (number of previous paragraphs included) is capped at L = 4 and stop the walk when the distance exceeds 100. For Window-Based and Semantic-Based baselines, we also set the context size to 4 paragraphs for a fair comparison.

3.2 Main Results

Performance on Technical Documentation

The evaluation results of all translation directions and backbones on SAP datasets are presented in Table 1. Firstly, we observe that the discourse context plays an important role in enhancing translation quality for DocMT. The Sentence baseline consistently underperformes all context-aware methods, trailing the simple Window-Based context by an average of 2-3 d-BLEU. Secondly, G2C-MT consistently achieves the highest d-BLEU scores across all translation directions and backbones, validating the robustness and generality of our graph-based approach regardless of the underlying model architecture. Thirdly, we observe that the Window-Based approach usually outperforms the Semantic-Based approach in this domain. This is intuitive for technical documentation, where logical progression (e.g., step 1, step 2) often implies that the adjacent sentences is the most relevant context. However, G2C-MT surpasses the Window-Based baseline by substantial margins-for instance, achieving a gain of +0.9 d-BLEU on EN→VI and +1.2 d-BLEU on VI→EN using Gemini-2.5-Flash-lite. This indicates that even in highly sequential documents, our Depth-Biased Sampling successfully retrieves necessary long-range constraints (such as terminology defined earlier in the document) that a fixed window misses, without introducing the noise associated with pure semantic retrieval. We also note the unstable performance of the Semantic-Based method, which sometimes even underperforms the Sentence baseline (EN→ ID). This suggests that treating context as a set of independent fragments may have the negative effect of disrupting the logical flow, leading to incoherent translations.

Performance on Narrative Discourse

Table 2 shows the results on the IWSLT 2017 benchmark using Qwen-2.5-72B-Instruct. This dataset is challenging for its loose conversational structure and long-range thematic dependencies. First, G2C-MT significantly outperforms the commercial and supervised baselines (NLLB-3.3B and Google Translate) across all directions, confirming the efficacy of LLMs for document-level translation when prompted with appropriate context. Second, our method proves superior to recent state-of-the-art agentic frameworks, which achieves comparable or higher d-BLEU scores (e.g., +1.4 over GRAFT in EN→ZH and +2.1 over DelTA in JP→EN). This result is significant given the computational efficiency of our method, as GRAFT and DelTA rely on computationally expensive, multi-step LLM calls to curate context or maintain memory modules.

Revisiting Context: Structure vs. Similarity. A notable pattern across both datasets is that the Semantic-Based baseline frequently fails to outperform the simple Window-Based approach, particularly on SAP (Table 1) and several IWSLT directions (e.g., EN→DE, JP→EN). This highlights a critical fact in document translation: local cohesion often outweighs global topical relevance. Pure semantic retrieval may break the linear narrative required for immediate syntactic dependency handling (e.g., pronoun resolution). G2C-MT avoids this trade-off by rooting retrieval in the discourse structure. By explicitly modeling sequential edges (Sseq) alongside semantic ones, our graph traversal prioritizes the immediate history while the depth-biased sampling allows the model to trace logical threads back to earlier context.

4 Analysis

In this section, we conduct a deeper analysis to investigate: (1) whether G2C-MT effectively handles discourse phenomena; (2) how the model exploits long-range dependencies; (3) the potential of multi-path sampling for robustness; and (4) the contribution of each component through ablation studies.

4.1 Evaluation of Discourse Metric

We adopt three specialized metrics to further investigate the discourse translation performance: BlonDe [Jiang et al., 2022], which explicitly tracks discourse phenomena such as entities, tenses, and pronouns; d-Prism [Thompson and Post, 2020; Vernikos et al., 2022], which measures semantic consistency using probability scores; and d-Comet [Rei et al.,

2022; Vernikos et al., 2022], which evaluates translation quality by considering the preceding context.

As shown in Table 3, G2C-MT achieves the best performance across all metrics. Window-Based achieves high BlonDe scores but obtains lower d-Prism scores than Semantic-Based. This indicates that the Window-Based method can capture local connections well, while the Semantic-Based method is good at finding relevant topics in long-range context. G2C-MT mitigates this trade-off by obtaining the highest BlonDe score (51.35) while maintaining strong semantic consistency through the combination of sequential and semantic edges.

4.2 Properites of Graph-Guided Context Selection

To better understand the efficacy of the proposed pipeline, we characterize the context selection behavior of G2C-MT compared to the Semantic-Based and Window-Based methods. We define the Context Distance ∆ = i - k and visualize the distribution of the selected nodes in Figure 2. We can observe two key properties of G2C-MT from the figure:

• Beyond Fixed Windows: The Window-Based method uses a fixed window size for context selection, where any dependency beyond the window size L is inaccessible. Our method G2C-MT can walk through semantic edges (Ssem) to skip over intermediate nodes. We can see that in Figure 2, G2C-MT effectively captures context at distances ∆ > 20.
• Beyond Isolated Retrieval (Coherence over Similarity): the Semantic-Based method retrieves context based on similarity scores, resulting in a bag of sentences {xk} without structural connections. However, the contexts selected by G2C-MT are the components of a connected path Pi. There exists a strong connection between nodes, since these edges of the path are weighted by discourse factors (Semantic, Sequential,

and Lexical). The explicitly modeled sequential edges (Sseq) act as glue, so the distribution of context distances in G2C-MT still peaks at small ∆ values.

4.3 Multi-Path Sampling for Robustness

In this section, we analyze the effect of multi-path sampling in G2C-MT. As introduced in Section 2.3, we first sample multiple context paths for the same target paragraph by random walks, and then select the final translation from multiple transslation candidates. We use the embedding model to vectorize each candidate translation, and then select the candidate closest to the cluster centroid as the final output. We experimented with sampling K = {1, 3, 5} paths on the difficult En→Vi subset, leaving larger K values for future work due to inference cost. As shown in Table 4, there is a consistent improvements in d-BLEU as we increase the number of sampled paths K. When K = 5, we achieve the best performance of 67.9 d-BLEU, which is +0.6 higher than the single-path baseline. This suggests that when translating ambiguous sentences, different context paths may provide complementary information, leading to more robust translations. Although this comes at the cost of increased inference latency, it offers a flexible trade-off for scenarios where quality is preferable.

4.4 Ablation Study

We conduct an ablation study on the SAP dataset to analyze the effect of different edge types and our proposed search strategies. The results are summarized in Table 5. From the table, we can observe that removing the Keyword Edge or the Biased RandomWalk results in the largest performance drops (-0.5). This result is intuitive, as terminological consistency is crucial in technical documents, especially for the SAP dataset which is in the IT domain. The Biased Random Walk also plays an important role in preventing the model from settling for shallow, uninformative context. Another noticeable observation is that the absence of the Sequential

Edge (Sseq) causes a larger performance drop (-0.4) compared to removing the Semantic Edge (Ssem) (-0.2). This indicates that local sequential order is crucial for immediate discourse coherence (e.g., pronoun resolution), while the less impact of semantic edges may imply that the Keyword Edge has already captured much of the necessary topical relevance.

4.5 Case Study

Table 6 demonstrates how G2C-MT handles long-range ambiguity. The source term posting is polysemous: it means publishing but refers to accounting entry in this specific ERP context. The defining context appears ten paragraphs earlier, causing the window-based baseline to default to the generic, incorrect translation. In contrast, G2C-MT successfully retrieves the prior paragraph guided by keyword overlap edges-and generates the correct domain terminology.

Table 6: A case study on long-range lexical disambiguation in SAP dataset.

5 RelatedWork

5.1 LLM-based Document-Level MT

LLMs have demonstrated strong in-context learning and long-context modeling capabilities, which makes them suitable for DocMT [Wang et al., 2023; Wu et al., 2024; Cui et al., 2024]. One recent line of work focuses on combining graph structures with LLMs to generate discourseaware translations since the graph can naturally model discourse dependencies. Dutta et al. proposed GRAFT, which uses an LLM agent to segment documents into discourse units, identify context dependencies, and form a directed acyclic discourse graph. TransGraph [Pham et al., 2025] similarly models inter-chunk discourse relations via LLMbased relation classification. Our work differs from both along three axes: (i) Graph construction cost-GRAFT and TransGraph require O(N 2 ) LLM calls for pairwise edge classification, whereas G2C-MT constructs edges using lightweight embedding similarity and TF-IDF in a single pass; (ii) Context depth-prior methods restrict context selection to first-order neighbors, while our depth-biased random walk discovers multi-hop paths spanning up to 100 nodes; (iii) Multi-path robustness-stochastic traversal enables multi-path sampling (Table 4), a capability absent in prior graph-based DocMT. Another line of work focuses on building memory mechanisms [Wang et al., 2025] to maintain document-level consistency during translation, but these approaches tend to underemphasize explicit discourse structure modeling.

5.2 Structured Reasoning and Self-Consistency in LLMs

LLMs' reasoning capabilities can be effectively invoked through sophisticated prompting techniques instead of simple instruction-response paradigms. Chain-of-Thought (CoT) prompting [Wei et al., 2022] shows the potential of handling complex reasoning tasks by generating intermediate reasoning steps. Building on this work, non-linear reasoning frameworks have been proposed, such as Tree of Thoughts (ToT) [Yao et al., 2023] and Graph of Thoughts (GoT) [Besta et al., 2024], further improving reasoning performance by exploring multiple reasoning paths. Beyond structural exploration, single-path generation can be extended to multi-path generation to enhance robustness via self-consistency [Wang et al., 2022]. This paradigm is particularly suitable for DocMT, since the translation of a given paragraph often relies on ambiguous discourse clues that may permit multiple valid interpretations. In this work, we bridge these mechanisms by integrating graph-based structural modeling with multi-path sampling for DocMT.

5.3 Retrieval-basedMachine Translation

Early works in NMT have explored retrieval-based methods to improve domain adaptation and translation quality. One representative line of work [Khandelwal et al., 2021; Meng et al., 2022] retrieves token-level examples from a vector datastore to calibrate the model's output distribution. With the powerful in-context learning ability of LLMs, retrieving few-shot examples in sentence-level for LLM has become a dominant paradigm [Agrawal et al., 2023; Ji et al., 2024; Zebaze et al., 2025]. [Wang et al., 2025; Cui et al., 2024] work on document-level translation by retrieving relevant examples but still lack explicit modeling of discourse structure and primarily consider semantic similarity, treating the document as a bag of unrelated sentences.

6 Conclusion

In this paper, we presented G2C-MT, a novel framework for document-level machine translation. Our method models the document as a directed graph to capture structured discourse dependencies. By using depth-biased random walks, we select high-quality context paths as discourse context for prompting LLMs. Experiments across technical and narrative domains show that G2C-MT significantly outperforms strong baselines. Furthermore, our approach is computationally efficient compared to complex agent-based methods. We believe this graph-guided strategy provides a robust solution for longtext translation tasks.

Acknowledgments

We would like to thank the anonymous reviewers for the helpful comments. This work was supported by National Natural Science Foundation of China (Grant No. 62276179, 62537001) and Project Funded by the Priority Academic Program Development of Jiangsu Higher EducationInstitutions. Xiangyu Duan is the corresponding author.