bluuebunny/crossref_metadata_2025 huggingface dataset:
Approximate Estimation of High-Dimension Execution Skill for Dynamic Agents in Continuous Domains
Authors: Nieves-Rivera Delma , Archibald Christopher
Published: October 2024

In many real-world continuous action domains, human agents must decide which actions to attempt and then execute those actions to the best of their ability. However, humans cannot execute actions without error. Human performance in these domains can potentially be improved by the use of AI to aid in decision-making. One requirement for an AI to correctly reason about what actions a human agent should attempt is a correct model of that human’s execution error, or skill. Recent work has demonstrated successful techniques for estimating this execution error with various types of agents across different domains. However, this previous work made several assumptions that limit the application of these ideas to real-world settings. First, previous work assumed that the error distributions were symmetric normal, which meant that only a single parameter had to be estimated. In reality, agent error distributions might exhibit arbitrary shapes and should be modeled more flexibly. Second, it was assumed that the execution error of the agent remained constant across all observations. Especially for human agents, execution error changes over time, and this must be taken into account to obtain effective estimates. To overcome both of these shortcomings, we propose a novel particle-filter-based estimator for this problem. After describing the details of this approximate estimator, we experimentally explore various design decisions and compare performance with previous skill estimators in a variety of settings to showcase the improvements. The outcome is an estimator capable of generating more realistic, time-varying execution skill estimates of agents, which can then be used to assist agents in making better decisions and improve their overall performance.
A More Practical Algorithm for Weighted First-Order Model Counting with Linear Order Axiom
Authors: Meng Qiaolan , Tóth Jan , Wang Yuanhong , Wang Yuyi , Kuželka Ondřej
Published: October 2024

We consider the task of weighted first-order model counting (WFOMC), a fundamental problem of probabilistic inference in statistical relational learning. The goal of WFOMC is to compute the weighted sum of models of a given first-order logic sentence over a finite domain, where each model is assigned a weight by a pair of weighting functions. Past work has shown that WFOMC can be solved in polynomial time in the domain size if the sentence is in the two-variable fragment of first-order logic (FO2). This result is later extended to the case where the sentence is in FO2with the linear order axiom, which requires a binary predicate in the sentence to introduce a linear ordering of the domain elements. However, despite its polynomial theoretical complexity, the existing domain-liftable algorithm for WFOMC with the linear order often suffers from inefficiencies when applied to real-world problems. This paper introduces a novel domain-lifted algorithm for WFOMC with the linear order axiom. Compared to the existing approach, our proposed algorithm exploits the inherent symmetries within first-order logic sentences and weighting functions to minimize redundant computations. Experimental results verify the efficiency of our approach, demonstrating a significant speedup over the existing approach.
Online Friends Partitioning Under Uncertainty
Authors: Cohen Saar , Agmon Noa
Published: October 2024

We study the friendship-based online coalition formation problem, in which agents that appear one at a time should be partitioned into coalitions, and an agent’s utility for a coalition is the number of her neighbors (i.e., friends) within the coalition. Unlike prior work, agents’ friendships may be uncertain. We analyze the desirability of the resulting partition in the common term of optimality, aiming to maximize the social welfare. We design an online algorithm termed Maximum Predicted Coalitional Friends (MPCF), which is enhanced with predictions of each agent’s number of friends within any possible coalition. For common classes of random graphs, we prove that MPCF is optimal, and, for certain graphs, provides the same guarantee as the best known competitive algorithm for settings without uncertainty.
United We Stand: Decentralized Multi-Agent Planning with Attrition
Authors: Nguyen Nhat , Nguyen Duong , Rizzo Gianluca , Nguyen Hung
Published: October 2024

Decentralized planning is a key element of cooperative multi-agent systems for information gathering tasks. However, despite the high frequency of agent failures in realistic large deployment scenarios, current approaches perform poorly in the presence of failures, by not converging at all, and/or by making very inefficient use of resources (e.g. energy). In this work, we propose Attritable MCTS (A-MCTS), a decentralized MCTS algorithm capable of timely and efficient adaptation to changes in the set of active agents. It is based on the use of a global reward function for the estimation of each agent’s local contribution, and regret matching for coordination. We evaluate its effectiveness in realistic data-harvesting problems under different scenarios. We show both theoretically and experimentally that A-MCTS enables efficient adaptation even under high failure rates. Results suggest that, in the presence of frequent failures, our solution improves substantially over the best existing approaches in terms of global utility and scalability.
How to Guide a Present-Biased Agent Through Prescribed Tasks?
Authors: Belova Tatiana , Dementiev Yuriy , Fomin Fedor , Golovach Petr , Ignatiev Artur
Published: October 2024

