论文检索

Social Aspects · Everything Else

Jessica Dai, Sean Garcia, Emma Pierson, Benjamin Recht, Nika Haghtalab

ChatGPT was launched on November 30, 2022; the r/ChatGPT subreddit was created just one day later. Since then, chatbot-based AI products have gone from niche proofs-of-concept to widely-used household names. However, the ways in which adoption has developed, especially among non-experts, remains poorly understood. In this paper, we propose a principled framework for using social media as a data source for understanding the societal impact of widely-adopted consumer AI products, as well as a general approach to monitoring for societally-impactful trends in real time. We apply our framework to conduct what is, to the best of our knowledge, the first longitudinal study of r/ChatGPT. We find that, overall, r/ChatGPT posts over time illustrate the normalization of ChatGPT as an everyday consumer product rather than an exceptional, novel technology. However, our retrospective analysis also finds that posts about using ChatGPT for mental health support, and posts about developing emotional attachments to ChatGPT, both rise steadily in frequency immediately after the launch of GPT-4o in May 2024. We show that our real-time method can detect the increase in emotional engagement as early as October 2024—months before OpenAI made any (public) acknowledgment of this impact.

General Machine Learning · Transfer, Multitask and Meta-learning

Zilin Du, Junqi Zhao, Albert Boyang Li

Synthetic data are increasingly used to train image classifiers, yet distributional mismatch with real data limits their effectiveness when used indiscriminately. A common strategy is to learn data weights via bi-level optimization, which we refer to as Meta-learning for Training-data Selection (MTS). Interestingly, in practice, MTS often performs below expectation. We identify two obstacles in properly training MTS: a poor gradient signal-to-noise ratio (GSNR), which causes optimization difficulties, and lack of informative features that correlates with data quality. We present a thorough mathematical analysis of MTS, which reveals the dynamics of normalized data weights and the relation between disparate data quality and poor GSNR. The analysis suggests a a simple yet effective solution: increasing the batch size. Further, we propose a set of informative features that capture the positions of training data in their distributions and training dynamics. Experiments across four benchmarks show consistent improvements, achieving average gains of 5.49\% over training without selection and 2.89\% over the strongest baseline.

Sima Noorani, Shayan Kiyani, Hamed Hassani, George Pappas

As humans increasingly rely on multi-round conversational AI for high-stakes decisions, principled frameworks are needed to ensure such interactions reliably improve decision quality. We adopt a human-centric view governed by two principles: counterfactual harm, ensuring the AI does not undermine human strengths, and complementarity, ensuring it adds value where the human is prone to err. We formalize these concepts via user-defined rules, allowing users to specify exactly what harm and complementarity mean for their specific task. We then introduce an online, distribution-free algorithm with finite-sample guarantees that enforces the user-specified constraints over the collaboration dynamics. We evaluate our framework across two interactive settings: LLM-simulated collaboration on a medical diagnostic task and a human crowdsourcing study on a pictorial reasoning task. We show that our online procedure maintains prescribed counterfactual-harm and complementarity violation rates even under non-stationary interaction dynamics. Moreover, tightening or loosening these constraints produces predictable shifts in downstream human accuracy, confirming that the two principles serve as practical levers for steering multi-round collaboration toward better decision quality without the need to model or constrain human behavior.

Reinforcement Learning · Policy Search

Jingduo Pan, Taoran Wu, Yiling Xue, Bai Xue

We study stochastic minimum-cost reach-avoid reinforcement learning, where an agent must satisfy a reach-avoid specification with probability at least $p$ while minimizing expected cumulative costs in stochastic environments. Existing safe and constrained reinforcement learning methods typically fail to jointly provide probabilistic reach-avoid guarantees and cost-optimality in the learning setting in stochastic environments. In order to overcome this issue, we introduce reach-avoid probability certificates (RAPCs), which characterize the states from which stochastic reach-avoid constraints are satisfiable. Based on RAPCs, we develop a contraction-based Bellman formulation that enables reinforcement learning to optimize cumulative cost while provably satisfying stochastic reach-avoid constraints. We establish almost sure convergence of the proposed algorithms to locally optimal policies under the reach-avoid constraints. Experiments in the MuJoCo simulator demonstrate improved cost performance and higher reach-avoid satisfaction compared to existing baselines.

Deep Learning · Theory

Fabiola Ricci, Claudia Merger, Sebastian Goldt

