Let $f\colon F_2^n\to\{-1,+1\}$ have $F_2$-degree $d\ge2$. We prove that its deterministic parity decision tree depth satisfies \[ D_{\oplus} (f)= O(4^d \log_2\|\widehat f\|_1) = O(4^d \log_2 s(f)), \] where $\|\widehat f\|_1=\sum_ξ|\widehat f(ξ)|$ is the Fourier spectral norm and $s(f)$ is the Fourier sparsity. The bound is linear in the logarithm of the spectral norm for every fixed degree, with singly exponential dependence on $d$. This improves the previously best known bound of $O(2^{d^2/2} \log^{d-2} \|\widehat f\|_1)$ due to Tsang, Wong, Xie and Zhang (FOCS 2013). Our result establishes the log-rank conjecture for $\mathrm{XOR}$ functions of $F_2$-degree $O(\log\log s(f))$, extending the previously accessible range $d=O(1)$. The proof combines field lifting, multiplicative derivatives, a multiplicity-based generic-rank comparison, a Schur-complement vanishing argument, and dimension-preserving descent to $F_2$ to lower the degree on every coset of a common subspace.
Residual connections give each Transformer block access to all earlier layers only through one fixed sum, broadcast to all of the block's inputs. This broadcast bottleneck imposes three constraints: the query, key, value and residual inputs of a block, which we call its roles, read the same vector; all hidden dimensions within a role share one set of weights over earlier layers; and every earlier layer has the same fixed weight for every token. We propose the Multi-Role Multi-Group Mixing Residual (M3), which removes all three: every role, and every group of hidden dimensions within a role, reads its own token-dependent mixture of all earlier layers. M3 starts as an exact residual connection and adds as little as 1.4% parameters and 1.8% FLOPs. From 100M to 1.4B parameters, M3Former outperforms the Transformer and coarse-grained cross-layer connections at every size, matching a Transformer 1.19-1.34x the size of the one it modifies, trained with 1.4-1.8x the compute. Relaxing only some of the constraints recovers only part of this gain. M3Former also improves sparse mixture-of-experts models of up to 4.6B parameters and trains more stably in deeper networks. Code: https://github.com/Kingchet10/m3former
Bin Wang, Yan Zhong, Zhengyu Zhang, Liang Luo, Buyun Zhang, Ellie Wen
Language models now propose hypotheses faster than anyone can check them, so the step that certifies them must need nothing from the proposer but the hypothesis. We state three requirements for such a step -- per-hypothesis automatable, attributable and diagnostic -- and introduce NxN e-valuation, which meets them. A hypothesis names a scope, the units it is about, and gives each of them a restriction that scores its outcome. The units of one scope serve as nulls for one another, so no resampling model is written per hypothesis; the algorithm certifies a stable, scope-level association and reports whether the scope, the restriction, or which unit receives which restriction carries the prediction. For independently drawn units, betting e-values bound the chance of a false certificate for each hypothesis in finite samples, under stated nulls. A betting lower bound on the share of units that carry the association gates every certificate, and an asymptotically valid equivalence test calls the restrictions shared only when it rejects differences between them above a declared noise ceiling. We test it on planted data, on randomized intervention data, and on real purchase data with 285 hypotheses that language models wrote without knowing our method or our classes, labeled by human experts. Meeting all three requirements costs no accuracy: NxN makes 692 correct decisions in 693 with one false certificate, against 659 with four for a composite of CRT tests that returns our verdicts but needs a resampling model per hypothesis, and 224 with 468 for held-out validation. Removing any of our statistics merges a verdict that certifies with one that rejects. The certificates concern predictive association, not causality.
Tianyu Zhan, Gui Ling, Ran Tao, Kunhai Lin, Tong Xiong, Wang Yang, Kaixuan Zhang, Zhihong Chen 等 12 位作者
Generative retrieval (GR) typically relies on item-level beam search to retrieve candidates, leaving cross-item dependencies unmodeled and limiting direct optimization of list-level objectives. A natural alternative is to generate the entire list within a single autoregressive trajectory. However, greedy decoding with directly trained list-wise models substantially underperforms beam search. We identify two contributing factors: the broader search space explored by beam search and the positional bias of scarce positive signals, which deprives later positions of adequate supervision. To address these challenges, we propose $\textbf{SLIDE}$, a search-to-list item distillation framework that decouples offline search from online list generation. A teacher model retrieves high-quality candidates through offline item-level beam search, providing additional conversion-relevant supervision beyond sparse behavioral labels. Their Semantic IDs (SIDs) are then concatenated in beam-score order to form list-wise distillation targets. This search-to-list conversion transforms candidates retrieved along separate search paths into sequential item-generation targets within a single trajectory. Trained on these targets, the student generates the Top-$K$ list in a single greedy pass, also decoupling teacher scaling from online deployment. Experiments on FORGE and Taobao Search show that SLIDE substantially improves retrieval quality under single greedy decoding and, with stronger offline teachers, surpasses the beam-search reference. Supplementary RL experiments support the effectiveness of list-level generation.
Mobile GUI agents powered by LMMs can perceive screens and follow instructions, yet existing benchmarks largely target short, linear workflows and step-level accuracy, offering limited insight into long-horizon planning and decision-making under branching structures. We present DAC-Bench, a decision-aware benchmark with compositional tasks comprising 830 episodes and 11,345 action steps across 35 applications on Android and iOS. Tasks are organized into Sequential, Conjunctive, Conditional, and Hierarchical structures, reflecting real-world multi-step and branching interaction patterns. To complement standard step-level evaluation, we introduce weighted longest common subsequence to capture length-sensitive progress and decision accuracy for branch correctness. Evaluations across 7 diverse agents show substantial performance degradation compared to prior benchmarks, with success rates dropping below 5% on 6–8 step tasks and branch accuracy averaging 38%, highlighting challenges in conditional decision-making. By exposing these failure modes, DAC-Bench provides a challenging and diagnostic benchmark for advancing decision-aware mobile GUI agents. Our code and dataset are available at: https://github.com/YuqingZhangMirror12/DAC-Bench.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表
Wenkai Wang, Xiyun Li, Hongcan Guo ByteDance Inc., Wenhao Yu OpenAI, Tianqing Fang Tencent AI Lab, Haitao Mi Tencent AI Lab, Dong Yu CapitalOne, Shengyu Zhang Zhejiang University
Graphical User Interface (GUI) grounding requires mapping natural language instructions to precise pixel coordinates. However, due to visually homogeneous elements and dense layouts, models typically grasp semantic intent yet fail to achieve precise localization. While scaling sampling attempts (Pass@k) reveals potential gains, static self-consistency strategies derived from geometric clustering often yield limited improvements, as the model’s predictions tend to be spatially dispersed. In this paper, we propose replacing static consistency strategies with a learnable selection mechanism that selects the optimal target by critiquing its own proposals rendered on the screenshot. Given the significant disparity between the model’s grounding and critiquing capabilities, we propose a co-evolving Propose-and-Critic framework. To jointly optimize these, we introduce a maturity-aware adaptive co-evolutionary reinforcement learning paradigm. This approach dynamically balances the training objectives of proposer and critic, where the diversity of the proposer’s outputs enhances critic robustness, while the critic’s maturing discrimination capability conversely unlocks the proposer’s potential for extensive spatial exploration, fostering the mutual reinforcement and co-evolution of both capabilities, thereby ensuring generalizability to adapt to diverse and complex interface layouts. Extensive experiments over 6 benchmarks show that our method significantly enhances both capabilities.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表