Computer Vision
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
All of arXiv
Monday 31 August
Class-Incremental Semantic Segmentation (CISS) is fundamentally challenged by catastrophic forgetting and background shift, where learning new concepts degrades performance on previously seen classes. While existing methods attempt to balance stability (retaining old knowledge) and plasticity (learning new knowledge), they often fail to leverage prior knowledge effectively. These approaches typically rely on indiscriminate knowledge transfer or ambiguous initializations, which can dilute crucial semantic information. To overcome this limitation, we propose SELECT, a novel approach for Selective Context Transfer, which instead grounds each new class in a small set of semantically similar past classes. Its core is a Context Transfer Attention mechanism that aggregates the learned tokens from similar classes into a structured initialization for the new class. To ensure this transfer does not corrupt the borrowed representations, we add a controlled noise perturbation and a margin-based context-transfer loss that enforces separation between the new class token and its source tokens. Extensive experiments on Pascal VOC and ADE20K show that SELECT consistently outperforms prior work, achieving mIoU of 2.2% on VOC and 2.8% on ADE, providing an effective handle on the stability-plasticity dilemma. Code is available at https://github.com/avigupta2798/SELECT.
Numerical Analysis
The specular ellipse method for scalar ordinary differential equations: exactness and accuracy up to fourth order
This paper introduces a family of one-step implicit methods for solving scalar ordinary differential equations. At each step, the update uses a scaled angular mean of two vector-field evaluations, and the positive scale may vary from step to step. The leading terms of the local truncation error can be expressed in terms of the derivative of the signed curvature of the scaled solution graph. We prove that the proposed method reproduces the exact solution at the mesh points when the solution graph has constant signed curvature under a fixed positive scaling and each implicit update is unique. When this special geometric condition is not satisfied, we establish second-order consistency and convergence for positive scale sequences satisfying suitable uniform conditions. Furthermore, third- and fourth-order consistency and convergence can be achieved by choosing the scale to cancel the relevant curvature terms in the local truncation error. Using only the given problem data, we classify when these improvements are possible and determine the corresponding scale choices. An example shows that the proposed fourth-order method can yield smaller errors than the classical fourth-order Runge–Kutta method at the same step size.
Read the full abstract
Computer Vision
Motion-Saliency Complementary Masked Modeling for Point Cloud Video Understanding
Point cloud video representation learning is crucial for 3D dynamic scene understanding. In this paper, we propose MoSaiC, a novel Motion-Saliency Complementary masked modeling framework for self-supervised point cloud video representation learning. MoSaiC couples three components: Curriculum Motion-Saliency Masking (CMSM), which guides the masking process toward motion-salient tokens under a curriculum schedule; Normal-Flow Motion (NFM) modeling, which supervises the local rigid rotation of each token in the Lie algebra so(3) as an explicit geometric motion target; and Cross-view Token Consistency Prediction (CTCP), which enforces consistency between two complementary masked views at the token level. Together, these components allow MoSaiC to effectively capture both appearance and motion dynamics. Extensive experiments on multiple downstream tasks, including action recognition, temporal action segmentation, and point-level semantic segmentation, demonstrate the effectiveness of our approach.
Read the full abstract
General Topology
Some function applications of weak $\lambda$-spaces
In this paper it is proved that there exists (in $ZFC$) a separable pseudocompact weak $\lambda$-space $X$ which is not $\Delta_1$-space. It follows that there exists a space $X$ such that $B_1(X,[0, 1])$ is Choquet, while $B_1(X)$ is not Choquet. Also it is proved that there exists a $\gamma$-set $X$ which is not weak $\lambda$-set. It follows that there exists a zero-dimensional separable metrizable space $X$ such that $B_1(X)$ is Baire, while $B_1(X, [0,1])$ is not Choquet. These results answers the previously posed questions.
Read the full abstract
Artificial Intelligence
SimCRAFT: Distilling Remote Sensing Agents via Synthetic Trajectories and Contextual Retrieval-Augmented Fine-Tuning
The unprecedented surge in Earth observation data volume and diversity has exposed a critical bottleneck for traditional manual workflows, catalyzing the emergence of Remote Sensing (RS) Agents. However, the practical deployment of these advanced agents is severely hindered by their heavy reliance on large-scale general-purpose LLMs, which lack deep domain expertise and impose prohibitive infrastructure demands. To resolve this, we propose SimCRAFT, a model-agnostic framework that distills sophisticated RS orchestration capabilities into a compact 7B-scale model. Addressing data scarcity, we first pair a multiagent synthesis engine with a Mock Execution Engine that checks schema correctness, inter-tool dependencies, and sensor/tool compatibility, producing SimRS-14k, a large-scale, constraint-validated workflow planning corpus. Second, we propose Contextual Retrieval-Augmented Fine-Tuning (CRAFT) that finetunes the model to reason analogically by adapting retrieved Standard Operating Procedures to novel queries under a noise-robust objective, generalizing RAFT to multi-step RS workflow planning without mechanical copying. Extensive experiments demonstrate that SimCRAFT-7B significantly outperforms openweights LLMs and rivals advanced closedsource models and specialized RS agents, while reproducing across three 7B backbones. This work contributes a competitive open-weights baseline for lightweight RS intelligence, enabling efficient autonomous deployment under resource-constrained or resource-conserving conditions.
Read the full abstract
Quantum Physics
Efficient biphoton generation by a waveguide-coupled single atom
A single atom undergoing spontaneous four-wave mixing near a chiral waveguide can efficiently channel an emitted Stokes-anti-Stokes photon pair into two tightly confined waveguide modes, yielding thus enhanced biphoton generation without requiring loss suppression or stringent phase matching. We develop a perturbative treatment, valid for a four-level atomic system under experimentally realistic conditions, to explain physical origins and clarify relevant constraints of such an enhancement determined by the interplay of atomic decay rates toward guided and unguided modes. Besides achieving optimal generation rates equivalent to a cold atomic ensemble hundreds of micrometers long in free space, our biphoton source naturally fulfills key requirements for next-generation on-chip quantum light sources, namely low-loss operation, robustness, compactness, and scalability.
Read the full abstract
Information Theory
An Explicit Family of Log-Concave Counterexamples to the Gaussian Completely Monotone Conjecture
We construct smooth, strictly log-concave counterexamples to the Gaussian completely monotone conjecture in every dimension. In one dimension, they form an explicit family $f_m$ whose signed $m$th entropy derivative at time zero is negative for every sufficiently large $m$; the inequality persists for all sufficiently small positive times. Tensorization with a broad Gaussian factor gives the higher-dimensional examples. The argument is analytic and self-contained. It reduces the sign to a two-frequency entropy calculation on the circle and transfers the resulting asymptotic to the real line through an exact heat-flow formula for Gaussian-windowed Fourier modes. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.
Read the full abstract
Digital Libraries
SoniMet - A tool for sonifying and visualizing the performance of single researchers
For centuries, the scientific community has predominantly relied on visual tools to communicate empirical results and complex datasets. While visual representations dominate bibliometric analyses, the human auditory system possesses sensitive capacities for processing complex temporal information, distinguishing intricate patterns, and tracking parallel data streams. Data sonification translates data relations into acoustic signals, offering an alternative method for data exploration, pattern recognition, and scientific communication. This paper applies this concept to the field of bibliometrics through metrics sonification-the auditory translation of bibliometric information-and introduces SoniMet (Sonifying Metrics), a web-based tool designed to visualize and sonify the publication and citation data of individual scientists (see https://sonimet.kennebec.co.uk). SoniMet connects to the OpenAlex database to retrieve bibliometric records and displays them on an interactive chronological timeline. The tool employs direct parameter mapping to translate citation impact indicators into non-speech sound: field-weighted citation impact and citation counts determine the pitch and volume of a synthesized note and are mapped to the acoustic echo strength. Although SoniMet expands the methodological toolkit for research evaluation, current limitations include its restriction to individual scholar profiles and the challenge of integrating transient audio files into traditional, text-based scientific publishing workflows. Future empirical user studies are necessary to systematically evaluate the analytical utility and cognitive benefits of metrics sonification compared to established visual methods.
Read the full abstract
Information Theory
Strengthening Recursive Constructions for Zero-Error Shannon Capacity
The exact Shannon capacity is unknown for every odd cycle beyond the five-cycle $C_5$, making odd cycles a central open problem in zero-error information theory. Improving the known lower bounds requires constructing large independent sets in strong powers of these graphs. Recent AI-assisted work has produced a rapid sequence of improvements: building on the construction of Itty et al., Gao developed a recursive product construction for combining structured independent sets, and Buys, Polak, and Zuiddam (BPZ) subsequently strengthened this through a richer recursion framework. We continue this line of AI-assisted exploration and introduce a heterogeneous refinement of these constructions. The central observation is that the usefulness of an intermediate construction depends not only on the size of its current main independent set, but also on the auxiliary structure it carries into subsequent recursion. Consequently, different parts of that auxiliary structure need not use the same independent set, and different occurrences in a recursion need not use the same intermediate representation. We formalize this for Gao's binary product and derive explicit propagation rules showing how heterogeneous choices strengthen the resulting gadget while leaving its current code size unchanged, then extend the principle to the more general BPZ framework, tailoring constructions to the distinct roles they play within the recursion. Applying these refinements to the seven-cycle $C_7$, we obtain an independent set in $C_7^{\boxtimes 500}$ yielding $\Theta(C_7)\ge 3.25883262\ldots$, improving the best known lower bound. Beyond the numerical gain, the results illustrate a general principle for recursive zero-error constructions: intermediate structures with the same dimension and current code size can have different downstream value depending on where and how they are used in the recursion.
Read the full abstract
Quantum Physics
Modular-Annihilator Parent Hamiltonians for Purified Gibbs States: Spectral Design and Controlled Approximation
Purified Gibbs states provide a bridge between finite-temperature physics, dissipative dynamics, and ground-state methods. In this work, we study the exact finite sum-of-squares (SoS) construction of their parent Hamiltonians and the associated Lindbladian based on modular annihilators. Given a finite set of Hermitian generators, the corresponding modular annihilators yield a frustration-free SoS representation without continuous time integrals or an explicit decomposition into Bohr-frequency sectors. The purified Gibbs state remains a common zero mode while the freedom to choose and combine the generators can be used to optimize the spectral properties of the parent Hamiltonian. For free-fermion Hamiltonians, modular transformations act linearly on Majorana operators, leading to an analytically solvable family of parent Hamiltonians parameterized by a real symmetric coefficient matrix \(S\). For the scalar-functional subclass $S=f(h)$, we show that, at fixed operator norm, the choice $S_{\mathrm{opt}}\propto 1/\sqrt{\cosh(2\beta h)}$ has mixing time upper bound $2\log(2N/\epsilon)$ for any $\beta$, which exhibits rapid mixing and is irrelevant to the inverse temperature $\beta$. For interacting systems, where the modularly dressed generators are not available in closed form, we introduce a Krylov–Lanczos approximation scheme and bound the resulting ground-state error in terms of the modular-approximation error and the parent-Hamiltonian gap. Numerical results illustrate the free-fermion spectral advantage and show how the accuracy of the interacting construction depends on temperature, interaction strength, and Krylov dimension.
Read the full abstract
Optimization and Control
Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
We study decentralized online optimization of upper-linearizable payoffs over an action set under efficient separation access, with applications to online continuous diminishing-return (DR) submodular maximization. We propose Decentralized Barrier Follow-the-Regularized-Leader (Dec-BFTRL), and evaluate each agent's played action against the average of all local objectives. Each agent maps an internal iterate to a feasible action through an approximate gauge projection, communicates only a cumulative surrogate-gradient dual state, and invokes the local HybridNewton procedure to approximately minimize its post-communication BFTRL potential. For every agent, we achieve expected network-aggregate regret of $\widetilde O(\sqrt{T})$. Over $T$ rounds, each agent uses $T$ neighbor-mixing steps and $\widetilde O(T)$ separation-oracle calls. We give wrapper instantiations covering four up-concave or DR-submodular maximization problems.
Read the full abstract
Computation and Language
Read the Room, Read the Image: Understanding Indirect Speech Acts in Multimodal Visual Contexts
Indirect speech acts (ISAs) require pragmatic reasoning over context, as directive intent can- not be inferred from surface form alone. Prior text-based studies and existing multimodal benchmarks largely overlook this requirement, focusing instead on explicitly encoded context or perceptual recognition, and thus underex- plore context-dependent pragmatic understand- ing, particularly in high-context languages such as Korean. We introduce READI, a multimodal benchmark for evaluating ISA understanding through integrated reasoning over visual con- text and dialogue. READI models graded in- directness grounded in pragmatic theory and formulates the task as vision-based pragmatic question answering (V-PQA), supporting cross- lingual evaluation in English and Korean. Ex- periments show that even state-of-the-art multi- modal models struggle with visually grounded indirect speech acts, with performance declin- ing as indirectness increases, underscoring the need for benchmarks that explicitly target con- textual pragmatic reasoning.
Read the full abstract
Metric Geometry
On low-dimensional uniform rectifiability in Heisenberg groups - Part 2
Let $1\leq k\leq n$. We prove that $k$-dimensional intrinsic Lipschitz graphs in the Heisenberg group $\mathbb{H}^n$ satisfy a geometric lemma $\mathrm{GLem}(\beta_{2,\mathcal{V}_k},p)$ for horizontal $\beta$-numbers with an exponent $p=p(k)$. Previously, this result was known only in the case $k=1$; our proof recovers the sharp exponent $p=4$ in this setting. For $k>1$, we adapt an integral geometric approach originally developed by Orponen for Euclidean and parabolic Lipschitz functions. In addition, for $k=n$, we show how to deduce a geometric lemma with $p=4$ directly from an isotropic Dorronsoro theorem in $\mathbb{R}^{2n}$ using a Poincaré inequality. Building on the new geometric lemmas, we establish a necessary condition for $k$-regular sets in $\mathbb{H}^n$ to admit corona decompositions by intrinsic Lipschitz graphs. The condition is known to be sufficient by earlier work of the last two authors together with Pinamonti. It involves additional flatness coefficients besides $\beta_{2,\mathcal{V}_k}$. Along the way, we therefore extend the known stability results for geometric lemmas under the “big pieces” functor to a larger class of coefficients.
Read the full abstract
Hardware Architecture
FABO: Agent-Guided Discovery of Joint Breakpoint Optimization for Timing-Driven Routing Trees
The topology of a routing tree determines how a multi-pin net branches and shares physical wire, directly affecting wirelength, congestion, capacitance, and delay. We study a central early-stage routing problem: minimizing wirelength while bounding the root-to-sink path stretch for every sink. SALT is the state-of-the-art constructive algorithm for this problem. We ask whether language-model-guided search can discover a constructive algorithm that improves on SALT. To make this search reliable, we develop an agent framework that combines parallel exploration with independent checking. Applied to SALT, the framework discovers a structural limitation: SALT repairs one sink path at a time and therefore never jointly decides where paths sharing root-side wire should split. This sink-local choice can split the paths too early and duplicate wire. This discovery leads to Flow-Aware Breakpoint Optimization (FABO), which jointly optimizes breakpoints across root-to-sink paths that share wire while preserving every sink's stretch budget. Across 1.29 million ICCAD15 nets and SALT's 20-point stretch-tolerance schedule, FABO reduces average FLUTE-normalized wirelength at every setting, with peak same reductions of 0.83% overall and 2.66% for nets with at least 30 pins. With 1.3x SALT's runtime, FABO-FAST identifies and optimizes most nets for which FABO provides a substantial wirelength reduction. Code is available at https://github.com/DevinShang/routing-FABO.
Read the full abstract
Game Theory
Tight Maximin Share Guarantees of EFX and PMMS
In the fair division of indivisible goods among autonomous agents, allocations frequently satisfy strong pairwise fairness criteria while failing to guarantee an agent's full maximin share. Maximin share (MMS) is a global benchmark: the value an agent can guarantee by partitioning all goods into $n$ bundles and receiving her least preferred bundle. In contrast, local pairwise fairness notions—most notably envy-freeness up to any good (EFX) and pairwise maximin share (PMMS)—evaluate fairness through bilateral bundle comparisons. We resolve the open question of determining the optimal universal MMS approximation factor guaranteed by either local notion under nonnegative additive valuations, proving that both factors equal exactly $10/17$. For the lower bound, we show that both EFX and PMMS imply a common local residual inequality: the value of any foreign bundle after removing its least valuable item cannot exceed the focal agent's allocated value. We design a continuous piecewise weight function that converts this local constraint into the global $10/17$ MMS guarantee. The same charging argument establishes that $\alpha$-EFX implies $(10\alpha/17)$-MMS. For tightness, we construct an explicit family of complete allocations that simultaneously satisfy PMMS and EFX$_0$, including comparisons involving zero-valued goods, and whose MMS ratios converge to $10/17$. For each fixed number of agents, we also establish exact reciprocal identities connecting fair division to scheduling: the EFX guarantee is the reciprocal of the pure price of anarchy in selfish identical-machine covering, while the PMMS guarantee is the reciprocal of a locality gap for exact repartition of two machines.
Read the full abstract
Combinatorics
Inversion-descent enumerators of $\underline{32}1$-avoiding permutations
We give the recurrence relation for counting polynomials for permutations avoiding the $\321$ vincular pattern, with respect to inversion numbers and descent numbers, and consequently give the $q$-exponential generating function for these counting polynomials. Furthermore, we give another explanation for these counting polynomials in terms of restricted-growth words.
Read the full abstract
Numerical Analysis
Parameter-Robust Subspace Correction with Multiple Semidefinite Penalties
Independently weighted semidefinite penalties arise in augmented-Lagrangian and constrained formulations. This paper characterizes when an exact additive subspace-correction preconditioner remains uniformly effective over all nonnegative penalty weights on a fixed finite-dimensional space. Robustness holds precisely when the correction spaces decompose every joint kernel generated by a nonempty subset of penalties. If one condition fails, a computable constant determines the exact first-order decay of the smallest preconditioned eigenvalue along the associated parameter ray, and the condition number grows linearly; none of the subset conditions can be discarded in general. Filtered decompositions provide computable sufficient bounds on parameter-ordering cones, while distributive kernel lattices permit a single common splitting. Exact-additive computations confirm the characterization and predicted rates. Separate Scott-Vogelius experiments produce stable multilevel iteration counts over the tested weights and mesh levels. The analysis does not establish mesh-uniformity.
Read the full abstract
High Energy Physics (Phenomenology)
High energy thermal photons from chirally imbalanced QGP
We compute the thermal photon production rate from a chirally asymmetric quark gluon plasma. We estimate the hard part from scattering of chiral quarks and demonstrate the cut-off independence of the total thermal photon emission rate. This is achieved by combining the hard with the soft contribution evaluated in our previous work using the Braaten-Pisarski method of hard thermal loop perturbation theory. It is observed that the presence of chiral imbalance leads to an overall enhancement in the emission rate of thermal photons.
Read the full abstract
Computer Vision
Centering before Pruning: Lightweight Geometry Correction for Diversity-Based Visual Token Pruning in LVLMs
Large vision-language models (LVLMs) incur substantial inference costs due to their long and highly redundant visual-token sequences. Diversity-based pruning mitigates this cost by selecting token subsets based on pairwise cosine similarity. We find, however, that similarities between raw visual tokens are strongly concentrated in the positive range, limiting their ability to distinguish non-redundant tokens. A natural way to improve this resolution is to center token features before computing cosine similarity. Centering indeed reveals a substantially richer pairwise structure, yet unexpectedly degrades pruning performance when used alone. We show that this apparent contradiction arises because the raw geometry does more than represent pairwise diversity: it also implicitly favors globally distinctive tokens, which tend to contain semantically informative content. Centering better resolves subset diversity but loses this useful token-wise preference, revealing that diversity and distinctiveness are entangled in the raw geometry. Based on this analysis, we propose the Centered Geometry Pruner (Cen-Prune), which measures subset diversity using centered cosine similarity while retaining raw-space distinctiveness as a complementary token-wise preference. This lightweight, plug-and-play correction leaves the underlying selection mechanism unchanged and incurs negligible computational overhead. Extensive experiments across multiple image- and video-understanding benchmarks and LVLM architectures demonstrate that Cen-Prune provides robust improvements in overall performance across existing diversity-based pruners.
Read the full abstract
Machine Learning
Multivariate Scientific Data Compression with Learned Cross-Variable Latent Decorrelation and Autoregressive Entropy Modeling
Scientific simulations generate collections of physical fields with heterogeneous statistics and dependencies, yet learned compressors often encode those fields independently or rely on a shared encoder without explicitly modeling the structure that remains in latent space. We present CAESAR-LDAR, an error-controlled multivariate learned compressor that augments a shared CAESAR-V backbone with two complementary mechanisms: a trainable orthogonal transform that reorganizes dependence across aligned latent channels, and a causal autoregressive hierarchical prior that captures local spatial structure left after transformation. Orthogonality is maintained through a matrix-exponential parameterization, making the transform exactly invertible without an additional penalty. A common residual-correction stage is applied uniformly to all variants to enforce the requested reconstruction tolerance. Experiments across combustion, climate, and turbulence data show that the two mechanisms are useful in different regimes. Latent decorrelation helps most when substantial linear cross-channel dependence survives the nonlinear encoder, whereas autoregressive modeling remains effective when the remaining structure is primarily local or spatial. Their combination provides the strongest or near-strongest rate-distortion performance across the evaluated datasets. The global transform adds little computational overhead, while autoregressive coding introduces a larger throughput tradeoff. More broadly, the results suggest a practical design principle for multivariate scientific compression: exploit global cross-channel dependence when it is measurably present in latent space, and use local probabilistic context as a complementary mechanism across a wider range of data regimes.
Read the full abstract
Machine Learning (Statistics)
Estimating Population-Risk Curves Along Nonconvex Gradient Flows from the Training Sample
We estimate the conditional population-risk curve of a realized smooth nonconvex gradient flow from the training sample. Flow approximate leave-one-out (Flow-ALO) propagates a deletion response and evaluates omitted observations at approximate deleted paths. The risk-curve error decomposes into response approximation, exact-LOO fluctuation, and deletion-to-full risk transfer. On each fixed finite horizon, bounded centered training-loss gradients, a one-sided Hessian lower bound, locally Lipschitz Hessians, and a strict tube-closure condition yield an explicit $(n-1)^{-2}$ bound for the deletion-response error. Bounded evaluation-loss gradients transfer the deletion-response bound to the score without requiring the Hessian to be invertible. Direct first-order jackknife cancellation and exact-LOO concentration control deletion-to-full risk transfer and fluctuation, respectively, completing recovery of the conditional population-risk curve. For bounded smooth two-layer mean-field networks training both layers, the score-error bound is uniform in width.
Read the full abstract
Computation and Language
Using Prosody to Predict Syntactic Structure
While it is well-established that prosody carries crucial cues for syntactic structure, the degree and nature of correspondence between these two domains remains contested. We investigate the syntax-prosody interface through an information-theoretic lens, quantifying the interaction between prosodic features and syntactic representations as their mutual information. We provide a general-purpose framework for estimating this quantity over large speech-text corpora using multimodal language models. Our framework is structure-agnostic and modular, insofar as it can be used to measure the contributions of individual prosodic features or components of structure. We evaluate the syntax-prosody relationship for two features (word duration and inter-word pauses) across two domains–read audiobooks and spontaneous conversations–both in English. Our results demonstrate that prosody contains measurable syntactic information, with prosodic features reducing syntactic uncertainty in spontaneous conversations by up to 10.2%. Our findings offer new empirical support for several theoretical accounts of the syntax-prosody interface.
Read the full abstract
Systems and Control
Subspace Based Identification of Errors-in-Variables Linear Descriptor Systems
The identification of linear descriptor systems (DAEs) from noise-corrupted data makes two critical assumptions: requirement of an a priori classification of variables into inputs and outputs, and a pre-specified structural assumption with respect to the index of the system. This paper proposes a data-driven methodology for identifying index-0 and index-1 DAEs within an errors-in-variables framework. We extend a subspace-based iterative PCA (SMI-IPCA) approach to the behavioral setting, treating all measured variables as a unified augmented vector to avoid classification bias. This method enables systematic estimation of the noise variances, the number of algebraic and differential output variables, while simultaneously identifying the algebraic constraints and kernel representation of the dynamic system corresponding to its minimal realization order without prior structural knowledge. Simulation studies on index-0 and index-1 systems demonstrate the effectiveness of the proposed approach and its practical applicability.
Read the full abstract
Computation and Language
Stratified Consistency Distillation for Natural Language Formalization
Neurosymbolic reasoning has shown promising success in addressing complex reasoning tasks by combining large language models (LLMs) and symbolic solvers. While this approach shows promise, a fundamental challenge remains: improving the accuracy of translations from natural language to logical formulas. Current methods predominantly rely on prompt engineering, which is difficult to scale across different domains and input formats. Drawing inspiration from the success of fine-tuning in other model adaptation and alignment applications, we propose a fine-tuning-based Stratified Consistency Distillation approach: (1) We generate K logical translations per input using a frontier LLM and cluster them by semantic equivalence (2) Based on the entropy level, we apply majority voting (low entropy), LLM-as-a-Judge (medium entropy), or unification/abstention (high entropy), and (3) fine-tune a smaller model using the selected pseudo-labels. Our experiments show significant and consistent improvements in both Pass@K and our novel Equivalent Logical Similarity metrics, demonstrating the potential of advancing logical translation through consistency distillation.
Read the full abstract
Game Theory
Residual Maximin Share: Exact Finite-Agent Frontier, Sparse Extremizers, and Threshold Cuts
Residual maximin share (RMMS) is the largest share threshold that remains guaranteeable throughout dynamic allocation processes, even after previously allocated, lower-valued bundles are removed from the item pool. For additive valuations, recent density-balance analyses established finite-agent lower bounds comparing RMMS with the classical maximin share (MMS). In this paper, we prove that these finite-agent lower bounds are exact. Specifically, if $d_n$ denotes the largest odd integer at most $n$, the worst-case ratio satisfies $\inf_{M,v:\operatorname{MMS}>0}\frac{\operatorname{RMMS}(M,v,n)}{\operatorname{MMS}(M,v,n)}=\frac{2d_n}{3d_n-1}$. Consequently, the exact additive frontier forms consecutive odd-even plateaus and converges monotonically to $2/3$. We then investigate the combinatorial structure of extremal instances. While naive witnesses require $\Theta(n^2)$ items, we construct an explicit three-valued family achieving the exact boundary with only linear support: $(5n-3)/2$ items for odd $n$ and $(5n-4)/2$ items for even $n$. Its low-valued block supports two exact partitions that simultaneously certify the MMS benchmark and the residual obstruction. By modeling these dual partitions as a bipartite transportation graph, we prove that this block attains the absolute minimum support $q+d-1=3q$. At minimum support, any two-valued filler is uniquely rigid up to relabeling. Finally, we establish structural characterizations of RMMS. A general min–max representation applies to all finite monotone valuations. For integer additive valuations, we prove that a threshold $T$ is residual self-feasible if and only if every subset cut satisfies a packing-covering condition. Because RMMS is pointwise maximal among residual self-feasible shares, these exact constants establish a tight limitation on the fairness guarantees achievable by share-based lone-divider algorithms.
Read the full abstract
Computation and Language
Beyond Surface Forms: Symbolic Edits as a Test for Logical Reasoning with LLMs
Logical reasoning with large language models (LLMs) is a critical capability, as it reflects a system's ability to correctly deduce hypotheses from a given context using faithful deductive processes. However, LLM reasoning has often been shown to be sensitive to small surface-level variations in problem formulation, raising questions about whether models truly follow the underlying logical structure. Studying this behavior is challenging because the symbolic components of logical problems, such as operators and predicates, are difficult to systematically manipulate in natural language. We introduce a tool-driven framework for generating controlled, label-preserving edits to logical reasoning problems. Our method operates on symbolic representations of first-order logic and constraint satisfaction problem tasks, enabling targeted modifications to logical operators and other structural components before translating them back into natural language. Using this framework, we evaluate various LLMs under cumulative and individual operator edits and analyze their behavior in response to these changes. Our quantitative and qualitative analyses show that LLM reasoning behavior under controlled operator edits is inconsistent, regardless of model size or family: models sometimes adapt correctly to structural changes but often fail to track their logical consequences. The results from this automated stress test enable an evaluation of language models across different dimensions and help measure the reliability of their reasoning.
Read the full abstract
Information Retrieval
CAMIE: Co-Engagement-Aware Multimodal Item Embeddings for Snap Dynamic Product Ads Retrieval
Item-to-item (I2I) retrieval is a core primitive in large-scale recommendation and advertising systems. In production Snap Dynamic Product Ads (DPA), I2I retrieval faces two challenges: separate visual, textual, and multimodal encoders fragment the retrieval stack, and content-only training does not align embeddings with the co-engagement behavior that drives downstream conversions. We present CAMIE, a co-engagement-aware multimodal item embedding framework for Snap DPA retrieval. CAMIE builds on LLM/MLLM backbones, using their native multimodal interfaces to represent item images and metadata in a shared embedding space. It then fine-tunes the backbone on co-engaged item pairs mined from user journeys with a symmetric in-batch InfoNCE objective. Offline, CAMIE outperforms the strongest commercial multimodal embedding model on Recall@10 and serves text-only retrieval from the same checkpoint with minimal quality loss. Online, CAMIE serves as a drop-in replacement for two deployed content-based I2I encoders, delivering +0.390% CTR / +10.832% CVR over the multimodal control, +18.958% CTR / +13.12% CVR over the text control, and +0.211% CTR / +1.911% CVR on overall DPA traffic. CAMIE is deployed in production.
Read the full abstract
Machine Learning
Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression
We resolve the threshold part of Question 4 of the COLT 2025 open problem "Data Selection for Regression Tasks" of Hanneke, Moran, Shlimovich and Yehudayoff. We study vector-valued linear regression with square loss $\ell_{(x,y)}(W)=\lVert Wx-y\rVert_2^2$, where $x\in\mathbb{R}^d$ and $y\in\mathbb{R}^m$. The learner returns the minimum-Frobenius-norm empirical risk minimizer. We prove that the minimal budget of weighted examples for recovering the full-data loss on every finite dataset is exactly $n^{\star}(d,m)=(m+1)d$. We determine the weighted selection profile $F_{\mathrm{weighted}}(d,m,n)$ at the near-threshold budget: $F_{\mathrm{weighted}}(d,m,(m+1)d-1)=1+1/(dm^2)$. We recover the known spanning-budget value $F_{\mathrm{weighted}}(d,m,d)=d+1$ for every $m$, and $F_{\mathrm{weighted}}(d,m,n)=\infty$ for $n<d$. For the smallest open intermediate cell $(d,m)=(2,2)$ we prove $F_{\mathrm{weighted}}(2,2,3)\in[13/8,15/8]$ and $F_{\mathrm{weighted}}(2,2,4)\in[5/4,3/2]$. We reduce the conjectured exact values $13/8$ and $5/4$ to a finite moment problem on the circle with at most seven atoms and assemble structural evidence for it. The upper bounds use a fixed-basis conic compression lemma, a determinant–facet rigidity theorem for maximal certificates, and sharp sparsification lemmas for zero-mean weighted point systems. These tools may be of independent interest. We also exhibit an explicit six-point integer dataset with $d=m=2$ on which no weighted selection of $2d$ points recovers the optimal loss. Thus the scalar sufficient budget $2d$ does not extend to vector-valued outputs. Our new regression-profile results for $m\ge2$ extend the scalar theory for $m=1$.
Read the full abstract
Numerical Analysis
Mesh-Uniform Power Stability of Two-Relaxation-Time Vector Lattice Boltzmann Schemes with Reversible Boundaries
We consider the collision-transport operator for vector-valued two-relaxation-time lattice Boltzmann schemes linearized about a uniform rest state. Assume that the equilibrium blocks are positive definite and that the link-even and link-odd relaxation parameters satisfy s_+ + s_- = 2 and 0 < s_- < 2. If the homogeneous transport is unitary in the equilibrium metric and reversible under velocity exchange, then the powers of the amplification operator are bounded uniformly with respect to the number and arrangement of lattice nodes. The admissible transports include periodic transport, vector halfway bounce-back, coordinate-aligned specular reflection, tangential orthogonal involutions, and compatible multi-channel scattering. The proof reduces the population equation to a two-step macroscopic recurrence generated by a contraction. An inclusion of the numerical range in an ellipse, combined with the Crouzeix-Palencia theorem, yields a dimension-independent estimate for the companion operator and hence the population bound. For a three-coefficient off-midpoint boundary interpolation, we give an exact rational D2N5 example whose finite-domain amplification matrix has a real eigenvalue larger than one, although the interpolation coefficients and bulk parameters are admissible. Thus coefficient convexity alone does not ensure stability for this boundary family.
Read the full abstract
Machine Learning
Strong Drafts Need Compact Memories: Long-Context Speculative Decoding with Compressed KV Cache
Long-context LLM applications such as document summarization and multi-turn agents require generation from prefixes spanning tens of thousands of tokens, making decoding latency a major bottleneck. Speculative decoding (SD) reduces latency without changing model outputs, but its speedup depends on both accepted draft tokens and draft-step latency: Lightweight drafts are fast but lack the capacity to capture long-range dependencies, whereas strong independent drafts recover acceptance but incur growing KV-access cost at long prefixes. We introduce memory-augmented drafting for long-context SD, equipping a strong independent draft with compressed draft-side KV memory: A lightweight adaptor constructs and incrementally updates this memory to retain distant information and exact recent context. The target verifier retains its full KV cache and applies the standard accept/reject rule, preserving SD's lossless guarantee. Experiments on Llama~3.1-8B and 70B targets at prefix lengths up to 32K show that our method reduces draft-side memory by over 70%. It achieves speedups of up to 2.08x and 3.33x , respectively, over autoregressive decoding.