August 2026

Attempted Anthropic's performance take-home to complement learnings from Parameter Golf and Language Models from Scratch (Stanford CS336).

Goal was the recruiting bar of sub-1,487 cycles but ended up at 1,064 cycles overall -- 12 cycles better than the highest visible submission at time-of-writing (1,076), which we achieved via:

• SIMD/vectorization, VLIW
• writing custom scheduler to map dependencies in a DAG for instruction packing
• using scheduler to allocate/free scratch memory efficiently
• leverage scratch memory as cache to reduce loads
• load-balancing / maximizing utilization by modifying work to be executable by less-bottlenecked engines
• kernel fusion
• abusing inherent structure in trees
• parameter sweeps on scheduling algorithms to empirically find optimum

The Task: Optimize A Virtual Kernel

The task itself is to optimize KernelBuilder, a small compiler that generates instructions for a simulated processor, so it can accomplish it's task of traversing a binary tree 16 times (for 256 independent inputs) in as few cycles as possible.

The instructions look like:

{"valu": [op1, op2], "load": [load1, load2]}

and each traversal round starts at the root node 0 and executes the following:

node_value = tree[index]
value = hash(value ^ node_value)
index = 2 * index + 1 + (value & 1)

if index >= 2047:
    index = 0

So all 256 inputs traverse the same tree, but paths diverge since each hashed value can choose a different child.

The Machinery

Our compiler, KernelBuilder, reserves scratch register addresses, creates constants, emits arithmetic, load, store and control instructions, and ultimately packs instructions into cycles before returning the final list.

The simulated processor has several independent execution engines:

• Scalar arithmetic (alu) - 12 slots/cycle
• Vector arithmetic (valu) - 6 slots/cycle
• Loads - 2 slots/cycle
• Stores - 2 slots/cycle
• Flow/select operations - 1 slot/cycle

And its vectors contain 8 slots. This gives us two kinds of parallelism:

1. SIMD - we can execute the same operation across 8 values (e.g. hash 8 values in parallel)
2. VLIW - we can do multiple independent operations during one cycle (e.g. scalar arithmetic and loads)

The final piece is our scratch memory -- in a world where this was unlimited, we'd load as much into scratch as possible and skip load/store instruction overhead.

But here we're limited to 1,536 words of scratch space, meaning we'll have to prioritize what we store to minimize movement, and make transfers efficient.

With our task and levers in mind, let's run the baseline and make our first optimization.

Vectorizing the baseline (147,734 -> 22,095 cycles)

The baseline processes one input at a time, giving us 147,734 cycles.

The immediate optimization is to use the valu engine to perform the same hash arithmetic on 8 values at a time. While this involved creating new functions (e.g. scratch_vconst) to accommodate 8-wide temp and const values, it yielded what will likely be our biggest speedup: 147,734 -> 22,095 cycles.

Worth noting this was not a full 8x improvement b/c tree-node loads are still sequential.

vload can only read neighboring memory, and while our values are stored next to each other, the tree addresses they store are quite different -- meaning each needs a separate load:

But the outputs go back into neighboring input-array cells, so we can write them with one vstore.

Minimize copying (22,095 -> 18,225)

Because we allocated space for only 8 indices and values (to be reused for each group of vectorized inputs) we waste cycles loading and reloading values each time.

Instead, let's give each group dedicated homes in scratch memory to reclaim those cycles: 22,095 -> 18,225.

Instruction Packing (18,225 -> 12,623)

With vectorization and loads reduced, let's see what independent instructions can be packed into the same cycle.

Several hash stages compute two independent expressions from the same old value:

left = value ^ constant
right = value >> shift
value = left ^ right

moving those into the same cycle drops 18,225 -> 15,183 cycles.

As mentioned earlier, each SIMD group needs eight unrelated tree-node loads.

Since the load engine has two slots, we can pack these into four cycles instead of eight, bringing us from 15,183 -> 13,135 cycles.

The final instruction-packing optimization came from the next-node calculation:

