Papers

Independently authored skills can impose incompatible requirements, competing preferences, and redundant instructions when jointly loaded by an LLM agent. We propose SkillFusion, an offline compiler that reconciles these interactions into a reusable merged skill. Its central idea is to make composition decisions explicit through typed, scoped constraints linked to their source directives. A type-scope gate selects candidate interactions, while selective fallback revisits pairs potentially missed by structural pruning. A classifier identifies interaction types, and an adversarial verifier re-examines uncertain judgments. The resolver applies conditional routing or explicit priorities to hard conflicts, verified abstraction to soft conflicts, and deduplication to redundant instructions. Source-linked checks guide synthesis and compression, and metadata synthesis supports discovery of the merged skill. The resulting artifact retains associated scripts and resources and can be reused across tasks and executor models. SkillFusion achieves the highest mean Success among evaluated non-oracle methods on all three agent benchmarks and on both transfer benchmarks across three executor models. At the largest tested instruction configurations, it achieves over 2.5 times the Success of unresolved multi-skill loading, highlighting the growing value of reconciliation as composition becomes more demanding. The code will be open-sourced after the review process concludes.

We study games on finite graphs with labelled or weighted edges in which plays end as soon as the first loop is formed. The resulting play has a lasso shape: a path (head) followed by a cycle (loop). We consider two semantics for determining the winner: the loop semantics, where only the loop matters, and the lasso semantics, where the entire play is taken into account. We show that adopting the lasso semantics may have a dramatic impact on both the complexity of the game and the memory required to play optimally. Mean-payoff games with lasso semantics are no longer positionally determined, and the threshold problem – deciding whether the value of the game is at least 0 – is PSPACE-complete. In contrast, lasso parity games are equivalent to weak parity games, remain positionally determined and are solvable in polynomial time. Furthermore, we show that if a positionally determined winning objective is closed under cyclic permutation and both the objective and its complement are closed under concatenation, then it is equivalent to the parity objective. Finally, we consider mod-k games, where the winner depends on the length of the path modulo k >= 2. We show that these games, in both semantics, are PSPACE-complete. Alongside computational complexity, we analyze the memory required to play optimally. We establish that for any game positionally determined in loop semantics, memory of size 2^n is sufficient in lasso semantics. We complement this by showing exponential memory lower bounds for lasso mean-payoff and mod-k games.

We present asymptotically optimal translations from linear temporal logic with past to limit-deterministic Buchi automata and onwards to deterministic parity automata. In contrast to previously known translations involving past, the ones presented here are incremental: states and transitions can be constructed as needed on-the-fly, and they do not involve backtracking in order to correct for temporal inconsistencies. The past is naturally encoded in the formula by alternating between weak and strong versions of past operators. To handle the difficulties that arise from the alternation of least and greatest fix-point operators (such as between the "until" operator and its weak counterpart), we rewrite the given formula based on the infinitary behavior of a given word with respect to subformulae rooted with such operators.

Timing information leakage occurs whenever an attacker successfully deduces confidential internal information by observing some timed information such as the total duration of a run. Timed automata (TAs) are an extension of finite-state automata with a set of clocks evolving at the same rate and that can be tested or reset. Hence, this formalism is able to represent systems involving timing constraints reacting to the passage of time. Some of the transitions in a timed automaton may be controlled, i.e., enabled or disabled, to limit the runs that are allowed. Execution-time opacity (ET-opacity) aims at studying timing information leakage through the analysis of timed automata. More precisely, the ET-opacity problem consists in deciding whether an attacker can deduce whether some secret locations were visited by a run, solely from the run's duration. When control is allowed, the goal becomes to find a strategy that blocks the runs leaking information. This problem has been shown decidable for TAs, with and without control. However, these existing results only provide upper bounds on the complexity of the ET-opacity problem, sometimes largely above the tight bound. Our main contribution is to provide tight lower bounds for those two results. Moreover, for controllable TAs, two variants of ET-opacity (depending on whether detecting if a run did not visit a secret location represents an information leakage or not, and named full and weak ET-opacity respectively) had been separately studied; we prove here that these two notions are inter-reducible.