Neural networks trained with gradient-based methods exhibit a strong simplicity bias, learning simpler statistical features of their data before moving to more complex features. In this work, we study this bias from a Fourier perspective, motivated by the approximate translation-invariance and the characteristic power spectra of natural images. We first show experimentally that simple neural networks trained on image classification tasks first rely on amplitude information -- related to pair-wise correlations between pixels -- before exploiting phase information, which encodes edges and higher-order correlations. To explain this phenomenon, we introduce a synthetic data model for translation-invariant inputs that allows precise control over the amplitudes and phases while remaining tractable. We rigorously establish that for isotropic and high-dimensional inputs, classifying them by relying only phase information is a genuinely hard task: online stochastic gradient descent cannot distinguish the structured inputs from noise within $n \ll N^3$ steps, but needs at least $n \gg N^3 \log^2{N}$ steps. In contrast, we prove that for non-isotropic inputs with power-law spectra, the existence of a dominant principal subspace can dramatically accelerate the speed of learning, even if the Fourier amplitudes are shared among classes and do not help with classification. Simulations with two-layer networks trained on textures, and with deep convolutional networks on ImageNet confirm this non-trivial interaction between amplitudes and phases, providing mechanistic insight into how deep neural networks can learn natural image distributions efficiently.

Applications · Computer Vision

Masakazu Yoshimura, Teruaki Hayashi, Yuki Hoshino, Wei-Yao Wang, Takeshi Ohashi

The realm of Mamba for vision has been advanced in recent years to strike for the alternatives of Vision Transformers (ViTs) that suffer from the quadratic complexity. While the recurrent scanning mechanism of Mamba offers computational efficiency, it inherently limits non-causal interactions between image patches. Prior works have attempted to address this limitation through various multi-scan strategies; however, these approaches suffer from inefficiencies due to suboptimal scan designs and frequent data rearrangement. Moreover, Mamba exhibits relatively slow computational speed under short token lengths, commonly used in visual tasks. In pursuit of a truly efficient vision encoder, we rethink the scan operation for vision and the computational efficiency of Mamba. To this end, we propose SF-Mamba, a novel visual Mamba with two key proposals: auxiliary patch swapping for encoding bidirectional information flow under an unidirectional scan and batch folding with periodic state reset for advanced GPU parallelism. Extensive experiments on image classification, object detection, and instance and semantic segmentation consistently demonstrate that our proposed SF-Mamba significantly outperforms state-of-the-art baselines while improving throughput across different model sizes. We will release the source code after publication.

Social Aspects · Alignment

Wenhao Chen, Sirui Sun, Shengyuan Bai, Guojie Song

Aligning large language models (LLMs) with human values typically relies on post-training or inference-time steering that directly manipulates the backbone’s parameters or representation space. However, a critical gap exists: the model’s residual stream is highly dynamic, in which values exist as fragile, low-dimensional properties, inherently incompatible with the stability required for consistent value expression. In this paper, we propose the Stable Value Guidance Transformer (SVGT), which addresses this gap through an independent value module incorporating two key designs: (1) *independent value modeling*, maintaining normative representations in a dedicated value space isolated from the backbone, and (2) *explicit behavioral guidance*, transducing these stable signals into learnable latent Bridge Tokens. These tokens serve as dynamic value anchors to explicitly steer the generative trajectory, ensuring robust adherence across diverse contexts without disrupting the backbone’s internal representations. Experiments across multiple backbones and safety benchmarks show that SVGT consistently reduces harmful scores by over 70\% while maintaining generation fluency, demonstrating the efficacy of architecturally grounded value modeling.

General Machine Learning · Hardware and Software

Seungheon Lee, Jeongmin Sun, Jaeyong Chung

Differentiable logic gate networks map learned models directly to gate-level circuits, enabling ultra-low-latency inference, yet their logic footprint often exceeds FPGA capacity budgets. Tightly fitting a trained model to a target FPGA requires a post-training mechanism to trade off network complexity and accuracy—analogous to pruning in standard neural networks. To this end, we introduce *unit tying*: a simplification that forces selected gates to constants (0 or 1), enabling constant propagation and downstream logic elimination. However, we observe that naively extending pruning criteria to logic networks is unreliable under such near-discrete modifications. We therefore propose a two-stage algorithm for unit tying: (i) a fast Gauss–Newton screening step under a teacher-referenced logit-distortion objective that constructs a high-recall overshoot set and (ii) a refinement step that corrects approximation and interaction-driven errors using a small number of finite-difference evaluations. On CIFAR-10 and MNIST, our method consistently improves the accuracy–area trade-off over common saliency baselines, yielding substantial post-synthesis LUT reductions of up to 48% on CIFAR-10 and 43% on MNIST, with modest accuracy degradation.