branch_bit = value % 2   # 0 means left, 1 means right
base = index * 2
next_index = base + 1 + branch_bit

The first two calculations here are independent, so we can run them in the same cycle via two slots of the valu engine, saving us 1 cycle x 32 groups x 16 rounds = 512 cycles, or 13,135 -> 12,623 cycles.

{
    "valu": [
        ("%", vtmp1, tmp_val, vtwo_const),
        ("*", tmp_idx, tmp_idx, vtwo_const),
    ]
}

Kernel Fusion (12,623 -> 10,061)

Looking for additional instruction-packing opportunities uncovered an algebraic improvement in the hash function itself.

Some stages were:

(x + c) + (x << s)

which can also be expressed as (modulo 32 bits since overflow wraps around):

x * (1 + 2^s) + c

meaning we can use a single multiply_add instruction for that, turning three operations over two cycles into one operation: 12,623 -> 11,085.

Similarly, the child index calculation uses unnecessary equality checks and conditionals:

2 * index + 1  # Left child, if value is even
2 * index + 2  # Right child, if value is odd

which can be fused into a single instruction by using the fact value & 1 yields 0 for even and 1 for odd:

next_index = 2 * index + 1 + (value & 1)

reducing 4 ->2 cycles per group per round, bringing us from 11,085 -> 10,061.

Leverage tree structure (10,061 -> 8,492)

Let's use predictable structure to compress further, a height-10 tree has 11 levels.

Therefore every traversal wraps after rounds 11, 22, 33, and so on regardless of values.

Instead of a conditional we can just emit a reset on multiples of 11, bringing us from 10,061 -> 9,002.

if (round + 1) % 11 == 0:
    emit_reset()

Similarly, on rounds 1 and 12 all 256 inputs are at the root. So we can load the root once and reuse it to drop from 9002 -> 8684 instructions.

Doing this on rounds 2 and 13 (which must be at node 1 or 2) we can again cache the nodes, reducing from 8684 -> 8492.

Time For A Scheduler (8,492 -> 2,393)

At this point each SIMD group is optimized internally, but the groups are still mostly processed one after another, wasting the processor's width.

For example:

A better schedule would overlap them so the vector, load, flow, and store engines can work simultaneously.

First Step: Private Temp Vars

Currently we have every group reusing the same temporary registers.

Allocating private temp vars for each active group enables independent processing, turning each SIMD group into an ordered stream.

Different streams may overlap, but operations within one stream remain ordered.

The Scheduler Itself

For our scheduler, we will process one round at a time, since each of the 32 SIMD groups executing multiple instructions per round.

(A reminder, there are 16 rounds of calculations for all 256 inputs, which we've separated into 32 SIMD groups. And each group in any given round will need to execute instructions fetching addresses, load, XOR, hash steps, child update, etc)

Within each round, we'll start with scheduling two groups entirely until both are finished, then move to the next two, etc.

Our scheduler will:

1. create an empty cycle
2. examine the next available bundle from each stream we're processing in parallel (2 to start)
3. take whichever operations fit in the remaining engine slots
4. emit the packed cycle
5. advance streams whose bundle completed

And we'll do this until the first two groups are done, then the next two, and so on until all 32 SIMD groups are complete for round 1. Then repeat this for round 2,3... to 16.

Our scheduler, with streams arg being the number we'll process in parallel (parameterized so we can experiment with increasing values):

Extending the final instruction list using our packed instructions via the scheduler:

Running this got us to 5,212 cycles. Results from increasing the number of groups (just a variable change):

• 2 groups -> 5,212 cycles
• 4 groups -> 3,636 cycles
• 8 groups -> 2,928 cycles
• 16 groups -> 2,566 cycles

Unfortunately 32 groups in parallel requires reducing our scratch memory usage as we were maxed out.

Realizing some of the temp vars were read before the next calculation, we reused the variable, reducing from four temp vectors to three.

With the ability to run 32 groups we got our best score of the bunch: 2,393 cycles

Remove Round Limitations

One inefficiency created by our scheduler is that we wait for all groups to complete round 1 before starting round 2, unnecessary.

Group 0 only depends on group 0's previous round.

So we scheduled each group's complete 16-round stream at once.

This brought us from 2,393 -> 2,002 cycles.

Including input loads and final stores inside the scheduling logic brought us from 2,002 -> 1,787.

Small Reductions

Realizing we can reuse the child calculations branch bit instead of recomputing a condition (swapped left and right because the values have opposite values after AND-ing with 1):

1,787 -> 1,735 cycles

We also switched to one-based node indices to eliminate an extra operation.

While this doesn't actually reduce cycles needed per group for this calc, removing this operation frees slots for other groups letting our scheduler-optimized workload finish 54 cycles sooner.

We also removed final stores and last child update (since not needed), as well as initial index loads since everything starts at the root.

Overall bringing us from 1,726 -> 1,606 cycles.

Scheduler Improvements (1,606 -> 1,423)

Currently our bundles don't allow splitting, but treating these as atomic wastes the slots that could potentially be doing partial work.

Let's allow "safe" bundles to issue one operation now and the second later (note: we don't do a safety check, but enforce through our safe construction of bundles).