We derive polynomial bubble duality in barycentric coordinates and construct explicit nodal bases for the first family of finite element differential forms. Logarithmic coordinates give an elementary proof of the Whitney–bubble decomposition. The Hessian of negative entropy defines a metric whose normalized Hodge star maps bubble generators to complementary-degree polynomial forms. This gives a direct geometric description of the known dualities and proves nondegeneracy of their integral pairings. Combining Whitney forms with shifted Lagrange polynomials then gives bases dual to tangential point evaluations in every dimension and order. The construction extends to scalar nodes that are unisolvent on every face. The interpolant is independent of the roots and commutes with face restriction.

One of the most well-known connections between logic and games is Pauly's representation theorem: the induced powers of individuals and coalitions in concurrent game frames correspond, in a precise sense, to a certain class of neighborhood frames. The precise sense here is what is called alpha effectivity (or alpha power): the power of a coalition is characterized by the sets of states in which it can ensure that the outcome lies by taking some joint action. This definition is inherently monotonic, and, as pointed out by van Benthem, Bezhanishvili, and Enqvist (2019), that fact can obscure relevant information about the power structure in the game: we do not know whether two sets that a coalition has the power to enforce correspond to the same joint action or to different joint actions. An alternative is to characterize the power of a coalition by its actual power (called basic power by van Benthem, Bezhanishvili, and Enqvist (2019)): the collection of sets of states, each of which corresponds to one joint action by the coalition and all possible joint actions by the other agents. It has recently been argued by Li and Ju (2025, 2026) that standard concurrent game frames rely on three assumptions that may, in some cases, be too strong: seriality, independence of agents, and determinism. This yields a total of eight different classes of general concurrent game frames. In this paper, assuming two agents, we prove that, in terms of actual powers, the eight classes of general concurrent game frames are represented by eight corresponding classes of neighborhood frames. This generalizes a result by van Benthem, Bezhanishvili, and Enqvist (2019).

Otto's Theorem characterises the bisimulation-invariant PTIME queries over graphs as exactly those that can be formulated in the polyadic mu-calculus. This extends to a characterisation of the full bisimulation-invariant exponential-time hierarchy, using a higher-order extension of the polyadic mu-calculus, called PHFL, which is naturally stratified by type order. The bisimulation-invariant fragment of k-EXPTIME is captured by the fragment of PHFL whose formulas have type order at most k. This is obtained using a generalisation of the Immerman-Vardi Theorem by Freire and Martins. Here we provide such a characterisation of the exponential-space hierarchy. We show that the bisimulation-invariant fragment of k-EXPSPACE is captured by the fragment of PHFL of type order k+1 whose formulas are tail-recursive. Tail recursion limits the interplay between fixpoints and higher-order functions so that model checking based on fixpoint iteration can be made more space efficient in a way comparable to tail recursion in programming languages. The capturing result makes use of a generalisation of Vardi's characterisation of PSPACE as first-order logic with partial fixpoints, namely that k-EXPSPACE is captured by higher-order logic of order k+1 with partial fixpoints.

We introduce Non-musical Audio to Symbolic Music Transformation (NASMT), a novel task that converts non-musical audio into symbolic music representations. Unlike automatic music transcription, which assumes musical input and a unique correct score, NASMT is inherently one-to-many and requires evaluation along two axes: input correspondence and musicality. We present Sori, an encoder–decoder Transformer that addresses this task through domain adversarial training (DAT), which bridges the gap between musical and non-musical audio in the encoder's feature space, and classifier-free guidance (CFG) with a continuous parameter~$\gamma$ that controls the trade-off between correspondence and musicality at inference time. Across objective metrics and a listening study, Sori provides effective continuous control via $\gamma$ and compares favorably with instrument-agnostic transcription models. Sori supports real-time streaming on a consumer CPU. Audio examples are available at https://soridemo0320.github.io/sori-demo/.

FirstFit colors each arriving vertex with the smallest positive integer absent from its previously colored neighborhood. We prove that this rule can require $n^{\Omega(1)}$ many colors on certain bipartite graph of $n$ vertices even when the vertices arrive in a uniformly random order. This refutes the conjecture of Bosek, Gutowski, Lasoń, and Przybyło [BGLP24] that FirstFit uses a polylogarithmic expected number of colors on every bipartite graph in the random order model. We obtain the lower bound by analyzing the FirstFit coloring process on random bipartite graphs, where vertices arrive to either side with equal probability, and with an independent edge density $n^{-x}$ for some $0 < x < 1$. Our result can also be viewed as a qualitative strengthening of Kučera [Kuč91], who showed that, for every $\epsilon > 0$, there are graphs with chromatic number at most $n^{\epsilon}$ on which FirstFit uses $\Omega(n/\log n)$ colors in expectation under a uniformly random order. Our result shows that such poor behavior of FirstFit already occurs for $\chi(G) = 2$.