The present bias is a well-documented behavioral trait that significantly influences human decision-making, with present-biased agents often prioritizing immediate rewards over long-term benefits, leading to suboptimal outcomes in various real-world scenarios. Kleinberg and Oren (2014) proposed a popular graph-theoretical model of inconsistent planning to capture the behavior of present-biased agents. In this model, a multi-step project is represented by a weighted directed acyclic task graph, where the agent traverses the graph based on present-biased preferences. We use the model of Kleinberg and Oren to address the principal-agent problem, where a principal, fully aware of the agent’s present bias, aims to modify an existing project by adding or deleting tasks. The challenge is to create a modified project that satisfies two somewhat contradictory conditions. On one hand, the present-biased agent should select specific tasks deemed important by the principal. On the other hand, if the anticipated costs in the modified project become too high for the agent, there is a risk of the agent abandoning the entire project, which is not in the principal’s interest. To tackle this issue, we leverage the tools of parameterized complexity to investigate whether the principal’s strategy can be efficiently identified. We provide algorithms and complexity bounds for this problem.
Counterfactual Thinking in Stochastic Dynamics of Cooperation
Authors: Fernandes António M. , Santos Francisco C. , Paiva Ana
Published: October 2024

Understanding the conundrum of human cooperation has been declared one of the century’s grand challenges. Traditionally, the evolution of cooperative action in nature is analyzed through the lens of Evolutionary Game Theory, specifically, using the social learning framework, a model for Darwinian competition. However, more complex individuals may resort to more sophisticated learning rules such as Counterfactual Thinking (CT). Given these individuals’ cognitive empowerment, the question of how the presence of counterfactuals influences the evolution of cooperation in a hybrid population of these complex agents and social learners. Here we explore how cooperation emerges from the interplay of different strategy revision paradigms by analyzing large-scale Markov processes. We find that increasing the prevalence of CT individuals can promote cooperation, but such an increase is non-monotonous. Moreover, whereas counterfactual reasoning generally fosters cooperation, it fails to promote such behaviour among counterfactuals. Lastly, we find that increasing the population’s heterogeneity level enhances cooperation among social learners, but again not among counterfactuals. This indicates that, under certain circumstances, the presence of more sophisticated agents may help promote cooperation in hybrid populations. The proposed study may come as a starting point for a more profound understanding of agents’ counterfactual rationality impact on hybrid populations.
Limited Voting for Better Representation?
Authors: Venema-Los Maaike , Christoff Zoé , Grossi Davide
Published: October 2024

Limited Voting (LV) is an approval-based method for multi-winner elections where all ballots are required to have a same fixed size. While it appears to be used as voting method in corporate governance and has some political applications, to the best of our knowledge, no formal analysis of the rule exists to date. We provide such an analysis here, prompted by a request for advice about this voting rule by a health insurance company in the Netherlands, which uses it to elect its work council. We study conditions under which LV would improve representation over standard approval voting and when it would not. We establish the extent of such an improvement, or lack thereof, both in terms of diversity and proportionality notions. These results help us understand if, and how, LV may be used as a low-effort fix of approval voting in order to enhance representation.
Control by Adding Players to Change or Maintain the Shapley–Shubik or the Penrose–Banzhaf Power Index in Weighted Voting Games Is Complete for NPPP
Authors: Kaczmarek Joanna , Rothe Jörg
Published: October 2024

Weighted voting games are a well-known and useful class of succinctly representable simple games that have many real-world applications, e.g., to model collective decision-making in legislative bodies or shareholder voting. Among the structural control types being analyzing, one is control by adding players to weighted voting games, so as to either change or to maintain a player’s power in the sense of the (probabilistic) Penrose–Banzhaf power index or the Shapley–Shubik power index. For the problems related to this control, the best known lower bound is PP-hardness, where PP is “probabilistic polynomial time,” and the best known upper bound is the class NP, i.e., the class NP with a PP oracle. We optimally raise this lower bound by showing NPPP-hardness of all these problems for the Penrose–Banzhaf and the Shapley–Shubik indices, thus establishing completeness for them in that class. Our proof technique may turn out to be useful for solving other open problems related to weighted voting games with such a complexity gap as well.
Existence of MMS Allocations of Mixed Manna
Authors: Hsu Kevin
Published: October 2024

Maximin share (MMS) allocations are a popular relaxation of envy-free allocations that have received wide attention in the fair division of indivisible items. Although MMS allocations of goods can fail to exist, previous work has found conditions under which they exist. Specifically, MMS allocations of goods exist whenever m ≤ n+5, and this bound is tight in the sense that they can fail to exist when m = n+6. The techniques used to obtain these results do not apply to the mixed manna setting, leaving the question of whether similar results hold for the general setting. This paper addresses this by introducing new techniques to handle these settings. In particular, we are able to answer this question completely for the chores setting, and partially for the mixed manna setting. An agent i is a chores agent if it considers every item to be a chore and a non-negative agent if its MMS guarantee is non-negative. In this paper, we prove that an MMS allocation exists as long as m ≤ n+5 and either (i) every agent is a chores agent, or (ii) there exists a non-negative agent. In addition, for n ≤ 3, we also prove that an MMS allocation exists as long as m ≤ n+5, regardless of the types of agents. To the best of our knowledge, these are the first non-trivial results pertaining to the existence of exact MMS allocations in the mixed manna setting.
Multi-Agent Path Finding with Task Assignment and Supporting Constraints
Authors: Bonhomme Caroline , Grand Christophe , Lesire Charles , Dufour Jean-Louis , Guettier Christophe
Published: October 2024