Brings us from 1,606 -> 1,543 cycles.

Avoid Stream Starvation

Looking at utilization our current scheduler allows early streams to monopolize slots, meaning the final streams ran almost alone in a sparse tail.

But the solution to this wasn't immediately obvious, since round-robin had poor results from forcing groups to synchronize and request the same engines at the same time.

So we want some staggering, e.g. one group loading while another hashes so there isn't an engine crunch. But we also need to shift prioritization periodically to avoid leaving stragglers.

Let's do a parameter sweep of:

• Period - how many cycles before a priority shift, tested 24-64 for 40 choices
• Offset - which stream starts with priority, test all 32 choices

From these 40 x 32 = 1280 configurations we found period 38 with offset 0 to be the best, how this would look in practice:

Implementation brings us to 1423 cycles.

Optimizing Setup Costs (1,423 -> 1,360)

With our hot loop pretty much full, setup costs now seem a high-ROI section to attack with instruction packing and fusion:

• Eliminate unused header fields - since the kernel generator already knows the rounds, tree height, batch size etc -- only need where tree values start and where input values start
• Load two scalar constants per cycle - just packing the load engine for max efficiency
• Batch vector constant broadcasts - since we have six VALU slots per cycle lets pack this engine
• Overlap loads with ready broadcasts - loads and broadcasts use different engines so we can pack them, but we must make sure the load happens in a previous cycle

• Move batch offset into instruction - instead of burning cycles adding the offset from scratch, let's just add the literal value to the pointer in the instruction
• Parallelize adjusted base calc with tree node loading - neither of these requires the other's result so we can put them in the same cycle via the ALU and LOAD engines

Overall these took us from 1,423 -> 1,360 cycles

Success, but can we do better?

We started at 147,734 cycles and achieved a 108.6x speedup to 1360 cycles, with 1482 out of 1536 available words used in scratch memory, 7990 vector slots and 2610 load slots.

Anthropic mentions 1487 as noteworthy, with 1363 being the best Opus 4.5 got in an improved harness, and we've improved this by 3.

But the best human performance was apparently substantially better than this.

So how good can it get?

Well if we divide the 7990 vector slots by 6 we get 1332 cycles as our floor, meaning our solution is only 28 above that. Pretty good.

But this assumes our current instruction set is optimal... looking at the execution engines, we've maxed out vector and loads but largely left the scalar engine unused despite it having a capacity of 12 operations/cycle.

Revisiting Scheduling For More Task Granularity

Before we pack the scalar engine, let's revisit our scheduler to see if we can improve the granularity of tasks to increase our potential efficiency gains.

Right now our scheduler can overlap groups and split bundles, but is limited to the next bundle in a given group -- i.e. it can't skip an unfinished bundle to issue an independent operation farther down that group's list.

