DEV Community: hidetzu

The Same Row Twice: Four Things Keyset Pagination Needs

hidetzu — Thu, 17 Sep 2026 12:47:40 +0000

Speed is OFFSET's second problem. The first is that page 2 can hand you a row you already read on page 1 — and no index will fix it, because it is not a performance bug.

Part 1 of this series measured why deep OFFSET is O(depth): at depth 9,999,980 PostgreSQL reads ten million rows and discards all but twenty. This is the other half — why you would switch even on a table small enough that nobody notices the speed, and the four things a keyset cursor needs before it works.

Page 2 shows you page 1's row

Ten rows, three per page, newest first.

CREATE TEMP TABLE feed(id int PRIMARY KEY, name text);
INSERT INTO feed SELECT n, 'item' || n FROM generate_series(1, 10) n;

SELECT id, name FROM feed ORDER BY id DESC LIMIT 3 OFFSET 0;

 id |  name
----+--------
 10 | item10
  9 | item9
  8 | item8

Now one row arrives before the user taps "next":

INSERT INTO feed VALUES (11, 'item11');

SELECT id, name FROM feed ORDER BY id DESC LIMIT 3 OFFSET 3;

 id | name
----+-------
  8 | item8
  7 | item7
  6 | item6

item8 came back. OFFSET 3 does not mean "after the three you saw" — it means "the 4th onward in the ordering as it stands now". One insert above the window shifted everything down by one.

Delete a row instead and the same arithmetic runs backwards: a row slides up past the boundary and is never shown at all. The user cannot reach it by paging.

A cursor asks a different question:

SELECT id, name FROM feed WHERE id < 8 ORDER BY id DESC LIMIT 3;

 id | name
----+-------
  7 | item7
  6 | item6
  5 | item5

Correct, because the cursor names a position (id = 8), not a rank ("the 4th"). Other people's inserts move ranks. They do not move positions.

This is the duplicated post in your infinite-scroll timeline. It is OFFSET's semantics, so it survives every index you add.

Where keyset still breaks

Keyset is not immune to everything, and it is worth being precise about what it fixes. It removes boundary drift caused by rows appearing or disappearing elsewhere in the set, because those rows change ranks and the cursor does not use ranks.

It does not help when the sort key of a row you already passed changes. Order a feed by updated_at DESC, let someone edit an old post, and that row jumps ahead of your cursor — you will see it a second time. Order by total_amount and let an amount change, and a row can move behind your cursor and never be returned.

The rule that falls out of this: order by something that does not move. created_at plus a primary key is a good default precisely because neither value is ever rewritten. If the product genuinely needs "most recently updated first", accept that pagination over it is approximate and say so, rather than pretending a cursor made it exact.

So: four things.

1. A tiebreaker, as a row comparison

A cursor on created_at alone breaks the moment two rows share a value. In my 10M-row table they do, by construction:

SELECT created_at, count(*) FROM orders
WHERE id BETWEEN 5000001 AND 5000100 GROUP BY created_at;

       created_at       | count
------------------------+-------
 2025-01-01 13:53:20+00 |   100

One hundred rows on the same timestamp. WHERE created_at < :cursor cannot express where inside those hundred the last page ended, so you get duplicates or gaps — the exact problem you switched to fix.

Add the primary key as a tiebreaker, and write it as a row comparison:

SELECT id, created_at
FROM orders
WHERE (created_at, id) < (:last_created_at, :last_id)
ORDER BY created_at DESC, id DESC
LIMIT 20;

(a, b) < (x, y) means "a < x, or a = x and b < y". Writing it that way is not cosmetic: PostgreSQL can push a row comparison into a composite index as a single Index Cond. Expand it into OR by hand and you can lose the index.

2. An index that satisfies the column order and the directions

CREATE INDEX orders_created_at_id_desc_idx
    ON orders (created_at DESC, id DESC);

With that in place, at the same depth that cost OFFSET 110,659 pages:

 Limit  (actual time=0.026..0.028 rows=20 loops=1)
   ->  Index Only Scan using orders_created_at_id_desc_idx on orders
         Index Cond: (ROW(created_at, id) < ROW('2025-01-01 13:53:20+00', 5000001))
         Heap Fetches: 0
         Buffers: shared read=4
 Execution Time: 0.062 ms

