ResearchPapers, evidence & method
AI-assisted agent search helps resolve the 31-year-old KLS conjecture, leading Microsoft Research Focus #98
Microsoft Research Focus #98 highlights an AI-assisted resolution of the 31-year-old KLS conjecture in high-dimensional geometry. It also covers CompactionBench, a benchmark and background-summarization method for long coding-agent sessions, and a 104-language tokenizer built around word structure.
From the Microsoft Research article of November 12, 2026 and cited sources: Microsoft's Xinzhi Zhang and outside collaborator Zhao Song posted a dimension-free, constant bound for the KLS constant in early October. [3] [4] [5]
SOURCES[3] Unite.AI: Microsoft Researcher and Collaborator Prove… unite.ai[4] MSR blog: Solving a 31-year-old grand challenge in… microsoft.com[5] arXiv 2610.05474: Presenting a proof of the KLS conjecture arxiv.org
AT Pulse research deskPublished · Updated · 5 min read · AI-assisted analysisAI-assisted, not human-edited. Methodology Corrections Who owns this site
- What happened
- Microsoft's Xinzhi Zhang and outside collaborator Zhao Song posted a dimension-free, constant bound for the KLS constant in early October. [3] [4] [5]
- Original source
- Microsoft Research article, company source
- Brief by
- AT Pulse research desk AI-assisted; publisher and contact on the desk page
- When
- November 12, 2026 article published
- Covered
- Nov 13 edition
- Evidence
- 9 sources across 5 sites
- 1Microsoft Research Focus – Edition #98microsoft.com
- 2Linked video: Microsoft Research Focus – Edition #98youtube.com
- 3Unite.AI: Microsoft Researcher and Collaborator Prove…unite.ai
- 4MSR blog: Solving a 31-year-old grand challenge in…microsoft.com
- 5arXiv 2610.05474: Presenting a proof of the KLS conjecturearxiv.org
- 6arXiv 2610.12376: Latent Core Tokenizerarxiv.org
QuietHow it’s measured
YouTube video · 726 views · 5 likes
Reach blends public engagement (views, likes, comments, shares, stars) from the platforms where the story or its original source lives: YouTube, Hacker News, GitHub, Substack and similar. A video and the article written from its transcript share one score, taken from the video. Platforms with no data are left out rather than counted as zero, and the age of a story never lowers its score.
Microsoft's Xinzhi Zhang and outside collaborator Zhao Song posted a dimension-free, constant bound for the KLS constant in early October. They used agentic search with human-guided pruning across more than 100 candidate approaches, and humans set the direction and assembled the final argument. On the same day, Bizeul, Klartag and Lehec posted a separate proof built on the Song–Zhang criterion. A Lean 4 formalization was also released. [3] [4] [5]
Across 13.5M GitHub Copilot sessions, fewer than 8% triggered context compaction, yet those sessions accounted for about 44% of tokens. APEC writes indexed summaries in the background and appends them to a stable prefix. This keeps compaction off the critical path and preserves the prefix cache. The Microsoft authors report, from proprietary Copilot data, cost reductions of up to 25.4% and a 9.6% time saving. [7] [2]
The Latent Core Tokenizer first identifies reusable word parts using Minimum Description Length, entropy-based boundary signals and morphotactic rules, and only then fixes a 200K vocabulary. Across 104 languages, it gained roughly 1.5 to 2 downstream points over BPE, Unigram and parity-aware BPE while keeping efficiency comparable. [6] [2]
two separate KLS proofs plus a machine-checked formalization; compaction costs concentrated in a small tail of sessions.
Read the full assessment
Implication: human-directed agent search can contribute to frontier mathematics, and coding-agent operators may cut spend by targeting long sessions and prefix caching.
Executive brief
The biggest item in Microsoft Research Focus #98 is the resolution of the Kannan–Lovász–Simonovits (KLS) conjecture. This geometry problem had been open for 31 years, and AI agents helped solve it. Microsoft's Xinzhi Zhang and collaborator Zhao Song published the key criterion. A separate team used it to post a parallel proof on the same day.
Read the full section
The biggest item in Microsoft Research Focus #98 is the resolution of the Kannan–Lovász–Simonovits (KLS) conjecture. This geometry problem had been open for 31 years, and AI agents helped solve it. Microsoft's Xinzhi Zhang and collaborator Zhao Song published the key criterion. A separate team used it to post a parallel proof on the same day. The 5-minute episode, published 12 November 2026, also covers:
- CompactionBench, built on 13.5M GitHub Copilot sessions, plus a background-summarization method that reportedly cuts agent costs by up to 25.4%.
- A 104-language tokenizer that targets linguistic structure rather than compression alone.
- An intern profile and a podcast on speech translation.
What changed and event timeline
KLS bound reaches a constant
Song and Zhang's 140-page "An O(1) Bound for the KLS Constant" first appeared on 1 October with an iterated-log bound. The 4 October revision made the bound dimension-free (;).
Parallel proof posted
Bizeul, Klartag and Lehec posted a 32-page proof built on the "very recent criterion from Song and Zhang." It includes a paragraph disclosing AI use ().
Latent Core Tokenizer preprint
Ali, Ochieng, O'Neill, Paul and colleagues posted LCT, which is under review ().
Microsoft explains the KLS work
The blog describes "agentic search with iterative, human-assisted pruning" across more than 100 candidate approaches, along with a Lean 4 formalization ().
CompactionBench preprint
Liu, Qiu, Goiri, Bianchini, Choukse and colleagues released the paper on Preprints.org. It has not been peer reviewed ().
Capabilities and access
- The papers are on arXiv, and a Lean 4 formalization (KLS500, constant 500) has been released (Unite.AI).
- The preprint and BibTeX are available (MSR). The reviewed sources don't confirm a public code release.
- The paper is CC BY 4.0 and uses a 200K vocabulary (arXiv). The reviewed sources don't confirm a public tokenizer release.
Read the full section
- KLS proof. The papers are on arXiv, and a Lean 4 formalization (KLS500, constant 500) has been released (Unite.AI). The specific AI models and agent tooling are not named in the reviewed sources.
- CompactionBench and APEC. The preprint and BibTeX are available (MSR). The reviewed sources don't confirm a public code release.
- LCT. The paper is CC BY 4.0 and uses a 200K vocabulary (arXiv). The reviewed sources don't confirm a public tokenizer release.
Technical analysis for researchers and developers
- The new criterion uses high-order derivatives of tilt averages (arXiv 2610.05474).
- APEC writes indexed summaries in the background and appends them to a stable prefix.
- It first finds reusable word parts using Minimum Description Length, entropy-based boundary signals and morphotactic constraints, and only then builds a fixed vocabulary (arXiv).
Read the full section
- KLS. The new criterion uses high-order derivatives of tilt averages (arXiv 2610.05474). Microsoft describes the proof as applying this criterion recursively, with refinement inspired by linear-programming algorithms, and then showing the accumulated error stays bounded by a constant (MSR blog).
- APEC (Asynchronous Progressive Compaction). APEC writes indexed summaries in the background and appends them to a stable prefix. This takes compaction off the critical path and keeps the prefix cache usable. The benchmark models multi-turn software evolution and scores it with executable tasks (MSR).
- LCT. It first finds reusable word parts using Minimum Description Length, entropy-based boundary signals and morphotactic constraints, and only then builds a fixed vocabulary (arXiv).
Claims and evidence
- KLS is resolved. Two separate proofs exist, an alternative proof by Balasubramanian and Kasiviswanathan followed, and there is a Lean formalization (Unite.AI).
- 7.8% of sessions trigger compaction but account for 44.2% of tokens, from 760M LLM calls by 3.2M users (MSR). No independent replication was found.
- Downstream scores improve by 1.48, 1.83 and 2.00 points over BPE, Unigram and parity-aware BPE (arXiv). These are author-reported only.
Read the full section
- KLS is resolved. Two separate proofs exist, an alternative proof by Balasubramanian and Kasiviswanathan followed, and there is a Lean formalization (Unite.AI). Together these give strong support for the episode's statement that the result was "independently validated" (video 2:42).
- Compaction economics. 7.8% of sessions trigger compaction but account for 44.2% of tokens, from 760M LLM calls by 3.2M users (MSR). APEC cuts cost by up to 25.4% and time by 9.6% (video 3:46). Both findings come only from the authors and rely on proprietary Copilot data. No independent replication was found.
- LCT gains. Downstream scores improve by 1.48, 1.83 and 2.00 points over BPE, Unigram and parity-aware BPE (arXiv). These are author-reported only.
Context and prior work
- Before this work, the best bound was Letwin's July 2026 result of O(log^{1/4} n), which still grew with dimension (Unite.AI).
- A separate team from outside Microsoft released a similarly named benchmark, Compact-Bench, which measures how compaction affects long-horizon coding agents (arXiv 2610.31710).
- One commentator argues that compression efficiency does not equal multilingual quality (Ken Ashe).
Read the full section
- KLS. Before this work, the best bound was Letwin's July 2026 result of O(log^{1/4} n), which still grew with dimension (Unite.AI). KLS is closely linked to Bourgain's slicing problem and the variance conjecture (arXiv 2610.05474).
- Compaction. A separate team from outside Microsoft released a similarly named benchmark, Compact-Bench, which measures how compaction affects long-horizon coding agents (arXiv 2610.31710). Readers should not confuse the two.
- Tokenizers. One commentator argues that compression efficiency does not equal multilingual quality (Ken Ashe).
Limitations, safety and contested findings
- The episode presents it as Microsoft research. However, the parallel Bizeul–Klartag–Lehec proof and the role of outside collaborator Song make credit shared.
- APEC's 25.4% figure is a ceiling. It is an "up to" number from a preprint that has not been peer reviewed.
- LCT's improvements are a few points and come from a paper still under review.
Read the full section
- Credit for the KLS proof. The episode presents it as Microsoft research. However, the parallel Bizeul–Klartag–Lehec proof and the role of outside collaborator Song make credit shared. Microsoft says humans, not the AI, set the direction and assembled the final argument (MSR blog).
- APEC's 25.4% figure is a ceiling. It is an "up to" number from a preprint that has not been peer reviewed.
- Small tokenizer gains. LCT's improvements are a few points and come from a paper still under review.
Business and practitioner implications
- The cost of long sessions is concentrated in the tail: under 8% of sessions drive roughly 44% of token spend.
- Picking a tokenizer by compression ratio alone may shortchange languages with rich word structure (morphology).
- The KLS work is a credible example of human-directed agent search producing a major mathematical result, with Lean verification as the check that makes it trustworthy.
Read the full section
- Coding-agent operators. The cost of long sessions is concentrated in the tail: under 8% of sessions drive roughly 44% of token spend. To control cost, focus on compaction and keeping the prefix cache usable rather than on the average session.
- Multilingual products. Picking a tokenizer by compression ratio alone may shortchange languages with rich word structure (morphology).
- AI in research. The KLS work is a credible example of human-directed agent search producing a major mathematical result, with Lean verification as the check that makes it trustworthy.
The source trail.
Sources (9)
Microsoft Research Focus – Edition #98
Article text retrieved; extracted text may omit tables or interactive elements. A transcript of the video linked from this page is supplied (linked video manual captions; https://www.youtube.com/watch?v=Hcc6Ua7uTas); automatic text may contain errors.
microsoft.comLinked video: Microsoft Research Focus – Edition #98
linked video manual captions
www.youtube.com