OpenAI's Claimed Refutation of ETH Sparks Debate, Meta Bets Big on AI Infrastructure

When AI Starts "Doing Science": A High-Stakes Bet on the Limits of Computation

This week, OpenAI announced three AI-assisted discoveries made together with academic collaborators, spanning mathematics, computer science, and physics. The most closely watched is a preprint in the computer science direction: the paper describes a deterministic algorithm that claims to exactly count the number of satisfying assignments for a certain class of KCNF formulas in sub-exponential time. If the result holds, it would directly challenge a cornerstone assumption in computational complexity theory—the Exponential Time Hypothesis (ETH).

ETH was proposed by Russell Impagliazzo and Ramamohan Paturi and conjectures that the 3SAT problem cannot be solved in sub-exponential time. This hypothesis has never been proven, but a large number of fine-grained complexity lower bounds are built on it. Precisely for this reason, any result claiming to overturn it would be regarded as one of the most surprising achievements in theoretical computer science in decades.

Cautious Excitement: Galactic Algorithms and the Gap from Reality

Community reaction has been enthusiastic but restrained. Among roughly 500 comments on Hacker News, many technical commenters pointed out that the algorithm's runtime is approximately 2^(n/√log n), a typical "galactic algorithm"—with enormous constant factors that make it unusable in practice. It neither solves the P vs NP problem nor implies that all NP problems have become sub-exponentially solvable, because the reduction process may cause instance sizes to balloon dramatically.

According to the discussion, verification work is being led by Impagliazzo, Paturi, Ryan Williams, and others, and Lean formalization is required. But independent review is still underway, and the physics-direction results have not yet been released. Some commenters praised OpenAI for bringing in mathematicians before publication this time, while others viewed it as PR positioning ahead of a potential IPO and expressed concern that the undisclosed physics research is being handled by a closed small circle.

KCNF formulas are a variant of Conjunctive Normal Form (CNF) with counting constraints, in which each clause carries an exact constraint on the number of true literals within it (for example, "exactly k literals are true"). The #SAT problem for standard CNF requires counting the number of assignments that satisfy all clauses and is #P-complete; because KCNF additionally introduces cardinality constraints, it is often used as a benchmark for studying the fine structure of counting complexity. The connection to 3SAT lies in the fact that if KCNF counting can be solved exactly in sub-exponential time, reductions can be used to attack the sub-exponential lower bound for 3SAT—this is precisely the mechanism by which the preprint threatens ETH.

The Exponential Time Hypothesis (ETH) was formally proposed by Impagliazzo and Paturi in 2001. Its core statement is that there exists a constant c>0 such that 3SAT cannot be solved in O(2^(cn)) time; an equivalent form is that 3SAT has no 2^o(n) algorithm. ETH is stronger than P≠NP, because even if P≠NP, 3SAT might still have sub-exponential but non-polynomial algorithms such as 2^(n^0.99). Based on ETH, researchers have established thousands of fine-grained lower bounds covering problems such as edit distance, orthogonal vectors, and dominating set, so refuting ETH would also undermine the conditional foundation of these results.

The term galactic algorithm was popularized by Ken Birman and others in discussions of distributed systems. It refers to an algorithm whose theoretical runtime is better than known methods but whose constant factors or lower-order terms are so large that it cannot actually run at any realistic input size. The usual criterion is the crossover point: if an algorithm is asymptotically better but would require n exceeding the number of atoms in the universe before it beats a simple method, it is a galactic algorithm. A bound like 2^(n/√log n) does have an asymptotic advantage over 2^n, but when n is on the order of hundreds, the former is still far beyond computable range, and polynomial factors and memory overhead in the implementation further widen the gap. This also explains why the community remains calm about its practical usability while acknowledging its theoretical significance.

Lean formalization refers to using the Lean 4 theorem prover and its mathematics library Mathlib to write the paper's algorithm correctness and complexity arguments as machine-checkable proofs. Compared with human review, formalization can eliminate subtle slip-ups, but for arguments in complexity theory that involve algorithms and asymptotic analysis, formalization is extremely costly and requires community consensus on the informal proof first. Requiring formalization in this context is a high-bar verification stance, not a step that can be completed immediately.

GPT-6.1 Tera: The Pricing and Positioning Dilemma of a Mid-Tier Model

OpenAI also released a mid-tier model, GPT-6.1 Tera (the source material also shows the spelling GPT-6.1 Terra), focused on visual reasoning, computer use, and clearer writing. Pricing is $1 per million input tokens and $5 per million output tokens, roughly half the price of the previous-generation GPT-5.6 Tera and the larger GPT-6.1 Sol.

OpenAI says that at medium reasoning effort, Tera scores 15 points higher than GPT-5.6 Tera on computer-use tasks at about one-third the cost; on the same tasks it can match the flagship GPT-6 Astra while costing only one-tenth as much per token. However, an OpenAI employee acknowledged on Hacker News that Tera lags behind Sol on most other tasks.