General Machine Learning · Evaluation

Sang Truong, Yuheng Tu, Rylan Schaeffer, Sanmi Koyejo

Scaling laws provide a fundamental framework for understanding the performance of Large Language Models (LLMs), yet deriving them requires prohibitively expensive evaluations across thousands of checkpoints or millions of inference samples. To address this, we introduce Item Response Scaling Laws (IRSL), a unified framework that integrates Item Response Theory (IRT) within scaling law formulation. Unlike traditional approaches that treat each model-benchmark pair in isolation, IRSL disentangles latent model ability from question characteristics, factorizing the scaling law estimation for $M$ models and $N$ questions to significantly reduce parameter complexity from $O(M \times N)$ to $O(M + N)$. We propose Beta-IRT, a novel extension that leverages the empirical probability responses of LLMs, such as token probabilities in pre-training and pass rates in test-time sampling, to capture richer signals than binary responses. We validate our approach across two prevalent scaling paradigms: (1) pre-training downstream scaling, using 6,612 LLM checkpoints and 37,682 questions from 10 benchmarks; and (2) test-time scaling, using 12 LLMs and 120 questions from 4 benchmarks with up to 2,500 samples per question. In both cases, we demonstrate that IRSL yields more reliable scaling estimates under limited query budgets. Furthermore, we show that the estimated latent model abilities are generalizable, enabling accurate performance forecasting across benchmarks that share the same measurement objective.

General Machine Learning · Causality

Qianglin Wen, Xiangkun Wu, Chengchun Shi, Ting Li, Niansheng Tang, Yingying Zhang, Hongtu Zhu

Experimental design has emerged as a powerful approach for improving the sample efficiency of A/B testing, yet existing designs rely critically on correctly specified models. We study robust sequential experimental design under model misspecification and develop a unified framework that covers both contextual bandit and dynamic settings. Theoretically, we prove that our design bounds the worst-case mean squared error of the estimated treatment effect. Empirically, we demonstrate the effectiveness of the proposed approach using synthetic and real-world datasets from a leading technology company.

Deep Learning · Everything Else

Rim Assouel, Amir Bar, Michal Drozdzal, Adriana Romero-Soriano

Despite remarkable progress in Multimodal Large Language Models (MLLMs), these models still struggle with fine-grained understanding tasks. In this work, we propose **Procedurally Generated Tasks (PGT)** a simple data-driven framework that serves a dual purpose: inducing fine-grained visual understanding and acting as a low-cost diagnostic tool to identify the source of perception failures. By overlaying unambiguous geometric primitives on images, PGT generate additional dense supervision that disentangles visual grounding capability from semantic priors. Extensive experiments on relational, quantitative, and 3D/depth understanding benchmarks show that PGT yields remarkable gains across diverse architectures. Instruction tuning MLLMs on LLaVA-v1.5-Instruct augmented with PGT data results in improvements of up to +20\% on the What’sUp benchmark and +13.3\% on CV-Bench-2D, while maintaining general perception capabilities. Moreover, finetuning state-of-the-art MLLMs on PGT data leads to boosts of up to +5.5\% on What’sUp and +8.3\% on CV-Bench-2D. These findings demonstrate that PGT effectively address the bottleneck of fine-grained perception, revealing that many spatial reasoning deficits stem from inadequate supervision signals rather than inherent architectural or resolution limitations.

General Machine Learning · Scalable Algorithms

Shuo Ji, Jie Hu, Zhouqiao He, Zijie Zhao, Tianrui Li, Jie Xu

Computation overhead has emerged as a critical bottleneck in Federated Learning (FL). Coreset selection tackles this challenge by constructing an informative subset to represent the full dataset. However, existing approaches optimize coreset construction solely at the data level and enforce a uniform retention ratio across all clients, ignoring client heterogeneity and introducing detrimental fragmented clients. In this paper, we first introduce a *gradient projection Shapley value* (GPSV) to evaluate client contributions. GPSV captures both the directional and magnitude information of client updates and enables exact Shapley value calculation with $\mathcal{O}(1)$ per-coalition evaluation. Building on GPSV, we then propose ShapCCS, the first client-level coreset selection strategy for FL. ShapCCS prioritizes clients with high GPSV scores while excluding fragmented clients with negligible or even negative GPSV. As a client-level coreset selection strategy, ShapCCS can be integrated with a data-level selection approach, and additionally reduces communication costs, an advantage unattainable by data-level methods alone. Extensive experiments demonstrate the superiority of ShapCCS on model performance and robustness to noise. The code is available at https://anonymous.4open.science/r/ShapCCS-5CBB.

