Finetuning language models on a collection of datasets phrased as instructions has been shown to improve model performance and generalization to unseen tasks. In this paper we explore instruction finetuning with a particular focus on (1) scaling the number of tasks, (2) scaling the model size, and (3) finetuning on chain-of-thought data. We find that instruction finetuning with the above aspects dramatically improves performance on a variety of model classes (PaLM, T5, U-PaLM), prompting setups (zero-shot, few-shot, CoT), and evaluation benchmarks (MMLU, BBH, TyDiQA, MGSM, open-ended generation, RealToxicityPrompts). For instance, Flan-PaLM 540B instruction-finetuned on 1.8K tasks outperforms PaLM 540B by a large margin (+9.4% on average). Flan-PaLM 540B achieves state-of-the-art performance on several benchmarks (at time of release), such as 75.2% on five-shot MMLU. We also publicly release Flan-T5 checkpoints,1 which achieve strong few-shot performance even compared to much larger models, such as PaLM 62B. Overall, instruction finetuning is a general method for improving the performance and usability of pretrained language models.

Joshua Ainslie, Tao Lei, Michiel de Jong, Santiago Ontanon, Siddhartha Brahma, Yury Zemlyanskiy, David Uthus, Mandy Guo, James Lee-Thorp, Yi Tay, Yun-Hsuan Sung, Sumit Sanghai. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

We propose Conditional Adapter (CoDA), a parameter-efficient transfer learning method that also improves inference efficiency. CoDA generalizes beyond standard adapter approaches to enable a new way of balancing speed and accuracy using conditional computation. Starting with an existing dense pretrained model, CoDA adds sparse activation together with a small number of new parameters and a light-weight training phase. Our experiments demonstrate that the CoDA approach provides an unexpectedly efficient way to transfer knowledge. Across a variety of language, vision, and speech tasks, CoDA achieves a 2x to 8x inference speed-up compared to the state-of-the-art Adapter approaches with moderate to no accuracy loss and the same parameter efficiency.

Prithviraj Sen, Marina Danilevsky, Yunyao Li, Siddhartha Brahma, Matthias Boehm, Laura Chiticariu, Rajasekar Krishnamurthy. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). 2020.

Split and Rephrase is a text simplification task of rewriting a complex sentence into simpler ones.As a relatively new task, it is paramount to ensure the soundness of its evaluation benchmark and metric.We find that the widely used benchmark dataset universally contains easily exploitable syntactic cues caused by its automatic generation process.Taking advantage of such cues, we show that even a simple rule-based model can perform on par with the state-of-the-art model.To remedy such limitations, we collect and release two crowdsourced benchmark datasets.We not only make sure that they contain significantly more diverse syntax, but also carefully control for their quality according to a welldefined set of criteria.While no satisfactory automatic metric exists, we apply fine-grained manual evaluation based on these criteria using crowdsourcing, showing that our datasets better represent the task and are significantly more challenging for the models. 1

Highly regularized LSTMs achieve impressive results on several benchmark datasets in language modeling.We propose a new regularization method based on decoding the last token in the context using the predicted distribution of the next token.This biases the model towards retaining more contextual information, in turn improving its ability to predict the next token.With negligible overhead in the number of parameters and training time, our Past Decode Regularization (PDR) method improves perplexity on the Penn Treebank dataset by up to 1.8 points and by up to 2.3 points on the WikiText-2 dataset, over strong regularized baselines using a single softmax.With a mixture-of-softmax model, we show gains of up to 1.0 perplexity points on these datasets.In addition, our method achieves 1.169 bits-per-character on the Penn Treebank Character dataset for character level language modeling.Each of these results constitute improvements over models without PDR in their respective settings.

In this paper, we look at how we can leverage Spark platform for efficiently processing fine-grained provenance queries on large volumes of workflow provenance data. Simple recursive querying based Spark solutions involve large data scanning cost and hence do not work well. We propose a novel provenance framework which is engineered to quickly determine a small volume of data containing the entire lineage of the queried data-item. This small volume of data is then recursively processed to figure out the provenance of the queried data-item. We study the effectiveness of the proposed framework on a provenance trace obtained from a financial domain text curation workflow and report our observations. We show that the proposed framework easily outperforms the naive approaches.

We consider the allocation of coded data over nodes in a distributed storage system under a budget constraint. A system with failed nodes can recover the original data of unit size if the amount of data in the active nodes is at least a unit. Building on the work of Leong et al. [1], we introduce the concepts of tight allocations and repair bandwidth in this distributed setting. For tight allocations, the amount of data in the failed nodes gives a lower bound to the repair bandwidth required to put the system back to its original state. Using this bound, we define the Minimum Expected Repair Bandwidth (MERB) to study the tradeoffs between reliability and repair bandwidth, both empirically and by proving bounds on MERB in terms of the reliability. We show that even computing MERB for a general allocation is #P-Hard and suggest a simpler objective function to optimize it approximately. Finally, we study the asymptotic behavior of MERB for large systems and show two distinct optimal allocation regimes depending on the failure probability of the storage nodes.

