Large Language Models (LLMs) have revolutionized the field of natural language processing, achieving unprecedented performance across a variety of applications. However, their increased computational and memory demands present significant challenges, especially when handling long sequences. This paper focuses on the long-context scenario, addressing the inefficiencies in KV cache memory consumption during inference. Unlike existing approaches that optimize the memory based on the sequence length, we identify substantial redundancy in the channel dimension of the KV cache, as indicated by an uneven magnitude distribution and a low-rank structure in the attention weights. In response, we propose ThinK, a novel query-dependent KV cache pruning method designed to minimize attention weight loss while selectively pruning the least significant channels. Our approach not only maintains or enhances model accuracy but also achieves a reduction in KV cache memory costs by over 20\% compared with vanilla KV cache eviction and quantization methods. For instance, ThinK integrated with KIVI can achieve $2.8\times$ peak memory reduction while maintaining nearly the same quality, enabling a batch size increase from 4$\times$ (with KIVI alone) to 5$\times$ when using a single GPU. Extensive evaluations on the LLaMA and Mistral models across various long-sequence datasets verified the efficiency of ThinK. Our code has been made available at https://github.com/SalesforceAIResearch/ThinK.

One way to enhance the reasoning capability of Large Language Models (LLMs) is to conduct Supervised Fine-Tuning (SFT) using Chain-of-Thought (CoT) annotations.This approach does not show sufficiently strong generalization ability, however, because the training only relies on the given CoT data.In math problemsolving, for example, there is usually only one annotated reasoning path for each question in the training data.Intuitively, it would be better for the algorithm to learn from multiple annotated reasoning paths given a question.To address this issue, we propose a simple yet effective approach called Reinforced Fine-Tuning (ReFT) to enhance the generalizability of learning LLMs for reasoning, with math problemsolving as an example.ReFT first warmups the model with SFT, and then employs on-line reinforcement learning, specifically the PPO algorithm in this paper, to further fine-tune the model, where an abundance of reasoning paths are automatically sampled given the question and the rewards are naturally derived from the ground-truth answers.Extensive experiments on GSM8K, MathQA, and SVAMP datasets show that ReFT significantly outperforms SFT, and the performance can be potentially further boosted by combining inference-time strategies such as majority voting and re-ranking.Note that ReFT obtains the improvement by learning from the same training questions as SFT, without relying on extra or augmented training questions.This indicates a superior generalization ability for ReFT 1 .* indicates equal contribution, † indicates corresponding author 1 Code: https://github.com/lqtrung1998/mwp_ReFTSupervised Fine-Tuning Model Question (x): Weng earns $12 an hour for babysitting.Yesterday, she just did 50 minutes of babysitting.How much did she earn?

Solving math word problems requires deductive reasoning over the quantities in the text.Various recent research efforts mostly relied on sequence-to-sequence or sequence-to-tree models to generate mathematical expressions without explicitly performing relational reasoning between quantities in the given context.While empirically effective, such approaches typically do not provide explanations for the generated expressions.In this work, we view the task as a complex relation extraction problem, proposing a novel approach that presents explainable deductive reasoning steps to iteratively construct target expressions, where each step involves a primitive operation over two quantities defining their relation.Through extensive experiments on four benchmark datasets, we show that the proposed model significantly outperforms existing strong baselines.We further demonstrate that the deductive procedure not only presents more explainable steps but also enables us to make more accurate predictions on questions that require more complex reasoning.1

Dependency parse trees are helpful for discovering the opinion words in aspect-based sentiment analysis (ABSA) (Huang and Carley, 2019).However, the trees obtained from offthe-shelf dependency parsers are static, and could be sub-optimal in ABSA.This is because the syntactic trees are not designed for capturing the interactions between opinion words and aspect words.In this work, we aim to shorten the distance between aspects and corresponding opinion words by learning an aspect-centric tree structure.The aspect and opinion words are expected to be closer along such tree structure compared to the standard dependency parse tree.The learning process allows the tree structure to adaptively correlate the aspect and opinion words, enabling us to better identify the polarity in the ABSA task.We conduct experiments on five aspectbased sentiment datasets, and the proposed model significantly outperforms recent strong baselines.Furthermore, our thorough analysis demonstrates the average distance between aspect and opinion words are shortened by at least 19% on the standard SemEval Restau-rant14 (Pontiki et al., 2014) dataset 1 .