Four pages. 0.062 ms.

The common advice — "a DESC query needs a DESC index" — is not quite it. A B-tree walks backwards perfectly well, so flipping every column at once is free. Ask this DESC/DESC index for ORDER BY created_at ASC, id ASC:

 ->  Index Only Scan Backward using orders_created_at_id_desc_idx on orders
       (actual time=0.015..0.016 rows=20 loops=1)
 Execution Time: 0.030 ms

Backward, and no sort node.

What breaks is mixing directions between columns. ORDER BY created_at DESC, id ASC:

 ->  Incremental Sort  (actual time=0.088..0.089 rows=20 loops=1)
       Sort Key: created_at DESC, id
       ->  Index Only Scan using orders_created_at_id_desc_idx on orders
             (actual time=0.015..0.020 rows=101 loops=1)
 Execution Time: 0.105 ms

An Incremental Sort appears. Here it is cheap — only 101 rows, because ties run 100 deep — and it would be easy to look at 0.105 ms and move on.

For keyset, that timing badly understates the damage. The sort is the visible symptom; the real loss is that with directions mixed, (created_at, id) < (...) no longer collapses into a single Index Cond. The cursor predicate stops being something the index can seek on, which is the entire mechanism that made the query independent of depth. You are back to scanning and filtering — the shape of the problem part 1 was about, reintroduced by a sort clause that looked harmless.

The requirement is not "make it DESC". It is: a B-tree matching your column order and your direction pattern. Want mixed directions? That is a second index.

3. Cursors clients cannot read

Expose ?after_id=9999980 and within a week someone's client is doing +1 to get the next page. You can never change the sort order again.

Encode the whole cursor and make it opaque:

type cursor struct {
    CreatedAt time.Time `json:"c"`
    ID        int64     `json:"i"`
}

func encode(c cursor) (string, error) {
    b, err := json.Marshal(c)
    if err != nil {
        return "", err
    }
    return base64.RawURLEncoding.EncodeToString(b), nil
}

Base64 is encoding, not encryption — readable and forgeable. Add an HMAC if you need to reject tampering. Include which sort order issued the cursor, so switching order invalidates old ones instead of silently returning nonsense.

4. Total count is a separate problem

"Page 1 of 1,234" needs this, and keyset does nothing for it:

 Finalize Aggregate  (actual time=243.851..248.230 rows=1 loops=1)
   ->  Gather  (actual time=243.751..248.222 rows=3 loops=1)
         Workers Planned: 2
         ->  Partial Aggregate  (actual time=234.020..234.020 rows=1 loops=3)
               ->  Parallel Seq Scan on orders
                     (actual time=0.009..129.056 rows=3333333 loops=3)
 Execution Time: 259.813 ms

260 ms across three processes — a leader plus two workers (max_parallel_workers_per_gather is 2 by default; loops=3 is those three, not all 16 threads).

The fix is to want it less. Usually the UI only needs "is there more", which is LIMIT 21 and checking whether a 21st row came back — you discard the extra row and report its existence as a boolean.

That falls out of the response shape a cursor API wants anyway:

{
  "items": [ "...20 rows..." ],
  "next_cursor": "eyJjIjoiMjAyNS0wMS0wMVQxMzo1MzoyMFoiLCJpIjo1MDAwMDAxfQ",
  "has_more": true
}

No total, no page number, and next_cursor is null on the last page. If an estimate is good enough for a "roughly N results" label, pg_class.reltuples is free.

Which one to use

OFFSET is not a mistake. It has a domain.

	OFFSET	Cursor (keyset)
Deep pages	O(depth)	Flat
Jump to page N	Yes	No — next/prev only
Total pages	Yes (count costs extra)	Usually not offered
Concurrent writes	Duplicates and gaps	Robust to inserts/deletes elsewhere
Build cost	Nothing	Tiebreaker, index, encoding
Switchable sort order	Free	An index and cursor format per order

Stay on OFFSET when the result set tops out in the thousands, when page numbers go in URLs to be bookmarked and shared, when jumping to an arbitrary page is a real requirement, or when the data is frozen while being read (a closed report).

Use a cursor for infinite scroll, timelines and notification feeds; for exports and batch reads; for public APIs where you do not control how deep clients go; and for anything on a table that is being written to continuously.