The Multi-Agent Path Finding with Task Assignment (MAPF-TA) problem combines task allocation and collision-free path finding for multiple agents within a graph. It can be solved by an extension of the well-known Conflict-Based Search (CBS) algorithm called CBS-TA, which has been demonstrated to be optimal in terms of the sum of costs of all agents. While coordination between agents in MAPF-TA is limited to no-collision constraints, real-world scenarios may require cooperation between agents. For instance, in an exploration mission involving a system of multiple robots, one robot might need to enter a hazardous area only if another agent is able to monitor this area from a support location. Given a hazardous location and its corresponding support location, this coordination requirement can be modeled by a support constraint. In this paper, we propose an extension of the CBS-TA algorithm to handle these support conflicts. In addition, we improve the algorithm’s performance by introducing an alternative cost matrix for task assignment, which takes into account support coordination while maintaining the optimality of the CBS-TA algorithm. We compare the proposed approach to a greedy algorithm in which the task assignment and path finding problems are decoupled, and using two different assignment matrices: the original matrix of CBS-TA and our support-aware matrix. Experiments are carried out using standard MAPF benchmark instances, showing that the proposed cost matrix improves search time and increases the number of instances solved within a given timeout.
Multi-Agent Planning Using Visual Language Models
Authors: Brienza Michele , Argenziano Francesco , Suriani Vincenzo , Bloisi Domenico D. , Nardi Daniele
Published: October 2024

Large Language Models (LLMs) and Visual Language Models (VLMs) are attracting increasing interest due to their improving performance and applications across various domains and tasks. However, LLMs and VLMs can produce erroneous results, especially when a deep understanding of the problem domain is required. For instance, when planning and perception are needed simultaneously, these models often struggle because of difficulties in merging multi-modal information. To address this issue, fine-tuned models are typically employed and trained on specialized data structures representing the environment. This approach has limited effectiveness, as it can overly complicate the context for processing. In this paper, we propose a multi-agent architecture for embodied task planning that operates without the need for specific data structures as input. Instead, it uses a single image of the environment, handling free-form domains by leveraging commonsense knowledge. We also introduce a novel, fully automatic evaluation procedure, PG2S, designed to better assess the quality of a plan. We validated our approach using the widely recognized ALFRED dataset, comparing PG2S to the existing KAS metric to further evaluate the quality of the generated plans.
Value-Based Rationales Improve Social Experience: A Multiagent Simulation Study
Authors: Tzeng Sz-Ting , Ajmeri Nirav , Singh Munindar P.
Published: October 2024

We propose Exanna, a framework to realize agents that incorporate values in decision making. An Exanna agent considers the values of itself and others when providing rationales for its actions and evaluating the rationales provided by others. Via multiagent simulation, we demonstrate that considering values in decision making and producing rationales, especially for norm-deviating actions, leads to (1) higher conflict resolution, (2) better social experience, (3) higher privacy, and (4) higher flexibility.
No Transaction Fees? No Problem! Achieving Fairness in Transaction Fee Mechanism Design
Authors: Damle Sankarshan , Srivastava Varul , Gujar Sujit
Published: October 2024

The recently proposed Transaction Fee Mechanism (TFM) literature studies the strategic interaction between the miner of a block and the transaction creators (or users) in a blockchain. In a TFM, the miner includes transactions that maximize its utility while users submit fees for a slot in the block. The existing TFM literature focuses on satisfying standard incentive properties – which may limit widespread adoption. We argue that a TFM is “fair” to the transaction creators if it satisfies specific notions, namely Zero-fee Transaction Inclusion and Monotonicity. First, we prove that one generally cannot ensure both these properties and prevent a miner’s strategic manipulation. We also show that existing TFMs either do not satisfy these notions or do so at a high cost to the miners’ utility. As such, we introduce a novel TFM using on-chain randomness – rFTM. We prove that rFTM guarantees incentive compatibility for miners and users while satisfying our novel fairness constraints.
Interpretation of the Intent Detection Problem as Dynamics in a Low-Dimensional Space
Authors: Sanchez-Karhunen Eduardo , Quesada-Moreno Jose F. , Gutiérrez-Naranjo Miguel A.
Published: October 2024