Image-computable low-level image saliency has shaped perceptual psychology and computer science, but is limited by its inability to capture human high-level cognitive factors that influence attention and eye movements. Here, we propose a new fully automated method to compute semantic saliency by quantifying each object's contribution to scene comprehension without fitting any parameters to human data: the Automated Scene Understanding Map (AUTO-SUM). AUTO-SUM automatically segments and removes individual objects from a scene, uses multimodal large language models (MLLMs) to describe the original and modified scenes, and measures the semantic similarity between these descriptions using text embeddings. We show that AUTO-SUM can predict which object is most important in a human-measured scene understanding map (H-SUM) estimated using human scene descriptions. We also show that AUTO-SUM can predict the object most fixated by human observers during free viewing and scene description tasks better than a low-level saliency model (GBVS, Itti-Koch), a saliency model trained based on human meaning ratings (Meaning Map), and comparable to DeepGaze, which is trained on human fixation data. We contend that AUTO-SUM can be used as a semantic saliency model that complements lower-level saliency models. Code are available at https://github.com/starsky77/AUTO-SUM-Source-Code .

With the rapid proliferation of social media, harmful memes have become a growing threat to online ecosystems. Their harmfulness is often implicitly conveyed through complex interactions among visual, textual, and contextual cues, making accurate detection challenging. Recent studies have introduced Retrieval-Augmented Generation (RAG) and external knowledge into harmful meme detection. However, existing methods mainly retrieve similar instances or auxiliary information, limiting their ability to capture reusable harmfulness knowledge and underlying reasoning mechanisms, and thus constraining both detection performance and interpretability. To address these challenges, we propose MemeLogos, a knowledge-driven retrieval-augmented reasoning framework for harmful meme detection. MemeLogos abstracts recurring harmfulness patterns and reasoning structures from diverse harmful cases into reusable knowledge units and organizes them into a dedicated star-shaped knowledge graph. By combining structured knowledge retrieval with an explicit multi-stage reasoning process inspired by cognitive mechanisms, MemeLogos leverages retrieved knowledge to guide harmfulness reasoning, improving both detection reliability and interpretability. Extensive experiments show that MemeLogos consistently outperforms existing harmful meme detection methods while generating more coherent and interpretable reasoning, demonstrating the effectiveness of structured harmfulness knowledge for multimodal content understanding.

MDP planners often rely on nominal transition models that may differ from the true dynamics. Robust MDP planning accounts for this uncertainty through a set of admissible models, but doing so with limited online computation is challenging: the search tree grows exponentially with the horizon and each robust backup requires an additional optimization. Existing online robust methods remain limited in scale and offer at most probabilistic guarantees. We introduce, to the best of our knowledge, the first deterministic anytime guarantees for robust online MDP planning. We restrict computation to the sampled search tree while deterministically bounding the contribution of unsampled trajectories. For any fixed policy, we derive lower and upper bounds on the gap between its projected and true robust values under rectangular and non-rectangular uncertainty sets. Under rectangular uncertainty, we propagate these bounds through the robust Bellman operator to bound the optimal robust value. These bounds are computable from the current sampled tree, hold at every node, tighten as the sampled support expands, and converge to the robust values as full support is recovered. We develop CAR-MCTS, a bound-guided MCTS planner that uses these deterministic bounds to guide exploration, prune provably suboptimal branches, and terminate once the optimal root action is certified. The fixed-policy bounds also yield an anytime policy-evaluation mechanism that certifies the robust value of any policy, independent of how it was obtained. Experiments verify the deterministic bounds, their tightening under support expansion, substantial branch pruning, root-action certification, and convergence to the optimal robust policy. To our knowledge, this is the first scalable robust MCTS framework with anytime deterministic guarantees for both online planning and policy evaluation, without enumerating the full state space.