They also coexist. Page-numbered admin screens on OFFSET and a cursor-based public API is a normal split. Just cap the depth on the OFFSET side — an endpoint that accepts offset=9999980 from anyone is a free denial-of-service handle, as part 1's 110,659 pages per request should make obvious.

Takeaway

Switch off OFFSET when rows shift under your users, not when the page feels slow — and budget for a tiebreaker, an index per sort order, an opaque cursor, and a separate answer for "how many".

OFFSET Doesn't Skip Rows: What 10M Rows in PostgreSQL Actually Cost

hidetzu — Tue, 15 Sep 2026 22:46:12 +0000

OFFSET 9999980 LIMIT 20 does not skip 9,999,980 rows. It reads every one of them, builds each tuple, and throws it away. To hand back 20 rows it touches 110,659 buffer pages — 865 MB of a 1.2 GB table — and EXPLAIN reports it without flinching.

I knew deep pages were slow. Asked to explain why, I said "it skips ahead, and skipping that far costs something" — which is wrong in the one way that matters. Nothing jumps. So I loaded 10 million rows into PostgreSQL and measured it.

The setup

PostgreSQL 17.11 (postgres:17-alpine), Docker 29.4.1, Ryzen 7 5700X, 78 GB RAM, shared_buffers left at the default 128 MB.

CREATE TABLE orders (
    id           bigint       PRIMARY KEY,
    created_at   timestamptz  NOT NULL,
    customer_id  bigint       NOT NULL,
    status       varchar(16)  NOT NULL,
    total_amount integer      NOT NULL
);

CREATE INDEX orders_created_at_id_desc_idx
    ON orders (created_at DESC, id DESC);

Ten million generated rows, with one deliberate property: created_at repeats every 100 rows. Real order tables have ties within the same second, and that matters in part 2.

Keep these physical sizes in mind — the Buffers numbers later resolve straight back into them at 8 KB per page:

Object	Size	Pages
`orders` heap	651 MB	~83,000
`orders_pkey`	214 MB	~27,000
`orders_created_at_id_desc_idx`	301 MB	~38,000

Every query below returns exactly 20 rows and selects only id, created_at. Otherwise you cannot tell which difference came from the pagination method.

The shape of the numbers

Five runs each, same session, no EXPLAIN attached:

Depth	OFFSET	Cursor
0	0.292 ms	0.130 ms
99,980	7.009 ms	0.027 ms
999,980	68.370 ms	0.020 ms
4,999,980	396.669 ms	0.021 ms
9,999,980	791.349 ms	0.016 ms

The ratio at the bottom row is about 49,000x, and it is the least interesting number here. Look at the shape of each column instead. Ten times the depth, ten times the time — OFFSET is cleanly linear. The cursor column does not move at all across a 100,000x change in depth.

This is not a constant factor. It is a different complexity class.

Note: The cursor timings sit at 0.016–0.027 ms, close to measurement resolution. Do not read the 49,000x as precise. The claim is that the column is flat.

EXPLAIN says it out loud

The plain OFFSET at depth 9,999,980:

 Limit  (cost=343020.75..343021.43 rows=20 width=16)
        (actual time=1171.800..1171.803 rows=20 loops=1)
   Buffers: shared read=110659
   ->  Index Scan using orders_pkey on orders
        (actual time=0.027..934.060 rows=10000000 loops=1)
         Buffers: shared read=110659
 Execution Time: 1172.019 ms

Three things to read.

The Limit node returns 20 rows. Its child returns 10,000,000. That gap is the whole story. Index Scan produced ten million rows; Limit discarded 9,999,980 of them and passed 20 up. Read, then discarded — not skipped.

Buffers scales with depth, not with the result size:

Depth	Index Scan rows	Buffers
0	20	4
99,980	100,000	1,110
999,980	1,000,000	11,069
4,999,980	5,000,000	55,331
9,999,980	10,000,000	110,659

Now put 110,659 next to the table above. The primary key index is ~27,000 pages and the heap is ~83,000. They sum to ~110,000. The query walked the entire index and the entire heap to return a few hundred bytes.

Most of the time is the discarding. Index Scan alone is 934 ms of the 1,172 ms total.

