Search

Cross encoders (CEs) are trained with sentence pairs to detect relatedness. As CEs require sentence pairs at inference, the prevailing view is that they can only be used as re-rankers in information retrieval pipelines. Dual encoders (DEs) are instead used to embed sentences, where sentence pairs are encoded by two separate encoders with shared weights at training, and a loss function that ensures the pair's embeddings lie close in vector space if the sentences are related. DEs however, require much larger datasets to train, and are less accurate than CEs. We report a curious finding that embeddings from earlier layers of CEs can in fact be used within an information retrieval pipeline. We show how to exploit CEs to distill a lighter-weight DE, with a 5.15x speedup in inference time.

Transformer-based video super-resolution (VSR) models have set new benchmarks in recent years, but their substantial computational demands make most of them unsuitable for deployment on resource-constrained devices. Achieving a balance between model complexity and output quality remains a formidable challenge in VSR. Although lightweight models have been introduced to address this issue, they often struggle to deliver state-of-the-art performance. We propose a novel lightweight, parameter-efficient deep residual deformable convolution network for VSR. Unlike prior methods, our model enhances feature utilization through residual connections and employs deformable convolution for precise frame alignment, addressing motion dynamics effectively. Furthermore, we introduce a single memory tensor to capture information accrued from the past frames and improve motion estimation across frames. This design enables an efficient balance between computational cost and reconstruction quality. With just 2.3 million parameters, our model achieves state-of-the-art SSIM of 0.9175 on the REDS4 dataset, surpassing existing lightweight and many heavy models in both accuracy and resource efficiency. Architectural insights from our model pave the way for real-time VSR on streaming data.

Many dynamical systems exhibit unexpected large amplitude excursions in the chronological progression of a state variable. In the present work, we consider the dynamics associated with the one-dimensional Higgs oscillator which is realized through gnomic projection of a harmonic oscillator defined on a spherical space of constant curvature onto a Euclidean plane which is tangent to the spherical space. While studying the dynamics of such a Higgs oscillator subjected to damping and an external forcing, various bifurcation phenomena, such as symmetry breaking, period doubling, and intermittency crises are encountered. As the driven parameter increases, the route to chaos takes place via intermittency crisis and we also identify the occurrence of extreme events due to the interior crisis. The study of probability distribution also confirms the occurrence of extreme events. Finally, we train the Long Short-Term Memory neural network model with the time-series data to forecast the extreme events (EEs)., Comment: Accepted for Publication in Chaos: An Interdisciplinary Journal of Nonlinear Science

Recommender systems create enormous value for businesses and their consumers. They increase revenue for businesses while improving the consumer experience by recommending relevant products amidst huge product base. Product bundling is an exciting development in the field of product recommendations. It aims at generating new bundles and recommending exciting and relevant bundles to their consumers. Unlike traditional recommender systems that recommend single items to consumers, product bundling aims at targeting a bundle, or a set of items, to the consumers. While bundle recommendation has attracted significant research interest recently, extant literature on bundle generation is scarce. Moreover, metrics to identify if a bundle is popular or not is not well studied. In this work, we aim to fulfill this gap by introducing new bundle popularity metrics based on sales, consumer experience and item diversity in a bundle. We use these metrics in the methodology proposed in this paper to generate new bundles for mobile games using content aware and context aware embeddings. We use opensource Steam Games dataset for our analysis. Our experiments indicate that we can generate new bundles that can outperform the existing bundles on the popularity metrics by 32% - 44%. Our experiments are computationally efficient and the proposed methodology is generic that can be extended to other bundling problems e.g. product bundling, music bundling.

Fidelity quantum kernels have shown promise in classification tasks, particularly when a group structure in the data can be identified and exploited through a covariant feature map. In fact, there exist classification problems on which covariant kernels provide a provable advantage, thus establishing a separation between quantum and classical learners. However, their practical application poses two challenges: on one side, the group structure may be unknown and approximate in real-world data, and on the other side, scaling to the `utility' regime (above 100 qubits) is affected by exponential concentration. In this work, we address said challenges by applying fidelity kernels to real-world data with unknown structure, related to the scheduling of a fleet of electric vehicles, and to synthetic data generated from the union of subspaces, which is then close to many relevant real-world datasets. Furthermore, we propose a novel error mitigation strategy specifically tailored for fidelity kernels, called Bit Flip Tolerance (BFT), to alleviate the exponential concentration in our utility-scale experiments. Our multiclass classification reaches accuracies comparable to classical SVCs up to 156 qubits, thus constituting the largest experimental demonstration of quantum machine learning on IBM devices to date. For the real-world data experiments, the effect of the proposed BFT becomes manifest on 40+ qubits, where mitigated accuracies reach 80%, in line with classical, compared to 33% without BFT. Through the union-of-subspace synthetic dataset with 156 qubits, we demonstrate a mitigated accuracy of 80%, compared to 83% of classical models, and 37% of unmitigated quantum, using a test set of limited size.

In this paper, we introduce a novel equilibrium concept, called the equilibrium cycle, which seeks to capture the outcome of oscillatory game dynamics. Unlike the (pure) Nash equilibrium, which defines a fixed point of mutual best responses, an equilibrium cycle is a set-valued solution concept that can be demonstrated even in games where best responses do not exist (for example, in discontinuous games). The equilibrium cycle identifies a Cartesian product set of action profiles that satisfies three important properties: stability against external deviations, instability against internal deviations, and minimality. This set-valued equilibrium concept generalizes the classical notion of the minimal curb set to discontinuous games. In finite games, the equilibrium cycle is related to strongly connected sink components of the best response graph.

Message aggregation is often used with a goal to reduce communication cost in HPC applications. The difference in the order of overhead of sending a message and cost of per byte transferred motivates the need for message aggregation, for several irregular fine-grained messaging applications like graph algorithms and parallel discrete event simulation (PDES). While message aggregation is frequently utilized in "MPI-everywhere" model, to coalesce messages between processes mapped to cores, such aggregation across threads in a process, say in MPI+X models or Charm++ SMP (Shared Memory Parallelism) mode, is often avoided. Within-process coalescing is likely to require synchronization across threads and lead to performance issues from contention. However, as a result, SMP-unaware aggregation mechanisms may not fully utilize aggregation opportunities available to applications in SMP mode. Additionally, while the benefit of message aggregation is often analyzed in terms of reducing the overhead, specifically the per message cost, we also analyze different schemes that can aid in reducing the message latency, ie. the time from when a message is sent to the time when it is received. Message latency can affect several applications like PDES with speculative execution where reducing message latency could result in fewer rollbacks. To address these challenges, in our work, we demonstrate the effectiveness of shared memory-aware message aggregation schemes for a range of proxy applications with respect to messaging overhead and latency., Comment: A shorter version of this paper has been accepted at IA^3 workshop at SC24

We consider a matching problem in a bipartite graph $G$ where every vertex has a capacity and a strict preference order on its neighbors. Furthermore, there is a cost function on the edge set. We assume $G$ admits a perfect matching, i.e., one that fully matches all vertices. It is only perfect matchings that are feasible for us and we are interested in those perfect matchings that are popular within the set of perfect matchings. It is known that such matchings (called popular perfect matchings) always exist and can be efficiently computed. What we seek here is not any popular perfect matching, but a min-cost one. We show a polynomial-time algorithm for finding such a matching; this is via a characterization of popular perfect matchings in $G$ in terms of stable matchings in a colorful auxiliary instance. This is a generalization of such a characterization that was known in the one-to-one setting.

This paper investigates the potential benefits of cooperation in scenarios where finitely many agents compete for shared resources, leading to congestion and thereby reduced rewards. By appropriate coordination the members of the cooperating group (a.k.a., coalition) can minimize the congestion losses due to inmates, while efficiently facing the competition from outsiders (coalitions indulge in a non-cooperative congestion game). The quest in this paper is to identify the stable partition of coalitions that are not challenged by a new coalition. In contrast to the traditional cooperative games, the worth of a coalition in our game also depends upon the arrangement of the opponents. Every arrangement leads to a partition and a corresponding congestion game; the resultant Nash equilibria (NEs) dictate the `worth'. The analysis is further complicated due to the presence of multiple NEs for each such game., Comment: 8 pages, 2 figures, Accepted in CDC 2024

There is an increasing body of work using Large Language Models (LLMs) as agents for orchestrating workflows and making decisions in domains that require planning and multi-step reasoning. As a result, it is imperative to evaluate LLMs on core skills required for planning. In this work, we present ACPBench, a benchmark for evaluating the reasoning tasks in the field of planning. The benchmark consists of 7 reasoning tasks over 13 planning domains. The collection is constructed from planning domains described in a formal language. This allows us to synthesize problems with provably correct solutions across many tasks and domains. Further, it allows us the luxury of scale without additional human effort, i.e., many additional problems can be created automatically. Our extensive evaluation of 22 LLMs and OpenAI o1 reasoning models highlights the significant gap in the reasoning capability of the LLMs. Our findings with OpenAI o1, a multi-turn reasoning model, reveal significant gains in performance on multiple-choice questions, yet surprisingly, no notable progress is made on boolean questions. The ACPBench collection is available at https://ibm.github.io/ACPBench., Comment: Added OpenAI o1 results