We consider an n-relay Gaussian diamond network where a source communicates to a destination with the help of n half-duplex relays. Achieving rates close to the capacity of this network requires to employ all the n relays under an optimal transmit/receive schedule. Even for the moderate values of n, this can have significant operational complexity as the optimal schedule may possibly have 2ndifferent states for the network (since each of the relays can be in either transmitting or receiving mode). In this paper, we investigate whether a significant fraction of the network capacity can be achieved by using transmit/receive schedules that have only few active states and by using only few relays. First, we conjecture that the approximately optimal schedule has at most n+1 states instead of the 2npossible states. We prove this conjecture for networks of size n ≤ 6 by developing a proof strategy and implementing it computationally. Second, we show that routing strategies that only employ the point-to-point communication and two of the relays with a half-duplex schedule that has only two active states can achieve at least half the capacity (approximately) of the network. Techniques from linear programming and submodular functions are used to derive the results.

We formulate a new variant of the index coding problem, where instead of demanding a specific message, clients are pliable, and are interested in receiving any t messages that they do not have. We term this problem pliable index coding or PICOD(t). We prove that, with this formulation, although some instances of the problem become simple, in general, the problem of finding the optimal linear code remains NP-hard. However, we show that it is possible to construct pliable index codes that are substantially smaller than index codes in many cases. If there are n clients, the server has m messages, and each client has a side information set of cardinality s ≤ m - t; we show that O(min{t log n, t + log2n}) broadcast transmissions are sufficient to satisfy all the clients. For t = 1, this is an exponential improvement over the n messages required in index coding in the worst case (for m = n). In addition, for t ≫ log2n, the number of broadcast transmissions required is only linearly dependent on t. We generalize the results to instances where the side information sets are not necessarily of equal cardinality. When m = O(nδ), for some constant δ > 0, we show that the codes of size O(min{t log2n, t log n + log3n}) are sufficient in general. We also consider the scenario when the server only knows the cardinality of the side information sets of the clients and each client is interested in receiving any t messages that it does not have. We term this formulation oblivious pliable index coding or OB-PICOD(t). If the cardinalities of side information sets of all the clients is s (with s ≤ m - t), then we show that min{s + t, m - s} messages are both sufficient and necessary for linear codes. Finally, we develop efficient heuristic approximation algorithms for PICOD(t) and show through simulations on the random instances of PICOD(t) that they perform well in practice.

Physical layer cooperation of a source with a relay can significantly boost the performance of a wireless connection. However, the best practical relaying scheme can vary depending on the relative strengths of the channels that connect the source, relay and destination. This paper proposes and evaluates QUILT, a system for physical-layer relaying that seamlessly adapts to the underlying network configuration to achieve competitive or better performance as compared to the best current approaches. QUILT combines on-demand, opportunistic use of Decode-Forward (DF) or Quantize-Map-Forward (QMF) followed by interleaving at the relay, with hybrid decoding at the destination that extracts information from received frames even if these are not decodable. We theoretically quantify how our design choices for QUILT affect the system performance. We also deploy QUILT on the WarpLab software radio platform, and show through over-the-air experiments up to 5 times FER improvement over the next best cooperative protocol.

We consider Gaussian diamond networks with n half-duplex relays. At any point of time, a relay can either be in a listening (L) or transmitting (T) state. The capacity of such networks can be approximated to within a constant gap (independent of channel SNRs) by solving a linear program that optimizes over the 2nrelaying states. We recently conjectured, and proved for the cases of n = 2, 3, that there exist optimal schedules with at most n+1 active states, instead of the possible 2n. In this paper we develop a computational proof strategy that relies on submodularity properties of information flow across cuts in the network and linear programming duality to resolve the conjecture. We implement the strategy for n = 4, 5, 6 and show that indeed there exist optimal schedules with at most n+1 active states in these cases.

We consider a Gaussian diamond network where a source communicates with the destination through n noninterfering half-duplex relays. Using simple approximations to the capacity of the network, we show that simple relaying strategies involving two relays and two scheduling states can achieve at least half the capacity of the whole network, independent of channel SNRs. The proof uses linear programming duality and implies an algorithm to find such a pair of relays in O(n log n) time.