Note: The average table said 791 ms for this query; this plan says 1,172 ms. Different instruments. The table is five bare runs; this is one run under EXPLAIN (ANALYZE, BUFFERS), which timestamps every node and charges more the more rows pass through. Compare absolute numbers within the table, and structure within the plans. Every comparison below is plan-to-plan.

Why it can only count

An index maps key to location. "Where is id = 9999980" takes a handful of node lookups from the root. OFFSET asks something else:

Which row is the 9,999,981st when sorted?

A PostgreSQL B-tree cannot answer that, because rank is not stored anywhere in it.

Every node knows which key ranges lie beneath it. None of them knows how many entries do. If they did, you could descend by rank — "the left subtree holds 5 million, so go right" — and deep OFFSET would cost the same as a cursor. Such structures exist; order-statistic trees and ranked B-trees are exactly this. PostgreSQL's B-tree is not one.

The leaves are chained together in key order, so walking the whole set is easy. Walking is the only thing on offer.

And there is a second layer. MVCC visibility is not in the index. Whether an index entry is visible to your transaction generally requires checking the heap (the visibility map can skip this when a page is known all-visible). So OFFSET does not want the Nth entry. It wants the Nth row currently visible to you. Even a subtree counter would count entries, not visible rows.

That leaves exactly one strategy: walk from the start and count.

OFFSET's cost is not a missing optimisation. It falls straight out of a structure that does not store rank.

Making the discarding cheaper

Discarding has internals worth separating. The scan above also returns created_at, which is not in the primary key index — so each of the ten million discarded rows triggers a heap visit. That part is pure waste.

Skip on id alone, then fetch the heap for the surviving 20. This is the deferred join:

SELECT o.id, o.created_at
FROM orders o
JOIN (
    SELECT id FROM orders ORDER BY id LIMIT 20 OFFSET 9999980
) t USING (id);

 Nested Loop  (actual time=799.685..799.704 rows=20 loops=1)
   Buffers: shared hit=82 read=27326
   ->  Limit  (actual time=799.620..799.623 rows=20 loops=1)
         ->  Index Only Scan using orders_pkey on orders
               (actual time=0.023..561.950 rows=10000000 loops=1)
               Heap Fetches: 0
 Execution Time: 800.047 ms

Heap Fetches: 0, and buffers drop to 27,408 — almost exactly the ~27,000-page primary key index and nothing else. The heap is gone from the scan entirely.

Plan-to-plan	Plain OFFSET	Deferred join	Change
Buffers	110,659	27,408	1/4
Execution time	1,172 ms	800 ms	2/3

Here is the part I did not expect. Pages fell to a quarter; time only fell to two thirds. Cutting I/O did not cut time proportionally, which means the dominant cost was never the pages. The Index Only Scan alone spends 562 ms walking 10 million entries: about 56 ns per row, just to produce a tuple and drop it.

And rows=10000000 is unchanged. The constant improved. The order is still O(depth).

It is not the disk

Buffers: shared read only means "not in PostgreSQL's shared buffers." Whether it reached the physical device or came from the OS page cache is a separate question — and a measurable one:

SET track_io_timing = on;

 Limit  (actual time=1176.118..1176.121 rows=20 loops=1)
   Buffers: shared read=110659
   I/O Timings: shared read=133.496
 Execution Time: 1176.317 ms

110,659 pages cost 133 ms of I/O — 11% of the runtime, about 1.2 µs per page. With 1.2 GB of data on a host with 78 GB of RAM, those reads were almost certainly served by the OS page cache.

The other ~1,040 ms is not time PostgreSQL attributed to reading anything. It is scanning ten million index entries, forming tuples, and discarding them.

So "OFFSET is slow because disks are slow" does not survive contact with the measurement. Faster storage buys back roughly a tenth of it. The O(depth) term is CPU work, and it stays.

Takeaway

OFFSET is not skipping. It is reading and discarding, because nothing in a B-tree can answer "which row is Nth right now" — and a cursor is fast not because it is cleverer, but because it replaces that question with "which rows come after this key," which an index can answer.

Part 2 is the other half: the reason to switch is usually not speed at all, and the four things keyset pagination needs before it works.

The Tests Passed. The Function Already Existed.

hidetzu — Tue, 15 Sep 2026 22:12:03 +0000

Both models passed the tests. Both rewrote a function that was sitting in their own prompt, twenty lines up.

