Searching for a Program Instead of Generating One

The question I started with was whether you could get small programs written without a language model and without a GPU. Not as a matter of principle, just as a matter of cost: the tasks are small, the answers are short, and it seemed likely that something cheaper would cover a useful fraction of them.

Two candidates are obvious enough that anyone would name them. Search the space of programs and keep the one that matches your examples, which is program synthesis in its oldest form. Or find code somebody has already written and check whether it does what you want. I priced both, and both closed, and in each case the wall was somewhere other than where I expected to find it.

The code lives in a private research repo, so there is no link to it here, and nothing below names a file inside it. Every figure comes from a recorded run rather than from memory.

Candidate one: search the program space

The setup is an exercise list, karan/Projects, which is a well-known list of practice problems and a fair source of tasks nobody wrote for me. Thirty-eight entries from three complete sections, of which 28 could be specified as a function from a string to a string and became the corpus. The searcher is a typed enumerator over 62 primitives, budgeted at 300,000 candidate terms and 20 seconds per entry, with a maximum term size of 7. Everything about it was frozen in advance, before a single primitive existed: the corpus, the split, the admissibility rules, the budget, and five predictions.

Split by position parity into calibration and held-out halves, so the entries I could look at while building primitives were not the entries it was scored on. The blind arm found terms consistent with the given examples for 6 of 28 entries, and 4 of those were right on held-out inputs. Giving the searcher the entry's title as a hint (a bag of words to bias primitive selection) took it to 7 and 5.

Read across the split rather than down it, and the shape is clearer. On calibration the blind arm got 4 example-consistent and 3 right; on held-out entries it got 2 and 1. The overfit rate, meaning terms that satisfied every example and still failed on inputs they had not seen, was 0.25 on calibration and 0.5 on held-out.

Then the finding that ended the arm. All five entries either arm solved already had hand-written implementations in the same repository. Running the existing tool over the same 28 gives 13 transforms, 10 record-storing apps and 5 refusals, so 13 entries covered; the union of that tool with the searcher is also 13. The marginal coverage of a 1,052-line searcher over the code already in the tree is zero entries, and its honest ceiling is one: Fast Exponentiation, which the biased arm reaches, and which existed in the repo already and was merely not wired up.

What the examples could not tell it

The part worth carrying elsewhere is not the count, it is why the count cannot be improved by searching harder.

Sorting is the case. The searcher returns sort_(toks(in)), which is consistent with all four examples it was given and right on 8 of 12 held-out inputs. It sorts the tokens as text. So -3 5 -1 0 comes back as -1 -3 0 5 where the answer is -3 -1 0 5, and every input with a negative number or a two-digit number is wrong. The correct term is one primitive away, sort_(nums(in)), and it is unreachable, because the wrong one is observationally identical on everything the search was shown and banks first. Check if Palindrome fails the same way on the empty string.

Two of the six example-consistent terms are wrong, and nothing in the examples could have said which. That is not a budget problem and more compute does not touch it. It is a property of specifying a function by examples: the examples admit a family of terms, the search returns whichever member it reaches first, and the ones it reaches first are the short ones. More compute buys wrong answers faster than right ones.

A generate-and-check loop needs a checker that can reject an observationally-identical impostor, which means a property rather than a set of examples. That is a whole other problem, and it is the one I ended up spending most of the project on.

Candidate two: find the code somebody already wrote

The second candidate has a much better reputation, and it is the thing people mean when they ask whether a vector database of code would help.

The mechanism I already had is a behavioural index. You take a function, run it against a fixed ladder of inputs, and record what comes back; two functions with the same outcome vector are candidates for being the same function. It works inside one repository, which is what it was built for: it found a helper duplicating another function's logic under a different name.

Pointed outward it has to survive foreign code, and an earlier round had already priced that badly. Its adapter had to import the containing package and call a positionally compatible function, and 81 of 96 fetched candidates never ran at all. The newer prober never imports the module: it parses with ast, keeps functions passing a purity gate, and executes the function's own source. So the reachable fraction was genuinely open, and I predicted it would reach at least 25 of exp 160's 48 recorded candidates.

It reached 14. That prediction was wrong in the generous direction, which was the third method prediction to miss that way in a single session.

Reach was not the interesting number though. Recognition was: across 48 candidates, one was recognised as the same function as ours (triflescure/is_palindrome, one of the ones the older importing adapter could not even load). Forty-six of the 48 fetched, and none of the 46 archives had drifted since the earlier round recorded them, despite being pinned only at HEAD.

