We present a linearized form of 2-simplicial attention by rewriting the trilinear score as an inner product between a composite query and a key, so that the sum over keys takes the same form as ordinary softmax attention. We then approximate this sum with positive random features and store all previous keys in a fixed-size state, while the sum over second keys stays exact over all previous tokens. This reduces the cost from cubic to quadratic in sequence length, and both keys range over all previous tokens, which windowed 2-simplicial attention does not allow. We implement it with custom Triton kernels and combine it with Kimi Delta Attention to build a model with no softmax attention at all. With 15B equal training tokens on FineWeb-Edu, this model lowers validation loss from 2.35 to 2.32 over a KDA hybrid and lowers LAMBADA perplexity from 40 to 38.
Aritra Das, Francesco Cagnetta, Darshil Doshi, Victor V. Albert, Maissam Barkeshli, Andrey Gromov
原文摘要
Hierarchical models have been proposed as synthetic settings for studying language. However, their relevance to realistic language corpora remains underexplored. In this work, we introduce tree-grams, autoregressive generative $n$-gram models that build the conditional probability tensor $p(x_n \mid x_{1:n-1})$ through a hierarchical composition of order-2 and order-3 tensors. $n$ controls the maximal context window, whereas a rank hyperparameter $d$ controls model capacity, yielding an interpretable and systematically scalable family of approximators of language. We show how tree-grams outperform existing $n$-gram baselines, while remaining competitive with deep transformer-based language models. We demonstrate the utility of such controlled approximations by using tree-grams as generative models. In particular, we show that hyperparameter transfer under $μ$P can be made more robust when narrower models are tuned on simpler data, generated by tree-grams with moderate $n$ and $d$. In addition, we show that entropy and effective range of correlations control performance gap after fine-tuning. This is because tree-grams allow us to explicitly control horizon and capacity. When allowed to route across candidate topologies, we observe emergent sparsity in tree-grams. Such concentrated routing permits pruning upto 95\% of topologies without significant change in performance.
Aritra Das, Debayan Gupta, Arup Mondal, Mihir More
原文摘要
We study interactive proofs for arithmetic circuits over the complex numbers $\mathbb{C}$ in which both the prover and the verifier compute approximately (unlike muggles, wizards can use magic, i.e., floating-point numbers). The goal is to prove that a claimed output $y$ is close to the exact output $C(x)$: for thresholds $0<Δ_0<Δ$, the honest prover is accepted whenever $|y-C(x)|\leΔ_0$, and every prover is rejected with high probability whenever $|y-C(x)|>Δ$. Existing proof systems for real-valued data verify rounded finite-field computations. Bitan et al.~[EUROCRYPT~2026] gave an approximate sum-check protocol. We extend the protocol of Goldwasser, Kalai, and Rothblum (GKR) [STOC~2008] to public-coin interactive proofs for logspace-uniform layered circuits over $\mathbb{C}$ of size $S$, depth $L$, and $n$ inputs, under public bounds on gate values and wiring coefficients. At constant soundness error, the verifier runs in time $(n+1)\mathrm{poly}(L,\log S,b)$, the communication is $\mathrm{poly}(L,\log S,b)$, and the prover runs in time $\mathrm{poly}(S,b)$, where $b$ is the bit precision. To the best of our knowledge, these are the first doubly efficient interactive proofs in which both parties compute approximately. GKR reduces two claims about a layer to one on a random line, which leaves the unit circle, where our error bounds hold. We instead label gates by complex roots of unity and combine the two claims with a random root of unity as coefficient. We choose the error thresholds backward from the input layer, so that a large output error survives the verifier's rounding at every step. The honest prover needs only $O(S \log S)$ complex operations. We also obtain zero-knowledge proofs from one-way functions, one-round arguments from private information retrieval, and interactive PCPs whose proof length is polynomial in the witness length.
The manifold hypothesis suggests that data lies on manifolds with smaller intrinsic dimension (ID) than their ambient dimension. However there is no empirical agreement on the estimates for ID from different estimators for realistic datasets. Thus it is important to test ID estimators (IDEs) with targeted stressors. In this work, we consider the role of anisotropy. To this end, we propose HomID, a collection of homogeneous spaces with anisotropic embedding, for benchmarking ID estimators. We observe that methods that perform well on standard benchmarks systematically degrade on HomID under identical resource allocation. We further observe that anisotropic distortion of such benchmarks also results in performance degradation. Finally, we demonstrate that controlled anisotropic distortions induce systematic shifts in the distributions on which these methods rely, providing a concrete mechanism for the resulting estimation errors in two particular IDEs. The code for the project is available at https://github.com/a-writes-code/homid
The rapid improvement of LLMs has made distinguishing AI-generated text from human writing a pressing problem. This challenge is further amplified by paraphrasing tools designed to make machine-generated text appear more ``human''. We study how access to human writing samples can be used to strategically paraphrase machine-generated responses toward the human distribution. Under a multi-sample setting with human and machine responses to the same prompts, we show that repeated paraphrasing moves the machine distribution toward a human target under mixing and stability conditions. We derive an explicit convergence rate, examine how semantic-preservation and quality constraints affect this rate, and extend the analysis to finite samples to characterize how the required human data and paraphrasing rounds scale with the desired error. We extend the analysis beyond the shared-parameter setting by learning a human-preserving rewriting kernel.
LLM agents are increasingly deployed in multi-agent systems, where they can collude while keeping their actions benign. Output monitors designed to detect such collusions can be fooled by obfuscation and steganography, motivating the use of probes trained on internal activations. However, these probes are usually evaluated on agents that do not know they are being watched. We study how activation-based detection changes when agents are explicitly informed that their internal activations are being monitored, and when they additionally receive feedback from the monitor. We keep the models, probes, and thresholds fixed and change only what the agents are told: nothing (baseline), that an activation monitor is present (aware), or that a monitor is present together with the previous round's score (feedback). We test two games, a four-agent blackjack game and a two-agent Simmons prisoners game, using Qwen3-32B-AWQ and GPT-OSS-20B in homogeneous and mixed pairings. Telling agents about the monitor does not hide them. The best probes stay accurate in all three conditions, and the agents keep colluding.