That is a worked example from the RepoExec paper, and it is the reason the benchmark exists. pass@k cannot see it — the tests are green. The bill arrives six months later, when you change the function that was supposed to be the only implementation and the change does not take everywhere.

RepoExec (NAACL 2025 Findings, Nam Le Hai, Dung Manh Nguyen, Nghi D. Q. Bui, FPT Software AI Center) adds a second axis next to correctness: of the dependencies you handed the model, how many did it actually call. Across 18 models the best pass@1 is 42.57%.

Two axes, not one

The second axis is the new one. Dependency Invocation Rate (DIR) is the share of provided dependencies that appear in the generated code. With Dg the set of identifiers in the output and Ds the set of dependencies extracted from the reference solution:

DIR = |Dg ∩ Ds| / |Ds|

Match-based metrics like BLEU weigh every token the same, so a valid alternative implementation scores badly for no good reason. DIR only looks at the identifiers that name dependencies. Calling _create_future() instead of Future() is not a stylistic variant — it is the choice the author of the repository already made.

The benchmark is 355 Python problems, each with an executable environment. Tests are LLM-generated, then filtered for syntax and execution and pushed for coverage: 99.45 test cases and 96.25% line coverage per problem on average. Prompts are short — 362.92 tokens on average with full dependency bodies, 253.05 with bodies stripped. 22.8% involve a cross-file dependency.

The coverage push is worth noting on its own. Strengthening the tests dropped pass@1 by over 5 points. Solutions that had been scoring as correct started failing, and the paper's diagnosis is that most of them had ignored the supplied context entirely and solved the natural-language description instead. They failed at the edges — which is exactly where the repository's own validation helpers live.

Nobody is close

Full context, ordered by pass@1:

Model	pass@1	DIR
DeepSeek-R1	42.57	70.86
DeepSeek-V3	42.00	80.35
CodeLlama-34b-Python	40.93	68.85
CodeLlama-13b-Python	38.65	62.26
GPT-4o	37.14	81.43
GPT-4o-mini	30.29	74.75
GPT-3.5	27.27	63.59

Every model is under 50% pass@1 on 355 problems with a single level of dependencies supplied.

Look at GPT-4o-mini. DIR 74.75, pass@1 30.29. It reaches for the dependencies and gets the call wrong. DIR counts whether a name appeared, not whether it was used correctly, which is precisely why the paper insists on reading both numbers together. Cross them and you get four quadrants:

	Low DIR — ignores the deps	High DIR — uses the deps
High pass@1	Works, but reimplements — debt	The target
Low pass@1	Just broken	Over-built, over-complicated

The paper's finding is that the two model families fail on opposite diagonals. Pretrained models land top-left: correct code that quietly rewrites what was already there. Instruction-tuned models land bottom-right: they find the dependency, then wrap it in machinery nobody asked for.

Half the context was worse than none

Dependencies are supplied at three levels. Full is signature + docstring + body; Medium is signature + docstring; Small is signature only. Information content runs Full > Medium > Small. Performance does not (BasePrompt, pass@1):

Model	Full	Medium	Small
CodeLlama-13b-Python	38.65	32.96	35.66
StarCoder	28.08	22.54	25.54
StarCoder2-15b	27.77	18.70	23.27
Phi-2	19.04	14.54	14.82

Full > Small > Medium, every time. Trimming halfway is worse than trimming all the way.

The explanation is the good part. A Medium-context dependency — signature, docstring, no body — has exactly the same shape as the target function's prompt. So the model reads the context as a run of few-shot examples with the last one blank, and treats the job as filling in the blank. The evidence is empty output: with Medium context, over 31% of StarCoder2's generations are empty function bodies. It did not lack information. It misread what the information was for.

That kills the "more context vs. less context" framing outright. What moved the numbers was not volume but what the supplied text looks like it is asking for.

The example

The Tornado case. maybe_future converts a value into a Future. The prompt supplies _create_future(), which builds a Future and then strips the extra asyncio debug stack entries the wrapper itself introduced.

The reference solution:

def maybe_future(x: Any) -> Future:
    if is_future(x):
        return x
    else:
        fut = _create_future()
        fut.set_result(x)
        return fut

The pretrained model — tests pass:

def maybe_future(x: Any) -> Future:
    if is_future(x):
        return x
    future = Future()          # builds it by hand, skipping _create_future()
    future.set_result(x)
    return future