LLM-based multi-agent systems (LLM-MAS) use specialized agents that exchange messages to accomplish complex tasks. Their reliance on networked protocols, remote tools, and model endpoints exposes communication to message loss, delay, and context expiration. Because agents often exchange open-ended natural language, anomalies can alter task-relevant information while leaving messages processable, allowing semantic errors to propagate through subsequent interactions. Systematic studies of faults in inter-agent communication remain limited. This paper presents a large-scale empirical study of how communication faults manifest, propagate, and affect task outcomes in LLM-MAS. We construct a cross-layer taxonomy linking lower-stack disturbances to application-visible faults and develop a fault-injection and tracing pipeline. Our evaluation covers more than 29,000 executions across 100 tasks, five domains, three workflow topologies, and three model configurations. We find that 20.7% of failures with complete detection records occur without an immediate failure signal, reaching 76.2% for partial-content faults. Flat maintains 53.0% task success under communication faults, compared with 3.3% and 3.2% for Sequential and Hierarchical, respectively. This advantage primarily arises when an alternative information path preserves the evidence required by downstream agents. We also evaluate execution-side and evidence protection mechanisms and find that they recover different failure cases. Evidence recovery depends on whether trustworthy information remains accessible through an unaffected path. These observations provide empirical insights into communication-fault propagation, workflow resilience, and protection design for LLM-MAS.

Existing analyses of interval length in split conformal prediction largely focus on clean data. However, how contamination at the training and calibration stages alters interval length relative to the corresponding clean population oracle remains understudied. In this paper, we consider Huber contamination and derive a finite-sample upper bound that holds uniformly over contaminating distributions, with leading terms scaling as $L(\delta_1+n_1^{-1/2}) +(n_2^{-1/2}+\delta_2)/((1-\delta_2)r_0)$, in addition to a clean-sample estimation term. We further establish a minimax lower bound matching the upper-bound rate up to constant factors on a regular asymmetric location submodel. For calibration contamination, we obtain an exact worst-case characterization of the population interval-length deviation. We also extend the upper-bound results to conformalized quantile regression and adaptive residual scores. Experiments on synthetic and real-world datasets provide empirical support for our theoretical findings on training and calibration contamination.

Accurate, physiologically consistent glucose forecasts could help people with type 1 diabetes respond to impending excursions. We applied our physiological-model-based neural network (PMB–NN) framework to glucose forecasting. A temporal convolutional network (TCN) used 180 min of history, constrained during training by a personalized four-parameter physiological model. The main PMB–NN combined forecast and neural–physiological agreement losses; a three-term variant additionally fitted physiological predictions to measured glucose. Data comprised 6–8 weeks of continuous glucose monitoring, pump, and meal records from 25 AZT1D participants. Person-specific models used chronological 70/10/20 train/validation/test splits and 30-, 60-, and 120-min horizons. Median mean absolute errors were 16.24, 25.00, and 30.20 mg/dL with basal insulin records and 15.38, 24.21, and 31.79 mg/dL before these records became available. In the latter setting, PMB–NN had the lowest median error at 30 and 60 min; it outperformed the physiological model alone in all six settings. In input-increase tests, glucose predictions changed in the expected direction for 85% of correction boluses and 100% of carbohydrate rescues, versus 57% for active insulin and 56% for active carbohydrates. Most standalone physiological fits showed locally distinguishable parameter effects, with glucose-related coefficients more stable under resampling than insulin- or carbohydrate-related coefficients. The three-term variant improved hyperglycaemia accuracy with basal records, but did not significantly change overall MAE and reduced directional plausibility in three tests. PMB–NN combines personalized forecasting with an explicit physiological model, allowing assessment of predictive accuracy, physiological response behavior, and participant-specific coefficients.

Neural audio codecs achieve remarkable performance but operate as closed ecosystems with rigidly co-trained encoderdecoder pairs, severely hindering interoperability. To resolve this, we propose BridgeCodec, a versatile framework that decouples these pairs by translating latent representations between mismatched, frozen endpoints. We formulate this cross-codec translation as a Schrödinger Bridge optimal transport problem, enabling robust mapping between disparate distributions without predefined noise priors. To efficiently capture longrange speech temporal dependencies, we integrate a Mambaenhanced U-Net architecture. We validate BridgeCodec on an extreme deployment scenario: mapping a lightweight 8 kHz source encoder directly to a 48 kHz target decoder at an ultralow bitrate of 1 kbps. Experimental results demonstrate that BridgeCodec achieves superior wideband reconstruction and high perceptual quality, successfully bridging heavily bottlenecked, heterogeneous codecs.