Developers welcomed its performance in cheap agent and automation scenarios, but the top-voted comment called it a "weird middle child"—on coding tasks, Sol is often more cost-effective. The most concentrated complaint is about the naming system: Luna, Tera, Sol, Astra, plus version numbers and reasoning-effort levels, make model selection extraordinarily difficult.

Cloudflare Incident Postmortem: Isolation Failure in a Shared Inference Stack

Cloudflare disclosed a cross-customer data leak: between August 27 and September 9, 155 responses from the GLM 5.3 model on its Workers AI platform contained data from other customers' recent requests. All affected requests had prompt lengths exceeding approximately 681,000 tokens.

Two problems combined to cause it. The first was a configuration error: the model claimed a context window of about 1.05 million tokens, but the KV cache pool on prefill nodes could hold only about 681,000 tokens, and Cloudflare knew about this mismatch before launch. The second was a defect in the open-source inference engine SGLang: in prefill-decode disaggregation mode, although overly long requests were marked as rejected, they still entered the cache transfer flow, causing decode nodes to continue generating on stale cache pages holding other people's data and to return a success status code. The fix is included in SGLang versions 0.521 and 0.522.

Cloudflare also admitted that pre-launch testing checked only status codes and performance and never verified whether the output content was correct—the most important warning for all inference service operators in this entire incident. Commenters generally praised its candor and rapid response, and pointed out that the problem had nothing to do with the GLM model itself but was an isolation and accounting failure in a shared service.

Prefill-decode disaggregation is a mainstream architecture for current large-model inference services: the prefill stage processes the entire prompt in parallel and computes the KV cache, while the decode stage generates tokens autoregressively one by one. The two have different compute and memory demands, and separate deployment can improve utilization and throughput. The KV cache stores the key-value vectors for each token in each layer's attention and is the main memory overhead of long-context inference; cache pages are usually reclaimed or reused after a request ends. When rejection logic and the cache transfer path are inconsistent, a request marked as overly long and rejected may still pass its cache pages to decode nodes. If the accounting system does not strictly bind pages to request ownership, decode nodes will continue generating on other people's data, creating a cross-request leak. Protection against such defects depends on request-level isolation, zeroing of cache pages, and validation of output content, not merely on status codes.

The Capital Angle: Meta's $95 Billion AI Financing

Meta announced plans to raise up to $95 billion through equity financing for AI infrastructure. The transaction began with a $35 billion underwritten offering, then was upsized and priced at $37.5 billion, after which a $60 billion at-the-market offering program could be launched as early as the first quarter of 2027. NVIDIA, AMD, and Broadcom have all expressed interest in purchasing up to $5 billion in total, but non-binding.

This would be Meta's first new stock issuance since 2013. Last quarter its capital expenditures were close to $35 billion, free cash flow was negative $2.1 billion, and full-year capex guidance is $135 billion to $145 billion. In other words, AI spending has exceeded Meta's own cash-generation capacity. Chipmakers buying their own customer's stock further tightens the circular financing chain in AI deals. After the announcement, Meta's stock fell about 1.6%.

Developer Ecosystem Briefs

A course on building a reasoning model from scratch. Sebastian Raschka released an 11-hour video course, including 8 coding videos, that implements reasoning techniques from scratch in PyTorch on a small pretrained Qwen3 model, as a companion to his book Build a Reasoning Model from Scratch. The content ranges from KV caching and a math answer verifier to inference-time scaling (self-consistency and self-refinement), then to reinforcement learning with verifiable rewards using GRPO, and finally distillation from DeepSeek^Ad R1 answers. Its value lies in compressing the modern reasoning technology stack to notebook scale.

The TypeServer protocol. Microsoft released version 0.4.1 of the TypeServer protocol, a JSON-RPC protocol that lets editors ask type servers about import resolution, search paths, and inferred types in code. The goal is to decouple Pylance's editor features from the underlying type checker, while also announcing that Meta's Pyrefly checker will be brought into Pylance. The 0.x version still allows breaking changes, and the community has debated whether the protocol name is too generic and whether a pure-Python protocol makes sense.

Other developments. Optical stocks rebounded on Monday, with Lumentum closing up about 8% after StoneX initiated coverage with a $1,200 target price and Coherent rising nearly 6%; Asian chip stocks followed on Tuesday, with South Korea's KOSPI rising more than 4% intraday and the Nikkei gaining nearly 2%. Simon Willison evaluated WebReframe—a tool that runs web pages in a hidden browser view from the command line—and concluded that it is not itself a sandbox and that only layering network isolation, temporary profiles, and timeouts can withstand its attack tests. Another blogger found that the 1993 version of FreeCell still runs as-is on Windows 11.

Editor's Observations

The main thread of the day is AI sliding from "assistive tool" toward "knowledge producer": on one side is a preprint that could rewrite complexity theory, and on the other is a model matrix whose pricing and positioning remain chaotic. The former requires patiently waiting for formalization and independent review, while the latter reminds us that beyond model capability, naming and cost structure are themselves part of the product experience. Cloudflare's postmortem offers the most practical lesson: launch checks for inference services cannot look only at status codes. And Meta's financing plan and chipmakers' subscription intentions push the AI capital cycle into a more conspicuous position.