DEV Community: Smit Sojitra

AI just cracked a 25-year-old conjecture. To get why, start with P vs NP.

Smit Sojitra — Sat, 31 Oct 2026 06:43:03 +0000

An AI model just disproved a hypothesis that complexity theorists had been building on since 1999.

On October 25, OpenAI posted a 67-page preprint titled "The Exponential Time Hypothesis is False", found by an internal model and partly checked in the Lean proof checker. Anthropic soon posted a refutation of its own. Lance Fortnow: "it is safe to assume now that the exponential-time hypothesis is toast."

Some coverage said P vs NP was about to fall, or encryption was about to break. To see what actually changed, start with P vs NP.

A puzzle that's quick to check and slow to solve

(a ∨ b ∨ c) ∧ (¬a ∨ d ∨ e) ∧ (¬c ∨ f ∨ g)

∨ is OR, ∧ is AND, ¬ is NOT. Set each letter true or false so every bracket has a true part. That's 3-SAT.

Checking an answer takes one pass. Finding one means searching 2ⁿ assignments: about a quadrillion at 50 variables. The best algorithm before October, PPSZ, gets that to about 1.307ⁿ. Faster, still exponential.

The full version has a live puzzle you can solve by hand before brute force grinds through it. Read more and try it here.

P is what we can solve fast. NP is what we can check fast.

"Fast" means polynomial time, steps growing like n² or n³. P is problems you can solve that fast: sorting, shortest paths. NP is problems where an answer can be checked that fast: 3-SAT, big Sudokus, exam scheduling.

Is everything easy to check also easy to solve? That's P vs NP, with a million-dollar prize since 2000. Most researchers think no. Nobody has proved it.

In 1971 Stephen Cook showed every NP problem translates into SAT in polynomial time. Problems everything in NP reduces to are NP-hard, and if they're in NP too, NP-complete. A fast algorithm for any one of them makes all of NP fast.

ETH: a bet on how hard 3-SAT really is

Between polynomial and exponential there's a middle zone, like 2^√n, called sub-exponential. In 1999 Russell Impagliazzo and Ramamohan Paturi bet 3-SAT can't get there: for some fixed δ > 0, it needs 2^(δn) time. That's ETH.

The logic runs one way. ETH true means P ≠ NP. ETH false says nothing about P = NP.

Lots of results said "no algorithm for X beats this, assuming ETH". Fortnow: "The fact that ETH and SETH fail doesn't mean their implications are false." They just need a new foundation.

What the AI actually proved

A deterministic algorithm that counts every satisfying assignment in:

(n+m)^O(1) · 2^( n / (log n)^(1/2 + o(1)) )

The exponent is n divided by about √log n, and that divisor keeps growing, so eventually this beats 2^(δn) for any δ. That's what ETH ruled out.

Watch the brackets. "2ⁿ divided by √log n" would barely beat brute force (about 2^998.6 at n = 1,000). The real bound puts the division inside the exponent: about 2^380.

Impagliazzo, Paturi and MIT's Ryan Williams are reviewing it. Fortnow notes the Lean proof gives "a slightly weaker bound". It isn't peer reviewed yet.

Sub-exponential doesn't mean fast

The paper hides its constants, and the new curve only beats PPSZ once √log n outgrows them.

My illustration: with C = 1 it wins from about 820 variables. With C = 6, you'd need more variables than atoms in the universe. It's a "galactic" algorithm, and nobody will ever run it.

Why it doesn't spread to every NP problem

Reductions to 3-SAT inflate the size. Turn n items into n² variables and the gain is gone.

The paper says the result "does not imply that general NP problems admit subexponential time algorithms". Fortnow: "It gives nothing new for Subset Sum or Traveling Salesman."

So is P = NP now? And encryption?

No. Sub-exponential time for all of NP would need 3-SAT in 2^(n^o(1)), and this is nowhere near. Williams still says people should "put a little more weight on the plausibility of P = NP, but one's weight may vary."

RSA rests on factoring, which isn't believed to be NP-complete and already has a sub-exponential algorithm, the number field sieve. Encoding it as SAT is the losing case above. Williams asked OpenAI whether it breaks any cryptosystem, and they said they're reasonably confident it doesn't.

What this can't tell you

Whether the proof holds. The review is ongoing.
How fast it really is. The constants aren't published.
Who found what first. Anthropic's Levent Alpöge suggested OpenAI built on existing work.