Intent detection is a text classification task whose aim is to recognize and label the semantics behind a users’ query. It plays a critical role in various business applications. The output of the intent detection module strongly conditions the behavior of the whole system. This sequence analysis task is mainly tackled using deep learning techniques. Despite the widespread use of these techniques, the internal mechanisms used by networks to solve the problem are poorly understood. Recent lines of work have analyzed the computational mechanisms learned by RNNs from a dynamical systems perspective. In this work, we investigate how different RNN architectures solve the SNIPS intent detection problem. Sentences injected into trained networks can be interpreted as trajectories traversing a hidden state space. This space is constrained to a low-dimensional manifold whose dimensionality is related to the embedding and hidden layer sizes. To generate predictions, RNN steers the trajectories towards concrete regions, spatially aligned with the output layer matrix rows directions. Underlying the system dynamics, an unexpected fixed point topology has been identified with a limited number of attractors. Our results provide new insights into the inner workings of networks that solve the intent detection task.
GLIMMER: Incorporating Graph and Lexical Features in Unsupervised Multi-Document Summarization
Authors: Liu Ran , Liu Ming , Yu Min , Jiang Jianguo , Li Gang , Zhang Dan , Li Jingyuan , Meng Xiang , Huang Weiqing
Published: October 2024

Pre-trained language models are increasingly being used in multi-document summarization tasks. However, these models need large-scale corpora for pre-training and are domain-dependent. Other non-neural unsupervised summarization approaches mostly rely on key sentence extraction, which can lead to information loss. To address these challenges, we propose a lightweight yet effective unsupervised approach called GLIMMER: a Graph and LexIcal features based unsupervised Multi-docuMEnt summaRization approach. It first constructs a sentence graph from the source documents, then automatically identifies semantic clusters by mining low-level features from raw texts, thereby improving intra-cluster correlation and the fluency of generated sentences. Finally, it summarizes clusters into natural sentences. Experiments conducted on Multi-News, Multi-XScience and DUC-2004 demonstrate that our approach outperforms existing unsupervised approaches. Furthermore, it surpasses state-of-the-art pre-trained multi-document summarization models (e.g. PEGASUS and PRIMERA) under zero-shot settings in terms of ROUGE scores. Additionally, human evaluations indicate that summaries generated by GLIMMER achieve high readability and informativeness scores. Our code is available at https://github.com/Oswald1997/GLIMMER.
TIGER: Temporally Improved Graph Entity Linker
Authors: Zhang Pengyu , Cao Congfeng , Groth Paul
Published: October 2024

Knowledge graphs change over time, for example, when new entities are introduced or entity descriptions change. This impacts the performance of entity linking, a key task in many uses of knowledge graphs such as web search and recommendation. Specifically, entity linking models exhibit temporal degradation - their performance decreases the further a knowledge graph moves from its original state on which an entity linking model was trained. To tackle this challenge, we introduce TIGER: a Temporally Improved Graph Entity Linker. By incorporating structural information between entities into the model, we enhance the learned representation, making entities more distinguishable over time. The core idea is to integrate graph-based information into text-based information, from which both distinct and shared embeddings are based on an entity’s feature and structural relationships and their interaction. Experiments on three datasets show that our model can effectively prevent temporal degradation, demonstrating a 16.24% performance boost over the state-of-the-art in a temporal setting when the time gap is one year and an improvement to 20.93% as the gap expands to three years. The code and data are made available at https://github.com/pengyu-zhang/TIGER-Temporally-Improved-Graph-Entity-Linker.
Semantic Similarity Driven Multi-Modal Model for Rumor Detection
Authors: Li Chenyang , Xu Bo , Wang Meng , He Kun
Published: October 2024

The wide spread of rumors with images and texts on social media has attracted broad attention in the academy and industry. Existing models focus on utilizing powerful feature extractors to obtain multi-modal features and introducing various external knowledge. However, the intrinsic semantic similarity of different modalities is either simply ignored in most models or far from adequate in others. The insufficiency of semantic similarity information suppresses the potential of rumor detection models severely. To address this issue, we propose a novel model termed the Semantic Similarity driven Multi-modal model (SemSim) for rumor detection, which deeply captures the semantic similarity through more comprehensive fusion between different modalities and designs a new classification method consequently. Specifically, the proposed SemSim first integrates the raw image and raw text into a virtual image, which fuses information at a new view, i.e., via the diffusion process inside stable diffusion models. Then SemSim captures the semantic similarity score between virtual image and raw image as the intrinsic information to drive SemSim. Besides, co-attention mechanism is employed to further perceive consistency and enhance interaction between the raw text-image pair. The fused representations via co-attention are utilized to evaluate the multi-modal feature score. In the end, SemSim balances the above two scores for final classification. Experiments on two typical real-world datasets show that SemSim can effectively detect rumors and outperform state-of-the-art methods.
Enhancing Discourse Coherence to Improve Cross-Document Event Coreference Resolution
Authors: Chen Xinyu , Xu Sheng , Li Peifeng , Zhu Qiaoming
Published: October 2024

Cross-Document Event Coreference Resolution (CD-ECR) is a task of grouping event mentions across multiple documents that refer to the same real-world events. In contrast to within-document event mentions, which are linked by rich, coherent contexts, cross-document event mentions lack such contexts, making it challenging for the model to establish a connection between two event mentions in different documents. To address this issue, we propose a novel mechanism of enhancing discourse coherence to boost CD-ECR. Specifically, we introduce a new task, ECD-CoE (Event-oriented Cross-Document Coherence Enhancement), which selects coherent sentences that form a coherent text for two cross-document event mentions. We then use this coherent text to represent the event mentions and resolve coreferent events. Experimental results on both the ECB+ and GVC datasets indicate that our proposed method outperforms several state-of-the-art baselines.
MLGAT: Multi-Scale Line Graph Attention Network for Emotion Recognition in Conversation
Authors: Xu Xiujuan , Shi Xiaoxiao , Zhao Zhehuan , Liu Yu
Published: October 2024

