About Me

I’m a fourth-year computer science PhD student in Northwestern University’s theory group. I’m very fortunate to be advised by Aravindan Vijayaraghavan. My research interests lie in theoretical computer science and the foundations of machine learning.

Before beginning my PhD studies at Northwestern University, I completed both my undergraduate and master’s degrees at the same institution. (Go Cats!)

Publications and Manuscripts

Publications

Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing Anxin Guo and Jingwei Li. ICML 2026 Spotlight · top 2.2% arXivVideofirst 10 min

We model the memorization of random, non-inferable facts as a membership testing problem, connecting Bloom-filter-style error metrics with the log-loss behavior of language models. In the sparse-fact regime, we prove a rate-distortion theorem showing that the optimal space-error tradeoff is governed by a KL-divergence frontier. The result gives an information-theoretic explanation for high-confidence hallucinations: in this regime under log-loss, the limiting space-optimal solution assigns the same confidence to all facts and a nonzero fraction of non-facts, rather than simply abstaining or forgetting.

Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals Anxin Guo and Aravindan Vijayaraghavan. COLT 2025 arXivVideo

We give the first polynomial-time statistical query (SQ) algorithm for agnostic PAC learning of an arbitrarily biased ReLU neuron under Gaussian marginals, achieving a constant-factor approximation with any desired additive tolerance. Large negative biases are challenging because the neuron activates only in the Gaussian tail, where adversarial noise can overwhelm the informative gradient signal or even drive gradient descent in the wrong direction. Complementing our algorithm, we prove a hardness separation between general SQ and correlational SQ (CSQ), formalizing this limitation of gradient-based methods.

To Store or Not to Store: A Graph-Theoretic Approach for Dataset Versioning Anxin Guo, Jingwei Li, Pattara Sukprasert, Samir Khuller, Amol Deshpande, and Koyel Mukherjee. IPDPS 2024 arXiv

We study a graph-theoretic framework for dataset versioning that optimizes storage costs while controlling retrieval costs across versions. On the theory side, we prove hardness-of-approximation results and give provably near-optimal algorithms for version graphs of bounded treewidth. On one real GitHub version graph, our dynamic programming heuristic achieved nearly three orders of magnitude lower total retrieval cost than the prior heuristic at comparable storage budgets.

Manuscripts

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries Aditya Bhaskara, Eric Evert, Anxin Guo, Tanmay Sinha, Vaidehi Srinivas, and Aravindan Vijayaraghavan. Corrected and revised version, 2026arXiv
Approximate Syzygies of Smoothed Polynomials and Applications Aditya Bhaskara, Anxin Guo, Tanmay Sinha, Vaidehi Srinivas, and Aravindan Vijayaraghavan. Manuscript PDF

A linear system can be sensitive to small errors when a combination of its columns almost cancels out. We study the same phenomenon for polynomials. After small random perturbations, we show that nearly canceling combinations are close to Koszul syzygies, simple exact cancellations that come from the fact that multiplication commutes. This answers an open question about efficiently decomposing a noisy sum of powers of polynomials in the smoothed setting [BHKX22]. We also establish robust uniqueness of symmetric third-order tensor decompositions at superlinear rank under small random perturbations, addressing an open question raised in [BCV14].

Learning Rules, Memorizing Facts: An Information-Theoretic View of Hallucination Gengze Xu, Anxin Guo, Yifei Hu, Xiangyu Wu, Yong Liu, and Ziqiao Wang. Preprint, 2026arXiv
How Much Do You Trust A Dog? Quantifying Hint-Following in Reasoning Language Models Anxin Guo, Chirag Pabbaraju, Sara Ahmadian, Kamesh Munagala, and Aravindan Vijayaraghavan. Preprint, 2026 arXiv

How much does an external hint sway a reasoning language model's prior judgment? On multiple-choice questions, we find that for a given source, a hint gives the suggested answer a roughly constant average boost in log-odds across a wide range of starting probabilities, as if it carried a fixed evidence weight. In our tests, the boost was not calibrated to the source's stated reliability, and explicit distrust warnings weakened it without eliminating it.

Regularized Transport Weights: a Principled Approach for Active Domain Adaptation Anxin Guo, Tanmay Sinha, Dionysis Arvanitakis, Vaidehi Srinivas, Alex Drlica-Wagner, Alexander Ji, and Aravindan Vijayaraghavan. Manuscript
Leanify: Verified Proof Compression and Reusable Lemma Discovery Ruize Xu, Anxin Guo, Yi Gu, Tianchong Jiang, Chenxiao Yang, Tianhao Wang, and Zhiyuan Li. Manuscript
Copying Under Repetition: From Prefix Matching to Position Hashing Anxin Guo, Tianlong Huang, Chenxiao Yang, and Zhiyuan Li. Preprint, 2026 arXiv

Language models that copy random text accurately can still stop too early or too late on a long run of identical characters. We prove a limit for a class of finite-precision transformers and construct a two-layer transformer that uses periodic position codes (with small prime periods) to copy any string up to a chosen length and stop exactly at the end. In synthetic copying experiments, baselines with standard positional encodings such as RoPE struggled on long repeated strings even within the training range, while our model trained on strings up to 2,000 tokens generalized to 5,000 tokens with near-perfect accuracy.

Selected Talks

Hallucination and Space-Optimality Oct 2026 Videofirst 10 min Sep 2026 Sep 2026
Intelligent Scheduling for Astronomical Surveys Sep 2026
Agnostically Learning Arbitrary ReLU Neurons Jun 2025 Feb 2025 Dec 2024

Education

Ph.D. student in Computer Science2023–present
B.A. in Math and M.S. in Computer Science2019–2023

Awards

Academic Activities

Research and Teaching

Service and Programs

Miscellaneous

I have written three articles on 知乎 about theoretical computer science. Here is the link.

More personal notes

I grew up in Beijing and still have a soft spot for its subway system and shared bicycles.