The instruction-tuned model — tests also pass:

def maybe_future(x: Any) -> Future:
    if isinstance(x, Future):   # is_future() is right there
        return x
    elif isawaitable(x):        # a branch the spec never asked for
        return asyncio.ensure_future(x)
    else:
        future = Future()
        future.set_result(x)
        return future

Neither calls _create_future(). The entire reason that function exists — the debug-info cleanup — is gone from both. The paper calls this a failure to optimise memory use and flags it as code smell and technical debt.

And no test catches it. Only DIR reports that _create_future was never invoked.

Two things that helped

Show it the errors. Feed back the failing test output, up to three rounds:

Round	GPT-3.5	WizardCoder	CodeLlama-13b-Python
0	27.04	34.37	39.44
1	36.34	40.85	39.44
2	40.00	41.69	39.44
3	41.97	42.54	39.44

GPT-3.5 gains nearly 15 points, and DIR rises by over 7 points as well — debugging improves dependency use, not just correctness. CodeLlama-13b-Python does not move a single digit across three rounds. Whether an error log is worth sending back is a per-model fact, which matters if you are wiring an agent loop.

Fine-tune on dependency-annotated data. The authors built a set from 1,555 repositories and 154,818 functions and LoRA-tuned on it (DepIT):

Model	Full pass@1	Full DIR	Small pass@1	Small DIR
Phi-2	19.04	48.22	14.82	44.54
Phi-2 + DepIT	20.20	61.66	20.31	70.30
StarCoder2	27.77	60.57	23.27	53.49
StarCoder2 + DepIT	28.45	69.76	27.27	73.98

pass@1 barely moves. DIR jumps 10-25 points. Using what is already there is a separable, learnable skill.

The part I keep thinking about: after tuning, Small context catches up with Full. Phi-2 scores higher on both metrics with signatures alone. That is two models, not a general law — but it says a signature and a good name can be enough to get a dependency called, without shipping its body.

Where this stops

One level of dependencies. The paper lists this first in its own limitations: only what the target function calls directly, no transitive graph. Input-length budget. Real comprehension goes deeper.
Python, 355 problems, one function at a time. Not multi-file changes.
Tests are LLM-generated. High coverage, but not human-annotated.
DIR only counts invocation. Whether the call was correct needs pass@1 alongside it, and calling a dependency that should not have been called is not measured at all.
Early-2025 models. These are DeepSeek-R1 and GPT-4o-era numbers. Do not carry 42.57% forward to whatever you are using today.
Context length barely correlates with score. Model size and family dominate. With 363-token prompts there is no haystack to search — the dependency extractor already did the selecting. Being able to hold a long context and being able to pick the right one are different jobs, and only the first belongs to the model.

What I'd change in a repo

Two things follow for me, and neither is exotic.

Invest in the public face — names, signatures, docstrings written from the caller's side. That has always been called good design; DIR just converts "readable" into "how often an LLM reuses this", which is a number you can move. For a function that breaks something when it is skipped, put the reason in the docstring: not "checks for a string" but "all str checks go through this so validation stays in one place."

And stop treating a green test run as a review signal for generated code. Two of the paper's three worked examples reimplement a supplied dependency while passing. The question worth asking of a diff is which existing function it should have called — which is a static-analysis job, not a human one. pydepcall, the extractor the authors released, walks dependencies up to 100 levels deep, so the raw material is there. I have not built this yet.

Takeaway

Measure whether generated code calls what your repository already has, separately from whether it passes. They are different abilities, and the second one hides the first.

Nam Le Hai, Dung Manh Nguyen, Nghi D. Q. Bui. "On the Impacts of Contexts on Repository-Level Code Generation." Findings of the ACL: NAACL 2025, pages 1496-1524. Dataset and code: https://github.com/FSoft-AI4Code/RepoExec

99.7% Rejected in 84ms: Why I Stopped Making the Generator Smarter

hidetzu — Sun, 06 Sep 2026 03:34:11 +0000

I wrote a puzzle generator whose acceptance rate is 0.26%. It throws away 99.7% of everything it produces, and that is the design working as intended, not failing. Generating five valid puzzles takes 1,947 attempts and 84 milliseconds.