Emotion Recognition in Conversation (ERC) plays an important role in intelligent human-computer interaction. Highly accurate emotion recognition helps to improve the ability of machines to serve humans. Recent works exhibit poor generalization ability and low recognition accuracy, and better performances can only be presented on specific datasets. To be able to adapt to complex real-world application scenarios, we propose a novel model, termed Multi-scale Line Graph ATtention Network for Emotion Recognition in Conversation (MLGAT). MLGAT mines the emotional information dependent on the target utterance by focusing on local context and global context at different scales. Experiments show that our model achieves the second-highest performance among all current methods on both IEMOCAP and MELD datasets. Wa-F1 scores are 71.49% and 75.08%, respectively, which are only slightly different from their respective SOTAs (state of the art). Moreover, the model can show high accuracy in a few classes without additional measures.
A Coin Has Two Sides: A Novel Detector-Corrector Framework for Chinese Spelling Correction
Authors: Zeng Xiangke , Li Zuchao , Zhang Lefei , Wang Ping , Wu Hongqiu , Zhao Hai
Published: October 2024

Chinese Spelling Correction (CSC) stands as a foundational Natural Language Processing (NLP) task, which primarily focuses on the correction of erroneous characters in Chinese texts. Certain existing methodologies opt to disentangle the error correction process, employing an additional error detector to pinpoint error positions. However, owing to the inherent performance limitations of error detector, precision and recall are like two sides of the coin which can not be both facing up simultaneously. Furthermore, it is also worth investigating how the error position information can be judiciously applied to assist the error correction. In this paper, we introduce a novel approach based on error detector-corrector framework. Our detector is designed to yield two error detection results, each characterized by high precision and recall. Given that the occurrence of errors is context-dependent and detection outcomes may be less precise, we incorporate the error detection results into the CSC task using an innovative feature fusion strategy and a selective masking strategy. Empirical experiments conducted on mainstream CSC datasets substantiate the efficacy of our proposed method.
Reassessing Non-Autoregressive Neural Machine Translation with a Fine-Grained Error Taxonomy
Authors: Liu Yan , Wang Longyue , Tu Zhaopeng , Xiong Deyi
Published: October 2024

Non-autoregressive neural machine translation (NAT) has made remarkable progress since it is proposed. The performance of NAT in terms of BLEU has approached or even matched that of autoregressive neural machine translation (AT). However, other evaluation metrics show that NAT still lags behind. Unfortunately, these metrics only provide a numerical difference, and it is unclear how the translations produced by NAT differ from those produced by AT. In addition, the multimodality problem is always a significant issue in NAT. To assess whether NAT models are fully capable of solving the multimodality problem and achieving the performance of AT, we specifically design an error taxonomy to annotate errors in translations. The taxonomy is grounded on a systematic and hierarchical error analysis. We carry out an extensive annotation with professional annotators and analyze four NAT models and two AT models. Our analysis and experiments show that (1) the number of errors in NAT translations marked by annotators is 1.54 times that of AT translations, (2) the multimodality problem of NAT affects translations from lexical to syntactic levels, and even up to discourse, and (3) the four NAT models cannot fully eradicate the multimodality problem despite mitigation efforts.
Tailored-LLaMA: Optimizing Few-Shot Learning in Pruned LLaMA Models with Task-Specific Prompts
Authors: Aftab Danyal , Davy Steven
Published: October 2024

Large language models demonstrate impressive proficiency in language understanding and generation. Nonetheless, training these models from scratch, even the least complex billion-parameter variant demands significant computational resources rendering it economically impractical for many organizations. With large language models functioning as general-purpose task solvers, this paper investigates their task-specific fine-tuning. We employ task-specific datasets and prompts to fine-tune two pruned LLaMA models having 5 billion and 4 billion parameters. This process utilizes the pre-trained weights and focuses on a subset of weights using the LoRA method. One challenge in fine-tuning the LLaMA model is crafting a precise prompt tailored to the specific task. To address this, we propose a novel approach to fine-tune the LLaMA model under two primary constraints: task specificity and prompt effectiveness. Our approach, Tailored LLaMA initially employs structural pruning to reduce the model sizes from 7B to 5B and 4B parameters. Subsequently, it applies a carefully designed prompt specific to the task and utilizes the LoRA method to accelerate the fine-tuning process. Moreover, fine-tuning a model pruned by 50% for less than one hour restores the mean accuracy of classification tasks to 95.68% at a 20% compression ratio and to 86.54% at a 50% compression ratio through few-shot learning with 50 shots. Our validation of Tailored LLaMA on these two pruned variants demonstrates that even when compressed to 50%, the models maintain over 65% of the baseline model accuracy in few-shot classification and generation tasks. These findings highlight the efficacy of our tailored approach in maintaining high performance with significantly reduced model sizes.
Large Language Model Prompting with Episodic Memory
Authors: Do Dai , Tran Quan , Venkatesh Svetha , Le Hung
Published: October 2024

