Memory-augmented assistants retrieve evidence from stored conversations and documents to answer queries. Most embedding-based retrievers compare single-vector representations of queries and memories, even when relevance depends on a small part of the content. Such local evidence can be matched to queries using the contextual token representations already computed by the same embedding models. Our method uses sparse token matching to improve retrieval without additional training. Each query token retrieves a small set of matching tokens across candidate memories. The matching scores are aggregated for each memory and combined with whole-memory similarity to rank memories. An optional low-rank query adapter can be trained with supervision while keeping the encoder and stored memory representations fixed. Our method improves retrieval across eight benchmarks and multiple model families without additional training. Query adaptation further increases the gains to 13.3 and 14.3 percentage points in average Recall@10 and NDCG@10 on Qwen3-Embedding-4B. These retrieval gains translate into higher question-answering accuracy on long-term memory benchmarks.
Memory retrieval aims to identify evidence from stored records to answer a query. Stored records with different factual details may share topics, entities, or events. Such shared contents would make records without the required evidence more likely to receive high similarity scores and outrank the correct evidence. In this paper, we use the information shared by these records to construct local references for query-memory matching. We propose NEighborhood-Aware Residuals (NEAR), a training-free framework that uses these references to construct residual representations that complement the original embeddings. Specifically, each memory derives a reference direction from its neighbors, and each query obtains its reference from a precomputed table. Using these references, NEAR constructs projection residuals for both queries and memories. These residuals are combined with the original embeddings for a single approximate nearest-neighbor search over a fixed memory index. Experiments on eight long-context retrieval benchmarks show consistent improvements across nine embedding models. Downstream evaluations show that NEAR improves question-answering performance.
NP-Hardness and Additive Inapproximability of Deterministic Communication Complexity
Serge Gaspers, Tao Zixu He, Simon Mackenzie
AI 速览：作者报告：给定布尔函数完整真值表，确定两方计算该函数所需最小最坏情况通信比特数是NP困难的，且在任何固定加性误差下不可近似。
Given the full truth table of a Boolean function whose input is split between two players, we study the complexity of determining the minimum worst-case number of bits they must communicate to compute it. This is a basic meta-complexity question, posed by Yao in 1979. We prove NP-hardness of approximation within every fixed additive error for deterministic communication complexity, under deterministic polynomial-time reductions. The result holds both in the standard model and in Yao's original model, where the players alternate after every bit and only the receiver of the last bit must determine the answer. In particular, it resolves the exact computation question under Yao's original conventions. Earlier versions of this same paper established exact NP-hardness for the standard model, independently and concurrently with Hirahara, Ilango, and Loff. In both models, a polynomial-time estimator with any fixed additive error would yield a polynomial-time $3$-SAT algorithm, deterministic or bounded-error randomized according to the estimator. For the standard model, we also give quantitative implications for errors that grow with the number $T$ of table entries. A bounded-error randomized polynomial-time estimator with additive error $c\log T/\log\log T$, for any fixed $0\le c<1/8$, yields a bounded-error randomized $3$-SAT algorithm on $N$ variables and $O(N)$ clauses running in time $2^{O(N^α)}$ for every fixed $8c<α<1$. A deterministic polynomial-time estimator with additive error $c_*\log\log T$, for an effective absolute constant $c_*>0$, yields a deterministic algorithm running in time $2^{O((\log N)^2)}$ on such formulas.
Jialiang Guo, Fucheng Xiong, Xu He, Haodong Zhao Meituan, Xingyang li Meituan, Ke Zeng, Xunliang Cai Meituan
Reinforcement Learning with Verifiable Rewards (RLVR) has become the standard paradigm for enhancing reasoning capabilities in Large Language Models, yet on-policy algorithms like GRPO suffer from sample inefficiency. Current experience replay methods for RLVR typically replay correct trajectories to consolidate learned reasoning patterns and accelerate convergence, but overlook the vast failure space. This work investigates how to effectively replay failure trajectories. We find that the high heterogeneity of failures renders random replay ineffective, and that high-value negatives should be both gradient-efficient and structurally proximal to correct solutions. To this end, we propose NexGRPO, which employs mid-confidence gating to filter invalid noise and saturated errors, and utilizes boundary failure sampling to retrieve boundary errors semantically similar to correct solutions for targeted refinement. Extensive experiments on mathematical and general reasoning benchmarks demonstrate that NexGRPO outperforms strong baaselines and achieves improved out-of-distribution generalization.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表