This is because we rely on group identity and ordering within that group for safety, but really all that matters is when a task's inputs are ready.

So let's take the following approach:

1. Have all SIMD groups append operations to a centralized list self.ops
2. Dynamically derive dependencies via the directed acyclic graph (DAG) described by these operations
3. Use this graph to assign operations to cycles

Apart from increased flexibility of existing operations, it also has the advantage of bringing constants, setup, and traversals into the same scheduling system.

Reclaiming Scratch Memory

While redesigning the scheduler to maximize task independence, another optimization presented itself: reclaiming unused scratch memory.

Scratch memory is only needed until that value is read by the next step, after which it's just wasted space.

Until now we haven't reclaimed it, but since we're dynamically deriving dependencies, we can also calculate and assign physical scratch, and free it up once no longer used -- putting the additional space towards cache to reduce loads further.

Putting this altogether we have our new build_kernel():

1. All SIMD groups append operations to self.ops
2. Derive dependencies graph
3. Assign operations to cycles using graph
4. Assign physical scratch using graph
5. Emit final instructions

Interestingly, implementing this actually regressed in cycles, taking us from 1360 -> 1377 cycles.

But it dropped scratch usage from 1,482 to 864 words, creating room for our subsequent caching experiments.

Caching and Scalar Executing Our Way To Victory

With our scheduler working let's start offloading arithmetic to the scalar ALUs.

We started with address arithmetic and branch-bit extraction, first by adding an optional scalar flag to our vector helper that emits 8 alu engine ops instead of a single valu

then enabling it for address and parity calculation:

but this only yielded a small cycle reduction: 1,377 -> 1,349.

Memory efficiency into cycle gains

Switching to caching to see if higher-ROI existed there, we cached another tree level using the lookup mechanism we implemented previously:

and then just changing the depth variable for what we cache (since we had the scratch memory overhead from our increased task independence/granularity):

and saw a whopping 127 cycle reduction from 1,349 -> 1,222 cycles.

Now we're getting somewhere.

Note, while there were slightly fewer operations, the enormity of this speedup primarily came from moving work from crowded load slots to more available flow slots to increase engine utilization.

More scalar ALU packing

Switching back to scalar utilization let's try automatically moving suitable vector operations onto available scalar ALUs by building this into our scheduler.

If there are empty slots the decision is easy, but what if there are genuine scalar operations that need to run? The complexity here is coming up with a priority algorithm or heuristic.

Skipping multiply_add and vbroadcast instructions (due to extra scaffolding needed), we'll fill the valu slots first, then compare the highest-priority vector operations still waiting against the best native scalar operations and already-partially-issued scalarized vectors.

For prioritization, we'll target operations that occur earlier (i/n \* schedule_weight) and have longer dependency chains (depth array ) to unblock later work.

Scores are calculated once for each operation before scheduling and then reused for native scalar work, vector work, and any lanes split (lower is better, with keys containing the score in a tuple):

then we use it to issue valu and alu instructions based on those scores, the heap represents a waiting line of ready work ordered by priority:

For vector operations converted into scalar, scalar_remaining[i] starts at eight and decreases as lanes are scheduled. Only when it reaches zero is operation i marked completed, allowing its consumers to become ready next cycle.

This automatic offloading knocks off 68 cycles (1,222 -> 1,154).

Selective and more-efficient caching

At 1,154 cycles we wanted more caching gains, but although keeping more nodes in scratch memory eliminates repeated loads, it also requires more selection work since we can't load dynamically-crafted scratch memory addresses at runtime like we can with load and main memory.

So how can we make cached traversal cheaper?

There's a repeated hash operation, an XOR with a fixed constant. The next round immediately XORed that result with a tree-node value.

Since XOR can be regrouped, we moved the constant into the cached node instead, changing: (h XOR C) XOR node into h XOR (node XOR C)

Prepping each cached node once, then skipping that operation in eligible hashes and saving two cycles (1,154 -> 1,152).

