Questions about boundaries of chunks

[Arthur-Null]

From eq. (4) in the paper, it seems that the boundaries are the starts of chunks, as the representation of the start of a new chunk should be very dissimilar from that of the end of the last chunk. However, the design of downsampler, smoothing module and upsampler mostly viewed the boundaries as tails of chunks (can be clearly viewed in Fig. 13). Why does this inconsistency exist? How should we understand the relationship between boundary and chunk?

[hmk114]

I have the same question! Why don't we take the representation at the end of each chunk, which hasn't experienced a sudden change in latent space at boundary and potentially embed information of the previous chunk with better integrity? Looking forward for authors' further clarification :(

[main-horse]

1. The inner $M$ should only execute once per chunk
2. The result of inner $M$, per chunk, should be used to predict all bytes in the chunk, up to and including their tails.
3. (2) => the result of inner $M$ must be available after the first input byte to predict the next byte of the chunk

@hmk114 I would suggest thinking about the causality of your suggestion. I believe what you are suggesting is only possible for non-causal H-Net.

[hmk114]

Oh, I see. So from figure 2c in the paper, if I didn't take it wrong, on the encoder side it's indeed the last byte of a chunk that is selected to pass the main network M (for example o in pro), and after M that byte is transformed to the first byte of the next chunk (d in duct) and is used to predict all bytes in it. But I'm still a bit confused: why would we expect the chunking module (on encoder side) to assign high dissimilarities to the last and second to last bytes of a chunk, instead of the last byte of a chunk and the first byte of the next chunk?

[main-horse]

I don't like figure 2. Here is how I would explain it:

1. The encoder $\mathcal E$ does not have a concept of a "chunk". It simply assigns each byte a vector $\hat x_t$
2. When an output byte ($q_t$) from the encoder is sufficiently different from its previous byte ($k_{t-1}$), we programmatically decide a new chunk has started, and that the byte's vector $x_t$ is all $\mathcal M$ can see.
3. After $\mathcal M$, we permit the concept of a "chunk" -- it is the boundary of the first byte selected in (2), up to but excluding the next byte selected by (2). This also corresponds to the top side of Figure 2b.

From this perspective, it is quite easy to explain how chunking should ""work"" -- for example, if the encoder was directly trained to group UTF-8 bytes to CJK, it would only need $W_q$ to classify what byte vectors look like the 2nd byte, and for $W_k$ to classify what byte vectors look like the 1st byte per hanzi.

[mutiann]

I have exactly the same question as well! I fail to see the causality issue if we take the last byte in the chunk. I think we can "update" or "recompute" the current state in the main network given the new input vector from the "new" last byte (e.g. for transformers, to recompute the $k_t$ and $v_t$ at time $t$ in the KV cache given the new $x^{s+1}_t$, instead of appending a KV pair). After all in the ablation studies in E.1, the authors have already tried other downsampling approaches, e.g. mean/max pooling, which involves "future" bytes. I'm a bit confused why the last byte approach is not considered as part of the ablation study...For me it seems to be more intuitive to predict the next chunk (e.g. word/character) given everything in the current chunk by a causal network, compared to predicting everything inside a chunk using the first byte, which is much less informative.
Also, it is a bit clumsy for me to expect $W_q$ to detect the 2nd byte and $W_k$ to detect the 1st byte in a CJK character, given that there are more natural boundaries (like the 1st byte of the current character and the last byte in the previous character).

[main-horse]

I fail to see the causality issue if we take the last byte in the chunk

Start with <BOS>.

The encoder says <BOS> is the start of a new chunk.

Now, how do you get the next byte in that chunk?

---

You can do recurrent solutions, but those make pretraining drastically harder. Start with single-network-forward-per-batch as a constraint.

[hmk114]

But in this case why not treat <BOS> alone as a separate chunk, so we can pass it to the main network and get the next byte (as the first byte of the next chunk)? I cannot see why this bothers pretraining...

[main-horse]

The previous statement was not specific to <BOS>, it applies equally to any first byte of a chunk.

It is my answer to @mutiann, who asks why we cannot use the last byte in a chunk, where the trivial answer is that it is not possible to obtain the 2nd, 3rd, ..., bytes, without first having defined what the input chunk to the main network was during the first byte.

[sukjunhwang]

These are great points, and as many of you guys mentioned, we actually have experimented with selecting the previous token at each boundary (i.e., a one-step look-ahead), but it performs much worse.
From our analysis of many qualitative results, our interpretation of the boundaries is that they capture not only the context of the completed chunk (preceding inputs), but also tries to hold the upcoming context. To be specific, in Fig 2, the information embedded in the vector at _ can be viewed as a mixture new_ and pro. Therefore, compared to the vector at w, the transition of context occurs as _ starts to capture the upcoming context. (This is why the boundaries are drawn as both the start & end of chunks in Fig 4.) It was very difficult put all these concepts in Fig 2, so had to compromise as the current version.

[malcolmsharpe]

I agree with everything said here about causality preventing H-Net from having lookahead. But something worth noting is that BPE Transformers actually have unbounded lookahead using a sneaky trick. (BPE Transformer lookahead is discussed in the H-Net paper appendix in the section "tokenization bias".)

The trick BPE Transformers use for unbounded lookahead is that boundaries are determined differently during prompt ingestion versus generation. During prompt ingestion, the boundaries are chosen by the tokenizer, which has unbounded lookahead. During generation, the boundaries are chosen by the network (since it's emitting tokens rather than bytes). Implicitly, the network is encouraged by training to predict token sequences that are consistent with greedy tokenization, but it doesn't assign zero probability to other sequences (as also mentioned in "tokenization bias").

It seems to me that H-Net might be modifiable to use a similar trick for unbounded lookahead, though the alteration required would be major, and my idea is still half-baked. The general idea would be to have the boundaries predicted by both a bidirectional network (during prompt ingestion) and the decoder (during generation). For training (which involves exclusively prompt ingestion), a consistency term would be added to the loss to encourage the decoder to predict the same boundaries as the bidirectional network.