Josh Alman, Baitian Li, Neha Pant, Kevin Pratt, Ryan Williams
We show that for any fixed $k$, there exists $\varepsilon_k > 0$ such that, given a $(k-1)$-uniform hypergraph $H$ on $n$ vertices, one can count the number of $k$-hypercliques in $H$ in $O(n^{k-\varepsilon_k})$ time. This refutes the hyperclique conjecture of Lincoln, Vassilevska Williams, and Williams (SODA 2018). Our result follows from the uniform construction of a family of arithmetic circuits of size $O(n^{k-\varepsilon_k})$ for the $k$-hyperclique tensor, a natural higher-order generalization of the matrix multiplication tensor. We obtain two corollaries. First, for every $k$, there exists $\varepsilon > 0$ such that Max-$k$SAT can be solved in $2^{(1-\varepsilon)n} \cdot \mathrm{poly}(m,n)$ time. Second, for every $k$, there exists $\varepsilon > 0$ such that arithmetic progressions of length $k$ in subsets of $\{0,1,\ldots,n\}$ can be detected in $n^{2-\varepsilon}$ time. Both corollaries refute other prominent conjectures in the literature.
This note is an exposition of the recent preprints from OpenAI that establish the bound $ω\leq 9/4$ on the matrix multiplication exponent. We argue that the heart of these preprints is a new technique, which we formulate as the untwisting lemma for semidirect sums of tensors. This gives a generally applicable method for analyzing tensors. We also discuss further consequences of this method, as well as the relation between the OpenAI proof and previous work.
Yujiao Shen, Jiahe Song, Haitian Li, Jingkang Yang, Ziwei Liu
Learning from human data offers a scalable path toward embodied intelligence, yet it requires models to accurately understand fine-grained human actions from egocentric observations. However, existing benchmarks remain limited in action atomicity, temporal precision, and hand-action association. We introduce EgoActionBench, a benchmark that represents continuous human manipulation as temporally localized atomic actions associated with the left hand, right hand, or both hands. EgoActionBench contains 1,407 episodes with 41,132 human-refined action annotations. To evaluate such dense predictions, we propose an evaluation protocol that retrieves temporally eligible candidates, selects a prediction by content agreement, and scores semantic fidelity and temporal overlap alongside action precision and recall, jointly capturing what happens, when it happens, and which hand performs it. We benchmark 20 baseline models and systems on EgoActionBench and further adapt two backbones, Qwen3-VL-4B and LLaVA-OneVision-2-8B, through supervised fine-tuning followed by reinforcement learning on automatically annotated training episodes. EgoAction improves EgoActionScore by 15.9 and 23.2 points on the two backbones, and both adapted models outperform all open-source baselines. Our experiments reveal substantial limitations of current models in action atomicity, temporal precision, and hand-action association, highlighting the gap between general video understanding and the action understanding required for embodied intelligence.
We show that the subset sum problem can be solved in randomized time $O(2^{0.49999\overline{7}n})$, breaking the $2^{n/2}$ meet-in-the-middle barrier. Our approach builds on the representation technique framework of Randolph and Węgrzycki (STOC 2026). We choose a representation for which testing the compatibility of pairs of partial solution vectors is exactly the partial match problem. To beat exponent $1/2$ for subset sum, it then suffices to give a nontrivial partial match algorithm in a certain parameter regime. We achieve this by designing a depth-2 linear circuit for the partial match matrix, which yields an efficient algorithm via the framework of Alman and Li (FOCS 2025).
Bo Gou, Jicheng Zhang, Jianlong Xiong, Tao He, Hai Wu, Bentian Liu, Yijiao Wang, Yu Zhang 等 13 位作者
Automated classification of standard echocardiographic views is crucial for efficient clinical workflow but faces three main challenges. First, publicly available datasets are scarce and limited in scale and view coverage. Second, the performance of some modern video-level architectures for echocardiographic view classification remains underexplored. Third, some view categories exhibit highly similar spatial appearances, making single-frame features insufficient for discrimination, while heterogeneous frame quality complicates robust temporal information fusion. To address these challenges, we release the Echocardiographic Videos of Nine Views (EV9V) dataset, comprising 5,138 videos, 910,579 frames, and 9 standard views, which is, to the best of our knowledge, the largest openly released echocardiography video dataset. Furthermore, we propose a Spatio-Temporal Fusion Model (STFM), an efficient dual-stream framework that jointly captures spatial anatomical structures and temporal cardiac dynamics. The STFM leverages uncertainty-aware learning to preferentially sample representative video segments during training and evidence-based fusion during inference, improving robustness to variations in frame quality across echocardiographic videos. Extensive experiments demonstrate that STFM achieves competitive performance and effectiveness compared with diverse video classification architectures, including two-dimensional and three-dimensional convolutional neural networks, recurrent neural networks, and Transformers. The code is released at https://huggingface.co/datasets/bgx666/EV9V and the EV9V dataset is available at https://github.com/bgx666/stfm.
Ruoyu He, Jisen Li, Anthony Ji, Changyi Yang, Zetian Li, Runduo Ma, Zhen Zhang, Zhongzhu Zhou
A full-duplex model should answer easy questions immediately, but hard questions often need stronger reasoning, which may require waiting. The challenge is to choose between these paths at the moment the model begins to speak. Recent systems learn related mode decisions through special-token generation inside the dialogue model, coupling routing to turn-taking and temporally annotated full-duplex training. We study a post-training alternative. We freeze MiniCPM-o 4.5, using only its speech input and output, and fit a logistic failure readout on hidden states already available at its native listen-to-speak transition. The resulting gate requires no additional model generation and exposes thresholds that can be retuned without changing the duplex policy. A probe fitted on text-input states also reads the states of spoken questions, including unseen human recordings. On the internal benchmark, selective handoff improves answer accuracy by 27.1 points. Compared with always using the expert, it reduces mean server time to first answer audio by 31.5 percent. It also outperforms matched random routing across external speech question-answering pools, as well as a zero-shot GPT-5.4 mini router that rates the transcribed question. The training recipe also transfers to a second duplex model family. These results show that an existing duplex model can be equipped to answer easy turns immediately and wait for stronger reasoning or fresher knowledge on the turns that need it, without further duplex training.
As coding agents achieve increasingly high success rates on software engineering benchmarks, recent efforts have sought to increase task complexity through longer horizons and more extensive code modifications. However, real-world software development often spans multiple interdependent repositories, introducing additional challenges in dependency reasoning, change propagation, and interface consistency. Rather than further increasing complexity within individual repositories, we introduce CrossSWE, a benchmark for cross-repository joint development comprising 171 real-world instances spanning 165 repositories, 20 technical domains, and 13 programming languages. CrossSWE verifies the necessity of coordinated changes by testing whether partial repository modifications are insufficient to achieve the intended behavior. Our evaluation of five LLMs reveals substantial challenges, with the strongest model, GPT-6.1 Sol, achieving only 58.48% Pass@1. Furthermore, cross-repository inconsistencies emerge as the most prevalent failure mode (44.2%), highlighting the difficulty of maintaining consistency across interdependent repositories.
We present Youtu-Parsing-Omni, an omni-modal parser that converts documents, images, audio, and video into structured records grounded in space and time, providing a perception layer for agents that read, locate, and cite evidence across modalities. Its design rests on one encoder for every modality and one schema for every task. Youtu-Omni-Encoder, initialized from a pre-trained language model to strengthen text reading, encodes all modalities with shared weights in a unified space-time coordinate system, and a few fusion layers let video frames attend to concurrent audio, bringing cross-modal fusion and temporal alignment into perception itself. OmniSchema unifies the outputs of all ten parsing tasks, allowing a single self-evolving post-training procedure, OmniSchema-Aware On-Policy Distillation (OSAD), to provide a shared token-role-based objective across tasks. In each round, the model is trained on its own rollouts against token-level targets from a reference-conditioned copy of itself, which is then refreshed with the trained weights, so that the parser and its supervision co-evolve. With a single 5 B-parameter checkpoint, Youtu-Parsing-Omni achieves state-of-the-art performance on OmniDocBench v1.6 (96.96 Overall) and leads all open-weight models on OmniParsingBench (75.08 Avg.), with its advantage concentrated on audio and video. It also achieves the best overall chart-parsing score (95.02) and the highest exact chemical-fingerprint agreement among compared systems, and matches a dedicated optical-music model in character-level transcription of typeset sheet music while staying far ahead of general-purpose systems. Code and model weights are publicly available.
Heavy-tailed stochastic gradient noise, commonly observed in transformer models, can destabilize the optimization process. Recent works mainly focus on developing and understanding approaches to address heavy-tailed noise in the centralized or distributed, synchronous setting, while asynchronous optimization under such noise remains underexplored, especially in the practical settings with local updates. In this work, we first investigate two asynchronous communication schemes (server- and client-centric) that handle stragglers under heavy-tailed gradient noise. We further propose and theoretically analyze algorithmic modifications based on delay-aware learning rate scheduling and delay compensation to enhance the performance of asynchronous algorithms. Our convergence guarantees achieve the optimal rate under heavy-tailed noise and improve delay tolerance compared with existing asynchronous approaches. Empirically, our approaches outperform prior synchronous and asynchronous methods in terms of accuracy/runtime trade-offs and are more robust to hyperparameters in both image and language tasks.
Xutian Li, Bo Xiong, Yifeng Zhu, Runbang Yan, Yanzhen Zou, Lu Zhang, Bing Xie
Retrieving task-relevant code dependencies is critical for repository-level code generation. Existing approaches obtain dependency context through similarity-based retrieval, repository graphs, or LLM-driven exploration. A central challenge is to identify the dispersed dependencies needed to implement a functional requirement, rather than merely retrieve broadly related code. This paper presents FeatLens, a feature-guided dependency retrieval approach for repository-level code generation. FeatLens first builds an offline index linking natural-language feature descriptions to function-level code entities. Given a task requirement and target function location, it selects relevant features and constructs dependency seeds. It then expands the seed graph and applies semantic and structural heuristics to select dependencies for inclusion in the generation context. Experiments on DevEval and EvoCodeBench show that FeatLens achieves the highest dependency recall among the evaluated baselines at each fixed retrieval budget, reaching DR@15 values of 0.527 and 0.529, respectively. On DevEval, the retrieved context supports the highest non-oracle Pass@1 with both DeepSeek-V3.2 and GPT-5-mini. These results are obtained without LLM calls in the online dependency retrieval stage.
Motivated by the observational incompleteness of intermediate-to-long-period Earth-size planets, we present TransitNet, a compact attention-augmented deep-learning framework for low-SNR transit blind searches. To enable realistic method development and objective threshold calibration under blind-search conditions, we develop a unified dataset construction, benchmarking, and threshold-selection framework. On recovery benchmarks constructed from unseen Kepler targets, TransitNet attains 95.2 percent accuracy in the challenging SNR range of 6 to 8 and outperforms both TLS and BLS, achieving ROC-AUC and PR-AP values of 0.974 and 0.982, respectively. In an injected Earth-size and sub-Earth-size transit recovery experiment, TransitNet achieves a recovery rate of 93.0 percent, substantially exceeding those of TLS (63.1 percent) and BLS (60.0 percent). In addition to detection, TransitNet provides attention-based estimates of transit windows and midpoints. On an independent evaluation set, 97.4 percent of injected transits are fully covered by the estimated transit window. Applied to real Kepler observations, the model successfully recovers all 34 selected confirmed Kepler planets, with a mean absolute transit midpoint error of 1.24 hours. The model combines a compact footprint of about 1.5 MB with high inference efficiency, yielding speed-ups of about 12 to 25 times relative to CPU-TLS and about 4 to 5 times relative to CPU-BLS. These results demonstrate that TransitNet provides an accurate, scalable, and computationally efficient framework for low-SNR transit blind searches in the tested regime and motivate its extension to longer-period Earth-size planet searches.
Multimodal Large Language Models (MLLMs) have achieved remarkable performance in Visually Rich Document Understanding (VRDU) tasks, but their capabilities are mainly evaluated on pristine, well-structured document images. We consider content restoration from shredded fragments, a challenging VRDU setting that requires integrating visual pattern recognition with semantic reasoning under significant content discontinuities. To facilitate systematic evaluation of complex VRDU tasks, we introduce ShredBench, a benchmark supported by an automated generation pipeline that renders fragmented documents directly from Markdown. The proposed pipeline ensures evaluation validity by allowing the flexible integration of latest or unseen textual sources to prevent training data contamination. ShredBench assesses four scenarios (English, Chinese, Code, Table) with three fragmentation granularities (8, 12, 16 pieces). Empirical evaluations on state-of-the-art MLLMs reveal a significant performance gap: The method is effective on intact documents; however, once the document is shredded, restoration becomes a significant challenge, with NED dropping sharply as fragmentation increases. Our findings highlight that current MLLMs lack the fine-grained cross-modal reasoning required to bridge visual discontinuities, identifying a critical gap in robust VRDU research.
Peter Romero, Haotian Li, Hugo Save, Luning Sun, Zachary R. Tidler, Kazuya Horibe, Joe Watson, Daniel Romero-Alvarado 等 11 位作者
We release a battery of 28 propensities for AI research, with expert-written rubrics, synthetic datasets, and annotated demand intervals, built with the method of Romero-Alvarado et al. (2026). We selected a wide collection of generic propensities that may influence the behavior of AI systems and humans. They are inspired by psychometric, psychological, and behavioral research, so that experimental results can be understood in the context of familiar constructs previously used also for human behavior research. The rubrics are useful for annotating existing benchmarks whose items may be relevant or not for one or more propensities. For easier profiling, however, the synthetic datasets are defined in such a way that they should be sensitive to one propensity only, allowing for a quick prototyping of propensity profiles using the battery of datasets. We also outline directions for future propensity research.
Qiuyi Qi Zhejiang University, Tian Liang Zhejiang University, Mutian Bao Zhejiang University, Jinjian Zhang Ant Group, Dongnan Liu Ant Group, Wei Zhou, Linjian Mo Ant Group, Ming Kong Zhejiang University 等 11 位作者
Reinforcement Learning (RL) is the dominant paradigm for training Large Language Model (LLM) agents on long-horizon tasks. However, sparse and delayed rewards often lead to trajectory neglect, in which agents lose focus on the task goal and interaction history at intermediate steps. Prior work has explored step-level supervision using Shannon-entropy–based uncertainty signals, which conflate inherent state complexity with agent confidence and therefore provide unreliable estimates of decision reliability. To address this issue, we propose normalized entropy, which measures confidence deviations relative to an agent’s average behavior under a given state, thereby strengthening the association between low-quality actions and trajectory neglect. Building on this insight, we introduce Selective Trajectory-Aware Policy Optimization (STAPO), a hierarchical group-based RL framework. STAPO leverages normalized entropy to locate outlier steps associated with trajectory neglect and optimizes them via a joint mechanism of trajectory-aware reward and trajectory-independent penalty, enhancing trajectory awareness while preserving training stability. Extensive experiments on ALFWorld, WebShop, and Search-Augmented QA demonstrate that STAPO achieves state-of-the-art performance while substantially alleviating trajectory neglect, validating its effectiveness and robustness for agentic tasks.
尚无 AI 解读，展示原文摘要
cs.CL · cs.AI
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表
Mutian Bao Zhejiang University, Qiuyi Qi Zhejiang University, Tian Liang Zhejiang University, Jinjian Zhang Ant Group, Wei Zhou, Ming Kong Zhejiang University, Linjian Mo Ant Group, Qiang Zhu Zhejiang University
Current evaluations of geospatial reasoning in LLMs are frequently impeded by the entanglement of factual recall and spatial logic, which often obscures the models’ true capabilities in complex city-scale environments. To address this, we introduce UrbanGeoEval, a comprehensive benchmark featuring a dual-module framework designed to disentangle these competencies. The Knowledge Module assesses urban memory via scalable map-based queries, while the Reasoning Module isolates pure logical inference across 3,148 realistic tasks by providing necessary geospatial context. Unlike prior benchmarks that hand the model pre-computed spatial text, UrbanGeoEval provides raw geometry and forces the model to act as a spatial computing engine. Our evaluation methodology introduces a reliable hybrid pipeline that merges deterministic programmatic checks with an LLM-as-a-Judge, achieving expert-level evaluation accuracy. Extensive experiments on 18 widely used LLMs uncover critical insights: (1) models exhibit severe geographic biases and resolution gaps; (2) failures in complex multi-hop tasks often stem from brittle foundational spatial skills rather than high-level logic deficits. UrbanGeoEval provides a precise diagnostic tool for advancing urban geospatial intelligence in LLMs.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表
Yanghao Zhou, Haitian Li, Rexar Lin, Heyan Huang Beijing Institute of Technology, Jinxing Zhou Mohamed bin Zayed University of Artificial Intelligence, Changsen Yuan, Tian Lan Alibaba Group, Ziqin Zhou Canva 等 15 位作者
Recent advances in text-to-audio-video (T2AV) generation have enabled models to synthesize audio-visual videos with multi-participant dialogues. However, existing evaluation benchmarks remain largely designed for human-recorded videos or single-speaker settings. As a result, structural failures in generated multi-talker dialogue videos, such as identity drift, unnatural turn transitions, and audio-visual misalignment, cannot be effectively diagnosed. To address this issue, we introduce MTAVG-Bench, a failure-driven diagnostic benchmark for multi-talker dialogue-centric audio-video generation. MTAVG-Bench is built via a semi-automatic pipeline, where 1.8k videos are generated using mainstream T2AV models with carefully designed prompts, yielding 2.4k manually annotated QA pairs for fine-grained failure diagnosis. The benchmark evaluates multi-speaker dialogue generation at four levels: audio-visual signal fidelity, temporal attribute consistency, social interaction, and cinematic expression. Built on a hierarchical failure taxonomy and a targeted QA protocol, MTAVG-Bench is primarily designed to evaluate whether proprietary and open-source omni-models can reliably identify failure modes in multi-speaker T2AV outputs. We benchmark 12 proprietary and open-source omni-models on MTAVG-Bench, with Gemini 3 Pro achieving the strongest overall performance, while leading open-source models remain competitive in signal fidelity and consistency. Overall, MTAVG-Bench enables fine-grained failure analysis for rigorous model comparison and targeted video generation refinement.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表