Papers with DAG
DepDist: Surface realization via regex and learned dependency-distance tolerance (D19-63)
Copied to clipboard
| Challenge: | The paper describes a method of inflecting and linearizing a lemmatized dependency tree by: (1) determining a regular expression and substitution to describe each productive wordform rule; (2) learning the dependency distance tolerance for each head-dependent pair; (3) topologically sorting the DAG into a surface realization based on edge weight. |
| Approach: | They propose a method of inflecting and linearizing a lemmatized dependency tree by learning the dependency distance tolerance for each head-dependent pair and topologically sorting the DAG into a surface order based on edge weight. |
| Outcome: | The proposed method generates a morphologically inflected surface order for 11 languages across 18 treebanks. |
FS-DAG: Few Shot Domain Adapting Graph Networks for Visually Rich Document Understanding (2025.coling-industry)
Copied to clipboard
| Challenge: | Recent advances in vision-language models have significantly enhanced performance across various natural language processing and computer vision tasks. |
| Approach: | They propose a few shot domain adapting graph (FS-DAG) that leverages domain-specific and language/vision specific backbones within a modular framework to adapt to diverse document types with minimal data. |
| Outcome: | The proposed model is highly performant with less than 90M parameters, making it well-suited for complex real-world applications for information extraction tasks where computational resources are limited. |
Hierarchy Builder: Organizing Textual Spans into a Hierarchy to Facilitate Navigation (2023.acl-demo)
Copied to clipboard
| Challenge: | Information extraction systems produce hundreds to thousands of strings on a specific topic. |
| Approach: | They propose a method that allows users to consume a large collection of related textual strings in an exploratory mode. |
| Outcome: | The proposed method allows users to consume a large collection of related textual strings in an exploratory mode. |
Control-DAG: Constrained Decoding for Non-Autoregressive Directed Acyclic T5 using Weighted Finite State Automata (2024.naacl-short)
Copied to clipboard
| Challenge: | Existing non-autoregressive (NAR) models fail to generate specified entity names in up to 40% of responses and produce OOV errors. |
| Approach: | They propose a constrained decoding algorithm for Directed Acyclic T5 model which offers lexical, vocabulary and length control. |
| Outcome: | The proposed model significantly improves on Schema Guided Dialogue and DART datasets, establishing strong results for Task-Oriented Dialog and Data-to-Text NLG. |
Diffusion Directed Acyclic Transformer for Non-Autoregressive Machine Translation (2025.acl-short)
Copied to clipboard
| Challenge: | Non-autoregressive transformers (NATs) often encounter performance challenges due to the multi-modality problem. |
| Approach: | They propose a direct-acyclic transformer (DAT) that captures multiple translation modalities to paths in a Directed Acyclic Graph (DAG) this allows the model to integrate latent variables into the model, which is crucial for DAT to achieve state-of-the-art performance. |
| Outcome: | The proposed model captures multiple translation modalities to paths in a Directed Acyclic Graph (DAG) but the collaboration with the latent variable introduced through the Glancing training is crucial for the model to attain state-of-the-art performance. |
The problem with probabilistic DAG automata for semantic graphs (N19-1)
Copied to clipboard
| Challenge: | Abstract Meaning Representation (AMR) annotations are directed acyclic graphs, but most probabilistic models view them as strings or trees. |
| Approach: | They show that some DAG automata cannot be made into useful probabilistic models by assigning weights to transitions. |
| Outcome: | The proposed model can't be made into useful probabilistic models by assigning weights to transitions . the proposed model is not feasible for all variants, but it is problematic for planar variants if they are not rooted . |
Directed Acyclic Graph Network for Conversational Emotion Recognition (2021.acl-long)
Copied to clipboard
| Challenge: | Empirical evidence shows that a good representation of conversation context significantly contributes to the model performance. |
| Approach: | They propose to encode query utterances with a directed acyclic graph to better model the intrinsic structure within a conversation. |
| Outcome: | The proposed model outperforms existing models on four ERC benchmarks with state-of-the-art models employed as baselines. |
Event Schema Induction with Double Graph Autoencoders (2022.naacl-main)
Copied to clipboard
| Challenge: | Experimental results show that a new method for learning event schemas from historical events is effective. |
| Approach: | They propose a new event schema induction framework which captures global dependencies among nodes in event graphs. |
| Outcome: | Experimental results show that the proposed model can learn event schemas with global consistency. |
Language Generation via DAG Transduction (P18-1)
Copied to clipboard
| Challenge: | Existing formal frameworks for graph manipulation are underexploited. |
| Approach: | They propose a DAG transducer to perform graph-to-program transformation using a declarative programming language. |
| Outcome: | The proposed transducer achieves a BLEU-4 score of 68.07 for natural language generation from type-logical semantic graphs. |
Taxonomy Construction of Unseen Domains via Graph-based Cross-Domain Knowledge Transfer (2020.acl-main)
Copied to clipboard
| Challenge: | Existing taxonomies are either entirely absent or missing. |
| Approach: | They propose a GNN-based cross-domain transfer framework for the taxonomy construction task. |
| Outcome: | The proposed framework improves on benchmark datasets from science and environment domains. |
N-ary Relation Extraction using Graph-State LSTM (D18-1)
Copied to clipboard
| Challenge: | Existing methods for cross-sentence relation extraction split the input graph into two DAGs, but important information can be lost in the splitting procedure. |
| Approach: | They propose a graph-state LSTM model which uses a parallel state to model each word, recurrently enriching state values via message passing. |
| Outcome: | The proposed model keeps the original graph structure, and speeds up computation by allowing more parallelization. |
An Encoding Strategy Based Word-Character LSTM for Chinese NER (N19-1)
Copied to clipboard
| Challenge: | Existing word-based model can not be trained in batches due to its DAG structure. |
| Approach: | They propose a lattice model that integrates word information into the start or end characters of a word and integrates it into a fixed-sized representation for efficient batch training. |
| Outcome: | The proposed model outperforms other state-of-the-art models on benchmark datasets and shows that it can be trained in batches without a shortcut path. |
MMAU: A Holistic Benchmark of Agent Capabilities Across Diverse Domains (2025.findings-naacl)
Copied to clipboard
Guoli Yin, Haoping Bai, Shuang Ma, Feng Nan, Yanchao Sun, Zhaoyang Xu, Shen Ma, Jiarui Lu, Xiang Kong, Aonan Zhang, Dian Ang Yap, Yizhe Zhang, Karsten Ahnert, Vik Kamath, Mathias Berglund, Dominic Walsh, Tobias Gindele, Juergen Wiest, Zhengfeng Lai, Xiaoming Simon Wang, Jiulong Shan, Meng Cao, Ruoming Pang, Zirui Wang
| Challenge: | Existing benchmarks focus on specific application scenarios, emphasizing task completion but failing to dissect the underlying skills that drive these outcomes. |
| Approach: | They propose a Massive Multitask Agent Understanding benchmark that evaluates LLMs across five domains and offline tasks. |
| Outcome: | The Massive Multitask Agent Understanding (MMAU) benchmark evaluates models across five domains including Tool-use, Directed Acyclic Graph (DAG) QA, Data Science and Machine Learning coding, Contest-level programming and Mathematics. |
Semantic graph parsing with recurrent neural network DAG grammars (D19-1)
Copied to clipboard
| Challenge: | Semantic parsing is the task of mapping natural language to machine interpretable meaning representations. |
| Approach: | They propose a graph-aware sequence model that generates only well-formed graphs . their model is based on a multilingual semantic graphbank . |
| Outcome: | The proposed model yields competitive results in English and establishes the first results for German, Italian and Dutch. |
Graph-Based Chain-of-Thought Pruning for Reducing Redundant Reflections in Reasoning LLMs (2026.findings-acl)
Copied to clipboard
Hongyuan Yuan, Xinran He, Run Shao, Bolei He, Xianwei Xue, Mengke Chen, Qiutong Pan, Haiwei Wang, Haifeng Li
| Challenge: | Extending CoT through RL can induce undesirable thinking patterns such as overthinking . prior work has focused on inefficient reflection, which manifests in two problematic patterns: Indiscriminate Reflection and Repetitive Reflectione . |
| Approach: | They propose a graph-based approach to optimize CoT by pruning each linear CoT into a directed acyclic graph with explicit dependency edges. |
| Outcome: | The proposed approach reduces the average reasoning tokens by 42% while maintaining or improving accuracy. |
Accurate polyglot semantic parsing with DAG grammars (2020.findings-emnlp)
Copied to clipboard
| Challenge: | Semantic parsers treat graphs as strings or trees, but there is no guarantee that the output is a well-formed graph. |
| Approach: | They propose a graph-aware sequence model that utilizes a DAG grammar to guide graph generation. |
| Outcome: | The proposed model outperforms string-based and DAG-grammar models by a large margin and can guarantee the well-formed graphs. |
Porous Lattice Transformer Encoder for Chinese NER (2020.coling-main)
Copied to clipboard
| Challenge: | Existing methods to integrate word boundary information into character-level Chinese NER are inefficient and lack semantic interaction. |
| Approach: | They propose an extension of transformer encoder that is tailored for ChineseNER to incorporate lexicons into character-level Chinese NER by lattices. |
| Outcome: | The proposed extension performs 11.4 times faster than state-of-the-art methods while retaining the rich long-term dependencies. |
Curriculum Learning Meets Directed Acyclic Graph for Multimodal Emotion Recognition (2024.lrec-main)
Copied to clipboard
| Challenge: | Existing models for multimodal Emotion Recognition in conversation (ERC) use text as the main modality for emotion recognition. |
| Approach: | They propose a Directed Acyclic Graph (DAG) approach that integrates textual, acoustic, and visual features within a unified framework. |
| Outcome: | The proposed model outperforms baseline models on the IEMOCAP and MELD datasets. |
A Search-based Neural Model for Biomedical Nested and Overlapping Event Detection (D19-1)
Copied to clipboard
| Challenge: | Existing structured prediction tasks target nested and overlapping events . a new structured prediction model is proposed that uses a relation graph to detect overlapping and nesting events. |
| Approach: | They propose a search-based neural network structured prediction model that treats the task as a searching problem on a relation graph of trigger-argument structures. |
| Outcome: | The proposed model performs comparable to the state-of-the-art model Turku Event Extraction System (TEES) on the BioNLP Cancer Genetics (CG) Shared Task 2013 without the use of syntactic and hand-engineered features. |
Legal Judgment Prediction via Topological Learning (D18-1)
Copied to clipboard
| Challenge: | Existing studies focus on a specific subtask of judgment prediction and ignore the dependencies among subtasks. |
| Approach: | They propose a topological multi-task learning framework that incorporates multiple subtasks and DAG dependencies into judgment prediction. |
| Outcome: | The proposed model improves on baselines on all judgment prediction tasks. |
Joint Enhancement of Relational Reasoning for Long-Context LLMs (2025.findings-emnlp)
Copied to clipboard
| Challenge: | JERR is a graph-based reasoning framework for large language models . it enables LLMs to handle extended contexts with improved reliability and transparency . |
| Approach: | They propose a graph-based reasoning framework that integrates synopsis extraction, graph construction, and relational reasoning. |
| Outcome: | The proposed framework outperforms baselines on ROUGE and F1 metrics and achieves the highest scores on the LLM-Rater evaluation. |
ESCP: Enhancing Emotion Recognition in Conversation with Speech and Contextual Prefixes (2024.lrec-main)
Copied to clipboard
| Challenge: | Emotion Recognition in Conversation (ERC) aims to analyze the speaker’s emotional state in a conversation. |
| Approach: | They propose to combine a directed acyclic graph and contextual prefixes to model historical utterances in a conversation and incorporate a contextual prefixed containing sentiment and semantics of historical . |
| Outcome: | The proposed model achieves state-of-the-art (SOTA) performance on several public benchmarks. |
Graph-Structured Speculative Decoding (2024.findings-acl)
Copied to clipboard
Zhuocheng Gong, Jiahao Liu, Ziyue Wang, Pengfei Wu, Jingang Wang, Xunliang Cai, Dongyan Zhao, Rui Yan
| Challenge: | Speculative decoding is a promising technique to accelerate the inference of Large Language Models. |
| Approach: | They propose a method that uses a token graph to record multiple sequence hypotheses within a single draft stage. |
| Outcome: | The proposed method significantly accelerates the inference of Large Language Models (LLMs) it allows the LLM to choose from and select the longest sequence that meets its standards. |
MedVerse: Efficient and Reliable Medical Reasoning via DAG-Structured Parallel Execution (2026.acl-long)
Copied to clipboard
Jianwen Chen, Xinyu Yang, Peng Xia, Arian Azarang, Yueh Z Lee, Gang Li, Hongtu Zhu, Yun Li, Beidi Chen, Huaxiu Yao
| Challenge: | Recent advances in large reasoning models have broadened the capabilities of medical artificial intelligence. |
| Approach: | They propose a reasoning framework for complex medical inference that reformulates medical reasoning as a parallelizable directed acyclic graph process based on Petri Net theory. |
| Outcome: | The proposed reasoning framework improves strong general-purpose LLMs by up to 8.9%. |
MMDAG: Multimodal Directed Acyclic Graph Network for Emotion Recognition in Conversation (2022.lrec-1)
Copied to clipboard
| Challenge: | Emotion recognition in conversation is important for an empathetic dialogue system to understand the user’s emotion and then generate appropriate emotional responses. |
| Approach: | They propose to use multimodal directed acyclic graphs to integrate multimodal information and contextual information into a DAG architecture to exploit multimodal contexts. |
| Outcome: | Comparative studies on IEMOCAP and MELD show that the proposed model outperforms state-of-the-art models. |
DeMAC: Enhancing Multi-Agent Coordination with Dynamic DAG and Manager-Player Feedback (2025.findings-emnlp)
Copied to clipboard
| Challenge: | Multi-agent systems (MAS) powered by large language models struggle to adapt to evolving task dependencies and to handle uncertainties. |
| Approach: | They propose a Dynamic Environment-Aware Manager-Player Agents Coordination framework that enhances multi-agent coordination through long-term strategic planning. |
| Outcome: | The proposed framework outperforms traditional reinforcement learning and human-agent collaboration in the Overcooked simulation. |
CausalDialogue: Modeling Utterance-level Causality in Conversations (2023.findings-acl)
Copied to clipboard
| Challenge: | Despite widespread adoption, neural conversation models have yet to exhibit natural chat capabilities with humans . despite their widespread adoption in society, chatbots have yet not shown natural chat capability . |
| Approach: | They propose a causality-enhanced method to enhance the impact of causality at the utterance level in training neural conversation models. |
| Outcome: | The proposed method improves diversity and agility of loss functions and still needs improvement . the proposed method is based on a CausalDialogue dataset . |
Enhanced Data Synthesis for LLM through Reasoning Structures Generated by Hierarchical GFlowNet (2025.findings-acl)
Copied to clipboard
| Challenge: | Existing methods to optimize instruction-response pairs lack a systematic design for the underlying reasoning structure. |
| Approach: | They propose a Reasoning Structure driven data Synthesis method that leverages a coarse-to-fine directed acyclic graph to construct reasoning structures efficiently. |
| Outcome: | The proposed method outperforms existing methods in 48.50%, 84.00%, 79.90% of the synthetic datasets trained on the proposed model. |
VillagerAgent: A Graph-Based Multi-Agent Framework for Coordinating Complex Task Dependencies in Minecraft (2024.findings-acl)
Copied to clipboard
| Challenge: | Multi-agent collaboration using LLMs is a challenging research topic that aims to enable multiple autonomous agents to coordinate their actions and achieve a common goal. |
| Approach: | They propose a benchmark for multi-agent collaboration in the Minecraft environment and introduce a Directed Acyclic Graph Multi-Agent Framework to resolve complex inter-ag dependencies. |
| Outcome: | The proposed framework outperforms existing ModelVerse, reducing hallucinations and improving task decomposition efficacy. |
WebClipper: Efficient Evolution of Web Agents with Graph-based Trajectory Pruning (2026.acl-long)
Copied to clipboard
Junjie Wang, Zequn Xie, Dan Yang, Jie Feng, Yue Shen, Duolin Sun, Meixiu Long, Yihan Jiao, Zhehao Tan, Jian Wang, Peng Wei, Jinjie Gu
| Challenge: | Open-source web agents rely on long tool-call trajectories with cyclic reasoning loops and exploration of unproductive branches. |
| Approach: | They propose a framework that compresses web agent trajectories via graph-based pruning. |
| Outcome: | The proposed framework reduces tool-call rounds by 20% while improving accuracy and efficiency while maintaining the same level of performance as existing models. |
Order Doesn’t Matter, But Reasoning Does: Training LLMs with Order-Centric Augmentation (2025.emnlp-main)
Copied to clipboard
| Challenge: | Logical reasoning is essential for large language models (LLMs) to ensure accurate and coherent inferences. |
| Approach: | They propose an order-centric data augmentation framework based on commutativity in logical reasoning that randomly shuffles independent premises to introduce condition order augmentation. |
| Outcome: | The proposed framework improves LLMs’ reasoning performance and adaptability to diverse logical structures. |
Divide-Then-Aggregate: An Efficient Tool Learning Method via Parallel Tool Invocation (2025.acl-long)
Copied to clipboard
| Challenge: | Large Language Models (LLMs) demonstrate remarkable capabilities but their ability to autonomously execute complex real-world tasks remains limited. |
| Approach: | They propose a parallel tool invocation framework that decomposes tasks into parallel tool-using subtasks while aggregating results for subsequent decisions. |
| Outcome: | The proposed method significantly improves task performance while reducing token consumption and inference time. |
Conjunctive Prompt Attacks in Multi-Agent LLM Systems (2026.acl-long)
Copied to clipboard
| Challenge: | Existing defenses do not reliably stop the attack because no single component appears malicious in isolation. |
| Approach: | They study conjunctive prompt attacks where trigger key and adversarial template appear benign alone but activate harmful behavior when routing brings them together. |
| Outcome: | The proposed model significantly improves performance over baselines while keeping false activations low. |
From Trajectories to Graphs: Contract-Checked Editing for Verifier-Guided LLM Reasoning (2026.acl-long)
Copied to clipboard
| Challenge: | Existing methods for inference-time search refine single trajectories and lack a reliable mechanism for composing partial solutions across candidates. |
| Approach: | a new method uses a gate-based algorithm to validate a nontrivial edit before invoking the verifier. |
| Outcome: | a new method improves verifier-runnable recombination and accuracy over existing methods . it outperforms execution-guided beam search on Spider and humanEval-MF on MCTS . a contract-checked graph editing improves recompilation and recombines partial solutions . |
Rolling Out Data Quality Overnight, without losing the plot: A Multi-Agent System for Speech Data Quality Management (2026.findings-acl)
Copied to clipboard
Rishabh Kumar, Abhinav Painuli, Chriss Philip Saji, Devesh Soni, Amrith Krishna, Ganesh Ramakrishnan
| Challenge: | Using automation to improve quality management is expensive and resource-intensive for speech datasets. |
| Approach: | They propose a natural language-driven agentic framework that compiles user requirements into dependency-aware DAG workflows over modular tools for audio, transcript, and metadata verification. |
| Outcome: | The proposed framework achieves 80-90% agreement with expert verification while requiring less than 20% of the cost and time of manual QC. |