Skip to content
Apart Research
Apart Research
Contact us
Sprint projectFeb 2, 2026Lausanne
2nd place

Markov Chain Lock Watermarking: Provably Secure Authentication for LLM Outputs

Chengheng Li Chen, Kyuhee Kim · Team MCL

Submitted to The Technical AI Governance Challenge. Sprint projects are early-stage work by participants, not Apart Research publications.

Read the report

Report: Markov Chain Lock Watermarking: Provably Secure Authentication for LLM Outputs

Open in a new tab (opens in new tab)
Code (opens in new tab)
Share

We present Markov Chain Lock (MCL) watermarking, a cryptographically secure framework for authenticating LLM outputs. MCL constrains token generation to follow a secret Markov chain over SHA-256 vocabulary partitions. Using doubly stochastic transition matrices, we prove four theoretical guarantees: (1) exponentially decaying false positive rates via Hoeffding bounds, (2) graceful degradation under adversarial modification with closed-form expected scores, (3) information-theoretic security without key access, and (4) bounded quality loss via KL divergence. Experiments on 173 Wikipedia prompts using Llama-3.2-3B demonstrate that the optimal 7-state soft cycle configuration achieves 100\% detection, 0\% FPR, and perplexity 4.20. Robustness testing confirms detection above 96\% even with 30\% word replacement. The framework enables $O(n)$ model-free detection, addressing EU AI Act Article 50 requirements. Code available at \url{https://github.com/ChenghengLi/MCLW}

Reviews

Judging this Sprint?

Review this project

Your public critique appears on this page without your name. Your private critique is not published; only the Apart team reads it. If you agree below, we share your review with grantmaking.ai (opens in new tab) and the Transformative AI Fund so strong projects can be funded.

Not shown on this page.

Shown on this page, without your name.

Only the Apart team reads this, and funders if you agree below.

Share my name publicly on grantmaking.ai *
Share my private critique with funders *

How much would this matter for AI safety if it worked? How innovative is it? For scores of 4-5: is this actually new to the field, or replicating recent work?

Scoring guide
  1. 1Negligible. No clear problem addressed, or no meaningful novelty.
  2. 2Limited. Addresses a real problem but with a generic or well-trodden approach. Incremental at best.
  3. 3Moderate. Clear problem with a reasonable approach; some novelty in framing or method beyond routine application of existing tools.
  4. 4Significant. Important problem with an original approach, or identifies a neglected problem area. A valuable contribution others could build on.
  5. 5Exceptional. Tackles a critical AI safety problem with a genuinely novel approach, or opens a new research direction. Clear theory of change. You'd be excited to share this with researchers in the area.

How sound are methodology, implementation, and findings?

Scoring guide
  1. 1Seriously flawed. Methodology broken, results uninterpretable, or implementation doesn't work.
  2. 2Weak. Approach has significant gaps: missing validation, flawed experimental design, or incomplete implementation.
  3. 3Competent. Technically solid given the short duration. Methodology makes sense, results are interpretable, limitations acknowledged, work builds toward clear conclusions.
  4. 4Strong. Thorough methodology with convincing validation. Results clearly support conclusions. Immediately useful for future work.
  5. 5Exceptional. Ambitious scope executed rigorously. Surprising findings, novel methods, or unusually robust validation.

How clearly are work, findings, and impact potential communicated?

Scoring guide
  1. 1Incomprehensible. Cannot determine what the project is actually claiming or doing.
  2. 2Hard to follow. Key information buried, missing, or diluted by excessive length. Significant effort to extract main points.
  3. 3Clear enough. Can understand the problem, approach, and results without undue effort. Core content clearly present: problem, method, findings, limitations.
  4. 4Well presented. Easy to follow, well-structured, appropriate level of detail. Target audience would get it quickly.
  5. 5Exceptionally clear. A pleasure to read. Complex ideas made accessible. Could serve as a model for how to present this type of work.

  1. Really nice idea, and impressive progress towards developing it in the timespan of a hackathon.

  2. When your theorems predict experimental results within 1-6% error, that's not a coincidence; that's a framework that actually works. The math seems to checks out and the experiments back it up across three different models.

    But the practical concerns are real. The detector needs to know which tokenizer generated the text. In a world where every model uses a different tokenizer, that's a deployment headache that the paper waves away. You'd need some kind of registry or metadata standard, and that's a whole separate problem.

    The overlap story is also worrying. At 0% overlap you get perfect detection. At 10% overlap, detection craters to 35%. There's no graceful middle ground. You're either getting full watermark strength with constrained vocabulary, or you're relaxing vocabulary and losing the watermark almost entirely. For production use, that cliff is a problem.

    And the robustness testing needs to be tougher. Replacing random words with "masked" isn't what a real adversary does. A real adversary paraphrases, back-translates, or runs the text through a second LLM. The 30% replacement survival rate is encouraging, but it's answering an easier question than the one that matters.

    The sparse watermarking idea they mention at the end (only watermark every N-th token) is where this probably needs to go for real-world use. That's worth a whole follow-up paper.

    Read full reviewShow less

Cite this project

@misc{chen2026markov,
  title = {{Markov Chain Lock Watermarking: Provably Secure Authentication for LLM Outputs}},
  author = {Chengheng Li Chen and Kyuhee Kim},
  year = {2026},
  month = feb,
  note = {Submitted to The Technical AI Governance Challenge, an Apart Research Sprint},
  howpublished = {\url{https://apartresearch.com/sprints/projects/markov-chain-lock-watermarking-provably-secure-authentication-for-llm-outputs-l8oe}},
  url = {https://apartresearch.com/sprints/projects/markov-chain-lock-watermarking-provably-secure-authentication-for-llm-outputs-l8oe}
}

More from The Technical AI Governance Challenge

All 47 entriesBrowse all projects

Build something like this at the next Sprint

AI Collusion Research Sprint · Oct 23 - 25, 2026