This paper presents a near-quadratic-time algorithm that correctly matches almost all nodes of two correlated Erdős-Rényi graphs without any incorrect matches. Each graph has average degree $λ$ and its edges are subsampled from a common parent Erdős-Rényi graph with $n$ nodes, with subsampling probability $s$. The nodes of one graph are then relabeled by an unknown permutation. The algorithm is built on a test for correlated versus independent Galton-Watson trees with approximated likelihood ratios. For every constant $s>\sqrt{C_{\mathrm{Otter}}}$, where $C_{\mathrm{Otter}}\approx0.338$ is Otter's tree-counting constant, and every $λ=ω(1)$ with $λ=(\log n)^{O(1)}$, the algorithm outputs a partial matching of size $n-o(n)$ that contains no incorrect matches with high probability. If, in addition, $λs\ge(1+ε)\log n$ for a constant $ε>0$, a seeded completion step recovers the permutation exactly. In both cases, the time complexity of the algorithm is $n^{2+o(1)}$ with high probability, whereas previous polynomial-time algorithms with the same guarantees either have a time-complexity bound whose exponent goes to $\infty$ as $s$ approaches $\sqrt{C_{\mathrm{Otter}}}$ from above, or apply only when $s$ is close to $1$.
We study the $(1-\varepsilon)$-approximate maximum weight matching problem in general graphs with $n$ vertices and integer edge weights in $[1,W]$. For $W=n^{O(1)}$, we obtain faster algorithms in the semi-streaming and dynamic settings: (1) Semi-streaming: Deterministic $O(\varepsilon^{-2})$-pass and $O(\varepsilon^{-2}\log(1/\varepsilon))$-pass algorithms for unweighted and weighted matching. (2) Incremental: A deterministic algorithm for weighted matching processing $m$ edge insertions in total time $O((m\varepsilon^{-3}+n\varepsilon^{-6})\log^3 n)$. (3) Decremental: A randomized algorithm for weighted matching processing all edge deletions from an $m$-edge graph in total time $O((m\varepsilon^{-8}+n\varepsilon^{-47})\log^{O(1)}n)$ with high probability. (4) Fully dynamic: A deterministic reduction from weighted matching in general graphs to unweighted matching in bipartite graphs incurring $O(\varepsilon^{-4}\log^{O(1)}(1/\varepsilon))$ multiplicative update-time overhead, independent of $n$. Underlying these results is a unified framework that reduces the problem to repeatedly solving two simpler matching subproblems: a $(1-\varepsilon)$-approximate maximum weight matching on a sparse subgraph with $O(n/\varepsilon)$ edges, and a constant approximation on the remaining edges. The framework builds on dual entropy regularization, a smoothing technique underlying efficient solvers for packing linear programs. To handle the exponentially many odd-set constraints, we adapt the smoothing technique to regularize only the vertex duals and develop a new cut partition that preserves odd-set feasibility during optimization.
Maojiang Su, Jiale Chen, Qijie Zhu, Shang Wu, Jiayi Wang, Jihai Zhao, Guo Ye, Yibo Wen 等 9 位作者
PairFormer-based all-atom models demonstrate strong capabilities in biomolecular binder design. However, existing methods often use all-atom representations for modality-specific binder design, such as protein and peptide design. In contrast, recent geometric latent diffusion models pursue unified binder design by representing molecular blocks from different modalities in a shared latent space. These complementary strengths motivate us to investigate how to generalize the use of pretrained all-atom representations to unified binder design. We introduce PairFuse, a parameter-efficient method that enables this generalization through representation fusion. Specifically, we use lightweight layerwise adapters to integrate pretrained all-atom representations into an independently pretrained geometric latent diffusion model. Our adapters integrate pretrained all-atom representations through two mechanisms: enriching the diffusion model's molecular block features and incorporating pairwise structural information into the geometric diffusion model's denoiser. Theoretically, we prove that the augmented denoiser preserves geometry and pairwise attention fusion provides additional attention expressivity beyond feature-only fusion. Experimentally, across antibody, peptide, and small molecule binder-design benchmarks, PairFuse achieves stronger performance than the pretrained diffusion model and existing representation-fusion baselines.
Jiale Cheng, Yusen Liu, Xinyu Zhang, Yulin Fei The Hong Kong University of Science and Technology, Wenyi Hong Department of Computer Science and Technology, Tsinghua University, Ruiliang Lyu Zhipu AI, Weihan Wang, Zhe Su 等 14 位作者
Large language models (LLMs) conventionally represent text as sequences of discrete tokens, making long-context scaling largely a matter of processing more tokens more efficiently.We instead explore a complementary direction: increasing how much original context each token represents.To this end, we introduce Glyph, a framework that renders long texts into compact visual pages and processes them with a vision-language model (VLM), allowing a fixed context window to cover substantially more text.To make visual compression practical, Glyph combines continual pre-training on rendered long-text data, an LLM-driven genetic search to identify rendering configurations that balance compression and task performance, and post-training with supervised fine-tuning and reinforcement learning.Across multiple long-context benchmarks, Glyph achieves 3–4× token compression while maintaining performance comparable to strong text-only LLMs such as Qwen3-8B, with over 4× faster prefilling and decoding and 2× faster supervised fine-tuning.Under more aggressive compression, a VLM with a 128K context window can handle tasks that would otherwise require up to 1M input tokens.Our code and model are released at https://github.com/thu-coai/Glyph.
尚无 AI 解读，展示原文摘要
cs.CL · cs.CV
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表
Large language models (LLMs) have demonstrated better safety performance in high-resource languages than in low-resource languages. We attribute this issue as a mismatch gap between language-agnostic semantic understanding ability and language dominant safety alignment biased toward high-resource languages. Based on above insights, we empirically identify the semantic bottleneck in LLMs: intermediate layers in which the geometry of model representations is governed primarily by shared semantic content rather than language identity. Then, we propose Language-Agnostic Semantic Alignment (LASA), which anchors safety alignment directly in semantic bottlenecks. Experiments show that LASA substantially improves safety across all languages: average attack success rate (ASR) drops from 24.7% to 2.8% on LLaMA-3.1-8B-Instruct and remains within 3–4% across Qwen2.5 and Qwen3 Instruct models (7B–32B). Besides, our analysis and method offer a representation-level perspective on LLM safety, suggesting that safety alignment requires anchoring safety understanding not in surface text, but in the model’s language-agnostic semantic space.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表
Data selection is a critical aspect of Reinforcement Learning with Verifiable Rewards (RLVR) for enhancing the reasoning capabilities of large language models (LLMs). Current data selection methods are largely heuristic-based, lacking theoretical guarantees and generalizability. This work proposes a theoretically-grounded approach using influence functions to estimate the contribution of each data point to the learning objective. To overcome the prohibitive computational cost of policy rollouts required for online influence estimation, we introduce an off-policy influence estimation method that efficiently approximates data influence using pre-collected offline trajectories. Furthermore, to manage the high-dimensional gradients of LLMs, we employ sparse random projection to reduce dimensionality and improve storage and computation efficiency. Leveraging these techniques, we develop Curriculum RL with Off-Policy Influence guidance (CROPI), a multi-stage RL framework that iteratively selects the most influential data for the current policy. Experiments on models up to 7B parameters demonstrate that CROPI significantly accelerates training. On a 1.5B model, it achieves a 2.66x step-level acceleration while using only 10% of the data per stage compared to full-dataset training. Our results highlight the substantial potential of influence-based data selection for efficient RLVR.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表