If someone pushes 3-SAT to 2^(n^o(1)), every NP problem goes sub-exponential and this gets much louder. Until then, one of the safest bets in computer science lost, and it lost to a machine.

The full version with five live demos
Why message 80 costs more than message 8
More posts: smiit.in/writing

Did you expect ETH to fall before P vs NP got any closer? Tell me in the comments.

Why Long AI Coding Sessions Get Expensive (Quadratic Attention Explained)

Smit Sojitra — Sat, 24 Oct 2026 04:37:00 +0000

Type "rename this variable" as the 8th message of a Claude Code session. Now type it again as the 80th. Same words, same answer, and with my sample numbers the second one costs about three times as much. Turn prompt caching off and it's six.

Nothing's broken. A long session walks into a quadratic curve twice: once inside the model, where every token looks at every earlier token, and once on your bill, where every turn ships the whole conversation again. Caching makes the repeat cheaper. It doesn't change the shape.

The model has no memory

Claude Code's docs put it bluntly: "The model doesn't remember anything between requests, so Claude Code re-sends the full context." And one message from you is rarely one request. Every tool call sends its result back as a new request carrying everything before it.

Everyone checks everyone, so the work is n²

Inside the model, each token gets a query (what it's looking for), a key (what it offers) and a value (what it hands over). A token compares its query with every key, softmax turns the scores into weights, and the output is the weighted mix of values:

Attention(Q, K, V) = softmax(Q·Kᵀ / √d_k) · V

Q·Kᵀ is every query against every key: n tokens, an n × n grid. Language models only look backwards, which trims the grid to a triangle of about n²/2 cells. That's still quadratic. Double the tokens, four times the work.

The full version has a live grid you can type into and double. Read more and try it here.

FlashAttention fixed the memory side by never storing the whole grid. It still computes every cell, so the time stays quadratic.

The KV cache helps, but not how you'd think

Replies come out one token at a time. The KV cache keeps the keys and values of old tokens in GPU memory so they aren't recomputed. Plenty of explainers say this makes generation linear. It doesn't. Each new token still does one dot product per earlier token, so a whole reply is still about n²/2. What the cache saves is the rerun, which would push the total toward cubic.

None of this shows up on your bill directly. Anthropic says a 900k-token request "is billed at the same per-token rate as a 9k-token request." So what makes the bill quadratic?

Your bill is quadratic for a dumber reason

Say a session starts with S tokens (system prompt, tools, CLAUDE.md) and each turn adds about a. Turn k sends roughly S + k·a, so K turns add up to about S·K + a·K²/2. The same triangle again: every turn is a row, and every row re-sends everything above it.

Prompt caching lowers the slope, not the shape

If the start of a request exactly matches something processed recently, the API skips the recompute and bills that part much cheaper. Anthropic doesn't say what it stores. Open-source servers like vLLM cache the KV blocks of earlier requests, so my guess is it's the same idea.

On Claude Sonnet 5.5, per million tokens: $2 input, $2.50 to write the 5-minute cache, $0.10 to read it, $10 output (Anthropic's pricing page, October 2026). A 20× discount on reads sounds like it solves everything, but the cached part is exactly the part that grows. You still re-read the whole history every turn, just cheaper, and a fraction of a quadratic is still a quadratic.

My sample session: Sonnet 5.5, a 20k-token start, 3k tokens added and 4 API requests per message. Message 8 costs about $0.05 and message 80 about $0.16. The whole 80 messages come to about $8.10, or about $112 with no caching. Cache reads are around two-thirds of the cached bill. That's the re-sending, on sale.

Watch the timer, too. Claude Code's docs say the cache lasts an hour on a subscription but five minutes on an API key or once you're on usage credits. Grab a coffee on an API key and your next message rewrites the whole context at the write price.

The full post has a simulator with sliders for all of this. Try it here.

What actually moves the curve

/clear resets the triangle. The system prompt and tools stay cached. Anthropic's docs: "/clear costs nothing."
/compact is a big request itself. It reads the whole conversation to write the summary, so it saves about what /clear does but pays for one large read first.
Long breaks hurt most late in a session. A 20-minute break before message 60 on the 5-minute cache takes that one message from about $0.13 to about $0.72.
Switching models throws the cache away. So does connecting an MCP server whose tools load up front.
Subagents get their own context. Their noisy output stays out of your main conversation, so it isn't re-sent on every later message.

What this can't tell you

It's a model with sample values, not your bill. Run /usage in Claude Code for your real numbers.
On Pro or Max you hit usage limits rather than a dollar figure, but the same curve decides how fast.
The attention maths is textbook, not Claude. Anthropic doesn't publish its architecture, so tricks like grouped KV heads change the constants, though not the n² shape of standard attention.

What I'd actually do

Treat a session like a branch, not a home. One task per session, /clear when the task changes. Keep CLAUDE.md short, since it rides along on every request. Pick the model at the start and leave it alone. On an API key, if you wander off mid-task, set promptCacheTtl to 1h or /compact before you go. None of that changes the shape. It just keeps you on the cheap end of it.

Your AI coding session gets pricier with every message, full version with live demos
More posts: smiit.in/writing

How long do your sessions usually run before you /clear? Tell me in the comments.

Your model doesn't need to write the answer. It needs to point at it.

Smit Sojitra — Thu, 15 Oct 2026 21:46:23 +0000

You gave the LLM the answer. So why is it writing it out from scratch?

Send a model a support ticket and four labels, and ask which one fits. It writes back {"label": "billing"}, one token at a time. The word "billing" was in your prompt the whole time.

Extraction is the same. The invoice number is in the PDF, and the model types it back to you. Usually it types it right.

Writing is a loop, and a writer can write anything

An LLM reads your prompt in one pass, then writes the answer one token at a time, each token another trip through the model. That's also why output costs more: on Anthropic's price list, Sonnet 5.5 is $2 per million input tokens and $10 per million output.

For a short label the cost isn't the real problem. The problem is that a writer can write anything: "Billing", "billing_dispute", "Sure! The label is billing." So you add a parser, a retry, a schema. JSON mode helps, but it's "a format constraint, not a correctness guarantee," as one guide puts it.

A pointer works differently. It reads the input once and scores what's already there: each of your labels, or each possible span of the document. The answer can only be something from the input.

This isn't new. Pointer Networks (2015) picked elements of the input as output. SQuAD (2016) defined every answer as "a segment of text from the corresponding reading passage." BERT answered it by scoring each token as a possible start or end of the answer. Named entity recognition still returns start and end offsets today.

What ScaleDown's CDMs are

ScaleDown launched four small task models on October 13 and calls them Constrained Decoding Models. Their partner post with LangChain sums up the idea: "a CDM is trained for one task and only returns answers that task allows, like a label from your list or spans of the input."

Going by ScaleDown's docs:

Classify scores your text against each label's rubric and returns top_label plus scores that sum to 1.0. It points.
Extract returns "the exact text span extracted from the input," with a confidence and start/end offsets. It points.
Summarize is "a fluent rewrite - not a selection of lifted sentences." It writes.
Compress shrinks long context. The docs don't say whether it selects or rewrites.

So the idea holds for two of the four. One naming note: "constrained decoding" usually means masking a normal LLM's tokens so it can't break your schema (Outlines, XGrammar). Here it's a product name.

The real win is the receipt

Speed is nice. The bigger deal is that a pointed answer comes with proof. If Extract says the invoice number sits at characters 8 to 17, you slice your own string and check. A written answer with two digits swapped looks exactly like a correct one.

Where they'd sit in an app

Not instead of your main LLM. Around it. Small models do the routine jobs and the general model does what actually needs writing.

The loop check comes from LangChain's example: stop the run when Classify scores "looping" above 0.8. That only works if 0.8 means something on your data. ScaleDown doesn't publish calibration numbers, and Classify "always returns a winner - even if the model is uncertain," so add an other label and measure on a few hundred of your own examples.

Jev, OpenAI and Cloudflare do half of this

TypeSafe's Jev, OpenAI's Decisions API and Cloudflare's Clef all answer typed questions with probabilities. That's the Classify half. None of them document pointing at spans.

What pointing can't do

The answer has to be in the input. "How many items on this invoice?" needs adding up. A pointer has nothing to point at.
A valid label isn't a correct one. It can point at the wrong thing.
Summarize writes, and Compress doesn't say. Don't assume the "can't invent text" property covers them.
The big numbers are ScaleDown's. The tweet says 200x faster and 467x cheaper. ScaleDown's own benchmark docs say 8 to 19.5% more accurate and 2.2x to 13.9x faster. Nobody independent has checked either yet.
Your text leaves your servers. It's a hosted API.

Want the deeper dive? Check out the detailed blog with interactive examples here: smiit.in/writing/answer-is-in-the-input

Which of your LLM calls are secretly multiple choice? Tell me in the comments.