The mechanism behind that one-in-forty-eight is the part I would want anyone considering a code index to read. Of 746 functions seen, 683 (91.6%) never reach a vector at all, and it is the purity gate rather than the ranking that stops them:

A behavioural index keyed on returns-for-inputs has nothing whatever to say about a nullary function, and a sixth of foreign Python is that shape. An embedding index would see the same 746 functions and would rank the ones it cannot run, which is a different failure and not a better one.

And where two functions did get compared, the comparison was mostly about how they break. Over 497 differing pairs the outcome was an answer disagreement 39.6% of the time, a mix 49.1%, and pure failure 11.3%, so 60.4% of pairs have at least one side raising. The case that made me pre-register that category: our count_vowels, written as c in "aeiouAEIOU", against a stranger's countNumber, written as char.lower() in vowels. Both are correct on every string. They are separated by ([1, 2, 3],), where one raises TypeError and the other raises AttributeError.

Inside one repository that divergence is a real inconsistency worth reading, which is why the tool exists. Across foreign code it is noise, at 60%.

The control, and the fix that died in it

The obvious objection to all that is the search. The candidates came from a code search that returned PIN brute-forcers for "pi digits", so low recognition might just be low relevance, and a relevance-improved candidate set is exactly what a vector database supplies. That objection is right; it is testable without building one.

So: hold everything constant except relevance. The prober, the twelve reference functions, the verdicts and the classifier are all imported from the previous round rather than copied, so a difference in the numbers cannot be a difference in the instrument. The candidates become karan/Projects-Solutions, which is other people's own solutions to the same exercise list: 66 Python links across 11 operations, with relevance guaranteed by construction rather than by ranking.

Recognised: 0 of 11.

Two things about the corpus first, because they are honest limits on that zero. Of the 66 links, 49 fetched and the other 17 are dead; a decade-old link list to other people's repositories has rotted about a quarter through. And 37 of the 49 fetched files (76%) define no function at all. They are top-level scripts, n = int(input()) and a loop and a print, because they are solutions to an exercise list rather than libraries. Reach went down, not up, to 8 of 49.

But the substance is in the 11 comparisons that did happen, and it is not about ranking or reach. The disagreement is the return contract. Our pi_digits returns a string and a stranger's compute_pi returns a Decimal. Our collatz returns the sequence and a correct outsider's collatz returns the number of steps, disagreeing at 21 of 31 ladder positions. Our is_palindrome returns a bool and the neighbouring longest_subpalindrome returns a pair of indices. Nothing there is wrong; there is simply no agreed shape for the answer.

Seven of the 11 comparisons were against a helper rather than the file's actual answer (a factorial defined inside a program that computes pi), because the index never reads names. That property is exactly what let it find a duplicate inside one repo, and across foreign files it means the function you wanted is often not the function being compared.

Then the part I would most want to keep. Every witness pointed at the first degenerate input on the ladder: pi_digits(0) is '' in our implementation and Decimal('3') in theirs, and both are defensible. That suggested a clear fix, restricting the ladder to a function's actual domain, and I would have shipped it on the strength of those witnesses. Instead I ran it post-hoc as a labelled probe: drop every degenerate position, 26 of the 31 remain, hold the same discrimination floor. Recognised: 0, unchanged.

The fix I believed in bought nothing, and the only reason I know is that it was run rather than reasoned about.

What generalises

Neither of these is a statement about search or retrieval in general, and the numbers are small: 28 entries for one, 48 and 66 candidates for the other, one language throughout, and a candidate list old enough to have rotted. What generalises is where each wall sat relative to where I would have tuned.

For search, I would have tuned the budget and the primitive set. The wall is that examples cannot distinguish the right term from an observationally identical wrong one, and 2 of 6 consistent terms were wrong with nothing in the examples able to say which. Tuning either knob moves the search deeper into a family it cannot discriminate inside.

For retrieval, I would have tuned the ranking, which is what a vector database improves. The wall is that 91.6% of functions never arrive, and then that two people solving one problem do not produce the same artifact: with the right file in hand, correct, and written for the same exercise, recognition was zero. Agreeing on what the answer looks like is the work, and it is the work whether or not you found the file.

That is the sentence I would carry out of the whole exercise. Both of these are ways of avoiding the question of what the answer should look like, and both of them ran into it anyway, one round later and with a worse instrument for handling it.