system designers

Abstract: Let $S$ be a reachable image of a strongly connected synchronizing automaton and $\varnothing\ne A\subsetneq S$. We determine the maximum shortest avoid-or-compress length over binary and arbitrary finite alphabets for $m=n-|S|=4$ and $m=5$. The exact values are $\min(n-|A|,11)$ and $\min(n-|A|,14)$, respectively. Uniform binary constructions attain both bounds. For the upper bounds, short-pair graphs and actual-image constraints reduce all parameters to finite necessary domains. Exhaustive checks exclude the domains, apart from a single relaxation eliminated by a multipartite overlap lemma. The largest calculation covers 3,206,988 domains.

Abstract: Continual vision-language models (VLMs) encounter a stream of environments and must also reject inputs that do not belong to the environment at hand. Class information from earlier environments can aid out-of-distribution (OOD) detection, yet existing detectors score each environment in isolation, and when previous environments help or hurt is theoretically unclear. We develop a theory of environment-aware OOD detection built on contribution scores, pairwise cosine expectations measuring how the image and text features of one environment align with those of another. We propose a cross-environment maximum-concept-matching (MCM) score with two terms: a primary term matching the test image against the current class texts, and a secondary term matching it against the class texts of a previous environment, weighted by the intra-modal alignment between the two environments. We prove that, under a positive environment transition and a bounded class-matching margin for OOD inputs, this score attains a false-positive rate no larger than that of the standard MCM detector at an adjusted threshold. We then show that the score gap of an MCM detector between two environments equals the self-contribution of the in-distribution environment minus its cross-modal contribution into the OOD environment, which separates soft OOD environments, with explicit AUROC, true-positive, and false-positive guarantees, from hard ones, which no threshold that retains the in-distribution data can reliably reject. For cascaded detection, in which the text prototypes of all seen environments are pooled, the false-positive rate on every past environment is non-decreasing in time, and we characterize when detection provably fails. A contribution balance factor applied to the gradients of the classification loss and of a smoothed false-positive rate completes the framework.

Abstract: A ring Petri net (weighted circuit, cyclic weighted T-system) consists of a single directed circuit with arbitrary positive arc weights. We show that deciding liveness of ring Petri nets is coNP-complete, and that coNP-hardness holds in the strong sense already for token-conserving rings, in which every transition consumes and produces the same number of tokens. The proof is a short reduction from the covering problem for systems of residue classes (the complement of Simultaneous Incongruences). Together with a known reduction to circuits, it follows that liveness of weighted T-systems (weighted marked graphs, synchronous dataflow graphs) is coNP-complete, and coNP-hard in the strong sense. As a further consequence, the halting problem for chip-firing on simple directed graphs is NP-complete, which answers a question of Farrell and Levine. On 7 October 2026, the problem of liveness was posed to the AI model Claude Opus 5.5 (Anthropic), which found the reduction, also suggesting the application to the chip-firing problem, and wrote a first version of this paper; the human authors checked it and, together with the model, revised it iteratively into the present form.

Abstract: Emerging dataflow accelerators offer exceptional energy efficiency and throughput for machine learning workloads, yet remain largely opaque to developers for performance analysis. Unlike CPUs and GPUs, where instrumentation frameworks enable fine-grained introspection, dataflow hardware exposes little information. This lack of transparency limits the ability of compiler engineers, system designers, and application developers to analyze, tune, or debug accelerator behavior. In this paper, we introduce DFIT (DataFlow Accelerator Instrumentation Tool), an instrumentation framework designed specifically for dataflow architectures. DFIT directly instruments operations, regions, and compiler transformations at the graph IR and backend-lowering stages using semantic program representation. DFIT captures high-level, semantically meaningful data that reflect the true dataflow of computation. These data can be exported for visualization and analysis. Our approach demonstrates how instrumentation can be generalized beyond traditional hardware to support heterogeneous architectures, providing portability without modifying tool logic. By opening the black box of dataflow execution, DFIT establishes a foundation for new classes of performance analysis tools for AI accelerators. It provides a practical path toward reproducible, architecture-aware introspection across heterogeneous systems, bridging the long-standing visibility gap between compiler design, runtime scheduling, and hardware realization. Evaluation across Cerebras, SambaNova, and TPU shows practical overhead of 3.53%-13.62% across instrumentation modes with robust cross-platform portability.

Abstract: A parallel sampler can choose at random which coordinates to generate together. For a target $p$ and the output law $q_U$ of a schedule $U$ drawn afresh for each output, we compare the schedule-averaged divergence $\mathbb{E}_U D_{\mathrm{KL}}(p\|q_U)$ with the output-law divergence $D_{\mathrm{KL}}(p\|\mathbb{E}_U q_U)$, in nats. Rounds commit independent draws from exact conditional marginals frozen at the round's start, each output's schedule is drawn before sampling from a finite mixture of schedules, and every scheduled round is charged. For the uniform distribution on binary strings of even length $n$ with $n/2$ ones, the least expected number of rounds at a fixed tolerance $\varepsilon>0$ is $Θ_\varepsilon((\log n)^2)$ under the first criterion but $(e^{-\varepsilon}+o(1))\log_2\ln n$ under the second, and the double-logarithmic order is attainable with the same round count on every run. For this target, a count-state recursion gives the exact least output divergence at every round cap over all causal randomized policies. The separation extends to weighted fixed-count targets with bounded weight ratios and quota fractions bounded away from zero and one, without permutation symmetry, and to the full-support Beta$(1,1)$--Bernoulli target, where the sharp expected cost under the output-law criterion is $(e^{-\varepsilon}/2+o(1))\log_2\log_2n$, attained with rare $n$-round runs. Prior work implies the order of the schedule-averaged cost on the balanced target and its $O_\varepsilon((\log n)^2)$ upper bounds on both extensions.

Abstract: We present a version of the vector balancing problem in which each vector may be given a sign and a permutation of its coordinates. We prove that this vector balancing problem and its corresponding prefix problem admit an explicit bound, and we further show that it is asymptotically optimal in the dimension. Our method of proof is purely geometric.