Publications
Our teams aspire to make discoveries that impact everyone, and core to our approach is sharing our research and tools to fuel progress in the field.
Our teams aspire to make discoveries that impact everyone, and core to our approach is sharing our research and tools to fuel progress in the field.
Sort By
1 - 15 of 11415 publications
Preview abstract
This talk addresses the challenges of operating Google's monitoring systems at scale, handling terabytes of telemetry data and preventing overload from diverse workloads. We'll explore how Google's internal client library and Monarch, its planet-scale time-series database, work together for cost-effective data collection. Key principles include a distributed push model, dynamic client-side data reduction, centralized retention, and periodic metric analysis. The session will then bridge these concepts to the open-source world, discussing our work with OpenTelemetry's OpAMP protocol to achieve similar scalable and efficient telemetry collection. Attendees will gain insights into adapting these principles for cost savings and learn about our collaboration with the OpAMP SIG to benefit the broader community.
View details
Preview abstract
Statistical evaluation aims to estimate the generalization performance of a model using held-out i.i.d. test data sampled from the ground-truth distribution. In supervised learning settings such as classification, performance metrics such as error rate are well-defined, and test error reliably approximates population error given sufficiently large datasets. In contrast, evaluation is more challenging for generative models due to their open-ended nature: it is unclear which metrics are appropriate and whether such metrics can be reliably evaluated from finite samples. In this work, we introduce a theoretical framework for evaluating language models and establish evaluability results for commonly used metrics. We study two categories of metrics: test-based metrics, including integral probability metrics (IPMs), and similarity-based metrics, including Rényi and KL divergences. We show that IPMs with respect to any bounded test class can be evaluated from finite samples up to multiplicative and additive approximation errors. Moreover, when the test class has finite fat-shattering dimension, IPMs can be evaluated with arbitrary precision. In contrast, similarity-based metrics, including Rényi and KL divergences, are not evaluable from finite samples, as their values can be critically determined by rare events. We also analyze the potential and limitations of perplexity as an evaluation method.
View details
Preview abstract
Large language models have achieved remarkable capabilities across domains, yet mechanisms underlying sophisticated reasoning continue to be explored1,2. Recent reasoning-reinforced models, including OpenAI’s o-series and DeepSeek-r1, outperform other merely instruction-tuned models on complex cognitive tasks3,4, attributed to extended test-time computation through longer chains of thought5. Here we show that enhanced reasoning emerges not from extended computation alone, but from the systematic simulation of complex, multi-agent interactions—a society of thought—which enables the deliberate diversification and debate among internal cognitive perspectives characterized by distinct personality traits and domain expertise. Through quantitative analysis using classified outputs and mechanistic interpretability methods applied to reasoning traces6–8, we find that reasoning models like DeepSeek-r1 exhibit much greater perspective diversity than baseline models, activating broader and more conflict between heterogeneous personality- and expertise-related features during reasoning. This multi-agent structure manifests in conversational behaviors including question-answering sequences, perspective shifts, and reconciliation of conflicting views, as well as in socio-emotional roles that characterize back-and-forth conversation, which together account for over 60% of the accuracy advantage in reasoning tasks through both direct and indirect facilitation of cognitive strategies9,10. Controlled reinforcement learning experiments further reveal that priming models with conversational scaffolding—even when dialogues lead to incorrect solutions—substantially accelerates reasoning improvement compared to answer-only training. These findings indicate that the social organization of thought, rather than correctness alone, enables effective exploration of solution spaces. We suggest that reasoning models establish a computational parallel to collective intelligence in human groups11–13, where diversity enables superior problem-solving when systematically structured and suggest new opportunities for agent organization to harness the wisdom of crowds.
View details
Preview abstract
Automating AI research differs from general software engineering due to computationally expensive evaluation (e.g., model training) and opaque performance attribution. Current LLM-based agents struggle here, often generating monolithic scripts that ignore execution costs and causal factors. We introduce MARS (Modular Agent with Reflective Search), a framework optimized for autonomous AI research. MARS relies on three pillars: (1) Budget-Aware Planning via cost-constrained Monte Carlo Tree Search (MCTS) to explicitly balance performance with execution expense; (2) Modular Construction, employing a "Design-Decompose-Implement" pipeline to manage complex research repositories; and (3) Comparative Reflective Memory, which addresses credit assignment by analyzing solution differences to distill high-signal insights. MARS achieves state-of-the-art performance among open-source frameworks on MLE-Bench under comparable settings, maintaining competitiveness with the global leaderboard's top methods. Furthermore, the system exhibits qualitative "Aha!" moments, where 63% of all utilized lessons originate from cross-branch transfer, demonstrating that the agent effectively generalizes insights across search paths.
View details
Preview abstract
We study the computational cost of differential privacy in terms of memory
efficiency. While the trade-off between accuracy and differential privacy is
well-understood, the inherent cost of privacy regarding memory use remains
largely unexplored. This paper establishes for the first time an unconditional
space lower bound for user-level differential privacy by introducing a novel
proof technique based on a multi-player communication game.
Central to our approach, this game formally links the hardness of low-memory
private algorithms to the necessity of ``contribution capping''---tracking and
limiting the users who disproportionately impact the dataset. We demonstrate
that winning this communication game requires transmitting information
proportional to the number of over-active users, which translates directly to
memory lower bounds.
We apply this framework, as an example, to the fundamental problem of
estimating the number of distinct elements in a stream and we prove that any
private algorithm requires almost $\widetilde{\Omega}(T^{1/3})$ space to
achieve certain error rates in a promise variant of the problem. This resolves
an open problem in the literature (by Jain et al. NeurIPS 2023 and Cummings et
al. ICML 2025) and establishes the first exponential separation between the
space complexity of private algorithms and their non-private $\widetilde{O}(1)$
counterparts for a natural statistical estimation task. Furthermore, we show
that this communication-theoretic technique generalizes to broad classes of
problems, yielding lower bounds for private medians, quantiles, and max-select.
View details
Preview abstract
As artificial intelligence (AI) is rapidly integrated into healthcare, ensuring that this innovation helps to combat health inequities requires engaging marginalized communities in health AI futuring. However, little research has examined Black populations’ perspectives on the use of AI in health contexts, despite the widespread health inequities they experience–inequities that are already perpetuated by AI. Addressing this research gap, through qualitative workshops with 18 Black adults, we characterize participants’ cautious optimism for health AI addressing structural well-being barriers (e.g., by providing second opinions that introduce fairness into an unjust healthcare system), and their concerns that AI will worsen health inequities (e.g., through health AI biases they deemed inevitable and the problematic reality of having to trust healthcare providers to use AI equitably). We advance health AI research by articulating previously-unreported health AI perspectives from a population experiencing significant health inequities, and presenting key considerations for future work.
View details
Preview abstract
Audio Description ( AD) provides essential access to visual media for blind and low vision ( BLV) audiences. Yet current AD production tools remain largely inaccessible to BLV video creators, who possess valuable expertise but face barriers due to visually- driven interfaces. We present ADCanvas, a multimodal authoring system that supports non- visual control
over audio description ( AD) creation. ADCanvas combines conversational interaction with keyboard- based playback control and a plain- text, screen reader–
accessible editor to support end- to- end AD authoring and visual question answering ( VQA). Combining screen- reader- friendly controls with a multimodal
LLM agent, ADCanvas supports live VQA, script generation, and AD modification. Through a user study with 12 BLV video creators, we find that users adopt
the conversational agent as an informational aide and drafting assistant, while maintaining agency through verification and editing. For example, participants
saw themselves as curators who received information from the model and filtered it down for their audience. Our findings offer design implications for
accessible media tools, including precise editing controls, accessibility support for creative ideation, and configurable rules for human- AI collaboration.
View details
Preview abstract
A common problem in private data analysis is the partition selection problem, where each user holds a set of partitions (e.g. keys in a GROUP BY operation) from a possibly unbounded set. The challenge here is in maximizing the set of released partitions while respecting a differential privacy constraint. Previous work [DVGM21] presented an optimal (ε, δ)-DP algorithm when each user submits only a single partition. We generalize this approach to find the optimal algorithm under δ-approximate (α, ε)-R´enyi differential privacy (RDP), which allows much tighter analysis under composition. Motivated by the non-existence of a general optimality result in the case where users submit multiple partitions each, we present a simple extension of our optimal algorithm tuned for L2 bounded weighted partition selection which can be used as a drop-in improvement over the Gaussian mechanism any time the partition frequency is not also needed. We show that our primitive can be easily plugged into state of the art partition selection algorithms (PolicyGaussian from [GGK+20] and MAD2R from [CCAEZ25]), improving performance both for parallel and sequential algorithms. Finally, we show that there is an inherent cost to algorithm which do support releasing the frequency as well as the partitions. Specifically, we formulate a basic notion of optimal approximate RDP algorithm for partition selection using additive noise, and show that there is a numerical separation between additive and non-additive noise mechanisms for this problem.
View details
MoXaRt: Audio-Visual Object-Guided Sound Interaction for XR
Sieun Kim
Qianhui Zheng
Ruoyu Xu
Ravi Tejasvi
Anuva Kulkarni
Junyi Zhu
2026
Preview abstract
In Extended Reality (XR), complex acoustic environments often overwhelm users, compromising both scene awareness and social engagement due to entangled sound sources. We introduce MoXaRt, a real-time XR system that uses audio-visual cues to separate these sources and enable fine-grained sound interaction. MoXaRt's core is a cascaded architecture that performs coarse, audio-only separation in parallel with visual detection of sources (e.g. faces, instruments). These visual anchors then guide refinement networks to isolate individual sources, separating complex mixes of up to five concurrent sources (e.g. two voices + three instruments) with ca. 2 second processing latency. We validate MoXaRt through a technical evaluation on a new, complex dataset we collected, and a 22-participant user study. Our results demonstrate that MoXaRt significantly improves communication clarity—boosting listening comprehension in noisy conditions by 33.2% (p=0.0058)—and significantly reduces cognitive load (M=7.50 vs. M=3.36, p<0.001), paving the way for more perceptive and socially adept XR experiences.
View details
Preview abstract
We study the stochastic linear bandits with parameter noise model, in which the reward of action $a$ is $a^\top \theta$ where $\theta$ is sampled i.i.d.
We show a regret upper bound of $\tO \brk{\sqrt{d T \logKdelta \sigmax}}$ for a horizon $T$, general action set of size $K$ of dimension $d$, and where $\sigmax$ is the maximal variance of the reward for any action.
We further provide a lower bound of $\tOmega \brk{d \sqrt{T \sigmax}}$ which is tight (up to logarithmic factors) whenever $\log \brk{K} \approx d$.
For more specific action sets, $\ell_p$ unit balls with $p \leq 2$ and dual norm $q$, we show that the minimax regret is $\tTheta \brk{\sqrt{dT \vsigq}}$, where $\vsigq$ is a variance-dependent quantity that is always at most $4$.
This is in contrast to the minimax regret attainable for such sets in the classic additive noise model, where the regret is of order $d \sqrt{T}$.
Surprisingly, we show that this optimal (up to logarithmic factors) regret bound is attainable using a very simple explore-exploit algorithm.
View details
Bi-level Hierarchical Neural Contextual Bandits for Online Recommendation
Yunzhe Qi
Yikun Ban
Allan Stewart
Chuanwei Ruan
Jiachuan He
Shishir Kumar Prasad
Haixun Wang
Jingrui He
Transactions on Machine Learning Research (2026)
Preview abstract
Contextual bandit algorithms aim to identify the optimal choice among a set of candidate arms, based on their contextual information. Among others, the neural contextual bandit algorithms have demonstrated generally superior performance compared to traditional linear and kernel-based methods. Nevertheless, neural methods are not inherently suitable to handle a large number of candidate arms due to their high computational cost when performing neural exploration.
Motivated by the widespread availability of arm category information (e.g., movie genres, retailer types), we formulate contextual bandits into a bi-level recommendation problem based on the accessible arm category information, and propose a novel neural bandit framework, named H2N-Bandit, which utilizes a bi-level hierarchical neural structure to mitigate the substantial computational cost found in conventional neural bandit methods.
To demonstrate its effectiveness, we provide the regret bound for H2N-Bandit under the over-parameterized neural bandit settings. Furthermore, to illustrate its efficiency, we conduct extensive experiments on multiple real-world public data sets with various specifications, showing that H2N-Bandit can significantly reduce the computational cost over existing non-linear methods while achieving better or comparable performances against state-of-the-art baselines.
View details
Preview abstract
High-volume enterprise service organizations face a persistent challenge in transitioning from reactive support models to proactive, preventative ones. This paper introduces the Agentic Trend-to-Knowledge (ATK) methodology, a novel, autonomous framework designed to address this gap. The ATK methodology employs an AI agent that operates in a recurring, closed loop. It first uses a two-stage process for the autonomous thematic analysis of recent support cases to identify the most significant recurring issue. It then leverages Retrieval-Augmented Generation (RAG) to source relevant institutional knowledge. A key innovation is the agent's adaptive, bimodal response: if relevant knowledge is found, it drafts a proactive communication for human review; if a knowledge gap is detected, it autonomously creates a content creation task for the appropriate team. This transforms the agent from an automation tool into a proactive process owner that creates a virtuous cycle of continuous improvement for both case deflection and knowledge base quality. By automating the entire workflow from insight to action, the ATK framework provides a concrete methodology for shifting from a "human-in-the-loop" to a more strategic "human-on-the-loop" operational paradigm.
View details
Online Advertising with Spatial Interactions
Yifan Wang
Mingfei Zhao
Proceedings of the ACM Web Conference 2026, Association for Computing Machinery, New York, NY, USA, 213–224
Preview abstract
Online advertising platforms must decide how to allocate multiple ads across limited screen real estate, where each ad's effectiveness depends not only on its own placement but also on nearby ads competing for user attention. Such spatial externalities — arising from proximity, clutter, or crowding — can significantly alter welfare and revenue outcomes, yet existing auction and allocation models typically treat ad slots as independent or ordered along a single dimension. We introduce a new framework for spatial externalities in online advertising, in which the value of an ad depends on both its slot and the configuration of surrounding ads. We model ad slots as points in a metric space, and model an advertiser's value as a function of both their bid and a discount factor determined by the configuration of other displayed ads.
Within this framework, we analyze two natural models. For the Nearest-Neighbor model, where the value suppression depends only on the closest neighboring ad, we present a polynomial-time algorithm that achieves a constant approximation for the general case. We show that the allocation rule is monotone and can be implemented as a truthful mechanism. For a structured setting of 2D Euclidean space, we provide a PTAS. In contrast, for the Product-Distance model, where interference is aggregated multiplicatively across all neighbors, we establish a strong (and nearly-tight) hardness of approximation -- no polynomial-time algorithm can achieve any polynomial-factor approximation unless P=NP, via a reduction from Max-Independent-Set. Our results provide a foundation for reasoning about spatial externalities in ad allocation and for designing efficient, truthful mechanisms under such interactions.
View details
Preview abstract
In this work, we prove computational lower bounds against differentially private (DP) coreset. Specifically, assuming the existence of one-way functions, we show that no polynomial-time $(\epsilon, 1/n^{\omega(1)})$-DP algorithm can compute $(\alpha, \beta)$-coreset for $k$-means in the $\ell_\infty$ metric for some constant $\alpha > 1$. For the Euclidean metric, we show a similar result but only for $\alpha = 1 + \Theta\left(\frac{1}{d^2}\right)$ where $d$ is the dimension.
View details
Preview abstract
Standard evaluations of backdoor attacks on text-to-image (T2I) models primarily measure trigger activation and visual fidelity. We challenge this paradigm, demonstrating that encoder-side poisoning induces persistent, trigger-free semantic corruption that fundamentally reshapes the representation manifold. We trace this vulnerability to a geometric mechanism: a Jacobian-based analysis reveals that backdoors act as low-rank, target-centered deformations that amplify local sensitivity, causing distortion to propagate coherently across semantic neighborhoods. To rigorously quantify this structural degradation, we introduce SEMAD (Semantic Alignment and Drift), a diagnostic framework that measures both internal embedding drift and downstream functional misalignment. Our findings, validated across diffusion and contrastive paradigms, expose the deep structural risks of encoder poisoning and highlight the necessity of geometric audits beyond simple attack success rates.
View details
