@Niccolg92: An interesting fact associated with this post. But first some context: Upon being hired by OpenAI, Alisa Liu has shared…

An interesting fact associated with this post. But first some context:

Upon being hired by OpenAI, Alisa Liu has shared a blog detailing her job seeking experience and study notes, including the necessity to sharpen her LeetCode (LC) skills. Across the replies, the never-ending debate about LC’s relevance in today’s world as usual got ignited.

Given this premise: in the recently released GLM-5.2, one novel architectural feature considered is IndexShare, which aims at further sparsifying DeepSeek Sparse Attention (DSA) by subsetting “layers into a small set of Full layers that run their own indexers and a majority of Shared layers that simply reuse the nearest Full layer’s top-k indices.”

In order to identify which layers should be Full or Shared, in the main corpus of the paper, they propose a combination of training-free and training-aware methods, ending up however considering only the latter method combined with uniform interleaving in GLM-5.2.

In Appendix C of the same paper, though, here attached, they also report how they tried a Dynamic Programming formulation to address the problem.

Consider a DSA model with N layers, and on a calibration set perform N forward passes. Given a couple of layers (i, j), i > j, calculate:

“1. the core attention output at layer i when using layer i’s own indexer (i.e., the original model), and

2. the core attention output at layer i when reusing layer j’s indexer (i.e., as if layer i were an S layer sharing from layer j).“

“This yields an N × N lower-triangular similarity matrix S, where S_{i,j} quantifies how well layer j’s index can serve as a proxy for layer i’s own index. Intuitively, if S_{i,j} is close to 1, then layer i can safely skip its own indexer computation and reuse the index from layer j with minimal distortion to its attention output.”

As visible from the pictures, the problem can indeed be solved via Dynamic Programming: “Let dp[i][k] denote the maximum cumulative similarity achievable for layers 1, . . . , i using exactly k F layers, with layer i being F itself”.

How do you transition to dp[i][k]?

Consider all the previous j F layers. Score (in terms of similarities) the old best pattern ending at j that uses one fewer F layer, plus the value of making all layers between j and i S from j, and pick the best j.

While this methodology turned out to be suboptimal, in reading it, it definitely made me think of a possible LC challenge.

Overall, more a curious coincidence than a statement over LC’s relevance in today’s world: up to the readers evaluate whether LC-like challenges still happen to be relevant.

Here attached the previously mentioned DP optimization. Below also a review I shared two days ago of IndexShare and Alisa Liu’s original post, including her excellent blog on her jobseeking journey.

Alisa Liu’s post:

My review, more in details, of IndexShare:

And here, also from the paper, the complete DP formulation of the problem: