GenAI4ELab/papercli-papers huggingface dataset:
Automated Composition of Agents: A Knapsack Approach for Agentic Component Selection
Authors: Michelle Yuan; Khushbu Pahwa; Shuaichen Chang; Mustafa Devrim Kaba; Jiarong Jiang; Xiaofei Ma; Yi Zhang; MONICA SUNKARA
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Designing effective agentic systems requires the seamless composition and integration of agents, tools, and models within dynamic and uncertain environments. Most existing methods rely on static, semantic retrieval approaches for tool or agent discovery. However, effective reuse and composition of existing components remain challenging due to incomplete capability descriptions and the limitations of retrieval methods. 
Component selection suffers because the decisions are not based on capability, cost, and real-time utility.
To address these challenges, we introduce a structured, automated framework for agentic system composition that is inspired by the knapsack problem. Our framework enables a composer agent to systematically identify, select, and assemble an optimal set of agentic components by jointly considering performance, budget constraints, and compatibility. By dynamically testing candidate components and modeling their utility in real-time, our approach streamlines the assembly of agentic systems and facilitates scalable reuse of resources. Empirical evaluation with Claude 3.5 Sonnet across five benchmarking datasets shows that our online-knapsack-based composer consistently lies on the Pareto frontier, achieving higher success rates at significantly lower component costs compared to our baselines. 
In the single-agent setup, the online knapsack composer shows a success rate improvement of up to 31.6\% in comparison to the retrieval baselines. 
In multi-agent systems, the online knapsack composer increases success rate from 37\% to 87\% when agents are selected from an agent inventory of 100+ agents. 
The substantial performance gap confirms the robust adaptability of our method across diverse domains and budget constraints.
On Union-Closedness of Language Generation
Authors: Steve Hanneke; Amin Karbasi; Anay Mehrotra; Grigoris Velegkas
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: We investigate language generation in the limit – a model by Kleinberg and Mullainathan and extended by Li, Raman, and Tewari. While Kleinberg and Mullainathan proved generation is possible for all countable collections, Li, Raman, and Tewari defined a hierarchy of generation notions (uniform, non-uniform, and generatable) and explored their feasibility for uncountable collections.
    Our first set of results resolve two open questions of Li et al. by proving finite unions of generatable or non-uniformly generatable classes need not be generatable. These follow from a stronger result: there is non-uniformly generatable class and a uniformly generatable class  whose union is non-generatable.
    This adds to the aspects along which language generation in the limit is different from traditional tasks in statistical learning theory like classification, which are closed under finite unions. 
    In particular, it implies that given two generators for different collections, one cannot combine them to obtain a single "more powerful" generator, prohibiting this notion of boosting. Our construction also addresses a third of Li et al.'s open questions on whether there are uncountable classes that are non-uniformly generatable and do not satisfy the eventually unbounded closure (EUC) condition introduced by Li et al.
    Our approach utilizes carefully constructed classes along with a novel diagonalization argument that could be of independent interest in the growing area of language generation.
Combining Cost Constrained Runtime Monitors for AI Safety
Authors: Tim Tian Hua; James Baskerville; Henri Lemoine; Mia Hopman; Aryan Bhatt; Tyler Tracy
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Monitoring AIs at runtime can help us detect and stop harmful actions. In this paper, we study how to efficiently combine multiple runtime monitors into a single monitoring protocol. The protocol's objective is to maximize the probability of applying a safety intervention on misaligned outputs (i.e., maximize recall). Since running monitors and applying safety interventions are costly, the protocol also needs to adhere to an average-case budget constraint. Taking the monitors' performance and cost as given, we develop an algorithm to find the best protocol. The algorithm exhaustively searches over when and which monitors to call, and allocates safety interventions based on the Neyman-Pearson lemma. By focusing on likelihood ratios and strategically trading off spending on monitors against spending on interventions, we more than double our recall rate compared to a naive baseline in a code review setting. We also show that combining two monitors can Pareto dominate using either monitor alone. Our framework provides a principled methodology for combining existing monitors to detect undesirable behavior in cost-sensitive settings.
Normalization in Attention Dynamics
Authors: Nikita Karagodin; Shu Ge; Yury Polyanskiy; Philippe Rigollet
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: We study the effect of normalization schemes on token representations in deep transformers. Modeling their evolution as interacting particles on the sphere, we show that normalization acts as a form of speed regulation. This perspective enables a unified analysis of several schemes---including **Post-LN**, **Pre-LN**, **Mix-LN**, **Peri-LN**, **nGPT**---revealing how they influence clustering dynamics and representation collapse. Our framework clarifies how different schemes shape token representations across layers and provides a principled basis for comparing them, identifying **Peri-LN** as a particularly effective choice.
Is Your Diffusion Model Actually Denoising?
Authors: Daniel Pfrommer; Zehao Dou; Christopher Scarvelis; Max Simchowitz; Ali Jadbabaie
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: We study the inductive biases of diffusion models with a conditioning-variable, which have seen widespread application as both text-conditioned generative image models and observation-conditioned continuous control policies. We observe that when these models are queried conditionally, their generations consistently deviate from the idealized "denoising" process upon which diffusion models are formulated, inducing disagreement between popular sampling algorithms (e.g. DDPM, DDIM). We introduce *Schedule Deviation*, a rigorous measure which captures the rate of deviation from a standard denoising process, and provide a methodology to compute it. Crucially, we demonstrate that the deviation from an idealized denoising process occurs irrespective of the model capacity or amount of training data. We posit that this phenomenon occurs due to the difficulty of bridging distinct denoising flows across different parts of the conditioning space and show theoretically how such a phenomenon can arise through an inductive bias towards smoothness.
The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
Authors: Ioannis Anagnostides; Ioannis Panageas; Tuomas Sandholm; Jingming Yan
Venue: NeurIPS 2025 (NeurIPS 2025 spotlight)

Abstract: We consider the problem of computing stationary points in min-max optimization, with a focus on the special case of Nash equilibria in (two-)team zero-sum games. We first show that computing $\epsilon$-Nash equilibria in $3$-player $\text{\emph{adversarial}}$ team games---wherein a team of $2$ players competes against a $\text{\emph{single}}$ adversary---is $\textsf{CLS}$-complete, resolving the complexity of Nash equilibria in such settings. Our proof proceeds by reducing from $\text{\emph{symmetric}}$ $\epsilon$-Nash equilibria in $\text{\emph{symmetric}}$, identical-payoff, two-player games, by suitably leveraging the adversarial player so as to enforce symmetry---without disturbing the structure of the game. In particular, the class of instances we construct comprises solely polymatrix games, thereby also settling a question left open by Hollender, Maystre, and Nagarajan (2024). 

Moreover, we establish that computing $\text{\emph{symmetric}}$ (first-order) equilibria in $\text{\emph{symmetric}}$ min-max optimization is $\textsf{PPAD}$-complete, even for quadratic functions. Building on this reduction, we show that computing symmetric $\epsilon$-Nash equilibria in symmetric, $6$-player ($3$ vs. $3$) team zero-sum games is also $\textsf{PPAD}$-complete, even for $\epsilon = \text{poly}(1/n)$. As a corollary, this precludes the existence of symmetric dynamics---which includes many of the algorithms considered in the literature---converging to stationary points. Finally, we prove that computing a $\text{\emph{non-symmetric}}$ $\text{poly}(1/n)$-equilibrium in symmetric min-max optimization is $\textsf{FNP}$-hard.
Knowing When to Stop: Efficient Context Processing via Latent Sufficiency Signals
Authors: Roy Xie; Junlin Wang; Paul Rosu; Chunyuan Deng; Bolun Sun; Zihao Lin; Bhuwan Dhingra
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Large language models (LLMs) process entire input contexts indiscriminately, which is inefficient when the information required to answer a query is localized within the context. We present dynamic context cutoff, a novel method enabling LLMs to self-terminate processing upon acquiring sufficient task-relevant information. Through analysis of model internals, we discover that specific attention heads inherently encode "sufficiency signals" -- detectable through lightweight classifiers -- that predict when critical information has been processed. This reveals a new efficiency paradigm: models' internal understanding naturally dictates processing needs rather than external compression heuristics. Comprehensive experiments across six QA datasets (up to 40K tokens) with three model families (LLaMA/Qwen/Mistral, 1B-70B) demonstrate 3.4% accuracy improvement while achieving 1.33x token reduction on average. Furthermore, our method demonstrates superior performance compared to other context efficiency methods at equivalent token reduction rates. Additionally, we observe an emergent scaling phenomenon: while smaller models require probing for sufficiency detection, larger models exhibit intrinsic self-assessment capabilities through prompting.
The Complexity of Finding Local Optima in Contrastive Learning
Authors: Jingming Yan; Yiyuan Luo; Vaggos Chatziafratis; Ioannis Panageas; Parnian Shahkar; Stelios Andrew Stavroulakis
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Contrastive learning is a powerful technique for discovering meaningful data representations by optimizing objectives based on $\textit{contrastive information}$, often given as a set of weighted triplets $\{(x_i, y_i^+, z_{i}^-)\}_{i = 1}^m$ indicating that an "anchor" $x_i$ is more similar to a "positive" example $y_i$ than to a "negative" example $z_i$. The goal is to find representations (e.g., embeddings in $\mathbb{R}^d$ or a tree metric) where anchors are placed closer to positive than to negative examples. While finding $\textit{global}$ optima of contrastive objectives is $\mathsf{NP}$-hard, the complexity of finding $\text{\textit{local}}$ optima---representations that do not improve by local search algorithms such as gradient-based methods---remains open. Our work settles the complexity of finding local optima in various contrastive learning problems by proving $\mathsf{PLS}$-hardness in discrete settings (e.g., maximize satisfied triplets) and $\mathsf{CLS}$-hardness in continuous settings (e.g., minimize Triplet Loss), where $\mathsf{PLS}$ (Polynomial Local Search) and $\mathsf{CLS}$ (Continuous Local Search) are well-studied complexity classes capturing local search dynamics in discrete and continuous optimization, respectively.  Our results imply that no polynomial time algorithm (local search or otherwise) can find a local optimum for various contrastive learning problems, unless  $\mathsf{PLS}\subseteq\mathsf{P}$ (or $\mathsf{CLS}\subseteq \mathsf{P}$ for continuous problems). Even in the unlikely scenario that $\mathsf{PLS}\subseteq\mathsf{P}$ (or  $\mathsf{CLS}\subseteq \mathsf{P}$), our reductions imply that there exist instances where local search algorithms need exponential time to reach a local optimum, even for $d=1$ (embeddings on a line).
From Flat to Hierarchical: Extracting Sparse Representations with Matching Pursuit
Authors: Valérie Costa; Thomas Fel; Ekdeep Singh Lubana; Bahareh Tolooshams; Demba E. Ba
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Motivated by the hypothesis that neural network representations encode abstract, interpretable features as linearly accessible, approximately orthogonal directions, sparse autoencoders (SAEs) have become a popular tool in interpretability literature. However, recent work has demonstrated phenomenology of model representations that lies outside the scope of this hypothesis, showing signatures of hierarchical, nonlinear, and multi-dimensional features. This raises the question: do SAEs represent features that possess structure at odds with their motivating hypothesis? If not, does avoiding this mismatch help identify said features and gain further insights into neural network representations? To answer these questions, we take a construction-based approach and re-contextualize the popular matching pursuit (MP) algorithm from sparse coding to design MP-SAE—an SAE that unrolls its encoder into a sequence of residual-guided steps, allowing it to capture hierarchical and nonlinearly accessible features. Comparing this architecture with existing SAEs on a mixture of synthetic and natural data settings, we show: (i) hierarchical concepts induce conditionally orthogonal features, which existing SAEs are unable to faithfully capture, and (ii) the nonlinear encoding step of MP-SAE recovers highly meaningful features, helping us unravel shared structure in the seemingly dichotomous representation spaces of different modalities in a vision-language model, hence demonstrating the assumption that useful features are solely linearly accessible is insufficient. We also show that the sequential encoder principle of MP-SAE affords an additional benefit of adaptive sparsity at inference time, which may be of independent interest. Overall, we argue our results provide credence to the idea that interpretability should begin with the phenomenology of representations, with methods emerging from assumptions that fit it.
Parallelizing MCMC Across the Sequence Length
Authors: David M. Zoltowski; Skyler Wu; Xavier Gonzalez; Leo Kozachkov; Scott Linderman
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Markov chain Monte Carlo (MCMC) methods are foundational algorithms for Bayesian inference and probabilistic modeling. However, most MCMC algorithms are inherently sequential and their time complexity scales linearly with the sequence length. Previous work on adapting MCMC to modern hardware has therefore focused on running many independent chains in parallel. Here, we take an alternative approach: we propose algorithms to evaluate MCMC samplers in parallel across the chain length. To do this, we build on recent methods for parallel evaluation of nonlinear recursions that formulate the state sequence as a solution to a fixed-point problem and solve for the fixed-point using a parallel form of Newton's method. We show how this approach can be used to parallelize Gibbs, Metropolis-adjusted Langevin, and Hamiltonian Monte Carlo sampling across the sequence length. In several examples, we demonstrate the simulation of up to hundreds of thousands of MCMC samples with only tens of parallel Newton iterations. Additionally, we develop two new parallel quasi-Newton methods to evaluate nonlinear recursions with lower memory costs and reduced runtime. We find that the proposed parallel algorithms accelerate MCMC sampling across multiple examples, in some cases by more than an order of magnitude compared to sequential evaluation.
Revisiting Bi-Linear State Transitions in Recurrent Neural Networks
Authors: MohammadReza Ebrahimi; Roland Memisevic
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: The role of hidden units in recurrent neural networks is typically seen as modeling memory, with research focusing on enhancing information retention through gating mechanisms. A less explored perspective views hidden units as active participants in the computation performed by the network, rather than passive memory stores. In this work, we revisit bilinear operations, which involve multiplicative interactions between hidden units and input embeddings. We demonstrate theoretically and empirically that they constitute a natural inductive bias for representing the evolution of hidden states in state tracking tasks. These are the simplest type of tasks that require hidden units to actively contribute to the behavior of the network. We also show that bilinear state updates form a natural hierarchy corresponding to state tracking tasks of increasing complexity, with popular linear recurrent networks such as Mamba residing at the lowest-complexity center of that hierarchy.
On Traceability in $\ell_p$ Stochastic Convex Optimization
Authors: Sasha Voitovych; Mahdi Haghifam; Idan Attias; Gintare Karolina Dziugaite; Roi Livni; Daniel M. Roy
Venue: NeurIPS 2025 (NeurIPS 2025 spotlight)

Abstract: In this paper, we investigate the necessity of traceability for accurate learning in stochastic convex optimization (SCO) under $\ell_p$ geometries. Informally, we say a learning algorithm is \emph{$m$-traceable} if, by analyzing its output, it is possible to identify at least $m$ of its training samples. Our main results uncover a fundamental tradeoff between traceability and excess risk in SCO. For every $p\in [1,\infty)$, we establish the existence of an excess risk threshold below which every sample-efficient learner is traceable with the number of samples which is a \emph{constant fraction} of its training sample. For $p\in [1,2]$, this threshold coincides with the best excess risk of differentially private (DP) algorithms, i.e., above this threshold, there exist algorithms that are not traceable, which corresponds to a sharp phase transition. For $p \in (2,\infty)$, this threshold instead gives novel lower bounds for DP learning, partially closing an open problem in this setup. En route to establishing these results, we prove a sparse variant of the fingerprinting lemma, which is of independent interest to the community.
A Unified Framework for Fair Graph Generation: Theoretical Guarantees and Empirical Advances
Authors: Zichong Wang; Zhipeng Yin; Wenbin Zhang
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Graph generation models play pivotal roles in many real-world applications, from data augmentation to privacy-preserving. Despite their deployment successes, existing approaches often exhibit fairness issues, limiting their adoption in high-risk decision-making applications. Most existing fair graph generation works are based on autoregressive models that suffer from ordering sensitivity, while primarily addressing structural bias and overlooking the critical issue of feature bias. To this end, we propose FairGEM, a novel one-shot graph generation framework designed to mitigate both graph structural bias and node feature bias simultaneously. Furthermore, our theoretical analysis establishes that FairGEM delivers substantially stronger fairness guarantees than existing models while preserving generation quality. Extensive experiments across multiple real-world datasets demonstrate that FairGEM achieves superior performance in both generation quality and fairness.
Adaptive Quantization in Generative Flow Networks for Probabilistic Sequential Prediction
Authors: Nadhir Hassen; Zhen Zhang; Johan W. Verjans
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Probabilistic time series forecasting, essential in domains like healthcare and neuroscience, requires models capable of capturing uncertainty and intricate temporal dependencies. While deep learning has advanced forecasting, generating calibrated probability distributions over continuous future values remains challenging. We introduce Temporal Generative Flow Networks (Temporal GFNs), adapting Generative Flow Networks (GFNs) – a powerful framework for generating compositional objects – to this sequential prediction task. GFNs learn policies to construct objects (eg. forecast trajectories) step-by-step, sampling final objects proportionally to a reward signal. However, applying GFNs directly to continuous time series necessitates addressing their inherently discrete action spaces and ensuring differentiability. Our framework tackles this by representing time series segments as states and sequentially generating future values via quantized actions chosen by a forward policy. We introduce two key innovations: (1) An adaptive, curriculum-based quantization strategy that dynamically adjusts the number of discretization bins based on reward improvement and policy entropy, balancing precision and exploration throughout training. (2) A straight-through estimator mechanism enabling the forward policy to output both discrete (hard) samples for trajectory construction and continuous (soft) samples for stable gradient propagation. Training utilizes a trajectory balance loss objective, ensuring flow consistency, augmented by an entropy regularizer. We provide rigorous theoretical bounds on the quantization error's impact and the adaptive factor's range. We demonstrate how Temporal GFNs offer a principled way to leverage the structured generation capabilities of GFNs for probabilistic forecasting in continuous domains.
Computable universal online learning
Authors: Dariusz Kalociński; Tomasz Steifer
Venue: NeurIPS 2025 (NeurIPS 2025 poster)

Abstract: Understanding when learning is possible is a fundamental task in the theory of machine learning. However, many characterizations known from the literature deal with abstract learning as a mathematical object and ignore the crucial question: when can learning be implemented as a computer program? We address this question for universal online learning, a generalist theoretical model of online binary classification, recently characterized by Bousquet et al. (STOC 2021). In this model, there is no hypothesis fixed in advance; instead, Adversary—playing the role of Nature—can change their mind as long as local consistency with the given class of hypotheses is maintained. We require Learner to achieve a finite number of mistakes while using a strategy that can be implemented as a computer program. We show that universal online learning does not imply computable universal online learning, even if the class of hypotheses is relatively easy from a computability-theoretic perspective. We then study the agnostic variant of computable universal online learning and provide an exact characterization of classes that are learnable in this sense. We also consider a variant of proper universal online learning and show exactly when it is possible. Together, our results give a more realistic perspective on the existing theory of online binary classification and the related problem of inductive inference.