The point is not the puzzles. The point is that the generator makes no correctness guarantee at all, and a verifier makes every one of them. Once you split those two responsibilities, "make the generator smarter" stops being the obvious optimisation — and that is exactly the position you are in when the generator is an LLM.

The loop

verigen is a Go CLI that produces cryptarithmetic puzzles — alphametics, the SEND + MORE = MONEY genre, where each letter stands for a distinct digit and the sum has to hold. The known answer to that one is 9567 + 1085 = 10652.

There is one rule, and everything else follows from it:

The generator guarantees nothing. Every guarantee lives in the verifier.

The generator throws plausible-looking letter combinations at the wall. The verifier does an exhaustive search and confirms two things: that a solution exists, and that it is unique. Anything that fails either check is discarded and the loop asks for another candidate.

The loop itself knows nothing about cryptarithmetic. Implement a Domain interface and any other puzzle rides the same loop.

What the log actually says

Five puzzles, seed 7:

── Puzzle 2  [hard]
   HAIKU + BONSAI = KOKORO
   Answer: 96542 + 378165 = 474707
   (attempts before this seed landed: 624)

=== generate/verify loop [alphametic] ===
seed=7  output=5 puzzles  total attempts=1947  elapsed=84ms
acceptance rate = 0.2568%  (average 389 generations per puzzle)
--- rejection reasons ---
  no unique solution                  770  (39.55%)
  no solution                         695  (35.70%)
  more than 10 distinct letters       477  (24.50%)
  ok                                    5  ( 0.26%)

Nearly 40% of candidates have more than one valid solution. Another 36% have none. A quarter cannot possibly have one and are rejected before the search starts. Five survive.

Filtering by difficulty makes it worse: asking for easy puzzles drops the acceptance rate to 0.03%, about 3,200 generations each. It still finishes instantly.

I never tried to raise that number. Making the generator cleverer costs my time; making the verifier run 1,947 times costs 84ms. When generation is cheap, you can afford to be stupid on that side and pay for it in verification. The log is what makes that trade-off intuitive rather than theoretical — I did not really believe it until I saw 99.7% of the work land in the discard pile without the wall-clock time moving.

What the verifier has to guarantee

The loop is only worth as much as the assertions the verifier can actually make. For alphametics, that is:

Guarantee	How
A solution exists	Exhaustive search, column by column, carrying digits
The solution is unique	Keep searching after the first hit; reject if a second exists
More than 10 distinct letters means no solution	Pigeonhole. Rejected before the search runs
No leading zero	Constrain the first letter of every multi-character word

Three design decisions made that table hold up.

I tested the verifier first. If the verifier is wrong, every guarantee downstream is a lie, and nothing in the output looks wrong. So the first tests were puzzles with published answers — SEND + MORE = MONEY → 9567 + 1085 = 10652, CROSS + ROADS = DANGER → 96233 + 62513 = 158746 — plus explicit cases for "no solution", "not unique", and the 11-letter rejection. The generator's tests came later. A broken generator lowers the acceptance rate; a broken verifier invalidates everything.

Pre-filtering only encodes facts, never heuristics. More than ten distinct letters cannot map to ten digits, so no solution exists — pigeonhole, not a guess. That check alone accounts for 24.5% of rejections and removes the most expensive searches before they begin. Note where the optimisation went: not into a smarter generator, but into the verifier's front door, rejecting hopeless candidates fast.

Difficulty is labelled a proxy, out loud. The difficulty score counts branch points during the search. That correlates with how much trial and error a human needs, probably — but I have not measured it against actual people, so the code and the docs both call it a proxy. Separating what you can assert from what you merely believe is not a nicety here. It is the discipline that keeps the word "verified" meaningful everywhere else.

Where this already is, and where it isn't

Swap the random generator for an LLM and the diagram is unchanged. That substitution is not a new idea in 2026 — in the major application areas it is already standard practice.

Code generation. Formalised as loop engineering: hooks and agent harnesses that refuse to let a run finish until tests, types and lint pass. Cognition's 2025 annual review put the merge rate of Devin-generated PRs at 67%, up from 34% the year before — while noting that roughly a third of those PRs still need substantial rework. Passing the verifier is the floor, not the goal.

SQL generation. Snowflake's Cortex Analyst moved automatic optimisation of verified queries into preview in December 2025. Vanna AI ships self-correction from dry-run errors as a standard feature. EXPLAIN, schema matching, and retry-on-execution-error are table stakes for text-to-SQL products.