Text-to-video (T2V) models are increasingly used to generate videos with targeted emotional expressions, yet existing evaluation methods mainly rely on holistic video-text alignment and provide limited insight into whether failures arise from target-emotion expression, intensity control, or specific affective cues. We introduce EmoTrace-Bench, a fine-grained diagnostic benchmark that controls emotion intensity and selected affective cues in prompts and evaluates generated videos at multiple levels. EmoTrace-Bench contains 448 controlled prompts covering eight emotions, two intensity levels, and diverse cue conditions. Using 12 T2V models, we generate 5,376 videos and evaluate target-emotion presence, perceived intensity, and ten audiovisual dimensions of emotional expression with an automated evaluator calibrated and validated against human annotations on a subset of the data. Results reveal substantial differences across models and prompt designs. Prompts that explicitly describe a character's emotional reaction are followed more reliably than prompts that describe only events or scenes, whereas adding more affective cues or using more explicit cinematic audiovisual language does not consistently improve emotional generation. These results illustrate how aggregate alignment scores may overlook localized differences in target-emotion expression, intensity control, and cue realization. EmoTrace-Bench provides a traceable and interpretable framework for diagnosing emotional video generation without modifying existing generation pipelines, and we release the prompts and the automated evaluation rules.

Functional magnetic resonance imaging (fMRI) commonly characterizes large-scale brain organization through functional connectivity (FC). However, an observed FC matrix is not a fixed brain graph but a statistical estimate determined by the finite BOLD frames used to compute it. Conventional FC-based approaches typically represent each scan with a single Pearson-correlation matrix, leaving frame-resolved variations in regional interactions unexploited. To address this limitation, we introduce CoFlu-Brain, which organizes framewise cofluctuation observations into multiple retained and dropped views, each summarized as an FC matrix. The model learns connectivity structure reproducible across retained views and predicts the representations of the corresponding dropped views, while adopting SIGReg from LeJEPA to prevent representation collapse. We pretrained CoFlu-Brain on 13,444 subjects from eight dataset groups and evaluated its representations via frozen-encoder linear probing on seven classification and two age-prediction tasks across seven datasets. CoFlu-Brain showed strong transfer across demographic, developmental, and clinical prediction tasks, outperforming the evaluated released models on most tasks. Random frame partitioning improved aggregate transfer, while the complete objective achieved the strongest overall performance. Code is available.

Despite significant advances in language understanding, Large Language Models (LLMs) can still miss meaning hidden in plain sight, failing to identify harmful intent in expressions readily understood by humans. Malicious users exploit this gap by strategically disguising harmful content to evade automated moderation, posing a serious threat to online platform safety. The vulnerability reflects a fundamental cognitive asymmetry between human readers, who integrate contextual, phonetic, and visual cues to decipher the intent behind deliberate obfuscation, and text-based LLMs, which rely primarily on token sequences and have limited exposure to evolving evasions. To bridge this asymmetry, we propose PASP (Perception-Aware Adversarial Self-Play), which combines multi-perceptual views with adversarial self-play to improve understanding of harmful intent as evasions evolve. Specifically, PASP constructs textual, phonetic, and visual views of each input, preserving its original context while exposing pronunciation and glyph cues obscured in token space. During adversarial self-play, an attacker uses defender feedback to generate intent-preserving evasions, while the defender is trained using an intent-invariance reward to understand harmful intent across changing surface forms. Extensive experiments show that PASP reduces adaptive attack success rates by up to 73.71% and 74.49% on ChineseHarm-Bench and EvoHarmBench, respectively, preserves model capabilities with minimal degradation, and effectively interprets real-world evasive expressions in e-commerce.