It has been shown that named entity recognition (NER) could benefit from incorporating the long-distance structured information captured by dependency trees.We believe this is because both types of features -the contextual information captured by the linear sequences and the structured information captured by the dependency trees may complement each other.However, existing approaches largely focused on stacking the LSTM and graph neural networks such as graph convolutional networks (GCNs) for building improved NER models, where the exact interaction mechanism between the two different types of features is not very clear, and the performance gain does not appear to be significant.In this work, we propose a simple and robust solution to incorporate both types of features with our Synergized-LSTM (Syn-LSTM), which clearly captures how the two types of features interact.We conduct extensive experiments on several standard datasets across four languages.The results demonstrate that the proposed model achieves better performance than previous approaches while requiring fewer parameters.Our further analysis demonstrates that our model can capture longer dependencies compared with strong baselines.1

Previous works on knowledge-to-text generation take as input a few RDF triples or keyvalue pairs conveying the knowledge of some entities to generate a natural language description.Existing datasets, such as WIKIBIO, WebNLG, and E2E, basically have a good alignment between an input triple/pair set and its output text.However, in practice, the input knowledge could be more than enough, since the output description may only cover the most significant knowledge.In this paper, we introduce a large-scale and challenging dataset to facilitate the study of such a practical scenario in KG-to-text.Our dataset involves retrieving abundant knowledge of various types of main entities from a large knowledge graph (KG), which makes the current graph-to-sequence models severely suffer from the problems of information loss and parameter explosion while generating the descriptions.We address these challenges by proposing a multi-graph structure that is able to represent the original graph information more comprehensively.Furthermore, we also incorporate aggregation methods that learn to extract the rich graph information.Extensive experiments demonstrate the effectiveness of our model architecture.1

Zhanming Jie, Wei Lu. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

We propose a novel dependency-based hybrid tree model for semantic parsing, which converts natural language utterance into machine interpretable meaning representations.Unlike previous state-of-the-art models, the semantic information is interpreted as the latent dependency between the natural language words in our joint representation.Such dependency information can capture the interactions between the semantics and natural language words.We integrate a neural component into our model and propose an efficient dynamicprogramming algorithm to perform tractable inference.Through extensive experiments on the standard multilingual GeoQuery dataset with eight languages, we demonstrate that our proposed approach is able to achieve state-ofthe-art performance across several languages.Analysis also justifies the effectiveness of using our new dependency-based representation. 1

Named entity recognition (NER), which focuses on the extraction of semantically meaningful named entities and their semantic classes from text, serves as an indispensable component for several down-stream natural language processing (NLP) tasks such as relation extraction and event extraction. Dependency trees, on the other hand, also convey crucial semantic-level information. It has been shown previously that such information can be used to improve the performance of NER. In this work, we investigate on how to better utilize the structured information conveyed by dependency trees to improve the performance of NER. Specifically, unlike existing approaches which only exploit dependency information for designing local features, we show that certain global structured information of the dependency trees can be exploited when building NER models where such information can provide guided learning and inference. Through extensive experiments, we show that our proposed novel dependency-guided NER model performs competitively with models based on conventional semi-Markov conditional random fields, while requiring significantly less running time.

Billions of user-shared images are generated by individuals in many social networks today, and this particular form of user data is widely accessible to others due to the nature of online social sharing. When user social graphs are only accessible to exclusive parties, these user-shared images are proved to be an easier and effective alternative to discover user connections. This work investigated over 360 000 user shared images from two social networks, Skyrock and 163 Weibo, in which 3 million follower/ followee relationships are involved. It is observed that the shared images from users with a follower / followee relationship show relatively higher similarities . A multimedia big data system that utilizes this observed phenomenon is proposed as an alternative to user- generated tags and social graphs for follower/followee recommendation and gender identification. To the best of our knowledge, this is the first attempt in this field to prove and formulate such a phenomenon for mass user-shared images along with more practical prediction methods. These findings are useful for information or services recommendations in any social network with intensive image sharing, as well as for other interesting personalization applications, particularly when there is no access to those exclusive user social graphs.