Prompt optimization is essential for enhancing the performance of Large Language Models (LLMs) in a range of Natural Language Processing (NLP) tasks, particularly in scenarios of few-shot learning where training examples are incorporated directly into the prompt. Despite the growing interest in optimizing prompts with few-shot examples, existing methods for prompt optimization are often resource-intensive or perform inadequately. In this work, we propose PrOmpting with Episodic Memory (POEM), a novel prompt optimization technique that is simple, efficient, and demonstrates strong generalization capabilities. We approach prompt optimization as a Reinforcement Learning (RL) challenge, using episodic memory to archive combinations of input data, permutations of few-shot examples, and the rewards observed during training. In the testing phase, we optimize the sequence of examples for each test query by selecting the sequence that yields the highest total rewards from the top-k most similar training examples in the episodic memory. Our results show that POEM outperforms recent techniques like TEMPERA and RLPrompt by over 5.3% in various text classification tasks. Furthermore, our approach adapts well to broader language understanding tasks, consistently outperforming conventional heuristic methods for ordering examples.
Differentiating Choices via Commonality for Multiple-Choice Question Answering
Authors: Deng Wenqing , Wang Zhe , Wang Kewen , Pan Shirui , Zhang Xiaowang , Feng Zhiyong
Published: October 2024

Multiple-choice question answering (MCQA) becomes particularly challenging when all choices are relevant to the question and are semantically similar. Yet this setting of MCQA can potentially provide valuable clues for choosing the right answer. Existing models often rank each choice separately, overlooking the context provided by other choices. Specifically, they fail to leverage the semantic commonalities and nuances among the choices for reasoning. In this paper, we propose a novel MCQA model by differentiating choices through identifying and eliminating their commonality, called DCQA. Our model captures token-level attention of each choice to the question, and separates tokens of the question attended to by all the choices (i.e., commonalities) from those by individual choices (i.e., nuances). Using the nuances as refined contexts for the choices, our model can effectively differentiate choices with subtle differences and provide justifications for choosing the correct answer. We conduct comprehensive experiments across five commonly used MCQA benchmarks, demonstrating that DCQA consistently outperforms baseline models. Furthermore, our case study illustrates the effectiveness of the approach in directing the attention of the model to more differentiating features.
Inside the Black Box: Detecting Data Leakage in Pre-Trained Language Encoders
Authors: Xin Yuan , Li Zheng , Yu Ning , Chen Dingfan , Fritz Mario , Backes Michael , Zhang Yang
Published: October 2024

Despite being prevalent in the general field of Natural Language Processing (NLP), pre-trained language models inherently carry privacy and copyright concerns due to their nature of training on large-scale web-scraped data. In this paper, we pioneer a systematic exploration of such risks associated with pre-trained language encoders, specifically focusing on the membership leakage of pre-training data exposed through downstream models adapted from pre-trained language encoders–an aspect largely overlooked in existing literature. Our study encompasses comprehensive experiments across four types of pre-trained encoder architectures, three representative downstream tasks, and five benchmark datasets. Intriguingly, our evaluations reveal, for the first time, the existence of membership leakage even when only the black-box output of the downstream model is exposed, highlighting a privacy risk far greater than previously assumed. Alongside, we present in-depth analysis and insights toward guiding future researchers and practitioners in addressing the privacy considerations in developing pre-trained language models.
Advancing Topic Segmentation of Broadcasted Speech with Multilingual Semantic Embeddings
Authors: Shukla Sakshi Deo , Denisov Pavel , Turan Tugtekin
Published: October 2024

Recent advancements in speech-based topic segmentation have highlighted the potential of pretrained speech encoders to capture semantic representations directly from speech. Traditionally, topic segmentation has relied on a pipeline approach in which transcripts of the automatic speech recognition systems are generated, followed by text-based segmentation algorithms. In this paper, we introduce an end-to-end scheme that bypasses this conventional two-step process by directly employing semantic speech encoders for segmentation. Focused on the broadcasted news domain, which poses unique challenges due to the diversity of speakers and topics within single recordings, we address the challenge of accessing topic change points efficiently in an end-to-end manner. Furthermore, we propose a new benchmark for spoken news topic segmentation by utilizing a dataset featuring approximately 1000 hours of publicly available recordings across six European languages and including an evaluation set in Hindi to test the model’s cross-domain performance in a cross-lingual, zero-shot scenario. This setup reflects real-world diversity and the need for models adapting to various linguistic settings. Our results demonstrate that while the traditional pipeline approach achieves a state-of-the-art Pk score of 0.2431 for English, our end-to-end model delivers a competitive Pk score of 0.2564. When trained multilingually, these scores further improve to 0.1988 and 0.2370, respectively. To support further research, we release our model along with data preparation scripts, facilitating open research on multilingual spoken news topic segmentation.
ALOE: Boosting Large Language Model Fine-Tuning with Aggressive Loss-Based Elimination of Samples
Authors: Demidovskij Alexander , Trutnev Aleksei , Tugaryov Artyom , Salnikov Igor
Published: October 2024