Deep Learning · Large Language Models

Jian Yao, Xiongcai Luo, Ran Cheng, KC Tan

Recent advances in Large Reasoning Models have significantly improved chain-of-thought (CoT) capabilities via reinforcement learning (RL). However, generated reasoning chains frequently suffer from structural redundancy (i.e., \emph{overthinking}), incurring high computational overhead without improving answer correctness. Existing mitigation strategies typically rely on token-uniform length penalties, which provide coarse, segment-agnostic pressure toward shorter outputs and can inadvertently suppress useful reasoning alongside redundancy. To address this, we demonstrate that inefficiency concentrates in high-probability segments with low marginal utility. We derive a theoretical characterization of segment suboptimality under the correctness-length trade-off objective and propose \textsc{SLAT} (Segment-Level Adaptive Trimming), an RL framework that selectively suppresses redundant segments based on this criterion. Empirical results on standard benchmarks indicate that \textsc{SLAT} establishes a superior accuracy-efficiency Pareto frontier, reducing reasoning length by 50\% relative to uncompressed baselines while maintaining competitive accuracy. Overall, our results suggest that theoretically grounded, segment-aware trimming is a promising direction for efficient CoT reasoning in large language models.

Optimization · Convex

Miria Feng, Mert Pilanci

Fine-tuning large language models (LLMs) to align with human preferences has driven the success of systems such as Gemini and ChatGPT. However, approaches like Reinforcement Learning from Human Feedback (RLHF) remain computationally expensive and complex. Direct Preference Optimization (DPO) offers a simpler alternative but has limitations such as inconsistent ranking accuracy, high dependence on expensive GPU resources, and sensitive hyperparameter tuning. We propose the Convex Optimization for Alignment and Preference Learning Algorithm (COALA): a novel lightweight strategy with strong theoretical guarantees. By leveraging the convex optimization reformulation of neural networks, COALA eliminates the need for a reference model and obtains significant reduction in both training time and VRAM consumption, thus enabling efficient training on a single GPU. Experiments across three datasets—including a 23,228-sample synthetic Educational Feedback dataset—and five models (including LLaMA-8B) demonstrate COALA's competitive performance and efficiency in utilizing as little as ${\approx}17.6$% of DPO's total TFLOPS. COALA exhibits stable, monotonically increasing rewards and reaches peak margins in significantly less time than traditional methods such as DPO and ORPO. To the best of our knowledge, this is the first time convex optimization has been effectively applied to preference fine-tuning of LLMs.

General Machine Learning · Causality

YiXin Ren, Chenghou Jin, Yewei Xia, Zichuan Lin, Deheng Ye, Hao Zhang, Jihong Guan, Shuigeng Zhou

Real-time estimation of average treatment effects (ATE) in streaming observational data poses two key challenges: strict memory constraints that preclude storing the full data history, and distributional shifts in both treatment assignment and outcome-generating process. Existing methods either require offline access to the entire dataset for covariate balancing or rely on parametric online models that are vulnerable to model misspecification under such shifts. This paper proposes a novel model-agnostic method for ATE estimation in streaming data, which effectively addresses the above challenges. Based on discrepancy theory, we first compress streaming data into feature coresets that preserve covariate balancing objectives over a rich nonparametric function class, enabling linear-time updates with bounded memory. Then, by directly learning balancing weights and bypassing parametric propensity score estimation, we enhance the model's robustness against the shift in treatment assignment, while by balancing over an expressive function space we make the model more adaptive to the shift in the outcome-generating process. Theoretically, we establish convergence guarantees with explicit bounds on memory usage and computational complexity. Empirically, extensive experiments on both synthetic and real-world datasets show the effectiveness and robustness of the proposed method, consistently outperforming existing techniques.

Optimization · Stochastic

Dimitris Oikonomou, Nicolas Loizou

Sharpness-Aware Minimization (SAM) has established itself as a powerful and widely adopted optimizer for training machine learning models. By explicitly minimizing the sharpness of the loss landscape, SAM often improves generalization while delivering strong empirical performance. However, SAM and its variants, like most training algorithms, are sensitive to the choice of learning rate, which is typically tuned by trial and error or via schedulers. In this work, motivated by recent advances on the effectiveness of stochastic Polyak step sizes for Stochastic Gradient Descent (SGD), we derive Polyak schedulers tailored to SAM-style updates, yielding novel adaptive algorithms in both deterministic and stochastic settings. In smooth setting, for the proposed methods, we prove linear convergence for strongly convex objectives and an $O(1/T)$ rate (up to a neighborhood in the stochastic setting) for convex objectives. Numerical experiments demonstrate that the proposed Polyak schedulers match or surpass tuned SAM baselines while substantially reducing the need for learning-rate tuning.