Planning remains one of the last standing bastions for large language models (LLMs), which now turn their attention to search. Most of the literature uses the language models as world models to define the search space, forgoing soundness for the sake of flexibility. A recent work, Thought of Search (ToS), proposed defining the search space with code, having the language models produce that code. ToS requires a human in the loop, collaboratively producing a sound successor function and goal test. The result, however, is worth the effort: all the tested datasets were solved with 100% accuracy. At the same time LLMs have demonstrated significant progress in code generation and refinement for complex reasoning tasks. In this work, we automate ToS (AutoToS), completely taking the human out of the loop of solving planning problems. AutoToS guides the language model step by step towards the generation of sound and complete search components, through feedback from both generic and domain specific unit tests. We achieve 100% accuracy, with minimal feedback iterations, using LLMs of various sizes on all evaluated domains.

Electric Vehicles (EVs) are emerging as battery energy storage systems (BESSs) of increasing importance for different power grid services. However, the unique characteristics of EVs makes them more difficult to operate than dedicated BESSs. In this work, we apply a data-driven learning approach to leverage EVs as a BESS to provide capacity-related services to the grid. The approach uses machine learning to predict how to charge and discharge EVs while satisfying their operational constraints. As a paradigm application, we use flexible energy commercialization in the wholesale markets, but the approach can be applied to a broader range of capacity-related grid services. We evaluate the proposed approach numerically and show that when the number of EVs is large, we can obtain comparable objective values to CPLEX and approximate dynamic programming, but with shorter run times. These reduced run times are important because they allow us to (re)optimize frequently to adapt to the time-varying system conditions.

Enterprises have a growing need to identify relevant tables in data lakes; e.g. tables that are unionable, joinable, or subsets of each other. Tabular neural models can be helpful for such data discovery tasks. In this paper, we present TabSketchFM, a neural tabular model for data discovery over data lakes. First, we propose novel pre-training: a sketch-based approach to enhance the effectiveness of data discovery in neural tabular models. Second, we finetune the pretrained model for identifying unionable, joinable, and subset table pairs and show significant improvement over previous tabular neural models. Third, we present a detailed ablation study to highlight which sketches are crucial for which tasks. Fourth, we use these finetuned models to perform table search; i.e., given a query table, find other tables in a corpus that are unionable, joinable, or that are subsets of the query. Our results demonstrate significant improvements in F1 scores for search compared to state-of-the-art techniques. Finally, we show significant transfer across datasets and tasks establishing that our model can generalize across different tasks and over different data lakes.

Like text, programs have styles, and certain programming styles are more desirable than others for program readability, maintainability, and performance. Code style transfer, however, is difficult to automate except for trivial style guidelines such as limits on line length. Inspired by the success of using language models for text style transfer, we investigate if code language models can perform code style transfer. Code style transfer, unlike text transfer, has rigorous requirements: the system needs to identify lines of code to change, change them correctly, and leave the rest of the program untouched. We designed CSB (Code Style Benchmark), a benchmark suite of code style transfer tasks across five categories including converting for-loops to list comprehensions, eliminating duplication in code, adding decorators to methods, etc. We then used these tests to see if large pre-trained code language models or fine-tuned models perform style transfer correctly, based on rigorous metrics to test that the transfer did occur, and the code still passes functional tests. Surprisingly, language models failed to perform all of the tasks, suggesting that they perform poorly on tasks that require code understanding. We will make available the large-scale corpora to help the community build better code models.

Inventory control typically considers controlling the price and the production rate. However, such systems have rigidity towards altering the physical storage capacity -- one can not easily alter the physical size after the initial design. The paper focuses on this critical aspect, consideration of which leads to a non-standard control problem. Here, the objective is a weighted combination of the classical integral term (formed by usual inventory costs) and an $L^{\infty}$ term (the maximum inventory level in the entire planning horizon). Our approach is to consider an additional state component to capture the `instantaneous' $L^{\infty}$ term (maximum inventory level till that instant) by virtue of which, we could convert the problem to the classical framework. For the direct ($L^{\infty}$) problem, we first identify a relation between the optimal price and the production rate policy, thereby reducing the dimensionality of the problem. By numerically solving a smooth variant of the converted problem, we obtain an optimal policy that illustrates a significant reduction in the storage capacity requirement. Interestingly, the loss in the revenue is negligible (less than $6\%$). As the importance of the $L^{\infty}$ component increases, the variations in the corresponding optimal inventory-level trajectory reduce. In the scenarios with partial/zero information about future demand curves, the above observation provides a guidance -- one should continually tune the policies to maintain instantaneous inventory-levels as close to zero as possible. With such a policy, the reduction in revenue is negligible, while having significant improvements for storage capacity. We theoretically establish certain interesting properties of the optimal policy, which also support the above guidance.

The classical game theory models rational players and proposes Nash equilibrium (NE) as the solution. However, real-world scenarios rarely feature rational players; instead, players make inconsistent and irrational decisions. Often, irrational players exhibit herding behaviour by simply following the majority. In this paper, we consider the mean-field game with $\alpha$-fraction of rational players and the rest being herding-irrational players. For such a game, we introduce a novel concept of equilibrium named $\alpha$-Rational NE (in short, $\alpha$-RNE). The $\alpha$-RNEs and their implications are extensively analyzed in the game with two actions. Due to herding-irrational players, new equilibria may arise, and some classical NEs may be deleted. The rational players are not harmed but benefit from the presence of irrational players. Notably, we demonstrate through examples that rational players leverage upon the herding behaviour of irrational players and may attain higher utility (under $\alpha$-RNE) than social optimal utility (in the classical setting). Interestingly, the irrational players may also benefit by not being rational. We observe that irrational players do not lose compared to some classical NEs for participation and bandwidth sharing games. More importantly, in bandwidth sharing game, irrational players receive utility that approaches the social optimal utility. Such examples indicate that it may sometimes be `rational' to be irrational., Comment: 8 pages, 3 figure, 1 table