We consider a source that would like to communicate with a destination over a layered Gaussian relay network.We present a computationally efficient method that enables to select a near-optimal (in terms of throughput) subnetwork of a given size connecting the source with the destination. Our method starts by formulating an integer optimization problem that maximizes the rates that the Quantize-Map-and-Forward relaying protocol can achieve over a selected subnetwork; we then relax the integer constraints to obtain a non-linear optimization over reals. For diamond networks, we prove that this optimization over reals is concave while for general layered networks we give empirical demonstrations of near-concavity, paving the way for efficient algorithms to solve the relaxed problem. We then round the relaxed solution to select a specific subnetwork. Simulations using off-the-shelf non-linear optimization algorithms demonstrate excellent performance with respect to the true integer optimum for both diamond networks as well as multi-layered networks. Even with these non-customized algorithms, significant time savings are observed vis-à-vis exhaustive integer optimization.

We consider a Gaussian diamond network where a source communicates with the destination through n non-interfering half-duplex relays. We focus on half-duplex schedules that utilize only local channel state information, i.e., each relay has access to its incoming and outgoing channel realizations. We demonstrate that random independent switching, resulting in multiple listen-transmit sub cycles at each relay, while still respecting the overall locally optimal listen-transmit fractions, enables to approximately achieve at least 3/4 of the capacity of the 2-relay diamond network. With a single listen-transmit cycle, this fraction drops from 3/4 to 1/2. We also provide simulation results that point to the same fractions of capacity being retained over networks with more than 2 relays.

The Pliable Index Coding problem is a recently proposed new formulation of the Index Coding problem where each client wants any one message that it does not have and the server tries to “satisfy” all the clients using the side information sets of each of the clients by broadcasting coded messages. We present two generalizations of the problem. Firstly, we consider the problem of each client requiring any t messages (t ≥ 1) that it does not have. If the cardinality of their side information sets is the same and there are n messages, then we show that O(min(t log n, t + log2n)) coded broadcast messages are sufficient. For t ≥ log n, this shows a linear dependence on t independent of n. We also develop simple approximation algorithms for the problem and evaluate their performance through simulations. Secondly, we consider the problem of the server having incomplete side information. If the server only knows the size s of the side information sets (assumed to be all equal), we show that there exists a linear code using min(s + 1, n - s) coded messages. We also show that this is tight for linear codes by proving a matching lower bound.

We present the design and experimental evaluation of a wireless system that exploits relaying in the context of WiFi. We opt for WiFi given its popularity and wide spread use for a number of applications, such as smart homes. Our testbed consists of three nodes, a source, a relay and a destination, that operate using the physical layer procedures of IEEE802.11. We deploy three main competing strategies that have been proposed for relaying, Decode-and-Forward (DF), Amplify-and-Forward (AF) and Quantize-Map-Forward (QMF). QMF is the most recently introduced of the three, and although it was shown in theory to approximately achieve the capacity of arbitrary wireless networks, its performance in practice had not been evaluated. We present in this work experimental results---to the best of our knowledge, the first ones---that compare QMF, AF and DF in a realistic indoor setting. We find that QMF is a competitive scheme to the other two, offering in some cases up to 12% throughput benefits and up to 60% improvement in frame error-rates over the next best scheme.

We propose a new formulation of the index coding problem, where instead of demanding a specific bit (or message), clients are “pliable” and are happy to receive any one bit they do not have. We prove that with this relaxation, although some instances of this problem become simple, in general the problem of finding the optimal linear code remains NP-hard. We also show that if the server has n bits, O(log n log(n/log n)) coded bit transmissions are sufficient to satisfy the clients in the worst case, in contrast to the Ω(n) transmissions required in index coding. We develop several approximation algorithms and evaluate their performance through simulations.

Abstract—We consider the diamond network where a source communicates with the destination through N non-interfering half-duplex relays. Using simple outer bounds on the capacity of the network, we show that simple relaying strategies having exactly two states and avoiding broadcast and multiple access communication can still achieve a significant constant fraction of the capacity of the 2 relay network, independent of the SNR values. The results are extended to the case of 3 relays for the special class of antisymmetric networks. We also study the structure of (approximately) optimal relaying strategies for such networks. Simulations show that optimal schedules have at most N +1 states, which we conjecture to be true in general. We prove the conjecture for N =2and in special cases for N =3. I.

We present a structured Quantize-Map-and-Forward (QMF) scheme for cooperative communication over wireless networks, that employs LDPC ensembles for the node operations and message-passing algorithms for decoding. We demonstrate through extensive simulation results over the full-duplex parallel relay network, that our scheme, with no transmit channel state information, offers a robust performance over fading channels and achieves the full diversity order of our network at moderate SNRs.

This work deals with multisensor data fusion to obtain landcover classification. The role of feature-level fusion using the Dempster-Shafer rule and that of data-level fusion in the MRF context is studied in this paper to obtain an optimally segmented image. Subsequently, segments are validated and classification accuracy for the test data is evaluated. Two examples of data fusion of optical images and a synthetic aperture radar image are presented, each set having been acquired on different dates. Classification accuracies of the technique proposed are compared with those of some recent techniques in literature for the same image data.