Creative story generation has achieved notable progress with large language models. Current methods construct narratives through hierarchical planning or incremental expansion. These approaches produce structurally complete stories but offer limited support for organic narrative development. Many fiction writers offer a complementary view of the creative process. They often describe their work as gradually uncovering a story embedded in the world they have built. This perspective motivates our approach. We propose that a world model can grow to contain latent narratives as it develops. When characters hold incomplete knowledge and situations remain unresolved, the world structure itself accumulates seeds for story development. Based on this insight we present FossilWriter, a framework that learns hypergraph world models for creative story generation. FossilWriter represents the story world as a shared hypergraph and introduces a narrative layer that marks elements with developmental potential. An excavation module detects and scores latent narratives on this structure. A scene controller selects locations and characters to develop promising narrative threads. The hypergraph grows during writing and serves as the single source of truth to ensure long-range consistency. Experiments on three benchmarks show that FossilWriter achieves an 81.4% win rate on plot coherence and 84.7% on world consistency. Human assessment shows a 32.5% reduction in long-range factual conflicts compared with strong baselines.
论文检索
输入标题、作者或关键词，从 100,903 篇学术成果中精准定位
We study the optimal design of a self-financing event, a problem that requires balancing the recruitment of costly, positive-value participants with revenue-generating agents who may impose negative values on the event. We introduce a novel two-sided mechanism design framework with plus agents equipped with private costs and positive impact, and minus agents with private values and negative impact upon inclusion in the event, to maximize the overall quality of the event under a budget-balanced (BB) constraint so that the designer does not run a deficit. We conduct a comprehensive study on the theory of optimal event curation on various utility functions. For additive utility, we fully characterize the optimal incentive-compatible Bayesian mechanism under both the ex-ante and ex-post BB constraints. For submodular utility, we propose an ex-ante BB mechanism that achieves a constant-factor approximation to the optimal Bayesian mechanism.
We study the limit CM rate of single-winner voting rules under Impartial Culture, defined as the probability that a preference profile is coalitionally manipulable in the limit of large electorates. For three candidates, Lepelley and Valognes [1999] derived a closed-form expression for Plurality with Runoff, or equivalently Instant-Runoff Voting (IRV), and showed that its limit CM rate is strictly below one. This is remarkable because Kim and Roush [1996] established a limit of one for several major rules, including Maximin and all positional scoring rules except Veto. In this paper, we generalize the result of Lepelley and Valognes to any number of candidates greater than or equal to four. We show that Plurality with Runoff has a limit CM rate equal to one for all such numbers of candidates, whereas IRV retains a limit CM rate strictly below one. To this end, we rely on the notion of Super Condorcet Winner, recently introduced by Durand [2025], which yields an upper bound on the CM rate of IRV. We prove that this bound is asymptotically tight and compute the probability that a Super Condorcet Winner exists, thereby obtaining the exact limit CM rate of IRV. (Extended version with appendices: https://hal.science/hal-05566713. Short video: https://youtu.be/4i2A7qUP-eo.)
Large language models (LLMs) are attractive for context-aware time series forecasting because they can integrate heterogeneous textual signals, yet their discrete, language-oriented tokenization and embedding interfaces are misaligned with continuous numerical values, often harming numerical ordering and forecasting reliability. We propose TempoWave, a plug-and-play temporal wavelet digit interface that maps each scalar observation into digit-wise embeddings constructed from multi-wavelet, multi-scale coefficients. By directly overriding standard token representations, TempoWave seamlessly exposes both fine-grained local fluctuations and macro global structures in a transformer-compatible form, ensuring that precise numerical formatting, distinct digit identity, and robustness to common normalization operations are maintained throughout the LLM pipeline. Experiments across five context-enriched forecasting benchmarks demonstrate that TempoWave consistently improves LLM-based forecasters over standard numeric tokenization and alternative embedding interfaces, achieving a new state-of-the-art. These results highlight the numeric interface as a key bottleneck and suggest that principled multi-resolution embeddings can better couple LLMs' contextual reasoning with precise forecasting. Our code is available at https://github.com/DC-research/TempoWAVE.
Finding an arbitrary number of shortest paths in a graph is a fundamental problem in Graph Theory and Artificial Intelligence with numerous applications to real-world problems. While some algorithms produce paths which might contain loops, the most interesting and challenging problem variant consists of finding simple (or loopless) paths. This problem has been addressed with algorithms which always conduct an arbitrary number of Dijkstra searches. While the current state-of-the-art leverages the notion of sidetrack edge, a new development upon sidetrack edges has been recently introduced which can be used to produce non-simple paths very efficiently, centroids. In this paper, centroids are used to compute an arbitrary number of simple paths with some important benefits: the expansion of a single centroid delivers an arbitrary number of paths; only a single Dijkstra search is required to complete the task; the same algorithm can be easily coupled with heuristics that improve search efficiency. Experimental results across various domains show substantial improvements over the current state of the art, both in runtime and memory usage.
Synthesising autonomous agents that can navigate uncertain environments while adhering to complex temporal constraints remains a fundamental challenge. While Linear Temporal Logic (LTL) provides a rigorous language for specifying such tasks, the inherent undecidability of qualitatively verifying LTL satisfaction in partially observable Markov decision processes renders quantitative synthesis difficult, especially when designing reliable reward signals for approximate solvers. In this paper, we bridge this gap with a novel, sound reward-shaping mechanism that dynamically generates belief-dependent rewards grounded in certified LTL satisfaction. By integrating this mechanism into an enhanced Monte Carlo Planning framework, we empower agents to navigate the `fog' of partial observability with a search process focused on maximising verifiable success. Our experiments demonstrate that this approach not only thrives in scenarios where existing solvers fail but also maintains effectiveness and scalability across diverse benchmark domains.
Parallel tempering, or the replica exchange method, is a Markov Chain Monte Carlo (MCMC) sampling technique for finding low-energy states in complex landscapes by executing multiple processes at different temperatures and allowing for states to migrate between parallel processes based on the Metropolis criterion. Despite a growing interest in the technique as a randomized search heuristic, it is not clear when and why parallel tempering is effective. We conduct a first runtime analysis of the parallel tempering algorithm on a simple quadratic unconstrained binary optimization problem that induces a rugged energy landscape with tunable parameters. We prove that a single-temperature Metropolis process fails to efficiently optimize the problem at any temperature. In sharp contrast, a two-state parallel tempering approach using a low and a high temperature typically solves the problem in O(n^2 log n) iterations. The low-temperature process ensures stability, as it is unlikely to accept worsenings, whereas the high-temperature process facilitates exploration by traversing energy barriers. Improvements are discovered through exploration in the high-temperature process and transferred to the low-temperature process, where they are permanently retained. This effective interplay between processes demonstrates the power of parallel tempering and lends credence to its design.
In heuristic search, a well-known technique to speed up search while providing a suboptimality guarantee is to multiply the heuristic function by a weight w > 1. In this paper, we study the theoretical and practical implications of using such a technique in bi-objective heuristic search, a natural academic exercise that has remained unexplored. We introduce Weighted BOA∗ϵ (WBOA∗ ϵ ), a weighted version of the BOA* algorithm, which uses two real parameters: a weight w for the heuristic and an approximation factor ϵ. Higher values of w and ϵ allow for faster computation of approximate Pareto-optimal solution sets. We prove that WBOA∗ ϵ returns a representative solution set containing (w − 1, ϵ)-approximate solutions. We empirically compare it to A*pex, the state-of-the-art approximate bi-objective search algorithm. We find that WBOA∗ ϵ is competitive with A*pex: when using perfect heuristic functions, in road maps WBOA∗ϵ is faster for higher approximation factors, while in grid maps WBOA∗ϵ dominates A*pex. With imperfect heuristic functions, WBOA∗ϵ performs better than A*pex for lower approximation factors, while the opposite is true for larger approximation factors.
We present D3Adapter, a threat-aware framework that unifies adversarial example detection (AED) and robust inference. D3Adapter attaches a small library of lightweight adapters to a frozen ResNet backbone; the adapters are trained under two loss functions (cross-entropy and optimized reverse cross-entropy) and complementary objectives (clean training and adversarial training), yielding intentionally distinct logit behaviors. During inference, D3Adapter quantifies inter-adapter logit divergence to produce an agreement-based threat score without any external detector for AED. The same pass also performs robust inference by outputting prediction from the selected adapter when an adversarial example is detected, therefore unifying detection and defense into single-pass forward computation. We evaluate D3Adapter under transfer-based and adaptive white-box attacks, and we study scalability across datasets with varying numbers of classes, showing that unified detection and robust inference can be achieved with predictable overhead proportional to the number of adapters.
This paper aims to achieve the segmentation of any 3D part in a scene based on natural language descriptions, extending beyond traditional object-level 3D scene understanding and addressing both data and methodological challenges. Due to the expensive 3D acquisition and annotation burden, existing datasets and methods are typically limited to object-level comprehension. To overcome these limitations, we introduce the 3D-PU dataset, the first large-scale 3D scene dataset with dense 3D part annotations, created through a cost-effective method for constructing synthetic 3D scenes with fine-grained part-level annotations, paving the way for advanced 3D-part scene understanding. On the methodological side, we propose OpenPart3D, a system to effectively tackle the challenges of part-level segmentation with three integrated modules that converts a 3D scene into 3D-part segmentation masks. Extensive experiments demonstrate the effectiveness in open-vocabulary 3D scene understanding tasks at part level, with strong generalization across real-world 3D scene datasets.
Neural network pruning is crucial for efficient deployment on resource-constrained devices, yet achieving high sparsity often leads to significant robustness degradation against adversarial perturbations and corruptions. Recent works typically rely on single-model fine-tuning along a fixed optimization trajectory, which renders the network susceptible to local optima and noise while failing to restore the multiple robustness properties compromised during compression. In this paper, we propose Mutual Heterogeneous Learning (MHL), a framework enabling robust pruning via single-model inference. MHL instantiates heterogeneity through two complementary mechanisms: layer-wise Lipschitz regularization for intermediate feature smoothness and adaptive margin objective for difficulty-aware boundary separation. To guide these diverse experts to converge, we employ entropy-based mutual distillation with a strategic schedule that shifts the optimization trajectory from exploring diverse feature subspaces to consolidating a unified robust model. Extensive experiments on 4 clean and corruption benchmarks and adversarial attacks demonstrate that MHL significantly outperforms single-model baselines in both adversarial robustness (+5%) and corruption robustness (+2.6%) while maintaining competitive clean accuracy.
Strategy synthesis typically follows an all-or-nothing paradigm, returning unrealisable whenever a specification cannot be guaranteed in an uncertain environment. In this paper, we introduce optimal LTLf synthesis, where the goal is to realise as many objectives as possible from a given specification consisting of multiple objectives, especially for the case that they are not all jointly realisable. We first consider max-guarantee synthesis, which commits to a maximal set of objectives that we can a priori guarantee to realise. We then introduce max-observation synthesis, which maximises a posteriori realised objectives that may be incomparable on different executions. Finally, we present incremental max-observation synthesis, which further improves strategies by exploiting opportunities for stronger guarantees when they arise during an execution. Experimental results show that different variations of optimal synthesis scale broadly equally well, solving a large fraction of the benchmark instances within the given timeout, demonstrating the practical feasibility of the approach.
Quantum Federated Learning (QFL) inherits the core vulnerability of federated optimization to malicious clients, while also introducing an attack surface from variational circuit training and measurement-driven gradients. This work proposes a novel CircUit-Level backdoor Threat (CULT) model that formalizes four stealthy attacks by exploiting quantum-aware mechanisms, including Grover, Pauli, Bit-flip, and Sign-flip. By enabling malicious clients on both in-training and post-training surfaces, these attacks can critically undermine the learning process. We establish a rigorous theoretical foundation to demonstrate attack stealthiness under standard smoothness assumptions. Experiments on the MNIST and CIFAR-10 datasets with non-IID splits and varying fractions of malicious clients show that even a single malicious client can induce severe accuracy degradation under FedAvg aggregation. While popular defenses, including Krum, Multi-Krum, FoolsGold, FLGuardian, and Mud-HoG, reduce degradation in many regimes, they fail to eliminate worst-case failure cases, where accuracy drops up to 50%. The experimental analysis further reveals that under the CULT model, malicious updates effectively mask their presence by staying close to benign norms, thereby helping attackers evade detection.
Convex clustering is a well-regarded clustering method, resembling the similar centroid-based approach of Lloyd's $k$-means, without requiring a predefined cluster count. It starts with each data point as its centroid and iteratively merges them. Despite its advantages, this method can fail when dealing with data exhibiting linearly non-separable or non-convex structures. To mitigate the limitations, we propose a kernelized extension of the convex clustering method. This approach projects the data points into a Reproducing Kernel Hilbert Space (RKHS) using a feature map, enabling convex clustering in this transformed space. This kernelization not only allows for better handling of complex data distributions but also produces an embedding in a finite-dimensional vector space. We provide a comprehensive theoretical underpinning for our kernelized approach, proving algorithmic convergence and establishing finite sample bounds for our estimates. The effectiveness of our method is demonstrated through extensive experiments on both synthetic and real-world datasets, showing superior performance compared to state-of-the-art clustering techniques. This work marks a significant advancement in the field, offering an effective solution for clustering in non-linear and non-convex data scenarios.
Understanding overthinking in large reasoning models (LRMs) is crucial for interpretability as well as reasoning efficiency and effectiveness. However, existing approaches primarily adopt coarse-grained reasoning strategies, such as truncating Chains-of-Thought or switching reasoning modes, which reduce verbosity but are insufficient to actively guide reasoning toward more effective trajectories. To address these issues, we propose a training-free, interpretable framework that selects thinking words via attention heads to guide LRMs toward more effective reasoning. Specifically, we categorize thinking steps into effective and redundant states, identify the attention head that best discriminates between them as the Thinking Partition Head to construct an Effective Thinking Representation Space, and compute the Information Gain Ratio (IGR) between candidate thinking words and this space to select the word that steers reasoning toward a more effective direction. Extensive experiments on mathematical and scientific reasoning benchmarks, including AIME24, AMC23, MATH-500, GSM8K, and GPQA-D, show that our method consistently outperforms the strong baseline DEER, achieving average improvements of 1.2–1.3% in accuracy and 2.5–4.5% in compression rate. Compared to vanilla baselines, our approach yields larger gains of 2.6–6.3% in accuracy while reducing token usage by 22–43%.
In several socioeconomic-critical decision-making settings, such as fair resource allocation, climate policy, or AI alignment, multiple principals interact within a common arena. While it is well established that these principals may have differing preferences, decision-making under heterogeneous time preferences remains relatively unexplored. In particular, principals may weigh future outcomes differently and may derive distinct utilities from the same decisions. Motivated by such scenarios, we introduce the notion of heterogeneous time preferences in MDPs, where multiple principals possess distinct reward functions and apply different discount factors to future rewards. To compute meaningful decisions in such settings, an AI agent must rely on a notion of optimality that accounts for the preferences of all principals. We adopt a utilitarian notion of social welfare, defined as the sum of utilities accrued to all principals, and study the synthesis of agent strategies that maximise this welfare. Under heterogeneous time preferences, we show that optimal strategies are no longer positional, even when all principals receive identical rewards. Nevertheless, optimal strategies remain structurally simple: they can be realised as pure finite-memory counting strategies, require only polynomial memory in the system size, and can be synthesised in polynomial time. On the other hand, we show that deciding threshold questions for optimal positional strategies is NP-hard, exposing a poor trade-off: insisting on positional simplicity neither makes synthesis tractable nor preserves social welfare.
We investigate the computational complexity of neural network verification in quantised settings. We distinguish three classes of Feedforward Neural Networks (FNNs): rational FNNs with exact rational weights, quantised FNNs whose weights come from a finite-width arithmetic, and dynamically quantised FNNs in which rational networks are evaluated with respect to a given finite-width arithmetic. We consider two types of specifications used in the literature. Linear programming (LP) specifications are conjunctions of linear constraints, while bit-vector (BV) specifications allow reasoning at the bit level and can express non-linear constraints. Our results give a complexity landscape of these verification problems. For quantised FNNs with fixed arithmetic precision, we show that verification under both LP and BV specifications remains NP-complete, matching the complexity of the rational case. For dynamically quantised FNNs with BV specifications, we establish upper bounds, complementing a previously known PSPACE-hardness result.
Algorithmic decision-making in high-stakes settings can have profound impacts on individuals and populations. While much prior work studies fairness in static settings, recent results show that enforcing static fairness constraints may exacerbate long-run disparities. Motivated by this tension, we study a stylized sequential selection problem in which a decision-maker repeatedly selects individuals, affecting both immediate utility and the population distribution over time. We introduce notions of group fairness for both the short and long term and theoretically analyze the trade-off between fairness and utility via the Price of Fairness (PoF). We characterize optimal and fair policies in the short term and show that the PoF can be large even when group distributions are nearly identical. In contrast, we show that long-term disparities can vanish under simple investment policies that achieve a low PoF. We also empirically validate these theoretical observations using both synthetic and real datasets.
The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MaxSTP: compute a maximum-cardinality consistent subset of constraints. This extension is NP-hard, and we analyze its parameterized complexity under measures that capture practically relevant instance features: the number of variables n (instance scale), the maximum coefficient magnitude k (numeric range), and structural parameters of the constraint graph such as treewidth tw (decomposability), and vertex cover size vc (density). We show that MaxSTP is W[1]-hard parameterized by n, implying that n and parameters that depend on n (including tw and vc) are insufficient for fixed-parameter tractability. For combined parameters, we give an O^*(k^n)-time algorithm, yielding single-exponential solvability for fixed k. While k+tw remains W[1]-hard, MaxSTP is in XP via an O^*((n * k)^tw) algorithm. Our results suggest that MaxSTP is often computationally harder than optimizing qualitative CSPs - we verify that many such problems (including RCC-8 and Allen's algebra) are FPT when parameterized by n or tw. However, we also demonstrate that FPT algorithms for MaxSTP are indeed possible but with other parameters such as k + vc.
Achieving optimal coordination in multiagent systems involves a trade-off between intractable centralized planning and suboptimal decentralized execution. We bridge this gap by introducing Approximate Recursive Small Step-Semi-Decentralized A* (RS-SDA*), a tree search algorithm that exploits time-varying centralization during periods of available communication conditioned on the environment or joint actions. By interleaving offline planning with online search and using relaxed heuristics, RS-SDA* achieves high solution quality with reduced computational overhead. SDec-POMDP benchmark experiments show that Approximate RS-SDA* often finds near exact optimal solutions in less than 1% of the time required by exact algorithms. We show scalability in six labyrinth environments both deterministic and stochastic state transitions, and demonstrate real-world feasibility with a multi-drone search-and-rescue simulation in the DARPA Subterranean Challenge cave system.