Creating multilingual task-oriented dialogue (TOD) agents is challenging due to the high cost of training data acquisition. Following the research trend of improving training data efficiency, we show for the first time, that in-context learning is sufficient to tackle multilingual TOD. To handle the challenging dialogue state tracking (DST) subtask, we break it down to simpler steps that are more compatible with in-context learning where only a handful of few-shot examples are used. We test our approach on the multilingual TOD dataset X-RiSAWOZ, which has 12 domains in Chinese, English, French, Korean, Hindi, and code-mixed Hindi-English. Our turn-by-turn DST accuracy on the 6 languages range from 55.6% to 80.3%, seemingly worse than the SOTA results from fine-tuned models that achieve from 60.7% to 82.8%; our BLEU scores in the response generation (RG) subtask are also significantly lower than SOTA. However, after manual evaluation of the validation set, we find that by correcting gold label errors and improving dataset annotation schema, GPT-4 with our prompts can achieve (1) 89.6%-96.8% accuracy in DST, and (2) more than 99% correct response generation across different languages. This leads us to conclude that current automatic metrics heavily underestimate the effectiveness of in-context learning.

Among the most important properties of algorithms investigated in computer science are soundness, completeness, and complexity. These properties, however, are rarely analyzed for the vast collection of recently proposed methods for planning with large language models. In this work, we alleviate this gap. We analyse these properties of using LLMs for planning and highlight that recent trends abandon both soundness and completeness for the sake of inefficiency. We propose a significantly more efficient approach that can, at the same time, maintain both soundness and completeness. We exemplify on four representative search problems, comparing to the LLM-based solutions from the literature that attempt to solve these problems. We show that by using LLMs to produce the code for the search components we can solve the entire datasets with 100\% accuracy with only a few calls to the LLM. We argue for a responsible use of compute resources; urging research community to investigate sound and complete LLM-based approaches that uphold efficiency.

The classical dances from India utilize a set of hand gestures known as Mudras, serving as the foundational elements of its posture vocabulary. Identifying these mudras represents a primary task in digitizing the dance performances. With Kathakali, a dance-drama, as the focus, this work addresses mudra recognition by framing it as a 24-class classification problem and proposes a novel vector-similarity-based approach leveraging pose estimation techniques. This method obviates the need for extensive training or fine-tuning, thus mitigating the issue of limited data availability common in similar AI applications. Achieving an accuracy rate of 92%, our approach demonstrates comparable or superior performance to existing model-training-based methodologies in this domain. Notably, it remains effective even with small datasets comprising just 1 or 5 samples, albeit with a slightly diminished performance. Furthermore, our system supports processing images, videos, and real-time streams, accommodating both hand-cropped and full-body images. As part of this research, we have curated and released a publicly accessible Hasta Mudra dataset, which applies to multiple South Indian art forms including Kathakali. The implementation of the proposed method is also made available as a web application.

This work proposes a compilation flow using open-source compiler passes to build a framework to achieve ninja performance from a generic linear algebra high-level abstraction. We demonstrate this flow with a proof-of-concept MLIR project that uses input IR in Linalg-on-Tensor from TensorFlow and PyTorch, performs cache-level optimizations and lowering to micro-kernels for efficient vectorization, achieving over 90% of the performance of ninja-written equivalent programs. The contributions of this work include: (1) Packing primitives on the tensor dialect and passes for cache-aware distribution of tensors (single and multi-core) and type-aware instructions (VNNI, BFDOT, BFMMLA), including propagation of shapes across the entire function; (2) A linear algebra pipeline, including tile, fuse and bufferization strategies to get model-level IR into hardware friendly tile calls; (3) A mechanism for micro-kernel lowering to an open source library that supports various CPUs., Comment: 13 pages, 8 figures, presented at CGO C4ML 2024 & MLIR Workshop EuroLLVM 2024