In recent years, the proliferation of smartphones has led to an upsurge in the digitization of document files via these portable devices. However, images captured by smartphones often suffer from distortions, thereby negatively affecting digital preservation and downstream applications. To address this issue, we introduce DRNet, a novel deep network for document image rectification. Our approach is based on three key designs. Firstly, we exploit the intrinsic geometric consistency inherent in document images to guide the learning process of distortion rectification. Secondly, we design a coarse-to-fine rectification network to leverage the representations derived from the distorted document image, thereby enhancing the rectification result. Thirdly, we propose a unique perspective for supervising the learning of rectification networks, where undistorted document images are employed for supervision, which is free of warping mesh as ground truth in existing methods. Technically, both low-level pixel alignment and high-level semantic alignment jointly contribute to the learning of the mapping relationship between deformed document images and distortion-free ones. We evaluate our method on the challenging DocUNet Benchmark dataset, where it sets a series of state-of-the-art records, demonstrating the superiority of our approach compared to existing learning-based solutions. Additionally, we conduct a comprehensive series of ablation experiments to further validate the effectiveness and merits of our method.

We study the fair allocation of $m$ indivisible chores among $n$ agents in the agent-arrival model against an oblivious adversary. The chore set and the number of agents are known in advance. When agent $i$ arrives, her nonnegative additive cost function $c_i$ is revealed, and the algorithm must immediately and irrevocably assign her a subset of the unallocated chores. We focus on the notion of maximin share (MMS) and measure the fairness of the realized allocation $X$ by the ex-post MMS approximation ratio $\rho(X)$. We measure an algorithm's performance by its expected ratio, and also the guarantees that hold with high probability. For binary additive costs, we achieve an expected ex-post MMS ratio of $3/2+o(1)$, and show that every randomized online algorithm has an expected ratio of at least $3/2-o(1)$. For every $n$, the expected ratio is at most $1.755$. A variant of our algorithm guarantees an approximation ratio of $2$ with high probability, which is optimal. % For general additive costs, we present a weighted-rounding algorithm that achieves an expected ratio of $2+o(1)$, which also holds with high probability. The expected ratio is at most $2.594$ for every $n$. We also show that similar algorithms extend to additive goods, achieving a constant expected ex-post MMS ratio and guaranteeing every agent an $x$-fraction of her MMS with probability at least $1-85x^2$ for every $x\le1/15$.

Recent years have seen the successful application of large pre-trained models of source code (CodePTMs) to code representation learning, which have taken the field of software engineering (SE) from task-specific solutions to task-agnostic generic models. By the remarkable results, CodePTMs are seen as a promising direction in both academia and industry. While a number of CodePTMs have been proposed, they are often not directly comparable because they differ in experimental setups such as pre-training dataset, model size, evaluation tasks and datasets, etc. In this paper, we first review the experimental setup used in previous work and propose a standardized setup to facilitate fair comparisons among CodePTMs to explore the impacts of their pre-training tasks. Then, under the standardized setup, we re-pre-train CodePTMs using the same model architecture, input modalities, and pretraining tasks, etc., as they declared and fine-tune each model on each evaluation SE task for evaluating. Finally, we present the experimental results and make a comprehensive discussion on the relative strength and weakness of different pre-training tasks w.r.t. each SE task. We hope our view can inspire and advance the future study of more powerful CodePTMs.

Large language models are increasingly used in reflective journaling, where articulating an experience is part of interpreting it. This raises questions about how writers retain authorship, exercise agency, and assess personalized assistance. We present AuthScribe, an LLM-assisted reflective journaling system that combines contextual anchors, writer-steered AI support, Autobiographical Citations, and read-only Provisional Drafts that require re-expression before AI-generated suggestions enter the journal. Retrieval and LLM inference run on-device. In a 14-day field deployment with 14 participants, grounding shifted from situating current experiences to reconnecting them with prior self-authored interpretations. Perceived agency remained stable through Week 1 and shifted during Week 2. Participants described authorship through transforming AI-generated suggestions into personally meaningful expression, and trusted personalized prompts when they could trace them to prior writing. We discuss design implications for adoption friction, longitudinal agency, and traceable personalization in AI systems for personal reflection.