Deep Learning · Theory

Moritz Brösamle, Stephan Eckstein

Existing expressivity results for transformers typically rely on hardmax attention, high precision, and other architectural modifications that disconnect them from the models used in practice. We bridge this gap by analyzing standard transformer decoders with softmax attention and rounding of activations and attention weights, while allowing depth and width to grow logarithmically with the context length. As an intermediate step, we construct hardmax transformers with ternary activations and well-separated attention scores that simulate Turing machines using Chain-of-Thought (CoT). This lets us convert the constructions to equivalent softmax transformers without the unrealistic parameter magnitudes or activation precision that prior approaches would require. Using the same technique, we analyze a recently proposed summarized CoT paradigm (InftyThink) and show that it simulates Turing machines more efficiently, with model size scaling logarithmically in a space bound rather than a time bound. We empirically demonstrate this advantage by training small transformers to solve Sudokus almost perfectly with summarized CoT, even on instances requiring more than a million reasoning tokens.

Deep Learning · Large Language Models

Sanghyun Lee, Seungryong Kim, Jongho Park, Dongmin Park

Masked Diffusion Models (MDMs) as language models generate by iteratively unmasking tokens, yet their performance crucially depends on the inference-time order of unmasking. Conventional methods such as confidence-based sampling are short-sighted, focusing on local optimization which neglects test-time computation and allows early decoding errors to cascade. We propose Lookahead Unmasking (LookUM), which addresses these concerns by guiding sampling path with a verifier over alternative unmasking orders, without requiring an external reward model. Our framework couples (i) a path generator that proposes paths by sampling from pools of unmasking sets with (ii) a verifier that computes the uncertainty of the proposed paths and performs importance sampling to subsequently select the final paths. Erroneous unmasking inflates sequence-level uncertainty, and our method exploits this to avoid error-prone trajectories. We validate our framework across six benchmarks, such as mathematics, planning, and coding, and demonstrate consistent performance improvements. LookUM requires only two to three paths to achieve peak performance. LLaDA with LookUM matches the performance of RL-tuned LLaDA 1.5 and yields additional gains when applied to LLaDA 1.5, suggesting complementarity with reinforcement learning.

General Machine Learning · Methodology

Travis Pence, Daisuke Yamada, Vikas Singh

Tensor Product Representations provide the structural fidelity required for symbolic reasoning in models but suffer from *exponential* dimensionality growth when encoding deep recursive structures. Conversely, Vector Symbolic Architectures maintain *constant* dimensionality but sacrifice capacity and fidelity due to noisy compression via superposition. In this work, we propose **Orthogonal Subspace Carving (OSC)**, a memory architecture that binds *fillers* to *roles* by projecting onto the null space of the role basis before aggregating into a fixed order-$p$ tensor. OSC uses projections to enforce geometric orthogonality between bound structures within a {\em static} memory trace. We show that this mechanism decouples the tensor order from the structural depth, enabling deep recursive binding within a *constant* memory footprint. This construction allows for component vectors that are *orders of magnitude* smaller than the memory tensor, giving excellent memory efficiency in settings involving high superposition. We also show that TPR is a special case of binding in Clifford algebra, and give a Clifford formulation of OSC.

Deep Learning · Theory

Takashi Furuya, Davide Murari, Carola-Bibiane Schönlieb

Stability and robustness are critical for deploying Transformers in safety-sensitive settings. A principled way to enforce such behavior is to constrain the model's Lipschitz constant. However, approximation-theoretic guarantees for architectures that explicitly preserve Lipschitz continuity have yet to be established. In this work, we bridge this gap by introducing a class of gradient-descent-type in-context Transformers that are Lipschitz-continuous by construction. We realize both MLP and attention blocks as explicit Euler steps of negative gradient flows, ensuring inherent stability without sacrificing expressivity. We prove a universal approximation theorem for this class within a Lipschitz-constrained function space. Crucially, our analysis adopts a measure-theoretic formalism, interpreting Transformers as operators on probability measures, to yield approximation guarantees independent of token count. These results provide a rigorous theoretical foundation for the design of robust, Lipschitz continuous Transformer architectures.