As modern neural network training and fine-tuning requires a lot of computational resources, there is a huge demand for novel, specialized algorithms for efficient and cost-effective training procedures. Aggressive Loss-based Elimination of Samples (ALOE) is an innovative method that operates with training samples based on losses obtained from a currently trained model or a pre-trained one. ALOE is designed to accelerate the fine-tuning process of Large Language Models and is perfectly integrated with the state-of-the-art Parameter-Efficient Fine-Tuning method LoRA. ALOE is a two-stage fine-tuning acceleration method. The two stages of ALOE are called offline and online. The proposed method is based on the idea that reducing the number of samples due to a certain rule decreases the number of training steps, thus reducing the overall fine-tuning time for LLM. This reduction allows to either get a fine-tuned version of the model faster or to perform more training iterations within the same time period as the fine-tuning baseline (ALOE Max). The ALOE (Offline) performs dataset reduction before the fine-tuning starts, while the ALOE (Online) selects the training samples from each training batch during the fine-tuning process. Results demonstrate significant acceleration by 45.6% in average across 6 models: GPT-2 S, GPT-2 M, DeBERTa-V2-XL, LLaMA-7B, LLaMA-2-7B, LLaMA-2-13B with average accuracy improvement by 5.91% in comparison to the fine-tuning results obtained with the use of LoRA method. ALOE (Offline) is able to accelerate GPT-2 M E2E-NLG fine-tuning by up to 92% with 1.2% BLEU improvement.
BiLEE: Bi-Level Early Exiting for Generative Document Retrieval
Authors: Fang Rui , Yeh Chin-Yuan , Chen Hsi-Wen , Chen Ming-Syan
Published: October 2024

Generative document retrieval (GDR) uses pre-trained Transformer-based large language models (LLMs) to extract contextual information and directly predict document identifier token sequences, outperforming traditional document retrieval methods. However, LLMs incur significant computational costs, hindering GDR’s practical application and making inference acceleration essential. Early exiting is one of the conditional computing techniques that expedites LLM inference, but it faces challenges when integrated into GDR due to GDR’s semantically hierarchical structured identifiers, which cause error amplification from premature exits. Moreover, although beam search expands the search space, the hierarchical structure of document identifiers restricts the diversity of initial tokens, leading to inefficiencies. In this work, we introduce Bi-Level Early Exiting for Generative Document Retrieval (BiLEE), comprising Layer Level Early Exiting (LLEE) and Token Level Early Exiting (TLEE). LLEEare designed for hierarchical document identifiers, dynamically escaping from the middle layer of the Transformer calculation based on a data-driven calibrated token threshold. TLEE exiting from unpromising candidate sequences, thus discarding unpromising search beams and enhancing beam search efficiency. Both components dynamically balance the speed-to-accuracy trade-offs for different token positions, doubling GDR’s inference speed and obtaining 13× reduction for FLOPs while maintaining the same level of accuracy. Source code: https://github.com/Rui-Fang/BiLEE.
Improving the Performance of Transformer-Based Models Over Classical Baselines in Multiple Transliterated Languages
Authors: Ahmed Fahim , Fahim Md , Amin Md Ashraful , Ali Amin Ahsan , Rahman AKM Mahabubur
Published: October 2024

Social media users express their feelings, experiences, ideas, and stories with little or no regard for the conventions of traditional grammar. Online discourse, by its very nature, is rife with transliterated text along with code-mixing and code-switching. Transliteration is heavily featured due to the ease of inputting romanized text with standard keyboards over native scripts. Due to its ubiquity, it is a critical area of study to ensure NLP models perform well in real-world scenarios. In this paper, we analyze the performance of various language models, Tiny Large Language models, TF-IDF and Bag-of-Words feature extraction-based classical ML models, as well as zero-shot classification with ChatGPT on romanized/transliterated social media text. We chose the tasks of sentiment analysis and offensive language identification and we carried out experiments for three different languages, namely Bangla, Hindi, and Arabic, for six datasets. To our surprise, we discovered across multiple datasets that the non-neural methods perform very competitively with fine-tuned transformer-based mono/multilingual language models, tiny large language models, and ChatGPT for classification tasks in transliterated text. These classical models train in seconds using only a fraction of the computing power, and thus the carbon footprint, required by language models. We demonstrate TF-IDF and BoW-based classifiers achieve performance within around 3% of fine-tuned LMs and could thus be considered as a strong baseline for transliterated text-based NLP tasks. Additionally, we investigated various mitigation strategies such as translation and augmentation via the use of ChatGPT, as well as Masked Language Modelling to dataset-specific pretraining for language models. Depending on the dataset and language, employing those mitigation techniques yields a 2-3% further improvement in accuracy and macro-F1 above baseline.
Planning with Logical Graph-Based Language Model for Instruction Generation
Authors: Zhang Fan , Jin Kebing , Zhuo Hankz Hankui
Published: October 2024