Structured output. This one has gone past verification entirely: XGrammar constrains decoding so schema-violating tokens are never emitted, and it is now a standard backend in vLLM, SGLang and TensorRT. OpenAI's Structured Outputs works the same way. "Parse the JSON, catch the error, retry" is close to obsolete.

Proofs. The most spectacular case, and the most instructive, because this is where the pattern was tested against its own alternative.

AlphaProof, paired with AlphaGeometry 2, scored 28/42 at the 2024 IMO — silver-medal level, one point under the gold threshold. The mechanism is continuous with verigen: generate candidate proofs, run them through Lean 4 as a mechanical verifier, repeat until one passes, at enormous scale. DeepSeek-Prover-V2 is the same shape. What exhaustive search does for "this puzzle has exactly one solution", Lean does for "this theorem holds".

Then the following year, the verifier came out. Gemini Deep Think took gold at the 2025 IMO — 35/42, five of six problems — reasoning end-to-end in natural language, inside the human time limit, with no formal proof assistant anywhere in the loop, at roughly two orders of magnitude better inference efficiency than the 2024 approach. On the face of it that is a counterexample to everything I have argued.

Look at what each one was solving. An olympiad problem is an exam question: a solution is known to exist, the search space is bounded by the syllabus, and a human grader decides at the end. Deep Think did not need a mechanical verifier because a mechanical verifier was never the binding constraint there. Now compare AlphaProof Nexus, which in May 2026 reported solving 9 of 353 open Erdős problems and 44 of 492 open OEIS conjectures (arXiv:2605.22763) — including two open for 56 years. Nobody can grade that output. There is no answer key, and no human referee who can check the volume of candidates the system produces. Lean is not decoration in that setting; it is the only thing standing between "solved" and "claimed".

So the split is not verifier versus no verifier. It is whether anything else can decide the question. Where a competent grader exists, a strict verifier is an optimisation you may be able to skip. Where none exists, it is the entire basis on which you are allowed to use the word "solved".

The common precondition is that the verifier can decide the question mechanically. Where it cannot — is this prose any good? — the whole design has nothing to offer.

What is still open is the design of the verifiers themselves.

Round-trip verification. Transform the output back and check that it matches the input. Schema validation is everywhere; round-trip verification of semantic equivalence is not, and ETL and code migration between languages or frameworks are where it would pay.

A uniqueness-equivalent guarantee. My verifier does not stop at "a solution exists"; it asserts the solution is unique. The LLM equivalent is not stopping at "the code runs" but checking that behaviour is uniquely determined by the spec — property-based testing that finds no counterexample gets close.

A quality filter. verigen cannot reject a puzzle that is solvable but boring, and nothing in the LLM stack reliably rejects code that passes its tests but is badly designed. The metric itself is the unsolved part.

When this works

Three conditions, in order of how often they are the one that breaks:

The verifier must be strict — and honest about its limits. A verifier that appears to guarantee something it does not makes the entire loop a lie. Assert nothing you cannot assert. Labelling my difficulty score a proxy is the small version of this; treating "the tests pass" as "the code is correct" is the expensive version.

Generation must be cheap. 1,947 attempts in 84ms is why a 0.26% acceptance rate is survivable. An LLM call is hundreds of milliseconds to seconds, so the same acceptance rate would be absurd. With an expensive generator you have to tune both sides: prompts that raise the hit rate and a verifier strict enough to be worth the round trip.

Verification must not cost more than generation. Exhaustive search is expensive in principle and still fits inside those 84ms. Test suites and type checks do not always fit so comfortably. If verifying costs more than generating, the loop does not close.

What I'd build next

Classic puzzles were a deliberately easy setting: a domain where a verifier can make total guarantees by brute force, so I could think about verifier design without the verifier itself being the hard part. The loop is standard practice now. The interesting question has moved to what, exactly, your verifier is willing to assert.

Next on the list: a quality filter, since right now I only guarantee that a puzzle is solvable and nothing about whether it is worth solving; more domains (polyomino tiling is done, knots and definite integrals are candidates); and checking that difficulty proxy against actual human solvers, so I can stop calling it a proxy.

The repository: https://github.com/hidetzu/verigen