In random order online sorting, a fixed multiset of $n$ real numbers arrives in a uniformly random order. Each value must be placed immediately and irrevocably into an empty position of an array with exactly $n$ positions. The objective is to minimize the sum of the absolute differences between consecutive entries. If the entire input were known in advance, sorting the values would be optimal and would have cost equal to the range of the input. We prove that the optimal worst case competitive ratio in this model is $\Theta(\log n)$ with high probability. In particular, we give a single online algorithm that achieves an $O(\log n)$ competitive ratio with high probability for every fixed input, and we show that every randomized online algorithm has some fixed input on which an $\Omega(\log n)$ ratio is unavoidable with high probability. The same upper bound also holds for independent samples from an arbitrary unknown distribution on the real line. The algorithm uses the random arrival order to learn the relative positions of future values from the values seen so far. It maintains a hierarchy of small regions of the input order and allows an arriving value to use nearby space when its preferred region is full. This flexibility avoids the need to reserve large amounts of space for unlikely local fluctuations. The analysis shows that large displacements become rapidly less likely as their scale grows, leading to the $O(\log n)$ high probability bound. A matching lower bound shows that no randomized online algorithm can improve the logarithmic dependence in the worst case.

We study the simultaneous achievement of share-based and envy-based fairness in the allocation of indivisible goods with nonnegative additive valuations. The AnyPrice share (APS) is a strengthening of the maximin share (MMS). A polynomial-time algorithm is known to guarantee a $2n/(3n-1)$ approximation of APS, but without an accompanying envy-based guarantee. Separately, allocations simultaneously satisfying minimum EFX share (MXS) and envy-freeness up to one less-preferred good (EFL), and subsequently the stronger requirement of residual maximin share (RMMS) together with EFL, have been shown to exist. However, the known constructions do not provide pseudopolynomial-time guarantees. We develop algorithms that combine these share-based and envy-based fairness requirements. First, for every $\varepsilon \in (0,1)$, we give an algorithm that computes an allocation satisfying exact EFL, $(1-\varepsilon)$-MXS, and $2n/(3n-1)$-APS. Its running time is polynomial in the binary input length and $1/\varepsilon$. Thus, we match the previously established polynomial-time APS approximation while simultaneously guaranteeing exact EFL and an arbitrarily close approximation to MXS. Second, we provide a pseudopolynomial-time algorithm that simultaneously guarantees exact MXS, exact EFL, and $2n/(3n-1)$-APS. Third, for every fixed number of agents, we obtain a pseudopolynomial-time algorithm that simultaneously achieves exact RMMS and exact EFL. Finally, we establish that computing a numerical threshold between MXS and RMMS is weakly NP-hard, even for additive valuations. This identifies a computational barrier to extending our polynomial-time approach to exact MXS through independently computed residual-valid share thresholds.

Code summarization is to provide a high-level comment for a code snippet that typically describes the function and intent of the given code. Recent years have seen the successful application of data-driven code summarization. To improve the performance of the model, numerous approaches use Abstract Syntax Trees (ASTs) to represent the structural information of the code, which is considered by most researchers to be the main factor that distinguishes code from natural language. Then, such data-driven methods are trained on large-scale labeled datasets to obtain a model with strong generalization capabilities that can be applied to new examples. Nevertheless, we argue that state-of-the-art approaches suffer from two key weaknesses: (1) inefficient encoding of ASTs; (2) reliance on a large labeled corpus for model training. As a result, such drawbacks lead to (1) oversized model, slow training, information loss and instability; (2) inability to be applied to programming languages with only a small amount of labeled data. In light of these weaknesses, we propose PassSum, a code summarization approach that addresses the aforementioned weaknesses via (1) a novel input representation which contains an efficient AST encoding method; (2) introducing three pre-training objectives and pre-training our model with a large amount of (easy-to-obtain) unlabeled data under the guidance of self-supervised learning. Experimental results on code summarization for Java, Python and Ruby methods demonstrate the superiority of PassSum to state-of-the-art methods. Further experiments demonstrate that the input representation we use has both temporal and spatial advantages in addition to performance leadership. In addition, pre-training is also shown to make the model more generalizable with less labeled data, and also to speed up the convergence of the model during training.

