Abstract
This paper presents a novel sentence ordering method by plugging a coherence verifier (CoVer) into pair-wise ranking-based and sequence generation-based methods. It does not change the model parameters of the baseline, and only verifies the coherence of candidate (partial) orders produced by the baseline and reranks them in beam search. We also propose a coherence model as CoVer with a novel graph formulation and a novel data construction strategy for contrastive pre-training independently of the sentence ordering task. Experimental results on four benchmarks demonstrate the effectiveness of our method with topological sorting-based and pointer network-based methods as the baselines. Detailed analyses illustrate how CoVer improves the baselines and confirm the importance of its graph formulation and training strategy.
Introduction
Sentence ordering is the task of arranging a set of unordered sentences into a coherent paragraph. It is a fundamental component in multi-sentence generation tasks such as document summarization and data-to-text generation. Existing approaches typically rely on local constraints—either by predicting the relative order of sentence pairs or by generating sequences step-by-step. However, these methods often fail to capture the global coherence of the entire document, leading to locally plausible but globally disjointed outputs.
Methodology: The Coherence Verifier (CoVer)
To address the limitations of local-only optimization, we introduce CoVer (COherence VERifier), a plug-and-play module designed to evaluate the global "flow" of candidate sentence orders.
Plug-and-Play Integration
CoVer is integrated during the inference phase without altering the underlying baseline model. During beam search, the baseline (e.g., a Pointer Network or a topological sorting model) generates multiple candidate partial orders. CoVer then scores these candidates based on their global coherence, allowing for re-ranking that favors the most logically sound sequence.
Novel Graph Formulation
CoVer represents a paragraph as a tournament digraph to capture complex inter-sentence relationships.
- Nodes: Each sentence is a node, complemented by a special Paragraph Node representing the global topic.
- Edges: Beyond standard sequential edges ($s_i \to s_{i+1}$), we introduce Skip Edges ($s_i \to s_j$ where $j > i+1$). These allow the model to learn long-distance dependencies.
- Architecture: We utilize DeBERTa for sentence embeddings and Relational Graph Convolutional Networks (RGCN) to process the graph structure.
Gradual Permutation Training
Standard training often uses random shuffling to create negative examples, which can be too easy for the model to distinguish. We propose Gradual Permutation: starting from a coherent document, we apply a series of swaps to create a spectrum of coherence. This contrastive learning strategy forces the model to recognize subtle differences in flow, making it a more nuanced judge.
Experimental Results
We evaluated CoVer on four diverse datasets: NIPS and AAN (scientific abstracts), SIND (visual stories), and ROCStory (short narrative stories).
Key Findings
- Significant PMR Gains: The Perfect Match Ratio (PMR)—the percentage of entirely correct sequences—saw the most dramatic improvements. For instance, on the NIPS dataset, adding CoVer to the B-TSort baseline increased PMR from 32.63% to 48.54%.
- Consistency Across Baselines: CoVer improved performance regardless of whether the baseline was ranking-based (B-TSort) or generation-based (BERSON).
- Global Context is Crucial: Ablation studies confirmed that the Paragraph Node and Skip Edges are vital. Without the Paragraph Node, ranking-based models suffered significant performance drops, highlighting the need for a global topic representation.
Conclusion and Future Work
CoVer acts as a "final editor," refining the outputs of existing sentence ordering models by focusing on global coherence. While highly effective, CoVer currently shows slightly lower accuracy in predicting the final sentences of a document compared to the beginning. Future work will explore improved sampling strategies to better capture document conclusions and investigate the scalability of this approach to longer, more complex texts.
Summary updated