Despite the superior performance of large language models to generate natural language texts, it is hard to generate texts with correct logic according to a given task, due to the difficulties for neural models to capture strict logic from free-form texts. In this paper, we propose a novel graph-based language model, Logical-GLM, to extract strict logic from free-form texts and then infuse into language models. Specifically, we first capture information from natural language instructions and construct logical probability graphs that generally describe domains. Next, we generate logical skeletons to guide language model training, infusing domain knowledge into language models. At last, we alternately optimize the searching policy of graphs and language models until convergence. The experimental results show that Logical-GLM is both effective and efficient compared with traditional language models, despite using smaller-scale training data and fewer parameters. Our approach can generate instructional texts with more correct logic owing to the internalized domain knowledge. Moreover, the search of logical graphs reflects the inner mechanism of the language models, which improves the interpretability of black-box models.
Decision-Focused Learning to Predict Action Costs for Planning
Authors: Mandi Jayanta , Foschini Marco , Höller Daniel , Thiebaux Sylvie , Hoffmann Jörg , Guns Tias
Published: October 2024

In many automated planning applications, action costs can be hard to specify. An example is the time needed to travel through a certain road segment, which depends on many factors, such as the current weather conditions. A natural way to address this issue is to learn to predict these parameters based on input features (e.g., weather forecasts) and use the predicted action costs in automated planning afterward. Decision-Focused Learning (DFL) has been successful in learning to predict the parameters of combinatorial optimization problems in a way that optimizes solution quality rather than prediction quality. This approach yields better results than treating prediction and optimization as separate tasks. In this paper, we investigate for the first time the challenges of implementing DFL for automated planning in order to learn to predict the action costs. There are two main challenges to overcome:  (1) planning systems are called during gradient descent learning, to solve planning problems with negative action costs, which are not supported in planning. We propose novel methods for gradient computation to avoid this issue.  (2) DFL requires repeated planner calls during training, which can limit the scalability of the method. We experiment with different methods approximating the optimal plan as well as an easy-to-implement caching mechanism to speed up the learning process. As the first work that addresses DFL for automated planning, we demonstrate that the proposed gradient computation consistently yields significantly better plans than predictions aimed at minimizing prediction error; and that caching can temper the computation requirements.
Heuristics for Partially Observable Stochastic Contingent Planning
Authors: Shani Guy
Published: October 2024

Acting to complete tasks in stochastic partially observable domains is an important problem in artificial intelligence, and is often formulated as a goal-based POMDP. Goal-based POMDPs can be solved using the RTDP-BEL algorithm, that operates by running forward trajectories from the initial belief to the goal. These trajectories can be guided by a heuristic, and more accurate heuristics can result in significantly faster convergence. In this paper, we develop a heuristic function that leverages the structured representation of domain models. We compute, in a relaxed space, a plan to achieve the goal, while taking into account the value of information, as well as the stochastic effects. We provide experiments showing that while our heuristic is slower to compute, it requires an order of magnitude less trajectories before convergence. Overall, it thus speeds up RTDP-BEL, particularly in problems where significant information gathering is needed.
Using Backdoors to Generate Learnt Information in SAT Solving
Authors: Andreev Alexander , Chukharev Konstantin , Kochemazov Stepan , Semenov Alexander
Published: October 2024

Backdoors for SAT, proposed by Williams et al. in 2003, are the sets of variables, the instantiation of which vastly simplifies the resulting subproblem. The focus of the present paper are ρ-backdoors — the probabilistic generalization of Strong Backdoor Sets. Unlike most kinds of backdoors, small ρ-backdoors with ρ > 0 are relatively easy to find and they can be found in many formulas. In the theoretical part of the paper, we show that there exists a connection between ρ-backdoors and the conflict information generated by CDCL SAT solvers. On the one hand, any set of variables appearing in some learnt clauses can be viewed as a ρ-backdoor (with ρ > 0) with respect to the Unit Propagation (UP) rule. On the other hand, surprisingly, ρ-backdoors can often be used to generate logical entailments of a formula, which can be viewed as learnt clauses, and we present several techniques and algorithms, that can be used to derive such clauses. We also show that a ρ-backdoor with ρ > 0 can be considered as a partial unsatisfiability certificate for a CNF formula as it proves that the formula is false for the fraction of at least ρ of all possible assignments. Therefore, from the practical viewpoint, finding ρ-backdoors with ρ close to 1 makes sense. To evaluate the proposed techniques, we implemented a proof-of-concept prototype, that interleaves the backdoor-based techniques with standard CDCL solving, and evaluated it on a variety of challenging benchmarks. The results of the experiments show that the proposed technique makes it possible to speed up the SAT solving for many hard SAT instances both from SAT Competitions and of industrial origin.