Next, instead of broadcasting a node into eight copies and modifying the vector, we modified the scalar node first and broadcast the result. While this actually regressed one cycle (1,152 -> 1,153), it gave us prepared scalar values we could reuse in the next step.

Finally we expanded the cache by another tree level, meaning we have to choose among 16 possible nodes.

Why?

Recall that we have no way to dynamically load a scratch memory address determined at runtime -- unlike load it must be included in the instruction. So instead we effectively implement the cache logic of val = cached_nodes[offset] but by re-creating the branching using the saved branch bits.

But isn't this more expensive than just a regular load from main memory?

Yes, we have 15 operations now (since our fixed instructions have to prepare every possibility), but keep in mind we're not trying to reduce operations, we're trying to reduce cycles, which are bottlenecked on specific engines.

If we kept all 15 selection operations as is, competing for the flow engine's single slot, then all we've done is swap one congestion source for another.

But remember how we modified our cached node above to retain encoded_scalar?

This means we now have named scalar versions of both encoded siblings, which we can pre-compute the difference for:

difference = encoded_left - encoded_right  # scalar ALU
difference_vector = broadcast(difference)

and use this to achieve selection via a multiply_add:

selected = bit * difference_vector + encoded_right_vector

which means we can offload the flow engine work (which only has one slot per cycle) to the valu engine which has six slots that can run in parallel!

So despite having more instructions, we can actually complete more work in parallel and therefore in fewer cycles.

But how many before the flow engine (aka cached selection cost) exceeds any benefit?

Tuning Our Cache Selectively

Instead of requiring an entire level to be cached, we can run a parameter sweep to determine how many N of our 32 groups we should cache at this level.

The first N would use caching, the remaining would keep loading from memory, giving the scheduler plenty of work to overlap.

We targeted the second visit to this level, in round 16 (which is also the final round, meaning we can store the result w/o preparing another traversal).

We ran a complete experiment for each configuration and counted cycles, the results from 280 configurations:

Which empirically give us an optimal value of 20 or 22, beyond this the additional selection work outweighs the benefit.

Finally we have the big gains from this caching optimization, a 66-cycle reduction bringing us from 1,154 -> 1,088 cycles.

Final tuning and optimizations

At this point there weren't anymore opportunities for big gains (that I could see at least) so shifted focus to tuning.

Additional parameter sweeps with different weights to account for our new cache selection ended up changing weight from 200 to 300 and flow_weight from 1 to 6 to prioritize flow operations.

(Since cached selections share a single flow slot, their placement can delay everything downstream -- 16 cycles saved)

Next we found a potential independence optimization in how the next memory address was calculated, where it initially depended on the completed hash:

hash → branch bit → child index → memory address → load

But most of the next address is already known, the hash just decides whether to use that address or the following one.

Using this knowledge we can change the dependency into:

which doesn't create immediate cycle gains, but reduces scratch from 1,248 to 1,195 words thus creating an opportunity for the scheduler to exploit since the operations can now run in parallel. Re-tuning with this independence gained us four more cycles.

Finally, revisiting the cache coverage parameter sweeps after these changes found the optimal number of selectively cached groups to be 23 instead of 20/22, saving another four cycles.

Final score: 1,064 cycles (beat top submission by 12)

Overall these tuning changes netted a deduction of 24 cycles to get our best and final score:

1,064 cycles.

At time of writing the best score we see in the Github issues is only 1,076 cycles, meaning we've achieved the top score of visible submissions (though very possible someone scored better privately).

Some takeaways:

• the key was identifying independent work and getting it to run efficiently
• our biggest gains came from the scheduler: mapping dependencies, determining optimal execution, etc
• more caching wasn't always faster: it removed loads but added selections, w/ the selection engine eventually becoming the bottleneck
• bottlenecks kept shifting in general
• converting work to be executable in less utilized engines provided valuable flexibility
• gains weren't always linear, improving the scheduling algorithm initially worsened performance until we used the reduced scratch overhead for caching
• we had to use both reasoning & empiricism to find optimal policies