Monocular depth estimation (MDE) has emerged as a cost-effective alternative to hardware-dependent 3D sensing modalities, yet predicting precise metric depth remains a persistent challenge due to intrinsic scale ambiguity, edge bleeding, and limited zero-shot generalization in unseen environments. Recent multi-modal approaches incorporate 1D/3D Single-Photon Avalanche Diode (SPAD) data to resolve these ambiguities, but they mainly treat SPAD noise as a harmful artifact required for denoising or leave the noise ignored. In this paper, we present an essentially different insight: native SPAD noise is an informative prior that implicitly encodes deterministic environmental characteristics. Driven by this paradigm shift, we introduce a novel, lightweight Test-Time Gated Attention framework by Harnessing SPAD Noise, therefore dubbed HSN. Tailored for indoor scenarios, HSN leverages the synergistic combination of 1D SPAD histograms and Gate Adapters (GAs). Through three complementary optimization phases, it generates channel-wise gated attention vectors to dynamically adjust encoder feature maps at inference time, effectively resolving ambiguous scale and boundary challenges without the heavy computational overhead or dense 3D modalities that other TTA methods suffer from. Extensive experiments on challenging real-world indoor benchmarks show that HSN achieves state-of-the-art metric depth accuracy in in-domain settings, while exhibiting even greater potential under zero-shot generalization to unfamiliar environments. Furthermore, interpretability analysis reveals that the proposed gated attention mechanism adaptively shifts attention toward deeper semantic layers under intensifying SPAD noise. Code will be made publicly available.

How do we tell a world model what information to preserve? We study this question through the lens of spectral representation learning. We introduce SpecWM, a JEPA framework that explicitly specifies desired relationships between observations through a target similarity kernel and trains the encoder to reproduce those relationships in its embedding geometry. Different kernels provide different supervision, ranging from physical state information to a fully self-supervised temporal kernel requiring only the ordering of observations within trajectories. We characterize the global optima of the objective, establish conditions for linear recoverability and invariance to nuisance information, and connect temporal-kernel similarity to the behavioral successor measure under an idealized setting. Empirically, the choice of kernel strongly controls which physical quantities are recoverable from the representation. More importantly, temporal spectral alignment improves CEM planning success over LeWorldModel from 52% to 68% on OGBench Cube, 49% to 77% on OGBench Scene, and 29% to 51% on CALVIN. These results suggest that explicitly specifying representation geometry provides a simple way to steer what latent world models preserve for control.

Context-based offline meta-reinforcement learning (COMRL) has advanced almost entirely through better task representations, which separate task identity from artifacts of the behavior policy so that the latent reflects the task alone. The implicit expectation has been that a clean representation will transfer to out-of-support (parameter-extrapolation) tasks. On such a task, however, the encoder produces a latent outside the training support, where the policy has never been trained. We address this gap with Pessimistic Latent Task-aware Optimization (PLATO), which exposes the policy to off-support latents during training. PLATO assumes a mild manifold hypothesis: task latents lie on a low-dimensional manifold, and out-of-support tasks lie farther from the training centroid. It exploits this geometry by perturbing inferred latents outward from the centroid to synthesize counterfactual tasks. A learned decoder ensemble then rolls out short trajectories at each perturbed latent, and the policy is updated on the imagined transitions under a pessimism weight that down-weights steps on which the ensemble disagrees. We prove that the perturbation leaves the training support by a controllable margin and that the out-of-support generalization gap is bounded by the same perturbation reach, and we give explicit conditions, verified empirically, under which the epistemic disagreement at the perturbed latent stays bounded away from zero. On eight MuJoCo continuous-control benchmarks, PLATO consistently improves out-of-support returns over strong COMRL baselines while remaining competitive on in-distribution tasks. Our code is available at https://github.com/deephoony/plato.

Foundation models are at the forefront of artificial intelligence. A tokenizer, converting the raw input into discrete representations that the model can understand, plays an important role to the success of foundation models. Unlike the text tokenizer that is well studied in large language models, graph tokenizer is still at its early stage, facing the challenges of tackling the non-Euclidean structures and capturing the structural semantics. How to design a graph tokenizer for structural knowledge transfer? To this end, we propose a Riemannian Graph Tokenizer (RGT) that bridges the structural knowledge and quantized representations to support cross-domain structural knowledge transfer. The connection is established by Riemannian geometry. Specifically, we first define the geometric vocabulary (trees, cycles and sequences), which captures fundamental structural patterns and reflects the intrinsic geometry of graph. Second, we construct a Riemannian quantizer with Riemannian Straight-Through Estimator to tokenise graph structures across multiple domains into discrete tokens. To ensure consistency and transferability across diverse geometric spaces, RGT further incorporates a geometry-aligned decoder that projects manifold-specific tokens into a unified tangent space. The theoretical analysis and geometric interpretations are provided to support the effectiveness of our proposed method. Extensive experiments across diverse datasets demonstrate that RGT significantly enhances structural knowledge transferability across graph domains.