The Nash-Williams--Tutte theorem characterizes the existence of $k$ edge-disjoint spanning trees by a condition on every vertex partition. We prove that, for simple graphs, the same condition guarantees $k$ edge-disjoint spanning trees, each of diameter $O(n/δ)$ and with $O((n/δ)\log(δ+1))$ internal vertices, where $n$ is the number of vertices and $δ$ is the minimum degree. Both bounds hold simultaneously for every tree, with absolute implicit constants independent of $k$, and each is asymptotically optimal in general. Our proof is constructive and yields a randomized algorithm with expected running time $\tilde{O}(n^5)$. We derive applications to short edge-disjoint routes and weak linkages, small Steiner trees, and survivable networks with short paths. The joint bounds also yield low-diameter spanning Eulerian subgraphs and short tours for postman and general routing problems.
Annika Bätz, Pavel Klasek, Seo-Young Ham, Martin Lauer
Benchmark suites are crucial for advancing computer vision research, providing not only curated datasets but also standardized evaluation protocols for reproducible comparison. The railway domain lacks such resources, hindering progress in automated train operation. To address this gap, we present RAIL-BENCH, the first perception benchmark suite designed specifically for railways. RAIL-BENCH comprises five challenges - rail track detection, object detection, vegetation segmentation, multi-object tracking, and monocular visual odometry - each tailored to railway-specific characteristics and including a curated dataset from diverse real-world scenarios, evaluation metrics, and public scoreboards; we demonstrate the first three challenges in this paper. We further introduce LineAP, a novel segment-based average precision metric for rail track detection that decouples geometric accuracy from instance-level grouping and employs a track-width-based distance threshold approximating a fixed real-world distance, addressing key limitations of existing line detection metrics. Our benchmark suite is publicly available at https://www.mrt.kit.edu/railbench/.
Natural gradient descent, and the preconditioned optimizers which have followed from it, correct gradient descent by estimating curvature and applying its inverse to the gradient. For any single layer of a deep neural network, this correction can be shown to approximately separate into two factors: one which accounts for correlations in the gradient signal, and one which accounts for correlations in the data arriving at that layer. Herein we show that this second factor can be expressed as a change of basis rather than of curvature and, considered thus, it can be removed from the optimizer entirely and placed within the network itself. Specifically, we show that, once forward weights are corrected, right-sided natural gradient descent can be implemented in a form which has three exactly equivalent forms: a gradient preconditioner, a decorrelating linear transform in the forward pass, or a set of recurrent dynamics in which all updates are Hebbian and rely only upon locally available signals. The (recurrent) decorrelation method we discover aligns closely with proposed methods for inhibitory learning and homeostatic plasticity in the brain. Notably, our transform requires no matrix inverse, no matrix decomposition, and no information beyond that which is available at an individual synapse. It can therefore be applied in distributed and physically constrained systems, including neuromorphic hardware and nervous systems, where existing preconditioners cannot. We demonstrate its effectiveness empirically in convolutional and residual network models while significantly improving a range of approximate biologically plausible methods for credit assignment.
We give a deterministic algorithm that counts the linear extensions of any $n$-element poset in $O^*(33^{n/6}) \le O^*(1.791^n)$ time and space, breaking the $O^*(2^n)$ barrier of standard order-ideal dynamic programming without assumptions on height, width, or dimension. Our algorithm fixes an antichain $B$ and tracks order ideals only on the remaining core $V \setminus B$. For each element $v \in B$ that has successors in the core, we guess which of those successors appears first in the linear extension, reducing all upper constraints on $v$ to a single deadline. An element $v \in B$ becomes available once all of its core predecessors have been placed; available elements with the same deadline then face identical remaining constraints, so the dynamic program only needs to record how many available elements have each deadline and weight transitions by the number of choices for the next element. Taking $B$ to be a maximum antichain and balancing this dynamic program against a Dilworth chain partition yields an $O^*(1.89^n)$ algorithm. To obtain our main bound, we use a minimum-cut computation in an auxiliary bipartite network to find an antichain $B$ whose comparability neighborhood $R$ satisfies $|B| \ge 5|R|$ while the remainder $V \setminus (B \cup R)$ partitions into stars with at most five leaves. Since a $j$-leaf star has $2^j+1$ independent sets and $(2^j+1)^{1/(j+1)} \le 33^{1/6}$ for $1 \le j \le 5$, combining the star bound on the remainder with our state bound on $B \cup R$ gives $O^*(33^{n/6})$ time and space.
Reinforcement learning with verifiable rewards (RLVR) typically improves pass@1 but can fall behind its base model at large sampling budgets $k$, commonly interpreted as sharpening existing solutions. Because adjacent pass@$k$ estimates reuse generations, pointwise error bars cannot establish a crossover. We formulate paired inference on the RL-minus-base difference curve: a prompt-level multiplier bootstrap yields a one-sided dominance test and simultaneous confidence bands requiring both an early gain and a later loss. Among nine public RLVR checkpoints at 3k-16k token limits, only one narrowly meets this criterion before multiplicity adjustment; asymmetric truncation can create, mask, or reverse crossovers. On 1,060 deduplicated competition problems at 32k tokens, two 1.5B models exhibit certified crossovers around $k\approx10$-$60$, while two 7B models show no supported loss. A paired variance decomposition shows why adding prompts improves power more than deeper sampling. Prompts with identical base success probability diverge after RLVR, with dispersion replicating across independent generation halves and violating Lipschitz slope bounds for reasonable deterministic maps. Modeling RLVR as a Markov kernel, Jensen's inequality shows that conditional dispersion depresses pass@$k$ for $k\ge2$. Once dispersion is modeled, the conditional-mean log-odds slope is below one in every pair: RLVR improves hard prompts on average, while late-$k$ loss comes from a 2%-3% minority of base-solved prompts collapsing onto a repeated modal wrong answer and resisting prefix rescue up to 4,096 tokens. In controlled runs from one base model on 3,000 new problems, all four GRPO arms fall behind near $k\approx200$ and remain behind through $k=4096$, while SFT stays significantly ahead throughout.
Jing Huang, Yu Cheng, Ziwei Yu, Lan Zhao, Sitan Li, Guangxiu Yao, Xin Wang, Yuanyong Luo 等 14 位作者
Quantization of Large Language Models (LLMs) has become increasingly important for reducing the computational costs and resource requirements for practical deployment. Growing interest in this area has motivated the community to move beyond 8-bit quantization towards 4-bit precision, leading to the development of customized 4-bit formats such as MXFP4 and NVFP4. Recently, HiFloat4 (HiF4) has emerged as a competitive alternative which adopts a Block Floating-Point (BFP) format with a three-level scaling hierarchy, thereby achieving a significantly larger dynamic range. While quantization can substantially reduce memory usage and accelerate inference, it frequently introduces accuracy degradation. Calibration is therefore essential for narrowing the performance gap between low-precision quantized models and their full-precision counterparts. Nevertheless, existing calibration methods are mainly designed and validated using integer-precision formats, such as INT4, lacking support for HiF4 due to its hierarchical BFP structure. In this paper, we investigate three calibration approaches, namely HiGPTQ, HiAutoRound, and HiFlatQuant, to further enhance model quantization based on the HiF4 format. Extensive experiment s demonstrate that all three proposed approaches improve inference accuracy compared with direct HiF4 conversion, reducing the gap between HiF4 and BF16 to less than 1% and outperforming the state-of-the-art NVFP4 format across various models and downstream tasks.
Under temporal nonstationarity, model performance rankings reverse across training horizons due to heterogeneous sensitivities to memory. While existing literature addresses adaptive lookbacks, effective model complexity, and empirical forecast evaluation in isolation, no unified framework explains the structural mechanics driving these rank reversals. We bridge this gap by deriving a model-agnostic decomposition of out-of-sample $R^2$ into target alignment, miscalibrated aggressiveness, and predictive instability. Within this framework, we mathematically characterize complexity phase boundaries, establish closed-form optimal-memory equations for ridge regression under local drift, and extend these guarantees to complex model architectures via surrogate bounds. We validate these theoretical dynamics by benchmarking 14 linear, tree-based, and neural architectures across large-scale financial panels. In doing so, our framework demonstrates that empirical model rank reversals are driven by predictable surges in miscalibrated aggressiveness, providing a rigorous mechanistic diagnosis of generalization under temporal shift.
Moving from geographically fragmented to pooled waiting lists in deceased-donor organ transplantation can improve efficiency, but it raises concerns about regional fairness and participation incentives. This paper studies Pareto gains from such transitions in a multi-class queueing model with impatient agents, perishable items, and a tractable homogeneous compatibility friction. In contrast to standard approaches that emphasize static match quality or overlook regional incentives in dynamic contexts, this analysis identifies dynamic risk pooling as the primary source of Pareto improvements for regions. Pooling reduces organ waste resulting from stochastic supply-demand fluctuations, temporal mismatches, and random compatibility outcomes. Although this dynamic surplus theoretically enables Pareto improvements, a purely utilitarian policy that treats all patients equally across regions often fails to achieve these improvements when regions are asymmetric. In these situations, utilitarian redistribution removes an excessive number of organs from high-supply regions and violates their participation constraints. To address this conflict, it is demonstrated that the set of achievable utilities can be represented by mixtures of static priority index policies. Building on this structure, the Constrained Pareto Frontier Search (CPFS) is proposed as a polynomial-time procedure that computes an approximately optimal allocation policy with arbitrarily small participation-constraint violations. The results indicate that, by adjusting priority indices to ensure redistribution remains within the gains from pooled supply, demand, and compatibility risk, policymakers can achieve global efficiency while maintaining local participation incentives.
Transolver has recently gained widespread adoption for solving diverse physical problems on unstructured geometric meshes by leveraging its Physics-Attention mechanism, which seamlessly extends standard softmax attention to handle physical domains at scale. For time-dependent problems, existing literature relies on time-conditioned or autoregressive rollouts to preserve temporal causality while retaining Physics-Attention as the spatial backbone. However, a fundamental limitation of this formulation is its sequential execution model, wherein computational costs scale linearly with the temporal horizon, rendering standard Transolver inefficient for transient problems despite its exceptional spatial efficacy. This bottleneck has historically hindered its broader application in time-dependent physical modeling. To address this limitation, we introduce TB-Transolver (also referred to as Temporally Bundled Transolver), an efficient framework built on temporal bundling that scales Transolver for time-dependent PDEs. Furthermore, we propose \emph{spatiotemporal coherence} (${\rm C(K)}$) as a general metric to systematically quantify snapshot correlation within a temporal bundle, enabling the \emph{a priori} selection of optimal bundle widths using training data alone, thereby avoiding expensive grid searches. We demonstrate the computational efficacy of TB-Transolver across four physically distinct domains, namely, plasticity, fluid dynamics, reaction-diffusion, and global weather forecasting; achieving training speedups of up to $29\times$ over conventional autoregressive and time-conditioned baselines. Finally, these computational gains are further amplified through distributed multi-node and multi-GPU parallelism, yielding aggregated speedups of up to $45.6\times$ at optimal bundle widths for systems exhibiting high spatiotemporal coherence compared to single-GPU implementations.
Silvio Martinico, Franco Maria Nardini, Cosimo Rulli, Rossano Venturini
Approximate Nearest Neighbors (ANN) search over neural embeddings powers modern retrieval systems such as Retrieval-Augmented Generation. Embeddings come in three representations (dense, sparse and multi-vector), and efficient search combines an index structure, a similarity function and a quantization scheme. Existing libraries fix one combination, hard-code each one separately, or factor only one side of the problem, and none covers all three representations. We present Vectorium and kANNolo, two open-source Rust libraries that split this design space into a data-management layer and an indexing layer. Vectorium abstracts the vector, the distance function, the quantizer and the dataset independently, and provides 11 encoders, from 32-bit floats to sub-bit codes. On top of it, kANNolo implements Hierarchical Navigable Small-World (HNSW) graph and Inverted Vector File (IVF) indexes that are generic over representation, encoder and metric, and a two-stage index that composes any first-stage index with any rescoring dataset. Since every combination is specialized at compile time, this modularity adds no run-time overhead, and the resulting indexes reach state-of-the-art performance: our Product Quantization matches Faiss in accuracy at competitive speed, our RaBitQ and HNSW match or outperform their reference implementations, and our IVF outperforms Faiss. Against six dense and five sparse systems on seven public collections, our indexes give the best memory-throughput trade-off on dense data in 9 of 12 collection-accuracy pairs and perform well on out-of-distribution queries. On sparse data, the systems built on Vectorium lead on all three collections, with Seismic and SeismicWave the fastest and kANNolo's indexes the most compact.
Recent developments in AI for Mathematics (AI4Math), especially Large Language Model (LLM)-driven theorem provers, has achieved remarkable success in formal proof generation for well-defined mathematical problems through Interactive Theorem Proving (ITP) languages. However, current systems remain fundamentally limited in tackling frontier research mathematics, such as discovering new theorems or resolving open conjectures, which are often open-ended, under-specified, and involve multiple layers of abstraction. We argue that the next leap in AI4Math systems requires a decisive shift from predefined problem-solvers to research agents that can address frontier mathematical challenges with rigorous formal mathematical reasoning. In this position paper, we provide a systematic review of the field, covering datasets, auto-formalization, and proof synthesis. More importantly, we identify core limitations of existing systems in serving as mathematical research agents, examining issues across datasets, relational structure, mathematical exploration, tool ecosystem, and human-AI collaboration, outlining a strategic road-map for the future of AI4Math.
Speech Emotion Recognition (SER) in low-resource languages remains a challenging problem due to limited labeled data. In this work, we study the use of Whisper for Persian SER with a particular focus on representation dimensionality reduction and language-specific model adaptation. We propose a SER framework in which frame-level embeddings extracted from the Whisper encoder are reduced in dimensionality using PCA, eliminating the need for learned projection layers and substantially reducing the number of trainable parameters. The reduced representations are aggregated using an attention-based pooling mechanism and classified with a lightweight prediction head. In addition, we investigate whether fine-tuning Whisper on a Persian automatic speech recognition (ASR) task improves downstream SER performance. Experiments conducted on the ShEMO dataset under a speaker-independent evaluation protocol show that PCA-based dimensionality reduction consistently improves emotion recognition performance while reducing training latency and memory usage. ASR fine-tuning yields only modest gains for SER, suggesting limited transfer from language adaptation to emotion-related representations under the evaluated conditions. These findings provide practical insights into the efficient use of large pretrained speech models for emotion recognition in low-resource languages.
Alan Nadelsticher Ruvalcaba, Chris Alvin, Supratik Mukhopadhyay, Adam Bess
Identifying ligands for a protein target requires searching a vast chemical space for a comparatively small set of compatible molecules. Existing machine learning approaches primarily address this problem by generating candidate ligands or scoring individual protein-ligand pairs, but provide limited information about the broader chemical space compatible with a binding pocket. We introduce RangeFinder, an SE(3)-equivariant transformer pocket-level model, trained and evaluated on BioLiP2 data, that predicts ranges over nine physicochemical ligand properties directly from pocket structure, chemistry, and evolutionary context. Using an intersection-over-union objective and evaluation metric (range-IoU), RangeFinder achieves a range-IoU of $0.464 \pm 0.002$, outperforming all deployable baselines while requiring only $12.2$ ms per pocket. We also quantify our method's ability to reduce the ligand search space while retaining compatible binders; in this regard, RangeFinder achieves a Reduction-Recall F-Score of $0.543 \pm 0.011$ --- once again outperforming all deployable baselines. Ablation experiments indicate that RangeFinder's performance depends more strongly on the density and quality of ligand supervision than on any individual input modality or specialized training strategy. Together, these results position RangeFinder as an inexpensive and effective molecular filtering prior, with demonstrated potential in narrowing the ligand search space of target pockets before docking, generation, or synthesis. The code for this project can be found at: https://github.com/alannadels/RangeFinder.
Hao Fu, Degang Sun, Wan Wei, Jinxia Wei, Chun Long, Peng Gao
Text-to-SQL translates natural language questions into SQL queries, enabling database access without writing SQL. Fine-tuning open-weight large language models (LLMs) is cost-effective, but existing methods treat SQL as ordinary text and optimize token-level likelihood without explicitly modeling its syntactic, semantic, and logical requirements. Thus, a single incorrect alias or comparison operator can invalidate a query while contributing little to training loss. We propose SQLoom, a constraint-aware fine-tuning framework with supervision at three levels: syntactic validity under SQL grammar and database schema, semantic alignment between query decisions and the question, and logical consistency across dependent clause decisions. SQLoom extends supervised fine-tuning with a unified set-contrastive objective favoring sets of correct outputs over minimally different incorrect ones at each level. LLM agents propose this supervision, which a SQL parser and execution on counterexample databases verify. We also release Spider-Refined, a training dataset correcting 378 flawed Spider annotations and enriching database schemas. Experiments on Spider, BIRD, and three perturbed Spider variants show that SQLoom improves execution accuracy for Qwen3-1.7B from 62.9% zero-shot to 88.7% on Spider development, reaching 89.2% on Spider test and 73.4% on BIRD development. It outperforms fine-tuning, reinforcement learning, and agent-based baselines with up to 70 billion parameters. On question perturbations, SQLoom loses at most 0.6 accuracy points versus up to 12.1 for agent-based methods. It generates SQL in a single pass at 0.42s per query, 23$\times$ faster than a GPT-4-based agent method. These results demonstrate the effectiveness of set-contrastive supervision over token-level training.
Face recognition systems have advanced significantly through deep learning techniques, delivering high performance and robustness in complex scenarios. However, these approaches incur substantial computational overhead, limiting their in situ applicability in resource-constrained platforms such as drones, where they can address challenges including non-frontal facial imagery. Memristor-based neuromorphic systems have emerged as a compelling approach for edge AI applications, combining biologically inspired processing with efficient and scalable computation. In this work, we propose a facial recognition framework that addresses non-frontal pose variations by integrating lightweight generative adversarial network (GAN)-based pose frontalisation with memristor-based neuromorphic recognition. The experimental results on two datasets demonstrate the effectiveness of combining adversarial learning with memristive technology, achieving up to 96% identification accuracy. The proposed approach alleviates the computational bottlenecks of conventional AI and offers a scalable, efficient solution for face recognition in dynamic real-world environments.
Junxi Wu, Kailin Huang, Dongjian Hu, Bin Chen, Hao Wu, Shu-Tao Xia, Changliang Zou
Detecting AI-generated text is an important but challenging problem. Existing likelihood-based detection methods are often sensitive to content complexity and may exhibit unstable performance. In this paper, our key insight is that modern Large Language Models (LLMs) undergo alignment (including fine-tuning and preference tuning), leaving a measurable distributional imprint. We theoretically derive this imprint by abstracting the alignment process as a sequence of constrained optimization steps, showing that the log-likelihood ratio can naturally decompose into implicit instructional biases and preference rewards. We refer to this quantity as the Alignment Imprint. Furthermore, to mitigate the instability in high-entropy regions, we introduce Log-likelihood Alignment Preference Discrepancy (LAPD), a standardized information-weighted statistic based on alignment imprint. We provide statistical guarantee that alignment-based statistics dominate Fast-DetectGPT in performance. We also theoretically show that LAPD strictly improves the unweighted alignment scores when the aligned and base models are close in distribution. Extensive experiments show that LAPD achieves an improvement 45.82% relative to the strongest existing baselines, yielding large and consistent gains across all settings.
Hao Jiang, Peiru Du, Pengfei Yao, Mengting Li, Siyuan Lou, Kuo Cai, Sheng Yu, Qiang Luo 等 13 位作者
Large language models (LLMs) have demonstrated strong reasoning capabilities, motivating their use as the backbone of foundation recommendation models (FRMs). Existing methods enhance recommendations through explicit Chain-of-Thought (CoT) reasoning under a Think-then-Answer paradigm. However, explicit CoT incurs substantial inference overhead by generating lengthy reasoning traces and relies on manually designed templates that struggle to capture diverse, dynamic user interests. We propose OneLatent, an efficient latent reasoning framework that compresses explicit reasoning traces into several learnable latent tokens, enabling Latent-Reason-then-Answer inference without generating verbose traces. OneLatent first introduces Multi-View Adaptive CoT (MV-ACoT), which creates diverse, high-quality teacher-generated supervision by exploring user interests from multiple perspectives and automatically adapting reasoning complexity to each instance. Building on pretrained FRMs, it then uses a three-stage latent-token alignment paradigm to progressively internalize CoT traces into learnable latent tokens. Finally, a multistage curriculum-based post-training strategy activates latent-token reasoning for downstream recommendation tasks. Experiments on an industrial-scale Kuaishou dataset and the public Kuaishou LLM-Rec benchmark show that OneLatent consistently outperforms explicit CoT-based methods and traditional baselines. Compared with the Think and No-Think variants of FRMs, OneLatent improves SID@64 by 17.44% and 9.33%, respectively, while achieving over 17x higher online inference throughput. We further develop a production serving system for scalable, real-time FRM inference. An online A/B test in Kuaishou's local-services advertising scenario shows that deploying OneLatent with this system yields an estimated 9.6% revenue lift over strong online baselines, including OneRec and OneReason.
Large language model agents increasingly take consequential actions in digital and physical environments, where safety risks may emerge only after multiple interaction steps. This has motivated world-model-driven predictive safety guardrails, which anticipate future consequences before execution. However, existing evaluations largely focus on end-to-end safety outcomes, leaving unclear whether safety gains arise from reliable prediction and faithful use of predicted risks. In this work, we systematically diagnose the prediction-to-action pipeline along three dimensions: how world-model predictions are integrated into decision making, whether the predictions themselves are reliable, and whether their content is faithfully used. Across seven policy models and two safety environments, we find that stronger prediction involvement does not yield monotonic safety gains and can reduce task completion while substantially increasing inference cost. We further find that world-model predictions remain insufficiently reliable, especially over longer horizons, where safety prediction degrades substantially relative to near-term forecasting. Finally, we find that safety gains can persist even under corrupted predictions, while locally verified predictions still leave subsequent safety violations, showing that predictive content is not faithfully incorporated into the decision process. Together, these findings expose a fundamental prediction-to-action gap in current predictive guardrails: producing more or seemingly accurate foresight is insufficient unless that foresight is both reliable and faithfully translated into safer decisions.
Olivier Sprangers, Cristian Challu, Jan Rathfelder, Han Wang, Max Mergenthaler Canseco
Synthetic time series constitute a substantial share of the training corpora of several recent forecasting foundation models. Existing studies report benefits at small data budgets and modest synthetic proportions, but each evaluates individual combinations of model and generator. Studying these benefits systematically requires generators that support controlled configuration, perturbation, reproducibility and mechanism-level ablation, and the 11 existing generators we review show gaps in this combined support. We present SynForecast, an open-source Python library with 32 generators, 19 of which implement named mechanisms with a published source in econometrics, quantitative finance, statistical physics and point-process theory. Perturbations and mechanism families can be varied while everything else is held fixed, output comes in the long format that forecasting libraries accept, and output does not depend on the number of parallel workers. We evaluate SynForecast on M4 at five frequencies with a neural network and a gradient-boosted ensemble. A classical baseline attains the lowest error in nine of ten frequency-history combinations. A synthetic prior outperforms the same network trained from scratch at a fixed budget by up to 34% with a few dozen observations, but loses to it at full history at every frequency, and none of three pre-specified rescalings of history predicts where the sign changes. At the hourly frequency, where the prior fails at every history, the corpus lacks daily cycles; adding them reduces zero-shot error by 43 to 63% for both models. Fine-tuning outperforms training from scratch by up to about 15%, but at short histories a fixed 300-step fine-tune is worse than the pretrained model used as is. Removing the classical mechanism family costs about 2% for both models; every other family has a smaller effect outside the hourly frequency.
Asynchronous reinforcement learning (RL) is becoming a mainstream paradigm for post-training large language models (LLMs), as it improves training efficiency by updating the model as rollouts arrive. Recent work argues that group-wise sampling in GRPO does not naturally fit asynchronous RL training because rollout lengths follow a long-tailed distribution, and proposes Single-rollout Asynchronous Optimization (SAO) to improve stability and off-policy behavior, especially on agentic tasks. However, SAO relies on a closed-source value model obtained from scaling value pretraining. In this paper, we analyze GRPO and LiSAO, our lightweight reproduction of SAO without the pretrained value model, on single-turn reasoning and multi-turn agentic tasks. We find that GRPO outperforms LiSAO on reasoning tasks, while the reverse holds on agentic tasks. Since the value model of LiSAO is not yet well trained , LiSAO lags behind GRPO substantially in early training steps. To address this issue, we propose Li$^{2}$SAO, which Lifts Light Single-rollout Asynchronous Optimization with group-relative actor-critic bootstrapping: while the critic is cold, a group-relative advantage trains the actor and a group-centered return trains the critic, after which training switches to single-rollout GAE. Experiments show that Li$^{2}$SAO catches up with or surpasses GRPO in early training and further raises the later performance ceiling. Code is available at https://github.com/jd-cc-coder/Li2SAO.
Yihong Zhang, Bala Vinaithirthan, Karima Ma, Zachary Tatlock, Maaz Bin Safeer Ahmad, Andrew Adams
Recurrences are ubiquitous in signal and image processing, bioinformatics, numerical computing, combinatorial optimization, and many other domains. Because recurrences seem inherently sequential, they are often implemented serially and thus do not leverage vector instructions in modern hardware. This leaves much of the available, often highly parallel, hardware underutilized. In this paper, we present an algebra of recurrences over semirings and study algebraic identities that enable vectorization. Using our algebraic framework, we present a number of vectorizing transformations that yield efficient, vectorized implementations across various settings. These transformations naturally extend to 2D recurrences and mutual recurrences. We implement the recurrence algebra and the vectorizing transformations in a compiler called VecRec.VecRec compiles recurrence programs to efficient vectorized C++ implementations. The generated kernels can achieve up to an order-of-magnitude speedup over serial implementations across a wide variety of recurrences. A case study in bioinformatics shows that they are competitive with, and in many cases better than, existing libraries with manually-crafted vectorization.
Autoregressive (AR) models have recently emerged as a promising paradigm for image generation, as they can model visual tokens through the same next-token prediction principle that underlies large language models. However, most competitive AR image generators still rely on Transformer attention, whose quadratic token interaction cost and growing key-value cache become increasingly expensive for high-resolution visual sequences. Linear attention provides an attractive route to efficient AR generation, but our study shows that directly importing linear or decay-based attention from language modeling leads to clear quality degradation. We identify a key cause: after a 2D token map is flattened by raster scan, 1D sequence locality no longer faithfully reflects spatial locality, and conventional decay mechanisms may introduce a false-locality bias at row transitions. To address this problem, we propose Linear Attention with Spatial-Aware Decay (LASAD), a simple recurrent attention mechanism that modulates decay according to the original 2D token geometry while preserving linear complexity. Built upon this layer, LASADGen replaces standard attention in an AR image generator with spatial-aware linear attention. Experiments on ImageNet demonstrate that LASADGen achieves a favorable quality-efficiency tradeoff, improving generation quality over linear-attention baselines while reducing inference cost and memory usage compared with Transformer-based AR models.
Qingfu Zhu, Huanyang Zheng, Ting Liu, Wanxiang Che
LLM planning often relies on reactive executors (e.g., ReAct) that generate a single action at each step to remain grounded in the latest observations, incurring substantial inference cost. Batched executors reduce this cost by predicting multiple actions in a single model invocation, yet they are prone to compounding errors, as intermediate observations are ignored. We propose an expectation-observation consistency verification (EOCV) mechanism for batched executors, preserving grounding while improving efficiency. The mechanism generates expectations of action outcomes and compares them with the resulting observations. Consistency permits continued execution, whereas mismatches trigger early termination and replanning from the current observation. Experiments on text-based and multimodal benchmarks across multiple backbones show broadly comparable average task performance between EOCV and reactive executors, with a 29-35% reduction in average weighted token usage. Moreover, the mechanism is model-agnostic and remains effective when integrated into state-of-the-art planners.
Ahmet Bahaddin Ersoz, Justin McHenry, Yevgeniya Kovalchuk, Edward Barrett, Mandana Sarey Khanie
The rise of agentic artificial intelligence (AI) in the built environment is shifting attention from isolated AI tools toward autonomous systems that reason, plan, and act across project and organizational workflows. The effectiveness of such systems depends not only on large language model capabilities, but also on the readiness of heterogeneous data environments across the Architecture, Engineering, and Construction (AEC) sector. These environments combine structured sources, such as CAD and BIM models, schedules, cost databases, and asset registers, with unstructured ones, including technical reports, design narratives, planning and policy documents, contracts, meeting minutes, and risk registers. This paper reviews how built environment data can be organized to support agentic AI-ready workflows, focusing on knowledge structures, interoperability, and access and integration mechanisms such as retrieval-augmented generation (RAG) and the Model Context Protocol (MCP). Drawing on existing literature, it examines approaches proposed to organize structured and unstructured data and considers how such data can be contextualized and made accessible to AI agents in a reliable manner. The paper synthesizes current perspectives, highlights challenges around fragmentation and interoperability, and identifies open questions for future research on AI-compatible information management in the built environment.
Jianting Zhang, Sen Yang, Alberto Sonnino, Sebastián Loza, Aniket Kate
Directed Acyclic Graph (DAG)-based Byzantine Fault-Tolerant (BFT) protocols have emerged as promising solutions for high-throughput blockchains. By decoupling data dissemination from transaction ordering and constructing a well-connected DAG in the mempool, these protocols enable zero-message ordering and implicit view changes. However, we identify a fundamental liveness vulnerability: an adversary can trigger mempool explosions to prevent transaction commitment, ultimately compromising the protocol's liveness. In response, this work presents Lifefin, a generic and self-stabilizing protocol designed to integrate seamlessly with existing DAG-based BFT protocols and circumvent such vulnerabilities. Lifefin leverages the Agreement on Common Subset (ACS) mechanism, allowing nodes to escape mempool explosions by committing transactions with bounded resource usage even in adverse conditions. As a result, Lifefin imposes (almost) zero overhead in typical cases while effectively eliminating liveness vulnerabilities. To demonstrate the effectiveness of Lifefin, we integrate it into two state-of-the-art DAG-based BFT protocols, Sailfish and Mysticeti, resulting in two enhanced variants: Sailfish-Lifefin and Mysticeti-Lifefin. We implement these variants and compare them with the original Sailfish and Mysticeti systems. Our evaluation demonstrates that Lifefin achieves comparable transaction throughput while introducing only minimal additional latency to resist similar attacks.
Two-party privacy-preserving Transformer inference today mainly follows one of two paradigms: non-interactive computation over fully homomorphic encryption (FHE), or a hybrid of FHE and secure multi-party computation (MPC). Either way, linear layers account for a large share of the compute and communication budget. Most existing systems attack this cost by designing bespoke plaintext encodings and ciphertext matrix algorithms that minimize the expensive key-switching operations. The price is tight coupling: each scheme only works with its own packing/encoding strategy, and moving data between linear and nonlinear layers still triggers online ciphertext transmission and ring-field conversion. We take a different route. Instead of optimizing within a chosen encoding, we design a series of general algorithms for linear layers that can be readily integrated into existing inference systems, based on FHE and additive secret sharing. Our algorithms work with any compatible RLWE-based scheme and plug into both non-interactive FHE and hybrid FHE-MPC pipelines. Output interfaces in proposed algorithms allow them to be composed with different downstream nonlinear layers. Relative to existing linear layer schemes, our construction removes online key switching, ciphertext transmission, and online ring-field conversion. As a complement, we further propose a fused RNS-CKKS technique that reduces the computational cost of multiplication followed by rotation. We prove correctness and semi-honest security of the proposed algorithms and quantify the resulting savings analytically.
Conventional recommender systems rely on fixed cascaded pipelines, limiting their ability to adapt to evolving user needs and feedback. Existing agentic recommenders introduce reasoning and tool use but often lack end-to-end decision control and systematic failure reflection. We propose EvoRec, a unified agentic recommendation framework that combines autonomous decision-making with reflection-driven self-evolution. A Need Agent infers user needs from long-term, short-term, and working memory. A Planning Agent adaptively allocates retrieval budgets between Behavior Continuation and Need Satisfaction, selects retrieval tools, and sets ranking-fusion weights. An Acting Executor executes the plan and records decision traces. Following user feedback, a Dynamic Reflection Tree identifies failures in need inference, planning, or previous repairs, proposes personalized corrections, and validates them through replay. Verified repairs update working memory and are distilled into reusable cross-user strategies, enabling continual improvement without parameter updates. Experiments on a Kuaishou local-services advertising dataset show a 15.7% Hit@50 improvement over the strongest baseline. Hierarchical reflection further improves Hit@50 by 13.1% among users with prior repairs. In a seven-day online A/B test, nearline EvoRec increases advertising revenue by 4.6% and CTCVR by 3.5%, with a 14.5% revenue gain for high-intent users. These results demonstrate the effectiveness of reflection-driven self-evolution in industrial-scale recommendation.
Jiaheng Xiao, Jiangtao Han, Jiachen Wang, Honghai Li, Lijun Sun, Kay Axhausen, Chang Liu, Zhengbing He
Understanding mobility dynamics and the effects of urban transportation management policies requires examining how individual travel decisions, traffic conditions, and policy interventions influence one another over time. We present AgenticMobility, an open-source experimental platform for studying how mobility AI agents and other AI agents interact, adapt through repeated experience, and collectively shape mobility outcomes. Persistent agents retain identities and relevant states across rounds, with explicit interfaces defining information access, admissible actions, and decision schedules; linked records trace decisions, execution, and feedback. In the current implementation, large language model (LLM) agents act as travelers choosing routes and departure times and as a manager periodically adjusting link charges within MATSim. A preliminary demonstration spans 100 simulated days in each of five configurations, with one run per configuration and a shared simulation seed. In the joint traveler--manager run, all 1,179,300 finalized target decisions satisfied action constraints; execution checks verified implementation of accepted choices and preservation of personal memories across days. Trajectories show stable route choices alongside departure-time adjustments and differences between controlled-trip and population-wide outcomes. The platform supports experiments on individual adaptation, collective outcomes, and management interventions by varying information access, retained experience, and management feedback. Source code is available at https://github.com/Agentic-City-Research/Agentic-Mobility
Hybrid language models interleave linear-attention layers with a small number of softmax-attention layers. Prior work largely attributes in-context retrieval to softmax attention, treating linear attention primarily as a mechanism for compressing past context. We revisit this division of labor and show that linear attention plays a direct role in retrieval by constructing the query used by softmax attention. Studying Qwen3.5 (Gated DeltaNet) and Granite4.0 (Mamba-2), we identify an Encode--Address circuit. An early Encode block preserves token identity, while an Address block constructs the final-position representation from which a softmax \emph{reader} forms its attention query. Transplanting this representation between prompts with different queried keys redirects retrieval in 0.97--0.99 of cases. The Address block's recurrent state carries the retrieval target, and its computation transfers across architectures: replacing Granite's Address block with Qwen's restores retrieval accuracy to 0.92--0.94 without updating either model's weights. Across six Qwen3.5 models, Address computation becomes distributed at larger scales over a chain of blocks, each guiding a successive reader, as the query no longer passes from one reader to the next through attention. These findings reveal a division of labor in hybrid retrieval: linear attention constructs the query, while softmax attention performs the lookup. Code is available at https://github.com/yuang-chen/LinearQuery
Mengting Li, Xilong Cheng, Zhihao Xiao, Zhenhua Xu, Jingyuan Zhou, Linfeng Li, Long Zhang, Borui Cai 等 9 位作者
LLM-based role-playing agents are fluent at imitating a character's style, yet struggle to make role-consistent decisions over long narrative horizons. Such decisions are shaped by experiences spanning many prior scenes, which are often partial and may point in different directions. Existing methods inject cross-scene memories as context, but do not reason about how past events shape a character's current motivations and behavior. We propose MemRole, a framework that makes this memory-to-decision process explicit. It introduces Long-Horizon Memory Thinking (LHMT), a reasoning schema that decomposes hidden reasoning into context understanding, memory activation, and response strategy planning, trained on a novel-derived dataset whose character-grounded, timeline-constrained memory pools limit each character to what it could plausibly know at the current narrative point. Beyond supervised fine-tuning, we propose Self-Refining On-Policy Self-Distillation (SR-OPSD): the model critiques its own rollouts against the reference under a data-driven rubric, and a critique-conditioned teacher view of the same model distills token-level guidance back into the policy. MemRole-32B improves over its backbone by 15.2 points on memory-grounded role-playing, performs on par with frontier LLMs such as GPT-5.4, and achieves the best character-motivation recognition accuracy on CroSS-MR.