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 11644 publications
Preview abstract
Modern transformers have been scaled up in size, data, training-time compute, and more recently test-time compute based on Chain-of-Thought (CoT), but the consequences of trading off these parameters are unknown. We construct explicit tradeoffs between two of these aspects: the number of layers in a transformer and the number of CoT tokens. Our first result is general: with mild assumptions and a single-token prompt, for any integer k, a transformer using soft attention and SwiGLU MLP layers with L layers and n CoT tokens can be converted to a transformer with at most ckL layers and ⌈n/k⌉ CoT tokens, and vice versa, although with an increase to the size of other parameters. We then a multi-token prompt path following task, finding that additional preprocessing from the multi-token prompt changes the depth-CoT relationship in this case. We construct an attention-only network with L layers and 2^(L−2) heads that can traverse 2^(L−1) − 1 edges along a path with a single CoT token, demonstrating at least an exponential relationship between increases in depth and reductions in the number of CoT tokens needed to traverse the entire path. This relationship for the path following task holds empirically as well, as demonstrated by training networks with up to 5 layers, with the tradeoff between depth and the maximum number of edge traversals in a single CoT token exactly matching our theoretical constructions.
View details
When Android Apps Request Location with a Reason: A Developer Study and User Behavior Experiment
May Smith
Aman Jain
Proceedings on Privacy Enhancing Technologies (2027)
Preview abstract
Recent reports have highlighted how mobile apps share user location data with third parties, risking user privacy and platform trust. Although location data is highly sensitive, when users grant apps location access, they may not know the full extent to which it is used. We study how requiring Android apps to show a reason for location access could impact developers, users, and the platform.
We surveyed 323 Android app developers and found most supported such a requirement. The majority said it would have a positive impact on user privacy, trust for apps, and trust for Android, where impact on user trust for Android correlated most strongly with support. Many developers also said the intervention would increase the number of users granting location access. Yet their open-ended comments also revealed consistent concerns, such as apps providing dishonest reasons and platform verification.
To study the impact on user behavior, we conducted a randomized controlled experiment with 2579 US Android users. We tested how users' decisions to grant location access were impacted by app type, whether reasons were included in the requests, and the content of the reasons, including monetization. We did not find the reasons impacted users' decisions; decisions were instead driven by app type and demographics. Yet we did find the reasons could have a positive impact on user perception for the platform when the reasons did not include using data for ads. Our findings provide insights into developers' willingness to implement privacy-enhancing changes, and expose limits to improving user privacy by simply adding information to user interfaces.
View details
A 3D Scene Graphs Survey: Open Challenges and Future Directions
Dennis Rotondi
Francesco Argenziano
Sebastian Koch
Nathan Hughes
Martin Büchner
Johanna Wald
Lukas Schmid
Daniele Nardi
Abhinav Valada
Liam Paul
Luca Carlone
Kai Arras
Annual Review of Control, Robotics, and Autonomous Systems (ARCRAS), 10 (2027) (to appear)
Preview abstract
3D Scene Graphs (3DSGs) have emerged as a powerful representation for spatial AI by combining geometric grounding with semantic and relational abstractions of the environment. Their expressiveness has made them relevant to a broad range of problems in robotics and computer vision, including mapping, task and motion planning, scene understanding, and many others. However, the field remains fragmented: different communities adopt distinct formulations, construction pipelines, and evaluation protocols, making it difficult to compare methods, identify common assumptions, and assess remaining challenges for robust real- world deployment. This survey provides a unified and critical review of 3DSGs, with particular emphasis on open challenges and future directions. We first formalize 3DSGs under a common definition and analyze the principal modeling choices that characterize existing formulations, including node and edge attributes, hierarchical structure, dynamic scene representations, and affordance-aware extensions. We then review how 3DSGs are constructed from raw sensory observations, covering both learning-oriented and construction-oriented systems. Finally, we examine downstream applications and evaluation strategies, from intrinsic graph quality to task-level performance. To support the community, we also provide a dedicated website that organizes and extends the surveyed works.
View details
Optimized Deferral for Imbalanced Settings
Anqi Mao
Proceedings of the 43rd International Conference on Machine Learning (ICML 2026)
Preview abstract
Learning algorithms can be significantly improved by routing complex or uncertain inputs to specialized experts, balancing accuracy with computational cost. This approach, known as learning to defer, is essential in domains like natural language generation, medical diagnosis, and computer vision, where an effective deferral can reduce errors at low extra resource consumption. However, the two-stage learning to defer setting, which leverages existing predictors such as a collection of LLMs or other classifiers, often faces challenges due to an expert imbalance problem. This imbalance can lead to suboptimal performance, with deferral algorithms favoring the majority expert. We present a comprehensive study of two-stage learning to defer in expert imbalance settings. We cast the deferral loss optimization as a novel cost-sensitive learning problem over the input-expert domain. We derive new margin-based loss functions and guarantees tailored to this setting, and develop novel algorithms for cost-sensitive learning. Leveraging these results, we design principled deferral algorithms, MILD (Margin-based Imbalanced Learning to Defer), specifically suited for expert imbalance settings. Extensive experiments demonstrate the effectiveness of our approach, showing clear improvements over existing baselines on both image classification and real-world Large Language Model (LLM) routing tasks.
View details
Meta-Initialized Warm Pool Manager: Predictive Cold Start Mitigation for Serverless Functions via Adaptive Meta-Learning
Praveen Baskar
Om Narayan
Ramkinker Singh
2026
Preview abstract
Serverless computing platforms commonly suffer
from cold-start latency because of Cold-start problems dynamic
invocation patterns, but with current warm pool management
strategies face difficulty in effectively adjusting to changes in
workload. We propose the Meta-Initialized Warm Pool Manager
(MI-WPM), a new component which combines meta-learning and
adaptive control to address the problem of cold start efficiently.
The innovation is based on a meta predictor trained on diverse
invocation scenarios, which offers a generalized Initialization for
rapid fine-tuning based on detection of workload drift. Contrary
to traditional schemes based upon static heuristics or expensive
“retraining, MI-WPM adapts its warm pool sizes by combining
“ meta-initialized predictions with lightweight statistical drift
detection. The architecture uses a temporal fusion transformer
for modeling invocation patterns, Kolmogorov-Smirnov test for
monitoring drift, and feedback-controlled controller for opti-
mizing resource distribution. The experimental results show the
reduction in the Cold Start problem using MI-WPM. occurring
by 47% compared to state-of-the-art approaches while keeping
provisioning costs below 5%. Moreover, the Meta learning frame-
work supports sub-minute adaptation on unknown invocation
patterns, filling a gap in serverless computing. The proposed
approach is developed as a modular extension of the existing
serverless architectures without any infrastructure modifications.
This work fills the gap between offline-trained models and
reactive scaling, providing a principled approach to cold start
mitigation in production environments.
View details
LiSA: Lifelong Safety Adaptation via Conservative Policy Induction
Minbeom Kim
Phil Wallis
Bharath Chandrasekhar
Kyomin Jung
NeurIPS (2026)
Preview abstract
Large language model agents increasingly act in deployment environments where failures are contextual, user-specific, and costly. In such settings, a \emph{static general-purpose guardrail is often insufficient}: whether an action should be allowed may depend on local privacy norms, organizational rules, or evolving user expectations that are difficult to enumerate fully in advance. We study \emph{lifelong deployment-time guardrail adaptation}, where a fixed base guardrail improves over time from sparse, noisy user-reported failures without repeated fine-tuning. We propose a conservative policy induction framework organized as an online--offline loop. Online, the deployed guardrail uses structured policy memory to guide runtime decisions. Offline, newly accumulated reports are converted into reusable policy items and folded back into memory through periodic refresh. The method combines three ingredients: \emph{broad policy abstraction} for sparse failure generalization, \emph{conflict-aware local policies} for mixed-label regions where broad reuse becomes too coarse, and \emph{confidence-gated reuse} based on conservative posterior lower bounds so that weakly supported memory does not influence inference too early. Across PrivacyLens+, ConFaide+, and AgentHarm, the resulting system consistently improves over a lightweight base guardrail and strong memory-based baselines in sparse-feedback regimes, remains robust to noisy feedback, traces a better cost--performance frontier than scaling the base model alone, and jointly reduces over-refusal and over-acceptance without an explicit balance knob.
View details
JAXBench: Benchmarking Autonomous TPU Kernel Optimization
Vijay Janapa Reddi
Charles Hong
Arya Tschand
Julian Walker
Suvinay Subramanian
Shangkun Wang
Sethu Sankaran
Nina Cai
2026
Preview abstract
Evaluation benchmarks have driven progress in automated kernel optimization, yet existing suites target GPUs exclusively. We present JAXBench, a TPU-native benchmark for AI-generated kernel optimization on Google Cloud TPUs. JAXBench comprises 50 JAX workloads, including 17 production LLM operators extracted from architectures in the public MaxText library such as Llama-3.1, DeepSeek-V3, Mixtral, Mamba-2, and AlphaFold2, and 33 fused operator sequences adapted from KernelBench. Eight of the 17 production operators ship with hand-optimized Pallas TPU kernels from the public Tokamax library, whose block sizes we tune via grid search, establishing strong reference baselines. We evaluate one-shot generation, iterative coding agents, the same iterative loop with TPU documentation injected, and a TPU-enabled Autocomp configuration augmented with the same TPU-specific documentation. Across the full 50-benchmark suite with Gemini 3 Flash, best-of-N solves 13/50 benchmarks at 1.01x geomean and iterative refinement reaches 32/50 at 1.18x. Injecting TPU documentation lifts iterative refinement to 48/50 at 1.28x and raises per-sample correctness from 5.8% to 37.3%. Autocomp solves 45/50 but converts those correct kernels into 1.36x geomean with 76% of benchmarks beating XLA. On the 8 hand-tuned references, Autocomp reaches 1.60x against the XLA baseline, showing strong performance against the 2.08x Tokamax geomean but trailing on the specialized paged and ragged attention operators. A Gemini 3.1 Pro ablation lifts Autocomp to 49.1% per-sample correctness and a 3.13x geomean. High-quality TPU kernel generation remains open, and we release the benchmark, profiling harness, and baseline results to support reproducible research.
View details
Regression Test Selection at Scale
Randall Parker
Laiba Mehnaz
Charlie Song
Michelle Wang
Daniel Lee
Brandon Stewart
Ilya Kavalerov
2026
Preview abstract
Core libraries in massive codebases are dependency
hot-spots with high code churn and an immense number of
reverse dependencies. A small code change in these libraries
can impact a vast number of clients, creating a massive blast
radius of costly breakages if a bug or regression is submitted.
To prevent expensive post-submit breakages, it is not feasible to
test global dependencies during the pre-submit stage for each
code change because of resource limitations and the desire for
minimal developer friction.
In this paper, we propose a novel ranking-based approach that
utilizes a hybrid call graph to test global dependencies during the
pre-submit stage. Our method leverages the call graph to select a
per-commit subset of these global dependencies and to generate
inexpensive graph structural features that allow our machine
learning model to learn the complex relationships between library
code changes and client tests to predict failures. Evaluating our
approach on 10 high-impact core libraries with an average test
suite size of 220,000, we demonstrate that a fixed budget of 2,000
tests per commit, representing just 0.9% of the total execution
cost, effectively catches regressions for 40% of failing commits.
View details
Budget-Aware Tool Use Enables Effective Agent Scaling
Tengxiao Liu
Jin Miao
I-Hung Hsu
Samira Daruki
COLM 2026 (2026)
Preview abstract
Scaling test-time computation improves performance across different tasks on large language models (LLMs), yet mainstream scaling methods remain challenging for tool-augmented LLM agents. Sequential scaling tends to yield shallow tool use and under-exploration, whereas parallel scaling inflates cost through repeated tool calls. The dual costs of tokens and tool calls further complicate cost accounting and hinder fair comparison. In this work, we study the test-time scaling of widely used, tool-reliant search agents under resource constraints, analyzing performance with a unified cost metric that incorporates both tokens and tool calls. To this end, we propose Cost-effective Agent Test-Time Scaling (CATS), a budget-aware framework designed to support more cost-effective scaling by guiding resource allocation between sequential and parallel exploration. Experiments across search-intensive benchmarks show that CATS produces more favorable scaling curves, attaining higher accuracy with fewer tool calls and lower overall cost. Our work introduces a cost-conscious design for agent test-time scaling and contributes empirical insights that enable a more transparent and principled understanding of scaling in tool-augmented agents.
View details
Dialect Bias in Speech Recognition Across 10 Spanish and French Varieties
Rodrigo Nieto
Maria Angelika-Nikita
Diane Sarkis
Diyi Yang
Proceedings of Interspeech 2026, ISCA
Preview abstract
ASR bias research is largely English-focused and the mechanisms underlying performance disparities remain poorly understood. We address both gaps for Spanish and French. Using a 20-hour, gender-balanced corpus (the first for these languages designed for dialect bias analysis, with country-level stratification and manual transcripts preserving dialectal features), we benchmark seven models and find non-uniform disparities: models favor European varieties in French, while Spanish reveals unexpected patterns with Dominican outperforming Peninsular and with Chilean showing the highest error rates. Lexical analysis links failures to morphosyntactic "correction" and regional discourse markers; acoustic analysis shows that speaker embeddings encode dialect information; a diagnostic fine-tuning experiment localizes these errors to the decoder. Together, these results demonstrate that ASR errors systematically reflect linguistic distance from training distributions.
View details
Preview abstract
The planning horizon in a Markov Decision Process (MDP) determines how far into the future an agent reasons. In practice, shorter horizons are commonly associated with policies that exhibit simpler or more interpretable decision-making behavior. In this paper, we establish a formal connection between environmental stochasticity and planning horizon in MDPs. We show that for broad classes of transition noise, solving a noisy MDP can be formally related to solving a noise-free MDP with a shorter effective discount factor, leading to identical optimal policies in some cases and near-optimal ones in others. We further characterize settings in which this correspondence breaks down, clarifying when horizon-based interpretations of noise are not valid. These results, which are supported by both theory and experiments, also give some insight into the common practice of using smaller discount factors for reinforcement learning than those that can be justified by standard modeling interpretations.
View details
Preview abstract
We study the problem of allocating access point bandwidth to users of a wireless network in the presence of adversarial jamming. Specifically, we consider a setting in which the network designer acts first and allocates access point bandwidth to the users of the network, before an adversary applies a jamming strategy to reduce the bandwidth of a subset (or all) of the access points. We consider a strong adversary who has complete information and can optimize the jamming strategy, subject to power budget constraints. In turn, the network designer must allocate the resources in anticipation of the adversary's actions.
We explain that our model gives rise to a special network interdiction model, which differs from the standard setting in two ways: The first is that the interdictor is given the benefit of responding, rather than leading the game. The second is that the interdiction is fractional and performed at the node level of the network. The interdiction then propagates to all edges incident to the access point.
In terms of technical results, we provide an allocation algorithm that is based on linear programming duality and show that the algorithm can solve the problem optimally, assuming knowledge of the adversary's budget constraints. We conduct experiments on synthetic data to show the extent to which the algorithm improves the total utilized bandwidth over the algorithm that optimizes bandwidth allocation while being oblivious to the adversary's existence.
View details
Preview abstract
We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across $k$ sites while minimizing communication. The communication complexity of this problem is known to be $\Theta(\frac{k}{\eps}\log N)$ for deterministic protocols. Huang, Yi, and Zhang (2012) showed that randomization can reduce this to $\Theta(\frac{\sqrt{k}}{\eps}\log N)$, but their analysis is restricted to the oblivious setting, where the stream of events is independent of the protocol's outputs.
Xiong, Zhu, and Huang (2023) presented a robust protocol for distributed counting that removes the oblivious assumption. However, their communication complexity is suboptimal by a polylog(k) factor and their protocol is substantially more complex than the oblivious protocol of Huang et al. (2012). This left open a natural question: could it be that the simple protocol of Huang et al. (2012) is already robust?
We resolve this question with two main contributions. First, we show that the protocol of Huang et al. (2012) is itself not robust by constructing an explicit adaptive attack that forces it to lose its accuracy. Second, we present a new, surprisingly simple, robust protocol for distributed counting that achieves the optimal communication complexity of $O(\frac{\sqrt{k}}{\eps} \log N)$. Our protocol is simpler than that of Xiong et al. (2023), perhaps even simpler than that of Huang et al. (2012), and is the first to match the optimal oblivious complexity in the adaptive setting.
View details
Architecting Simulation-Acceleration-Ready SoC Testbenches to Left-Shift Critical Verification cycles
Naveen Tumati
Rahul Chandran
Vijayprasanth V
2026
Preview abstract
Simulation acceleration platforms such as SimXL are reshaping how complex SoC architectures are verified, allowing performance benchmarks, boot flows, and low-power scenarios to run at speeds unreachable by traditional RTL simulation. Adopting SimXL, however, is not a drop-in change: it demands a restructured testbench architecture, new memory-loading and clock-modeling strategies, and a rethinking of how bus trackers, coverage, and assertions are implemented once design logic is compiled directly into an emulator target. This paper documents the architecture, bring-up challenges, and debug methodology developed while deploying SimXL across multiple concurrent SoC verification domains.
View details
Quantum Advantage in Topological Data Analysis via Mayer Homology
Anh Nghiem
Dominic Berry
Trung Phan
Guo-Wei Wei
Ryu Hayakawa
arXiv:2609.28058 (2026)
Preview abstract
Prior work has explored quantum algorithms for topological data analysis (TDA), revealing the possibility of exponential quantum speedups in estimating the ratios of Betti numbers to the dimension of the combinatorial Laplacian. However, this quantity is only non-vanishing and efficient-to-quantumly-estimate when Betti numbers are exponentially large, a case for which concrete examples are rarely known. Furthermore, certain randomized classical algorithms are sometimes efficient in this regime. Thus, the prospect of achieving quantum advantage in conventional TDA appears fairly narrow. Here, we address these challenges to the quantum advantage in TDA by developing quantum algorithms for Mayer homology, which generalize simplicial homology to N-nilpotent boundary operators (∂N=0) and have recently been successfully applied to real-world TDA contexts. We introduce an efficient quantum algorithm for estimating Mayer Betti numbers and their persistent counterparts. We then prove that for high-order simplices, Mayer Betti numbers are often exponentially large in the dense regime, which ameliorates the normalization bottleneck of conventional quantum TDA. In the same regime, we argue that existing dequantization algorithms developed for conventional TDA, when applied to Mayer homology, generally lose theoretical guaranties, facing certain structural barriers that prevent their practical utilities. We also provide logical resource estimates revealing that a quantum computer with roughly a few hundred qubits and sixty million Toffoli gates could solve Mayer homology problems beyond the capabilities of known classical approaches. Finally, we discuss real-world applications of Mayer homology in genomics, supersymmetry, drug discovery, and neuroscience, revealing the potential of our quantum algorithm to deliver real-world impacts via Mayer homology.
View details
